Todos estamos tan acostumbrados a la sincronización en la nube de Dropbox y a la coautoría en Google Docs que combinar los resultados de las acciones de diferentes usuarios puede parecer un problema de larga data. Pero, de hecho, existen muchas trampas en este asunto, y el trabajo en los algoritmos CRDT todavía está en pleno apogeo.
, — (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 . .
. , , , , , .
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 y Pascal Molli: “ Logoot: un algoritmo de replicación optimista escalable para la edición colaborativa en redes 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 . , , — .