CRDTs: The Hard Parts

Channel:Martin Kleppmann · Length:1:10:09 · Published:2020-07-06 · Views:90832

Watch on YouTube

Summary

Martin Kleppmann surveys current research on CRDTs, the algorithms for merging concurrent edits across offline replicas. He covers the hard parts such as rich text, moves and merge results that are technically correct but poor.

Why HN recommends it

Recommended as an excellent first education on CRDTs and their limits.

I found this video from him to be an excellent first education on CRDTs — HN, 2021

Distributed systems · Algorithms & data structures

Subtitles (excerpt)

hello everybody my name is Martin clapman I'm a researcher of the University of Cambridge and today I'd like to talk about some of our work on conflict free replicated data types or CRD T's so I'm going to start this talk with a very brief introduction as to what CR duties are and why they are useful but most of this talk is going to be about new results that we have figured out only within the last year or two so you might know me from this book here which I wrote a couple of years ago it's called designing data intensive applications and it's a broad overview of the architecture of data systems and how to choose your database for your particular application that's not what we're talking about today so today we're talking about collaboration software so in collaboration software I'm taking a fairly broad view of this this is any kind of software where several users can come in and update a document or database or some kind of state shared state and various examples of software that fits in this category Google Docs is an obvious example where you can have several people editing a document at the same time create a text document or spreadsheet similar things you get with office 365 figma is an example of graphics

On Hacker News

The author is a researcher on distributed systems. I found this video from him to be an excellent first education on CRDTs, how they work, what they're good for and what they aren't (yet) good for: [VIDEO] — rkangel, 2021-01
What they claim is that if all editing stops, then after a period of time everybody will be looking at the SAME document. This is what is meant by "eventual consistency". Achieving this in general is indeed a difficult problem, but (some of) these algorithms do solve it, though it can be tricky to correctly prove that they do. I agree that it is not possible to ensure that the document everybody … — williamstein, 2024-12
Ah, I'll put it in as a note in the beginning. You can see a more basic introduction in a previous post I wrote: [LINK] [LINK] Here's some introductory material I found helpful: - [An interactive intro to CRDTs]( [LINK] ) - [An introduction to state-based CRDTs]( [LINK] ) - [CRDTs for non-academics]( [LINK] ) - [CRDT: The Hard Parts]( [VIDEO] ) - [Readings in CRDTs]( [LINK] ) - [crdt.tech]( [LINK… — iamwil, 2024-01
We are almost there, for lists and structs there are CDRT's but a move operation across the data structure is missing. Martin Kleppman (from automerge) talks about this in his talk "CRDTs: the hard parts"[0]. I also think a range move or range delete is missing from many of these algorithms. A submission here on HN did implement a range delete on rich text (but I forgot what the name was). [0]: [… — thomasikzelf, 2021-12
Disclosure: I work on a related project (Fluid Framework) that makes application agnostic CRDTs easily available. The CKEditor folks did a great job building an OSS text editor and they did an especially strong work building a text editor that works well with collaboration. I've made a few OSS rich text editors work (mostly) with Fluid [0, 1] and the design of the text editor really changes how e… — sambroner, 2020-12

Related videos