10 ms·
Faster CRDTs (2021)
- fredrikholm 2y agoI remember stumbling over this post a few years ago. Really entertaining post, one of my favorites in recent years.
- luke-stanley 2y agoCould be good to have the date put with the title?
- gchamonlive 2y agoJuly 31 2021
- dang 2y agoAdded above.
- JohnDeHope 2y agoYeah, new rule: I don't believe anything in a published scientific paper until it has been independently verified for the third time. I don't even want to hear about it, before then, unless I read the journal the original (or second) paper was published in. What I'd really like, and would subscribe to even as a lay person, is the JOURNAL OF STUDIES WHOSE FINDINGS HAVE BEEN SUCCESSFULLY REPRODUCED FOR THE THIRD TIME. I'd pay for a subscription to that.
- lylejantzi3rd 2y agoMe too.
- kirubakaran 2y ago- https://news.ycombinator.com/item?id=28017204 https://news.ycombinator.com/item?id=28017204 (3 years ago, 151 comments) - https://news.ycombinator.com/item?id=33903563 https://news.ycombinator.com/item?id=33903563 (2 years ago, 22 comments) - https://news.ycombinator.com/item?id=41372833 https://news.ycombinator.com/item?id=41372833 (this post) - https://news.ycombinator.com/item?id=41373288 https://news.ycombinator.com/item?id=41373288 (this comment)
- deleted 2y ago[deleted]
- dang 2y agoThanks! Macroexpanded: 5000x faster CRDTs: An adventure in optimization (2021) - https://news.ycombinator.com/item?id=33903563 https://news.ycombinator.com/item?id=33903563 - Dec 2022 (22 comments) Faster CRDTs: An Adventure in Optimization - https://news.ycombinator.com/item?id=28017204 https://news.ycombinator.com/item?id=28017204 - July 2021 (151 comments)
- IshKebab 2y ago(2021) and Automerge's Rust implementation seems to have landed so it would be interesting to see an updated benchmark.
- josephg 2y agoAuthor here. Yjs has also been rewritten in rust (yrs) and it’s significantly faster than the JavaScript version. I’ve also got a new, totally different approach to solving this problem too. It would definitely be good to update the benchmarks. Everything has gotten faster.
- britannio 2y agoBut in the eg-walker paper, you benchmark against Yjs rather than Yrs because Yrs performed worse?
- demircancelebi 2y agowould love to read the totally different approach
- og2023 2y agoAbsolutely support this, so do I!
- endlessvoid94 2y ago[flagged]
- jzelinskie 2y agoWhat are some real world apps using CRDTs that have really good experiences? IIRC Notion was supposed to be one of them but realistically taking notes with two people in Notion is almost unusable compared to Google Docs.
- danielvaughn 2y agoFigma uses a CRDT-ish approach. I'm working on one at the moment, but it'll be a while before it's publicly available. At the moment, I'm using Loro: https://loro.dev https://loro.dev
- spacecadet 2y agoNot a public high bandwidth example, but a consulting team I was on implemented CRDTs in a private mobile app used for a compliance documentation use case. More of a precaution, the actual number of end-users editing a record at any given time is expected to be 1, but while reviewing their system, we found that the clients system can support multiple and sometimes their employees don't communicate/follow procedures. We first tried to convince them to make changes on their end, but their development team straight up refused.
- yazaddaruvala 2y agoIn practice, Git Some CRDT purists would say "its not perfectly conflict free so its not a CRDT". Sure[0], but for the rest of us that are pragmatic about best effort conflict resolution Git is likely the most successful CRDT application. [0] https://en.wikipedia.org/wiki/No_true_Scotsman https://en.wikipedia.org/wiki/No_true_Scotsman
- kiitos 2y agoCRDT literally means Conflict-free Replicated Data Type. Expecting CRDTs to be conflict-free isn't purism, it's simple validation. Git is, inarguably, not a CRDT.
- yazaddaruvala 2y ago> CRDT literally means Conflict-free Replicated Data Type. Git could be "conflict-free" with a simple `rand(ours, theirs)`. It would be useless, but technically "conflict-free". Is the addition or removal of that rand function really, pragmatically the difference in the answer to "what is a CRDT?"
- ericyd 2y ago> Why is WASM 4x slower than native execution? I thought it was because every string operation had to be copied into WASM memory and then back into JS when the result was computed. Am I wrong? Am I misunderstanding the context? Genuinely curious!
- echelon 2y agoThat strikes me as the likely plausible culprit. The one that keeps tripping me up in unrelated domains is that the multithreading story is not easy or fully supported by libraries and tooling. We've run game engines and utility binaries (ffmpeg, zip, etc.) in the browser and they're super slow because of this.
- josephg 2y agoAuthor here. This post was from a few years ago but from memory I controlled for that. So the problem wasn't FFI. I loaded the whole history into wasm before I started timing, then processed it in an inner loop that was written in rust, running in the wasm context itself. There were only 2 calls to wasm or something. The 4x slowdown wasn't FFI. The algorithmic code itself was actually running 4x slower. It'd be interesting to rerun the benchmark now. I assume compilers are better at emitting wasm, and wasm runtimes have gotten faster. I'm sure I've still got the benchmarking code around somewhere.
- ericyd 2y agoInteresting, thanks for the reply!
- Validark 2y agoI think the better question is why would someone expect them to be the same? I haven't worked on a WASM interpreter or JIT, but how often is it better to go through multiple layers of translation instead of one? Translating high level code to WASM, or any assembly language, makes you lose a lot of the "intent" embedded in the higher level code. In lower-level code, you often see a series of language-specific idioms for accomplishing the goal, that may or may not have direct equivalents on your actual machine. In the case of modern x86-64, you have a ton of instructions that are far more powerful than what you can do in WASM. Decompilers exist of course, and maybe a list of macro-op fusions exists where a WASM JIT can do a relatively simple pattern match and get good native code (probably not though, and good luck with cross-platform optimization). And, LLVM is definitely not perfect, there's definitely low-hanging fruit where a post-processing optimizer could make improvements. So it is theoretically possible to make WASM faster than LLVM's native emit by doing something equivalent to an optimization step LLVM should have but doesn't at the moment. But I highly, highly doubt that you'd get just as good results without some seriously well-laid plans, which I doubt exist, or by creating a set of instructions which is, in effect, a superset of what target ISAs support. From what I've seen, it's a subset, so good luck trying to canonicalize the operations and merge them back together in real time. Not entirely impossible of course, but it would be a serious feat of engineering. Intuitively, if I wrote a book in English, then it got translated to a very different language that's also limited to only a few thousand words, then translated back to English, it wouldn't be exactly the same text. There would be concepts that have to be explained with a paragraph that, in English, would only take a single word. Getting my English back out would require a 1-to-1 translation of everything, or a list of paragraph-to-1 translations that both translators agree upon.
- felipefar 2y agoCRDTs are powerful, but it's unfortunate that they leave behind a trail of historical operations (or elements), both in their ops- or state-based variants. Even with compression, it's still a downside that makes me concerned about adopting them. Even so, the discussion surrounding them made me excited by the possibility of implementing conflict-free (or fine-grained conflict resolution) algorithms over file-based storage providers (Dropbox, Syncthing, etc.).
- jakelazaroff 2y agoIf you’re not building something fully decentralized, you may be able to loosen some of the constraints CRDTs require. As an example, if you can guarantee that all clients have received changes later than X date, you can safely drop any operations from before that date.
- shipp02 2y agoCould you also make it fully decentralized but require clients to come online within a deadline (1 day, week) or risk losing their local changes? This would also allowing trimming history but with loss of some functionality to sync.
- jakelazaroff 2y agoYes, you can go that direction as well, although in a decentralized architecture there’s no shared notion of “coming online”. For example: 1. you have four peers collaborating on a document 2. for some extended period peer A only communicates with peer B and peer C only communicates with peer D (and vice versa) 3. the peers truncate the operations at some point within that period 4. each pair of peers now has a document irreconcilable with the other even though all peers “came online” recently
- jchanimal 2y agoThe full op-log plus deterministic merging is a great fit for immutable block storage, which can have other security, performance, and cost benefits. I'm building Fireproof[1] to take advantage of recent research in this area. An additional benefit to content addressing the immutable data is that each operation resolves to a cryptographically guaranteed proof (or diff), enforcing causal consistency and allowing stable references to be made to snapshots. This means your interactive, offline-capable, losslessly-merging database can run on the edge or in the browser, but still have the integrity you'd have looked to a centralized database or the blockchain for in the past. (Eg you can drop a snapshot CID into a PDF for signature, or a smart contract, and remove all ambiguity about the referenced state. [1] https://github.com/fireproof-storage/fireproof https://github.com/fireproof-storage/fireproof
- pjz 2y ago> And why 32 entries? I ran this benchmark with a bunch of different bucket sizes and 32 worked well. I have no idea why that worked out to be the best. If you were using 2-byte ints, this is likely because cache lines are 64 bytes, so 32 entries would be exactly one cache line, letting each cache line hold an entire bucket, thus reducing those expensive main memory transfers.
- VHRanger 2y agoYeah when benchmarking by batch sizes it's common to see huge jumps associated with the memory hierarchy: - word size (64bits) - cache alingment fetch size (generally 64bytes as mentioned above) - OS page size (4-16kb) - L1 size (~80kb/core) - L2 (low megabyte number)
- hinkley 2y agoWith lots of bizarre artifacts if you don’t force alignment.
- taeric 2y agoI really like the way Knuth benchmarks many of his later programs. He basically puts a counter for how many times something has to be loaded from memory. Would be curious to know if you could approximate how many times you have to clear cache lines, in the same way?
- kmoser 2y agoThis is one of those rare articles which, although much of the material is over my head, I couldn't stop reading because it's written so well.
- josephg 2y agoAuthor here. Very kind :)
- EGreg 2y agoCan someone explain to me please why CRDTs are slow? This article suggests the future to me: https://joelgustafson.com/posts/2023-05-04/merklizing-the-key-value-store-for-fun-and-profit https://joelgustafson.com/posts/2023-05-04/merklizing-the-ke... Take a look at this and compare it to Y.js or automerge: https://github.com/canvasxyz/okra-js https://github.com/canvasxyz/okra-js
- josephg 2y ago> Can someone explain to me please why CRDTs are slow? Author here. The main reason was that a lot of CRDT libraries were written by academics, who don't have the time, skill or interest in optimising them. Since writing this article a few years ago, all the major CRDT libraries have gotten orders of magnitude faster.
- riedel 2y agoQuoting the current github Readme [0]: >And since that blog post came out, performance has increased another 10-80x (!). [0] https://github.com/josephg/diamond-types https://github.com/josephg/diamond-types
- arkh 2y agoSeeing the hierarchical structure used I wonder if they tried using nested set instead. No idea if a possible gain in read operation would offset the losses in insertions.