{"id":10005995,"date":"2022-07-22T11:59:05","date_gmt":"2022-07-22T03:59:05","guid":{"rendered":"https:\/\/ityet.com\/?p=10005995"},"modified":"2022-07-22T11:59:05","modified_gmt":"2022-07-22T03:59:05","slug":"%e5%a6%82%e4%bd%95%e5%ae%9e%e7%8e%b0%e4%b8%80%e4%b8%aa-paxos","status":"publish","type":"post","link":"https:\/\/itmax.cn\/?p=10005995","title":{"rendered":"\u5982\u4f55\u5b9e\u73b0\u4e00\u4e2a Paxos"},"content":{"rendered":"

\u7b80\u4ecb\uff1a\u00a0Paxos \u4f5c\u4e3a\u4e00\u4e2a\u7ecf\u5178\u7684\u5206\u5e03\u5f0f\u4e00\u81f4\u6027\u7b97\u6cd5(Consensus Algorithm)\uff0c\u5728\u5404\u79cd\u6559\u6750\u4e2d\u4e5f\u88ab\u5f53\u505a\u8303\u4f8b\u6765\u8bb2\u89e3\u3002\u4f46\u7531\u4e8e\u5176\u62bd\u8c61\u6027\uff0c\u5f88\u5c11\u6709\u4eba\u57fa\u4e8e\u6734\u7d20 Paxos \u5f00\u53d1\u4e00\u81f4\u6027\u5e93\uff0c\u672c\u6587\u4ecb\u7ecd\u7684\u5b9e\u73b0\u4ee3\u7801\u53c2\u8003\u4e86 RAFT \u4e2d\u7684\u6982\u5ff5\u4ee5\u53ca phxpaxos \u7684\u5b9e\u73b0\u548c\u67b6\u6784\u8bbe\u8ba1\uff0c\u5b9e\u73b0 multi-paxos \u7b97\u6cd5\uff0c\u4e3b\u8981\u9488\u5bf9\u7ebf\u7a0b\u5b89\u5168\u548c\u6a21\u5757\u62bd\u8c61\u8fdb\u884c\u5f3a\u5316\uff0c\u7f51\u7edc\u3001\u6210\u5458\u7ba1\u7406\u3001\u65e5\u5fd7\u3001\u5feb\u7167\u3001\u5b58\u50a8\u4ee5\u63a5\u53e3\u5f62\u5f0f\u63a5\u5165\uff0c\u7b97\u6cd5\u8bbe\u8ba1\u4e3a\u4e8b\u4ef6\u9a71\u52a8\uff0c\u4ec5\u5305\u542b\u5934\u6587\u4ef6\uff0c\u4fbf\u4e8e\u79fb\u690d\u548c\u6269\u5c55\u3002Paxos \u4f5c\u4e3a\u4e00\u4e2a\u7ecf\u5178\u7684\u5206\u5e03\u5f0f\u4e00\u81f4\u6027\u7b97\u6cd5(Consensus Algorithm)\uff0c\u5728\u5404\u79cd\u6559\u6750\u4e2d\u4e5f\u88ab\u5f53\u505a\u8303\u4f8b\u6765\u8bb2\u89e3\u3002\u4f46\u7531\u4e8e\u5176\u62bd\u8c61\u6027\uff0c\u5f88\u5c11\u6709\u4eba\u57fa\u4e8e\u6734\u7d20 Paxos \u5f00\u53d1\u4e00\u81f4\u6027\u5e93\uff0c\u800c RAFT \u5219\u662f\u5de5\u4e1a\u754c\u91cc\u5b9e\u73b0\u8f83\u591a\u7684\u4e00\u81f4\u6027\u7b97\u6cd5\uff0cRAFT \u7684\u8bba\u6587\u53ef\u4ee5\u5728\u4e0b\u9762\u53c2\u8003\u8d44\u6599\u4e2d\u627e\u5230\uff08In Search of an Understandable Consensus Algorithm\uff09\uff0cRAFT \u901a\u8fc7\u5f15\u5165\u5f3a leader \u89d2\u8272\uff0c\u89e3\u51b3\u4e86 Paxos \u7b97\u6cd5\u4e2d\u5f88\u591a\u5de5\u7a0b\u5b9e\u73b0\u96be\u9898\uff0c\u540c\u65f6\u5f15\u5165\u4e86\u65e5\u5fd7+\u72b6\u6001\u673a\u7684\u6982\u5ff5\uff0c\u5c06\u591a\u8282\u70b9\u540c\u6b65\u8fdb\u884c\u4e86\u9ad8\u5ea6\u62bd\u8c61\uff0c\u89e3\u51b3\u4e86\u5f88\u591a\u95ee\u9898\u3002\u8fd9\u91cc\u6211\u4e4b\u6240\u4ee5\u53cd\u5176\u9053\u800c\u884c\u4e4b\uff0c\u9009\u62e9 Paxos \u8fdb\u884c\u5b9e\u73b0\uff0c\u4e3b\u8981\u662f\u56e0\u4e3a\uff1aPaxos \u5f00\u6e90\u5b9e\u73b0\u8f83\u5c11\uff0c\u7ecf\u5178\uff0c\u5404\u79cd\u5b9a\u4e49\u9ad8\u5ea6\u62bd\u8c61\uff08\u9002\u5408\u4f5c\u4e3a\u901a\u7528\u5e93\uff09\uff0c\u6311\u6218\u6027\u5f3a\u6b63\u786e\u6027\u4e0d\u4f9d\u8d56 leader \u9009\u4e3e\uff0c\u9002\u5408\u5feb\u901f\u5199\u5165\u8282\u70b9\u5207\u6362\uff08\u62a2\u4e3b\uff09\uff0c\u672c\u5b9e\u73b0\u91cc\uff0c\u5355paxos group\uff0c3\u8282\u70b9\u672c\u5730\u56de\u73af\u5185\u5b58\u5b58\u50a8\uff0c3\u8282\u70b9\u5e76\u53d1\u5199\u6027\u80fd16k\/s\uff0c10ms leader lease\u4f18\u531643k\/s\uff08MBP13 2018\u4e0b\u6d4b\u8bd5\uff09\u5b9e\u73b0\u9650\u5236\u5c11\uff0c\u6269\u5c55\u6027\u5f3a\u672c\u5b9e\u73b0\u4ee3\u7801\u53c2\u8003\u4e86 RAFT \u4e2d\u7684\u6982\u5ff5\u4ee5\u53ca phxpaxos \u7684\u5b9e\u73b0\u548c\u67b6\u6784\u8bbe\u8ba1\uff0c\u5b9e\u73b0 multi-paxos \u7b97\u6cd5\uff0c\u4e3b\u8981\u9488\u5bf9\u7ebf\u7a0b\u5b89\u5168\u548c\u6a21\u5757\u62bd\u8c61\u8fdb\u884c\u5f3a\u5316\uff0c\u7f51\u7edc\u3001\u6210\u5458\u7ba1\u7406\u3001\u65e5\u5fd7\u3001\u5feb\u7167\u3001\u5b58\u50a8\u4ee5\u63a5\u53e3\u5f62\u5f0f\u63a5\u5165\uff0c\u7b97\u6cd5\u8bbe\u8ba1\u4e3a\u4e8b\u4ef6\u9a71\u52a8\uff0c\u4ec5\u5305\u542b\u5934\u6587\u4ef6\uff0c\u4fbf\u4e8e\u79fb\u690d\u548c\u6269\u5c55\u3002\u672c\u6587\u5047\u8bbe\u8bfb\u8005\u5bf9 Paxos \u534f\u8bae\u6709\u4e00\u5b9a\u7684\u4e86\u89e3\uff0c\u5e76\u4e0d\u4f1a\u5bf9 Paxos \u7b97\u6cd5\u7684\u63a8\u5bfc\u8bc1\u660e\u548c\u4e00\u4e9b\u57fa\u672c\u6982\u5ff5\u505a\u8fc7\u591a\u8bb2\u89e3\uff0c\u4e3b\u8981\u7740\u91cd\u4e8e Paxos \u7684\u5de5\u7a0b\u5b9e\u73b0\u3002\u5982\u679c\u8bfb\u8005\u5bf9 Paxos \u7b97\u6cd5\u7684\u63a8\u5bfc\u8bc1\u660e\u611f\u5174\u8da3\u53ef\u4ee5\u9605\u8bfb\u53c2\u8003\u8d44\u6599\u4e2d\u7684\u76f8\u5173\u8bba\u6587\u8d44\u6599\u3002\u6709\u4e86 Paxos \u53ef\u4ee5\u5e72\u4ec0\u4e48Paxos \u5982\u6b64\u77e5\u540d\uff0c\u5199\u4e86\u4e2a\u5e93\u53ef\u4ee5\u5e72\u4e9b\u5565\u70ab\u9177\u7684\u4e8b\u60c5\u5462\uff1f\u6700\u76f4\u89c2\u7684\uff0c\u4f60\u53ef\u4ee5\u5728 Paxos \u57fa\u7840\u4e0a\u5b9e\u73b0\u4e00\u4e2a\u5206\u5e03\u5f0f\u7cfb\u7edf\uff0c\u5b83\u5177\u5907\uff1a\u5f3a\u4e00\u81f4\u6027\uff0c\u4fdd\u8bc1\u5404\u4e2a\u8282\u70b9\u7684\u6570\u636e\u90fd\u662f\u4e00\u6837\u7684\uff0c\u53ca\u65f6\u5e76\u53d1\u5730\u5728\u591a\u4e2a\u8282\u70b9\u4e0a\u505a\u5199\u64cd\u4f5c\u9ad8\u53ef\u7528\u6027\uff0c\u4f8b\u59823\u8282\u70b9\u7684 Paxos \u7cfb\u7edf\uff0c\u53ef\u4ee5\u5bb9\u5fcd\u4efb\u4f55\u4e00\u4e2a\u8282\u70b9\u6302\u6389\uff0c\u540c\u65f6\u7ee7\u7eed\u63d0\u4f9b\u670d\u52a1\u57fa\u4e8e Paxos \u7cfb\u7edf\u7684\u65e5\u5fd7+\u72b6\u6001\u673a\uff0c\u53ef\u4ee5\u8f7b\u6613\u5b9e\u73b0\u5e26\u72b6\u6001\u7684\u9ad8\u53ef\u7528\u670d\u52a1\uff0c\u6bd4\u5982\u4e00\u4e2a\u5206\u5e03\u5f0f KV \u5b58\u50a8\u7cfb\u7edf\u3002\u518d\u7ed3\u5408\u5feb\u7167+\u6210\u5458\u7ba1\u7406\uff0c\u53ef\u4ee5\u8ba9\u8fd9\u4e2a\u670d\u52a1\u5177\u5907\u5728\u7ebf\u8fc1\u79fb\u3001\u52a8\u6001\u6dfb\u52a0\u591a\u526f\u672c\u7b49\u8bf8\u591a\u9ad8\u7ea7\u529f\u80fd\u3002\u662f\u4e0d\u662f\u5fc3\u52a8\u4e86\u5462\uff0c\u8ba9\u6211\u4eec\u8fdb\u5165\u4e0b\u9762\u7684\u7b97\u6cd5\u5b9e\u73b0\u73af\u8282\u3002\u4ee3\u7801\u5730\u5740Talk is cheap, show me the code.\u5148\u653e\u4ee3\u7801\u4ed3\u5e93\u94fe\u63a5zpaxos github \u4ed3\u5e93\u4e2a\u4eba\u4e60\u60ef\u5c06\u57fa\u7840\u7c7b\u7b97\u6cd5\u5e93\u76f4\u63a5\u5199\u6210\u5934\u6587\u4ef6\uff0c\u4fbf\u4e8e\u540e\u7eed\u4ee3\u7801\u5f15\u7528\u548c\u79fb\u690d\u5230\u5176\u4ed6\u9879\u76ee\u4e2d\uff0c\u540c\u65f6\u53ef\u4ee5\u8ba9\u7f16\u8bd1\u5668\u5145\u5206\u5185\u8054\u5404\u79cd\u51fd\u6570\uff0c\u7f3a\u70b9\u662f\u7f16\u8bd1\u65f6\u95f4\u53d8\u6162\u3002\u516c\u5f00\u7684\u4ee3\u7801\u4e2d\uff0c\u4e3a\u4e86\u51cf\u5c11\u989d\u5916\u9879\u76ee\u5f15\u7528\uff0c\u4ec5\u5e26\u4e86\u4e2a\u65e5\u5fd7\u5e93\uff08spdlog\uff0c\u540c\u6837\u7684 header only\uff09\uff0c\u5355\u5143\u6d4b\u8bd5\u5199\u7684\u6bd4\u8f83\u7b80\u5355\uff0c\u611f\u5174\u8da3\u7684\u5c0f\u4f19\u4f34\u4e5f\u53ef\u4ee5\u52a0\u4e9b\u66f4\u591a\u7684\u6d4b\u8bd5\u3002\u6838\u5fc3\u7b97\u6cd5\u76ee\u5f55\u6d4b\u8bd5\u4ee3\u7801\u76ee\u5f55Paxos \u7b97\u6cd5\u57fa\u7840\u8fd9\u91cc\u4e3a\u907f\u514d\u7ffb\u8bd1\u9020\u6210\u9519\u8bef\u7406\u89e3\uff0c\u4e0b\u9762\u5168\u90e8\u62f7\u8d1dPaxos Made Simple\u539f\u6587\u4f5c\u4e3a\u53c2\u8003\u7b97\u6cd5\u76ee\u6807A consensus algorithm ensures that a single one among the proposed values is chosenOnly a value that has been proposed may be chosen,Only a single value is chosen, andA process never learns that a value has been chosen unless it actually has been.\u4e00\u4e2a\u6700\u6734\u7d20\u7684\u4e00\u81f4\u6027\u7b97\u6cd5\u7684\u76ee\u7684\uff0c\u5c31\u662f\u5728\u4e00\u5806\u5bf9\u7b49\u8282\u70b9\u4e2d\u534f\u5546\u51fa\u4e00\u4e2a\u5927\u5bb6\u90fd\u516c\u8ba4\u7684\u503c\uff0c\u540c\u65f6\u8fd9\u4e2a\u503c\u662f\u5176\u4e2d\u67d0\u4e2a\u8282\u70b9\u63d0\u51fa\u7684\u800c\u4e14\u5728\u8fd9\u4e2a\u503c\u786e\u5b9a\u540e\uff0c\u80fd\u88ab\u6240\u6709\u8282\u70b9\u83b7\u77e5\u3002\u7b97\u6cd5\u5b9e\u73b0\u5173\u4e8e Paxos \u7b97\u6cd5\u7684\u63a8\u5bfc\u8bc1\u660e\uff0c\u5df2\u7ecf\u6709\u5f88\u591a\u6587\u7ae0\u63cf\u8ff0\u4e86\uff0c\u8fd9\u91cc\u6211\u5c31\u4e0d\u5728\u8d58\u8ff0\uff0c\u6bd5\u7adf\u672c\u6587\u7684\u4e3b\u8981\u76ee\u6807\u662f\u5b9e\u73b0\u4e00\u4e2a Paxos \u5e93\uff0c\u6211\u4eec\u7740\u91cd\u4e8e\u4ee3\u7801\u7684\u5b9e\u73b0\u3002Phase 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.\u6700\u57fa\u7840\u7684\u6d41\u7a0b\u5219\u662f\u8fd9\u4e2a\u4e24\u8f6e\u6295\u7968\uff0c\u4e3a\u4e86\u5b9e\u73b0\u6295\u7968\uff0c\u6211\u4eec\u9700\u8981\u5bf9\u63cf\u8ff0\u4e2d\u7684\u5b9e\u4f53\u8fdb\u884c\u4ee3\u7801\u5b9e\u73b0\u3002\u57fa\u7c7bCbasebase.h\u00a0\u5b9a\u4e49\u4e86\u7b97\u6cd5\u4e2d\u6240\u9700\u8981\u7684\u5b9e\u4f53\uff0c\u4e3b\u8981\u5305\u62ec\uff0c\u6295\u7968\u00a0ballot_number_t\uff0c\u503c\u00a0value_t\uff0cacceptor \u72b6\u6001\u00a0state_t\uff0c\u89d2\u8272\u95f4\u4f20\u9012\u7684\u6d88\u606f\u00a0message_t\u3002struct ballot_number_t final {<\/p>\n

proposal_id_t proposal_id;\nnode_id_t node_id;<\/code><\/pre>\n
};<\/p>\n
struct value_t final {<\/p>\n
state_machine_id_t state_machine_id;\nutility::Cbuffer buffer;<\/code><\/pre>\n
};<\/p>\n
struct state_t final {<\/p>\n
ballot_number_t promised, accepted;\nvalue_t value;<\/code><\/pre>\n
};<\/p>\n
struct message_t final {<\/p>\n
enum type_e {\n    noop = 0,\n    prepare,\n    prepare_promise,\n    prepare_reject,\n    accept,\n    accept_accept,\n    accept_reject,\n    value_chosen,\n    learn_ping,\n    learn_pong,\n    learn_request,\n    learn_response\n} type;\n\n\/\/ Sender info.\ngroup_id_t group_id;\ninstance_id_t instance_id;\nnode_id_t node_id;\n\n\/**\n * Following field may optional.\n *\/\n\n\/\/ As sequence number for reply.\nproposal_id_t proposal_id;\n\nballot_number_t ballot;\nvalue_t value;\n\n\/\/ For learner data transmit.\nbool overload; \/\/ Used in ping & pong. This should be consider when send learn request.\ninstance_id_t min_stored_instance_id; \/\/ Used in ping and pong.\nstd::vector<learn_t> learn_batch;\nstd::vector<Csnapshot::shared_ptr> snapshot_batch;<\/code><\/pre>\n
};\u6298\u53e0 \u540c\u65f6\u00a0base.h\u00a0\u5b9a\u4e49\u4e86\u4e00\u4e2a\u8282\u70b9\u7684\u57fa\u7c7b\u00a0Cbase\uff0c\u7528\u4e8e\u63cf\u8ff0\u4e86\u8be5\u57fa\u7840\u8282\u70b9\u7684\u72b6\u6001\u3001\u5f53\u524d log instance id\u3001\u9501\u7b49\u5185\u5bb9\uff0c\u540c\u65f6\u63d0\u4f9b\u4e00\u4e9b\u57fa\u7840\u7684 index \u63a8\u8fdb\u3001\u6d88\u606f\u6536\u53d1\u3001\u6210\u5458\u5224\u522b\u3001\u6d88\u606f\u5b58\u50a8\u529f\u80fd\u3002\u4e0b\u9762\u622a\u53d6\u4e86 Cbase \u7684\u90e8\u5206\u4ee3\u7801\u3002template<class T>
class Cbase {<\/p>\n
\/\/ Const info of instance.\nconst node_id_t node_id_;\nconst group_id_t group_id_;\nconst write_options_t default_write_options_;\n\nstd::mutex update_lock_;\nstd::atomic<instance_id_t> instance_id_;\n\nCstorage &storage_;\nCcommunication &communication_;\nCpeerManager &peer_manager_;\n\nbool is_voter(const instance_id_t &instance_id);\nbool is_all_peer(const instance_id_t &instance_id, const std::set<node_id_t> &node_set);\nbool is_all_voter(const instance_id_t &instance_id, const std::set<node_id_t> &node_set);\nbool is_quorum(const instance_id_t &instance_id, const std::set<node_id_t> &node_set);\n\nint get_min_instance_id(instance_id_t &instance_id);\nint get_max_instance_id(instance_id_t &instance_id);\nvoid set_instance_id(instance_id_t &instance_id);\n\nbool get(const instance_id_t &instance_id, state_t &state);\nbool get(const instance_id_t &instance_id, std::vector<state_t> &states);\nbool put(const instance_id_t &instance_id, const state_t &state, bool &lag);\nbool next_instance(const instance_id_t &instance_id, const value_t &chosen_value);\nbool put_and_next_instance(const instance_id_t &instance_id, const state_t &state, bool &lag);\nbool put_and_next_instance(const instance_id_t &instance_id, const std::vector<state_t> &states, bool &lag);\n\nbool reset_min_instance(const instance_id_t &instance_id, const state_t &state);\n\nbool broadcast(const message_t &msg,\n               Ccommunication::broadcast_range_e range,\n               Ccommunication::broadcast_type_e type);\nbool send(const node_id_t &target_id, const message_t &msg);<\/code><\/pre>\n
};\u6298\u53e0 Proposer \u89d2\u8272 Cproposeproposer.h\u00a0\u8d1f\u8d23\u5b9e\u73b0 Paxos \u7b97\u6cd5\u4e2d\u7684 proposer \u7684\u884c\u4e3a\uff0c\u5305\u62ec\u63d0\u51fa\u51b3\u8bae\uff0c\u5904\u7406 acceptor \u56de\u590d\u7684\u6d88\u606f\u7b49\u3002on_prepare_reply\u00a0\u5904\u7406 acceptor \u8fd4\u56de prepare \u6d41\u7a0b\u7684\u54cd\u5e94\uff0c\u76f8\u5bf9\u4e8e Paxos \u8bba\u6587\u4e2d\u7684\u63cf\u8ff0\uff0c\u8fd9\u91cc\u9700\u8981\u5bf9\u6d88\u606f\u505a\u8be6\u7ec6\u7684\u68c0\u6d4b\uff0c\u5224\u65ad\u662f\u5f53\u524d\u4e0a\u4e0b\u6587\u4e2d\u9700\u8981\u5904\u7406\u7684\u6d88\u606f\u540e\uff0c\u52a0\u5165\u5230\u54cd\u5e94\u7edf\u8ba1\u96c6\u5408\u4e2d\uff0c\u6700\u540e\u6839\u636e\u591a\u6570\u6d3e\u539f\u5219\uff0c\u505a\u51fa\u8fdb\u4e00\u6b65\u5224\u65ad\uff0c\u662f\u653e\u5f03\u8fd8\u662f\u7ee7\u7eed\u8fdb\u5165\u4e0b\u4e00\u6b65 accept \u6d41\u7a0b\u3002response_set_.insert(msg.node_id);<\/p>\n
if (message_t::prepare_promise == msg.type) {<\/p>\n
\/\/ Promise.\npromise_or_accept_set_.insert(msg.node_id);\n\/\/ Caution: This will move value to local variable, and never touch it again.\nupdate_ballot_and_value(std::forward<message_t>(msg));<\/code><\/pre>\n
} else {<\/p>\n
\/\/ Reject.\nreject_set_.insert(msg.node_id);\nhas_rejected_ = true;\nrecord_other_proposal_id(msg);<\/code><\/pre>\n
}<\/p>\n
if (base_.is_quorum(working_instance_id_, promise_or_accept_set_)) {<\/p>\n
\/\/ Prepare success.\ncan_skip_prepare_ = true;\naccept(accept_msg);<\/code><\/pre>\n
} else if (base_.is_quorum(working_instance_id_, reject_set_) ||<\/p>\n
        base_.is_all_voter(working_instance_id_, response_set_)) {\n\/\/ Prepare fail.\nstate_ = proposer_idle;\nlast_error_ = error_prepare_rejected;\nnotify_idle = true;<\/code><\/pre>\n
}on_accept_reply\u00a0\u5904\u7406 acceptor \u8fd4\u56de accept \u6d41\u7a0b\u7684\u54cd\u5e94\uff0c\u8fd9\u91cc\u6839\u636e Paxos \u4e2d\u63cf\u8ff0\uff0c\u901a\u8fc7\u591a\u6570\u6d3e\u539f\u5219\uff0c\u5224\u65ad\u8be5\u63d0\u6848\u662f\u5426\u88ab\u6700\u7ec8\u901a\u8fc7\uff0c\u5982\u679c\u901a\u8fc7\uff0c\u5219\u8fdb\u5165\u00a0chosen\u00a0\u6d41\u7a0b\uff0c\u5e7f\u64ad\u786e\u5b9a\u7684\u503c\u3002response_set_.insert(msg.node_id);<\/p>\n
if (message_t::accept_accept == msg.type) {<\/p>\n
\/\/ Accept.\npromise_or_accept_set_.insert(msg.node_id);<\/code><\/pre>\n
} else {<\/p>\n
\/\/ Reject.\nreject_set_.insert(msg.node_id);\nhas_rejected_ = true;\nrecord_other_proposal_id(msg);<\/code><\/pre>\n
}<\/p>\n
if (base_.is_quorum(working_instance_id_, promise_or_accept_set_)) {<\/p>\n
\/\/ Accept success.\nchosen(chosen_msg);\nchosen_value = value_;<\/code><\/pre>\n
} else if (base_.is_quorum(working_instance_id_, reject_set_) ||<\/p>\n
        base_.is_all_voter(working_instance_id_, response_set_)) {\n\/\/ Accept fail.\nstate_ = proposer_idle;\nlast_error_ = error_accept_rejected;\nnotify_idle = true;<\/code><\/pre>\n
}Acceptor \u89d2\u8272 Cacceptoracceptor.h\u00a0\u8d1f\u8d23\u5b9e\u73b0 Paxos \u7b97\u6cd5\u4e2d acceptor \u7684\u884c\u4e3a\uff0c\u5904\u7406 proposer \u7684\u8bf7\u6c42\uff0c\u540c\u65f6\u8fdb\u884c\u6301\u4e45\u5316\u3001\u63a8\u9ad8 log instance id \u7b49\u3002\u540c\u65f6 Cacceptor \u8fd8\u6709\u4e2a\u91cd\u8981\u4f7f\u547d\uff0c\u5c31\u662f\u5728\u521d\u59cb\u5316\u65f6\u5019\uff0c\u52a0\u8f7d\u5df2\u6709\u7684\u72b6\u6001\uff0c\u4fdd\u8bc1 promise \u7684\u72b6\u6001\u4ee5\u53ca accept \u7684\u503c\u3002on_prepare\u00a0\u5bf9\u5e94\u6536\u5230 prepare \u8bf7\u6c42\u540e\u7684\u5904\u7406\uff0c\u9488\u5bf9\u63d0\u6848\u6295\u7968\u53f7\uff0c\u51b3\u5b9a\u8fd4\u56de\u6d88\u606f\uff0c\u53ca promise \u72b6\u6001\u6301\u4e45\u5316\u3002if (msg.ballot >= state_.promised) {<\/p>\n
\/\/ Promise.\nresponse.type = message_t::prepare_promise;\nif (state_.accepted) {\n    response.ballot = state_.accepted;\n    response.value = state_.value;\n}\n\nstate_.promised = msg.ballot;\n\nauto lag = false;\nif (!persist(lag)) {\n    if (lag)\n        return Cbase<T>::routine_error_lag;\n\n    return Cbase<T>::routine_write_fail;\n}<\/code><\/pre>\n
} else {<\/p>\n
\/\/ Reject.\nresponse.type = message_t::prepare_reject;\nresponse.ballot = state_.promised;<\/code><\/pre>\n
}on_accept\u00a0\u5bf9\u5e94\u5904\u7406\u6536\u5230\u7684 accept \u8bf7\u6c42\u7684\u5904\u7406\uff0c\u6839\u636e\u81ea\u8eab\u72b6\u6001\u548c\u63d0\u6848\u53f7\uff0c\u51b3\u5b9a\u662f\u66f4\u65b0\u5f53\u524d\u72b6\u6001\u8fd8\u662f\u8fd4\u56de\u62d2\u7edd\uff0c\u6700\u7ec8\u5c06\u5408\u9002\u7684 accept \u72b6\u6001\u548c value \u6301\u4e45\u5316\u3002if (msg.ballot >= state_.promised) {<\/p>\n
\/\/ Accept.\nresponse.type = message_t::accept_accept;\n\nstate_.promised = msg.ballot;\nstate_.accepted = msg.ballot;\nstate_.value = std::move(msg.value); \/\/ Move value to local variable.\n\nauto lag = false;\nif (!persist(lag)) {\n    if (lag)\n        return Cbase<T>::routine_error_lag;\n    return Cbase<T>::routine_write_fail;\n}<\/code><\/pre>\n
} else {<\/p>\n
\/\/ Reject.\nresponse.type = message_t::accept_reject;\nresponse.ballot = state_.promised;<\/code><\/pre>\n
}on_chosen\u00a0\u662f\u5904\u7406 proposer \u5e7f\u64ad\u7684\u5bf9\u5e94\u503c\u786e\u5b9a\u7684\u6d88\u606f\uff0c\u7ecf\u8fc7\u5224\u522b\u540e\uff0c\u4f1a\u63a8\u9ad8\u5f53\u524d log instance id\uff0c\u8ba9\u5f53\u524d\u8282\u70b9\u8fdb\u5165\u4e0b\u4e00\u4e2a value \u7684\u5224\u65ad\uff08multi-paxos \u7684\u903b\u8f91\uff09\u3002if (base_.next_instance(working_instance_id_, state_.value)) {<\/p>\n
chosen_instance_id = working_instance_id_;\nchosen_value = state_.value;<\/code><\/pre>\n
} else<\/p>\n
return Cbase<T>::routine_error_lag;Paxos \u7b97\u6cd5\u8fdb\u9636Multi-Paxos\u81f3\u6b64\uff0c\u6211\u4eec\u5b9e\u73b0\u4e86\u8bba\u6587\u4e2d\u4e24\u4e2a\u57fa\u672c\u89d2\u8272\u7684\u57fa\u7840\u529f\u80fd\uff0c\u540c\u65f6\u4e5f\u975e\u5e38\u660e\u663e\u7684\uff0c\u8fd9\u4e24\u4e2a\u89d2\u8272\u5e76\u6ca1\u4ec0\u4e48\u7528\uff0c\u53ea\u80fd\u786e\u5b9a\u4e00\u4e2a\u56fa\u5b9a\u7684\u503c\uff0c\u8fd9\u65f6\u5c31\u9700\u8981\u5f15\u5165 multi-paxos \u7b97\u6cd5\u4e86\u3002\u65e2\u7136\u786e\u5b9a\u4e00\u4e2a\u503c\u6ca1\u6709\u7528\uff0c\u90a3\u4e48\uff0c\u786e\u5b9a\u4e00\u7cfb\u5217\u503c\uff0c\u5c31\u53ef\u4ee5\u7ed3\u5408\u72b6\u6001\u673a\u5b9e\u73b0\u66f4\u52a0\u590d\u6742\u7684\u529f\u80fd\u4e86\u3002\u8fd9\u4e2a\u5c31\u662f\u4e4b\u524d\u63d0\u5230\u7684 log instance id \u4e86\uff0c\u8fd9\u4e2a\u662f\u4e2a\u4ece0\u5f00\u59cb\u7684u64\u3002typedef uint64_t instance_id_t; \/\/ [0, inf)\u8fd9\u65f6\u5f88\u7b80\u5355\u5c31\u80fd\u5b9e\u73b0\u4e00\u4e2a\u591a\u503c\u7684\u5e8f\u5217\uff0c\u6bcf\u4e2a\u503c\u90fd\u4f7f\u7528 Paxos \u7684\u7b97\u6cd5\u8fdb\u884c\u786e\u8ba4\u3002\u5982\u4e0b\u6240\u793a\uff0cinstance_id_t \u4ece0\u5f00\u59cb\uff0c\u4f9d\u6b21\u9012\u589e\uff0cproposer \u901a\u8fc7 prepare & accept \u6d41\u7a0b\u4f9d\u6b21\u786e\u5b9a\u503c\u3002value \u662f\u4e00\u7cfb\u5217\u64cd\u4f5c\uff0c\u6211\u4eec\u5c31\u80fd\u901a\u8fc7\u72b6\u6001\u673a\u5b9e\u73b0\u591a\u8282\u70b9\u95f4\u7684\u5f3a\u4e00\u81f4\u540c\u6b65\u4e86\u3002instance_id_t0123...infvalue_ta=1b=2b=a+1a=b+1...\u00a0Paxosprepareacceptprepareacceptprepareacceptprepareaccept...\u00a0\u8fd9\u91cc\u4e0d\u96be\u53d1\u73b0\uff0c\u6bcf\u4e2a\u503c\u7684\u786e\u5b9a\uff0c\u90fd\u81f3\u5c11\u9700\u89812\u6b21\u901a\u4fe1RT\uff08on_chosen \u7684\u6d88\u606f\u53ef\u4ee5\u88ab pipeline\uff0c\u5e76\u4e0d\u5360\u7528\u5ef6\u8fdf\uff09+2\u6b21\u78c1\u76d8IO\uff0c\u8fd9\u4e2a\u4ee3\u4ef7\u662f\u76f8\u5f53\u5927\u7684\u3002\u4f46 Paxos \u6587\u4e2d\u4e5f\u63d0\u51fa\u4e86 multi-paxos \u601d\u8def\u3002Key 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\u2019s algorithm, either the value to be proposed is determined or else the proposer is free to propose any value.\u7b80\u800c\u8a00\u4e4b\uff0c\u5c31\u662f\uff1avalue\u53ef\u4ee5\u4e0d\u4ec5\u4ec5\u662f\u4e00\u4e2a\u503c\uff0c\u800c\u662f\u4e00\u4e2a\u5e8f\u5217\u7684\u503c\uff08\u628a\u8fd9\u4e9b\u5e8f\u5217\u770b\u6210\u4e00\u4e2a\u6574\u5957\uff0c\u7406\u89e3\u4e3a\u4e00\u4e2a\u5927\u503c\uff0c\u82b1\u4e86\u591a\u6b21\u7f51\u7edc\u8fdb\u884c\u4f20\u8f93\uff09\uff0c\u5728\u590d\u7528 proposer id \u7684\u60c5\u51b5\u4e0b\uff0c\u53ef\u4ee5\u591a\u6b21\u8d70 phase 2 accept \u6d41\u7a0b\uff0c\u5b9e\u73b0\u5e8f\u5217\u503c\u7684\u63d0\u4ea4\u8be5\u4f18\u5316\u6ca1\u6709\u6253\u7834paxos\u7684\u5047\u8bbe\u53ca\u8981\u6c42\uff0c\u56e0\u6b64 leader \u5e76\u4e0d\u662f multi-paxos \u7684\u5fc5\u987b\u9879\u8be5\u8fde\u7eed\u6d41\u7a0b\u968f\u65f6\u80fd\u88ab\u66f4\u9ad8\u7684 proposer id \u6253\u65ad\uff08\u7406\u89e3\u4e3a\u65b0\u503c\u7684\u62a2\u5360\uff0c\u4e2d\u65ad\u4e4b\u524d\u7684\u4f20\u8f93\uff0c\u540c\u6837\u6ca1\u6709\u6253\u7834\u4e4b\u524d\u503c\u7684\u7ea6\u675f\uff0c\u53ea\u662f\u88ab\u526a\u77ed\u4e86\uff09\u8fd9\u65f6\u5019\uff0c\u4e00\u4e2a\u7406\u60f3\u60c5\u51b5\u662f\uff0c\u4e00\u4e2a\u8282\u70b9\u62a2\u5360\u5e76\u88ab\u8ba4\u53ef\u4e86\u4e00\u4e2a proposer id \u4e4b\u540e\uff0c\u7528 accept \u8fdb\u884c\u8fde\u7eed\u63d0\u4ea4\u3002\u6bcf\u4e2a\u503c\u7684\u786e\u5b9a\u7cbe\u7b80\u4e3a1\u6b21\u901a\u4fe1RT+1\u6b21\u78c1\u76d8IO\uff0c\u4e5f\u5c31\u662f\u591a\u8282\u70b9\u6570\u636e\u540c\u6b65\u7684\u6700\u4f18\u4ee3\u4ef7\u3002instance_id_t0123...infvalue_ta=1b=2b=a+1a=b+1...\u00a0Paxosprepareacceptacceptacceptaccept...\u00a0\u540c\u65f6\uff0c\u6211\u4eec\u5728\u5b9e\u73b0\u7684\u57fa\u7840\u4e0a\u53ef\u4ee5\u5f15\u5165\u4e00\u4e9b\u673a\u5236\uff0c\u52a0\u5feb\u67d0\u4e9b\u4e0d\u5fc5\u8981\u7684\u6d41\u7a0b\uff0c\u8fdb\u884c\u6027\u80fd\u7684\u4f18\u5316\u3002proposer.h\u00a0\u4e2d\u4f7f\u7528 can_skip_prepare \u548c has_rejected \u5224\u65ad\u662f\u5426\u8df3\u8fc7\u53ef\u4ee5 prepare \u6d41\u7a0b\u4ee5\u53ca\u5728\u88ab\u62d2\u540e\uff08\u4efb\u4f55\u5176\u4ed6\u8282\u70b9\u7684 proposer \u62a2\u5360\u66f4\u9ad8 proposer id\uff09\u9000\u56de\u52302\u9636\u6bb5\u6d41\u7a0b\u867d\u7136\u591a\u4e2a\u8282\u70b9\u4e4b\u95f4\u62a2\u5360\u5199\u5165\u5e76\u4e0d\u4f1a\u5e26\u6765\u6b63\u786e\u6027\u95ee\u9898\uff0c\u4f46\u591a\u6b21\u62a2\u5360\u5bfc\u81f4\u6ca1\u6709\u4efb\u4f55\u8282\u70b9\u80fd\u957f\u671f\u8fdb\u884c\u8fde\u7eed accept \u4f18\u5316\uff0c\u8fd9\u91cc\u5f15\u5165\u4e86\u00a0leader_manager.h\uff0c\u5728 accept \u540e\uff0c\u65e0\u8111\u62d2\u7edd\u4efb\u4f55\u5176\u4ed6\u8282\u70b9\u7684 prepare \u4e00\u6bb5\u65f6\u95f4\uff0c\u8ba9 accept \u6210\u529f\u7684\u8282\u70b9\u80fd\u6301\u7eed\u72ec\u5360 acceptor \u4e00\u6bb5\u65f6\u95f4\uff0c\u53ef\u4ee5\u5728\u9ad8\u51b2\u7a81\u7684\u573a\u666f\u4e0b\uff0c\u5728\u65f6\u95f4\u7a97\u53e3\u4e2d\u5b8c\u6210\u8fde\u7eed accept \u63d0\u4ea4\u3002learner \u89d2\u8272learner \u7528\u4e8e\u5feb\u901f\u5b66\u4e60\u5df2\u786e\u5b9a\u7684 log instanceTo 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\u2014a number of responses equal to the product of the number of acceptors and the number of learners.\u8bba\u6587\u4e2d\u7684\u65b9\u6cd5\u662f\u8be2\u95ee\u6240\u6709 acceptor\uff0c\u786e\u5b9a\u591a\u6570\u6d3e\u7684value\uff0c\u8fd9\u91cc\u6211\u4eec\u901a\u8fc7 proposer \u7684 on_chosen \u5e7f\u64ad proposer id\uff0c\u8ba9\u6240\u6709\u5176\u4ed6\u8282\u70b9\u77e5\u9053\u54ea\u4e2a\u503c\u5df2\u7ecf\u88ab\u786e\u5b9a\uff0c\u5feb\u901f\u63a8\u5347 log instance id\uff0c\u4e5f\u6709\u52a9\u4e8e\u8282\u70b9\u77e5\u9053\u54ea\u4e9b\u503c\u53ef\u4ee5\u88ab\u4f20\u9012\u5230\u72b6\u6001\u673a\u8fdb\u884c\u56de\u653e\u3002learner.h\u00a0\u901a\u8fc7 ping \u5305\u7684\u5f62\u5f0f\uff0c\u4e86\u89e3\u5404\u4e2a\u5bf9\u7b49\u8282\u70b9\u7684\u88ab\u786e\u5b9a\u7684 log instance id\uff0c\u9009\u62e9\u5408\u9002\u7684\u8282\u70b9\u8fdb\u884c\u5feb\u901f\u5b66\u4e60\uff0c\u5b9e\u9645\u5de5\u7a0b\u4e2d\u4f1a\u6839\u636e\u843d\u540e\u7a0b\u5ea6\u548c log \u88ab\u88c1\u526a\u7684\u60c5\u51b5\uff0c\u9009\u62e9\u901a\u8fc7 log \u8fd8\u662f snapshot \u7684\u65b9\u5f0f\u8fdb\u884c\u5b66\u4e60\u3002\u7f51\u7edc\u3001\u6210\u5458\u3001\u65e5\u5fd7\u3001\u72b6\u6001\u673a\u63d2\u4ef6\u5316\u6839\u636e\u00a0Paxos Made Live\u00a0\u4e2d\u7684\u63cf\u8ff0\uff0c\u5b9e\u73b0\u6b63\u786e\u7684 Paxos \u7684\u96be\u5ea6\u4e0d\u4ec5\u5728\u4e8e\u5b9e\u73b0\u6807\u51c6 Paxos \u7b97\u6cd5\uff0c\u66f4\u5728\u4e8e\u5176\u6d88\u606f\u4f20\u8f93\u548c\u5b58\u50a8\u53ef\u9760\u7684\u5047\u8bbe\uff08\u975e\u62dc\u5360\u5ead\u9519\u8bef\uff09\uff0cquorum\u51c6\u786e\u5224\u65ad\uff08\u6210\u5458\u53d8\u66f4\uff09\u7b49\u3002\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898\u7684\u65b9\u5f0f\u662f\uff0c\u4f7f\u7528\u63a5\u53e3\u5c06\u8fd9\u90e8\u5206\u540c\u6838\u5fc3\u7b97\u6cd5\u5206\u79bb\u5f00\u6765\uff0c\u4ea4\u7ed9\u66f4\u4e13\u4e1a\u7684\u4eba\u6216\u5e93\u53bb\u89e3\u51b3\uff0c\u800c\u6211\u4eec\u4ec5\u4e13\u7cbe\u4e8e\u5f53\u524d\u7684\u7b97\u6cd5\u3001\u4f18\u5316\u548c\u8c03\u5ea6\uff08\u8ba9\u5e93\u6210\u4e3a\u65e0\u72b6\u6001\u7684\uff09\u3002\u540c\u65f6\u8fd9\u79cd\u5206\u79bb\u7684\u505a\u6cd5\uff0c\u53ef\u4ee5\u8ba9 Paxos \u5de5\u4f5c\u5728\u5df2\u6709\u7684\u5b58\u50a8\u3001\u7f51\u7edc\u7cfb\u7edf\u4e4b\u4e0a\uff0c\u907f\u514d\u989d\u5916\u5f15\u5165\u7684\u5b58\u50a8\u6216\u7f51\u7edc\u5e26\u6765\u5197\u4f59\u3001\u5f71\u54cd\u6027\u80fd\u3002\u56e0\u6b64\u6240\u6709\u975e Paxos \u7b97\u6cd5\u7684\u5047\u8bbe\u548c\u5b9e\u73b0\uff0c\u90fd\u901a\u8fc7\u63a5\u53e3\u7684\u65b9\u5f0f\u63a5\u5165\u5230\u6838\u5fc3\u7b97\u6cd5\u4e2d\u3002\u5305\u62ec\u5b58\u50a8\u3001\u901a\u4fe1\u3001\u6210\u5458\u7ba1\u7406\u548c\u72b6\u6001\u673a\u548c\u5feb\u7167\u3002\u5f53\u7136\u4e3a\u4e86\u6d4b\u8bd5\uff0c\u4ee3\u7801\u4e2d\u63d0\u4f9b\u4e86\u6700\u7b80\u5355\u7684\u57fa\u4e8e\u961f\u5217\u7684\u901a\u4fe1\uff0c\u53ef\u4ee5\u6a21\u62df\u968f\u673a\u5ef6\u8fdf\u3001\u4e71\u5e8f\u3001\u4e22\u5305\u7b49\u975e\u62dc\u5360\u5ead\u9519\u8bef\uff0c\u5185\u5b58\u5b58\u50a8\u3002\u540e\u9762\u9644\u5f55\u4f1a\u9644\u4e0a RocksDB \u5b9e\u73b0\u7684\u5b58\u50a8\u3001\u652f\u6301\u53d8\u66f4\u7684\u6210\u5458\u7ba1\u7406+\u6210\u5458\u72b6\u6001\u673a+\u5feb\u7167\u5b9e\u73b0\u4ee5\u53ca\u57fa\u4e8e asio \u7684 TCP&UDP \u6df7\u5408\u7684\u901a\u4fe1\u7cfb\u7edf\u3002\u5355 Paxos Group \u89d2\u8272\u878d\u5408 Cinstanceproposer acceptor learner \u4e09\u89d2\u8272\u9f50\u5168\u4e86\uff0c\u4e0b\u9762\u5c31\u9700\u8981\u4e00\u4e2a\u7ba1\u7406\u5bf9\u8c61\u628a\u4ed6\u4eec\u878d\u5408\u5230\u4e00\u8d77\uff0c\u5f62\u6210\u4e00\u4e2a Paxos Group \u4e86\uff0c\u8fd9\u91cc\u6211\u4eec\u4f7f\u7528\u7684\u662f\u00a0instance.h\u00a0\u8fd9\u4e2a\u7c7b Cinstance\uff0c\u901a\u8fc7\u6a21\u677f\u7684\u65b9\u5f0f\u5b9e\u73b00\u635f\u8017\u7684\u63a5\u53e3\uff0c\u89c4\u907f\u865a\u51fd\u6570\u7684\u8c03\u7528\u4ee3\u4ef7\uff0c\u5c06\u4e09\u4e2a\u89d2\u8272\u4ee5\u53ca\u5904\u7406 log instance \u63a8\u8fdb\u3001\u901a\u4fe1\u3001\u5b58\u50a8\u548c\u72b6\u6001\u673a\u7684 Cbase \u5b8c\u5168\u8fde\u63a5\u8d77\u6765\u3002\u4e3a\u4e86\u5916\u90e8\u8c03\u7528\u65b9\u4fbf\uff0cCinstance \u4e5f\u63d0\u4f9b\u4e86\u5e26\u6d41\u63a7\u7684\u963b\u585e\u63a5\u53e3\uff0c\u7ed9\u5b9a\u5404\u79cd\u8d85\u65f6\u53c2\u6570\uff0c\u5411 Paxos Group \u4e2d\u63d0\u4ea4\u4e00\u4e2a\u503c\uff0c\u5728\u6210\u529f\u6216\u8d85\u65f6\u540e\u8fd4\u56de\u3002\u4e3a\u4e86\u8ba9\u89d2\u8272\u76f4\u63a5\u5145\u5206\u89e3\u8026\uff0c\u6240\u6709\u6d89\u53ca\u5230\u89d2\u8272\u72b6\u6001\u6d41\u8f6c\u7684\u63a5\u53e3\u90fd\u66b4\u9732\u51fa\u6765\uff0c\u4ee5\u56de\u8c03\u7684\u65b9\u5f0f\u5728 Cinstance \u4e2d\u5904\u7406\uff0c\u4e5f\u80fd\u76f4\u89c2\u5730\u5728\u4e00\u4e2a\u4ee3\u7801\u4e0a\u4e0b\u6587\u4e2d\u5904\u7406\u8fd9\u4e9b\u4ea4\u4e92\u4fe1\u606f\uff0c\u5c3d\u53ef\u80fd\u51cf\u5c11\u903b\u8f91bug\u3002void synced_value_done(const instance_id_t &instance_id, const value_t &value);\n<\/code><\/pre>\n
void synced_reset_instance(const instance_id_t &from, const instance_id_t &to);<\/p>\n
Cbase::routine_status_e self_prepare(const message_t &msg);<\/p>\n
Cbase::routine_status_e self_chosen(const message_t &msg);<\/p>\n
void on_proposer_idle();<\/p>\n
void on_proposer_final(const instance_id_t &instance_id, value_t &&value);<\/p>\n
void value_chosen(const instance_id_t &instance_id, value_t &&value);<\/p>\n
void value_learnt(const instance_id_t &instance_id, value_t &&value);<\/p>\n
void learn_done();<\/p>\n
Cbase::routine_status_e take_snapshots(const instance_id_t &peer_instance_id, std::vector<Csnapshot::shared_ptr> &snapshots);<\/p>\n
Cbase::routine_status_e load_snapshots(const std::vector<Csnapshot::shared_ptr> &snapshots);\u591a\u7ebf\u7a0b\u5316\u8fd9\u91cc\u7684\u5b9e\u73b0\u4e3b\u8981\u662f\u5de5\u7a0b\u4e0a\u7684\u5b9e\u73b0\uff0c\u8fd9\u91cc\u53ea\u63d0\u4e0b\u57fa\u672c\u601d\u8def\uff0c\u5177\u4f53\u5b9e\u73b0\u53ef\u4ee5\u53c2\u8003\u4ee3\u7801\u3002Paxos \u7b97\u6cd5\u6210\u529f\u5730\u5c06\u51e0\u4e2a\u89d2\u8272\u5b8c\u5168\u5206\u89e3\u5f00\u6765\uff0c\u9664\u4e86 log instance \u63a8\u8fdb\u9700\u8981\u4e25\u683c\u987a\u5e8f\u8fdb\u884c\uff0c\u5176\u4ed6\u89d2\u8272\u90fd\u53ef\u4ee5\u5728\u4efb\u610f log instance id \u4e0a\u8fdb\u884c\uff0c\u89d2\u8272\u5185\u90e8\u72b6\u6001\u673a\u901a\u8fc7\u9501\u63a7\u5236\u901a\u8fc7\u5728\u6301\u4e45\u5316\u548c\u63a8\u8fdb log instance id \u7684\u65f6\u5019\uff0c\u77ed\u6682\u6301\u6709\u5168\u5c40\u9501\uff0c\u5c3d\u53ef\u80fd\u51cf\u5c11\u4e32\u884c\u5316\u70b9\uff0c\u540c\u65f6\u901a\u8fc7\u539f\u5b50\u53d8\u91cf\u5feb\u901f\u5224\u65ad\u5f53\u524d\u89d2\u8272\u662f\u5426\u843d\u540e\u5b8c\u5168\u4e8b\u4ef6\u63a8\u52a8\u6a21\u578b\uff08\u5305\u62ec\u8d85\u65f6\u548c\u72b6\u6001\u53d8\u66f4\uff09\u8d85\u65f6\u53ca\u4efb\u52a1\u961f\u5217timer_work_queue.h\u53ef\u91cd\u7f6e\u8d85\u65f6\u673a\u5236resetable_timeout_notify.hlog+\u72b6\u6001\u673a+snapshot(\u65e5\u5fd7\u538b\u7f29)\u5e8f\u5217\u5316\u7684\u503c\u5df2\u7ecf\u5c31\u7eea\u4e86\uff0c\u5b9e\u73b0\u5b8c\u6574\u7684\u5e26\u72b6\u6001\u7684\u5e94\u7528\u5c31\u5dee\u72b6\u6001\u673a\u4e86\uff0cRAFT\u00a0\u91cc\u9762\u5df2\u7ecf\u6709\u4e86\u5b8c\u6574\u53d9\u8ff0\uff0c\u8fd9\u91cc\u6211\u4eec\u540c\u6837\u628a\u8bbe\u8ba1\u4e3a\u65e5\u5fd7+\u72b6\u6001\u673a\u7684\u5b9e\u73b0\uff0c\u4e3a\u4e86 learner \u5feb\u901f\u5b66\u4e60\uff0c\u540c\u6837\u63d0\u4f9b\u4e86\u5feb\u7167\u7684\u63a5\u53e3\u3002\u8fdb\u4e00\u6b65\u7684\uff0c\u56e0\u4e3a\u6709\u4e86\u5feb\u7167\uff0c\u6211\u4eec\u5c31\u4e0d\u9700\u8981\u4fdd\u7559\u5b8c\u6574\u7684\u65e5\u5fd7\u4e86\uff0c\u901a\u8fc7\u5feb\u7167\u5c31\u80fd\u5feb\u901f\u91cd\u653e\u5230\u5bf9\u5e94\u7684 log instance id\uff0c\u5b9e\u73b0\u5feb\u901f\u5b66\u4e60\u3002\u540c\u6837\u65e5\u5fd7\u3001\u72b6\u6001\u673a\u3001\u5feb\u7167\u90fd\u91c7\u7528\u63a5\u53e3\u65b9\u5f0f\u5b9e\u73b0\uff0c\u53c2\u8003\u00a0state_machine.h\u00a0\u90e8\u5206\u4ee3\u7801\uff0c\u63a5\u53e3\u4e2d\u9884\u7559\u4e86\u5f88\u591a\u8f85\u52a9\u7c7b\u64cd\u4f5c\u63a5\u53e3\uff0c\u4fbf\u4e8e\u5b9e\u73b0\u65e0\u963b\u585e\u7684\u5feb\u7167\u83b7\u53d6\u548c\u5e94\u7528\u3002
\"\u56fe\u7247\"
class Csnapshot {
public:<\/p>\n
\/\/ Get global state machine id which identify myself, and this should be **unique**.\nvirtual state_machine_id_t get_id() const = 0;\n\n\/\/ The snapshot represent the state machine which run to this id(not included).\nvirtual const instance_id_t &get_next_instance_id() const = 0;<\/code><\/pre>\n
};<\/p>\n
class CstateMachine {
public:<\/p>\n
\/\/ Get global state machine id which identify myself, and this should be **unique**.\nvirtual state_machine_id_t get_id() const = 0;\n\n\/\/ This will be invoked sequentially by instance id,\n\/\/ and this callback should have ability to handle duplicate id caused by replay.\n\/\/ Should throw exception if get unexpected instance id.\n\/\/ If instance's chosen value is not for this SM, empty value will given.\nvirtual void consume_sequentially(const instance_id_t &instance_id, const utility::Cslice &value) = 0;\n\n\/\/ Supply buffer which can move.\nvirtual void consume_sequentially(const instance_id_t &instance_id, utility::Cbuffer &&value) {\n    consume_sequentially(instance_id, value.slice());\n}\n\n\/\/ Return instance id which will execute on next round.\n\/\/ Can smaller than actual value only in concurrent with consuming, but **never** larger than real value.\nvirtual instance_id_t get_next_execute_id() = 0;\n\n\/\/ Return smallest instance id which not been persisted.\n\/\/ Can smaller than actual value only in concurrent with consuming, but **never** larger than real value.\nvirtual instance_id_t get_next_persist_id() = 0;\n\n\/\/ The get_next_instance_id of snapshot returned should >= get_next_persist_id().\nvirtual int take_snapshot(Csnapshot::shared_ptr &snapshot) = 0;\n\n\/\/ next_persist_id should larger or equal to snapshot after successfully load.\nvirtual int load_snapshot(const Csnapshot::shared_ptr &snapshot) = 0;<\/code><\/pre>\n
};\u6298\u53e0 \u5176\u6b21\u4e3a\u4e86\u5b9e\u73b0\u66f4\u9ad8\u7ea7\u7684\u529f\u80fd\uff0c\u7b97\u6cd5\u63d0\u4f9b\u4e862\u5957 value chosen \u56de\u8c03\u63a5\u53e3\uff0c\u4e00\u4e2a\u662f\u5728 log instance id \u63a8\u8fdb\u7684\u4e34\u754c\u533a\u5185\u7684\u56de\u8c03\u00a0synced_value_done\uff0c\u53e6\u4e00\u4e2a\u662f\u5f02\u6b65\u7684\u56de\u8c03\u00a0value_chosen\uff0c\u5206\u522b\u9002\u7528\u4e8e\u548c log instance id \u5f3a\u76f8\u5173\u7684\u72b6\u6001\u63a7\u5236\uff08\u4f8b\u5982\u6210\u5458\u7ba1\u7406\uff0c\u540e\u9762\u4f1a\u63d0\u5230\uff09\uff0c\u4ee5\u53ca\u666e\u901a\u7684\u72b6\u6001\u673a\u3002\u5f02\u6b65\u7684\u56de\u8c03\u662f\u5728\u4e34\u754c\u533a\u4e4b\u5916\u7684\uff0c\u5360\u7528\u4e8b\u4ef6\u9a71\u52a8\u7ebf\u7a0b\uff0c\u4f46\u4e0d\u4f1a\u5f71\u54cd Paxos \u7b97\u6cd5\u603b\u4f53\u541e\u5410\u91cf\uff0c\u540c\u65f6\u4e5f\u6709\u4e2a\u540c\u6b65\u961f\u5217\u00a0CstateMachineBase\u00a0\u4fdd\u8bc1\u65e5\u5fd7\u5e94\u7528\u7684\u987a\u5e8f\u6027\u3002\u6210\u5458\u53d8\u66f4\u81f3\u6b64\u6211\u4eec\u5b9e\u73b0\u4e86\u5927\u90e8\u5206\u5bf9\u5206\u5e03\u5f0f\u4e00\u81f4\u6027\u5e93\u7684\u9700\u6c42\uff0c\u4f46\u8fd8\u6709\u4e2a\u5e38\u89c1\u7684\u91cd\u8981\u9700\u6c42\uff1a\u5728\u5b9e\u7528\u5316\u7684\u5206\u5e03\u5f0f\u4e00\u81f4\u6027\u5e93\u4e2d\u5b9e\u73b0\u52a8\u6001\u6210\u5458\u7ba1\u7406\u3002\u5b9e\u73b0\u8fd9\u4e2a\u529f\u80fd\u4e3b\u8981\u6709\u4ee5\u4e0b\u51e0\u79cd\u65b9\u5f0f\uff1a\u505c\u673a\uff0c\u624b\u52a8\u53d8\u66f4\u914d\u7f6e\u6587\u4ef6RAFT\u00a0\u7684\u5b9e\u73b0 joint consensusjoint 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.\u4e00\u6b65\u6210\u5458\u53d8\u66f4\uff0c\u5c06\u6210\u5458\u7ba1\u7406\u95ee\u9898\u8f6c\u6362\u4e3a Paxos \u5904\u7406\u7684\u4e00\u81f4\u6027\u95ee\u9898\uff08\u672c\u5e93\u4f7f\u7528\u7684\u65b9\u6cd5\uff09\u4e4b\u6240\u4ee5 RAFT \u4e0d\u91c7\u7528\u4e00\u6b65\u53d8\u66f4\uff0c\u662f\u56e0\u4e3a\u4e00\u6b65\u53d8\u66f4\u4f1a\u5728\u4e2d\u95f4\u72b6\u6001\u4e2d\u51fa\u73b0\u4e0d\u4ea4\u53c9\u7684\u591a\u7ec4 quorum\uff0c\u5982\u4e0b\u9762\u6837\u4f8b\u4e2d\u7684\u573a\u666f\uff0c\u9700\u8981\u5c06C\u8282\u70b9\u66ff\u6362\u4e3aD\u8282\u70b9\uff0c\u5728 log instance id 3\u4e0a\uff0c\u7531\u4e8e\u5ef6\u8fdf\u7b49\u539f\u56e0\uff0cA\u548cC\u8282\u70b9\u8fd8\u6ca1\u6709\u8fdb\u884c\u6210\u5458\u53d8\u66f4\uff0c\u8fd8\u8ba4\u4e3a\u6210\u5458\u662fABC\uff0cAC\u4f5c\u4e3a quorum \u8fdb\u800c accept \u4e86\u4e00\u4e2a value\uff0c\u800c\u5bf9\u4e8e\u77e5\u9053\u6700\u65b0\u6210\u5458\u4e3aABC\u7684BD\u4e24\u4e2a\u8282\u70b9\uff0c\u4ecd\u53ef\u4ee5\u4f5c\u4e3a quorum \u53bb accept \u53e6\u5916\u4e00\u4e2a\u503c\uff0c\u8fd9\u5c31\u5bfc\u81f4\u4e86 Paxos \u7b97\u6cd5\u5931\u6548\u3002
\"\u56fe\u7247\"
\u8fd9\u4e2a\u95ee\u9898\u7684\u672c\u8d28\u5728\u4e8e\uff0c\u5728\u8fdb\u884c\u5171\u8bc6\u7b97\u6cd5\u65f6\uff0c\u6210\u5458\u4e0d\u662f\u539f\u5b50\u7684\u53d8\u5316\u7684\uff0c\u800c\u662f\u5728\u5404\u4e2a\u8282\u70b9\u95f4\u5b58\u5728\u4e2d\u95f4\u72b6\u6001\u7684\u3002\u5c06\u6210\u5458\u53d8\u66f4\u64cd\u4f5c\u5f15\u5165log\u4e2d\uff0c\u5e76\u901a\u8fc7\u72b6\u6001\u673a\u5728\u5404\u4e2a\u8282\u70b9\u91cd\u653e\uff0c\u901a\u8fc7\u591a\u7248\u672c\u6210\u5458\u63a7\u5236\u5bf9\u4e0d\u540c log instance id \u7684\u60c5\u51b5\u4f7f\u7528\u6b63\u786e\u7684\u6210\u5458\u7ec4\uff0c\u5373\u53ef\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898\u3002\u6b64\u65f6\u6210\u5458\u53d8\u66f4\u88ab\u6574\u5408\u5230 Paxos \u7b97\u6cd5\u4e2d\uff0c\u5e76\u6210\u4e3a\u4e00\u4e2a\u539f\u5b50\u7684\u53d8\u66f4\u51fa\u73b0\u3002
\"\u56fe\u7247\"
\u4e0d\u96be\u53d1\u73b0\uff0c\u5728\u901a\u4fe1\u548c\u6210\u5458\u7ba1\u7406\u63a5\u53e3\u4e2d\u4e5f\u4f20\u9012\u4e86 group id\uff08\u591a Paxos Group\uff09\u548c log instance id \u7684\u53c2\u6570\uff08\u901a\u4fe1\u63a5\u53e3\u5728 message \u4e2d\u83b7\u53d6\uff09\uff0c\u4fbf\u4e8e\u5728\u5b9e\u73b0\u7684\u65f6\u5019\u517c\u5bb9\u52a8\u6001\u6210\u5458\u53d8\u66f4\u7684\u7ba1\u7406\u3002class Ccommunication {
public:<\/p>\n
virtual int send(const node_id_t &target_id, const message_t &message) = 0;\n\nenum broadcast_range_e {\n    broadcast_voter = 0,\n    broadcast_follower,\n    broadcast_all,\n};\n\nenum broadcast_type_e {\n    broadcast_self_first = 0,\n    broadcast_self_last,\n    broadcast_no_self,\n};\n\nvirtual int broadcast(const message_t &message, broadcast_range_e range, broadcast_type_e type) = 0;<\/code><\/pre>\n
};<\/p>\n
class CpeerManager {
public:<\/p>\n
virtual bool is_voter(const group_id_t &group_id, const instance_id_t &instance_id,\n                      const node_id_t &node_id) = 0;\n\nvirtual bool is_all_peer(const group_id_t &group_id, const instance_id_t &instance_id,\n                         const std::set<node_id_t> &node_set) = 0;\n\nvirtual bool is_all_voter(const group_id_t &group_id, const instance_id_t &instance_id,\n                          const std::set<node_id_t> &node_set) = 0;\n\nvirtual bool is_quorum(const group_id_t &group_id, const instance_id_t &instance_id,\n                       const std::set<node_id_t> &node_set) = 0;<\/code><\/pre>\n
};\u6298\u53e0 \u603b\u7ed3\u81f3\u6b64\u4e00\u4e2a\u5b8c\u6574\u7684\u3001\u6a21\u5757\u5316\u7684 Paxos \u5e93\u5df2\u7ecf\u5b9e\u73b0\u4e86\uff0c\u53ef\u4ee5\u5b8c\u6210\u5927\u90e8\u5206\u6211\u4eec\u671f\u671b\u7684\u80fd\u529b\uff0c\u4e5f\u5177\u5907\u6781\u5927\u7684\u6269\u5c55\u80fd\u529b\u3002\u5f53\u7136\u5728\u5b9e\u73b0\u8fd9\u4e2a\u5e93\u7684\u65f6\u5019\uff0c\u4e5f\u5b58\u5728\u53d6\u820d\uff0c\u672c\u5e93\u4ec5\u5b9e\u73b0\u4e86\u4e00\u4e2a Paxos Group\uff0c\u53ea\u80fd\u4e32\u884c\u4f9d\u6b21\u786e\u5b9a\u4e00\u4e2a\u503c\uff0c\u8fd9\u662f\u4e3a\u4e86\u5177\u5907\u5feb\u901f\u62a2\u4e3b\u7684\u80fd\u529b\uff0c\u820d\u5f03\u4e86 pipeline \u7684\u80fd\u529b\uff08pipeline\u5feb\u901f\u62a2\u5360\u7684\u7a7a\u6d1e\u5bf9\u72b6\u6001\u673a\u5b9e\u73b0\u5f88\u4e0d\u53cb\u597d\uff09\u3002\u5f53\u7136\u4e3a\u4e86\u5b9e\u73b0 pipeline \u53ef\u4ee5\u901a\u8fc7\u591a GROUP \u5b9e\u73b0\uff0c\u6548\u7387\u4e5f\u4e0d\u4f1a\u6709\u592a\u5927\u5dee\u522b\u3002\u66f4\u591a\u7684\u4f18\u5316\u6bd4\u5982\u5b58\u50a8\u7684\u65e5\u5fd7\u548c\u72b6\u6001\u673a\u7684\u6df7\u5408\u6301\u4e45\u5316\u3001\u6d88\u606f\u7684 GROUPING(BATCHING) \u7b49\u90fd\u53ef\u4ee5\u5728\u63d0\u4f9b\u7684\u63a5\u53e3\u4e0a\u968f\u610f\u53d1\u6325\u3002\u8fd9\u91cc\u63d0\u4f9b\u51e0\u4e2a\u6269\u5c55\u4ee3\u7801\u6837\u4f8b\u4f5c\u4e3a\u53c2\u8003\uff0c\u5305\u62ec\u57fa\u4e8e RocksDB \u7684\u5b58\u50a8\u00a0rocks_storage.h\u57fa\u4e8e ASIO \u7684 TCP & UDP \u901a\u4fe1\u00a0asio_network.h\u57fa\u4e8e \u72b6\u6001\u673a+MVCC \u7684\u52a8\u6001\u6210\u5458\u7ba1\u7406\u00a0dynamic_peer_manager.h\u53c2\u8003\u8d44\u6599Paxos Made SimplePaxos Made Live – An Engineering PerspectiveIn Search of an Understandable Consensus Algorithmphxpaxos wikiPolarDB-X \u4e00\u81f4\u6027\u5171\u8bc6\u534f\u8bae (X-Paxos)\u6570\u636e\u5e93\u67b6\u6784\u6742\u8c08\uff08\u4e8c\uff09\u9ad8\u53ef\u7528\u4e0e\u4e00\u81f4\u6027phxpaxos\u539f\u6587\u94fe\u63a5\uff1ahttp:\/\/click.aliyun.com\/m\/100…<\/a>\u672c\u6587\u4e3a\u963f\u91cc\u4e91\u539f\u521b\u5185\u5bb9\uff0c\u672a\u7ecf\u5141\u8bb8\u4e0d\u5f97\u8f6c\u8f7d\u3002<\/p>\n
https:\/\/segmentfault.com\/a\/1190000042195170<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
\u7b80\u4ecb\uff1a\u00a0Paxos \u4f5c\u4e3a\u4e00\u4e2a\u7ecf\u5178\u7684\u5206\u5e03\u5f0f\u4e00\u81f4\u6027\u7b97\u6cd5(Consensus Algorithm)\uff0c\u5728\u5404\u79cd\u6559\u6750\u4e2d\u4e5f\u88ab […]<\/p>\n","protected":false},"author":0,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[],"tags":[],"class_list":["post-10005995","post","type-post","status-publish","format-standard","hentry"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/posts\/10005995","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"replies":[{"embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=10005995"}],"version-history":[{"count":0,"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/posts\/10005995\/revisions"}],"wp:attachment":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=10005995"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=10005995"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=10005995"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}