I've been following the literature on this topic for a while now, and I've always wished for more examples of <i>actual systems</i> 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].)<p>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:<p><pre><code> * 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.
</code></pre>
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.<p>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?<p>[1] - <a href="https://medium.com/@raphlinus/towards-a-unified-theory-of-operational-transformation-and-crdt-70485876f72f" rel="nofollow">https://medium.com/@raphlinus/towards-a-unified-theory-of-op...</a>
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.<p>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.<p>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?<p>Finally, and less critically, the lossy cleanup steps make it impossible to retrieve old revisions or identify the author of a particular change.