在分布式數(shù)據(jù)庫系統(tǒng)領(lǐng)域, 多主(多寫入點, Leader-less)是一個非常誘人的特性, 因為客戶端可以隨機請求任何一個節(jié)點. 這種可隨機選擇訪問點(寫入點)的特性, 使得系統(tǒng)的高可用唾手可得, 因為當客戶端發(fā)現(xiàn)某個節(jié)點出故障時, 更換另一個節(jié)點重試就可以了, 只要系統(tǒng)沒有完全宕機, 幾次重試之后一定成功, 也就可以達到百分之百高可用。

[[422305]]

傳統(tǒng)的 Basic Paxos 常常被誤認為是 Leader-less 的, 也即多主, 但 Basic Paxos 只能用于確定一個實例的共識, 真正落地還需要結(jié)合日志復(fù)制狀態(tài)機, 如果復(fù)制組(多節(jié)點)不指定 Leader 的話, 那么就會出現(xiàn)爭取同一個位置的日志的情況, 也就是在嘗試達成這個位置的日志的共識時出現(xiàn)活鎖. 這種多節(jié)點爭取同一個位置的情況, 在實踐上將導(dǎo)致系統(tǒng)不可用, 因為, 通常自稱采用 Paxos 的多副本數(shù)據(jù)庫系統(tǒng), 依然要顯式指定 Leader, 并不是真正 Leader-less 的.

借鑒 vector 時鐘和多復(fù)制組的思路(如 Multi Raft Group), 是可以避免多主沖突的, 因為, 不同的節(jié)點作為各自組的 Leader, 分別寫入不同的日志序列, 也就完全沒有爭取同一個位置的日志而導(dǎo)致沖突了.

以一個3節(jié)點的集群來舉例, 通過預(yù)先配置強制指定各為其主, 結(jié)構(gòu)為:

有復(fù)制組 G1, 成員節(jié)點是 {A, B, C} , 其中節(jié)點 A 是主. 類似的, 復(fù)制組 G2 和 G3 的主是 B, C. 當客戶端請求不同節(jié)點時, 將日志寫入不同復(fù)制組的日志序列, 因此不會產(chǎn)生沖突.

某一時刻, 所有節(jié)點的狀態(tài)是:

這個狀態(tài)表明, 復(fù)制組 G1 累計有 6 條日志, 復(fù)制組 G2 是 1 條, 復(fù)制組 G3 是 2 條.

到目前為此, 似乎一切順利, 寫入沒有沖突, 還能通過復(fù)制組形成多副本. 但是, 現(xiàn)實不是這樣的, 一個只能寫入的數(shù)據(jù)庫幾乎沒有任何用處, 數(shù)據(jù)庫必須支持讀取, 所以, 日志復(fù)制狀態(tài)機架構(gòu)必須有狀態(tài)機, 也即這 3 條日志序列必須在所有節(jié)點 Apply 到各節(jié)點的狀態(tài)機實例中.

最簡單的方法是在各個節(jié)點上把 3 條日志序列合并成(Merge)一條日志序列, 通過某種算法保證所有節(jié)點上的合并結(jié)果一定是相同的, 例如按時間戳排序, 這樣才能保證狀態(tài)機一致(相同).

但是, 節(jié)點不能只依賴自己本地的 3 條日志序列合并, 在每一次合并時, 它需要獲取其它復(fù)制組的最新信息, 判斷自己本地的日志序列是不是足夠新. 自己作為 Leader 的那一條序列, 當然自己能確定, 但其它兩條不能, 需要詢問其它節(jié)點, 不能定死詢問 Leader, 因為需要容忍某個復(fù)制組的 Leader 宕機的情況.

所以, 針對其它復(fù)制組, 采取 Read Index 邏輯, 可以判斷是否最新. 并且在其它組 Leader 宕機的情況下, 將對應(yīng)的日志序列從其它 Follower 那里補齊.

日志序列中可能包含非冪等的指令, 通過加入時間戳之后, 非冪等的指令可以變成冪等的.(需要文章論證). 以一個 key 為例, 狀態(tài)機中的 key-value 帶有初始化時間戳和最新更新時間戳 {reset_time, modify_time} . 當收到一條 incr 指令時, 指令中帶有時間戳, 與 key-value 中的 meta 信息比對之后, 就能知道 Apply 算法.

if key.reset_time < op.time { 
    value += 1 
} else { 
    // 忽略在初始化之前的指令 
} 

例如, 在 A 節(jié)點上針對 key 執(zhí)行了 set 操作, 便會復(fù)位其 reset_time, 之后, 再收到其它節(jié)點的更早的 incr 指令時, 這個 incr 指令就不能修改狀態(tài)機了, 因為這個指令發(fā)生在復(fù)位之前.

各個節(jié)點的系統(tǒng)時鐘不同步?jīng)]關(guān)系, 因為一致性與系統(tǒng)時鐘沒有必然聯(lián)系(需要文章論證). 只要確保所有節(jié)點最終的結(jié)果是一致的(相同)的就行. 不要讓 A 節(jié)點先執(zhí)行 set 再執(zhí)行 incr, 而 B 節(jié)點先執(zhí)行 incr 再執(zhí)行 set 這種情況出現(xiàn). 在這個例子中, 從上帝視角知道 incr 在 set 之前, 所以, A 節(jié)點先執(zhí)行 set, 然后遇到 incr 指令時會忽略.

上面的時間戳比較要求不同的節(jié)點產(chǎn)生的時間戳不能相同, 可以把節(jié)點ID當作時間戳的最低位, 避免兩個時間戳相同.

對于 incr 操作, 初始化比較簡單, 但是, 對于 pop 這種非冪等性的操作, 并不是初始化, 很難解決. 本質(zhì)上, 是一種回滾操作, 能實現(xiàn), 但成本太大, 要討論起來真是夠多的.

不同的節(jié)點收到不是自己負責(zé)的日志序列的延遲不一定, 但是, 我們又不能等確保全部日志序列都收到之后再 Apply, 雖然等全部日志序列都到齊之后再 Apply 可以不需要回滾操作, 但等待行為不能容忍宕機(CAP 理論).

總結(jié)起來, 就是 沒有銀彈 . vector 時鐘看起來很美好, 但日志序列之間的相互依賴問題, 要么通過停止等待來解決, 要么通過回滾操作來解決, 否則無法保證多副本一致(相同). 但是, 某些操作的回滾成本太大.

注: 有一種技術(shù)叫 CRDT, 思想類似, 但是上面討論的問題依然存在.

考慮過這個問題:

• C 宕機, 但是它上面有一條日志還沒有復(fù)制到其它節(jié)點.
• A 和 B 各自合并日志序列之后 Apply 了, 兩者的狀態(tài)機一致, 沒問題.

這時, C 恢復(fù), 那條日志得以復(fù)制出去, 這時, A 和 B 需要回滾, 然后重新合并, 再 Apply.

如果 C 在恢復(fù)之后, 給那條日志賦予新的時間戳, 那么也會有一種場景(C 宕機前日志已經(jīng)復(fù)制出去了, 但它還沒知道結(jié)果), 同樣需要回滾, 因為別的節(jié)點可能已經(jīng) Apply 過那條日志了.