Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Faster CRDTs: An Adventure in Optimization

josephg.com

Post reply on HN
Print view View original

41–50 of 154 posts

Re: Faster CRDTs: An Adventure in Optimization

#41

Post by josephg »

the-smug-one wrote: post #23
saurik wrote: post #12

Earlier quoted context omitted.

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…

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.

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

Re: Faster CRDTs: An Adventure in Optimization

#43

Post by __s »

feikname wrote: post #15

Correct me I'm mistaken The difference between diamond native and diamond WASM demonstrates how, even with WASM, native implementations beat browsers hard , and native implementations performance-wise are still very worth, specially for lower powered devices, and, perhaps, reducing battery usage (as consequence of less CPU use) in mobile devices.

Yes. Ultimately WASM is executing within a sandbox & involves being JIT compiled (read: not heavily optimized except for hot loops eventually). If native compilation is an option it makes sense to go that route

WASM competes with asm.js not asm (or, arguably, jvm etc)

Re: Faster CRDTs: An Adventure in Optimization

#44

Post by josephg »

stephc_int13 wrote: post #34

Trees are a powerful and practical data structure, but even if it does not appear clearly when doing O(n) style complexity analysis, they are usually slow. Unfortunately, the difference between slow and fast can be several orders of magnitude, while the perception of the programmer doing a back of the envelope analysis seems to be a logarithmic scaling of the reality...

Trees seemed to work pretty well for me here!

The problem with trees is usually that people don't pack enough data into each node in the tree. I implemented a skip list in C a few years ago[1]. For a lark I benchmarked its performance against the C++ SGI rope class which was shipped in the C++ header directory somewhere. My skip list was 20x faster - which was suspicious. I looked into what the SGI rope does and it turns out it was only putting one character into each leaf node in the tree it constructed. Benchmarking showed the optimal number was ~120 or so characters per leaf. Memcpy is much much faster in practice than main memory lookups.

In diamond-types (benchmarked here), the internal nodes in my B-tree store 16 pointers and leaf nodes store 32 entries. With run-length encoding, all 180,000 inserted characters in this data set end up in a tree with just 88 internal nodes and a depth of 3. It goes fast like this. But if you think an array based solution would work better, I'd love to see it! It would certainly need a lot less code.

[1] https://github.com/josephg/librope

Re: Faster CRDTs: An Adventure in Optimization

#45

Post by omgtehlion »

gritzko wrote: post #35

About a decade ago, I implemented the Causal Tree CRDT (aka RGA, Timestamped Insertion Tree) in regular expressions using a Unicode string as a storage. Later we made a collaborative editor for Yandex based on that code. It used many of the tricks as described in the text, even the optimization where you remember the last insertion point. So I am terribly glad it all gets rediscovered. The code is on GitHub [1] There…

That is nice!

A couple of questions: Do you have released a CT implementation in top of Chronofold? Have you any plans to benchmark it against other algs?

Re: Faster CRDTs: An Adventure in Optimization

#46

Post by josephg »

Jweb_Guru wrote: post #19
feikname wrote: post #15

Correct me I'm mistaken The difference between diamond native and diamond WASM demonstrates how, even with WASM, native implementations beat browsers hard , and native implementations performance-wise are still very worth, specially for lower powered devices, and, perhaps, reducing battery usage (as consequence of less CPU use) in mobile devices.

The wasm implementation here was still running under a JavaScript test harness, so I suspect it's the JS-WASM boundary interactions that are causing the slowdown. WASM itself (if it doesn't need to interact with JavaScript) usually runs with a much smaller performance penalty.

I suspect so too - given there are 280 000 calls across the JS-wasm boundary, and most of those calls pass a string. I'd love to know for sure though. I considered making this benchmark pass the whole data set in one go through JSON or something, but that felt like cheating - since thats not how the API would be used in practice during a real editing session.

But even paying that cost, it still seems much faster to use rust + WASM than run the same algorithm in native javascript. And the JS-wasm boundary will probably get gradually faster over the next few years.

Re: Faster CRDTs: An Adventure in Optimization

#47

Post by lewisjoe »

I've been looking for a practical OT alternative for our online word processor (https://zoho.com/writer). We already use OT for syncing our realtime edits and exploring CRDTs targetting stronger consistency for tackling offline edits (which are typically huge & defragmented, since the edits are not syncing in realtime)

So the baseline is that OT has a better model for holding state in terms of performance/memory, since the edits can be compiled into plain string types. CRDTs in comparison forces us to hold deleted states as well and demands richer information per unit (character/string/etc) - which makes it harder on the CPU/RAM.

Here's the story as I understand:

1. Automerge tackles this by just moving to a better lower-level runtime: Rust.

2. Yjs handles this by using a similar technique i.e relying on V8's hidden classes to handle the performance optimizations and assuming real-world cases to narrow down and optimize datastructures.

But none of these, seem to be a fundamental breakthrough in the efficiency of the algorithm itself. They all at best look like a workaround and this keeps bothering me.

Re: Faster CRDTs: An Adventure in Optimization

#48

Post by Majromax »

josephg wrote: post #36
Majromax wrote: post #27

Earlier quoted context omitted.

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 'h…

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 r…

Ah, I see. I had thought that the consolidation gave a batched update with a single ID, so 'h' + 'ell' + 'o' would have IDs of 1, 2, and 3 respectively. That would have made an editing conflict in the middle of 'ell' impossible.

Re: Faster CRDTs: An Adventure in Optimization

#49

Post by pfraze »

lewisjoe wrote: post #47

I've been looking for a practical OT alternative for our online word processor ( https://zoho.com/writer ). We already use OT for syncing our realtime edits and exploring CRDTs targetting stronger consistency for tackling offline edits (which are typically huge & defragmented, since the edits are not syncing in realtime) So the baseline is that OT has a better model for holding state in terms of performance/memory, s…

You can remove tombstones in a cleanup pass if you constrain behavior a bit.

For instance, if there’s just a single server, after 5 minutes of no active connections you could clean out tombstones. After that, if a client connects with some changes they had been holding onto but got DCed, you can reject the write and let the user’s client merge by some other means (perhaps even manual).

Re: Faster CRDTs: An Adventure in Optimization

#50

Post by Jailbird »

teodorlu wrote: post #4
josephg wrote: post #2

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

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?

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?)

Post reply on HN