CRDTS:难的部分

2020-07-11 22:49:01

在九头蛇的在线演讲(原计划在俄罗斯莫斯科举行),2020年7月6日。

无冲突复制数据类型(CRDT)是一个日益流行的乐观复制算法家族。它们允许同时更新多个副本上的数据,即使这些副本处于离线状态,并提供了一种将这些更新合并回一致状态的可靠方式。CRDT用于地理复制数据库、多用户协作软件、分布式处理框架和各种其他系统。

然而,尽管CRDT的基本原理现在已相当为人所知,但许多具有挑战性的问题仍潜藏在表面之下。事实证明,CRDT很容易实现得很差。许多已公布的算法都存在异常,导致它们在某些情况下行为异常。SimpleImplementation的性能通常很差,要使性能良好很有挑战性。

在这次演讲中,马丁超越了关于CRDT的介绍性材料,并讨论了从多年来使CRDT在实践中发挥作用的研究中获得的一些来之不易的经验教训。

Logoot:Stéphane Weiss、Pascal Urso和Pascal Molli:“Logoot:一种用于P2P网络协作编辑的可伸缩乐观复制算法”,ICDCS 2009。

LSEQ:Brice Nédelec、Pascal Molli、Achour Mostefaoui和Emmanuel Desmontils:“LSEQ:分布式协作编辑中序列的自适应结构”,DocEng 2013。

RGA:Hyun-Gul Roh,Myeongjae Jeon,Kim-soo Kim,and Joonwon Lee:“复制的抽象数据类型:协作应用的构建块”,并行与分布式计算期刊,71(3):354-368,2011。

Treedoc:Nuno Preguiça、Joan Manuel Marque、Marc Shapiro和Mihai Letia:“一种用于合作编辑的可交换复制数据类型”,ICDCS 2009。

WOOT:Gérald Oster、Pascal Urso、Pascal Molli和Abdessamad Imine:“P2P协作编辑的数据一致性”,CSCW 2006。

强者:Hagit Attiya、Sebastian Burckhardt、Alexey Gotsman、Adam Morrison、Hong seok Yang和Marek Zawirski:“协作文本编辑的规范和复杂性”,PODC 2016。

交叉异常:马丁·克莱普曼、维克多·B·F·戈麦斯、多米尼克·P·穆利根和阿拉斯泰尔·R·贝雷斯福德:“协作文本编辑器中的交叉异常”。PaPoC 2019。

RGA中不存在交错的证据:Martin Kleppmann、Victor B F Gomes、Dominic P Mullican和Alastair R Beresford:“OpSet:Sequence Specification for Replated Data Types”,2018年5月。

移动列表项:Martin Kleppmann:“移动列表CRDT中的元素”。PaPoC 2020。

在CRDT树中的移动操作:Martin Kleppmann,Dominic P.Mulligan,Victor B.F.Gomes,和Alastair R.Beresford:“复制的树和分布式文件系统的高度可用的移动操作”。预印本,2020。

降低元数据开销:Martin Kleppmann:“实验:Automerge的柱状数据编码”,2019年。另外:“预览:Automerge二进制数据格式(Automerge PR#253)”,2020。

本地优先软件:马丁·克莱普曼(Martin Kleppmann)、亚当·威金斯(Adam Wiggins)、彼得·范·哈登伯格(Peter Van Hardenberg)和马克·麦格拉纳汉(Mark McGranaghan):“本地优先软件:不管云是什么,你都拥有自己的数据。”前进!2019年。