想像三個人在飛機上、各自沒有網路,同時編輯同一份共享筆記——落地後手機一連上網,三份筆記要怎麼自動合而為一、還不吵架? 傳統做法是先「開會投票」(共識演算法,如資料庫的 Raft/Paxos)決定誰說了算,但要投票就得等大家上線、彼此協調,慢。 CRDT 走的是另一條路:只要每次「合併」兩份狀態的動作滿足三個數學性質——交換律(先併你還是先併我都一樣)、 結合律(三份怎麼兩兩併都一樣)、冪等性(同一份重複併不會出錯)——那麼不管誰先連上、訊息重送幾次、以什麼順序合併, 每個人最後都會收斂到「完全相同」的結果。不需要開會、不需要鎖,這就是最終一致(eventual consistency)。 這頁用兩個最經典的 state-based(狀態型)CRDT 帶你看它怎麼做到:只增計數器 G-Counter 與可加可刪的集合 OR-Set。
示範場景固定:3 個副本(可想成三台裝置)各自離線做本地操作,狀態因此分歧;接著以不同的 merge 順序兩兩合併, 最後全部收斂到相同的最終狀態。核心觀察就是——因為 merge 滿足交換/結合/冪等, 順序不影響結果(本頁對 G-Counter 實地跑了「順序 A」與「順序 B」兩種合併順序,得到完全相同的向量)。
r<副本>:<序號> 產生(決定性、可重播),
非真隨機 UUID;本頁無任何隨機,兩次播放逐幀相同。③grid 只顯示「狀態格」(G-Counter 的分量、OR-Set 的存活 tag 數),
合併過程的細節放在下方面板與旁白。④這是最終一致路線;需要「讀到的一定是最新、且全域看到同一順序」時,仍得走
強一致的共識演算法(Raft/Paxos)——兩者是分散式系統的兩條路,各有取捨。
G-Counter:每個副本持有一個「分量向量」,increment() 只加自己那一格(所以每格只增不減);value()=各分量總和;
merge=逐分量取 max。三副本離線各自 +3/+2/+5,收斂後每個副本都變成 [3,2,5](value=10)。
OR-Set:add(e) 給元素配一個唯一 tag 存入 added;remove(e) 只把「自己已經看過」的 tag 記入 tombstone(observed-remove);
lookup(e)=added 中存在未被 removed 的 tag;merge=added 逐元素聯集、removed 聯集。示範裡 r0 把 A、B 都 remove 了,
但 r1、r2 並發 add 的 A、B 用的是不同 tag、r0 沒看過也就沒移除——收斂後 A、B 因此存活,最終集合 {A,B,C}。
這正是 OR-Set 的招牌語意:並發的 add 勝過 remove。