3 ms·
CRDTs are awesome! I’m working on a similar article going in-depth on Victor Grishchenko’s Causal Tree[1] CRDT, which makes several ingenious decisions (making
by archagon 9y ago
CRDTs are awesome! I’m working on a similar article going in-depth on Victor Grishchenko’s Causal Tree[1] CRDT, which makes several ingenious decisions (making a tree out of atoms and their causes, storing the full ordered atom history for each site, treating the output data as a DFS traversal of the atom tree, sorting atoms by their on-creation awareness of other atoms) that allow the format to be extended to many other data types, all with generally O(N) performance and permitting git-like document history and per-change blame queries without any extra work. I've grown to think of it as the purest possible expression of the CRDT concept.
In my example project[2] (NOT PRODUCTION READY!) I’ve already implemented text editing and basic vector drawing that synchronize over arbitrary network topologies. If you can massage your data into the CT format, you get real-time collaboration, offline mode, cloud sync, and decentralized network support for basically free — all in a thousand lines of comprehensible, functional code! You can even use it with a basic key-value store like CloudKit, which was admittedly one of my main reasons of diving into this class of algorithm.
Hope to finish v1 of the demo and post the article by the end of the month, but writing is very hard...
More on point, I really like how this article dissects and visualizes CRDTs, which can be a difficult topic to breach. If you're looking to implement something like this, however, it should be noted that Logoot has a pretty significant interleaving problem for concurrent operations if you use it to sync individual characters as opposed to lines: https://stackoverflow.com/questions/45722742/logoot-crdt-interleaving-of-data-on-concurrent-edits-to-the-same-spot https://stackoverflow.com/questions/45722742/logoot-crdt-int...
I think for text this is a deal-breaker, because if one client goes offline for a while, they'll basically corrupt the document if anything they've been working on overlaps with other users' changes. You could solve this with a central server by forcing a re-sync and/or manual merge, but I feel that sort of defeats the purpose of using a CRDT.
[1]: https://ai2-s2-pdfs.s3.amazonaws.com/6534/c371ef78979d7ed84b6dc19f4fd529caab43.pdf https://ai2-s2-pdfs.s3.amazonaws.com/6534/c371ef78979d7ed84b...
[2]: https://github.com/archagon/crdt-playground https://github.com/archagon/crdt-playground