We're all so used to Dropbox cloud sync and co-authoring in Google Docs that combining the results of different users' actions can seem like a long-standing problem. But in fact, there are many pitfalls in this matter, and work on CRDT algorithms is still in full swing.
One of the people behind this work is Martin Kleppmann, a researcher at the University of Cambridge and creator of the popular Automerge library . And at the Hydra conference, he talked about a few things that he had researched literally in the last couple of years. What user actions can cause Google Drive to issue an "unknown error"? Why in CRDT metadata about work on a document can take up a hundred times more space than the document itself, and how to deal with this? What problem doesn't even have a known solution right now?
He told about all this in the report, and now we have made a text translation for Habr. Video and translation - under the cut, then the narration will be on behalf of the speaker.
Contents of the report
CRDT (Conflict-free Replicated Data Types, ). , , , . , . (collaborative software).
, , - . . Google Docs Office 365 . Figma. Trello , . , .
( ).
, . , , «Hello!». «World», :
, , . : «Hello World! :-)».
. , , . , . , . , Git. , , .
, :
- (operational transformation, OT), Google Docs .
- 15 : CRDT.
, .
. , , «Helo», . «l», — . :
. — . , . . «l» — 3, — 4.
- . , 3 «l», . . 4, «Hell!o», 3, - . 4 5. — . .
, . Bluetooth, ( Google Docs Google). , . , , — Bluetooth, P2P .
CRDT . , . , , . , , CRDT.
CRDT . , , , . ; , .
. , , — . , , .
, , — , . , , , — . . , CRDT, , , — . CRDT .
. :
, .
, . CRDT ; . . . , 0 1, 0 — , 1 — . «Helo» 0.2, — 0.4, — 0.6, — 0.8.
«l» «l» «o» 0.6 0.8 — , 0.7. 0.9.
. , , , , . , , . . , .
, , , .
. , . .
«Hello!». « Alice» , « Charlie». . ? , , .
«o» 0.64, — 0.95. , 0.64 0.95. , .
, . , , , , . , - , .
, . . — , . , . , .
CRDT , .
— Logoot LSEQ. - . , . Treedoc WOOT , , , . , , LSEQ, Treedoc WOOT. . , Astrong — , , . , .
RGA
— RGA. , , , , , . .
, « reader» «Hello» «!», « reader» « dear». . « Alice» «Hello» «!». RGA : «Hello dear Alice reader!». , , .
, . RGA , .
, . . — «Hello!». — «reader», «Alice» «dear». RDA , . , , , . .
RGA — . , . , - - , RGA , . RGA .
Logoot LSEQ , , , , , - . RGA, , . , PaPoC 2019 . .
. , , , , , .
CRDT-. , , CRDT . CRDT . . , .
, , — .
: «phone joe» . , . , , . , «phone joe» . , .
: ?
, . «phone joe» , — «buy milk». ? , , «phone joe», , «buy milk». . . , , , . , «phone joe» .
? CRDT, . , , . last writer wins register. , , .
, . . last writer wins register, , — . «phone joe» , «buy milk», , . .
CRDT (last writer wins register). , . -, , , -, ( , ). , .
, . CRDT . , , CRDT. , Treedoc , Logoot — , RGA — . CRDT . . , , last writer wins register.
, last writer wins . : CRDT add-wins set (AWSet ):
add-wins set, , , (, ) last writer wins . last writer wins AWSet, CRDT last writer wins register. , CRDT CRDT, CRDT . — , , . , CRDT . CRDT .
. , , , . , . . :
, «Milk» , . «Milk» «Soy milk». «Milk», . , . ? — «Milk» «Soy milk». , , , .
, . «Milk» , . «Soy m». , , , . , , . , - .
— . , JSON XML — . , , — , JSON . . , , : , ?
( ) , B. C. , . -, — . B, — C. A . .
— A B, C. — , (DAG), . , . , A B, C. , , , .
. . «a», «b», «a» «b». «a» . , ? , . macOS «Invalid argument». , , , , , .
, , . CRDT . .
B A. A B. . , . .
, . — . A B, , , — . , - . , , , . A B, , .
? Google Drive, .
A B, — B A, . Google Drive . , Google . CRDT - . , , . .
:
op1, op3, mv A B op5. t. — 1, 3, 4 5. mv B A 6. , . , , .
— , . , . .
. 1 5. op2, . — 2, , .
op2 , . , , — , , .
, , . .
. , 2, 5. 2, op5, mv A B op3. op2, . , , , .
. - , , . , , , . . , . , , . , 600 . , , , , , . .
, (. ).
MoveOp. Timestamp. ; , , . , , . child — , parent — . Metadata meta — . , , meta . , . .
, LogEntry. . .
. , , a b. .
a b , (a, m, b) ∈ , a b , c, , a c, c b. . , . , , . , . , . , .
. , , , , . , . , . , , CRDT. , — , . , , .
CRDT . CRDT . , .
, . , UTF-8 ; , , . ; . - , . , . , , . , , 100 , . , .
, Automerge, CRDT. , CRDT. .
. , — . ( plain text- LaTeX 100 ) , . 300 000 : , . , ( , ).
, CRDT. JSON, 150 . gzip 6 , 100 . , 700 ( - 200 ), . , 22%. , CRDT , , 228 . . gzip, 100 . , (tombstones), 50 . , . .
, . , . , . , . RGA, . , . , .
. — . , . , — . UTF-8, , . , , .
. . 1, 2, 3, 4, 5, 6. -, . 1, 1, 1, 1, 1, 1. , , 6 1. , . , — , . , , ⅓ . , . 0, 0, 0, 0, 0, 0. - , , , , .
UTF-8. , , . . UTF-8 UTF-8 6 . , , . , , , . . , , , .
. , CRDT . , — . , CRDT: , , . , , CRDT .
Logoot: Stéphane Weiss, Pascal Urso, and Pascal Molli: “ Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks ,” ICDCS 2009.
LSEQ: Brice Nédelec, Pascal Molli, Achour Mostefaoui, and Emmanuel Desmontils: “LSEQ: an Adaptive Structure for Sequences in Distributed Collaborative Editing,” DocEng 2013.
RGA: Hyun-Gul Roh, Myeongjae Jeon, Jin-Soo Kim, and Joonwon Lee: “Replicated abstract data types: Building blocks for collaborative applications,” Journal of Parallel and Distributed Computing, 71(3):354–368, 2011.
Treedoc: Nuno Preguiça, Joan Manuel Marques, Marc Shapiro, and Mihai Letia: “A Commutative Replicated Data Type for Cooperative Editing,” ICDCS 2009.
WOOT: Gérald Oster, Pascal Urso, Pascal Molli, and Abdessamad Imine: “Data consistency for P2P collaborative editing,” CSCW 2006.
Astrong: Hagit Attiya, Sebastian Burckhardt, Alexey Gotsman, Adam Morrison, Hongseok Yang, and Marek Zawirski: “Specification and Complexity of Collaborative Text Editing,” PODC 2016.
, , .
Interleaving anomaly: Martin Kleppmann, Victor B. F. Gomes, Dominic P. Mulligan, and Alastair R. Beresford: “Interleaving anomalies in collaborative text editors”. PaPoC 2019.
Proof of no interleaving in RGA: Martin Kleppmann, Victor B F Gomes, Dominic P Mulligan, and Alastair R Beresford: “OpSets: Sequential Specifications for Replicated Datatypes”, May 2018.
Moving list items: Martin Kleppmann: “Moving Elements in List CRDTs”. PaPoC 2020.
Move operation in CRDT trees: Martin Kleppmann, Dominic P. Mulligan, Victor B. F. Gomes, and Alastair R. Beresford: “A highly-available move operation for replicated trees and distributed filesystems”. Preprint
Reducing metadata overhead: Martin Kleppmann: “Experiment: columnar data encoding for Automerge”, 2019.
Local-first software: Martin Kleppmann, Adam Wiggins, Peter van Hardenberg, and Mark McGranaghan: “Local-first software: You own your data, in spite of the cloud”. Onward! 2019.
Hydra 2020 , , . Hydra 2021, 15 18 . , , — .