text: 在分散式計算中，無衝突複製資料型別是一種可以在網路中的多臺計算機上覆制的資料結構，副本可以獨立和併發地更新，而不需要在副本之間進行協調，並且在數學上總是可以解決可能出現的不一致問題。CRDT的概念是由Marc Shapiro、Nuno Preguiça、Carlos Baquero和Marek Zawirski於2011年正式定義。 開發的最初動機是和移動計算。CRDTs也被用於線上聊天系統、線上賭博和SoundCloud音訊分發平臺中。NoSQL分散式資料庫Redis、Riak和Cosmos DB有CRDT資料型別。背景.對同一資料的多個副本同時進行更新，而託管這些副本的計算機之間沒有協調，可能會導致副本之間的不一致，在一般情況下，這些不一致可能無法解決。當更新之間存在衝突時，恢復一致性和資料完整性可能需要完全或部分放棄一些或全部的更新。因此，分散式計算的大部分內容都集中在如何防止複製資料的併發更新問題上。但另一種可能的方法是，即允許所有併發的更新透過，可能會產生不一致的情況，而結果會在以後合併或“解決”。在這種方法中，副本之間的一致性最終會透過不同副本的“合併”來重新建立。雖然樂觀複製在一般情況下可能不起作用，但事實證明，有一類重要的、實際有用的資料結構，即CRDT，它確實能夠起到作用——在數學上，總是有可能在資料結構的不同副本上合併或解決併發更新而不產生衝突。這使得CRDT成為樂觀複製的理想選擇。舉個例子，單向的布林事件標誌是一個最簡單的CRDT：它有一個位元，其值為真或假。“真”意味著某些特定事件至少發生過一次。“假”的意味著該事件沒有發生。一旦設定為真，該標誌就不能再設定為假。的副本時，解決的結果是真——該事件已經被觀測到。CRDT的種類.CRDT有兩種方法，都可以提供最終一致性：基於操作的CRDT和基於狀態的CRDT。這兩種方法在理論上是等同的，因為一個可以模仿另一個。 然而，實際上還是有區別的。基於狀態的CRDT通常更容易設計和實現；它們對通訊底層的唯一要求是某種。它們的缺點是，每個CRDT的整個狀態最終都必須傳輸給其他每個副本，這可能開銷很大。相比之下，基於操作的CRDT只傳輸更新操作，通常很小。然而，基於操作的CRDT需要通訊中介軟體的保證；在傳輸給其他副本時，操作不會被丟棄或重複，而且它們是按傳輸的。基於操作的CRDT.基於操作的CRDT也被稱為交換性複製資料型別。副本接收更新並在本地應用這些更新。這些操作是可交換的。然而，它們不一定冪等。因此，通訊基礎設施必須確保一個副本上的所有操作都被傳遞給其他副本，沒有重複，但以任何順序傳輸都是可以的。"純"基於操作的CRDT是基於操作的CRDT的一個變種，它減少了元資料的大小。基於狀態的CRDT.基於狀態的CRDT被稱為收斂複製資料型別。與CmRDT相反，CvRDT將其完整的本地狀態傳送給其他副本，在這些副本中，狀態必須透過可交換的、可結合的並且是冪等的函式合併。合併函式為任何一對副本的狀態提供連線，因此所有狀態的集合形成一個半格。更新函式必須按照與半格相同的規則，單調地增加內部狀態。函式必須內部狀態，根據與半網格相同的偏序規則。"Delta狀態"CRDT是基於狀態的最佳化CRDT，其中只有最近應用到一個狀態的更改才會被傳播，而不是傳播到整個狀態。對比.雖然CmRDT對副本間傳輸操作的協議提出了更多的要求，但當事務數量與內部狀態的大小相比較小時，它們使用的頻寬比CvRDT要少。不過，由於CvRDT的合併函式是可結合的，與某個副本的狀態合併會產生該副本之前的所有更新。在向其他副本傳播CvRDT狀態時效果很好，同時減少了網路使用並處理了拓撲變化。基於狀態的CRDT的儲存複雜性的一些下界是已知的。行業運用.Nimbus Note是一個協作記事的應用程式，使用Yjs CRDT進行協作編輯。Redis是一個分散式、高可用和可擴充套件的記憶體資料庫，它使用CRDT來實現基於開源Redis的全球分散式資料庫，並與之完全相容。SoundCloud開源了Roshi ，這是一個在Redis之上實現的用於SoundCloud流的LWW-元素集CRDT。Riak是一個基於CRDT的分散式NoSQL鍵值資料儲存。 英雄聯盟將Riak CRDT實現用於其遊戲內的聊天系統，該系統可處理750萬併發使用者和每秒11000條資訊。 Bet365，在OR-Set的Riak實現中儲存了數百MB的資料。TomTom採用CRDT在使用者的裝置之間同步導航資料。Phoenix，一個用Elixir編寫的網路框架，在1.2版本中使用CRDT來支援實時的多節點資訊共享。Facebook在他們的Apollo低延遲“規模一致性”資料庫中實現了CRDT。Teletype for Atom採用了CRDT，使開發人員能夠與團隊成員分享他們的工作空間，並實時進行程式碼協作。Haja Networks的OrbitDB在其核心資料結構IPFS-Log中使用基於操作的CRDT。蘋果在Notes應用中實現了CRDT，用於在多個裝置之間同步離線編輯。
metadata.dataset: erhwenkuo/wikipedia-zhtw
metadata.title: 無衝突複製資料型別
metadata.url: https://zh.wikipedia.org/wiki?curid=7783563