12 ms·

Hello HN! Post author here. I’m happy to answer questions & fix typos once morning rolls around here in Australia

teodorlu 5y ago
Have you used CRDTs to solve any practical problems? If so, how does the CRDT solution compare to a non-CRDT solution? If a non-CRDT solution is feasible at all?
- mirekrusin 5y ago
  Article mentions at the beginning that the author used CRDT in Google Wave/ShareJS.
  - paulgb 5y ago
    Wave used OT rather than CRDTs, as the author discusses in another post: https://josephg.com/blog/crdts-are-the-future/ https://josephg.com/blog/crdts-are-the-future/
  - saurik 5y ago
    AFAIK Wave and ShareJS both used OT (which the paper that this article referred to was also attempting to benchmark). FWIW, I am myself also curious about this (the question of comparing CRDT to non-CRDT solutions): I found OT beautiful, but never really felt CRDT had the same feeling of elegance; and so I am downright fascinated to see the person I have always seen as a "god of OT" deciding to forsake it and move to CRDTs going forward. Are they really that great? Is there something simple I am missing for the explanation for why they are so much better? (Is it maybe that they can support arbitrary merging without a sequencer to linearize the edits? Honestly, my question probably sucks a bit as I haven't spent any time thinking about OT or CRDT in at least three years--and even then only once since a few years before that, as I have had other things to spend most of my mental energy on recently--and so I am failing to remember the details of my use cases or the tradeoffs I saw or the implementation issues I felt were easy/hard.)
    - the-smug-one 5y ago
      Do you want a centralized server to control the data? Then just use OT. Do you want users to control the data, and have your server essentially just be a forever-present user? Then use CRDT. CRDTs certainly do have a mathematical elegance to them.
      - josephg 5y ago
        Yep, this is the best practical advice at the moment. Well, for list CRDTs. State CRDTs (like a counter) are small and fast, and kinda better than OT in every way. List ("operation based") CRDTs and OT systems are "equivalent" in a very academic sense that nobody really talks about or understands. Its really not obvious unless you've been staring at this stuff for years but the equivalence is there: You can make a CRDT out of any OT system by just shipping the entire history of operations to each peer. List CRDTs essentially do that, with a whole lot of tricks to compress that data set and use it without needing to linearly scan. And you can convert the other way too. You can add a "rename" operation into a list CRDT which assigns a new name to each element currently in the document. Before the rename operation document "hello" might have IDs [a4, b2, b3, b1, a5]. The rename operation changes the IDs to [c1, c2, c3, c4, c5]. When an operation happens you specify the version and the ID at that version of the predecessor (eg c2). The insert happens there. Then you need a method to take the ID at one version and "transform" it to the ID of the same item at a different version. Do the rename operation implicitly after every change, and viola! You now have OT semantics. "Insert after c1" means "Insert after position 1". OT systems have one big advantage which is that you don't have to ship the CRDT state to every peer. With a rename operation, we can add back the operational simplicity of OT systems into a CRDT. But the code is (and always will be) much more complicated. So I think OT makes sense for strictly server-client systems. You can also have a hybrid server, which talks CRDT to full peers on the network but just does OT when talking to browser clients and things like that. We talked about this at our public braid meeting at the start of the week. The discussion about this stuff starts about 30 minutes in: https://braid.org/meeting-15 https://braid.org/meeting-15
        zozbot234 5y ago
  - mirekrusin 5y ago
    My mistake, it says OT was used, thank you for correcting me.
- Jailbird 5y ago
  Drifting off-topic but I've wondered this myself - I've been interested in CRDTs in a "read the news" way but not a "this rises to something I'm going to implement" way. Perhaps it's blindingly obvious to all here, so no one mentions it: Thinking about more practical and real-world problems seems like collaboration on on more complex/structured data. Today, it seems one would still have to transform that data to a large flat string underneath, and implement an editor that only performs edits that maintain the integrity of the higher-level object, while the flat string provides collaboration features. Perhaps it's possible to implement an XML schema known to the editor so all insertions/deletions keep the document syntactically correct. I wonder if there's some other way to either generalize on top of "big string" or create another base model (somehow?)
  - detaro 5y ago
    CRDT is a general concept, editing text is just one possible application. If you have a stronger datatype, great, you can build operations on top of it to implement a CRDT system, depending on its properties.
    - Jailbird 5y ago
      What I've read talks about character insertion and concepts that apply to editing text. Perhaps I just need to find bedrock to build up from about the properties of a stronger datatype that allow CRDTs to work.
      - detaro 5y ago
        https://arxiv.org/pdf/1805.06358.pdf https://arxiv.org/pdf/1805.06358.pdf looks like a decent starting point, with references to work on other types.
        Jailbird 5y ago
        and pointers to other papers, too - thanks!
    - 5y ago
mirekrusin 5y ago
It seeems that the issue of reproducibility in computer science where no gigantic/proprietary datasets are needed should not be a problem by simply publishing repository with the code. Are there any forces present that make it so rare in practice?
- josephg 5y ago
  Credit where its due, the academics did publish the code they wrote on github. But I don't know if anyone - reviewers or readers - actually took the time to read it. Let alone understand why it throws doubt on the paper's conclusions.
  - JW_00000 5y ago
    Usually, (at least in my specific niche of the computer science field,) if the code is published it's only published after the paper has been reviewed. This is partly to preserve anonymity during the review process, and also because usually the code isn't seen as "part of the paper" (i.e. "the paper should stand on its own"). Although I agree that you could argue that for papers about benchmarks, the code should definitely be considered an essential part of the paper.
robmorris 5y ago
That’s an impressive optimisation! Out of curiosity, what do you think are the most interesting or useful possible applications for an optimised CRDT? When you’re approaching an optimisation like this, do you mind me asking how you think about it and approach it?
- josephg 5y ago
  The most useful application I see is moving toward building local first software[1]. And as for optimizations, my approach is surprisingly non systematic. I think about the program on the whole, and think through & investigate where all the time is being spent. There's usually ways to restructure things so the hottest code path runs faster. Sometimes that involves changing data structures or languages. Sometimes it just needs early returns for common cases, or inlining string libraries and things like that to avoid allocations. Sometimes it helps to imagine yourself going through by hand the drudgery the computer is doing. If I was actually doing that boring work by hand, there's almost always ways I'd start taking short cuts. All thats left then is programming those shortcut into the computer. [1] https://www.inkandswitch.com/local-first.html https://www.inkandswitch.com/local-first.html
politician 5y ago
Great post! I had no idea that list CRDTs could actually be fast because I read the papers showing how they were impractical. Thanks for investigating and writing this up — please accept my offer of a legitimate academic credential.
GlennS 5y ago
When optimizing `findItem`, did you consider storing the original index of each item on itself and using that as a starting point? Obviously this might move later (maybe it can only increase?), but usually not by much, so I would guess it would make an efficient starting point / be immediately correct 99% of the time? Looks like you already have 2 good solutions to this though (start from index of recent edits and range tree).
thechao 5y ago
I love high level systems languages like C/++ and Rust… but everything you said about JavaScript being slow is the same thing assembly programmers experience when optimizing high level systems languages. In general, when I see C code and I’m asked to speed it up, I always use “100x” as my target baseline.
- josephg 5y ago
  Whoa thats a really impressive baseline to reach for when optimizing C code! I'd love to hear some war stories. As you can probably tell from my article, most of my skill at this stuff is from hard won tricks I've picked up over the years - like reducing heap allocations and packing memory for cache coherency. There's probably lots of things I just haven't learned because I haven't discovered it on my own. Do you have a blog, or any recommendations for stuff to read by you or others?
  - thechao 5y ago
    I learned low level programming while at Intel, working with one of their performance teams; so, nothing written. In general, though, assembly is more expressive than higher level languages; it lets you “tighten up” the code the computer executes, reducing work & bandwidth. Specifically, a guy named Mike Abrash taught me some of this stuff, and he’s got some books explaining the theory in terms of practice.
deleted 5y ago
[deleted]
lewisjoe 5y ago
Thank you for writing this piece Joseph. Just want to make sure if something's a possible typo or I'm getting it all wrong :) Quote: "But how do we figure out which character goes first? We could just sort using their agent IDs or something. But argh, if we do that the document could end up as abcX, even though Mike inserted X before the b. That would be really confusing." Since the conflict is only between the children of (seph, 0) the only possibilities are, either ending up with "aXbc" or "abXc" right? Or is there a legitimate possibility of ending up with "abcX" ? I'm assuming we'll apply a common sorting logic only to clashing siblings.
- josephg 5y ago
  Good question. That part of the article could probably use another diagram to explain it. The resulting document is generated by doing a depth-first prefix traversal of the tree. The ambiguity comes because "b" and "X" are both direct children of "a". So its not clear how they should be ordered relative to each other. Because "c" is a child of "b" in this example, the "X" can't appear between the "c" and "b". The only valid orderings are, as I said, "aXbc" or "abcX". But without knowing how "b" and "X" should be ordered, its ambiguous which one to use. Let me know if thats still confusing! This stuff is hard to explain without a whiteboard.
  - lewisjoe 5y ago
    Clear enough Joseph. Thanks :)
Majromax 5y ago
When you write: > Yjs does one more thing to improve performance. Humans usually type in runs of characters. So when we type "hello" in a document, instead of storing ['h','e','l','l,'o'], Yjs just stores: ['hello']. [...] This is the same information, just stored more compactly. Isn't this not just the same information when faced with multiple editors? In the first implementation, if I pause to think after typing 'hel', another editor might be able to interject with 'd' to finish the word in another way. In my view, these data structures are only "the same information" if you provide for a reasonably-sized, fixed quantum of synchronization. The merging makes sense if e.g. you batch changes every one or two seconds. It makes less sense if you would otherwise stream changes to the coordinating agent as they happen, even with latency.
- goldenkey 5y ago
  The chunking should depend entirely on the network synchronization. If synchronization is editing-debounced, then chunking could be applied rather safely.
- josephg 5y ago
  I didn't explain this well but the transformation is lossless. No data is lost from compressing like this. It has no impact on the concurrency protocol or network protocol; it just impacts how the data is stored locally. If we need to, we could split the run back out again into individual characters without losing information. And that does happen - we do that if something later gets inserted into the middle of the run of characters. Pausing doesn't help. Even the same user could later type something in the middle of a word they'd typed previously. This limits what we can run-length encode. The code in diamond only run-length encodes items when they are: - Typed sequentially in time - And sequentially in insert location (position 10, 11, 12, 13, ...) - And either all of the characters have been deleted or none of them have been deleted Notice the other fields in that example in the post. Each subsequent character has: - An id field = the previous id + 1 - A parent field = the id of the previous item - The same value for isDeleted If any of this stuff didn't match, the run would be split up. Instead of storing those fields individually, we can store the id and parent of the first item, an isDeleted flag and a length field. Thats all the information we actually need to store. With yjs style entries (which is what diamond-types actually implements), the code is here if you can make heads or tails of it. The poorly named "truncate" method splits an item in two. Spans are only extended if can_append() returns true: https://github.com/josephg/diamond-types/blob/c4d24499b70a2315df33627834f9085bcb486bc9/src/list/span.rs#L6-L57 https://github.com/josephg/diamond-types/blob/c4d24499b70a23... With real data from Martin's editing trace, 182 000 inserted characters get compacted down to 12 500 list items. Which is still pretty good - thats 14x fewer entries. And it means performance doesn't stutter when large paste events happen.
username91 5y ago
It's a great article - really informative and enjoyable to read. Thanks for making it happen. :)
conaclos 5y ago
Hi josephg, I'm a CRDT researcher. This is great to see so much work around CRDT nowadays! Some optimizations whom you discuss are already proposed by some papers and implementations. For instance, LogootSplit [1] proposes an implementation based on an AVL tree with extra metadatas to get a range tree. LogootSplit proposes also a block-wise approach that stores strings instead of individual characters. Xray [2], an experimental editor built by Github and written in Rust, uses a copy-on-write B-tree. Teletype [3] uses a splay tree to speedup local insertions/deletions based on the observation that a user performs several edits on the same region. [1] https://members.loria.fr/CIgnat/files/pdf/AndreCollabCom13.pdf https://members.loria.fr/CIgnat/files/pdf/AndreCollabCom13.p... [2] https://github.com/atom-archive/xray https://github.com/atom-archive/xray [3] https://github.com/atom/teletype https://github.com/atom/teletype
- josephg 5y ago
  Cool! It'd be interesting to see those CRDT implementations added to Kevin Jahns' CRDT Benchmarks page[1]. The LogootSplit paper looks interesting. It looks like xray is abandoned, and I'm not sure about teletype. Though teletype's CRDT looks to be entirely implemented in javascript[2]? If the authors are around I'd love to see some benchmarks so we can compare approaches and learn what actually works well. And I'm not surprised these techniques have been invented before. Realising a tree is an appropriate data structure here is a pretty obvious step if you have a mind for data structures. To name it, I often find myself feeling defensive when people read my work and respond with a bunch of links to academic papers. Its probably totally unfair and a complete projection from my side, but I hear a voice in my head reword your comment to instead say something awful like: "Cool, but everything you did was done before. Even if they didn't make any of their work practical, usable or good they still published first and you obviously didn't do a good enough literature review if you didn't know that." And I feel an unfair defensiveness arise in me as a result that wants to find excuses to dismiss the work, even if the work might be otherwise interesting. Its hard to compare their benchmark results because they used synthetic randomized editing traces, which always have different performance profiles than real edits for this stuff. Their own university gathered some great real world data in an earlier study. It would have been much more instructive if that data set was used here. At a glance their RAM usage looks to be about 2 orders of magnitude worse than diamond-types or yjs. And their CPU usage... ?? I can't tell because they have no tables of results. Just some hard to read charts with log scales, so you can't even really eyeball the figures. So its really hard to tell if their work ends up performance-competitive without spending a couple days getting their enterprise style java code running with a better data set. Do you think thats worth doing? [1] https://github.com/dmonad/crdt-benchmarks https://github.com/dmonad/crdt-benchmarks [2] https://github.com/atom/teletype-crdt https://github.com/atom/teletype-crdt
ta988 5y ago
This was a great read, thank you. I wish there were more explanations of the "black magic" part of Yjs. I'll have to dig into that.
- josephg 5y ago
  If you’re interested in learning more about Yjs’s internals, I interviewed Kevin for 3 hours on zoom and got him to take me through Yjs’s code. He’s a great guy. The video of that conversation is here: https://youtu.be/0l5XgnQ6rB4 https://youtu.be/0l5XgnQ6rB4
  - ta988 5y ago
    Thanks a lot. Thats on my video queue.
- nevf 5y ago
  There's a series videos on YJS and whitepapers etc. Check out the YJS web site and search Youtube for details.
trishume 5y ago
Have you seen my Xi CRDT writeup from 2017 before? https://xi-editor.io/docs/crdt-details.html https://xi-editor.io/docs/crdt-details.html It's a CRDT in Rust and it uses a lot of similar ideas. Raph and I had a plan for how to make it fast and memory efficient in very similar ways to your implementation. I think the piece I got working during my internship hits most of the memory efficiency goals like using a Rope and segment list representation. However we put off some of the speed optimizations you've done, like using a range tree instead of a Vec of ranges. I think it also uses a different style of algorithm without any parents. We never finished the optimizing and polished it up, so it's awesome that there's now an optimized text CRDT in Rust people can use!
- neolog 5y ago
  Out of curiosity, what do you use to make those diagrams?
  - trishume 5y ago
    https://www.figma.com/ https://www.figma.com/ and putting a lot of effort into them
- josephg 5y ago
  Oooohhhh no I haven’t read that - thanks for the link! I feel embarrassed to say this but I knew about Xi editor years ago but I totally forgot to go read & learn about your crdt implementation when I was learning about Yjs and automerge and others. I’ll have a read. And thanks for writing such an in depth article. It’s really valuable going forward. Maybe it’s addressed in your write up but are there any plans for that code, or has everyone moved on? I’d love to have a zoom chat about it and hear about your experiences at some point if you’d be willing.
pookeh 5y ago
Wait it doesn't look like you used the performance branch of automerge (which is now merged into master). It is significantly faster. https://github.com/automerge/automerge/pull/253 https://github.com/automerge/automerge/pull/253
- josephg 5y ago
  I did use the performance branch. And I had a chat with a few people in the automerge community about the performance numbers I was seeing long before I published to see if I was doing anything wrong. I tested a few different versions of automerge but in this test there wasn’t much performance difference between 0.12, 1.0.x-preview versions (which are built from the merged performance branch) and I tried the unreleased automerge-rs. When I ran my tests timing numbers for automerge ranged from about 5m with the old non performance branch down to about 4m20s or so with automerge-rs. Still far from Yjs’s 0.9 seconds. I just checked and it looks like automerge 1.0.1-preview-4 has landed. I wrote the post benchmarking preview-2. I’ve been knee deep in diamond types lately and haven’t been watching. Fingers crossed there’s some more performance improvements in the pipeline. I’d love to do a follow up in 6 months showing much improved performance.
benjismith 5y ago
I've been following your work for years (and I'm actually neck-deep in a ShareDB project right now) so I just want to say thank you for all of your contributions! I especially enjoyed this post.
gfodor 5y ago
Thanks for ShareDB. It’s dope. I extended it to support collaborative voxel editing (https://jel.app https://jel.app) and works great.
- josephg 5y ago
  Oh that’s cool!! Did you use json-ot for that? I haven’t touched that code in years and it’s delightful people are actively maintaining it and using it to make cool stuff.
  - gfodor 5y ago
    I use ot-json for other stuff, but wrote my own ot-vox which deals with voxel grid cells that can be assigned a color.
xcombelle 5y ago
I believe that I understood the code tagged as follow > (But don't be alarmed if this looks confusing - we could probably fit everyone on the planet who understands this code today into a small meeting room.) and the follow up reading confirm what I believed about this code should I be worried about myself ?
fulafel 5y ago
Terminology nit: cache coherence refers to CPU cache implementation behaviours at hw level in presence of concurrent access from multiple cores. Data locality or cache friendly data layout could work better here.
- josephg 5y ago
  Good point - thanks. I'll tidy that up!

Have you used CRDTs to solve any practical problems? If so, how does the CRDT solution compare to a non-CRDT solution? If a non-CRDT solution is feasible at all?

mirekrusin 5y ago
Article mentions at the beginning that the author used CRDT in Google Wave/ShareJS.
- paulgb 5y ago
  Wave used OT rather than CRDTs, as the author discusses in another post: https://josephg.com/blog/crdts-are-the-future/ https://josephg.com/blog/crdts-are-the-future/
- saurik 5y ago
  AFAIK Wave and ShareJS both used OT (which the paper that this article referred to was also attempting to benchmark). FWIW, I am myself also curious about this (the question of comparing CRDT to non-CRDT solutions): I found OT beautiful, but never really felt CRDT had the same feeling of elegance; and so I am downright fascinated to see the person I have always seen as a "god of OT" deciding to forsake it and move to CRDTs going forward. Are they really that great? Is there something simple I am missing for the explanation for why they are so much better? (Is it maybe that they can support arbitrary merging without a sequencer to linearize the edits? Honestly, my question probably sucks a bit as I haven't spent any time thinking about OT or CRDT in at least three years--and even then only once since a few years before that, as I have had other things to spend most of my mental energy on recently--and so I am failing to remember the details of my use cases or the tradeoffs I saw or the implementation issues I felt were easy/hard.)
  - the-smug-one 5y ago
    Do you want a centralized server to control the data? Then just use OT. Do you want users to control the data, and have your server essentially just be a forever-present user? Then use CRDT. CRDTs certainly do have a mathematical elegance to them.
    - josephg 5y ago
      Yep, this is the best practical advice at the moment. Well, for list CRDTs. State CRDTs (like a counter) are small and fast, and kinda better than OT in every way. List ("operation based") CRDTs and OT systems are "equivalent" in a very academic sense that nobody really talks about or understands. Its really not obvious unless you've been staring at this stuff for years but the equivalence is there: You can make a CRDT out of any OT system by just shipping the entire history of operations to each peer. List CRDTs essentially do that, with a whole lot of tricks to compress that data set and use it without needing to linearly scan. And you can convert the other way too. You can add a "rename" operation into a list CRDT which assigns a new name to each element currently in the document. Before the rename operation document "hello" might have IDs [a4, b2, b3, b1, a5]. The rename operation changes the IDs to [c1, c2, c3, c4, c5]. When an operation happens you specify the version and the ID at that version of the predecessor (eg c2). The insert happens there. Then you need a method to take the ID at one version and "transform" it to the ID of the same item at a different version. Do the rename operation implicitly after every change, and viola! You now have OT semantics. "Insert after c1" means "Insert after position 1". OT systems have one big advantage which is that you don't have to ship the CRDT state to every peer. With a rename operation, we can add back the operational simplicity of OT systems into a CRDT. But the code is (and always will be) much more complicated. So I think OT makes sense for strictly server-client systems. You can also have a hybrid server, which talks CRDT to full peers on the network but just does OT when talking to browser clients and things like that. We talked about this at our public braid meeting at the start of the week. The discussion about this stuff starts about 30 minutes in: https://braid.org/meeting-15 https://braid.org/meeting-15
      - zozbot234 5y ago
- mirekrusin 5y ago
  My mistake, it says OT was used, thank you for correcting me.
Jailbird 5y ago
Drifting off-topic but I've wondered this myself - I've been interested in CRDTs in a "read the news" way but not a "this rises to something I'm going to implement" way. Perhaps it's blindingly obvious to all here, so no one mentions it: Thinking about more practical and real-world problems seems like collaboration on on more complex/structured data. Today, it seems one would still have to transform that data to a large flat string underneath, and implement an editor that only performs edits that maintain the integrity of the higher-level object, while the flat string provides collaboration features. Perhaps it's possible to implement an XML schema known to the editor so all insertions/deletions keep the document syntactically correct. I wonder if there's some other way to either generalize on top of "big string" or create another base model (somehow?)
- detaro 5y ago
  CRDT is a general concept, editing text is just one possible application. If you have a stronger datatype, great, you can build operations on top of it to implement a CRDT system, depending on its properties.
  - Jailbird 5y ago
    What I've read talks about character insertion and concepts that apply to editing text. Perhaps I just need to find bedrock to build up from about the properties of a stronger datatype that allow CRDTs to work.
    - detaro 5y ago
      https://arxiv.org/pdf/1805.06358.pdf https://arxiv.org/pdf/1805.06358.pdf looks like a decent starting point, with references to work on other types.
      - Jailbird 5y ago
        and pointers to other papers, too - thanks!
  - 5y ago

mirekrusin 5y ago

It seeems that the issue of reproducibility in computer science where no gigantic/proprietary datasets are needed should not be a problem by simply publishing repository with the code. Are there any forces present that make it so rare in practice?

josephg 5y ago
Credit where its due, the academics did publish the code they wrote on github. But I don't know if anyone - reviewers or readers - actually took the time to read it. Let alone understand why it throws doubt on the paper's conclusions.
- JW_00000 5y ago
  Usually, (at least in my specific niche of the computer science field,) if the code is published it's only published after the paper has been reviewed. This is partly to preserve anonymity during the review process, and also because usually the code isn't seen as "part of the paper" (i.e. "the paper should stand on its own"). Although I agree that you could argue that for papers about benchmarks, the code should definitely be considered an essential part of the paper.

robmorris 5y ago

That’s an impressive optimisation! Out of curiosity, what do you think are the most interesting or useful possible applications for an optimised CRDT? When you’re approaching an optimisation like this, do you mind me asking how you think about it and approach it?

josephg 5y ago
The most useful application I see is moving toward building local first software[1]. And as for optimizations, my approach is surprisingly non systematic. I think about the program on the whole, and think through & investigate where all the time is being spent. There's usually ways to restructure things so the hottest code path runs faster. Sometimes that involves changing data structures or languages. Sometimes it just needs early returns for common cases, or inlining string libraries and things like that to avoid allocations. Sometimes it helps to imagine yourself going through by hand the drudgery the computer is doing. If I was actually doing that boring work by hand, there's almost always ways I'd start taking short cuts. All thats left then is programming those shortcut into the computer. [1] https://www.inkandswitch.com/local-first.html https://www.inkandswitch.com/local-first.html

politician 5y ago

Great post! I had no idea that list CRDTs could actually be fast because I read the papers showing how they were impractical. Thanks for investigating and writing this up — please accept my offer of a legitimate academic credential.

GlennS 5y ago

When optimizing `findItem`, did you consider storing the original index of each item on itself and using that as a starting point? Obviously this might move later (maybe it can only increase?), but usually not by much, so I would guess it would make an efficient starting point / be immediately correct 99% of the time? Looks like you already have 2 good solutions to this though (start from index of recent edits and range tree).

thechao 5y ago

I love high level systems languages like C/++ and Rust… but everything you said about JavaScript being slow is the same thing assembly programmers experience when optimizing high level systems languages. In general, when I see C code and I’m asked to speed it up, I always use “100x” as my target baseline.

josephg 5y ago
Whoa thats a really impressive baseline to reach for when optimizing C code! I'd love to hear some war stories. As you can probably tell from my article, most of my skill at this stuff is from hard won tricks I've picked up over the years - like reducing heap allocations and packing memory for cache coherency. There's probably lots of things I just haven't learned because I haven't discovered it on my own. Do you have a blog, or any recommendations for stuff to read by you or others?
- thechao 5y ago
  I learned low level programming while at Intel, working with one of their performance teams; so, nothing written. In general, though, assembly is more expressive than higher level languages; it lets you “tighten up” the code the computer executes, reducing work & bandwidth. Specifically, a guy named Mike Abrash taught me some of this stuff, and he’s got some books explaining the theory in terms of practice.

deleted 5y ago

[deleted]

lewisjoe 5y ago

Thank you for writing this piece Joseph. Just want to make sure if something's a possible typo or I'm getting it all wrong :) Quote: "But how do we figure out which character goes first? We could just sort using their agent IDs or something. But argh, if we do that the document could end up as abcX, even though Mike inserted X before the b. That would be really confusing." Since the conflict is only between the children of (seph, 0) the only possibilities are, either ending up with "aXbc" or "abXc" right? Or is there a legitimate possibility of ending up with "abcX" ? I'm assuming we'll apply a common sorting logic only to clashing siblings.

josephg 5y ago
Good question. That part of the article could probably use another diagram to explain it. The resulting document is generated by doing a depth-first prefix traversal of the tree. The ambiguity comes because "b" and "X" are both direct children of "a". So its not clear how they should be ordered relative to each other. Because "c" is a child of "b" in this example, the "X" can't appear between the "c" and "b". The only valid orderings are, as I said, "aXbc" or "abcX". But without knowing how "b" and "X" should be ordered, its ambiguous which one to use. Let me know if thats still confusing! This stuff is hard to explain without a whiteboard.
- lewisjoe 5y ago
  Clear enough Joseph. Thanks :)

Majromax 5y ago

When you write: > Yjs does one more thing to improve performance. Humans usually type in runs of characters. So when we type "hello" in a document, instead of storing ['h','e','l','l,'o'], Yjs just stores: ['hello']. [...] This is the same information, just stored more compactly. Isn't this not just the same information when faced with multiple editors? In the first implementation, if I pause to think after typing 'hel', another editor might be able to interject with 'd' to finish the word in another way. In my view, these data structures are only "the same information" if you provide for a reasonably-sized, fixed quantum of synchronization. The merging makes sense if e.g. you batch changes every one or two seconds. It makes less sense if you would otherwise stream changes to the coordinating agent as they happen, even with latency.

goldenkey 5y ago
The chunking should depend entirely on the network synchronization. If synchronization is editing-debounced, then chunking could be applied rather safely.
josephg 5y ago
I didn't explain this well but the transformation is lossless. No data is lost from compressing like this. It has no impact on the concurrency protocol or network protocol; it just impacts how the data is stored locally. If we need to, we could split the run back out again into individual characters without losing information. And that does happen - we do that if something later gets inserted into the middle of the run of characters. Pausing doesn't help. Even the same user could later type something in the middle of a word they'd typed previously. This limits what we can run-length encode. The code in diamond only run-length encodes items when they are: - Typed sequentially in time - And sequentially in insert location (position 10, 11, 12, 13, ...) - And either all of the characters have been deleted or none of them have been deleted Notice the other fields in that example in the post. Each subsequent character has: - An id field = the previous id + 1 - A parent field = the id of the previous item - The same value for isDeleted If any of this stuff didn't match, the run would be split up. Instead of storing those fields individually, we can store the id and parent of the first item, an isDeleted flag and a length field. Thats all the information we actually need to store. With yjs style entries (which is what diamond-types actually implements), the code is here if you can make heads or tails of it. The poorly named "truncate" method splits an item in two. Spans are only extended if can_append() returns true: https://github.com/josephg/diamond-types/blob/c4d24499b70a2315df33627834f9085bcb486bc9/src/list/span.rs#L6-L57 https://github.com/josephg/diamond-types/blob/c4d24499b70a23... With real data from Martin's editing trace, 182 000 inserted characters get compacted down to 12 500 list items. Which is still pretty good - thats 14x fewer entries. And it means performance doesn't stutter when large paste events happen.

username91 5y ago

It's a great article - really informative and enjoyable to read. Thanks for making it happen. :)

conaclos 5y ago

Hi josephg, I'm a CRDT researcher. This is great to see so much work around CRDT nowadays! Some optimizations whom you discuss are already proposed by some papers and implementations. For instance, LogootSplit [1] proposes an implementation based on an AVL tree with extra metadatas to get a range tree. LogootSplit proposes also a block-wise approach that stores strings instead of individual characters. Xray [2], an experimental editor built by Github and written in Rust, uses a copy-on-write B-tree. Teletype [3] uses a splay tree to speedup local insertions/deletions based on the observation that a user performs several edits on the same region. [1] https://members.loria.fr/CIgnat/files/pdf/AndreCollabCom13.pdf https://members.loria.fr/CIgnat/files/pdf/AndreCollabCom13.p... [2] https://github.com/atom-archive/xray https://github.com/atom-archive/xray [3] https://github.com/atom/teletype https://github.com/atom/teletype

josephg 5y ago
Cool! It'd be interesting to see those CRDT implementations added to Kevin Jahns' CRDT Benchmarks page[1]. The LogootSplit paper looks interesting. It looks like xray is abandoned, and I'm not sure about teletype. Though teletype's CRDT looks to be entirely implemented in javascript[2]? If the authors are around I'd love to see some benchmarks so we can compare approaches and learn what actually works well. And I'm not surprised these techniques have been invented before. Realising a tree is an appropriate data structure here is a pretty obvious step if you have a mind for data structures. To name it, I often find myself feeling defensive when people read my work and respond with a bunch of links to academic papers. Its probably totally unfair and a complete projection from my side, but I hear a voice in my head reword your comment to instead say something awful like: "Cool, but everything you did was done before. Even if they didn't make any of their work practical, usable or good they still published first and you obviously didn't do a good enough literature review if you didn't know that." And I feel an unfair defensiveness arise in me as a result that wants to find excuses to dismiss the work, even if the work might be otherwise interesting. Its hard to compare their benchmark results because they used synthetic randomized editing traces, which always have different performance profiles than real edits for this stuff. Their own university gathered some great real world data in an earlier study. It would have been much more instructive if that data set was used here. At a glance their RAM usage looks to be about 2 orders of magnitude worse than diamond-types or yjs. And their CPU usage... ?? I can't tell because they have no tables of results. Just some hard to read charts with log scales, so you can't even really eyeball the figures. So its really hard to tell if their work ends up performance-competitive without spending a couple days getting their enterprise style java code running with a better data set. Do you think thats worth doing? [1] https://github.com/dmonad/crdt-benchmarks https://github.com/dmonad/crdt-benchmarks [2] https://github.com/atom/teletype-crdt https://github.com/atom/teletype-crdt

ta988 5y ago

This was a great read, thank you. I wish there were more explanations of the "black magic" part of Yjs. I'll have to dig into that.

josephg 5y ago
If you’re interested in learning more about Yjs’s internals, I interviewed Kevin for 3 hours on zoom and got him to take me through Yjs’s code. He’s a great guy. The video of that conversation is here: https://youtu.be/0l5XgnQ6rB4 https://youtu.be/0l5XgnQ6rB4
- ta988 5y ago
  Thanks a lot. Thats on my video queue.
nevf 5y ago
There's a series videos on YJS and whitepapers etc. Check out the YJS web site and search Youtube for details.

trishume 5y ago

Have you seen my Xi CRDT writeup from 2017 before? https://xi-editor.io/docs/crdt-details.html https://xi-editor.io/docs/crdt-details.html It's a CRDT in Rust and it uses a lot of similar ideas. Raph and I had a plan for how to make it fast and memory efficient in very similar ways to your implementation. I think the piece I got working during my internship hits most of the memory efficiency goals like using a Rope and segment list representation. However we put off some of the speed optimizations you've done, like using a range tree instead of a Vec of ranges. I think it also uses a different style of algorithm without any parents. We never finished the optimizing and polished it up, so it's awesome that there's now an optimized text CRDT in Rust people can use!

neolog 5y ago
Out of curiosity, what do you use to make those diagrams?
- trishume 5y ago
  https://www.figma.com/ https://www.figma.com/ and putting a lot of effort into them
josephg 5y ago
Oooohhhh no I haven’t read that - thanks for the link! I feel embarrassed to say this but I knew about Xi editor years ago but I totally forgot to go read & learn about your crdt implementation when I was learning about Yjs and automerge and others. I’ll have a read. And thanks for writing such an in depth article. It’s really valuable going forward. Maybe it’s addressed in your write up but are there any plans for that code, or has everyone moved on? I’d love to have a zoom chat about it and hear about your experiences at some point if you’d be willing.

pookeh 5y ago

Wait it doesn't look like you used the performance branch of automerge (which is now merged into master). It is significantly faster. https://github.com/automerge/automerge/pull/253 https://github.com/automerge/automerge/pull/253

josephg 5y ago
I did use the performance branch. And I had a chat with a few people in the automerge community about the performance numbers I was seeing long before I published to see if I was doing anything wrong. I tested a few different versions of automerge but in this test there wasn’t much performance difference between 0.12, 1.0.x-preview versions (which are built from the merged performance branch) and I tried the unreleased automerge-rs. When I ran my tests timing numbers for automerge ranged from about 5m with the old non performance branch down to about 4m20s or so with automerge-rs. Still far from Yjs’s 0.9 seconds. I just checked and it looks like automerge 1.0.1-preview-4 has landed. I wrote the post benchmarking preview-2. I’ve been knee deep in diamond types lately and haven’t been watching. Fingers crossed there’s some more performance improvements in the pipeline. I’d love to do a follow up in 6 months showing much improved performance.

benjismith 5y ago

I've been following your work for years (and I'm actually neck-deep in a ShareDB project right now) so I just want to say thank you for all of your contributions! I especially enjoyed this post.

gfodor 5y ago

Thanks for ShareDB. It’s dope. I extended it to support collaborative voxel editing (https://jel.app https://jel.app) and works great.

josephg 5y ago
Oh that’s cool!! Did you use json-ot for that? I haven’t touched that code in years and it’s delightful people are actively maintaining it and using it to make cool stuff.
- gfodor 5y ago
  I use ot-json for other stuff, but wrote my own ot-vox which deals with voxel grid cells that can be assigned a color.

xcombelle 5y ago

I believe that I understood the code tagged as follow > (But don't be alarmed if this looks confusing - we could probably fit everyone on the planet who understands this code today into a small meeting room.) and the follow up reading confirm what I believed about this code should I be worried about myself ?

fulafel 5y ago

Terminology nit: cache coherence refers to CPU cache implementation behaviours at hw level in presence of concurrent access from multiple cores. Data locality or cache friendly data layout could work better here.

josephg 5y ago
Good point - thanks. I'll tidy that up!