![分佈式一致性算法-CRDT二](http://p2.ttnews.xyz/loading.gif)
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。讓我們依次看看我們的三個示例系統。對於三個整數的系統,我們可以畫出下圖:
![分佈式一致性算法-CRDT二](http://p2.ttnews.xyz/loading.gif)
回想一下,對於圖中的任何兩個元素成為 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地心 的文章