← 回首頁

CRDT 無衝突複製資料型別(Conflict-free Replicated Data Type)

想像三個人在飛機上、各自沒有網路,同時編輯同一份共享筆記——落地後手機一連上網,三份筆記要怎麼自動合而為一、還不吵架? 傳統做法是先「開會投票」(共識演算法,如資料庫的 Raft/Paxos)決定誰說了算,但要投票就得等大家上線、彼此協調,慢。 CRDT 走的是另一條路:只要每次「合併」兩份狀態的動作滿足三個數學性質——交換律(先併你還是先併我都一樣)、 結合律(三份怎麼兩兩併都一樣)、冪等性(同一份重複併不會出錯)——那麼不管誰先連上、訊息重送幾次、以什麼順序合併, 每個人最後都會收斂到「完全相同」的結果。不需要開會、不需要鎖,這就是最終一致(eventual consistency)。 這頁用兩個最經典的 state-based(狀態型)CRDT 帶你看它怎麼做到:只增計數器 G-Counter 與可加可刪的集合 OR-Set

示範場景固定:3 個副本(可想成三台裝置)各自離線做本地操作,狀態因此分歧;接著以不同的 merge 順序兩兩合併, 最後全部收斂到相同的最終狀態。核心觀察就是——因為 merge 滿足交換/結合/冪等, 順序不影響結果(本頁對 G-Counter 實地跑了「順序 A」與「順序 B」兩種合併順序,得到完全相同的向量)。

教學誠實揭露: ①本頁為 state-based(狀態型) CRDT 骨架,真實產品級 CRDT(如 Automerge、Yjs、Redis CRDT)另含因果追蹤(causal context / version vector)tombstone 垃圾回收、op-based 傳遞等,遠比此複雜。②tag 以固定序號 r<副本>:<序號> 產生(決定性、可重播), 非真隨機 UUID;本頁無任何隨機,兩次播放逐幀相同。③grid 只顯示「狀態格」(G-Counter 的分量、OR-Set 的存活 tag 數), 合併過程的細節放在下方面板與旁白。④這是最終一致路線;需要「讀到的一定是最新、且全域看到同一順序」時,仍得走 強一致的共識演算法(Raft/Paxos)——兩者是分散式系統的兩條路,各有取捨。

CRDT 收斂動畫:G-Counter → OR-Set → 兩序收斂

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

固定示範(決定性、無隨機):G-Counter 三副本增量 [3,2,5];OR-Set — r0: add A/add B/remove A/remove B, r1: add A/add C,r2: add B。先跑 G-Counter 順序 A、再以順序 B 重跑(驗證順序無關),接著跑 OR-Set 收斂。
累計 merge 次數(merges):0 目前結構:G-Counter 階段(phase):
每一列 = 一個副本(由上而下 r0 / r1 / r2);欄位隨結構切換 —— G-Counter 欄=分量索引(第 i 欄為副本 i 的貢獻), OR-Set 欄=元素 A / B / C,格內數字為該元素在該副本的「存活 tag 數」(0=不存在)。 藍框(active)= 本步涉及的副本列(merge 時同時框來源列與目標列);綠底(changed)= 本步 merge 真正變動的格。 收斂後所有列會變得完全相同。

各副本目前狀態(本頁自繪,讀 grid 同一份資料)

收斂目標 LUB(最小上界,獨立計算)

是否已收斂(所有副本相同)

尚未收斂

已執行操作紀錄(opLog)