前言

前言

之前寫了一篇 Paxos 的直觀解釋，用簡(jiǎn)單的語(yǔ)言描述了 paxos 的工作原理，看過(guò)的朋友說(shuō)是看過(guò)的最易懂的 paxos 介紹，同時(shí)也問(wèn)我是否也寫一篇 raft 的。但 raft 介紹文章已經(jīng)很多很優(yōu)質(zhì)了，感覺(jué)沒(méi)什么可寫的，就一直拖著。

后來(lái)想起來(lái)，在分布式崗的面試中，會(huì)經(jīng)常被問(wèn)到 raft 和 paxos 有什么區(qū)別， 雖然可能會(huì)惹惱面試官，但我會(huì)說(shuō)：沒(méi)區(qū)別。今天介紹一個(gè)把 paxos 和 raft 等統(tǒng)一到一起的分布式一致性算法 abstract-paxos，解釋各種分布式一致性算法從 0 到 1 的推導(dǎo)過(guò)程。算是填了 raft 的坑，同時(shí)在更抽象的視角看 raft，也可以很容易看出它設(shè)計(jì)上的不足和幾個(gè)優(yōu)化的方法。

為了清楚的展現(xiàn)分布式一致性協(xié)議要解決的問(wèn)題，我們將從 0 開始，即從 2 個(gè)基本需求：技術(shù)爆炸和猜疑鏈信息確定和分布式開始。推導(dǎo)出所有的分布式強(qiáng)一致協(xié)議的統(tǒng)一形式，然后再把它特例化為 raft 或 paxos。

本文的整個(gè)推導(dǎo)過(guò)程順著以下過(guò)程，從 assumption 開始，最終達(dá)到 protocol：

本文結(jié)構(gòu)

本文結(jié)構(gòu)

提出問(wèn)題

協(xié)議推導(dǎo)

定義 commit

定義 系統(tǒng)狀態(tài)（State）

協(xié)議描述

工程實(shí)踐

成員變更

使用 abstract-paxos 描述 paxos

使用 abstract-paxos 描述 raft

問(wèn)題

問(wèn)題

從我們要解決的問(wèn)題出發(fā)：實(shí)現(xiàn)一個(gè)分布式的、強(qiáng)一致的存儲(chǔ)系統(tǒng)。存儲(chǔ)系統(tǒng)是存儲(chǔ)信息的，我們首先給出信息和分布式存儲(chǔ)的定義：

香農(nóng)信息定義

香農(nóng)信息理論定義：信息是用來(lái)消除隨機(jī)不定性的東西。

具體來(lái)說(shuō)，對(duì)某個(gè)信息的讀操作，每次得到的內(nèi)容應(yīng)該都是唯一的，確定的。這個(gè)定義將貫穿本文，作為我們?cè)O(shè)計(jì)一致性協(xié)議的最根本的公理。

分布式存儲(chǔ)

存儲(chǔ)系統(tǒng)可以看做一個(gè)可以根據(jù)外部命令（Cmd）改變系統(tǒng)狀態(tài)（State）的東西。例如一個(gè) key-value 存儲(chǔ)，set x=1 或 set x=y+1 都可以看做一個(gè) Cmd。

而分布式則表示存儲(chǔ)系統(tǒng)由多個(gè)節(jié)點(diǎn)（node）組成（一個(gè) node 可以簡(jiǎn)單的認(rèn)為是一個(gè)進(jìn)程），存儲(chǔ)系統(tǒng)的操作者是多個(gè)并發(fā)的寫入者（write）和讀取者（reader）。

而一個(gè)可靠的分布式也意味著它必須允許宕機(jī)：它必須能容忍部分節(jié)點(diǎn)宕機(jī)還能正常工作。

所以它必須有冗余，即：每個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè) State 的副本，而我們需要的分布式一致性協(xié)議的目的，就是保證對(duì)外界觀察者（reader）能夠提供保證香農(nóng)信息定義的 State 的信息。

系統(tǒng)要提供在 writer 或 reader 只能訪問(wèn)到部分節(jié)點(diǎn)時(shí)系統(tǒng)也能工作，這里的部分節(jié)點(diǎn)在分布式領(lǐng)域一般定義為一個(gè)quorum：

Quorum

Quorum

一個(gè) quorum 定義為一個(gè)節(jié)點(diǎn)（node）集合。e.g. HashSet。

在這個(gè)系統(tǒng)中，分布式的特性要求 writer 只需能聯(lián)系到一個(gè) quorum 就可以完成一個(gè)信息的寫入，即：實(shí)現(xiàn)quorum-write。而 reader 只需要聯(lián)系到一個(gè) quorum 就可以確定的讀取到信息，即實(shí)現(xiàn)quorum-read。

因?yàn)?writer 寫入的信息 reader 必須能讀到，所以任意 2 個(gè) quorum 必須有交集：

大部分時(shí)候， 一個(gè) quorum 都是指 majority，也就是多于半數(shù)個(gè) node 的集合。例如【a,b】，【b,c】，【c,a】是集合【a,b,c】的 3 個(gè) quorum。

如果 任何一個(gè) reader 都能通過(guò)訪問(wèn)一個(gè) quorum 來(lái)讀到某個(gè)數(shù)據(jù)，那么這條數(shù)據(jù)就滿足了香農(nóng)信息定義，我們稱這條數(shù)據(jù)為 commit 的。

Commit

Commit

根據(jù)香農(nóng)信息定義，如果寫入的數(shù)據(jù)一定能通過(guò)某種方法讀取到，則認(rèn)為它是 committed。

如果某個(gè)數(shù)據(jù)有時(shí)能讀到有時(shí)不能，它就不是一個(gè)信息。

不確定讀的例子

例子1: 讀到不確定的結(jié)果

例如下面 3 個(gè) node N1，N2，N3 的 例子1，

N1 存儲(chǔ)了[x,y]，

N3 存儲(chǔ)了 [z]，

使用 quorum-read 去讀的時(shí)候，有時(shí)能得到【x,y】（訪問(wèn) N1,N2），有時(shí)能得到【z】（訪問(wèn) N2,N3）

所以【x,y】和【z】在這個(gè)系統(tǒng)中都不是信息，都不是 commit 完成的狀態(tài)。

例子2: 總能讀到的結(jié)果

而像以下這個(gè) 例子2， 一次 quorum-read 不論落到哪 2 個(gè) node 上，都能看到【z】

所以【z】在這個(gè)系統(tǒng)中有機(jī)會(huì)成為一個(gè)信息。

這時(shí)還不能確定【z】是一個(gè)信息，因?yàn)檫@里如果 reader 訪問(wèn) N1,N2，還涉及到是選 【x,y】還是選 【z】作為系統(tǒng)當(dāng)前的狀態(tài)的問(wèn)題，也就是說(shuō)讀取的結(jié)果還不能保證唯一。后面繼續(xù)討論。

因此，我們就得到了在一個(gè)多副本的存儲(chǔ)系統(tǒng)中 commit 完成的條件：

commit-寫 quorum：以保證任何 reader 都可讀到。

commit-唯一：以保證多個(gè) reader 返回相同的結(jié)果。

commit 后不能修改：以保證多次讀返回同樣的結(jié)果。

我們先解釋這幾個(gè)條件，接著討論如何設(shè)計(jì)一個(gè) commit 的協(xié)議來(lái)滿足這幾個(gè)條件，從而達(dá)到一致性。

commit-寫 quorum

一個(gè)數(shù)據(jù)必須有機(jī)會(huì)被 reader 見(jiàn)到：即一個(gè)數(shù)據(jù)已經(jīng)寫到一個(gè)quorum中：commit-寫 quorum。

commit-唯一

這里唯一是指，在可見(jiàn)的基礎(chǔ)上，增加一個(gè)唯一確定的要求：

例如在上面的例子2 中，如果 reader 一次讀操作訪問(wèn)到 N1, N2 這 2 個(gè) node，那么它收到的看到的 2 個(gè) State 的副本分別是【x,y】和【z】，這 2 個(gè) State 的副本都是可見(jiàn)的，但作為一個(gè)存儲(chǔ)系統(tǒng)，任何一個(gè) reader 都必須選擇同樣的 State 作為當(dāng)前系統(tǒng)的 State（否則違反香農(nóng)信息定義的消除不確定性的原則）。

所以我們對(duì)讀操作還要求 reader 能有辦法在所有可見(jiàn)的副本中唯一確定的選擇一個(gè) State，作為讀操作的結(jié)果。

commit 后不能修改

香農(nóng)信息定義要求一個(gè) commit 完成的 State 必須永遠(yuǎn)可被讀到：即要求 commit 的 State 不能被覆蓋和修改，只能增加。

State 不能被修改有點(diǎn)反直覺(jué),，因?yàn)橐话愕拇鎯?chǔ)系統(tǒng),，先存儲(chǔ)了 x=1，還可以修改為 x=2?？雌饋?lái)是允許修改的。

這里可以這樣理解：

經(jīng)歷了 x=1，再到 x=2 的一個(gè) State （【x=1, x=2】），跟直接到 x=2 的 State（【x=1,】）是不同的。這個(gè)不同之處體現(xiàn)在：可能有個(gè)時(shí)間點(diǎn)，可以從第一個(gè) State 讀出 x=1 的信息，而第二個(gè) State 不行。

常見(jiàn)的 State 定義是：一個(gè) Cmd 為元素的，只允許 append 的 list：Vec.

這也就是一個(gè)記錄變更操作（Cmd）的日志（log），或稱為 write-ahead-log(WAL). 而系統(tǒng)的 State 也由 WAL 唯一定義的。在一個(gè)典型的 WAL + State Machine 的系統(tǒng)中（例如 leveldb），WAL 決定了系統(tǒng)狀態(tài)（State），如這 3 條log：【set x=1, set x=2, set y=3】，而平常人們口中的 State Machine，僅僅是負(fù)責(zé)最終將整個(gè)系統(tǒng)的狀態(tài)呈現(xiàn)為一個(gè) application 方便使用的形式，即一般的 HashMap 的形式：【x=2, y=3】。

所以在本文中，WAL 是真實(shí)的 State，我們這里說(shuō)的不能修改，只能追加，就是指 WAL 不能修改，只能追加。本文中我們不討論 State Machine 的實(shí)現(xiàn)。

如果把存儲(chǔ)系統(tǒng)的 State 看做是一個(gè)集合，那么它必須是一個(gè)只增的集合：

State

State

本文的目的僅僅是來(lái)統(tǒng)一 paxos 和 raft，不需要太復(fù)雜，只需把 State 定義為一個(gè)只能追加的操作日志：

log 中的每個(gè) entry 是一個(gè)改變系統(tǒng)狀態(tài)的命令（Cmd）。

這是 State 的初步設(shè)計(jì)，為了實(shí)現(xiàn)這個(gè)一致性協(xié)議，后面我們將對(duì) State 增加更多的信息來(lái)滿足我們的要求。

根據(jù)commit-寫 quorum的要求，最終 State 會(huì)寫到一個(gè) quorum 中以完成 commit，我們將這個(gè)過(guò)程暫時(shí)稱作phase-2。它是最后一步，在執(zhí)行這一步之前，我們需要設(shè)計(jì)一個(gè)協(xié)議，讓整個(gè) commit 的過(guò)程也遵守：

commit-唯一，

commit 后不能修改

的約束。

首先看如何讓 commit 后的數(shù)據(jù)唯一，這涉及到 reader 如何從 quorum 中多個(gè) node 返回的不同的 State 副本中選擇一個(gè)作為讀操作的最終結(jié)果：

reader：找出沒(méi)有完成 commit 的 State 副本

reader：找出沒(méi)有完成 commit 的 State 副本

根據(jù)香農(nóng)信息定義， 已經(jīng) commit 的 State 要求一定能被讀到，但多個(gè) writer 可能會(huì)（在互不知曉的情況下）并發(fā)的向多個(gè) node 寫入不同的 State。

寫入了不同的 State 指：兩個(gè) State：s?, s?，如果 s? ? s? 和 s? ? s? 都不滿足，那么只有一個(gè)是可能被 commit 的。否則就產(chǎn)生了信息的丟失。

而當(dāng) reader 在不同的 node 上讀到 2 個(gè)不同的 State 時(shí)，reader 必須能排除其中一個(gè)肯定沒(méi)有 commit 的 State，如例子2中描述問(wèn)題。

即，commit-唯一要求：兩個(gè)非包含關(guān)系的 State 最多只有一個(gè)是可能 commit 狀態(tài)的。并要求 2 個(gè) State 可以通過(guò)互相對(duì)比，來(lái)排除掉其中一個(gè)肯定不是 commit 的 State，這表示 State 之間存在一個(gè)全序關(guān)系：即任意 2 個(gè) State 是可以比較大小的，在這個(gè)大小關(guān)系中：

較大的是可能 commit 的，

較小的一定不是 commit 的。

State 的全序關(guān)系

State 的全序關(guān)系

State 的全序關(guān)系來(lái)表示 commit 的有效性，但到目前為止，State 本身是一個(gè)操作日志，也就是一個(gè) list，list 之間只有一個(gè)偏序關(guān)系，即包含關(guān)系?；ゲ话?2 個(gè) list 無(wú)法確定大小關(guān)系。

例如, 如果在 2 個(gè)節(jié)點(diǎn)上分別讀到 2 個(gè) log：【x, y, z】和【x, y, w]】，無(wú)法確認(rèn)哪個(gè)是可能 commit 的，哪個(gè)是一定沒(méi)有 commit 的：

所以 State 必須具備更多的信息讓它能形成全序關(guān)系。

并且這個(gè)全序關(guān)系是可控的：即，對(duì)任意一個(gè) State，可以使它變得比任何已知 State 大。否則，writer 在試圖 commit 新的數(shù)據(jù)到系統(tǒng)里時(shí)將無(wú)法產(chǎn)生一個(gè)足夠大的 State 讓 reader 去選它，導(dǎo)致 writer 無(wú)法完成 commit。

給 State 添加用于排序的信息

例如下面 例子3 中，如果每個(gè) node 都為其 State 增加一個(gè)序號(hào)（在例子中的角標(biāo)位置），那么 reader 不論聯(lián)系到哪 2 個(gè)節(jié)點(diǎn)，都可以確定選擇序號(hào)更大的【y】作為讀取結(jié)果，這時(shí)就可以認(rèn)為【y】是一個(gè)信息了。

而 commit 后不能修改 的原則要求系統(tǒng)所有的修改，都要基于已 commit 的 State，所以當(dāng)系統(tǒng)中再次 commit 一個(gè)數(shù)據(jù)后可能是在【y】s 之上追加【z,w】：

為了實(shí)現(xiàn)上述邏輯， 一個(gè)簡(jiǎn)單的實(shí)現(xiàn)是讓最后一個(gè) log 節(jié)點(diǎn)決定 2 個(gè) State 之間的大小關(guān)系。

于是我們可以對(duì) State 的每個(gè) log 節(jié)點(diǎn)都需要加入一個(gè)偏序關(guān)系的屬性 commit_index（本文為了簡(jiǎn)化描述, 使用一個(gè)整數(shù)）來(lái)確定 State 的全序關(guān)系：

在后面的例子中，我們將 commit_index 寫成每條 log 的下標(biāo)的形式，例如

將表示為：

同時(shí)定義一個(gè) method 用來(lái)取得一個(gè) State 用于比較大小的 commit_index：

commit_index 的值是由 writer 寫入 State 時(shí)決定。即 writer 決定它寫入的 State 的大小。

如果兩個(gè) State 不是包含關(guān)系，那么大小關(guān)系由 commit_index 決定。writer 通過(guò) quorum-write 寫入一個(gè)足夠大的 State，就能保證一定被 reader 選擇，就完成了 commit。

這也暗示了：

非包含關(guān)系的 2 個(gè) State 的 commit_index 不能相同。否則 State 之間無(wú)法確定全序關(guān)系。即，任意 2 個(gè) writer 不允許產(chǎn)生相同的 commit_index。

同一個(gè) writer 產(chǎn)生的 State 一定是包含關(guān)系，不需要使用 commit_index 去決定大?。?br /> 對(duì)于 2 個(gè)包含關(guān)系的 State：s? ? s?，顯然對(duì)于 reader 來(lái)說(shuō)，應(yīng)該選擇更大的 s?，無(wú)需 commit_index 來(lái)確定 State 的大小。因此一個(gè) writer 產(chǎn)生的 State，允許多個(gè) log 的 commit_index 相同。并用 log 的長(zhǎng)度確定大小關(guān)系。

這樣我們就得到了 State 的大小關(guān)系的定義：

State-全序定義

兩個(gè) State 的順序關(guān)系：通過(guò) commit_index 和 log 長(zhǎng)度確定，即比較 2 個(gè) State 的：（s.commit_index(), s.log.len()）。

上面提到，commit_index 是一個(gè)具有偏序關(guān)系的值，不同類型的 commit_index 會(huì)將 abstract-paxos 具體化為某種協(xié)議或協(xié)議族，例如：

如果 commit_index 是一個(gè)整數(shù)，那就是類似 paxos 的 rnd。

而 raft 中，與 commit_index 對(duì)應(yīng)的概念是【term, Option】，它是一個(gè)偏序關(guān)系的值，也是它造成了 raft 中選舉容易出現(xiàn)沖突。

關(guān)于 abstract-paxos 如何映射為 paxos 或 raft，在本文的最后討論。

另一方面，從 writer 的角度來(lái)說(shuō)：

如果一個(gè) writer 可以生成一個(gè) commit_index 使之大于任何一個(gè)已知的 commit_index，那么這時(shí) abstract-paxos 就是一個(gè)活鎖的系統(tǒng)：它永遠(yuǎn)不會(huì)阻塞，但有可能永遠(yuǎn)都不會(huì)成功提交。例如 paxos 或 raft

如果一個(gè) writer 無(wú)法生成任意大的 commit_index，那么它就是一個(gè)死鎖的系統(tǒng)，例如 2pc

當(dāng)然也可以構(gòu)造 commit_index 使 abstract-paxos 既活鎖又死鎖，那么可以認(rèn)為它是一個(gè)結(jié)合了 paxos 和 2pc 的協(xié)議。

有了 State 之間的全序關(guān)系，然后再讓 writer 保證phase-2寫到 quorum 里的 State 一定是最大的，進(jìn)而讓 reader 讀取時(shí)都可以選擇這個(gè) State，達(dá)到香農(nóng)信息定義要求的信息確定性要求，即commit-唯一的要求，完成 commit：

下面來(lái)設(shè)計(jì)協(xié)議，完成這一保證：

協(xié)議設(shè)計(jì)

協(xié)議設(shè)計(jì)

現(xiàn)在我們來(lái)設(shè)計(jì)整個(gè)協(xié)議，首先，有一個(gè) writer w，w 最終 commit 的操作是在 phase-2 將 State 寫到一個(gè)quorum。writer 的數(shù)據(jù)結(jié)構(gòu)定義為一個(gè)它選擇的 quorum，以及它決定使用的 commit_index：

因?yàn)?reader 讀取時(shí)，只選它看到的最大的 State 而忽略較小的。所以如果一個(gè)較大的 State 已經(jīng) commit，那么整個(gè)系統(tǒng)就不能再允許 commit 一個(gè)較小的 State，否則會(huì)造成較小的 State 認(rèn)為自己 commit 完成，但永遠(yuǎn)不會(huì)被讀到，這就造成了信息丟失。

例如下面 例子5 中描述的場(chǎng)景，如果最終寫入 State 前不做防御，那么是無(wú)法完成 commit 的：假設(shè)有 2 個(gè) writer w?, w? 同時(shí)在寫它們自己的 State 到自己的 quorum：

t1 時(shí)間 w? 將 【y?】寫到 N2, N3,

t2 時(shí)間 w? 將 【x?,y?】寫到了 N1。

那么當(dāng)一個(gè) reader 聯(lián)系到 N1, N2 進(jìn)行讀操作時(shí)，它會(huì)認(rèn)為【x?,y?】是 commit 完成的， 而真正由 w? commit 的數(shù)據(jù)就丟失了，違背了香農(nóng)信息定義。

所以：writer 在 commit 一個(gè) State 前，必須阻止更小的 State 被 commit。這就是phase-1要做的第一件事：

Phase-1.1 阻止更小的 State 被 commit

假設(shè) writer w?要寫入的 State 是 s?，在 w?將 s? 寫到一個(gè) quorum 前，整個(gè)系統(tǒng)必須阻止小于 s? 的 State 被 commit。

因?yàn)椴煌?writer 不會(huì)產(chǎn)生同樣的 commit_index。所以整個(gè)系統(tǒng)只需阻止更小的 commit_index 的 State 被 commit：

為達(dá)到這個(gè)目的，在這一步，首先通知 w? quorum 中的每個(gè)節(jié)點(diǎn)：拒絕所有其他 commit_index 小于 w?。commit_index 的 phase-2 請(qǐng)求。

于是我們基本上可以確定 node 的數(shù)據(jù)結(jié)構(gòu)，它需要存儲(chǔ)phase-2中真正寫入的 State，以及phase-1.1中要拒絕的 commit_index：

在后面的例子中，我們將用一個(gè)數(shù)字前綴表示 node 中的 commit_index，例如：

將表示為:

一個(gè)直接的推論是, 一個(gè) node 如果記錄了一個(gè) commit_index , 就不能接受更小的 commit_index , 否則意味著它的防御失效了: Node.commit_index 單調(diào)增。

如果 writer 的phase-1.1請(qǐng)求沒(méi)有被 quorum 中全部成員認(rèn)可，那么它無(wú)法安全的進(jìn)行phase-2，這時(shí)只能終止。

最后我們整理下phase-1.1的流程：

每個(gè) node 在 P1Reply 中返回自己之前保存的 commit_index，writer 拿到 reply 后跟自己的commit_index 對(duì)比，如果 w.commit_index >= P1Reply.commit_index，表示 phase-1.1 成功。

完成phase-1.1后，可以保證沒(méi)有更小的 State 可以被 commit 了。

然后，為了滿足 commit 后不能修改 的原則，還要求 s? 必須包含所有已提交的，commit_index 小于 s?.commit_index() 的所有 State：

Phase-1.2 讀已完成 commit 的 State

因?yàn)?commit 的條件之一是將 State 寫入一個(gè) quorum，所以 w? 詢問(wèn) w?.quorum，就一定能看到小于 w?.commit_index 的，已 commit 的其他 State。這時(shí) writer 是一個(gè) reader 的角色（如果遇到大于 w?.commit_index 的 State，則當(dāng)前 writer 是可能無(wú)法完成提交的，應(yīng)終止）。

且讀過(guò)某個(gè) node 之后，就不允許這個(gè) node 再接受來(lái)自其他 writer 的，小于 w?.commit_index 的 phase-2 的寫入。以避免讀后又有新的 State 被 commit，這樣就無(wú)法保證 w? 寫入的 State 能包含所有已 commit 的 State。

w? 在不同的節(jié)點(diǎn)上會(huì)讀到不同的 State，根據(jù) State 的全序的定義，只有最大的 State 才可能是已 commit 的（也可能不是, 但更小的一定不是），所以 w? 只要選最大的 State 就能保證它包含了所有已 commit 的 State。

在最大 State 的基礎(chǔ)上，增加 w? 自己要寫的內(nèi)容。最后進(jìn)行 phase-2 完成 commit 。

phase-1.1 跟 phase-1.2 一般在實(shí)現(xiàn)上會(huì)合并成一個(gè) RPC，即 phase-1。

Phase-1

Phase-1: Data

Phase-1: Req

Phase-1: Reply

Phase-1: Handler

Phase-2

最后，保證了 s? 當(dāng)前最大，和 commit 后不能修改這兩個(gè)條件后，第 2 階段，writer 就可以安全的寫入一個(gè) s? 完成 commit。

如果 phase-2 完成了，則表示 commit 一定成功了，任何一個(gè) reader 都能讀到唯一確定的 State s?（除非有更大的 State 被寫入了）。

反之，如果有其他 writer 通過(guò) phase-1 阻止了 w?.commit_index 的寫入，那么 w? 的 phase-2 就可能失敗，這時(shí)就退出 commit 過(guò)程并終止。

這里有一個(gè)學(xué)習(xí)分布式系統(tǒng)時(shí)經(jīng)常提出的問(wèn)題：

Q:

因?yàn)樵?phase-1 中 w 已經(jīng)阻止了所有小于 w.commit_index 的 State 的提交，phase-2 是否可以寫入一個(gè)小于 w.commit_index 的 State？

A:

不可以，phase-2 寫入的 State 的commit_index() 跟 w.commit_index 相等時(shí)才能保證安全，簡(jiǎn)單分析下：

顯然要寫的 s?.commit_index() 不能大于 w?.commit_index，因?yàn)?phase-1.1 沒(méi)有保護(hù)大于 w?.commit_index 的 State 的寫入。

雖然在 phase-1 階段，系統(tǒng)已經(jīng)阻止了所有小于 s?.commit_index() 的其他 State 的 phase-2 寫入，如果 w? 寫的 State 的 s_1.commit_index() 小于w.commit_index，那么系統(tǒng)中可能存在另一個(gè)稍大一點(diǎn)的 State (但沒(méi)有 commit，導(dǎo)致 reader 不認(rèn)為 s? 是 commit 的。

例如：

一個(gè) writer w? 在 t1 時(shí)間完成了 phase-1，在 t2 時(shí)間 phase-2 只寫入了 N1；

然后另一個(gè) writer w? 在 t3 時(shí)間完成了 phase-1，phase-2 只寫入了一個(gè)較小的 commit_index=4 的 State。

那么某個(gè) reader 如果通過(guò)訪問(wèn) N1,N2 讀取數(shù)據(jù)，會(huì)認(rèn)為 N1 上的【x?】是 commit 的，破壞了 香農(nóng)信息定義。

所以必須滿足：s?.commit_index() == w?.commit_index

這時(shí)，只要將 State 寫入到 w?.quorum，就可以認(rèn)為提交。

對(duì)應(yīng)每個(gè) node 的行為是：在每個(gè)收到 phase-2 請(qǐng)求的節(jié)點(diǎn)上，如果 node 上沒(méi)有記錄拒絕 commit_index 以下的 phase-2 請(qǐng)求，就可以接受這筆寫入。

一個(gè)推論：一個(gè)節(jié)點(diǎn)如果接受了 commit_index 的寫入，那么同時(shí)它應(yīng)該拒絕小于 commit_index 的寫入了。因?yàn)檩^小的 State 一定不是 commit 的，如果接受，會(huì)造成信息丟失。

Phase-2: data

和 phase-1 類似，一個(gè) node 返回它自己的 commit_index 來(lái)表示它是否接受了 writer 的 phase-2 請(qǐng)求。

在 P2Req 中，如果 state 是完整的，commit_index 總是與 state.commit_index() 一樣，可以去掉；這里保留是因?yàn)橹髮?huì)討論到的分段傳輸：每個(gè)請(qǐng)求只傳輸 State 的一部分，這時(shí)就需要額外的 P2Req.commit_index。

Phase-2: Req

Phase-2: Reply

Phase-2: Handler

也就是說(shuō) phase-2 不止可能修改 Node.state，同時(shí)也會(huì)修改 Node.commit_index。

這里也是一個(gè)學(xué)習(xí)分布式容易產(chǎn)生誤解的地方，例如很多人曾經(jīng)以為的一個(gè) paxos 的bug: paxos-bug。

這里也很容易看出為何在 raft 中必須當(dāng)前 term 復(fù)制到 quorum 才認(rèn)為是 commit 了。

可重復(fù)的 phase-2

要保證寫入的數(shù)據(jù)是 commit 的，只需保證寫入一個(gè) quorum 的 State 是最大的即可。所以 writer 可以不斷追加新的日志，不停的重復(fù)phase-2。

Writer 協(xié)議描述

Writer 協(xié)議描述

最后將整個(gè)協(xié)議組裝起來(lái)的是 writer 的邏輯，如前所講，它需要先在一個(gè) quorum 上完成 phase-1 來(lái)阻止更小的 State 被 commit，然后在 quorum 上完成 phase-2 完成一條日志的提交。

工程實(shí)現(xiàn)

工程實(shí)現(xiàn)

Phase-2: 增量復(fù)制

這個(gè)算法的正確性 還需考慮工程上的方便，

到目前為止，算法中對(duì) State 的寫都假設(shè)是原子的。但在工程實(shí)現(xiàn)上， State 是一個(gè)很大的數(shù)據(jù)結(jié)構(gòu)，很多條 log

所以在phase-2傳輸 State 的過(guò)程中，我們還需要一個(gè)正確的分段寫的機(jī)制：

原則還是保證香農(nóng)信息定義，即：commit 的數(shù)據(jù)不丟失。

State 不能留空洞：有空洞的 State 跟沒(méi)空洞的 State 不同，不能通過(guò)最后一條日志來(lái)確定其所在的 State 大小。

writer 在phase-1完成后可以保證一定包含所有已經(jīng) commit 的 State。

所以在一個(gè)接受phase-2的 node 上，它 Node.state 中任何跟 Writer.State 不同的部分都可以刪除，因?yàn)椴灰恢碌牟糠忠欢](méi)有被 commit。

以下是 phase-2 過(guò)程中刪除 N3 上不一致數(shù)據(jù)的過(guò)程：

t1 時(shí)刻，writer W 聯(lián)系到 N1，N2 完成 phase-1，讀到最大的State【x?,z?】，添加自己的日志到最大 State 上：【x?,z?,w?】，這時(shí)系統(tǒng)中沒(méi)有任何一個(gè) node 的 State 是 commit 完成狀態(tài)的，一個(gè) reader 可能選擇【x?,z?】作為讀取結(jié)果（訪問(wèn)N1,N2），可能選擇【x?,y?】作為讀取結(jié)果（訪問(wèn)N2,N3）。

但這時(shí)一個(gè) State 的子集：【x?】是commit完成的狀態(tài)。

t2 時(shí)刻，W 向 N3 復(fù)制了一段 State：【x?】，它是 N3 本地日志的子集，不做變化。
這時(shí) reader 還是可能讀到不同的結(jié)果，同樣【x?】是 commit 完成的狀態(tài)。

t3 時(shí)刻，W 向 N3 復(fù)制了另一段 State z?，它跟 N3 本地 State 沖突，于是 N3 放棄本地的一段與 writer 不一致的 Statey?，將本地 State 更新為：【x?,z?】

這時(shí)【x?,z?】是 commit 完成狀態(tài)。

t4 時(shí)刻，W繼續(xù)復(fù)制 w_6 到 N3，這是【x?,z?,w_4】是 commit 完成狀態(tài)。

Snapshot 復(fù)制

snapshot 復(fù)制跟 State 分段復(fù)制沒(méi)有本質(zhì)區(qū)別，將 State 中的 log 從 0 到某一范圍以壓縮后的形式傳輸?shù)牡狡渌?node。

成員變更

成員變更

為支持成員變更，我們先加入下面這幾個(gè)行為來(lái)支持成員變更操作：

State 中某些日志（config日志）表示集群中的成員配置。

State 中最后一個(gè)成員配置（config）日志出現(xiàn)就開始生效。

config 日志與普通的日志寫入沒(méi)有區(qū)別。

config 定義一個(gè)集群的 node 有哪些，以及定義了哪些 node 集合是一個(gè) quorum。

例如一個(gè)普通的3成員集群的 config 【{a,b,c}】，它定義的 quorum 有

再如一個(gè)由 2 個(gè)配置組成的 joint config【{a,b,c}, {x,y,z}】。它定義的 quorum 集合是【a,b,c】的 quorum 集合跟【x,y,】的 guorum 集合的笛卡爾積：

然后，我們對(duì)成員變更增加約束，讓成員變更的過(guò)程同樣保證香農(nóng)信息定的要求：

成員變更約束-1

首先，顯然有2 個(gè)相鄰 config 的 quorum 必須有交集。否則新配置啟用后就立即會(huì)產(chǎn)生腦裂。即：

在后面的討論中我們將滿足以上約束的 2 個(gè) config 的關(guān)系表示為：c? ~ c???。

例如：假設(shè) State 中某條日志定義了一個(gè) joint config：【{a,b,c}, {x,y,z}】那么，

下一個(gè)合法的 config 可以是：

uniform config【{a,b,c}】，

或另一個(gè) joint config 【{x,y,z}, {o,p,q}】。

但不能是【{a,x,p}】，因?yàn)樗囊粋€(gè) quorum【a,x}】與 上一個(gè) config 的 quorum【{b,c}, {y,z}】沒(méi)有交集。

成員變更Lemma-1

對(duì) 2 個(gè) config c? ~ c?，以及 2 個(gè) State S? 和 S? 如果 S? 和 S? 互相不是子集關(guān)系，S? 在 c? 上 commit 跟 S? 在 c? 上 commit 不能同時(shí)發(fā)生。

成員變更約束-2

因?yàn)?2 個(gè)不同 writer 提出（propose）的 config 不一定 有交集，所以為了滿足 commit-唯一 的條件，包含新 config 的日志要提交到一個(gè)新，舊配置的 joint config 上。即, c??? 必須在【c?, c???】上 commit. c??? 之后的 State， 只需使用 c??? 進(jìn)行 commit。

但是，當(dāng) writer 中斷，另一個(gè) writer 看到 c??? 時(shí)，它不知道 c??? 處于變更中間，也就是說(shuō)新的 writer 不知道現(xiàn)在的 commit 應(yīng)該使用【c?, c???】，它只使用【c???】。

所以對(duì) config 日志向 joint config 的 commit 分為兩步：

先在舊配置上拒絕更小的 State 的提交，再 propose 新配置。根據(jù)成員變更Lemma-1，即：至少將一個(gè)與 w.commit_index 相同的 State commit 到 c? 上。

再 propose c???，從日志 c??? 之后的日志開始，都只需 commit 到 c??? 上。

最后總結(jié)：

成員變更的約束條件

上一個(gè) config 在當(dāng)前 commit_index 上提交后才允許 propose 下一個(gè)配置。

下一個(gè)配置必須跟最后一個(gè)已提交的配置有交集。

成員變更舉例

raft 只支持以下的成員變更方式

c1 → c1c2 → c2 → c2c3 → c3 …

其中 c1c2 指 c1 跟 c2 的 joint config，例如：

c? ：【a, b, c】；

c?c?：【{a, b, c}，{x, y, z}】。

abstract-paxos 可以支持更靈活的變更:

c1 → c1c2c3 → c3c4 → c4

或回退到上一個(gè) config：

c1c2c3 → c1

合法變更狀態(tài)轉(zhuǎn)換圖示

下面的圖示中簡(jiǎn)單列出了至多 2 個(gè)配置的 joint config 跟 uniform config 之間可轉(zhuǎn)換的關(guān)系：

Variants

Variants

以上為 abastract-paxos 的算法描述部分。接下來(lái)我們將看它是如何通過(guò)增加一些限制條件，absract-paxos 將其變成 classic-paxos 或 raft 的。

秒變 Paxos

限制 State 中的日志只能有一條，那么它就變成 paxos。

不支持成員變更。

其中概念對(duì)應(yīng)關(guān)系為：

秒變 Raft

Raft 為了簡(jiǎn)化實(shí)現(xiàn)（而不是證明），有一些刻意的閹割：

commit_index 在 raft 里是 一個(gè) 偏序關(guān)系 的 tuple，包括：

term

和是否投票給了某個(gè) Candidate：

其中 VotedFor 的大小關(guān)系（即覆蓋關(guān)系：大的可以覆蓋小的）定義是：

即，VotedFor 只能從 None 變化到 Some，不能修改。或者說(shuō)，Some（A）和 Some（B）沒(méi)有大小關(guān)系，這限制了 raft 選主時(shí)的成功幾率.。導(dǎo)致了更多的選主失敗沖突。

commit_index 在每條日志中的存儲(chǔ)也做了簡(jiǎn)化，先看直接嵌入后的結(jié)構(gòu)如下：

raft 中，因?yàn)?VotedFor 的特殊的偏序關(guān)系的設(shè)計(jì)，日志中 Term 相同則 voted_for 一定相同，所以最終日志里并不需要記錄 voted_for，也能用來(lái)唯一標(biāo)識(shí)日志，State，及用于比較 State 的大小。最終記錄為：

這樣的確讓 raft 少記錄一個(gè)字段, 但使得其含義變得更加隱晦，工程上也引入了一些問(wèn)題, xp 并不欣賞這樣的作法。

但不否認(rèn) raft 的設(shè)計(jì)在出現(xiàn)時(shí)是一個(gè)非常漂亮的抽象，主要在于它對(duì) multi-paxos 沒(méi)有明確定義的問(wèn)題，即多條日志之間的關(guān)系到底應(yīng)該是怎樣的，給出了一個(gè)確定的答案。

概念對(duì)應(yīng)關(guān)系:

成員變更方面，raft 的 joint 成員變更算法將條件限制為只允許 uniform 和 joint 交替的變更：c0 -> c0c1 -> c1 -> c1c2 -> c2 ....

不難看出，raft 的 單步變更算法也容易看出是本文的成員變更算法的一個(gè)特例。

Raft 的優(yōu)化

abstract-paxos 通過(guò)推導(dǎo)的方式，得出的一致性算法可以說(shuō)是最抽象最通用的。不像 raft 那樣先給出設(shè)計(jì)再進(jìn)行證明，現(xiàn)在從上向下看 raft 的設(shè)計(jì)，就很容易看出 raft 丟棄了哪些東西和給自己設(shè)置了哪些限制，也就是 raft 可能的優(yōu)化的點(diǎn)：

一個(gè) term 允許選出多個(gè) leader：將 commit_index 改為字典序，允許一個(gè) term 中先后選出多個(gè) leader。

提前 commit：raft 中 commit 的標(biāo)準(zhǔn)是復(fù)制本 term 的一條日志到 quorum。這樣在新 leader 剛剛選出后可能會(huì)延后 commit 的確認(rèn)，如果有較多的較小 term 的日志需要復(fù)制的話。因此一個(gè)可以較快 commit 的做法是復(fù)制一段 State 時(shí)（raft 的 log），也帶上 writer 的 commit_index 信息（即 raft leader 的 term）到每個(gè) node，同時(shí)，對(duì) State 的比較（即raft 的 log 的比較）改為比較【writer.commit_index, last_log_commit_index, log.len()】，在 raft 中，對(duì)應(yīng)的是比較【leader_term, last_log_term, log.len()】。

成員變更允許更靈活的變化：例如 c0c1 -> c1c2.

其中 1,3 已經(jīng)在 openraft 中實(shí)現(xiàn)（朋友說(shuō)它是披著raft皮的paxos/:-)）。

Reference

Reference

可靠分布式系統(tǒng)-paxos的直觀解釋 : https://blog.openacid.com/algo/paxos/

abstract-paxos : https://github.com/openacid/abstract-paxos

(Not a) bug in Paxos : https://github.com/drmingdrmer/consensus-bugs#trap-the-bug-in-paxos-made-simple

leveldb : https://github.com/google/leveldb

openraft : https://github.com/datafuselabs/openraft

Two phase commit : https://en.wikipedia.org/wiki/Two-phase_commit_protocol

偏序關(guān)系 : https://zh.wikipedia.org/wiki/偏序關(guān)系

字典序 : https://zh.wikipedia.org/wiki/字典序

作者介紹：張炎潑（xp）Databend 分布式研發(fā)負(fù)責(zé)人