> For the complete documentation index, see [llms.txt](https://joyous-x.gitbook.io/mbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://joyous-x.gitbook.io/mbook/part-algorithm/distributed_consensus_protocols.md).

# 分布式一致性协议简介

## Raft：

* leader election
  * two timeouts
    * eletction timeout
      * randomized to be between 150ms and 300ms
    * heartbeat timeout: 
      * usage: Append Entries messages
* log replication
  * client make request to leader
  * leader make log entry and log replication, expecting major votes from all clients
  * leader respone to client and accept client's request
  * leader make log replication that commit client's request
* status
  * follower ---> candidate ---> leader
    * follower become candidate when eletction timeout
    * candidate become leader when major votes
* infomations:
  * url    : <http://thesecretlivesofdata.com/raft/>
  * github: <https://github.com/benbjohnson/thesecretlivesofdata>

## Paxos：

### Basic Paxos：

* abstract
  * 强一致性
  * Proposer、Acceptor、ProposalID(以高位时间戳 + 低位机器 IP 可以保证唯一性和递增性)
* steps:
  * prepare
    * Proposer 发送 Prepare
      * 生成新的ProposalID
    * Acceptor 应答 Prepare
      * response：
        * 返回自己已经 Accept 过的提案中 ProposalID 最大的那个提案的内容，如果没有则返回空值;
        * 应答前要在本地持久化当前 Propsalid
      * promise：
        * 不再应答 Proposalid 小于等于（注意：这里是 <= ）当前请求的 PrepareRequest
        * 不再应答 Proposalid 小于（注意：这里是 < ）当前请求的 AcceptRequest
  * accept
    * Proposer 发送 Accept
      * “提案生成规则”：
        * Proposer 收集到多数派应答的 PrepareResponse 后，从中选择proposalid最大的提案内容，作为要发起 Accept 的提案，如果这个提案为空值，则可以自己随意决定提案内容。然后携带上当前 Proposalid，向 Paxos 集群的所有机器发送 AccpetRequest。
    * Acceptor 应答 Accept
      * 检查AccpetRequest不违背自己之前作出的“两个承诺”情况下，持久化当前 Proposalid 和提案内容。最后 Proposer 收集到多数派应答的 AcceptResponse 后，形成决议。
* infomations
  * <http://chuansong.me/n/2189245>
  * <https://blog.csdn.net/heiyeshuwu/article/details/42426811>

    **Fast Paxos**

    **Multi Paxos**

## Gossip:

* abstract
  * 反熵（Anti-Entropy）
  * 种子节点
  * 去中心化
  * 最终一致性（现实中存在，理论无法证明的时间点）
* weakness
  * 冗余通信
* kernel
  * 信息同步
  * Merkle tree(MT)是一个非常适合同步的数据结构
* paper
  * Efficient Reconciliation and Flow Control for Anti-Entropy Protocols

## Totem：

* abstract
  * 强一致性
* steps：
  * 通信方式
    * 当集群有节点要发起通信时，需要等待token。当拿到token后，先广播这次需要发送的数据，然后传递token来确认所有人都接收到消息。

      如果确认成功，释放token
  * 节点的加入和退出
    1. 当集群中有节点加入时，加入的节点广播一个加入信息，所有人都开始广播自己的信息，当所有人都获得同伴信息，开始由id最小的人提交一个token，交由所有节点确认。
    2. 如果都确认后，则节点正式加入，开始正常运行。
    3. 当集群有节点退出时，由于令牌环断链，触发token超时，则同样开始广播信息，然后由最小id提交token，经过确认后恢复正常。