CRDT——解決最終一緻問題的利器

概述

跨資料中心的資料同步是企業提升容災能力的必備手段，對于社交、視訊直播、電商以及遊戲等通路規模大、業務分布廣的行業，跨區域全球部署也愈發重要。

然而面對大型分布式系統, 不免要讨論CAP理論，在跨區域多活的場景下如何取舍？顯然P(網絡分區)是首要考慮因素。其次，跨區域部署就是為了提高可用性，而且對于常見的一緻性協定，不管是2PC、Paxos還是raft，在此場景下都要做跨區域同步更新，不僅會降低使用者體驗，在網絡分區的時候還會影響可用性，是以C必定被排在最後。那是不是C無法被滿足了呢？事實并非如此，退而求其次，最終一緻也是一種選擇。CRDT(Conflict-Free Replicated Data Type)1是各種基礎資料結構最終一緻算法的理論總結，能根據一定的規則自動合并，解決沖突，達到強最終一緻的效果。2012年CAP理論提出者Eric Brewer撰文回顧CAP[3]時也提到，C和A并不是完全互斥，建議大家使用CRDT來保障一緻性。自從被大神打了廣告，各種分布式系統和應用均開始嘗試CRDT，redislabs[4]和riak[5]已經實作多種資料結構，微軟的CosmosDB[6]也在azure上使用CRDT作為多活一緻性的解決方案。

阿裡雲redis現配套推出了全球多活産品[7]，助力企業在雲上部署跨區域服務，并且依據CRDT確定在全球多活的場景下，所有redis執行個體中資料最終一緻。本篇文章我們會對CRDT進行簡要介紹，下一篇文章将說明我們是如何實作CRDT的。

CRDT簡介

先簡單統一一下概念和名詞:

• object: 可以了解為“副本”
• operation: 操作接口，由用戶端調用，分為兩種，讀操作query和寫操作update
• query: 查詢操作，僅查詢本地副本
• update: 更新操作，先嘗試進行本地副本更新，若更新成功則将本地更新同步至遠端副本
• merge: update在遠端副本的合并操作

一個資料結構符合CRDT的條件是update操作和merge操作需滿足交換律、結合律和幂等律，具體證明見[1]，在此不做贅述。如果update操作本身滿足以上三律，merge操作僅需要對update操作進行回放即可，這種形式稱為op-based CRDT，最簡單的例子是集合求并集。

如果update操作無法滿足條件，則可以考慮同步副本資料，同時附帶額外元資訊，通過元資訊讓update和merge操作具備以上三律，這種形式稱為state-based CRDT。讓元資訊滿足條件的方式是讓其更新保持__單調__，這個關系一般被稱為__偏序關系__。舉一個簡單例子，每次update操作都帶上時間戳，在merge時對本地副本時間戳及同步副本時間戳進行比對，取更新的結果，這樣總能保證結果最新并且最終一緻，這種方式稱為Last Write Wins：

有兩點值得注意的地方：

• update操作無法滿足三律，如果能将元資訊附加在操作或者增量上，會是一個相對state-based方案更優化的選擇
• 如果同步過程能確定exactly once的語義，幂等律條件是可以被放寬掉，比如說加法本身滿足交換律結合律但不幂等，如果能保證加法操作隻回放一次，其結果還是最終一緻的。

有了以上的理論基礎後，我們可以看看各種資料結構如何設計，才能滿足CRDT，達到最終一緻。

CRDTs一覽

以下展示一些典型的CRDT資料結構的例子，每一種資料類型都會給出示意圖，必要時給出僞代碼說明，證明略過，有興趣可參見[2]。

Counter

counter是最簡單的例子，為了說明state-based和op-based的差異，在此分别給出兩種形式的描述。

Op-based counter

counter的op-based形式支援兩種寫操作：increment和decrement，由于加法天然滿足交換律和結合律，是以非常容易實作，直接轉發操作即可：

但要注意的是加法不幂等，是以同步過程中需要保證不丢不重。

G-Counter (Grow-only Counter)

counter的state-based形式并非那麼的顯而易見，為了簡化問題，我們先從一個隻有increment的counter開始看起。

由于同步的是全量，如果每個副本單獨進行累加，在進行merge的時候無法知道每個副本具體累加了多少，更不能簡單的取一個max作為最終結果，比如A做一次INCR 1同時B做一次INCR 2，副本全量同步之後，A和B都取max以2做為結果并最終一緻，但正确的結果應該是3。

是以一種可行的方式是在每個副本上都使用一個數組保留其它所有副本的值，update時隻操作目前副本在數組中對應項即可，merge時對數組每一項求max進行合并，query時傳回數組的和，即為counter的目前結果。

update increment()
    let g = myID()
    P[g] := P[g] + 1
query value(): integer v
    let v = sum(P)
merge (X, Y): Z
    let Z.P[i] = max(X.P[i], Y.P[i]) (i in [0, n - 1])           

易見update和merge均能保證單調的遞增，是以G-Counter是state-based CRDT。

PN-Counter

帶有decrement的state-based CRDT也并非像G-Counter那樣顯而易見，帶有減法之後，不能滿足update時單調的偏序關系。 是以正确的方式是構造兩個G-Counter，一個存放increment的累加值，一個存放decrement的累加值。

Register

register本質是一個string，僅支援一種寫操作assign。并發assign是不存在交換律的，是以需要考慮附加上偏序關系。

Last-Writer-Wins Register (LWW Register)

一種簡單的做法是後assign的覆寫先assign的(last write wins)，方式是每次修改都附帶時間戳，update時通過時間戳生成偏序關系，merge時隻取較大時間戳附帶的結果。示意圖前文已經給出。

Set

Set一共有兩種寫操作，add和remove，多節點并發進行add和remove操作是無法滿足交換律的, 會産生沖突：

是以必須附加一些額外資訊，可以從一個隻做添加的set開始看起。

Grow-Only Set (G-Set)

set的add操作本質上是求并，天然滿足交換律、結合律和幂等律, 滿足Op-based CRDT：

交換律: X U Y = Y U X

結合律: (X U Y) U Z = X U (Y U Z)

幂等律: X U X = X           

2P-Set

考慮删除操作，思路和PN-Counter一緻，使用兩個G-Set, set A隻負責添加，對于從set A中remove的元素不做實際删除，隻是複制到set R中，如下：

query時如果元素在set A且不在set R中，則表示該元素存在。

query lookup(e): bool b 
    let b = (e in A && e not in R)           

由于隻同步操作，且兩個set隻添加不減少，易證其為op-based CRDT。但2P-Set十分不實用，一方面已經被删除的元素不能再次被添加，一方面删除的元素還會保留在原set中，占用大量空間。

LWW-element-Set

為了解決删除元素不能再次添加的問題，可以考慮給2P-Set中A和R的每個元素加一個更新時間戳，其它操作保持不變，隻要在查詢的時候做如下處理：

query lookup(e): bool b
    let b = (t1 < t2): (e, t1) in A && (e, t2) not in R               

一個更優化的實作是不要R集合，而A集合中每一個元素除了維護一個更新時間戳之外，還有一個删除标志位。

Observed-Remove Set (OR-Set)

還有一種想法不太相同的設計，核心思想是每次add(e)的時候都為元素e加一個唯一的tag，remove(e)将目前節點上的所有e和對應的tag都删除，這樣在remove(e)同時其它節點又有并發add(e)的情況下e是能夠最終保證添加成功，此種語義稱為add wins。如圖，A上做remove e時僅有A一個tag，是以在C收到A同步過來的remove時，隻删除tag A，tag B保留e在C上仍然存在，最終ABC三個節點是一緻的，都有e及tag B。

雖然在remove時看似存在并不能保證交換律的删除操作出現，但删除的元素是全局唯一的，是以并不破壞語義，故仍然是為CRDT。

ORSet相對來說是一種比較實用的結構，但實作上仍然有幾個問題要解決：

• 重複add和remove的場景下會産生大量的tag，空間需要優化
• 在考慮空間優化的前提下如何生成全局唯一的tag
• 需要考慮如何進行垃圾回收

學術界有多篇論文都是在探讨對此種算法的優化。但OR-Set在實踐中最嚴重的問題是一旦同步通道出現延遲或者中斷，很可能出現使用者認為早已删除掉的字段在同步恢複之後再次出現。從工程實踐角度講，更優化的方案是使用時間戳作為unique tag，好處是易保證唯一性，同時自帶單調遞增屬性，重複删除添加時不會生成大量tag。

附錄

1. CRDT: https://hal.inria.fr/inria-00609399/document
2. CRDT tech report: https://hal.inria.fr/file/index/docid/555588/filename/techreport.pdf
3. Eric Brewer: https://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed
4. redislabs, Developing Applications with Geo-replicated CRDBs on Redis Enterprise Software(RS): https://redislabs.com/redis-enterprise-documentation/developing/crdbs/
5. riak: https://docs.basho.com/riak/kv/2.0.0/developing/data-types/
6. cosmosDB: https://docs.microsoft.com/en-us/azure/cosmos-db/multi-region-writers