9 ms·

Pure Operation-Based Replicated Data Types

86 points by blopeur 9y ago

burntsushi 9y ago
I've been following the literature on this topic for a while now, and I've always wished for more examples of actual systems built with these techniques. Are there any? What kind of scales do they deal with? Are there any write-ups on them? (I know of at least one good one[1].) In particular, I've wondered how a simpler solution to the problems posed in this paper stacks up. At what point does it fail? e.g., Consider: * An op based model. * A client-server architecture (not p2p). * Operations are assigned a total ordering by a central server. * Given any two dependent operations A and B, A is always transmitted before B. This still gives you a lot of the stated advantages of an eventually consistent system, where each client communicating with the server will eventually converge even if they all temporarily diverge. The central server and total ordering is a key ingredient, because it's what lets you guarantee ordering between any two causal operations by having the server "choose" an ordering. I'm naturally interested in trade offs. For what use cases does the central server model break down? Is it still useful for other things at lesser scales? [1] - https://medium.com/@raphlinus/towards-a-unified-theory-of-operational-transformation-and-crdt-70485876f72f https://medium.com/@raphlinus/towards-a-unified-theory-of-op...
- thdxr 9y ago
  What happens in your scenario if operation B arrives hours later? It's hard to provide reliable ordering in practice because networks aren't dependable and things that happened earlier may show up later. I work on a realtime database and we heavily rely on CRDTs for communication. We can't have a central server because our goals are fault tolerance and high throughout. If you're more curious about the subject look into Riak. Afaik that is the biggest project built with CRDTs
  - marknadal 9y ago
    @thdxr, which realtime database do you work on? I know some people at Riak/Basho who are now at MIT, they are helping us formalize our CRDT ( https://github.com/amark/gun/wiki/Conflict-Resolution-with-Guns https://github.com/amark/gun/wiki/Conflict-Resolution-with-G... ). We were chatting just last night and he said that Riak actually lacked proper CRDT in many settings (for example, secondary indices would produce non-deterministic results depending on order).
  - burntsushi 9y ago
    > What happens in your scenario if operation B arrives hours later? It's hard to provide reliable ordering in practice because networks aren't dependable and things that happened earlier may show up later. I guess I'm trying to figure out why this is a problem. If operation B shows up hours later, then the client simply doesn't know about B until then. But since my stated design requires that dependent operations are delivered in order, we have that any other operations are necessarily concurrent with B, so it shouldn't matter when B is "evaluated." > I work on a realtime database and we heavily rely on CRDTs for communication. We can't have a central server because our goals are fault tolerance and high throughout. > If you're more curious about the subject look into Riak. Afaik that is the biggest project built with CRDTs Yeah, I'm definitely aware of Riak. I guess I'm more interested in the systems layered on top of these components. i.e., What problems are they trying to solve? For instance, what if you could relax your requirements? Maybe: throughput/latency only need to be good enough for web response time to end users.
    - im_down_w_otp 9y ago
      For the most part CRDTs of all types solve primarily one problem. The "lost update" problem. When I worked with CRDTs---even inventing a new one based on R*-trees---they were most useful for objects/structures that needed constant mutating by lots and lots of participants concurrently where it made sense to trade constant coordination/protection overhead for lazy-evaluation/merging. Like in a settlement ledger, or massive leaderboard, or indexing structure, etc.
      - burntsushi 9y ago
        Interesting, thanks for sharing that!
- zzzcpan 9y ago
  Central server for ordering would require you to always wait for its decision on every operation, which adds latency, limits throughput and reduces availability, not to mention how much complexity it adds, compared to something as simple as vector clocks.
  - burntsushi 9y ago
    I don't see how you need to wait. It's still an eventually consistent system. Any client can build up their own replica of operations and synchronize with the central server at any time. I'm not sure I see the additional complexity. With a central server, you get to enforce a total ordering automatically across all operations. In any case, what I'm looking for is actual data. I implicitly understand that a central server won't scale as well, but that's not particularly interesting to me. For example, what if my requirements on throughput are very low? I want to know the breaking point. So I guess I'm looking for an experience report from someone who has actually gone through this process.
    - zzzcpan 9y ago
      Operations require sort of versions to synchronize, these versions is where ordering comes from too. This is important because since networks are asynchronous messages can arrive to this central server at different order. So, the way to achieve order with central server and being able to synchronize operations is to ask that server and wait for its decision. Not really that simple nor even usable. Instead the simplest and the most naive way to do this is to use timestamps for versions, still without a central server though. But time is not really possible to synchronize, so instead logical clocks should be used, like lamport timestamps, vector clocks. (And yes, I've been through this)
      - burntsushi 9y ago
        If you have a single logical server, then it chooses the ordering, but a single client doesn't need to ask the server for the ordering of any operations generated locally: it can pick the order because it determines the relative ordering of those operations. A client could be disconnected from the network for hours and re-synchronize at some later point in time and it all would work just fine. The only time the client needs to connect to the server are when the client wants to publish updates, or when the client wants to receive the updates. If you only need to do that once every 10 seconds (or even once every second), does that make a client/server model workable?
- runT1ME 9y ago
  You need a server, which is a single point of failure. If you want redundancy, you now need a quorum in the event of a split brain. CRDTs have the advantage of not needing a quorum in event of a split brain. There is no way to 'lose' information. In addition to being resilient to network split brain, this allows you to make performance gains at the sacrifice of consistency, where you could buffer your updates to other nodes. Operation based CRDTs do seem more limiting compared to State Based though, so you're at the mercy of your data structure being able to be represented as a CRDT.
  - burntsushi 9y ago
    Sure, but let's say I was OK with a single point of failure. Or let's be more specific and say my central server is a PostgeSQL instance. > In addition to being resilient to network split brain, this allows you to make performance gains at the sacrifice of consistency, where you could buffer your updates to other nodes. My scheme allows this too, no?
    - runT1ME 9y ago
      > Sure, but let's say I was OK with a single point of failure. I cannot imagine designing a system for production use where anyone is OK with a single point of failure being a single instance of a machine. I mean if we're playing hypothetical games you don't need a distributed system either, just get one giant instance and put everything on it.
      - burntsushi 9y ago
        I'm trying to distill the design down to its essential components, and then figure out when it will break. If you're going to stick on this point, then let's imagine I have a PostgreSQL setup with replication, such that if any one fails, I can fall back to another. I primarily want to put this in the context of what problems folks are solving with operational CRDTs to get a sense of the scale that requires them. > I mean if we're playing hypothetical games you don't need a distributed system either, just get one giant instance and put everything on it. I guess the requirements need to be more explicitly stated. You need to at least be able to support multiple simultaneous clients interacting with the system, where any client could disconnect for some period of time.
- naasking 9y ago
  Consider a version control system where you had to communicate with the server for every commit, branch, merge, etc. That's how it used to be, and it was painful. Distributed version control relaxes those constraints with better merging to ensure commits are commutative. Now take that property and extend it to general programming, and you have similar advantages with eventual consistency. It's harder to see with typical concurrent abstractions, but Microsoft's concurrent revisions explicitly models their concurrency abstractions around distributed version control. Their papers are worth a read if you want ideas, data and inspiration that concurrency and distributed programming can actually be easy.
  - burntsushi 9y ago
    I think I've done a bad job at communicating my design because it's perfectly consistent with what you've said. My proposed design is a client/server model, but that doesn't mean it isn't distributed. Each client can still operate on its own for as long as it wants, and it chooses to synchronize with the central server whenever it likes. (In fact, this is quite similar to most peoples' workflows with Git/Github, and I certainly wouldn't call that painful.) In any case, thanks for the pointers about the Microsoft research. I don't think I've seen that. I'll check it out.
    - naasking 9y ago
      See here for a comprehensive review of CR: http://lambda-the-ultimate.org/node/4699 http://lambda-the-ultimate.org/node/4699 Each client can operate on its own what though? If they have some kind of private copy of the data, then how do you resolve conflicts? CRDTs are about doing this automatically by restricting the types of changes clients can make. Concurrent revisions permit arbitrary changes so long as you provide a merge function to make them commute. I think you're just hand-waving a lot of the complexity away by using "synchronize" without explaining what is synchronized and how. That's where all the complexity in distributed computation stems from.
      - burntsushi 9y ago
        > Each client can operate on its own what though? Imagine the fundamental representation of your data structure is a sequence of operations. From those operations, you can generate your model. A really simple application of this is a graph, which is just a set of vertices and edges. So if you have these operations VertexAdd { id: fooID, label: foo } VertexAdd { id: barID, label: bar } VertexAdd { id: quuxID, label: quux } EdgeAdd { src: fooID, dst: quuxID } where the ids generated are unique (say, uuids). The corresponding model is just the graph: Graph { vertices: {foo, bar, quux}, edges: {{foo, bar}}, } You might imagine operations to remove vertices and edges as well. Many operations are commutative (add vertex), but some pairs of operations don't commute, e.g., add vertex/remove vertex. As I understand that, that's the central problem this paper is trying to address via CRDTs. What I'm saying is that the total ordering imposed by the server makes this concern moot, because the server always picks one sequential ordering. Let's say there are multiple simultaneous clients editing our graph structure above at the same time. Let's consider an example of a pair of operations that commute. One of them decides to remove vertex quux while the other adds an edge that connects quux to foo: client1: VertexDelete { id: quuxID } client2: EdgeAdd { src: quuxID, dst: fooID } If both clients attempt to update the server with these new operations, then the server will declare one ordering as true and send the resulting operations back to the clients with the correct ordering. The clients must then adjust. In this case, the outcome is the same regardless of the ordering chosen (because you can't draw an edge to a vertex that doesn't exist). What about the case when two operations are not commutative? Well, that means they are dependent, which in turn means that every client receives them in the order in which they were applied. An add/delete vertex is one such example, because the client doing the delete must acquire a vertex ID to give to the VertexDelete operation, but the only way to acquire the ID is to observer the VertexAdd first. Another example of dependent operations is attaching meta data to vertices, e.g., client1: VertexAdd { id: anotherID, label: Another } VertexLabel { id: anotherID, label: Changed } In this case, VertexAdd/VertexLabel are dependent, but the Label operation requires the vertex ID. Now of course, clients can misbehave. There's no reason why a client couldn't generate the ID and add operations in this order: client1: VertexLabel { id: anotherID, label: Changed } VertexAdd { id: anotherID, label: Another } But if we can assume well behaving clients, then this should be OK! And even if clients are misbehaving, then the process of turning the operations into a model can simply drop operations like VertexLabel because they reference a vertex that doesn't exist.
- acjohnson55 9y ago
  We use it for pretty basic purposes -- just replicating emphemeral data across our cluster, for debug settings, flash messages, etc. If the whole cluster goes down, no big deal.
- ryuuseijin 9y ago
  What you describe looks a lot like a Google Wave like OT system. Wave-style OT is eventually consistent, like CRDTs, but you need a central server to give the event history a total order. This is necessary because Wave-style OT is a 1-1 model: clients are 1-1 connected with the server, but not with each other, which would be n-n, which is what CRDTs can do. The total order of the central server can make the system simpler and more efficient, but by itself it doesn't solve the problem that Wave has, which is allowing a client to edit his text/message without being interrupted by network latency/interruptions -- imagine typing a letter and having to wait for the server to acknowledge that keypress with >100ms latencies. To solve this problem, you still need some form of xform/merge algorithm that OT and CRDT systems provide. EDIT: I assumed you were not familiar with OT systems since you didn't mention it in your post, but now that I followed your link I can see that you are. In that light, it seems your comment is more a question about what the tradeoffs are between OT and CRDT systems rather than whether a central server can solve all problems without xform/merge logic. One tradeoff that comes to mind when thinking about OT and CRDT systems is in the way operations track locations in the datastructure. In OT systems you have offsets (small), in CRDTs you have uuids (large) or dynamically growing identifiers (usually small but possibly large). This has implications for the byte-size of operations or the in-memory datastructure. Another is that CRDTs have a pruning problem. It has been some time since I looked at CRDTs, but I remember that Wave-style OT didn't have the same problem due to the central server. The pruning problem can cause a CRDT to grow larger than it needs to by forcing it to keep more historic data around just in case it gets an old operation it hasn't seen yet. The central server solves this problem by guaranteeing that it will have sent you all old operations before sending you a newer one. If you know all actors in a n-n system you can also solve this issue, but in an unbounded n-n system I didn't see any way this issue can be solved when I was researching it. EDIT2: Just want to add that there are lots of other problems that are more practical than theoretical. For example, authorization, authorative copy of the data, REST API, things like that, but that would depend more on the exact use case.
  - zzzcpan 9y ago
    With CRDTs log entries can be purged once they synchronize with everyone, no need to keep them just in case. Although it's rather implementation specific.
- teraflop 9y ago
  Check out Bayou (it's cited in the references of this paper, but not discussed). It's basically what you're describing: operations are initially assigned a temporary timestamp and distributed through gossip, and when they reach a central server, they're given a permanent monotonic sequence number that allows old entries to be garbage-collected.
  - deleted 9y ago
    [deleted]
- pjc50 9y ago
  Normally we talk about these things in terms of CAP: consistency, availability, and partition tolerance. Systems with a central server avoid problems of partition tolerance and consistency just fine. It's the availability that's a problem. The system cannot operate without the central server. Whether this is a problem in your use case depends on your use case. Nationwide financial system? Aerospace control system? You probably care a lot about availability and can't use the central server model. (Although ironically a large part of how stock exchange clearing works is imposing an order on transactions and reconciling the result at the end of the day)
  - burntsushi 9y ago
    Yeah that is a good take! Thanks. Do you have any links to (relatively?) accessible reading on how stock exchange clearing works? That sounds like an interesting application of exactly this sort of problem that I'd like to learn more about.
    - pjc50 9y ago
      You could have a look at https://www.lseg.com/areas-expertise/our-markets/turquoise/equities/tq-technology https://www.lseg.com/areas-expertise/our-markets/turquoise/e... although I don't know if I'd call it "accessible". "Clearing" in general is a pre-digital technique for resolving concurrency. Someone writes a cheque for payment and puts a date on it, then exchanges it for goods; at some point later, it reaches the single, central ledger of that customer's bank account which is updated to reflect the transaction. I'll also reccommend https://martinfowler.com/articles/lmax.html https://martinfowler.com/articles/lmax.html , because it's an interesting architecture with a similar approach of just routing all the operations through in series, but with a number of producer/consumers attached to a ring buffer.
- archagon 9y ago
  I think there are few systems built like this because we're living in a decidedly centralized world. Also, CRDTs involve many tradeoffs (limited # of primitive types, complex performance characteristics, difficult algorithms, garbage collection) which make them less a swap-in option than a complete paradigm shift. Still, there are many situations where building on CRDTs would make your software far more resilient. For instance: let's say you want to design a document-based app that a) supports real-time collaboration, b) supports sync to a central server, c) works offline for arbitrary periods of time, d) supports real-time sync between offline and/or local devices. If you're relying on a central server to give you a total order, this would be very hard to do. With a CRDT-based system, it's effectively built-in. Doesn't matter if your peers are local devices, ad-hoc peers, a central server, or even a file on a USB stick: everything will still merge in the end, as long as you can distribute your ops in causal order. (And if you're using a state-based CvRDT, even that doesn't matter. Just send your file and it will merge.) At the limit, this means not having to think about the consistency of your data in terms of the network.
  - burntsushi 9y ago
    > a) supports real-time collaboration, b) supports sync to a central server, c) works offline for arbitrary periods of time, d) supports real-time sync between offline and/or local devices. If you're relying on a central server to give you a total order, this would be very hard to do. I guess my question is: why is this hard to do? I have another comment[1] in this thread that gives a bit more of a detailed example. Others in this thread also seem to be implying that my stated design is similar to how Google Wave worked. From Raph's article that I linked my initial comment: > Almost all practical implementations of OT forego TP2, and solve the problem by limiting concurrency in some way, generally requiring a central server to decide on a canonical ordering of the operations (but still using transformations to let clients apply operations out-of-order just a little bit). Maybe the parenthetical bit about transformations is the part I'm leaving out that I need to make more explicit? Not sure. [1] - https://news.ycombinator.com/item?id=15498216 https://news.ycombinator.com/item?id=15498216
    - archagon 9y ago
thdxr 9y ago
This is the exact topic I've been trying to think on for the past month. Excited to dig through it.
archagon 9y ago
I'm not an expert or an academic, but I've been spending a lot of time with CRDTs lately. It seems to me that there are two major issues with this approach. First, little is said about performance. As the paper explains, the meat of each CRDT is pushed into the eval function, which to my understanding is simply a function over the PO-Log. However, is it always possible to adapt a convergent data structure in such a way that eval takes a reasonable amount of time? I notice that sequences — perhaps the most important data type in CRDT-land! — have not been implemented using this approach. If we assume that a sequence can be retrieved from an insert/delete PO-Log by simply sorting it and removing the deleted operations, does that mean that every eval is O(Nlog(N)) at best? And if your solution is to cache the output sequence as an array, a) how do you ensure a correct mapping between the PO-Log and cache on every new operation, and b) what happens if you lose your data and need to replay your PO-Log from scratch? Can the cache be reconstructed O(Nlog(N)) at worst? A complete guess, but maybe having CRDT-specific bits in the prepare/effect steps is what actually allows CRDTs to be performant in the first place! PO-Log representation is alluringly flexible but seems to come with some hefty tradeoffs. Second, one of the cleanup steps relies on causal stability, i.e. knowing that each client is ahead of a potentially concurrent op. This is a problem in pure, decentralized P2P environments. First, depending on your network architecture, it's not necessarily possible to identify each peer until they actually start sending messages around. Maybe they got their hands on an early revision of the data and have been chipping away for weeks before going online. Second, nothing prevents a peer from connecting for a bit and then leaving forever, thus ensuring that their last edits will never be causally stable. This can be solved with some centralized logic, but then what's the point of using a CRDT at all? Finally, and less critically, the lossy cleanup steps make it impossible to retrieve old revisions or identify the author of a particular change.

86 points by blopeur 9y ago

I've been following the literature on this topic for a while now, and I've always wished for more examples of actual systems built with these techniques. Are there any? What kind of scales do they deal with? Are there any write-ups on them? (I know of at least one good one[1].) In particular, I've wondered how a simpler solution to the problems posed in this paper stacks up. At what point does it fail? e.g., Consider: * An op based model. * A client-server architecture (not p2p). * Operations are assigned a total ordering by a central server. * Given any two dependent operations A and B, A is always transmitted before B. This still gives you a lot of the stated advantages of an eventually consistent system, where each client communicating with the server will eventually converge even if they all temporarily diverge. The central server and total ordering is a key ingredient, because it's what lets you guarantee ordering between any two causal operations by having the server "choose" an ordering. I'm naturally interested in trade offs. For what use cases does the central server model break down? Is it still useful for other things at lesser scales? [1] - https://medium.com/@raphlinus/towards-a-unified-theory-of-operational-transformation-and-crdt-70485876f72f https://medium.com/@raphlinus/towards-a-unified-theory-of-op...

thdxr 9y ago
What happens in your scenario if operation B arrives hours later? It's hard to provide reliable ordering in practice because networks aren't dependable and things that happened earlier may show up later. I work on a realtime database and we heavily rely on CRDTs for communication. We can't have a central server because our goals are fault tolerance and high throughout. If you're more curious about the subject look into Riak. Afaik that is the biggest project built with CRDTs
- marknadal 9y ago
  @thdxr, which realtime database do you work on? I know some people at Riak/Basho who are now at MIT, they are helping us formalize our CRDT ( https://github.com/amark/gun/wiki/Conflict-Resolution-with-Guns https://github.com/amark/gun/wiki/Conflict-Resolution-with-G... ). We were chatting just last night and he said that Riak actually lacked proper CRDT in many settings (for example, secondary indices would produce non-deterministic results depending on order).
- burntsushi 9y ago
  > What happens in your scenario if operation B arrives hours later? It's hard to provide reliable ordering in practice because networks aren't dependable and things that happened earlier may show up later. I guess I'm trying to figure out why this is a problem. If operation B shows up hours later, then the client simply doesn't know about B until then. But since my stated design requires that dependent operations are delivered in order, we have that any other operations are necessarily concurrent with B, so it shouldn't matter when B is "evaluated." > I work on a realtime database and we heavily rely on CRDTs for communication. We can't have a central server because our goals are fault tolerance and high throughout. > If you're more curious about the subject look into Riak. Afaik that is the biggest project built with CRDTs Yeah, I'm definitely aware of Riak. I guess I'm more interested in the systems layered on top of these components. i.e., What problems are they trying to solve? For instance, what if you could relax your requirements? Maybe: throughput/latency only need to be good enough for web response time to end users.
  - im_down_w_otp 9y ago
    For the most part CRDTs of all types solve primarily one problem. The "lost update" problem. When I worked with CRDTs---even inventing a new one based on R*-trees---they were most useful for objects/structures that needed constant mutating by lots and lots of participants concurrently where it made sense to trade constant coordination/protection overhead for lazy-evaluation/merging. Like in a settlement ledger, or massive leaderboard, or indexing structure, etc.
    - burntsushi 9y ago
      Interesting, thanks for sharing that!
zzzcpan 9y ago
Central server for ordering would require you to always wait for its decision on every operation, which adds latency, limits throughput and reduces availability, not to mention how much complexity it adds, compared to something as simple as vector clocks.
- burntsushi 9y ago
  I don't see how you need to wait. It's still an eventually consistent system. Any client can build up their own replica of operations and synchronize with the central server at any time. I'm not sure I see the additional complexity. With a central server, you get to enforce a total ordering automatically across all operations. In any case, what I'm looking for is actual data. I implicitly understand that a central server won't scale as well, but that's not particularly interesting to me. For example, what if my requirements on throughput are very low? I want to know the breaking point. So I guess I'm looking for an experience report from someone who has actually gone through this process.
  - zzzcpan 9y ago
    Operations require sort of versions to synchronize, these versions is where ordering comes from too. This is important because since networks are asynchronous messages can arrive to this central server at different order. So, the way to achieve order with central server and being able to synchronize operations is to ask that server and wait for its decision. Not really that simple nor even usable. Instead the simplest and the most naive way to do this is to use timestamps for versions, still without a central server though. But time is not really possible to synchronize, so instead logical clocks should be used, like lamport timestamps, vector clocks. (And yes, I've been through this)
    - burntsushi 9y ago
      If you have a single logical server, then it chooses the ordering, but a single client doesn't need to ask the server for the ordering of any operations generated locally: it can pick the order because it determines the relative ordering of those operations. A client could be disconnected from the network for hours and re-synchronize at some later point in time and it all would work just fine. The only time the client needs to connect to the server are when the client wants to publish updates, or when the client wants to receive the updates. If you only need to do that once every 10 seconds (or even once every second), does that make a client/server model workable?
runT1ME 9y ago
You need a server, which is a single point of failure. If you want redundancy, you now need a quorum in the event of a split brain. CRDTs have the advantage of not needing a quorum in event of a split brain. There is no way to 'lose' information. In addition to being resilient to network split brain, this allows you to make performance gains at the sacrifice of consistency, where you could buffer your updates to other nodes. Operation based CRDTs do seem more limiting compared to State Based though, so you're at the mercy of your data structure being able to be represented as a CRDT.
- burntsushi 9y ago
  Sure, but let's say I was OK with a single point of failure. Or let's be more specific and say my central server is a PostgeSQL instance. > In addition to being resilient to network split brain, this allows you to make performance gains at the sacrifice of consistency, where you could buffer your updates to other nodes. My scheme allows this too, no?
  - runT1ME 9y ago
    > Sure, but let's say I was OK with a single point of failure. I cannot imagine designing a system for production use where anyone is OK with a single point of failure being a single instance of a machine. I mean if we're playing hypothetical games you don't need a distributed system either, just get one giant instance and put everything on it.
    - burntsushi 9y ago
      I'm trying to distill the design down to its essential components, and then figure out when it will break. If you're going to stick on this point, then let's imagine I have a PostgreSQL setup with replication, such that if any one fails, I can fall back to another. I primarily want to put this in the context of what problems folks are solving with operational CRDTs to get a sense of the scale that requires them. > I mean if we're playing hypothetical games you don't need a distributed system either, just get one giant instance and put everything on it. I guess the requirements need to be more explicitly stated. You need to at least be able to support multiple simultaneous clients interacting with the system, where any client could disconnect for some period of time.
naasking 9y ago
Consider a version control system where you had to communicate with the server for every commit, branch, merge, etc. That's how it used to be, and it was painful. Distributed version control relaxes those constraints with better merging to ensure commits are commutative. Now take that property and extend it to general programming, and you have similar advantages with eventual consistency. It's harder to see with typical concurrent abstractions, but Microsoft's concurrent revisions explicitly models their concurrency abstractions around distributed version control. Their papers are worth a read if you want ideas, data and inspiration that concurrency and distributed programming can actually be easy.
- burntsushi 9y ago
  I think I've done a bad job at communicating my design because it's perfectly consistent with what you've said. My proposed design is a client/server model, but that doesn't mean it isn't distributed. Each client can still operate on its own for as long as it wants, and it chooses to synchronize with the central server whenever it likes. (In fact, this is quite similar to most peoples' workflows with Git/Github, and I certainly wouldn't call that painful.) In any case, thanks for the pointers about the Microsoft research. I don't think I've seen that. I'll check it out.
  - naasking 9y ago
    See here for a comprehensive review of CR: http://lambda-the-ultimate.org/node/4699 http://lambda-the-ultimate.org/node/4699 Each client can operate on its own what though? If they have some kind of private copy of the data, then how do you resolve conflicts? CRDTs are about doing this automatically by restricting the types of changes clients can make. Concurrent revisions permit arbitrary changes so long as you provide a merge function to make them commute. I think you're just hand-waving a lot of the complexity away by using "synchronize" without explaining what is synchronized and how. That's where all the complexity in distributed computation stems from.
    - burntsushi 9y ago
      > Each client can operate on its own what though? Imagine the fundamental representation of your data structure is a sequence of operations. From those operations, you can generate your model. A really simple application of this is a graph, which is just a set of vertices and edges. So if you have these operations VertexAdd { id: fooID, label: foo } VertexAdd { id: barID, label: bar } VertexAdd { id: quuxID, label: quux } EdgeAdd { src: fooID, dst: quuxID } where the ids generated are unique (say, uuids). The corresponding model is just the graph: Graph { vertices: {foo, bar, quux}, edges: {{foo, bar}}, } You might imagine operations to remove vertices and edges as well. Many operations are commutative (add vertex), but some pairs of operations don't commute, e.g., add vertex/remove vertex. As I understand that, that's the central problem this paper is trying to address via CRDTs. What I'm saying is that the total ordering imposed by the server makes this concern moot, because the server always picks one sequential ordering. Let's say there are multiple simultaneous clients editing our graph structure above at the same time. Let's consider an example of a pair of operations that commute. One of them decides to remove vertex quux while the other adds an edge that connects quux to foo: client1: VertexDelete { id: quuxID } client2: EdgeAdd { src: quuxID, dst: fooID } If both clients attempt to update the server with these new operations, then the server will declare one ordering as true and send the resulting operations back to the clients with the correct ordering. The clients must then adjust. In this case, the outcome is the same regardless of the ordering chosen (because you can't draw an edge to a vertex that doesn't exist). What about the case when two operations are not commutative? Well, that means they are dependent, which in turn means that every client receives them in the order in which they were applied. An add/delete vertex is one such example, because the client doing the delete must acquire a vertex ID to give to the VertexDelete operation, but the only way to acquire the ID is to observer the VertexAdd first. Another example of dependent operations is attaching meta data to vertices, e.g., client1: VertexAdd { id: anotherID, label: Another } VertexLabel { id: anotherID, label: Changed } In this case, VertexAdd/VertexLabel are dependent, but the Label operation requires the vertex ID. Now of course, clients can misbehave. There's no reason why a client couldn't generate the ID and add operations in this order: client1: VertexLabel { id: anotherID, label: Changed } VertexAdd { id: anotherID, label: Another } But if we can assume well behaving clients, then this should be OK! And even if clients are misbehaving, then the process of turning the operations into a model can simply drop operations like VertexLabel because they reference a vertex that doesn't exist.
acjohnson55 9y ago
We use it for pretty basic purposes -- just replicating emphemeral data across our cluster, for debug settings, flash messages, etc. If the whole cluster goes down, no big deal.
ryuuseijin 9y ago
What you describe looks a lot like a Google Wave like OT system. Wave-style OT is eventually consistent, like CRDTs, but you need a central server to give the event history a total order. This is necessary because Wave-style OT is a 1-1 model: clients are 1-1 connected with the server, but not with each other, which would be n-n, which is what CRDTs can do. The total order of the central server can make the system simpler and more efficient, but by itself it doesn't solve the problem that Wave has, which is allowing a client to edit his text/message without being interrupted by network latency/interruptions -- imagine typing a letter and having to wait for the server to acknowledge that keypress with >100ms latencies. To solve this problem, you still need some form of xform/merge algorithm that OT and CRDT systems provide. EDIT: I assumed you were not familiar with OT systems since you didn't mention it in your post, but now that I followed your link I can see that you are. In that light, it seems your comment is more a question about what the tradeoffs are between OT and CRDT systems rather than whether a central server can solve all problems without xform/merge logic. One tradeoff that comes to mind when thinking about OT and CRDT systems is in the way operations track locations in the datastructure. In OT systems you have offsets (small), in CRDTs you have uuids (large) or dynamically growing identifiers (usually small but possibly large). This has implications for the byte-size of operations or the in-memory datastructure. Another is that CRDTs have a pruning problem. It has been some time since I looked at CRDTs, but I remember that Wave-style OT didn't have the same problem due to the central server. The pruning problem can cause a CRDT to grow larger than it needs to by forcing it to keep more historic data around just in case it gets an old operation it hasn't seen yet. The central server solves this problem by guaranteeing that it will have sent you all old operations before sending you a newer one. If you know all actors in a n-n system you can also solve this issue, but in an unbounded n-n system I didn't see any way this issue can be solved when I was researching it. EDIT2: Just want to add that there are lots of other problems that are more practical than theoretical. For example, authorization, authorative copy of the data, REST API, things like that, but that would depend more on the exact use case.
- zzzcpan 9y ago
  With CRDTs log entries can be purged once they synchronize with everyone, no need to keep them just in case. Although it's rather implementation specific.
teraflop 9y ago
Check out Bayou (it's cited in the references of this paper, but not discussed). It's basically what you're describing: operations are initially assigned a temporary timestamp and distributed through gossip, and when they reach a central server, they're given a permanent monotonic sequence number that allows old entries to be garbage-collected.
- deleted 9y ago
  [deleted]
pjc50 9y ago
Normally we talk about these things in terms of CAP: consistency, availability, and partition tolerance. Systems with a central server avoid problems of partition tolerance and consistency just fine. It's the availability that's a problem. The system cannot operate without the central server. Whether this is a problem in your use case depends on your use case. Nationwide financial system? Aerospace control system? You probably care a lot about availability and can't use the central server model. (Although ironically a large part of how stock exchange clearing works is imposing an order on transactions and reconciling the result at the end of the day)
- burntsushi 9y ago
  Yeah that is a good take! Thanks. Do you have any links to (relatively?) accessible reading on how stock exchange clearing works? That sounds like an interesting application of exactly this sort of problem that I'd like to learn more about.
  - pjc50 9y ago
    You could have a look at https://www.lseg.com/areas-expertise/our-markets/turquoise/equities/tq-technology https://www.lseg.com/areas-expertise/our-markets/turquoise/e... although I don't know if I'd call it "accessible". "Clearing" in general is a pre-digital technique for resolving concurrency. Someone writes a cheque for payment and puts a date on it, then exchanges it for goods; at some point later, it reaches the single, central ledger of that customer's bank account which is updated to reflect the transaction. I'll also reccommend https://martinfowler.com/articles/lmax.html https://martinfowler.com/articles/lmax.html , because it's an interesting architecture with a similar approach of just routing all the operations through in series, but with a number of producer/consumers attached to a ring buffer.
archagon 9y ago
I think there are few systems built like this because we're living in a decidedly centralized world. Also, CRDTs involve many tradeoffs (limited # of primitive types, complex performance characteristics, difficult algorithms, garbage collection) which make them less a swap-in option than a complete paradigm shift. Still, there are many situations where building on CRDTs would make your software far more resilient. For instance: let's say you want to design a document-based app that a) supports real-time collaboration, b) supports sync to a central server, c) works offline for arbitrary periods of time, d) supports real-time sync between offline and/or local devices. If you're relying on a central server to give you a total order, this would be very hard to do. With a CRDT-based system, it's effectively built-in. Doesn't matter if your peers are local devices, ad-hoc peers, a central server, or even a file on a USB stick: everything will still merge in the end, as long as you can distribute your ops in causal order. (And if you're using a state-based CvRDT, even that doesn't matter. Just send your file and it will merge.) At the limit, this means not having to think about the consistency of your data in terms of the network.
- burntsushi 9y ago
  > a) supports real-time collaboration, b) supports sync to a central server, c) works offline for arbitrary periods of time, d) supports real-time sync between offline and/or local devices. If you're relying on a central server to give you a total order, this would be very hard to do. I guess my question is: why is this hard to do? I have another comment[1] in this thread that gives a bit more of a detailed example. Others in this thread also seem to be implying that my stated design is similar to how Google Wave worked. From Raph's article that I linked my initial comment: > Almost all practical implementations of OT forego TP2, and solve the problem by limiting concurrency in some way, generally requiring a central server to decide on a canonical ordering of the operations (but still using transformations to let clients apply operations out-of-order just a little bit). Maybe the parenthetical bit about transformations is the part I'm leaving out that I need to make more explicit? Not sure. [1] - https://news.ycombinator.com/item?id=15498216 https://news.ycombinator.com/item?id=15498216
  - archagon 9y ago

thdxr 9y ago

This is the exact topic I've been trying to think on for the past month. Excited to dig through it.

archagon 9y ago

I'm not an expert or an academic, but I've been spending a lot of time with CRDTs lately. It seems to me that there are two major issues with this approach. First, little is said about performance. As the paper explains, the meat of each CRDT is pushed into the eval function, which to my understanding is simply a function over the PO-Log. However, is it always possible to adapt a convergent data structure in such a way that eval takes a reasonable amount of time? I notice that sequences — perhaps the most important data type in CRDT-land! — have not been implemented using this approach. If we assume that a sequence can be retrieved from an insert/delete PO-Log by simply sorting it and removing the deleted operations, does that mean that every eval is O(Nlog(N)) at best? And if your solution is to cache the output sequence as an array, a) how do you ensure a correct mapping between the PO-Log and cache on every new operation, and b) what happens if you lose your data and need to replay your PO-Log from scratch? Can the cache be reconstructed O(Nlog(N)) at worst? A complete guess, but maybe having CRDT-specific bits in the prepare/effect steps is what actually allows CRDTs to be performant in the first place! PO-Log representation is alluringly flexible but seems to come with some hefty tradeoffs. Second, one of the cleanup steps relies on causal stability, i.e. knowing that each client is ahead of a potentially concurrent op. This is a problem in pure, decentralized P2P environments. First, depending on your network architecture, it's not necessarily possible to identify each peer until they actually start sending messages around. Maybe they got their hands on an early revision of the data and have been chipping away for weeks before going online. Second, nothing prevents a peer from connecting for a bit and then leaving forever, thus ensuring that their last edits will never be causally stable. This can be solved with some centralized logic, but then what's the point of using a CRDT at all? Finally, and less critically, the lossy cleanup steps make it impossible to retrieve old revisions or identify the author of a particular change.