Victor Grishchenko, Mikhail Patrakeev
2020 · arXiv
Chronofold is a replicated data structure for versioned text. It is designed for use in collaborative editors and revision control systems. Past models of this kind either retrofitted local linear orders to a distributed system (the OT approach) or employed distributed data models locally (the CRDT approach). That caused either extreme fragility in a distributed setting or egregious overheads in local use. Overall, that local/distributed impedance mismatch is cognitively taxing and causes lots of complexity. We solve that by using subjective linear orders locally at each replica, while inter-replica communication uses a distributed model. A separate translation layer insulates local data structures from the distributed environment. We modify the Lamport timestamping scheme to make that translation as trivial as possible. We believe our approach has applications beyond the domain of collaborative editing.
Metadata: arXiv. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
4 selected excerpts · 4 total mentions
In 2007 Bram said to me that my Causal Tree algorithm is a variant of weave. Which is broadly correct. In these 20 years, the family of weave-class algos grew quite big. In my 2020 article, I devoted the intro to making their family portrait https://arxiv.org/abs/2002.09511 Could have been a separate article.
There was a recent post of a series that dives into CRDTs [1] . Someone linked to a paper, Chronofold: a data structure for versioned text [2] dated this April, that attempts to map CRDT semantics onto text editing. It's still on my list. [1]: https://news.ycombinator.com/item?id=23737639 [2]: https://arxiv.org/pdf/2002.09511v4.pdf
After studying [3], I came to the conclusion that the specific CRDTs they attempted to use for Xi editor might be too low level to be useful in building a text editor directly, but that this is not an intrinsic shortcoming of CRDTs. Rather, the kind of automerging behavior of the CRDTs they used didn't match the design needs of the editor. (btw, check out chronofold, designed for text: https://arxiv.org/abs/2002.09511v4 ) Anyhow, I've come to see CRDTs as very low level primitives that can assist in creating decentralized applications. Their strength is not that they automagically solve the inherently subjective problem of merging asynchronously edited, divergent data.…
That problem is more of a design problem that needs to be solved on a case by case basis. The strength of CRDTs is in that they have extremely well defined behavior and aren't fundamentally reliant on a central coordinator or leader. Of course you can design in a leader if you want, or multiple leaders. But that has nothing to do with CRDTs. So I imagine them being more useful in composing higher level data structures and smooth interfaces for users to make inherently difficult decisions about merge conflicts themselves. My favorite kind of CRDTs are "delta state CRDTs". They're very cool. I wish the paper about them was easier to understand.
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 is also an article which might be a tough reading, so no link. Recently I greatly improved CTs by introducing the Chronofold data structure [2]. Regarding that benchmark article, I spent many years in academia, so the quality of content problem is familiar to me. In other words, I don't take such articles seriously. CRDTs are fast enough, that is not a concern. [1]: https://github.com/gritzko/citrea-model [2]: https://arxiv.org/abs/2002.09511
More from the same topics.
Martin Kleppmann
The CAP Theorem is a frequently cited impossibility result in distributed systems, especially among NoSQL distributed databases.
Haoran Xu, Fredrik Kjolstad
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
David Manheim, Scott Garrabrant
There are several distinct failure modes for overoptimization of systems on the basis of metrics.
Donald E. Knuth
The author presents two tricks to accelerate depth-first search algorithms for a class of combinatorial puzzle problems, such as tiling a tray by a fixed set of polyominoes.