CRDTs: The Hard Parts
Channel:Martin Kleppmann · Length:1:10:09 · Published:2020-07-06 · Views:90832
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
- The Only Unbreakable Law · Molly Rocket · 53:25
- Preventing the Collapse of Civilization / Jonathan Blow (Thekla, Inc) · DevGAMM · 1:02:41
- "I See What You Mean" by Peter Alvaro · Strange Loop Conference · 52:29
- The Soul of Erlang and Elixir • Sasa Juric • GOTO 2019 · GOTO Conferences · 42:02
- "Testing Distributed Systems w/ Deterministic Simulation" by Will Wilson · Strange Loop Conference · 40:20
- CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step” · CppCon · 59:33
- Erlang Factory 2014 - That's 'Billion' with a 'B': Scaling to the Next Level at WhatsApp · Erlang Solutions · 49:15
- "Turning the database inside out with Apache Samza" by Martin Kleppmann · Strange Loop Conference · 47:42
- The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever? · Reducible · 28:23
- Modern Dictionaries by Raymond Hettinger · SF Python · 1:07:41
- The Language of the System - Rich Hickey · ClojureTV · 1:02:49
- Google I/O 2012 - Go Concurrency Patterns · Google for Developers · 51:27
- Conflict Resolution for Eventual Consistency • Martin Kleppmann • GOTO 2016 · GOTO Conferences · 51:35
- "Unison: a new distributed programming language" by Paul Chiusano · Strange Loop Conference · 41:05
- CppCon 2014: Chandler Carruth "Efficiency with Algorithms, Performance with Data Structures" · CppCon · 1:13:41
- CppCon 2017: Juan Pedro Bolivar Puente “Postmodern immutable data structures” · CppCon · 1:05:59