LeoHsiao's Notes

# 共识算法

# 2PC

：两阶段提交（two-phase commit），是 1980 年代发布的一个共识算法。

  • 流程：
    1. Voting 阶段：一个节点担任 coordinator 角色，发送一个提议（比如想 commit 一个事务）给其它节点。其它各个节点对该提议进行投票，回复一个表示同意或否决的消息。
    2. Commit 阶段：如果所有节点都投票同意，则 coordinator 执行该提议，并通知其它节点跟随该决策。
      • 如果投票不通过，则 abort 该提议。并且如果该提议已经修改了一些数据，则 rollback 到之前状态。
  • 缺点：
    • 如果 coordinator 在发送提议之后故障，则其它节点可能不知道投票结果，即该提议是被 commit 还是 abort ，导致其它节点阻塞在当前阶段，该问题称为 fail-stop 。
    • 在 Commit 阶段，coordinator 需要阻塞等待其它节点都行动完毕，才能确定该提议的执行结果。
    • 要求所有节点都投票同意，没有容错性，存在单点故障的风险。

# 3PC

：三阶段提交（three-phase commit），是 1980 年代发布的一个共识算法。

  • 流程：
    1. Voting 阶段
    2. PreCommit 阶段：如果所有节点都投票同意，则 coordinator 将投票结果发送给其它节点。其它节点收到投票结果之后，回复一个表示确认的消息。
    3. Commit 阶段：如果其它节点已确认，则 coordinator 执行该提议，并通知其它节点跟随该决策。
  • 优点：
    • 3PC 在 2PC 的基础上增加了 PreCommit 阶段，能解决 fail-stop 问题。
    • 在 Commit 阶段，coordinator 不必阻塞等待其它节点都行动完毕。
  • 缺点：
    • 发生网络分区时，3PC 依然不能达成共识。例如一半的节点收到了 PreCommit 消息，另一半的节点没收到，导致作出不同的决策。

# Paxos

：一个共识算法，于 1990 年发布。

  • 系统中一些节点担任 Proposer ，有权发出提议（Proposal）、投票。
    • 其它节点担任 Acceptor ，有权投票。
  • 一个提议需要超过半数的节点投票同意，才能通过。
    • 用公式描述：假设节点总数为 N ，要求法定成员数为 Quorum = N/2 + 1 ，其中 / 为整除运算符。当一个提议被至少 Quorum 个节点投票同意时，才能通过。
    • 这属于多数派（Majority）策略，可容忍不超过半数的节点不同意、离线。

# Raft

：一个共识算法，于 2013 年发布，在 Paxos 算法的基础上作了改进，是目前流行的共识算法。

  • 系统中有且仅有一个节点担任 Leader ，有权发出提议（Proposal）、投票。
    • 其它节点担任 Follower ，有权投票。
    • Leader 会定期发送心跳包给其它 Follower 节点。如果其它节点超过一定时长没有收到心跳包，则变为 Candidate 状态，选举一个节点担任新 Leader 。
      • 每次选出新 Leader ，就开始一个新任期，称为 Term 。
  • 每次准备修改集群数据时，Leader 会将该提议发送给所有 Follower ，等超过半数的节点同意并执行之后，才通过该提议，从而达成共识、数据一致性。
    • Quorum 必须超过半数。如果允许 Quorum 等于集群半数，甚至小于半数，则集群可能同时存在不止一个 Leader ，发生脑裂。
    • Leader 并不会等待所有节点都同意，因此属于最终一致性。
    • 每个节点都信任其它节点发来的信息，因此不能实现拜占庭容错。
  • 部署更多节点，增加 Quorum 的值，可以提高系统可用性，但是会增加每次达成共识的耗时。
    • Raft 集群应该部署奇数个节点。例如从节点总数从 3 增加到 4 ， Quorum 依然为 2 ，并不会提高可用性。
    • 至少需要部署 1 个节点，但此时没有冗余节点，存在单点故障的风险。
    • 建议部署 3 或 5 个 节点，此时允许 1 或 2 个节点故障，可用性较高。
    • 如果部署 7 个或更多节点，可用性虽然很高，但会明显增加写操作的耗时。

# Bully

：一个共识算法，与 Raft 算法相似。

  • 如果 Leader 节点故障，则由 ID 最大的一个节点担任新 Leader 。

# Gossip

：一个广播消息的协议，常用于 P2P 服务。

  • 每个节点定期散播一次消息，最多发送给 k 个节点。
    • 发送消息之后，不必确保对方接收。
    • 其它节点收到消息之后，会散播给除了源节点之外的其它节点。
  • 消息被病毒式传播，能实现最终一致性。

# PoW

：工作量证明（Proof of Work），区块链的一个共识算法。

  • 例如比特币采用基于哈希函数的 PoW 算法：
    • 以区块为单位写入数据。
    • 一些节点担任矿工，负责生成新区块，即写入数据到区块链。
      • 每个矿工节点需要进行大量哈希运算，穷举猜测下一个区块的 nonce 随机数，第一个猜出来的节点有权生成该区块，然后广播给其它节点。
      • 生成新区块的矿工，可以获得该区块产生的一定量 BTC 作为奖励。
    • 非矿工的普通节点，只能读取区块链，或者向矿工发送写入请求。
  • 可实现顺序一致性，并实现拜占庭容错。

# PoS

：权益证明（Proof of Stake），区块链的一个共识算法。

  • 例如以太坊采用 PoS 算法：
    • 一些节点质押 32 个 ETH ，获得成为验证者的资格，负责投票验证新区块是否有效。
      • 如果行为不诚实，或者没有准时验证新区块，则质押的 ETH 销毁一部分，作为惩罚。
      • 如果工作称职，则质押的 ETH 少量增加，作为奖励。
    • 每个出块周期，随机选取一个验证者来打包新区块，然后广播给其它节点。
  • 与 PoW 相比，PoS 去掉了工作量成本，大幅降低了挖矿消耗的计算机硬件、电能。