So... I'm a "learn by stackexchange" dev and really enjoyed tracking this person's thought process.<p>I find that most tutorial/explanations come fully baked with the the problems -predictively- solved, as opposed to reactively solved, if that makes sense -- The difference between ("In order to prevent this problem, we'll do X" as opposed to "Hmm that's not working. Why is that? Ah. Okay perhaps we can do W... no, that won't work and here's (y, zing) why, let's try X")<p>Author's blog notwithstanding, where are other places to read other developers essentially plain-speak their way through problem solving / program architecture in a similar fashion?
Assuming the author of the article spots this on HN, I'd just like to say a quick thanks for mentioning Overleaf [1] in this! It's a nice easy to read article and it reminded me that we were planning to write one along these lines but never got around to it :)<p>It's interesting to see how CRDT has been adopted -- we wrote our own OT implementation for Overleaf (back when we were writeLaTeX) and it's still serving us well. We took a lot of inspiration from Etherpad [2], which is still a great collaborative editor, especially for notes.<p>We're now going over much of our code as we work on the integration with ShareLaTeX [3], which also has a very nice real time track changes / commenting implementation [4]. This helps with the UI aspect of collaboration, which is important on top of the use of OT or CRDT to ensure no version conflicts.<p>Good luck in your next projects, and I look forward to reading write ups like this of those too :)<p>[1] <a href="https://www.overleaf.com/" rel="nofollow">https://www.overleaf.com/</a><p>[2] <a href="http://etherpad.org/" rel="nofollow">http://etherpad.org/</a><p>[3] <a href="https://www.overleaf.com/blog/518-exciting-news-sharelatex-is-joining-overleaf" rel="nofollow">https://www.overleaf.com/blog/518-exciting-news-sharelatex-i...</a><p>[4] <a href="https://www.sharelatex.com/blog/2017/03/09/track-changes-and-comments-in-latex.html" rel="nofollow">https://www.sharelatex.com/blog/2017/03/09/track-changes-and...</a><p>(Note: Edited for grammar)
Very cool to see this on the front page. I would agree that for the use case of plain text, yes, the problem has been solved, but for just about anything more complicated it quickly becomes intractable. Rich Text, for example, is extremely difficult to get right (ask the ckeditor guys!)<p>For those wanting real-time collaboration functionality in their apps but don't have the intellectual curiosity (or time!) to learn the ins and outs, we [1] built a general-purpose API for folks to add real-time collaboration to their web apps. Think Firebase but designed from the ground up for simultaneous editing and with additional first-class support for common UX needs such as shared cursors and selections. We agree that the web is moving in this direction and are excited to see what gets built!<p>[1]convergencelabs.com
The problem I ran into when I had to do this on a prior project wasn't the algorithm for worrying about individual characters. It was dealing with how to manage people highlighting entire paragraphs or documents, and pasting over them with new content, at the same time as the other editor(s) had been changing things.<p>Ultimately, while there were algorithmic answers to just about any scenario, we ended up just declaring a business answer instead - the editor only would let you into edit mode one paragraph at a time, and you locked that paragraph while you were in it. We found that almost nobody was actually editing the exact same paragraph at the same time anyway... they were working in different parts of the documents. So not only did that resolve all possible copy/paste insanity, the algorithm became brain-dead simple -- when you update or leave the paragraph, send those changes to everyone else's editor.
I liked Raph's writings on CRDTs: <a href="https://medium.com/@raphlinus/working-code-for-operational-transformation-crdt-hybrid-9d04a57309da" rel="nofollow">https://medium.com/@raphlinus/working-code-for-operational-t...</a>
For the keys, I created a similar library called <a href="https://github.com/Cirru/bisection-key" rel="nofollow">https://github.com/Cirru/bisection-key</a> to generate string keys.
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.<p>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.<p>Hope to finish v1 of the demo and post the article by the end of the month, but writing is very hard...<p>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: <a href="https://stackoverflow.com/questions/45722742/logoot-crdt-interleaving-of-data-on-concurrent-edits-to-the-same-spot" rel="nofollow">https://stackoverflow.com/questions/45722742/logoot-crdt-int...</a><p>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.<p>[1]: <a href="https://ai2-s2-pdfs.s3.amazonaws.com/6534/c371ef78979d7ed84b6dc19f4fd529caab43.pdf" rel="nofollow">https://ai2-s2-pdfs.s3.amazonaws.com/6534/c371ef78979d7ed84b...</a><p>[2]: <a href="https://github.com/archagon/crdt-playground" rel="nofollow">https://github.com/archagon/crdt-playground</a>
Hmm, FYI, I seem to have broken it a little bit: <a href="https://i.imgur.com/qrNeZFJ.png" rel="nofollow">https://i.imgur.com/qrNeZFJ.png</a>