无冲突复制数据类型：修订间差异

删除的内容添加的内容

行内

2021年12月23日 (四) 11:22的版本

在分布式计算中，无冲突复制数据类型（英語：CRDT）是一种可以在网络中的多台计算机上复制的数据结构，副本可以独立和并发地更新，而不需要在副本之间进行协调，并且在数学上总是可以解决可能出现的不一致问题。^[1]^[2]^[3]^[4]^[5]^[6]^[7]^[8]

CRDT的概念是由Marc Shapiro、Nuno Preguiça、Carlos Baquero和Marek Zawirski于2011年正式定义。^[9] 开发的最初动机是协作式文本编辑（英语：Collaborative real-time editor）和移动计算。CRDTs也被用于在线聊天系统、在线赌博和SoundCloud音频分发平台中。NoSQL 分布式数据库 Redis、Riak和Cosmos DB有CRDT数据类型。

背景

对同一数据的多个副本同时进行更新，而托管这些副本的计算机之间没有协调，可能会导致副本之间的不一致，在一般情况下，这些不一致可能无法解决。当更新之间存在冲突时，恢复一致性和数据完整性可能需要完全或部分放弃一些或全部的更新。

因此，分布式计算的大部分内容都集中在如何防止复制数据的并发更新问题上。但另一种可能的方法是乐观复制（英语：optimistic replication），即允许所有并发的更新通过，可能会产生不一致的情况，而结果会在以后合并或“解决”。在这种方法中，副本之间的一致性最终会通过不同副本的“合并”来重新建立。虽然乐观复制在一般情况下可能不起作用，但事实证明，有一类重要的、实际有用的数据结构，即CRDT，它确实能够起到作用——在数学上，总是有可能在数据结构的不同副本上合并或解决并发更新而不产生冲突。这使得CRDT成为乐观复制的理想选择。

举个例子，单向的布尔事件标志是一个最简单的CRDT：它有一个比特，其值为真或假。“真”意味着某些特定事件至少发生过一次。“假”的意味着该事件没有发生。一旦设置为真，该标志就不能再设置为假。（一个事件一旦发生，就已不可改变。）解决方法是 "真赢"：当合并一个标志为真（该副本已经观测到该事件）的副本和另一个标志为假（该副本没有观测到该事件）的副本时，解决的结果是真——该事件已经被观测到。

CRDT的种类

CRDT有两种方法，都可以提供强（英语：strong consistency）最终一致性：基于操作的CRDT^[10]^[11]和基于状态的CRDT。^[12]^[13]

这两种方法在理论上是等同的，因为一个可以模仿另一个。^[1] 然而，实际上还是有区别的。基于状态的CRDT通常更容易设计和实现；它们对通信底层的唯一要求是某种流言协议（英语：gossip protocol）。它们的缺点是，每个CRDT的整个状态最终都必须传输给其他每个副本，这可能开销很大。相比之下，基于操作的CRDT只传输更新操作，通常很小。然而，基于操作的CRDT需要通信中间件的保证；在传输给其他副本时，操作不会被丢弃或重复，而且它们是按因果顺序（英语：causal order）传输的。^[1]

基于操作的CRDT

基于操作的CRDT也被称为交换性复制数据类型（commutative replicated data types，或CmRDT）。CmRDT副本只通过传输更新操作来传播状态。例如，单一整数的CmRDT可以广播操作（+10）或（-20）。副本接收更新并在本地应用这些更新。这些操作是可交换的。然而，它们不一定冪等。因此，通信基础设施必须确保一个副本上的所有操作都被传递给其他副本，没有重复，但以任何顺序传输都是可以的。

纯基于操作的CRDT^[11]是基于操作的CRDT的一个变种，它减少了元数据的大小。

基于状态的CRDT

基于状态的CRDT被称为收敛复制数据类型（convergent replicated data types，或CvRDT）。与CmRDT相反，CvRDT将其完整的本地状态发送给其他副本，在这些副本中，状态必须通过可交换的、可结合的并且是幂等的函数合并。合并函数为任何一对副本的状态提供连接，因此所有状态的集合形成一个半格。更新函数必须按照与半格相同的偏序规则，单调地增加内部状态。函数必须内部状态，根据与半网格相同的偏序规则。

Delta状态CRDT^[13]^[14]（或简称Delta CRDT）是基于状态的优化CRDT，其中只有最近应用到一个状态的更改才会被传播，而不是传播到整个状态。

对比

虽然CmRDT对副本间传输操作的协议提出了更多的要求，但当事务数量与内部状态的大小相比较小时，它们使用的带宽比CvRDT要少。不过，由于CvRDT的合并函数是可结合的，与某个副本的状态合并会产生该副本之前的所有更新。流言协议（英语：Gossip protocol）在向其他副本传播CvRDT状态时效果很好，同时减少了网络使用并处理了拓扑变化。

基于状态的CRDT的存储复杂性的一些下界^[15]是已知的。

行业运用

Nimbus Note是一个协作记事的应用程序，使用Yjs CRDT进行协作编辑。^[16]

Redis是一个分布式、高可用和可扩展的内存数据库，它使用CRDT来实现基于开源Redis的全球分布式数据库，并与之完全兼容。

SoundCloud开源了Roshi （页面存档备份，存于互联网档案馆），这是一个在Redis之上实现的用于SoundCloud流的LWW-元素集CRDT。^[17]

Riak是一个基于CRDT的分布式NoSQL键值数据存储。^[18] 英雄联盟将Riak CRDT实现用于其游戏内的聊天系统，该系统可处理750万并发用户和每秒11000条信息。^[19] Bet365，在OR-Set的Riak实现中存储了数百MB的数据。^[20]

TomTom采用CRDT在用户的设备之间同步导航数据。^[21]

Phoenix，一个用Elixir编写的网络框架，在1.2版本中使用CRDT来支持实时的多节点信息共享。^[22]

Facebook在他们的Apollo低延迟“规模一致性”数据库中实现了CRDT。^[23]

Teletype for Atom采用了CRDT，使开发人员能够与团队成员分享他们的工作空间，并实时进行代码协作。^[24]

Haja Networks的OrbitDB在其核心数据结构IPFS-Log中使用基于操作的CRDT。^[25]

苹果在Notes应用中实现了CRDT，用于在多个设备之间同步离线编辑。^[26]

参考文献

^ ^1.0 ^1.1 ^1.2 Shapiro, Marc; Preguiça, Nuno; Baquero, Carlos; Zawirski, Marek. Conflict-Free Replicated Data Types. Stabilization, Safety, and Security of Distributed Systems (PDF). Lecture Notes in Computer Science 6976. Grenoble, France: Springer Berlin Heidelberg. 2011: 386–400 [2021-12-17]. ISBN 978-3-642-24549-7. doi:10.1007/978-3-642-24550-3_29. （原始内容存档 (PDF)于2021-12-18）. |issue=被忽略 (帮助)
^ Shapiro, Marc; Preguiça, Nuno; Baquero, Carlos; Zawirski, Marek. A Comprehensive Study of Convergent and Commutative Replicated Data Types. Rr-7506. 13 January 2011.
^ Shapiro, Marc; Preguiça, Nuno. Designing a Commutative Replicated Data Type. Computing Research Repository (CoRR). 2007,. abs/0710.1784. Bibcode:2007arXiv0710.1784S. arXiv:0710.1784 .
^ Oster, Gérald; Urso, Pascal; Molli, Pascal; Imine, Abdessamad. Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work - CSCW '06. 2006: 259. CiteSeerX 10.1.1.554.3168 . ISBN 978-1595932495. S2CID 14596943. doi:10.1145/1180875.1180916.
^ Letia, Mihai; Preguiça, Nuno; Shapiro, Marc. CRDTs: Consistency without Concurrency Control. Computing Research Repository (CoRR). 2009,. abs/0907.0929. Bibcode:2009arXiv0907.0929L. arXiv:0907.0929 .
^ Preguiça, Nuno; Marques, Joan Manuel; Shapiro, Marc; Letia, Mihai, A Commutative Replicated Data Type for Cooperative Editing (PDF), Proc 29th IEEE International Conference on Distributed Computing Systems, Montreal, Quebec, Canada: IEEE Computer Society: 395–403, June 2009 [2021-12-17], ISBN 978-0-7695-3659-0, S2CID 8956372, doi:10.1109/ICDCS.2009.20, （原始内容存档 (PDF)于2021-12-17）
^ Baquero, Carlos; Moura, Francisco, Specification of Convergent Abstract Data Types for Autonomous Mobile Computing, Universidade do Minho, 1997
^ Schneider, Fred. Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. ACM Computing Surveys. December 1990, 22 (4): 299–319. S2CID 678818. doi:10.1145/98163.98167.
^ Conflict-free Replicated Data Types (PDF). inria.fr. July 19, 2011 [2021-12-17]. （原始内容存档 (PDF)于2021-10-27）.
^ Letia, Mihai; Preguiça, Nuno; Shapiro, Marc. Consistency without Concurrency Control in Large, Dynamic Systems (PDF). SIGOPS Oper. Syst. Rev. 1 April 2010, 44 (2): 29–34 [2021-12-17]. S2CID 6255174. doi:10.1145/1773912.1773921. （原始内容存档 (PDF)于2021-11-27）.
^ ^11.0 ^11.1 Baquero, Carlos; Almeida, Paulo Sérgio; Shoker, Ali. Magoutis, Kostas; Pietzuch, Peter , 编. Making Operation-Based CRDTs Operation-Based. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 2014-06-03: 126–140. CiteSeerX 10.1.1.492.8742 . ISBN 9783662433515. doi:10.1007/978-3-662-43352-2_11 （英语）.
^ Baquero, Carlos; Moura, Francisco. Using Structural Characteristics for Autonomous Operation. SIGOPS Oper. Syst. Rev. 1 October 1999, 33 (4): 90–96. S2CID 13882850. doi:10.1145/334598.334614. hdl:1822/34984 .
^ ^13.0 ^13.1 Almeida, Paulo Sérgio; Shoker, Ali; Baquero, Carlos. Bouajjani, Ahmed; Fauconnier, Hugues , 编. Efficient State-Based CRDTs by Delta-Mutation. Lecture Notes in Computer Science. Springer International Publishing. 2015-05-13: 62–76. ISBN 9783319268491. S2CID 7852769. arXiv:1410.2803 . doi:10.1007/978-3-319-26850-7_5 （英语）.
^ Almeida, Paulo Sérgio; Shoker, Ali; Baquero, Carlos. Delta State Replicated Data Types. Journal of Parallel and Distributed Computing. 2016-03-04, 111: 162–173. Bibcode:2016arXiv160301529S. S2CID 7990602. arXiv:1603.01529 . doi:10.1016/j.jpdc.2017.08.003.
^ Burckhardt, Sebastian; Gotsman, Alexey; Yang, Hongseok; Zawirski, Marek. Replicated Data Types: Specification, Verification, Optimality. Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (PDF). 23 January 2014: 271–284 [2021-12-17]. ISBN 9781450325448. S2CID 15023909. doi:10.1145/2535838.2535848. （原始内容存档 (PDF)于2021-12-17）.
^ About CRDTs. [2020-06-18]. （原始内容存档于2021-12-17）.
^ Bourgon, Peter. Roshi: a CRDT system for timestamped events. SoundCloud. 9 May 2014 [2021-12-17]. （原始内容存档于2021-11-21）.
^ Introducing Riak 2.0: Data Types, Strong Consistency, Full-Text Search, and Much More. Basho Technologies, Inc. 29 October 2013 [2021-12-17]. （原始内容存档于2014-11-29）.
^ Hoff, Todd. How League of Legends Scaled Chat to 70 Million Players - It Takes Lots of Minions. High Scalability. 13 October 2014 [2021-12-17]. （原始内容存档于2021-12-17）.
^ Macklin, Dan. bet365: Why bet365 chose Riak. Basho. [2021-12-17]. （原始内容存档于2015-11-19）.
^ Ivanov, Dmitry. Practical Demystification of CRDTs. [2021-12-17]. （原始内容存档于2021-12-17）.
^ McCord, Chris. What makes Phoenix Presence Special. [2021-12-17]. （原始内容存档于2021-12-17）.
^ Mak, Sander. Facebook Announces Apollo at QCon NY 2014. [2021-12-17]. （原始内容存档于2021-12-17）.
^ Code together in real time with Teletype for Atom. Atom.io. November 15, 2017 [2021-12-17]. （原始内容存档于2021-05-14）.
^ OrbitDB/ipfs-log on Github. [2018-09-07]. （原始内容存档于2021-12-17）.
^ IOS Objective-C headers as derived from runtime introspection: NST/IOS-Runtime-Headers. 2019-07-25 [2021-12-17]. （原始内容存档于2021-12-18）.

外部链接

A collection of resources and papers on CRDTs （页面存档备份，存于互联网档案馆）
"Strong Eventual Consistency and Conflict-free Replicated Data Types" (A talk on CRDTs) by Marc Shapiro
Readings in conflict-free replicated data types （页面存档备份，存于互联网档案馆） by Christopher Meiklejohn
CAP theorem and CRDTs: CAP 12 years later. How the rules have changed （页面存档备份，存于互联网档案馆） by Eric Brewer

[2011CRDT-1] 1.0 ^1.1 ^1.2 Shapiro, Marc; Preguiça, Nuno; Baquero, Carlos; Zawirski, Marek. Conflict-Free Replicated Data Types. Stabilization, Safety, and Security of Distributed Systems (PDF). Lecture Notes in Computer Science 6976. Grenoble, France: Springer Berlin Heidelberg. 2011: 386–400 [2021-12-17]. ISBN 978-3-642-24549-7. doi:10.1007/978-3-642-24550-3_29. （原始内容存档 (PDF)于2021-12-18）. |issue=被忽略 (帮助)

[2011CRDTSurvey-2] Shapiro, Marc; Preguiça, Nuno; Baquero, Carlos; Zawirski, Marek. A Comprehensive Study of Convergent and Commutative Replicated Data Types. Rr-7506. 13 January 2011.

[2007CRDTOriginal-3] Shapiro, Marc; Preguiça, Nuno. Designing a Commutative Replicated Data Type. Computing Research Repository (CoRR). 2007,. abs/0710.1784. Bibcode:2007arXiv0710.1784S. arXiv:0710.1784 .

[OsterUrso2006-4] Oster, Gérald; Urso, Pascal; Molli, Pascal; Imine, Abdessamad. Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work - CSCW '06. 2006: 259. CiteSeerX 10.1.1.554.3168 . ISBN 978-1595932495. S2CID 14596943. doi:10.1145/1180875.1180916.

[2009CRDT-5] Letia, Mihai; Preguiça, Nuno; Shapiro, Marc. CRDTs: Consistency without Concurrency Control. Computing Research Repository (CoRR). 2009,. abs/0907.0929. Bibcode:2009arXiv0907.0929L. arXiv:0907.0929 .

[2009CRDTTreedoc-6] Preguiça, Nuno; Marques, Joan Manuel; Shapiro, Marc; Letia, Mihai, A Commutative Replicated Data Type for Cooperative Editing (PDF), Proc 29th IEEE International Conference on Distributed Computing Systems, Montreal, Quebec, Canada: IEEE Computer Society: 395–403, June 2009 [2021-12-17], ISBN 978-0-7695-3659-0, S2CID 8956372, doi:10.1109/ICDCS.2009.20, （原始内容存档 (PDF)于2021-12-17）

[1997scadt-7] Baquero, Carlos; Moura, Francisco, Specification of Convergent Abstract Data Types for Autonomous Mobile Computing, Universidade do Minho, 1997

[Schneider-8] Schneider, Fred. Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. ACM Computing Surveys. December 1990, 22 (4): 299–319. S2CID 678818. doi:10.1145/98163.98167.

[CRDT_paper-9] Conflict-free Replicated Data Types (PDF). inria.fr. July 19, 2011 [2021-12-17]. （原始内容存档 (PDF)于2021-10-27）.

[2010OpBased-10] Letia, Mihai; Preguiça, Nuno; Shapiro, Marc. Consistency without Concurrency Control in Large, Dynamic Systems (PDF). SIGOPS Oper. Syst. Rev. 1 April 2010, 44 (2): 29–34 [2021-12-17]. S2CID 6255174. doi:10.1145/1773912.1773921. （原始内容存档 (PDF)于2021-11-27）.

[:0-11] 11.0 ^11.1 Baquero, Carlos; Almeida, Paulo Sérgio; Shoker, Ali. Magoutis, Kostas; Pietzuch, Peter , 编. Making Operation-Based CRDTs Operation-Based. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 2014-06-03: 126–140. CiteSeerX 10.1.1.492.8742 . ISBN 9783662433515. doi:10.1007/978-3-662-43352-2_11 （英语）.

[1999StateBased-12] Baquero, Carlos; Moura, Francisco. Using Structural Characteristics for Autonomous Operation. SIGOPS Oper. Syst. Rev. 1 October 1999, 33 (4): 90–96. S2CID 13882850. doi:10.1145/334598.334614. hdl:1822/34984 .

[:1-13] 13.0 ^13.1 Almeida, Paulo Sérgio; Shoker, Ali; Baquero, Carlos. Bouajjani, Ahmed; Fauconnier, Hugues , 编. Efficient State-Based CRDTs by Delta-Mutation. Lecture Notes in Computer Science. Springer International Publishing. 2015-05-13: 62–76. ISBN 9783319268491. S2CID 7852769. arXiv:1410.2803 . doi:10.1007/978-3-319-26850-7_5 （英语）.

[Almeida-14] Almeida, Paulo Sérgio; Shoker, Ali; Baquero, Carlos. Delta State Replicated Data Types. Journal of Parallel and Distributed Computing. 2016-03-04, 111: 162–173. Bibcode:2016arXiv160301529S. S2CID 7990602. arXiv:1603.01529 . doi:10.1016/j.jpdc.2017.08.003.

[Burckhardt-15] Burckhardt, Sebastian; Gotsman, Alexey; Yang, Hongseok; Zawirski, Marek. Replicated Data Types: Specification, Verification, Optimality. Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (PDF). 23 January 2014: 271–284 [2021-12-17]. ISBN 9781450325448. S2CID 15023909. doi:10.1145/2535838.2535848. （原始内容存档 (PDF)于2021-12-17）.

[16] About CRDTs. [2020-06-18]. （原始内容存档于2021-12-17）.

[Roshi-17] Bourgon, Peter. Roshi: a CRDT system for timestamped events. SoundCloud. 9 May 2014 [2021-12-17]. （原始内容存档于2021-11-21）.

[Riak-18] Introducing Riak 2.0: Data Types, Strong Consistency, Full-Text Search, and Much More. Basho Technologies, Inc. 29 October 2013 [2021-12-17]. （原始内容存档于2014-11-29）.

[LoL-19] Hoff, Todd. How League of Legends Scaled Chat to 70 Million Players - It Takes Lots of Minions. High Scalability. 13 October 2014 [2021-12-17]. （原始内容存档于2021-12-17）.

[bet365-20] Macklin, Dan. bet365: Why bet365 chose Riak. Basho. [2021-12-17]. （原始内容存档于2015-11-19）.

[TomTom-21] Ivanov, Dmitry. Practical Demystification of CRDTs. [2021-12-17]. （原始内容存档于2021-12-17）.

[Phoenix-22] McCord, Chris. What makes Phoenix Presence Special. [2021-12-17]. （原始内容存档于2021-12-17）.

[Apollo-23] Mak, Sander. Facebook Announces Apollo at QCon NY 2014. [2021-12-17]. （原始内容存档于2021-12-17）.

[atom_teletype-24] Code together in real time with Teletype for Atom. Atom.io. November 15, 2017 [2021-12-17]. （原始内容存档于2021-05-14）.

[25] OrbitDB/ipfs-log on Github. [2018-09-07]. （原始内容存档于2021-12-17）.

[26] IOS Objective-C headers as derived from runtime introspection: NST/IOS-Runtime-Headers. 2019-07-25 [2021-12-17]. （原始内容存档于2021-12-18）.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]