核心解决问题

选择Leader接管写入 分布式异构网络中共同确定一个值 不存在拜占庭将军问题

基本原理

  • Leader选择

    Node 通过投票的方式，多数服从少数

Case

  • Single Node System

    客户端写入值，Node接受并更新

  • Multiple Node

    Node必然在三个状态之一

    1. Follower state
    2. Candidate state
    3. Leader state

    所有的节点开始于Follower state , Listen Leader 节点的响应。 规定时间未得到响应，成为 candidate 状态，并且发送votes(投票给自己) request 给其他的node

    其他节点进行投票。如果大多数投票给该candidate ，则该candidate 成为Leader.

    • 投票细节

      1. Node检查在当前的term内没有投票，则投票给当前的candidate
      2. Node reset lection term

      这个过程是Leader 选举。 所有的写请求被Leader接管。

如何写(Log Replication)

  1. Leader 接受到 set 5 的请求
  2. Leader 写入本地日志（Uncommited)
  3. Leader 广播到其他节点
  4. 大多数节点都写入成功
  5. Leader节点commit
  6. Leader节点通知其他节点commit

re-election

  • Leader挂了 投票可以选出Leader

  • 多节点同时选举Leader. 通过 election timeout 机制可以保证选择出Leader

网络分区问题

  • 当网络分区的时候，

    • Leader 在多节点区

      不需要重新选择，因为在少节点区，无法获得多数投票。无法产生新的Leader

    • Leader 在少节点区

      被分割的多节点区间，重新选举Leader,term增加. 当Client 的写请求到达该 Leader的时候，因为无法收到多数的commit,则导致该写无法被commit

  • 当分区恢复的时候

    当Leader 在少数节点区，系统现在有两个Leader,但是因为 少数Leader区的terms较小。无法被系统认可，因此会回滚它们未被提交的日志。 然后同步新Leader的log

关键术语

  • lection term

    当follower 转换成candidate 的时候，开始一个新的lection term

  • Timeout

    1. election timeout : follower 在等待该时间后未得到Leader的响应，则变化未candidate. 随机时间 150ms and 300ms
    2. heartbeat timeout Leader和follower 节点的心跳检测

思考

分布式系统中达成共识需要选择一个值。引入选举随机时间的目的是为了解决活锁问题。可以尽快选择出一个Leader。 terms的引入可以保证多个Leader存在的时候，选择正确的Leader. 投票机制是保证共识的机制，每个节点都有投票权。所有的节点平等。