如何實現一個 Paxos

語言: CN / TW / HK

Paxos 作為一個經典的分散式一致性演算法(Consensus Algorithm),在各種教材中也被當做範例來講解。但由於其抽象性,很少有人基於樸素 Paxos 開發一致性庫,而 RAFT 則是工業界裡實現較多的一致性演算法,RAFT 的論文可以在下面參考資料中找到( In Search of an Understandable Consensus Algorithm ),RAFT 通過引入強 leader 角色,解決了 Paxos 演算法中很多工程實現難題,同時引入了日誌+狀態機的概念,將多節點同步進行了高度抽象,解決了很多問題。這裡我之所以反其道而行之,選擇 Paxos 進行實現,主要是因為:

  • Paxos 開源實現較少,經典,各種定義高度抽象(適合作為通用庫),挑戰性強
  • 正確性不依賴 leader 選舉,適合快速寫入節點切換(搶主),本實現裡,單paxos group,3節點本地迴環記憶體儲存,3節點併發寫效能16k/s,10ms leader lease優化43k/s(MBP13 2018下測試)
  • 實現限制少,擴充套件性強

本實現程式碼參考了 RAFT 中的概念以及 phxpaxos 的實現和架構設計,實現 multi-paxos 演算法,主要針對執行緒安全和模組抽象進行強化,網路、成員管理、日誌、快照、儲存以介面形式接入,演算法設計為事件驅動,僅包含標頭檔案,便於移植和擴充套件。

本文假設讀者對 Paxos 協議有一定的瞭解,並不會對 Paxos 演算法的推導證明和一些基本概念做過多講解,主要著重於 Paxos 的工程實現。如果讀者對 Paxos 演算法的推導證明感興趣可以閱讀參考資料中的相關論文資料。

有了 Paxos 可以幹什麼

Paxos 如此知名,寫了個庫可以幹些啥炫酷的事情呢?

最直觀的,你可以在 Paxos 基礎上實現一個分散式系統,它具備:

  • 強一致性,保證各個節點的資料都是一樣的,及時併發地在多個節點上做寫操作
  • 高可用性,例如3節點的 Paxos 系統,可以容忍任何一個節點掛掉,同時繼續提供服務

基於 Paxos 系統的日誌+狀態機,可以輕易實現帶狀態的高可用服務,比如一個分散式 KV 儲存系統。再結合快照+成員管理,可以讓這個服務具備線上遷移、動態新增多副本等諸多高階功能。是不是心動了呢,讓我們進入下面的演算法實現環節。

程式碼地址

Talk is cheap, show me the code.

先放程式碼倉庫連結

zpaxos github 倉庫

個人習慣將基礎類演算法庫直接寫成標頭檔案,便於後續程式碼引用和移植到其他專案中,同時可以讓編譯器充分內聯各種函式,缺點是編譯時間變慢。公開的程式碼中,為了減少額外專案引用,僅帶了個日誌庫(spdlog,同樣的 header only),單元測試寫的比較簡單,感興趣的小夥伴也可以加些更多的測試。

核心演算法目錄

測試程式碼目錄

Paxos 演算法基礎

這裡為避免翻譯造成錯誤理解,下面全部拷貝Paxos Made Simple原文作為參考

演算法目標

A consensus algorithm ensures that a single one among the proposed values is chosen

  • Only a value that has been proposed may be chosen,
  • Only a single value is chosen, and
  • A process never learns that a value has been chosen unless it actually has been.

一個最樸素的一致性演算法的目的,就是在一堆對等節點中協商出一個大家都公認的值,同時這個值是其中某個節點提出的而且在這個值確定後,能被所有節點獲知。

演算法實現

關於 Paxos 演算法的推導證明,已經有很多文章描述了,這裡我就不在贅述,畢竟本文的主要目標是 實現 一個 Paxos 庫,我們著重於程式碼的實現。

Phase 1. (prepare)

  • A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.
  • If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.

Phase 2. (accept)

  • If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.
  • If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

最基礎的流程則是這個兩輪投票,為了實現投票,我們需要對描述中的實體進行程式碼實現。

基類Cbase

base.h 定義了演算法中所需要的實體,主要包括,投票 ballot_number_t ,值 value_t ,acceptor 狀態 state_t ,角色間傳遞的訊息 message_t

struct ballot_number_t final {
    proposal_id_t proposal_id;
    node_id_t node_id;
};

struct value_t final {
    state_machine_id_t state_machine_id;
    utility::Cbuffer buffer;
};

struct state_t final {
    ballot_number_t promised, accepted;
    value_t value;
};

struct message_t final {
    enum type_e {
        noop = 0,
        prepare,
        prepare_promise,
        prepare_reject,
        accept,
        accept_accept,
        accept_reject,
        value_chosen,
        learn_ping,
        learn_pong,
        learn_request,
        learn_response
    } type;

    // Sender info.
    group_id_t group_id;
    instance_id_t instance_id;
    node_id_t node_id;

    /**
     * Following field may optional.
     */

    // As sequence number for reply.
    proposal_id_t proposal_id;

    ballot_number_t ballot;
    value_t value;

    // For learner data transmit.
    bool overload; // Used in ping & pong. This should be consider when send learn request.
    instance_id_t min_stored_instance_id; // Used in ping and pong.
    std::vector<learn_t> learn_batch;
    std::vector<Csnapshot::shared_ptr> snapshot_batch;
};

同時 base.h 定義了一個節點的基類 Cbase ,用於描述了該基礎節點的狀態、當前 log instance id、鎖等內容,同時提供一些基礎的 index 推進、訊息收發、成員判別、訊息儲存功能。下面截取了 Cbase 的部分程式碼。

template<class T>
class Cbase {
    // Const info of instance.
    const node_id_t node_id_;
    const group_id_t group_id_;
    const write_options_t default_write_options_;

    std::mutex update_lock_;
    std::atomic<instance_id_t> instance_id_;

    Cstorage &storage_;
    Ccommunication &communication_;
    CpeerManager &peer_manager_;

    bool is_voter(const instance_id_t &instance_id);
    bool is_all_peer(const instance_id_t &instance_id, const std::set<node_id_t> &node_set);
    bool is_all_voter(const instance_id_t &instance_id, const std::set<node_id_t> &node_set);
    bool is_quorum(const instance_id_t &instance_id, const std::set<node_id_t> &node_set);

    int get_min_instance_id(instance_id_t &instance_id);
    int get_max_instance_id(instance_id_t &instance_id);
    void set_instance_id(instance_id_t &instance_id);

    bool get(const instance_id_t &instance_id, state_t &state);
    bool get(const instance_id_t &instance_id, std::vector<state_t> &states);
    bool put(const instance_id_t &instance_id, const state_t &state, bool &lag);
    bool next_instance(const instance_id_t &instance_id, const value_t &chosen_value);
    bool put_and_next_instance(const instance_id_t &instance_id, const state_t &state, bool &lag);
    bool put_and_next_instance(const instance_id_t &instance_id, const std::vector<state_t> &states, bool &lag);

    bool reset_min_instance(const instance_id_t &instance_id, const state_t &state);

    bool broadcast(const message_t &msg,
                   Ccommunication::broadcast_range_e range,
                   Ccommunication::broadcast_type_e type);
    bool send(const node_id_t ⌖_id, const message_t &msg);
};

Proposer 角色 Cpropose

proposer.h 負責實現 Paxos 演算法中的 proposer 的行為,包括提出決議,處理 acceptor 回覆的訊息等。

on_prepare_reply 處理 acceptor 返回 prepare 流程的響應,相對於 Paxos 論文中的描述,這裡需要對訊息做詳細的檢測,判斷是當前上下文中需要處理的訊息後,加入到響應統計集合中,最後根據多數派原則,做出進一步判斷,是放棄還是繼續進入下一步 accept 流程。

response_set_.insert(msg.node_id);

if (message_t::prepare_promise == msg.type) {
    // Promise.
    promise_or_accept_set_.insert(msg.node_id);
    // Caution: This will move value to local variable, and never touch it again.
    update_ballot_and_value(std::forward<message_t>(msg));
} else {
    // Reject.
    reject_set_.insert(msg.node_id);
    has_rejected_ = true;
    record_other_proposal_id(msg);
}

if (base_.is_quorum(working_instance_id_, promise_or_accept_set_)) {
    // Prepare success.
    can_skip_prepare_ = true;
    accept(accept_msg);
} else if (base_.is_quorum(working_instance_id_, reject_set_) ||
            base_.is_all_voter(working_instance_id_, response_set_)) {
    // Prepare fail.
    state_ = proposer_idle;
    last_error_ = error_prepare_rejected;
    notify_idle = true;
}

on_accept_reply 處理 acceptor 返回 accept 流程的響應,這裡根據 Paxos 中描述,通過多數派原則,判斷該提案是否被最終通過,如果通過,則進入 chosen 流程,廣播確定的值。

response_set_.insert(msg.node_id);

if (message_t::accept_accept == msg.type) {
    // Accept.
    promise_or_accept_set_.insert(msg.node_id);
} else {
    // Reject.
    reject_set_.insert(msg.node_id);
    has_rejected_ = true;
    record_other_proposal_id(msg);
}

if (base_.is_quorum(working_instance_id_, promise_or_accept_set_)) {
    // Accept success.
    chosen(chosen_msg);
    chosen_value = value_;
} else if (base_.is_quorum(working_instance_id_, reject_set_) ||
            base_.is_all_voter(working_instance_id_, response_set_)) {
    // Accept fail.
    state_ = proposer_idle;
    last_error_ = error_accept_rejected;
    notify_idle = true;
}

Acceptor 角色 Cacceptor

acceptor.h 負責實現 Paxos 演算法中 acceptor 的行為,處理 proposer 的請求,同時進行持久化、推高 log instance id 等。同時 Cacceptor 還有個重要使命,就是在初始化時候,載入已有的狀態,保證 promise 的狀態以及 accept 的值。

on_prepare 對應收到 prepare 請求後的處理,針對提案投票號,決定返回訊息,及 promise 狀態持久化。

if (msg.ballot >= state_.promised) {
    // Promise.
    response.type = message_t::prepare_promise;
    if (state_.accepted) {
        response.ballot = state_.accepted;
        response.value = state_.value;
    }

    state_.promised = msg.ballot;

    auto lag = false;
    if (!persist(lag)) {
        if (lag)
            return Cbase<T>::routine_error_lag;

        return Cbase<T>::routine_write_fail;
    }
} else {
    // Reject.
    response.type = message_t::prepare_reject;
    response.ballot = state_.promised;
}

on_accept 對應處理收到的 accept 請求的處理,根據自身狀態和提案號,決定是更新當前狀態還是返回拒絕,最終將合適的 accept 狀態和 value 持久化。

if (msg.ballot >= state_.promised) {
    // Accept.
    response.type = message_t::accept_accept;

    state_.promised = msg.ballot;
    state_.accepted = msg.ballot;
    state_.value = std::move(msg.value); // Move value to local variable.

    auto lag = false;
    if (!persist(lag)) {
        if (lag)
            return Cbase<T>::routine_error_lag;
        return Cbase<T>::routine_write_fail;
    }
} else {
    // Reject.
    response.type = message_t::accept_reject;
    response.ballot = state_.promised;
}

on_chosen 是處理 proposer 廣播的對應值確定的訊息,經過判別後,會推高當前 log instance id,讓當前節點進入下一個 value 的判斷(multi-paxos 的邏輯)。

if (base_.next_instance(working_instance_id_, state_.value)) {
    chosen_instance_id = working_instance_id_;
    chosen_value = state_.value;
} else
    return Cbase<T>::routine_error_lag;

Paxos 演算法進階

Multi-Paxos

至此,我們實現了論文中兩個基本角色的基礎功能,同時也非常明顯的,這兩個角色並沒什麼用,只能確定一個固定的值,這時就需要引入 multi-paxos 演算法了。既然確定一個值沒有用,那麼,確定一系列值,就可以結合狀態機實現更加複雜的功能了。這個就是之前提到的 log instance id 了,這個是個從0開始的u64。

typedef uint64_t instance_id_t; // [0, inf)

這時很簡單就能實現一個多值的序列,每個值都使用 Paxos 的演算法進行確認。如下所示,instance_id_t 從0開始,依次遞增,proposer 通過 prepare & accept 流程依次確定值。value 是一系列操作,我們就能通過狀態機實現多節點間的強一致同步了。

instance_id_t 0 1 2 3 ... inf
value_t a=1 b=2 b=a+1 a=b+1 ...
Paxos prepareaccept prepareaccept prepareaccept prepareaccept ...

這裡不難發現,每個值的確定,都至少需要2次通訊RT(on_chosen 的訊息可以被 pipeline,並不佔用延遲)+2次磁碟IO,這個代價是相當大的。但 Paxos 文中也提出了 multi-paxos 思路。

Key to the efficiency of this approach is that, in the Paxos consensus algorithm, the value to be proposed is not chosen until phase 2. Recall that, after completing phase 1 of the proposer’s algorithm, either the value to be proposed is determined or else the proposer is free to propose any value.

簡而言之,就是:

  • value可以不僅僅是一個值,而是一個序列的值(把這些序列看成一個整套,理解為一個大值,花了多次網路進行傳輸),在複用 proposer id 的情況下,可以多次走 phase 2 accept 流程,實現序列值的提交
  • 該優化沒有打破paxos的假設及要求,因此 leader 並不是 multi-paxos 的必須項
  • 該連續流程隨時能被更高的 proposer id 打斷(理解為新值的搶佔,中斷之前的傳輸,同樣沒有打破之前值的約束,只是被剪短了)

這時候,一個理想情況是,一個節點搶佔並被認可了一個 proposer id 之後,用 accept 進行連續提交。每個值的確定精簡為1次通訊RT+1次磁碟IO,也就是多節點資料同步的最優代價。

instance_id_t 0 1 2 3 ... inf
value_t a=1 b=2 b=a+1 a=b+1 ...
Paxos prepareaccept accept accept accept ...

同時,我們在實現的基礎上可以引入一些機制,加快某些不必要的流程,進行效能的優化。

  • proposer.h 中使用 can_skip_prepare 和 has_rejected 判斷是否跳過可以 prepare 流程以及在被拒後(任何其他節點的 proposer 搶佔更高 proposer id)退回到2階段流程
  • 雖然多個節點之間搶佔寫入並不會帶來正確性問題,但多次搶佔導致沒有任何節點能長期進行連續 accept 優化,這裡引入了 leader_manager.h ,在 accept 後,無腦拒絕任何其他節點的 prepare 一段時間,讓 accept 成功的節點能持續獨佔 acceptor 一段時間,可以在高衝突的場景下,在時間視窗中完成連續 accept 提交。

learner 角色

learner 用於快速學習已確定的 log instance

To learn that a value has been chosen, a learner must find out that a proposal has been accepted by a majority of acceptors. The obvious algorithm is to have each acceptor, whenever it accepts a proposal, respond to all learners, sending them the proposal. This allows learners to find out about a chosen value as soon as possible, but it requires each acceptor to respond to each learner—a number of responses equal to the product of the number of acceptors and the number of learners.

論文中的方法是詢問所有 acceptor,確定多數派的value,這裡我們通過 proposer 的 on_chosen 廣播 proposer id,讓所有其他節點知道哪個值已經被確定,快速推升 log instance id,也有助於節點知道哪些值可以被傳遞到狀態機進行回放。 learner.h 通過 ping 包的形式,瞭解各個對等節點的被確定的 log instance id,選擇合適的節點進行快速學習,實際工程中會根據落後程度和 log 被裁剪的情況,選擇通過 log 還是 snapshot 的方式進行學習。

網路、成員、日誌、狀態機外掛化

根據Paxos Made Live 中的描述,實現正確的 Paxos 的難度不僅在於實現標準 Paxos 演算法,更在於其訊息傳輸和儲存可靠的假設(非拜占庭錯誤),quorum準確判斷(成員變更)等。解決這個問題的方式是,使用介面將這部分同核心演算法分離開來,交給更專業的人或庫去解決,而我們僅專精於當前的演算法、優化和排程(讓庫成為無狀態的)。同時這種分離的做法,可以讓 Paxos 工作在已有的儲存、網路系統之上,避免額外引入的儲存或網路帶來冗餘、影響效能。

因此所有非 Paxos 演算法的假設和實現,都通過介面的方式接入到核心演算法中。包括 儲存通訊成員管理狀態機和快照 。當然為了測試,程式碼中提供了最簡單的基於佇列的 通訊 ,可以模擬隨機延遲、亂序、丟包等非拜占庭錯誤, 記憶體儲存 。後面附錄會附上 RocksDB 實現的儲存、支援變更的成員管理+成員狀態機+快照實現以及基於 asio 的 TCP&UDP 混合的通訊系統。

單 Paxos Group 角色融合 Cinstance

proposer acceptor learner 三角色齊全了,下面就需要一個管理物件把他們融合到一起,形成一個 Paxos Group 了,這裡我們使用的是 instance.h 這個類 Cinstance,通過模板的方式實現0損耗的介面,規避虛擬函式的呼叫代價,將三個角色以及處理 log instance 推進、通訊、儲存和狀態機的 Cbase 完全連線起來。為了外部呼叫方便,Cinstance 也提供了帶流控的阻塞介面,給定各種超時引數,向 Paxos Group 中提交一個值,在成功或超時後返回。為了讓角色直接充分解耦,所有涉及到角色狀態流轉的介面都暴露出來,以回撥的方式在 Cinstance 中處理,也能直觀地在一個程式碼上下文中處理這些互動資訊,儘可能減少邏輯bug。

void synced_value_done(const instance_id_t &instance_id, const value_t &value);

void synced_reset_instance(const instance_id_t &from, const instance_id_t &to);

Cbase::routine_status_e self_prepare(const message_t &msg);

Cbase::routine_status_e self_chosen(const message_t &msg);

void on_proposer_idle();

void on_proposer_final(const instance_id_t &instance_id, value_t &&value);

void value_chosen(const instance_id_t &instance_id, value_t &&value);

void value_learnt(const instance_id_t &instance_id, value_t &&value);

void learn_done();

Cbase::routine_status_e take_snapshots(const instance_id_t &peer_instance_id, std::vector<Csnapshot::shared_ptr> &snapshots);

Cbase::routine_status_e load_snapshots(const std::vector<Csnapshot::shared_ptr> &snapshots);

多執行緒化

這裡的實現主要是工程上的實現,這裡只提下基本思路,具體實現可以參考程式碼。

  • Paxos 演算法成功地將幾個角色完全分解開來,除了 log instance 推進需要嚴格順序進行,其他角色都可以在任意 log instance id 上進行,角色內部狀態機通過鎖控制
  • 通過在持久化和推進 log instance id 的時候,短暫持有全域性鎖,儘可能減少序列化點,同時通過原子變數快速判斷當前角色是否落後
  • 完全事件推動模型(包括超時和狀態變更)
  • 超時及任務佇列 timer_work_queue.h
  • 可重置超時機制 resetable_timeout_notify.h

log+狀態機+snapshot(日誌壓縮)

序列化的值已經就緒了,實現完整的帶狀態的應用就差狀態機了,RAFT 裡面已經有了完整敘述,這裡我們同樣把設計為日誌+狀態機的實現,為了 learner 快速學習,同樣提供了快照的介面。進一步的,因為有了快照,我們就不需要保留完整的日誌了,通過快照就能快速重放到對應的 log instance id,實現快速學習。同樣日誌、狀態機、快照都採用介面方式實現,參考 state_machine.h 部分程式碼,介面中預留了很多輔助類操作介面,便於實現無阻塞的快照獲取和應用。

class Csnapshot {
public:

    // Get global state machine id which identify myself, and this should be **unique**.
    virtual state_machine_id_t get_id() const = 0;

    // The snapshot represent the state machine which run to this id(not included).
    virtual const instance_id_t &get_next_instance_id() const = 0;
};

class CstateMachine {
public:

    // Get global state machine id which identify myself, and this should be **unique**.
    virtual state_machine_id_t get_id() const = 0;

    // This will be invoked sequentially by instance id,
    // and this callback should have ability to handle duplicate id caused by replay.
    // Should throw exception if get unexpected instance id.
    // If instance's chosen value is not for this SM, empty value will given.
    virtual void consume_sequentially(const instance_id_t &instance_id, const utility::Cslice &value) = 0;

    // Supply buffer which can move.
    virtual void consume_sequentially(const instance_id_t &instance_id, utility::Cbuffer &&value) {
        consume_sequentially(instance_id, value.slice());
    }

    // Return instance id which will execute on next round.
    // Can smaller than actual value only in concurrent with consuming, but **never** larger than real value.
    virtual instance_id_t get_next_execute_id() = 0;

    // Return smallest instance id which not been persisted.
    // Can smaller than actual value only in concurrent with consuming, but **never** larger than real value.
    virtual instance_id_t get_next_persist_id() = 0;

    // The get_next_instance_id of snapshot returned should >= get_next_persist_id().
    virtual int take_snapshot(Csnapshot::shared_ptr &snapshot) = 0;

    // next_persist_id should larger or equal to snapshot after successfully load.
    virtual int load_snapshot(const Csnapshot::shared_ptr &snapshot) = 0;
};

其次為了實現更高階的功能,演算法提供了2套 value chosen 回撥介面,一個是在 log instance id 推進的臨界區內的回撥 synced_value_done ,另一個是非同步的回撥 value_chosen ,分別適用於和 log instance id 強相關的狀態控制(例如成員管理,後面會提到),以及普通的狀態機。非同步的回撥是在臨界區之外的,佔用事件驅動執行緒,但不會影響 Paxos 演算法總體吞吐量,同時也有個同步佇列 CstateMachineBase 保證日誌應用的順序性。

成員變更

至此我們實現了大部分對分散式一致性庫的需求,但還有個常見的重要需求:在實用化的分散式一致性庫中實現動態成員管理。實現這個功能主要有以下幾種方式:

  • 停機,手動變更配置檔案
  • RAFT 的實現 joint consensus

joint consensus (two-phase approach)

  • Log entries are replicated to all servers in both configurations.
  • Any server from either configuration may serve as leader.
  • Agreement (for elections and entry commitment) requires separate majorities from both the old and new configurations.
  • 一步成員變更,將成員管理問題轉換為 Paxos 處理的一致性問題(本庫使用的方法)

之所以 RAFT 不採用一步變更,是因為一步變更會在中間狀態中出現不交叉的多組 quorum,如下面樣例中的場景,需要將C節點替換為D節點,在 log instance id 3上,由於延遲等原因,A和C節點還沒有進行成員變更,還認為成員是ABC,AC作為 quorum 進而 accept 了一個 value,而對於知道最新成員為ABC的BD兩個節點,仍可以作為 quorum 去 accept 另外一個值,這就導致了 Paxos 演算法失效。

這個問題的本質在於,在進行共識演算法時,成員不是原子的變化的,而是在各個節點間存在中間狀態的。將成員變更操作引入log中,並通過狀態機在各個節點重放,通過多版本成員控制對不同 log instance id 的情況使用正確的成員組,即可解決這個問題。此時成員變更被整合到 Paxos 演算法中,併成為一個原子的變更出現。

不難發現,在通訊和成員管理介面中也傳遞了 group id(多 Paxos Group)和 log instance id 的引數(通訊介面在 message 中獲取),便於在實現的時候相容動態成員變更的管理。

class Ccommunication {
public:

    virtual int send(const node_id_t ⌖_id, const message_t &message) = 0;

    enum broadcast_range_e {
        broadcast_voter = 0,
        broadcast_follower,
        broadcast_all,
    };

    enum broadcast_type_e {
        broadcast_self_first = 0,
        broadcast_self_last,
        broadcast_no_self,
    };

    virtual int broadcast(const message_t &message, broadcast_range_e range, broadcast_type_e type) = 0;
};

class CpeerManager {
public:

    virtual bool is_voter(const group_id_t &group_id, const instance_id_t &instance_id,
                          const node_id_t &node_id) = 0;

    virtual bool is_all_peer(const group_id_t &group_id, const instance_id_t &instance_id,
                             const std::set<node_id_t> &node_set) = 0;

    virtual bool is_all_voter(const group_id_t &group_id, const instance_id_t &instance_id,
                              const std::set<node_id_t> &node_set) = 0;

    virtual bool is_quorum(const group_id_t &group_id, const instance_id_t &instance_id,
                           const std::set<node_id_t> &node_set) = 0;
};

總結

至此一個完整的、模組化的 Paxos 庫已經實現了,可以完成大部分我們期望的能力,也具備極大的擴充套件能力。當然在實現這個庫的時候,也存在取捨,本庫僅實現了一個 Paxos Group,只能序列依次確定一個值,這是為了具備快速搶主的能力,捨棄了 pipeline 的能力(pipeline快速搶佔的空洞對狀態機實現很不友好)。當然為了實現 pipeline 可以通過多 GROUP 實現,效率也不會有太大差別。更多的優化比如儲存的日誌和狀態機的混合持久化、訊息的 GROUPING(BATCHING) 等都可以在提供的介面上隨意發揮。

這裡提供幾個擴充套件程式碼樣例作為參考,包括

參考資料

原文連結

本文為阿里雲原創內容,未經允許不得轉載。