我這里將主要列舉一致性Hash算法、Gossip協(xié)議、QuorumNWR算法、PBFT算法、PoW算法、ZAB協(xié)議，Paxos會分開單獨講。

一致性Hash算法

一致性Hash算法是為了解決Hash算法的遷移成本，以一個10節(jié)點的集群為例，如果向集群中添加節(jié)點時，如果使用了哈希 算法，需要遷移高達90.91%的數(shù)據(jù)，使用一致哈希的話，只需要遷移 6.48% 的數(shù)據(jù)。

所以使用一致性Hash算法實現(xiàn)哈希尋址時，可以通過增加節(jié)點數(shù)降低節(jié)點 宕機對整個集群的影響，以及故障恢復(fù)時需要遷移的數(shù)據(jù)量。后續(xù)在需要時，你可以通過增 加節(jié)點數(shù)來提升系統(tǒng)的容災(zāi)能力和故障恢復(fù)效率。而做數(shù)據(jù)遷移時，只需要遷移部分數(shù)據(jù)，就能實現(xiàn)集群的穩(wěn)定。

不帶虛擬節(jié)點的一致性Hash算法

我們都知道普通的Hash算法是通過取模來進行路由尋址的，同理一致性Hash用了取模運算，但與哈希算法不同的是，哈希算法是對節(jié)點的數(shù)量進行取模 運算，而一致哈希算法是對 2^32 進行取模運算。你可以想象下，一致哈希算法，將整個 哈希值空間組織成一個虛擬的圓環(huán)，也就是哈希環(huán)：

在一致哈希中，你可以通過執(zhí)行哈希算法，將節(jié)點映射到哈希環(huán)上，從而每個節(jié)點就能確定其在哈希環(huán)上的位置了：

然后當要讀取指定key的值的時候，通過對key做一個hash，并確定此 key 在環(huán)上的位置，從這個位置沿著哈希環(huán)順時針“行走”，遇到的第一節(jié)點就是 key 對應(yīng)的節(jié)點。

這個時候，如果節(jié)點C宕機了，那么節(jié)點B和節(jié)點A的數(shù)據(jù)實際上不會受影響，只有原來在節(jié)點C的數(shù)據(jù)會被重新定位到節(jié)點A，從而只要節(jié)點C的數(shù)據(jù)做遷移即可。

如果此時集群不能滿足業(yè)務(wù)的需求，需要擴容一個節(jié)點：

你可以看到，key-01、key-02 不受影響，只有 key-03 的尋址被重定位到新節(jié)點 D。一般 而言，在一致哈希算法中，如果增加一個節(jié)點，受影響的數(shù)據(jù)僅僅是，會尋址到新節(jié)點和前 一節(jié)點之間的數(shù)據(jù)，其它數(shù)據(jù)也不會受到影響。

實現(xiàn)代碼如下：

/**
 * 不帶虛擬節(jié)點的一致性Hash算法 
 */
public class ConsistentHashingWithoutVirtualNode
{
    /**
     * 待添加入Hash環(huán)的服務(wù)器列表
     */
    private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
            "192.168.0.3:111", "192.168.0.4:111"};

    /**
     * key表示服務(wù)器的hash值，value表示服務(wù)器的名稱
     */
    private static SortedMap<Integer, String> sortedMap =
            new TreeMap<Integer, String>();

    /**
     * 程序初始化，將所有的服務(wù)器放入sortedMap中
     */
    static
    {
        for (int i = 0; i < servers.length; i++)
        {
            int hash = getHash(servers[i]);
            System.out.println("[" + servers[i] + "]加入集合中, 其Hash值為" + hash);
            sortedMap.put(hash, servers[i]);
        }
        System.out.println();
    } 

    /**
     * 得到應(yīng)當路由到的結(jié)點
     */
    private static String getServer(String node)
    {
        // 得到帶路由的結(jié)點的Hash值
        int hash = getHash(node);
        // 得到大于該Hash值的所有Map
        SortedMap<Integer, String> subMap =
                sortedMap.tailMap(hash);
        // 第一個Key就是順時針過去離node最近的那個結(jié)點
        Integer i = subMap.firstKey();
        // 返回對應(yīng)的服務(wù)器名稱
        return subMap.get(i);
    }

    public static void main(String[] args)
    {
        String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
        for (int i = 0; i < nodes.length; i++)
            System.out.println("[" + nodes[i] + "]的hash值為" +
                    getHash(nodes[i]) + ", 被路由到結(jié)點[" + getServer(nodes[i]) + "]");
    }
}

帶虛擬節(jié)點的一致性Hash算法

上面的hash算法可能會造成數(shù)據(jù)分布不均勻的情況，也就是 說大多數(shù)訪問請求都會集中少量幾個節(jié)點上。所以我們可以通過虛擬節(jié)點的方式解決數(shù)據(jù)分布不均的情況。

其實，就是對每一個服務(wù)器節(jié)點計算多個哈希值，在每個計算結(jié)果位置上，都放置一個虛擬 節(jié)點，并將虛擬節(jié)點映射到實際節(jié)點。比如，可以在主機名的后面增加編號，分別計算 “Node-A-01”，“Node-A-02”，“Node-B-01”，“Node-B-02”，“Node-C01”，“Node-C-02”的哈希值，于是形成 6 個虛擬節(jié)點：

增加了節(jié)點后，節(jié)點在哈希環(huán)上的分布就相對均勻了。這時，如果有訪 問請求尋址到“Node-A-01”這個虛擬節(jié)點，將被重定位到節(jié)點 A。

具體代碼實現(xiàn)如下：

/**
 * 帶虛擬節(jié)點的一致性Hash算法
 */
public class ConsistentHashingWithVirtualNode
{
    /**
     * 待添加入Hash環(huán)的服務(wù)器列表
     */
    private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
            "192.168.0.3:111", "192.168.0.4:111"};

    /**
     * 真實結(jié)點列表,考慮到服務(wù)器上線、下線的場景，即添加、刪除的場景會比較頻繁，這里使用LinkedList會更好
     */
    private static List<String> realNodes = new LinkedList<String>();

    /**
     * 虛擬節(jié)點，key表示虛擬節(jié)點的hash值，value表示虛擬節(jié)點的名稱
     */
    private static SortedMap<Integer, String> virtualNodes =
            new TreeMap<Integer, String>();

    /**
     * 虛擬節(jié)點的數(shù)目，這里寫死，為了演示需要，一個真實結(jié)點對應(yīng)5個虛擬節(jié)點
     */
    private static final int VIRTUAL_NODES = 5;

    static
    {
        // 先把原始的服務(wù)器添加到真實結(jié)點列表中
        for (int i = 0; i < servers.length; i++)
            realNodes.add(servers[i]);

        // 再添加虛擬節(jié)點，遍歷LinkedList使用foreach循環(huán)效率會比較高
        for (String str : realNodes)
        {
            for (int i = 0; i < VIRTUAL_NODES; i++)
            {
                String virtualNodeName = str + "&&VN" + String.valueOf(i);
                int hash = getHash(virtualNodeName);
                System.out.println("虛擬節(jié)點[" + virtualNodeName + "]被添加, hash值為" + hash);
                virtualNodes.put(hash, virtualNodeName);
            }
        }
        System.out.println();
    }

    /**
     * 得到應(yīng)當路由到的結(jié)點
     */
    private static String getServer(String node)
    {
        // 得到帶路由的結(jié)點的Hash值
        int hash = getHash(node);
        // 得到大于該Hash值的所有Map
        SortedMap<Integer, String> subMap =
                virtualNodes.tailMap(hash);
        // 第一個Key就是順時針過去離node最近的那個結(jié)點
        Integer i = subMap.firstKey();
        // 返回對應(yīng)的虛擬節(jié)點名稱，這里字符串稍微截取一下
        String virtualNode = subMap.get(i);
        return virtualNode.substring(0, virtualNode.indexOf("&&"));
    }

    public static void main(String[] args)
    {
        String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
        for (int i = 0; i < nodes.length; i++)
            System.out.println("[" + nodes[i] + "]的hash值為" +
                    getHash(nodes[i]) + ", 被路由到結(jié)點[" + getServer(nodes[i]) + "]");
    }
}

Gossip協(xié)議

Gossip 協(xié)議，顧名思義，就像流言蜚語一樣，利用一種隨機、帶有傳染性的方式，將信息 傳播到整個網(wǎng)絡(luò)中，并在一定時間內(nèi)，使得系統(tǒng)內(nèi)的所有節(jié)點數(shù)據(jù)一致。Gossip 協(xié)議通過上面的特性，可以保證系統(tǒng)能在極端情況下（比如集群中只有一個節(jié)點在運行）也能運行。

Gossip數(shù)據(jù)傳播方式

Gossip數(shù)據(jù)傳播方式分別有：直接郵寄（Direct Mail）、反熵（Anti-entropy）和謠言傳播 （Rumor mongering）。

直接郵寄（Direct Mail）：就是直接發(fā)送更新數(shù)據(jù)，當數(shù)據(jù)發(fā)送失敗時，將數(shù)據(jù)緩存下來，然后重傳。直接郵寄雖然實現(xiàn)起來比較容易，數(shù)據(jù)同步也很及時，但可能會因為 緩存隊列滿了而丟數(shù)據(jù)。也就是說，只采用直接郵寄是無法實現(xiàn)最終一致性的。

反熵（Anti-entropy）：反熵指的是集群中的節(jié)點，每隔段時間就隨機選擇某個其他節(jié)點，然后通過互相交換自己的 所有數(shù)據(jù)來消除兩者之間的差異，實現(xiàn)數(shù)據(jù)的最終一致性。

在實現(xiàn)反熵的時候，主要有推、拉和推拉三種方式。推方式，就是將自己的所有副本數(shù)據(jù)，推給對方，修復(fù)對方副本中的熵，拉方式，就是拉取對方的所有副本數(shù)據(jù)，修復(fù)自己副本中的熵。

謠言傳播 （Rumor mongering）：指的是當一個節(jié)點有了新數(shù)據(jù)后，這個節(jié)點變成活躍狀態(tài)，并周期性地聯(lián)系其他節(jié)點向其發(fā)送新數(shù)據(jù)，直到所有的節(jié)點都存儲了該新數(shù)據(jù)。由于謠言傳播非常具有傳染性，它適合動態(tài)變化的分布式系統(tǒng)

Quorum NWR算法

Quorum NWR 中有三個要素，N、W、R。

N 表示副本數(shù)，又叫做復(fù)制因子（Replication Factor）。也就是說，N 表示集群中同一份 數(shù)據(jù)有多少個副本，就像下圖的樣子：

在這個三節(jié)點的集群中，DATA-1 有 2 個副本，DATA-2 有 3 個副 本，DATA-3 有 1 個副本。也就是說，副本數(shù)可以不等于節(jié)點數(shù)，不同的數(shù)據(jù)可以有不同 的副本數(shù)。

W，又稱寫一致性級別（Write Consistency Level），表示成功完成 W 個副本更新。

R，又稱讀一致性級別（Read Consistency Level），表示讀取一個數(shù)據(jù)對象時需要讀 R 個副本。

通過 Quorum NWR，你可以自定義一致性級別，通過臨時調(diào)整寫入或者查詢的方式，當 W + R > N 時，就可以實現(xiàn)強一致性了。

所以假如要讀取節(jié)點B，我們再假設(shè)W(2) + R(2) > N(3)這個公式，也就是當寫兩個節(jié)點，讀的時候也同時讀取兩個節(jié)點，那么讀取數(shù)據(jù)的時候肯定是讀取返回給客戶端肯定是最新的那份數(shù)據(jù)。

關(guān)于 NWR 需要你注意的是，N、W、R 值的不同組合，會產(chǎn)生不同的一致性效 果，具體來說，有這么兩種效果：

當 W + R > N 的時候，對于客戶端來講，整個系統(tǒng)能保證強一致性，一定能返回更新后的那份數(shù)據(jù)。當 W + R < N 的時候，對于客戶端來講，整個系統(tǒng)只能保證最終一致性，可能會返回舊數(shù)據(jù)。

PBFT算法

PBFT 算法非常實用，是一種能在實際場景中落地的拜占庭容錯算法。

我們從一個例子入手，看看PBFT 算法的具體實現(xiàn)：

假設(shè)蘇秦再一次帶隊抗秦，這一天，蘇秦和 4 個國家的 4 位將軍趙、魏、韓、楚商量軍機要事，結(jié)果剛商量完沒多久蘇秦就接到了情報，情報上寫道：聯(lián)軍中可能存在一個叛徒。這 時，蘇秦要如何下發(fā)作戰(zhàn)指令，保證忠將們正確、一致地執(zhí)行下發(fā)的作戰(zhàn)指令，而不是被叛徒干擾呢？

需要注意的是，所有的消息都是簽名消息，也就是說，消息發(fā)送者的身份和消息內(nèi)容都是 無法偽造和篡改的（比如，楚無法偽造一個假裝來自趙的消息）。

首先，蘇秦聯(lián)系趙，向趙發(fā)送包含作戰(zhàn)指令“進攻”的請求（就像下圖的樣子）。

當趙接收到蘇秦的請求之后，會執(zhí)行三階段協(xié)議（Three-phase protocol）。

趙將進入預(yù)準備（Pre-prepare）階段，構(gòu)造包含作戰(zhàn)指令的預(yù)準備消息，并廣播給其他 將軍（魏、韓、楚）。

因為魏、韓、楚，收到消息后，不能確認自己接收到指令和其他人接收到的指令是相同的。所以需要進入下一個階段。

接收到預(yù)準備消息之后，魏、韓、楚將進入準備（Prepare）階段，并分別廣播包含作戰(zhàn) 指令的準備消息給其他將軍。

比如，魏廣播準備消息給趙、韓、楚（如圖所示）。為了 方便演示，我們假設(shè)叛徒楚想通過不發(fā)送消息，來干擾共識協(xié)商（你能看到，圖中的楚 是沒有發(fā)送消息的）。

因為魏不能確認趙、韓、楚是否收到了 2f（這里的 2f 包括自己，其中 f 為叛徒數(shù)，在我的演示中是 1） 個一致的包含作戰(zhàn)指令的準備消 息。所以需要進入下一個階段Commit。

進入提交階段后，各將軍分別廣播提交消息給其他將軍，也就是告訴其他將軍，我已經(jīng)準備好了，可以執(zhí)行指令了。

最后，當某個將軍收到 2f + 1 個驗證通過的提交消息后，大部分的將軍們已經(jīng)達成共識，這時可以執(zhí)行作戰(zhàn)指 令了，那么該將軍將執(zhí)行蘇秦的作戰(zhàn)指令，執(zhí)行完畢后發(fā)送執(zhí)行成功的消息給蘇秦。

最后，當蘇秦收到 f+1 個相同的響應(yīng)（Reply）消息時，說明各位將軍們已經(jīng)就作戰(zhàn)指令達 成了共識，并執(zhí)行了作戰(zhàn)指令。

在上面的這個例子中：

可以將趙、魏、韓、楚理解為分布式系統(tǒng)的四個節(jié)點，其中趙是主節(jié)點（Primary node），魏、韓、楚是從節(jié)點（Secondary node）；

將蘇秦理解為業(yè)務(wù)，也就是客戶端；

將消息理解為網(wǎng)絡(luò)消息；

將作戰(zhàn)指令“進攻”，理解成客戶端提議的值，也就是希望被各節(jié)點達成共識，并提交 給狀態(tài)機的值。

最終的共識是否達成，客戶端是會做判斷的，如果客戶端在指定時間內(nèi)未 收到請求對應(yīng)的 f + 1 相同響應(yīng)，就認為集群出故障了，共識未達成，客戶端會重新發(fā)送請 求。

PBFT 算法通過視圖變更（View Change）的方式，來處理主節(jié)點作 惡，當發(fā)現(xiàn)主節(jié)點在作惡時，會以“輪流上崗”方式，推舉新的主節(jié)點。感興趣的可以自己去查閱。

相比 Raft 算法完全不適應(yīng)有人作惡的場景，PBFT 算法能容忍 (n 1)/3 個惡意節(jié)點 (也可以是故障節(jié)點)。另外，相比 PoW 算法，PBFT 的優(yōu)點是不消耗算 力。PBFT 算法是O(n ^ 2) 的消息復(fù)雜度的算法，所以以及隨著消息數(shù) 的增加，網(wǎng)絡(luò)時延對系統(tǒng)運行的影響也會越大，這些都限制了運行 PBFT 算法的分布式系統(tǒng) 的規(guī)模，也決定了 PBFT 算法適用于中小型分布式系統(tǒng)。

PoW算法

工作量證明 (Proof Of Work，簡稱 PoW)，就是一份證明，用 來確認你做過一定量的工作。具體來說就是，客戶端需要做一定難度的工作才能得出一個結(jié)果，驗 證方卻很容易通過結(jié)果來檢查出客戶端是不是做了相應(yīng)的工作。

具體的工作量證明過程，就像下圖中的樣子：

所以工作量證明通常用于區(qū)塊鏈中，區(qū)塊鏈通過工作量證明（Proof of Work）增加了壞人作惡的成本，以此防止壞 人作惡。

工作量證明

哈希函數(shù)（Hash Function），也叫散列函數(shù)。就是說，你輸入一個任意長度的字符串，哈 希函數(shù)會計算出一個長度相同的哈希值。

在了解了什么是哈希函數(shù)之后，那么如何通過哈希函數(shù)進行哈希運算，從而證明工作量呢？

例如，我們可以給出一個工作量的要求：基于一個基本的字符串，你可以在這個字 符串后面添加一個整數(shù)值，然后對變更后（添加整數(shù)值) 的字符串進行 SHA256 哈希運 算，如果運算后得到的哈希值（16 進制形式）是以"0000"開頭的，就驗證通過。

為了達到 這個工作量證明的目標，我們需要不停地遞增整數(shù)值，一個一個試，對得到的新字符串進行 SHA256 哈希運算。

通過這個示例你可以看到，工作量證明是通過執(zhí)行哈希運算，經(jīng)過一段時間的計算后，得到 符合條件的哈希值。也就是說，可以通過這個哈希值，來證明我們的工作量。

區(qū)塊鏈如何實現(xiàn) PoW 算法的？

首先看看什么是區(qū)塊鏈：

區(qū)塊鏈的區(qū)塊，是由區(qū)塊頭、區(qū)塊體 2 部分組成的：

• 區(qū)塊頭（Block Head）：區(qū)塊頭主要由上一個區(qū)塊的哈希值、區(qū)塊體的哈希值、4 字節(jié) 的隨機數(shù)（nonce）等組成的。
• 區(qū)塊體（Block Body）：區(qū)塊包含的交易數(shù)據(jù)，其中的第一筆交易是 Coinbase 交易， 這是一筆激勵礦工的特殊交易。

在區(qū)塊鏈中，擁有 80 字節(jié)固定長度的區(qū)塊頭，就是用于區(qū)塊鏈工作量證明的哈希運算中輸 入字符串，而且通過雙重 SHA256 哈希運算（也就是對 SHA256 哈希運算的結(jié)果，再執(zhí)行 一次哈希運算），計算出的哈希值，只有小于目標值（target），才是有效的，否則哈希值 是無效的，必須重算。

所以，在區(qū)塊鏈中是通過對區(qū)塊頭執(zhí)行 SHA256 哈希運算，得到小于目標 值的哈希值，來證明自己的工作量的。

計算出符合條件的哈希值后，礦工就會把這個信息廣播給集群中所有其他節(jié)點，其他節(jié)點驗 證通過后，會將這個區(qū)塊加入到自己的區(qū)塊鏈中，最終形成一串區(qū)塊鏈，就像下圖的樣子：

所以，就是攻擊者掌握了較多的算力，能挖掘一條比原鏈更長的攻擊鏈，并將攻擊鏈 向全網(wǎng)廣播，這時呢，按照約定，節(jié)點將接受更長的鏈，也就是攻擊鏈，丟棄原鏈。就像下 圖的樣子：

ZAB協(xié)議

Zab協(xié)議 的全稱是 Zookeeper Atomic Broadcast （Zookeeper原子廣播）。Zookeeper 是通過 Zab 協(xié)議來保證分布式事務(wù)的最終一致性。ZAB 協(xié)議的最核心設(shè)計目標就是如何實現(xiàn)操作的順序性。

由于ZAB不基于狀態(tài)機，而是基于主備模式的 原子廣播協(xié)議（Atomic Broadcast），最終實現(xiàn)了操作的順序性。

主要有以下幾點原因?qū)е铝薢AB實現(xiàn)了操作的順序性：

首先，ZAB 實現(xiàn)了主備模式，也就是所有的數(shù)據(jù)都以主節(jié)點為準：

其次，ZAB 實現(xiàn)了 FIFO 隊列，保證消息處理的順序性。

最后，ZAB 還實現(xiàn)了當主節(jié)點崩潰后，只有日志最完備的節(jié)點才能當選主節(jié)點，因為日志 最完備的節(jié)點包含了所有已經(jīng)提交的日志，所以這樣就能保證提交的日志不會再改變。

作者丨luozhiyun

來源：https://www.luozhiyun.com/archives/304