維基百科

無衝突複製數據類型

在分布式計算中，無衝突複製數據類型（英語：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. ^ 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=被忽略 (幫助)
  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. 
  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  . 
  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. 
  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  . 
  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） 
  7. ^ Baquero, Carlos; Moura, Francisco, Specification of Convergent Abstract Data Types for Autonomous Mobile Computing, Universidade do Minho, 1997 
  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. 
  9. ^ Conflict-free Replicated Data Types (PDF). inria.fr. July 19, 2011 [2021-12-17]. （原始內容存檔 (PDF)於2021-10-27）. 
  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）. 
  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 （英語）. 
  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  . 
  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 （英語）. 
  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. 
  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）. 
  17. ^ Bourgon, Peter. Roshi: a CRDT system for timestamped events. SoundCloud. 9 May 2014 [2021-12-17]. （原始內容存檔於2021-11-21）. 
  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）. 
  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）. 
  20. ^ Macklin, Dan. bet365: Why bet365 chose Riak. Basho. [2021-12-17]. （原始內容存檔於2015-11-19）. 
  21. ^ Ivanov, Dmitry. Practical Demystification of CRDTs. [2021-12-17]. （原始內容存檔於2021-12-17）. 
  22. ^ McCord, Chris. What makes Phoenix Presence Special. [2021-12-17]. （原始內容存檔於2021-12-17）. 
  23. ^ Mak, Sander. Facebook Announces Apollo at QCon NY 2014. [2021-12-17]. （原始內容存檔於2021-12-17）. 
  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）. 

外部連結

取自「https://zh.wikipedia.org/w/index.php?title=无冲突复制数据类型&oldid=70223541」