Gravity團隊
在本系列的第一部分中，我們考察了order理論的基礎知識，以便探究 join semi-lattice 的概念，這是Convergent CRDT（或CvRDT）的基礎。如果您還沒有閱讀過上篇文章，我強烈建議在繼續本文之前閱讀上一篇，因為我們將在此基礎上繼續。在這篇文章中，我們將詳細介紹CvRDTs，在實現一個簡單的增長分佈計數器示例之前，首先介紹它們的工作原理。
Convergent CRDTs
Convergent CRDT（或CvRDT）是複製的數據結構，合併後會趨於一個值。我們需要牢記 CvRDT 的兩個基本組成部分。首先，我們有state.我們將所有可能的狀態視為一個集合的元素。對於 CvRDT，該集合必須按某種二元關係排序。例如，想象一下，我們的狀態是一個計數器。簡單來看，可以將我們計數器的所有可能狀態視為所有整數，並且我們的順序小於或等於這些整數。
CvRDT 的另一個關鍵組成是 merge() 函數。CvRDTs 的全部重點是複製節點之間的狀態。我們需要一個合併函數來最終保持該狀態同步。 對於 CvRDT，合併函數充當我們秩序的 join 。
如果我們看一些例子就會更清楚。回想一下，對於全部 order，任何兩個元素的 join 將成為這兩個元素中的一個。對於小於或等於整數，join 總是兩個整數中較大的一個。這意味著相應的合併函數將是 max() 。這裡有一些例子：
merge(1,3)=3
merge(9,5)=9
merge(8,8)=8
在每個示例中，兩個整數之間的最大值是這些整數的最小上限值。
現在想象一下，我們的狀態集不是整數，而是矢量時鐘時間戳。在這種情況下，我們可以使用座標最大值作為我們的合併函數。這裡有一些例子：
merge((1,0,0),(0,1,1))=(1,1,1)
merge((0,0,0),(2,0,2))=(2,0,2)
merge((5,3,1),(1,9,2))=(5,9,2)
最後，思考一下我們的狀態集合是 location 並且我們的 order 是located-in。在這種情況下，我們可以用“least-common-enclosing-location”作為我們的合併函數。通過least-common-enclosing-location，我只是指包含合併的兩個位置的最小位置。這裡有一些例子：
merge(Seattle,Mumbai)=Earth
merge(Bronx,NYC)=NYC
merge(Mumbai,Delhi)=India
如果這一點不清楚，也不要擔心。我們將繼續以下這些相同的例子。但要記住的重要一點是，在定義 CvRDT 時，我們必須確定一組 state，一個關係 ≤ 表示該集合的順序，以及一個合併函數，該函數就像該順序的 join 一樣。
Systems
在得到 CvRDTs 之前，引入一些概念將有助於我們更好地理解它們。首先，我們稱一組可用的states 為 System 。下面的例子，是我們到目前為止討論過的 state：
[2,5,7]
[Seattle,Delhi,Mumbai]
[(0,0,1),(1,0,0),(1,1,0)]
區分當前狀態集（我稱之為Systems）和 background sets 很重要。在上面的第一個例子中，我們的系統由三個整數組成，2 , 5 和 7 。我們的 background sets是所有整數的集合。為了清楚這一點，我將從現在開始討論 Systems 和 background sets。
以下是一個有趣的事實：對於具有合併操作的任何 states 系統，為系統中的所有對定義充當 join，我們可以繪製 join semi-lettice。讓我們依次看看我們的三個示例系統。對於三個整數的系統，我們可以畫出下圖：
回想一下，對於圖中的任何兩個元素成為 join semi-lattice，我們都可以找到它們兩個的最小值。在這種情況下，任何兩個元素可以通過小於或等於直接相關，並且 join 只是兩者中的最大值。對於一個更有趣的例子，我們需要看看分序，就像 located-in 一樣。所以我們來看看三個位置的系統。如果您單獨繪製了這三個位置的圖表，它將如下所示：
這些元素在定位方面都不能直接相互比較。所以如果這個系統也是整個 background sets，那麼我們就不能畫出一個 semi-lattice 。幸運的是，我們在這裡設置的background sets是一組更大的locations（如第一部分所定義）。所以我們可以通過逐步地取元素對的 join 來把這個圖轉換成semi-lattice 。我們稍後會強調，我們接受這些連接的順序並不重要。因此，我們開始在圖表中添加孟買和德里的連接：
注意，我們正在從 background sets 中獲取一個原本不屬於我們系統的部分，並將其添加到我們的圖中。如印度，我標記了它不同的顏色，以表明它實際上不是我們系統的一部分。
現在我們繼續選擇另一對，西雅圖和孟買。Join 是地球：
最後，讓我們 join 西雅圖和印度。好吧，這又是地球，這意味著我們不再在圖上增加任何locations，但我們可以添加從印度到地球的新箭頭：
現在，如果仔細觀察我們的圖表，就會發現無論選擇哪兩個元素，都可以在圖表中找到 join。這是因為地球是圖中所有其他東西的最大值，所以我們至少可以達到上限。
只要我們的 background sets 和我們的≤關係形成 join semi-lattice，那麼對於任何系統，我們總是可以通過從 background sets 選取元素通過 join 來繪製相應的 semi-lattice 。這引出我們接下來一個重要概念。我們將系統的 Value 定義為相應 semi-lattice 的最大值。以下是一些考慮系統 Value 的例子：
Value([2,5,7])=7
Value([Seattle,Delhi,Mumbai])=Earth
Value([(0,0,1),(1,0,0),(1,1,0)])=(1,1,1)
關鍵在於系統中的 states 在合併它們時彙集成系統的 value 。設想從系統中隨機選擇一對狀態併合並它們，每次將合併結果添加到系統中。這個過程最終應該將 Value 加到系統中。現在，每個合併都起到 join 作用。join 的屬性確保了兩件重要的事情：
1.合併順序無關緊要。這由 join 的結合性和交換性來保證。
2.不管重複多少次特定的合併都不重要。這由 join 的冪等性保證。
Implementing a CvRDT
我們現在有實現首個 CvRDT 所需的一切條件。將系統與節點網絡相對應，每個節點都包含其自己的全局 state 版本。如，這是一個與上面的整數系統相對應的網絡：
如果我們的節點隨機地傳遞 states，合併任何進入的 states，它們都會趨向於系統的 value。在這種情況下，我們系統的 value 是 5.這是因為 5 是系統中三種狀態的最大值。當我們從節點到節點之間傳遞整數時，我們通過將狀態更新為本地整數和傳入整數的最大值來執行合併。下面的動畫應該有助於明確這一點：
CvRDT 的偉大之處在於允許我們抽象出這些網絡/系統細節。我們可以來實施一個計數器來說明這個想法。
我們的計數器有一個簡單的界面：
increment()：增加計數器
value()：獲取計數器的值
我們希望將這個計數器複製到三個節點上。其思想是，用戶能夠與這三個節點中的任何一個進行交互，但只要它們仍然連接到同一個節點，就會看到一致的結果。此外，我們需要這些節點隨著時間的推移保持同步（最終）。
抽象地說，當用戶在任何三個節點上調用 increment()，它都應該增加我們系統的 value 。這是因為我們的複製計數器跟蹤所有用戶的所有 increment() 調用。這說明我們可以繪製系統如下圖，對系統作為一個整體進行抽象地調用（即使實際上它們總是對特定節點進行調用）：
我們的系統的起始值是 0.現在想象一下，increment()在節點 X 上調用一次，在節點 Y 上調用兩次，在節點 Z 上調用三次。該值應該等於 6。但是請記住關於系統 value 的重要一點：該值不一定存在於任何一個節點上。相反，它是我們 join semi-lattice 的最大值。也就是說，這是我們合併收斂的價值。
其主旨是，value 將最終反映在所有節點。除了傳遞狀態之外，不需要任何協調。合併順序無關緊要。而且我們重複特定合併的次數也不重要。這意味著我們就可以在方便的時候傳遞狀態。沒有必要追溯到過去發生的合併或發生的順序。
試著執行我們的計數器。我們將從所謂的 G-counter 開始，也就是增長計數器。我們的界面只是 increment() 和 value() 。 回想一下，我們需要兩件事情：
1. states 類型 S 按某種≤關係排序。
2. merge() 操作，作為我們的 order
每個節點將有一個 value，我們將稱之為 local state，表示該節點對系統當前 value 的記錄。我們需要能夠通過該節點上的 increment()調用來更新 local state 。而且我們還需要能夠通過該節點上的 value() 調用讀取 local state。首先，我們將簡單地將本地狀態表示為一個整數。
現在我們需要考慮 merge()。請記住，節點可以隨時從另一個節點接收 states 。它從哪個節點接收並不重要，它是否已經被接收到相同的狀態，也不重要。無論如何，我們的 local state 應該總是趨於系統的 value，在本例中，這個值就是系統中任何地方調用的 increment() 的總次數。
merge() 的一個簡單實現是將傳入狀態的值添加到我們的本地值中。 但這種做法肯定會失敗。問題是添加不是冪等的。如果我們合併5次，我們會繼續在當地總計中加5。這意味著我們很快就會超越系統的價值。merge() 的這種實現不作為 join 。
在我們上一篇文章中，我們看到整數上的 max() 充當 join 。因此，另一種簡單的做法是考慮到達的state和我們 local state。但想象下面的歷史：
1.節點1增加3次。
2.節點2增加2次。
3.節點3增加1次。
在所有這些調用之後，系統的價值是什麼？由於該值是我們網絡中任何地方被調用的增量總次數，因此這裡的答案看起來應該是 6.下面的動畫展示瞭如果我們在整數上使用 max() 作為我們的合併函數會發生什麼：
從我們的系統中的三個整數開始：3, 2 和 1.不管我們在任意隨機選擇的對之間調用 max() 多少次，我們都不會得到高於3的值。但是，我們應該彙集的值是 6。我們需要再試一次。
事實證明，我們需要區分作為 semi-lattice 的系統 value 和與該值對應的人類可讀值。通過尋找一個更好的方法來表示我們的計數器狀態，而不是簡單地使用整數，這是一種借鑑矢量時鐘的方法，這種區別將更加清晰。
我們不使用整數作為 local state，而是使用整數向量。向量中的每個元素都對應一個節點。因此，在我們的最後一個例子中，我們將從以下分佈的 local state 開始：
X: (3, 0, 0)
Y: (0, 2, 0)
Z: (0, 0, 1)
這一次，為了合併傳入的值，我們採用了座標最大值。我們將 value()作為向量中所有元素的總和。以下動畫演示了在這種情況下會發生什麼情況：
每個節點逐漸獲取其他節點的最新值。在這裡，取一個座標的最大值實際上是取這個座標的最新值。我們的系統的價值是
（3,2,1），並且在一個節點上調用value() 的人類可讀結果可以達到 6。現在我們已經有了一個工作實現，讓我們來定義我們的接口操作：
increment()：遞增該節點對應的向量索引處的整數。
value() ：向量中的所有整數求和。
merge（incoming_state）：用 local state 的最大座標值和 incoming_state 代替 local state。
我們來畫一下剛才考慮的系統 semi-lattice ：
我們看到對應於系統值的向量是 semi-lattice 的最大值。我們的 merge() 函數完全對應於這些元素中的任何兩個元素上的 join 操作。這些連接向上收斂。
您可以親自驗證，我們採用哪個順序並不重要。如果我們多次合併相同的值，這也無關緊要。實質上，我們忘記了圖中較低的值，並且要麼保持我們的位置，要麼移動到更高的位置。
如果你希望看到代碼，下面是一個在 Python 中實現為簡單可變數據結構的 G-Counter 示例（本地狀態表示為一個名為 state_list 的整數列表）：
class GCounter:
def __init__(self, nodeId, state_list):
self.nodeId = nodeId
self.state_list = state_list
def value(self):
return sum(self.state_list)
def increment(self):
self.state_list[self.nodeId] += 1
def merge(self, incoming):
for idx in range(0, len(self.state_list)):
self.state_list[idx] = max(self.state_list[idx],
incoming.state_list[idx])
Conclusion
還有許多其他類型的數據結構可以建模為收斂CRDT。您可以擁有計數器，集，映射和圖表。在每種情況下，我們都需要先定義一個 value() 方法和 merge() 方法。也許在未來的文章中，我們將看看如何實現其中的一些。
同時，如果您想更深入地瞭解 CRDT 背後的理論（包括基於操作的 CRDT，我們還沒有討論過），請查看收斂性和交換性複製數據類型的綜合研究 Marc Shapiro，Nuno Preguiça，Carlos Baquero和Marek Zawirski。
閱讀更多 Gravity地心 的文章
