基于CRDT的數(shù)據(jù)最終一致性
對(duì)于分布式系統(tǒng)的架構(gòu)師來說，CAP 定理所描述的一致性和可用性是一個(gè)較大的挑戰(zhàn)。網(wǎng)絡(luò)遠(yuǎn)程跨機(jī)房是不可避免的，數(shù)據(jù)中心之間的高延遲總是導(dǎo)致數(shù)據(jù)中心之間在短時(shí)間內(nèi)出現(xiàn)某種斷開。因此，傳統(tǒng)的分布式應(yīng)用體系結(jié)構(gòu)被設(shè)計(jì)成要么放棄數(shù)據(jù)一致性，要么降低可用性。
不幸的是，我們不能犧牲應(yīng)用可用性。嘗試保持一致性，業(yè)界接受了最終一致性模型。在這個(gè)模型中，應(yīng)用依賴于數(shù)據(jù)庫管理系統(tǒng)來合并數(shù)據(jù)的所有本地副本，以使它們最終保持一致。除非出現(xiàn)數(shù)據(jù)沖突，最終一致性模型看起來很好。一些最終一致性模型承諾盡最大努力解決沖突，但不能保證強(qiáng)一致性。
1. 什么是CRDT?
一個(gè)新趨勢是，圍繞CRDT構(gòu)建的模型提供了強(qiáng)最終一致性。那么，什么是CRDT 呢?
CRDT是無沖突復(fù)制數(shù)據(jù)類型的縮寫。CRDT通過預(yù)先確定的一套解決沖突規(guī)則和語義來實(shí)現(xiàn)了最終一致性，它引入一組特殊的基礎(chǔ)數(shù)據(jù)類型， CRDT是一種特殊的數(shù)據(jù)類型，可以從所有數(shù)據(jù)庫副本匯聚數(shù)據(jù)。常用的 CRDTs包括 G-counters (grow-only counters)、 PN-counters (positive-negative counters)、寄存器、 G-sets (grow-only sets)、2P-sets (two-phase sets)、 or- sets (observed-remove sets)等等。
在背后，CRDT依靠以下數(shù)學(xué)特性來處理數(shù)據(jù):
- 交換律：a ☆ b = b ☆ a
- 結(jié)合律：a ☆ ( b ☆ c ) = ( a ☆ b ) ☆ c
- 等冪: a ☆ a = a
G 計(jì)數(shù)器是一個(gè)完美的例子，操作 CRDT合并的業(yè)務(wù)。這里，a + b = b + a 和 a + (b + c) = (a + b) + c。副本之間只交換更新(增加的內(nèi)容)。CRDT 通過添加更新來合并更新。例如，g 集合應(yīng)用冪等({ a，b，c } u { c } = { a，b，c })來合并所有元素。冪等可以避免在元素通過不同路徑傳遞和匯聚時(shí)重復(fù)添加到數(shù)據(jù)結(jié)構(gòu)中的元素。
一個(gè)典型的多主系統(tǒng)的副本同步方式如下：
CRDT能夠自己解決合并沖突，更一般的情況是處理在多l(xiāng)eader分布式系統(tǒng)中的副本同步。
那么， 有哪些典型的副本同步模式呢?
2. 副本同步模式
2.1 基于狀態(tài)的同步
基于狀態(tài)的同步， 也稱為被動(dòng)同步，形式為聚合復(fù)制數(shù)據(jù)類型(Convergent Replicated Data Type，CvRDT)， 用于 NFS、 AFS、 Coda 等文件系統(tǒng)，以及 Riak、 Dynamo 等 KV存儲(chǔ)。
在這種情況下，副本通過發(fā)送對(duì)象的完整狀態(tài)來傳播更改，必須定義 merge ()函數(shù)，以將傳入的更改與當(dāng)前狀態(tài)合并。
基于狀態(tài)的同步必須滿足以下要求，以確保復(fù)制的一致性:
- 數(shù)據(jù)類型(或復(fù)制上的狀態(tài))形成一個(gè)具有最小上界的偏序集
- Merge ()函數(shù)產(chǎn)生一個(gè)最小上界
- 副本構(gòu)成一個(gè)連通圖
例子:
數(shù)據(jù)類型: 自然數(shù)集是N，極小元到正負(fù)無窮大，則Merge (x，y) = max (x，y)
這樣的要求給出了一個(gè)用于交換的冪等merge()函數(shù)，它也是給定數(shù)據(jù)類型上的一個(gè)單調(diào)遞增函數(shù)。
這保證了所有的副本最終都會(huì)聚合收斂，并且讓我們不用擔(dān)心傳輸協(xié)議ーー可以丟失傳播更新，也可以多次發(fā)送它們，甚至可以按任何順序發(fā)送它們。
2.2 基于操作的同步
基于操作的同步，也稱為主動(dòng)同步，形式為交換復(fù)制數(shù)據(jù)類型(Commutative Replicated Data Type ，CmRDT)，用于 Bayou, Rover, IceCube, Telex這樣的系統(tǒng)。
在這種情況下，副本通過向所有副本發(fā)送操作來傳播更改。當(dāng)對(duì)副本進(jìn)行更改時(shí):
執(zhí)行 generate ()方法，該方法返回一個(gè)要在其他副本上調(diào)用的 effector ()函數(shù)。換句話說，effector ()是一個(gè)用于修改其他副本狀態(tài)的閉包。
將effector ()應(yīng)用于本地狀態(tài)
向所有其他副本傳播effector ()
基于操作的同步必須滿足以下要求，以確保復(fù)制的一致性:
- 可靠的傳輸協(xié)議
- 如果effector()以因果順序交付，那么并發(fā) effector ()就必須轉(zhuǎn)換為OR
- 如果effector()在沒有遵守因果順序的情況下交付，那么所有effector()都必須轉(zhuǎn)換
- 如果能夠多次傳遞，則 effector ()必須是冪等的.
- 在現(xiàn)實(shí)中，一般會(huì)依賴于可靠的發(fā)布-訂閱系統(tǒng)(例如，Kafka)作為交付的一部分。
2.3 基于增量的同步
考慮到基于狀態(tài)/操作的同步，如果一個(gè)更改只影響對(duì)象的一部分，那么傳輸整個(gè)對(duì)象的狀態(tài)是沒有意義的。此外，如果更新修改了相同的狀態(tài)(如計(jì)數(shù)器) ，我們可以周期性地只發(fā)送一個(gè)聚合狀態(tài)。
增量同步結(jié)合了狀態(tài)和操作這兩種方法，并傳播所謂的 Delta 變異，這些變異相應(yīng)地將狀態(tài)更新到最后的同步日期。所以，需要發(fā)送一個(gè)完整的狀態(tài)進(jìn)行第一次同步，然而，一些實(shí)現(xiàn)實(shí)際上考慮了遠(yuǎn)程副本的狀態(tài)以降低所需的數(shù)據(jù)量。
如果允許延遲，那么基于操作的日志壓縮可能是下一個(gè)優(yōu)化:
2.4 基于純操作的同步
在基于操作的同步中有一個(gè)延遲，以創(chuàng)建一個(gè)effector()。在某些系統(tǒng)中，這樣的延遲是不可接受的，必須立即傳播更新，需要更復(fù)雜的組織協(xié)議以及更多的元數(shù)據(jù)空間。
典型用法：
- 如果在系統(tǒng)中必須立即傳播更新，基于狀態(tài)的同步是一個(gè)糟糕的選擇，因?yàn)樗鼤?huì)增加整個(gè)狀態(tài)的成本。然而，在這種特殊情況下，基于增量的同步是更好的選擇，與基于狀態(tài)更新的差別不會(huì)太大。
- 如果你需要在失敗后同步副本，基于狀態(tài)/基于 delta 是正確的選擇。如果必須使用基于操作的同步，則必須:
- 回復(fù)所有失敗后遺漏的更改
- 獲取其中一個(gè)副本的完整副本并應(yīng)用于所有錯(cuò)過的操作
3.基于操作的同步只需要將 effector ()傳遞給每個(gè)副本一次。通過要求effector ()具有冪等性，可以放松這一要求。實(shí)際上，前者比后者更容易實(shí)現(xiàn)。
基于操作和基于狀態(tài)的同步之間的關(guān)系是:基于操作和基于狀態(tài)的同步可以在保持 CRDT 要求的前提下相互仿真。
3. 數(shù)據(jù)一致性模型
一致性模型數(shù)據(jù)協(xié)議是分布式數(shù)據(jù)庫和應(yīng)用程序之間的一個(gè)協(xié)議，它定義了在寫操作和讀操作之間數(shù)據(jù)的清潔程度。
例如，在一個(gè)強(qiáng)一致性模型中，數(shù)據(jù)庫保證應(yīng)用程序總是讀取最后一次寫入的數(shù)據(jù)。使用循序一致性數(shù)據(jù)庫的時(shí)候，數(shù)據(jù)庫保證你讀取的數(shù)據(jù)的順序與數(shù)據(jù)寫入數(shù)據(jù)庫的順序一致。在最終一致性模型中，分布式數(shù)據(jù)庫承諾在幕后同步和整合數(shù)據(jù)庫副本之間的數(shù)據(jù)。因此，如果將數(shù)據(jù)寫入一個(gè)數(shù)據(jù)庫副本并從另一個(gè)數(shù)據(jù)庫副本讀取數(shù)據(jù)，則可能不會(huì)讀取數(shù)據(jù)的最新副本。
關(guān)于最終一致性的研究已經(jīng)有了許多的研究成果。當(dāng)前的趨勢是從強(qiáng)一致性轉(zhuǎn)向其他可能的一致性變化，研究什么樣的數(shù)據(jù)一致性模型最適合特定的系統(tǒng)/場景，并需要重新考慮當(dāng)前的定義。這就導(dǎo)致了一些矛盾，例如，當(dāng)一些人考慮一個(gè)具有特殊屬性的最終一致性時(shí)，同時(shí)，其他作者已經(jīng)為這個(gè)特殊情況創(chuàng)建了一個(gè)定義。
簡單地，可以從效果來重新定義最終一致性，即如果所有請(qǐng)求都沒問題，那么它最終是一致的。
3.1 數(shù)據(jù)一致性的分類
強(qiáng)一致性(SC)
所有的寫操作都嚴(yán)格按順序執(zhí)行，對(duì)任何副本的讀請(qǐng)求都返回相同的、最后的寫結(jié)果，需要實(shí)時(shí)的共識(shí)(及其所有后果) 。為了解決沖突，允許 n/2-1節(jié)點(diǎn)關(guān)閉。
最終一致性(EC)
在本地進(jìn)行更新，然后傳播更新。讀取一些副本可能會(huì)返回過時(shí)的狀態(tài)。回滾或以某種方式?jīng)Q定在發(fā)生沖突時(shí)應(yīng)該做什么。也就是說，我們還需要共識(shí)，不是實(shí)時(shí)的。
強(qiáng)最終一致性(SEC)
EC + 復(fù)制有一個(gè)自動(dòng)解決沖突的方法。因此，我們不要求達(dá)成共識(shí)，允許關(guān)閉 n-1節(jié)點(diǎn)。
如果放松 CAP 定理中的 SC 要求，那么 SEC 就解決了那些惱人的問題。
3.2 強(qiáng)一致性
兩階段提交是實(shí)現(xiàn)強(qiáng)一致性的常用技術(shù)。這里，對(duì)于本地?cái)?shù)據(jù)庫節(jié)點(diǎn)上的每個(gè)寫操作(添加、更新、刪除) ，數(shù)據(jù)庫節(jié)點(diǎn)將更改傳播到所有數(shù)據(jù)庫節(jié)點(diǎn)，并等待所有節(jié)點(diǎn)確認(rèn)。然后，本地節(jié)點(diǎn)向所有節(jié)點(diǎn)發(fā)送一個(gè)提交，并等待另一個(gè)確認(rèn)。應(yīng)用程序只能在第二次提交之后才能讀取數(shù)據(jù)。當(dāng)網(wǎng)絡(luò)斷開數(shù)據(jù)庫之間的連接時(shí)，分布式數(shù)據(jù)庫將不能進(jìn)行寫操作。
3.3 最終一致性的實(shí)現(xiàn)方法
最終一致性模型的主要優(yōu)點(diǎn)是，即使在分布式數(shù)據(jù)庫副本之間的網(wǎng)絡(luò)連接中斷的情況下，數(shù)據(jù)庫也可以執(zhí)行寫操作。一般來說，這個(gè)模型避免了兩階段提交產(chǎn)生的往返時(shí)間，因此支持的每秒寫操作比其他模型多得多。最終一致性必須解決的一個(gè)問題是沖突，即在不同的地方同時(shí)寫同一個(gè)條目。根據(jù)如何避免或解決沖突，最終一致性可以進(jìn)一步分為以下幾類:
最后寫入的最終一致性(Last writer wins ，LWW)
在這種策略中，分布式數(shù)據(jù)庫依賴于服務(wù)器之間的時(shí)間戳同步。數(shù)據(jù)庫交換每個(gè)寫操作的時(shí)間戳和數(shù)據(jù)本身。如果發(fā)生沖突，使用最新時(shí)間戳的寫操作獲勝。
這種技術(shù)的缺點(diǎn)是假設(shè)所有系統(tǒng)時(shí)鐘都是同步的。實(shí)際上，同步所有的系統(tǒng)時(shí)鐘是困難和昂貴的。
法定人數(shù)的最終一致性(Quorum-based eventual consistency)
此技術(shù)類似于兩階段提交。然而，本地?cái)?shù)據(jù)庫并不等待所有數(shù)據(jù)庫的確認(rèn); 它只是等待大多數(shù)數(shù)據(jù)庫的確認(rèn)。多數(shù)人的確認(rèn)確定了法定人數(shù)。如果發(fā)生沖突，建立仲裁的“寫”操作獲勝。
另一方面，這種技術(shù)增加了寫操作的網(wǎng)絡(luò)延遲，從而降低了應(yīng)用程序的可伸縮性。此外，如果本地?cái)?shù)據(jù)庫與拓?fù)渲械钠渌麛?shù)據(jù)庫副本隔離，那么它將不能進(jìn)行寫操作。
合并復(fù)制(Merge replication)
在這種關(guān)系數(shù)據(jù)庫中常見的傳統(tǒng)方法中，一個(gè)集中的合并代理將所有數(shù)據(jù)合并。這種方法還提供了一些靈活性，可以實(shí)現(xiàn)自己解決沖突的規(guī)則。
合并復(fù)制速度太慢，無法支持實(shí)時(shí)使用的應(yīng)用程序，還存在一個(gè)單點(diǎn)故障。由于此方法不支持沖突解決的預(yù)設(shè)規(guī)則，因此常常導(dǎo)致沖突解決的錯(cuò)誤實(shí)現(xiàn)。
無沖突復(fù)制數(shù)據(jù)類型(Conflict-free replicated data type，CRDT)
簡而言之，基于 CRDT的數(shù)據(jù)庫提供無沖突的最終一致性?；? CRDT的數(shù)據(jù)庫是可用的，即使分布式數(shù)據(jù)庫副本不能交換數(shù)據(jù)。它們總是將本地延遲交付給讀寫操作。
因此，我們希望為不穩(wěn)定且經(jīng)常分區(qū)的分布式系統(tǒng)提供一組基礎(chǔ)數(shù)據(jù)類型。此外，希望這些數(shù)據(jù)類型為我們解決沖突，這樣就不需要與用戶交互或查詢仲裁節(jié)點(diǎn)。
然而，并非所有數(shù)據(jù)庫用例都受益于CRDT，而且，基于 CRDT數(shù)據(jù)庫的沖突解決語義是預(yù)定義的，不能被重寫。
4. CRDT 分析
4.1 CRDT 之 Counter
一個(gè)帶有兩個(gè)操作的整數(shù)值: inc ()和 dec ()，讓我們考慮一些基于操作和狀態(tài)同步的實(shí)現(xiàn):
4.1.1 基于操作的計(jì)數(shù)器
很明顯，我們只需要傳播更新。
例如，Inc () : generator (){ return function (counter){ counter + = 1}}。
4.1.2 基于狀態(tài)的計(jì)數(shù)器
這是一個(gè)棘手的問題，因?yàn)槲覀冞€不清楚如何實(shí)現(xiàn) merge ()函數(shù)。
增量計(jì)數(shù)器，g 計(jì)數(shù)器:
讓我們使用一個(gè)具有副本數(shù)量大小的向量(又叫版本向量) ，每個(gè)副本在 inc ()操作中增加它的向量元素。Merge ()函數(shù)取相應(yīng)向量項(xiàng)的最大值，即計(jì)數(shù)器值中所有向量元素的和。
此外，G-Set 也可以使用。
例如，社交媒體中點(diǎn)擊/喜歡 的計(jì)數(shù)器。
加減計(jì)數(shù)器
使用兩個(gè) g 計(jì)數(shù)器，一個(gè)用于增量，另一個(gè)用于減量。
例如，P2P網(wǎng)絡(luò)(Skype)中登錄的用戶數(shù)量。
非負(fù)數(shù)計(jì)數(shù)器:
不幸的是，到目前為止還沒有一個(gè)現(xiàn)實(shí)中的應(yīng)用。
4.2 CRDT之 Register
具有兩個(gè)操作的存儲(chǔ)單元：assign()和value()。問題在于assign()操作，它們不進(jìn)行交換。有兩種方法可以解決這個(gè)問題:
4.2.1 LWW-Register
通過在每個(gè)操作上生成惟一的 id (時(shí)間戳)來引入總順序。
例如，基于狀態(tài)的，通過元組(value，id)的更新:
現(xiàn)實(shí)中，cassandra 中的列和 NFS中整個(gè)文件或其中的一部分都是具體的應(yīng)用場景。
4.2.2 Multi-Value Register
該方法類似于每個(gè)節(jié)點(diǎn)的 G-Counter+ store 的集合。Multi-Value Register的值是所有值，merge ()函數(shù)對(duì)所有向量元素應(yīng)用 LWW 方法。
例如，網(wǎng)上商城中的購物籃。
4.3 CRDT之 Set
一個(gè)集合有兩個(gè)非交換操作: add ()和 rmv () ，它是容器、映射、圖等的基礎(chǔ)類型。
考慮一個(gè)原生的集合實(shí)現(xiàn)，其中 add ()和 rmv ()在到達(dá)時(shí)順序執(zhí)行。首先，在第1和第2個(gè)副本上有并發(fā)的 add () ，然后 rmv ()在第1個(gè)副本上到達(dá)。
果然，在同步之后副本發(fā)生了偏移。
4.3.1 Grow-Only Set
一個(gè)非常簡單的解決方案是根本不允許 rmv ()操作。Add ()操作轉(zhuǎn)換，merge ()函數(shù)只是一個(gè)集合。
4.3.2 2P-Set
允許 rmv ()操作，但不能在刪除元素后重新添加元素。一個(gè)附加的 g-set可以用來跟蹤刪除的元素(也稱為墓碑集)。
4.3.3 LWW-element Set
思路是在一個(gè)集合中引入一個(gè)總順序。例如，生成時(shí)間戳。我們需要兩個(gè)集合: 添加集和刪除集。Add ()將(element，unique _ id ())添加到 add-set，rmv ()將添加到 remove-set。Lookup ()檢查 id 在 add-set 或 rmv-set 中的大小。
4.3.4 PN-Set
對(duì)集合進(jìn)行排序的另一種方法ーー為每個(gè)元素添加一個(gè)計(jì)數(shù)器。在 add ()操作上增加它，在 rmv ()上減少它。當(dāng)且僅當(dāng)其計(jì)數(shù)器為正時(shí)，集合中要考慮相應(yīng)的元素。
4.3.5 Observe-Remove Set, OR-Set, Add-Win Set:
在此數(shù)據(jù)類型中，add ()優(yōu)先于 rmv ()?？赡軐?shí)現(xiàn)的一個(gè)例子是: 向每個(gè)新添加的元素添加唯一的標(biāo)記(每個(gè)元素)。然后 rmv ()將元素的所有可見標(biāo)記發(fā)送給其他副本，副本保留其他標(biāo)記。
4.3.6 Remove-win Set
同上，但是 rmv ()優(yōu)先于 add ().
4.4 CRDT之Graph
圖類型基于集合類型。這里有以下問題: 如果有兩個(gè)并發(fā) addEdge (u，v)和 removeVertex (u)操作ー我們應(yīng)該怎么做?有三種可能的策略:
- removeVertex ()具有優(yōu)先級(jí)，所有關(guān)聯(lián)的邊都將被刪除
- addEdge ()具有優(yōu)先級(jí)，所有移除的頂點(diǎn)將被重新添加
- 延遲 removeVertex ()的執(zhí)行，直到所有并發(fā) removeVertex ()都執(zhí)行為止
第一個(gè)是最容易實(shí)現(xiàn)的，因?yàn)榭梢灾皇褂脙蓚€(gè)2p 集，得到的數(shù)據(jù)類型稱為2p2p 圖.
4.5 CRDT之 Map
對(duì)于map，有兩個(gè)問題需要解決:
- 如何處理并發(fā) put ()操作? 可以類比計(jì)數(shù)器，使用 LWW 或 MV 語義嗎?
- 如何處理并發(fā)的 put ()/rmv ()操作?我們可以通過類比設(shè)置和使用 put-wins 或 rmv-wins 或 last-put-wins 語義么?
Map允許嵌套其他 CRDT 類型。需要注意的是，Map不處理其值的并發(fā)更改，必須由嵌套的 CRDT 本身來處理。
4.5.1 Remove-as-recursive-reset map
在此數(shù)據(jù)類型中，rmv (k)操作“重置”給定 k 下 CRDT 對(duì)象的值，例如，對(duì)于值為零的計(jì)數(shù)器。
例如，一個(gè)共享的購物車。一個(gè)用戶添加更多的面粉，另一個(gè)同時(shí)做一個(gè)檢查(這導(dǎo)致刪除所有元素)。同步之后，有一個(gè)“單元”的面粉，這似乎是合理的。
4.5.2 Remove-wins map
在這種情況下，rmv ()優(yōu)先于 add ()。
例如，玩家張三在一個(gè)網(wǎng)絡(luò)游戲中有10個(gè)硬幣和一個(gè)錘子。接下來發(fā)生了兩個(gè)并發(fā)操作: 在副本 a 上她發(fā)現(xiàn)了一個(gè)釘子，在副本 b 上 Alice 被刪除(刪除所有項(xiàng)目)。
4.5.3 Update-wins map
Add ()優(yōu)先于 rmv () ，更準(zhǔn)確地說，add ()取消了以前所有的并發(fā) rmv ()。
例如，玩家李四在一個(gè)在線游戲中在副本 a 上被刪除，同時(shí)她在副本 b 上做了一些活動(dòng)。很明顯，rmv ()操作必須被取消。
需要注意的是， 假設(shè)我們有兩個(gè)副本 a 和 b，它們以 k 為單位存儲(chǔ)一組復(fù)制品。如果 a 刪除了密鑰 k，b 刪除了集合中的所有元素，那么最終，兩個(gè)副本的密鑰 k 下都會(huì)有一個(gè)空集。
然而，有時(shí)不能取消以前所有的 rmv ()操作?？紤]下面的例子，如果用這種方法，同步狀態(tài)將與初始狀態(tài)相同，這是一個(gè)不正確的結(jié)果。
4.6 CRDT之List
這種類型的問題在于，在本地更新操作之后，不同的副本上的元素索引將會(huì)不同。為了解決這個(gè)問題，可以使用操作轉(zhuǎn)換索引的方法，在應(yīng)用接收到的更新操作時(shí)，必須考慮原始索引。
5 構(gòu)建基于CRDT的應(yīng)用
將應(yīng)用程序連接到基于CRDT的數(shù)據(jù)庫與將應(yīng)用程序連接到任何其他數(shù)據(jù)庫沒有什么不同。然而，由于最終一致性的策略，應(yīng)用程序需要遵循一定的規(guī)則來提供一致的用戶體驗(yàn)，其中的三個(gè)關(guān)鍵點(diǎn)是:
1. 應(yīng)用程序無狀態(tài)
無狀態(tài)應(yīng)用程序通常是 api 驅(qū)動(dòng)的。對(duì) API 的每次調(diào)用都會(huì)導(dǎo)致從頭重新構(gòu)建完整的消息。這可以確保在任何時(shí)候獲得一個(gè)干凈的數(shù)據(jù)副本?；贑RDT的數(shù)據(jù)庫提供的低本地延遲使得重構(gòu)消息更快更容易 。
2. 選擇適合場景的正確 CRDT
計(jì)數(shù)器是 crt 中最簡單的。它可以應(yīng)用于諸如全局投票、跟蹤活動(dòng)會(huì)話、計(jì)量等用例。但是，如果要合并分布式對(duì)象的狀態(tài)，那么還必須考慮其他數(shù)據(jù)結(jié)構(gòu)。例如，對(duì)于允許用戶編輯共享文檔的應(yīng)用程序，您可能不僅希望保留編輯，還希望保留執(zhí)行編輯的順序。在這種情況下，將編輯保存在基于 crdt 的列表或隊(duì)列數(shù)據(jù)結(jié)構(gòu)中將是比將編輯保存在寄存器中更好的解決方案。了解由 crt 強(qiáng)制執(zhí)行的沖突解決語義，以及您的解決方案符合規(guī)則也很重要
3. CRDT 不是一個(gè)萬能的解決方案 !
為了實(shí)現(xiàn)更快的上線應(yīng)用，建議擁有一致的開發(fā)、測試、階段化和生產(chǎn)設(shè)置。除此之外，這意味著開發(fā)和測試設(shè)置必須有一個(gè)小型化的模型。檢查基于CRDT的數(shù)據(jù)庫是可用的 Docker 容器還是可用的虛擬設(shè)備。將數(shù)據(jù)庫副本部署到不同的子網(wǎng)上，這樣就可以模擬已連接和斷開連接的集群設(shè)置。
使用分布式多l(xiāng)eader數(shù)據(jù)庫測試應(yīng)用程序可能聽起來很復(fù)雜。但是在大多數(shù)情況下，需要測試的是數(shù)據(jù)一致性和應(yīng)用程序可用性，這兩種情況分別是: 連接分布式數(shù)據(jù)庫時(shí)，以及數(shù)據(jù)庫之間存在網(wǎng)絡(luò)劃分時(shí)。
通常，可以在開發(fā)環(huán)境中設(shè)置一個(gè)三節(jié)點(diǎn)的測試用分布式數(shù)據(jù)庫，就可以覆蓋單元測試中的大多數(shù)測試場景。以下是測試應(yīng)用的基本準(zhǔn)則:
(1)網(wǎng)絡(luò)連接和節(jié)點(diǎn)間延遲低的測試用例
測試用例必須更加強(qiáng)調(diào)模擬沖突。通常，可以通過多次跨不同節(jié)點(diǎn)更新相同的數(shù)據(jù)來實(shí)現(xiàn)這一點(diǎn)，在所有節(jié)點(diǎn)上合并暫停并驗(yàn)證數(shù)據(jù)的步驟。即使數(shù)據(jù)庫副本是連續(xù)同步的，測試最終一致性數(shù)據(jù)庫也需要暫停測試并檢查數(shù)據(jù)。
對(duì)于驗(yàn)證，要驗(yàn)證兩件事: 所有數(shù)據(jù)庫副本具有相同的數(shù)據(jù)，以及每當(dāng)發(fā)生沖突時(shí)，沖突解決將按照設(shè)計(jì)進(jìn)行。
(2)分區(qū)網(wǎng)絡(luò)的測試用例
這里，通常執(zhí)行與前面相同的測試用例，但是分為兩個(gè)步驟。在第一步中，使用分區(qū)網(wǎng)絡(luò)測試應(yīng)用程序，也就是說，數(shù)據(jù)庫無法彼此同步的情況。當(dāng)網(wǎng)絡(luò)被拆分時(shí)，數(shù)據(jù)庫不會(huì)合并所有數(shù)據(jù)。因此，測試用例必須假設(shè)只讀取數(shù)據(jù)的本地副本。在第二步中，重新連接所有網(wǎng)絡(luò)以測試合并是如何發(fā)生的。如果遵循與前一節(jié)相同的測試用例，那么最終的數(shù)據(jù)必須與前一組步驟中的數(shù)據(jù)相同。
6. CRDT的應(yīng)用示例
6.1 CRDT 用例: 投票，喜歡，愛心，表情符號(hào)等的計(jì)數(shù)
計(jì)數(shù)器有許多應(yīng)用程序。作為一個(gè)分布式的應(yīng)用程序，它可以收集選票，衡量一篇文章中“贊”的數(shù)量，或者跟蹤一條信息的表情符號(hào)反應(yīng)數(shù)量。例如，每個(gè)地理位置的本地應(yīng)用程序連接到最近的數(shù)據(jù)庫集群，更新計(jì)數(shù)器并用本地延遲讀取計(jì)數(shù)器。
可以使用 PN-Counter 的CRDT，示意代碼如下：
- void countVote(String pollId){
- // CRDT Command: COUNTER_INCREMENT poll:[pollId]:counter
- }
- long getVoteCount(String pollId){
- // CRDT Command: COUNTER_GET poll:[pollId]:counter
- }
6.2 CRDT 用例: 分布式緩存
分布式緩存的緩存機(jī)制與本地緩存中使用的機(jī)制相同: 應(yīng)用程序嘗試從緩存中獲取對(duì)象。如果對(duì)象不存在，則應(yīng)用程序從主存儲(chǔ)區(qū)檢索并將其保存在緩存中，并設(shè)置適當(dāng)?shù)倪^期時(shí)間。如果將緩存對(duì)象存儲(chǔ)在基于CRDT的數(shù)據(jù)庫中，該數(shù)據(jù)庫將自動(dòng)在所有區(qū)域中提供緩存。例如，將每個(gè)電影的海報(bào)緩存到本地環(huán)境。
采用register的CRDT，示意代碼如下：
- void cacheString(String objectId, String cacheData, int ttl){
- // CRDT command: REGISTER_SET object:[objectId] [cacheData] ex [ttl]
- }
- String getFromCache(String objectId){
- // CRDT command: REGISTER_GET object:[objectId]
- }
6.3 CRDT 用例: 使用共享會(huì)話數(shù)據(jù)進(jìn)行協(xié)作
CRDT最初是為支持多用戶文檔編輯而開發(fā)的。共享會(huì)話用于游戲、電子商務(wù)、社交網(wǎng)絡(luò)、聊天、協(xié)作、應(yīng)急響應(yīng)和許多其他應(yīng)用程序。例如，一個(gè)簡單的婚禮祝福應(yīng)用，在這個(gè)應(yīng)用中，新婚夫婦的所有祝福者都將他們的禮物添加到購物車中，該購物車作為共享會(huì)話進(jìn)行管理。
婚禮祝福的應(yīng)用程序是一個(gè)分布式應(yīng)用，每個(gè)實(shí)例都連接到本地?cái)?shù)據(jù)庫。在開始一個(gè)會(huì)話時(shí)，應(yīng)用的所有者邀請(qǐng)他們來自世界各地的朋友。一旦被邀請(qǐng)者接受邀請(qǐng)，他們就可以訪問會(huì)話對(duì)象。然后，他們購物并將商品添加到購物車中。
2P-Set 和一個(gè) PN-counter 用于存放購物車中的物品，另外還有一個(gè)2P-Set 用于存儲(chǔ)活動(dòng)會(huì)話，示意代碼如下：
- void joinSession(String sharedSessionID, sessionID){
- // CRDT command: SET_ADD sharedSession:[sharedSessionId] [sessionID]
- }
- void addToCart(String sharedSessionId, String productId, int count){
- // CRDT command:
- // ZSET_ADD sharedSession:[sharedSessionId] productId count
- }
- getCartItems(String sharedSessionId){
- // CRDT command:
- // ZSET_RANGE sharedSession:sessionSessionId 0 -1
- }
- 6.4 CRDT 應(yīng)用: 多
6.4 CRDT 應(yīng)用: 多區(qū)域數(shù)據(jù)攝取
List或隊(duì)列在許多應(yīng)用程序中使用。例如，訂單處理系統(tǒng)在基于 CRDT的 List 數(shù)據(jù)結(jié)構(gòu)中維護(hù)活動(dòng)作業(yè)。這個(gè)解決方案在不同的地點(diǎn)收集任務(wù)。每個(gè)位置的分布式應(yīng)用程序連接到最近的數(shù)據(jù)庫副本。這減少了寫操作的網(wǎng)絡(luò)延遲，從而允許應(yīng)用程序支持大量作業(yè)提交。這些作業(yè)是從一個(gè)集群的 List 數(shù)據(jù)結(jié)構(gòu)中彈出的。這保證了作業(yè)只被處理一次。
基于 CRDT的List，列表數(shù)據(jù)結(jié)構(gòu)用作 FIFO 隊(duì)列的示意代碼如下：
- pushJob(String jobQueueId, String job){
- // CRDT command: LIST_LEFT_PUSH job:[jobQueueId] [job]
- }
- popJob(String jobQueueId){
- // CRDT command: LIST_RIGHT_POP job:[jobQueueId]
- }
小結(jié)
CRDT 對(duì)于許多用例來說確實(shí)是一個(gè)很好的工具，通過在這些場景和其他場景中利用基于 crdt 的數(shù)據(jù)庫，您可以專注于業(yè)務(wù)邏輯，而不用擔(dān)心區(qū)域之間的數(shù)據(jù)同步。最重要的是，基于 crdt 的數(shù)據(jù)庫可以提供本地的應(yīng)用延遲，同時(shí)承諾即使在數(shù)據(jù)中心之間出現(xiàn)網(wǎng)絡(luò)故障時(shí)也可以提供強(qiáng)大的最終一致性。
但是，它可能不是所有用例(例如 ACID 事務(wù))的最佳工具?；? CRDT的數(shù)據(jù)庫通常非常適合微服務(wù)體系結(jié)構(gòu)，其中每個(gè)微服務(wù)都有一個(gè)專門的數(shù)據(jù)庫。當(dāng)然，區(qū)塊鏈或許是使用CRDT 的又一主要場景。
【參考資料與關(guān)聯(lián)閱讀】
- https://www.infoq.com/presentations/CRDT
- Strong Eventual Consistency and Conflict-free Replicated Data Types
- Key-CRDT Stores https://run.unl.pt/bitstream/10362/7802/1/Sousa_2012.pdf
- Conflict-free Replicated Data Types: An Overview https://arxiv.org/pdf/1806.10254.pdf
- A Conflict-Free Replicated JSON Datatype https://arxiv.org/abs/1608.03960
- A comprehensive study of Convergent and Commutative Replicated Data Types https://hal.inria.fr/inria-00555588/document
- Convergent and Commutative Replicated Data Type https://core.ac.uk/download/pdf/55634119.pdf
- Conflict-free replicated data type https://en.wikipedia.org/wiki/Conflict-freereplicateddata_type
- CRDTs: An UPDATE (or just a PUT) https://speakerdeck.com/lenary/crdts-an-update-or-just-a-put
- https://medium.com/@amberovsky/crdt-conflict-free-replicated-data-types-b4bfc8459d26
