Hacker News new | past | comments | ask | show | jobs | submit login

Excellent. This approach to CRDTs existed even before the term itself was invented. In the 2010 article[2] on Causal Trees[1], your humble servant calls these per-peer op logs "yarns". In the 2011, observing the proliferation of proposals, Shapiro&friends propose[3] the term "CRDT".

That is essentially a partially-ordered approach to oplogs. Oplogs (binlogs, WALs) underlie the entire universe of databases. The problems are exactly the same as the problems "normal" database developers faced in the far past: how much history do you want to keep? How to synchronize the log and the state reliably? What is the format of the log? How to store/transfer the log reliably?

The last question seems trivial, but it is not. If you read some databases' source code, you may find a lot of paranoid things[4], obviously inspired by humiliating real-life incidents. The other questions are not trivial by any means.

So, yes, this is the way[5].

[1]: Alexei "archagon" Baboulevitch excellent popular summary of Causal Trees, 2018 http://archagon.net/blog/2018/03/24/data-laced-with-history/

[2]: The 2010 paper https://www.researchgate.net/publication/221367739_Deep_hype...

[3]: The CRDT paper https://pages.lip6.fr/Marc.Shapiro/papers/RR-7687.pdf

[4]: e.g. https://github.com/facebook/rocksdb/blob/main/db/log_reader....

[5]: the simultaneous post by Nikita Prokopov https://tonsky.me/blog/crdt-filesync/




Thanks for the links, awesome!


...and they existed long before 2010, too. 1975 called, and said to check out the SCCS "Weave" data structure: https://en.wikipedia.org/wiki/Interleaved_deltas

Weaves are the same thing as modern text CRDTs!




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: