Distributed Notes

Posted on In

分布式（Distributed System）

CAP theory

  1. CAP = 一致性（Consistency），可用性（Availability），分区容错性（Partition Tolerance）。分布式系统最多满足两项
    • Consistency:
    • Availability:
    • Partition Tolerance:
  2. 在实际实现中，P特性是必须满足的，因为如果不满足P特性，发生分区错误后整个系统完全不能用，所以剩下一个特性只能选C或A
    因此，开源的分布式系统分为CP和AP系统
    • 当一套系统在发生分区故障后，客户端的任何请求都被卡死或者超时，但是，系统的每个节点总是会返回一致的数据，则这套系统就是CP系统，经典的比如Zookeeper
    • 如果一套系统发生分区故障后，客户端依然可以访问系统，但是获取的数据有的是新的数据，有的还是老数据，那么这套系统就是AP系统，经典的比如Eureka
  3. 分布式系统在运行时，大部分时间分区都是平稳的，并不会发生分区错误，因此要均衡CA之间

PACELC theory

Raft

名词

  • Log entry: 日志条目

复制状态机（Replicated state machine）

  • 复制状态机（Replicated State Machine, RSM）是分布式系统中常用的一种架构，用于确保多个节点之间的一致性，使得分布式系统能够可靠地处理请求并保持一致的状态
  • 相同初始状态 + 相同输入 = 相同结束状态
  • 在多个节点上，从相同的初始状态开始，执行相同的命令，产生相同的最终状态
  • 在Raft中，leader将客户端请求（command）封装到一个个Log Entry中，将这些log entries复制到所有follower节点，所有follower按照相同顺序应用这些command，得到相同的结束状态
  • 通过共识算法实现复制状态机，可以保证每个节点之间的状态一致

状态简化

  • 任何时刻，每一个服务器节点都会处于一个状态
  • 服务器状态：Leader，Follower，Candidate
  • Raft只考虑状态之间的切换

    alt text
  • Raft将时间分割为任意长度的任期（term），term使用连续的政府标记
  • 每一段term从一次election开始。某些情况下一次election无法选出leader，那么这个term也会正常结束，同时新的election和新的term也会很快重新开始
  • Raft保证任意一个term中，最多只有一个leader（0 & 1）

通信 Communication

  • Raft中服务器节点只用RPC通信，分为
    • RequestVote RPC(请求投票): 由candidate在election期间发起
    • AppendEntries RPC(追加条目): 由leader发起，用来复制日志和提供心跳机制
  • 服务器节点之间通信会交换当前term号，若某服务器节点的term号比其他的小，该服务器会将自身term号更新为较大值
  • 若candidate或leader发现自身term号过期，会立即回到Follower状态
  • 若节点收到包含过期任期号的request，会直接拒绝request

Leader Election

  • 心跳机制：若存在Leader，则Leader会周期性向索引Follower发送心跳（heartbeat）。若Follower在一段时间内未收到心跳，会认为系统中目前没有可用的Leader，开始进行新的Election
  • 选举过程：开始Election后，Follower首先增加自身term号，然后切换到candidate状态，投票给自己。随后并行的向其他服务器节点发送RequestVote RPC
  • 选举结果：
    • 当前节点获得超过半数选票 -> 立即切换到leader状态，并向其他节点发送heartbeat
    • 其他节点获胜 -> 收到新leader发送的心跳后，若新leader任期号不小于自身任期号，那么从candidate切换为follower状态
    • 无节点获胜 -> 每个candidate在一个随机选举超时时间（150ms ~ 300ms）后重新启动选举流程
  • 服务器集群（cluster）在刚启动时，所有节点都是follower状态，然后会有节点启动选举，变为candidate状态。经过选举会产生leader。当leader任期结束，循环往复过程

Log Replication

  • 当Leader接收到客户端的command后，会将command作为一个新的条目追加到log中
  • 每条log需要有三个信息
    • 状态机指令
    • leader的term号
    • 日志号（用于日志索引）
  • 当完成上面步骤后，Leader并行发送AppendEntries RPC给follower，follower会复制该条目。当该条目被超过半数follower复制后，leader就可以在本地执行指令并返回结果给客户端
  • 日志的两个状态：
    • committed已提交：当某个日志被复制到集群超过半数节点，当前日志就可以处于committed状态
    • applied已应用：
  • follower与leader同步：
    • follower缓慢：若某个follower未回复leader，leader会不断重发AppendEntries RPC，保证follower追上进度（即使leader已经执行命令回复客户端）
    • follower宕机：当follower崩溃后恢复，Raft的追加条目一致性检查会保证follower按顺序回复崩溃后缺失的日志
    • leader宕机：当leader宕机后恢复，可能会存在某些未提交日志（这些日志可能与当前leader不同，并且还多出当前leader）。此时，leader通过强制follower复制leader日志来解决冲突；follower中与leader冲突的日志会被覆盖（不违反一致性，因为都是未提交的日志）
  • 优点：
    • 只要过半服务器节点正常运行，Raft就可以接收，复制，应用新的日志
    • 单个缓慢follower不影响性能
    • 新的日志可以保证复制到集群中的过半节点
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      // AppendEntries RPC
      type AppendEntriesRequest struct{
          term            int     // 自身当前任期号
          leaderId        int     // leader ID
          prevLogIndex    int     // 前一个日志的的日志号
          prevLogTerm     int     // 前一个日志的任期号
          entries         []byte  // 当前日志体
          leaderCommit    int     // leader已提交的日志号
      }

      // AppendEntries Response
      type AppendEntriesResponse struct{
          term            int     // 自身当前任期号
          success         bool    // 若follower包括前一个日志，则返回true
      }

安全性

  • 选举限制
    • 同一任期内每个节点最多投票1次，并且安装FCFS原则
    • 日志条目只能从leader到follower，leader从来不会覆盖或者删除自身日志
    • 日志完整性高的follower不会投票给日志完整性低的candidate
      • 即使candidate的任期大于follower的任期，但是candidate向follower发送的RequestVote RPC中的term小于follower最后一条日志中的term，follower会拒绝向此candidate投票
  • Leader只能提交任期内的日志条目
  • Follower和Candidate宕机：Raft会无限次进行重试来处理RPC发送失败
  • Raft不依赖客观时间，Raft需要满足下面时间要求：
    1
    广播时间(Broadcast Time) << 选举超时时间(Election Timeout) << 平均故障时间(MTBF)
  • 广播时间和平均故障时间由系统决定，选举超时时间可自定义，大约是 10ms ~ 500ms，广播时间大约是0。5ms ~ 20ms，MTBF大约在几个月或更长

集群成员变更

  • 比如增减节点，替换宕机机器，改变复制长度。Raft可进行配置变更自动化。
  • 自动化配置变更机制可能会带来脑裂问题（即整个集群可能划分为两个独立的大多数，比如出现同一任期的两个Leader）
  • 概念
    • 联合共识（joint consensus）：集群从旧配置变更成新配置的过程中使用一个过渡中间配置，联合共识是新旧配置的并集
    • Configuration配置：集群中所有节点地址信息的集合，比如节点A，B，C组成的集群，配置就是[A, B, C]
    • Cold,new; Cnew，Cold：联合共识配置，新配置，旧配置
  • Consensus Joint约束：
    • 新旧配置的日志会复制给新、旧配置的所有节点
    • 新、旧配置的任何节点都可能成为 Leader(领导者)
    • 选举和日志复制阶段需要在新老配置上面都超多半数才能被提交生效

日志一致性检查

  • Leader会强制覆盖Follower中不一致的日志条目
  • 若Follower落后Leader许多日志，Leader会不断逐个向前发送AppendEntries RPC，直到找到Follower最新的那个日志，随后开始逐个向后复制。虽然耗时，但是这个情况比较少见，同时能够保证每一个Follower都拥有完整的日志，保证各个节点日志一致

Log compaction 日志压缩

  • 随着Raft集群的运行，每个节点上的Log会不断积累直到达到内存上限。Raft采用一种快照技术（snapshot），每个节点在达到一定条件（内存使用情况，达到日志数，定时器定时快照）后，可以吧当前日志中的命令都写入自己的快照，然后就可以把已经写入快照的日志删除
  • 快照中的一个key只会有最新的val，减少占用
  • Leader会直接向Follower发送自己的快照，保证落后的Follower的日志和Leader保持同步

相关

  • All changes from the Client to the system will go through the leader

Paxos