Clever Geek Handbook

Complexités non évidentes du CRDT







Nous sommes tous tellement habitués à la synchronisation et à la co-création dans le cloud Dropbox dans Google Docs que la combinaison des résultats des actions de différents utilisateurs peut sembler un problÚme de longue date. Mais en fait, il y a de nombreux écueils à ce sujet, et les travaux sur les algorithmes CRDT sont toujours en plein essor.







, — (Martin Kleppmann): Automerge. Hydra , . Google Drive «unknown error»? CRDT , , ? ?







, . — , .













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 . .









(PaPoC 2020). .













. , , , , , .







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 et Pascal Molli: « Logoot: un algorithme de réplication optimiste évolutif pour l'édition collaborative sur les réseaux P2P », 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 . , , — .


More articles:


All Articles