維基百科

無衝突複製資料類型

在分散式計算中，無衝突複製資料類型（英語：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"