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

51–60 of 154 posts

Re: Faster CRDTs: An Adventure in Optimization

#51

Post by detaro »

Jailbird wrote: post #50
teodorlu wrote: post #4

Earlier quoted context omitted.

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

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.

Re: Faster CRDTs: An Adventure in Optimization

#53

Post by teleforce »

This previous HN discussions on OT vs CRDT paper is an excellent overview of the topics [1],[2].

From the paper conclusions "Our discoveries from this work revealed facts and evidences that refute CRDT superiority claims over OT on all accounts, which helps to explain the underlying reasons behind the choices between OT and CRDT in the real world."

The fact that the paper provided the refutation to one of the HN discussion points being made in [1] (i.e. reference to itself), regarding the claimed of CRDT superiority in its footnotes is rather amusing and the first such attempt I have personally seen in a published paper.

[1]https://news.ycombinator.com/item?id=18191867

[2]https://arxiv.org/abs/1810.02137

Re: Faster CRDTs: An Adventure in Optimization

#54

Post by josephg »

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…

If you've got big offline edits (or you're merging multiple large sets of edits), even existing CRDTs will generally handle that more efficiently than OT will. OT algorithms are usually O(n * m) time complexity when merging n edits from one peer with m edits from another peer. A CRDT like diamond-types is O((n + m) * log(s)) where s is the current size of the document. In practice its super fast.

As for holding deleted states and richer information per unit, its not so bad in absolute terms. 1-2mb of data in memory for a 17 page document is honestly fine. But there's also a few different techniques that exist to solve this in CRDTs:

1. Yjs supports "garbage collection" APIs. Essentially you say "anything deleted earlier than this point is irrelevant now" and the data structures will flatten all runs of items which were deleted earlier. So storage stays proportional to the size of the not-deleted content.

2. Sync9 has an algorithm called "antimatter" which mike still hasn't written up poke poke mike!. Antimatter actively tracks the set of all peers which are on the network. When a version is known to have been witnessed by all peers, all extra information is safely discarded. You can also set it up to assume any peer which has been offline for however long is gone forever.

3. Personally I want a library to have an API method for taking all the old data and just saving it to disk somewhere. The idea would be to reintroduce the same devops simplicity of OT where you can just archive old history when you know it probably won't ever be referenced again. Keep the last week or two hot, and delete or archive history at will. If you combined this with a "rename" operation, you could reduce the "hot" dataset to basically nothing. This would also make the implementation much simpler - because we wouldn't need all these performance tricks to make a CRDT like diamond-types fast if the dataset stayed tiny anyway.

Re: Faster CRDTs: An Adventure in Optimization

#55

Post by johnarno »

If it weren’t for academic papers, we probably wouldn’t have the beautiful and nice concept of a CRDT in the first place. We might have 100 different solutions promising us 100 different replication schemes, some with and some without guarantees, hiding behind a gazillion different undefined terms that want to make us believe each solution is better than sliced bread. Also, I don’t thing Google Wave didn’t make it due to its OT algorithm.

Re: Faster CRDTs: An Adventure in Optimization

#57

Post by Jailbird »

detaro wrote: post #51
Jailbird wrote: post #50

Earlier quoted context omitted.

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

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.

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.

Re: Faster CRDTs: An Adventure in Optimization

#58

Post by conaclos »

josephg wrote: post #2

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

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.p... [2] https://github.com/atom-archive/xray [3] https://github.com/atom/teletype

Re: Faster CRDTs: An Adventure in Optimization

#59

Post by josephg »

Majromax wrote: post #48
josephg wrote: post #36

Earlier quoted context omitted.

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.

Ah that makes sense! Concurrent changes are one thing, but concurrent changes are rare. The big problem if we did it that way is that it would become impossible to insert in the middle of "ell", because we wouldn't be able to name any of those internal positions.

To get around that we assign a sequential ID for every inserted character, regardless of how they're typed or stored. Typing "hello" would assign IDs 1-5 even if you paste "hello" from the clipboard.

Re: Faster CRDTs: An Adventure in Optimization

#60

Post by gritzko »

omgtehlion wrote: post #45
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?

Thanks. No, I didn't release it, although there are implementations on GitHub. Rust and Kotlin, at least. The RON proof-of-concept wiki runs on the (unreleased) C++ implementation [1]. I benchmarked it at some point, everything was like "k nanoseconds" [2].

[1]: http://doc.replicated.cc/%5EWiki/ron.sm

[2]: https://github.com/dmonad/crdt-benchmarks/issues/3#issue-599...

Post reply on HN