【笔记】分布式理论 & 算法

发表于 分类于 阅读次数： 本文字数： 3.1k 阅读时长 ≈ 4 分钟

理论

CAP 理论

一致性（Consistency)、可用性（Availability）、分区容错性（Partition Tolerance）。实现一致性只能在 CP 和 AP 中进行选择。（理论上无法选择 CA 架构，在分区情况下，C 与 A 产生了冲突）。

BASE 理论

可以理解为对 AP 方案的一个补充。

即使无法做到强一致，但每个应用可以根据自身业务特点，采用适当的方式来使系统达到最终一致性。（也就是牺牲数据的一致性来满足系统的高可用性，系统中一部分数据不可用或者不一致时，仍需要保持系统整体“主要可用”）。

  1. 基本可用：分布式系统在出现不可预知故障时，允许损失部分可用性。但不等价于系统不可用。
    1. 响应时间上的损失
    2. 系统功能上的损失
  2. 软状态：允许系统中的数据存在中间状态，并认为该中间状态存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。
  3. 最终一致性：在经过一段时间的同步后，最终能够达到一个一致的状态。最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致。
  • 强一致：写入后马上读出来新值
  • 弱一致：写入后不一定可以读到最新写入的值，也不保证多少时间之后读取到的数据是最新的，只是会尽量保证某个时刻达到数据一致的状态。
  • 最终一致：弱一致的升级，系统会保证在一定时间内达到数据一致的状态。

算法

Paxos

  • Basic Paxos： 多个节点之间如何就某个值（提案 Value）达成共识。
  • Multi Paxos：执行多个 Basic Paxos 实例，就一系列值达成共识。

Paxos

  1. 提议者（Proposer）：也叫做协调者（coordinator），提议者负责接受客户端的请求并发起‘提案。提案信息通常包括提案编号和提议值。
  2. 接受者（Acceptor）：也叫做投票员（voter），负责对提议者的提案进行投票，同时需要记住自己的投票历史。
  3. 学习者（Learner）：如果有超过半数的接受者就某个提议达成了共识，那么学习者就需要接受这个提议，并就该提议作出运算，然后将运算结果返回给客户端。

Multi Paxos 是一种思想，核心是通过多个 Basic Paxos 实例就一系列值达成共识。

Raft

Raft 集群包括若干服务器，在任意的时间，每个服务器都处于下面三个状态中的一个：

  • Leader：负责发起心跳，响应客户端，创建日志，同步日志
  • Candidate：Leader 选举过程中的临时角色，由 Follower 转化而来，发起投票参与竞选
  • Follower：接受 Leader 的心跳和日志同步数据，投票给 Candidate

状态转移

任期：raft 算法将时间划分为任意长度的任期（term），任意用连续的数字表示，看作当前 term 号。每一个任期的开始都是一次选举。

日志：

  • Entry：每一个事件成为 entry，只有 Leader 可以创建 entry，entry 的内容为 <term,index,cmd> 其中 cmd 是可以应用到状态机的操作。
  • Log： 由 entry 构建的数组，每个 entry 都有一个表明自己在 log 中的 index。只有 Leader 才可以改变其他节点的 log。entry 总是先被 Leader 添加到自己的 log 数组中，然后再发起共识请求，获得同意后才会被 Leader 提交给状态机。Follower 只能从 Leader 获取新日志和当前的 commitIndex，然后把对应的 entry 应用到自己的状态机中。

Leader 选举：

采用心跳机制来触发 Leader 的选举。

Leader 会向所有的 Follower 周期性的发送心跳来保证自己的 Leader 地位。如果 Follower 在一个周期内没有收到心跳信息，会认为此时没有可用的 Leader，并开始进行一次选举。

选举时，会先自增自己的 term 号，转换状态为 Candidate，向所有节点发起投票。当获得 N/2 + 1 的选票时，可以成为 Leader。

当选举过程中如果收到了 Leader 的心跳，则根据 term 号判断是否接受。

  1. 该 Leader 的 term 号大于等于自己的 term 号，则自己退回 follower
  2. 该 Leader 的 term 号小于自己的 term 号，那么会拒绝该请求并让该节点更新 term

同一时间可能存在多个 Candidate。raft 使用随机的选举超时避免永远没有选出 Leader 的情况。

日志复制：

当选出 Leader 后，Leader 将接受客户端的请求，每一个客户端的请求都包含一条需要被复制状态机星星的命令。收到客户端请求后，产生一条 entry，添加到自己的日志末尾后，向所有节点广播该 entry，要求其他服务器复制这条 entry。

Follower 收到 entry 后，添加 entry 到 log，然后返回成功。

Leader 收到多数成功响应，Leader 将这条 entry 应用到自己的状态机中，返回客户端执行结果。

Raft 保证两个性质：

  • 在两个日志里，有两个 entry 拥有相同的 index 和 term，那么一定有相同的 cmd （仅 Leader 可以生成 entry 保证）
  • 在两个日志里，有两个 entry 拥有相同的 index 和 term，那它们之前的 entry 也一定相同 （一致性检查保证）

Leader 会在强制 Follower 复制自己的日志 来处理日志不一致。Leader 给每一个 Follower 维护了一个 nextIndex，记录下一个需要发送给该 Follower 的日志条目索引。当成为 Leader 时，nextIndex + 1，开始一轮检查，如果不一致，则 nextIndex -1，直到 appendEntries 成功。

安全性：

  1. 选举限制
    1. Follower 接受选举投票前提是要求发起投票的最后一个 entry 大于自己的 entry
    2. 如果两个日志 term 不同，term 大为更新；term 相同，更长的 index 为更新
  2. 节点崩溃
    1. Leader 崩溃，则进行选举
    2. Follower 和 Candidate 崩溃，则 Leader 进行不断重试
  3. 时间与可用性
    1. 向其他节点并发发送消息的平均响应时间 << 选举超市时间 << 单台机器的平均健康时间

Gossip

集中式发散消息，一个主节点同时共享最新信息给其他所有节点，比较适合中心化系统。缺点是节点多时同步消息效率低，过于依赖中心节点，存在单点风险。

Gossip 协议是一种允许在分布式系统中共享状态的去中心化通信协议，通过这种通信协议，可以将信息传播给网络或集群中的所有成员。

两种可能的消息传播模式：

  • 反熵（Anti-entropy）：消除节点中的差异，提升相似度
    • 推方式：将自己的所有副本数据推给对方，修复对方副本中的熵
    • 拉方式：拉取对方的所有副本数据，修复自己副本中的熵
    • 推拉：同时修复自己副本和对方副本中的熵
    • 一般会给反熵设计一个闭环。
  • 传谣（Rumor-Mongering）：一个节点一旦有了新数据之后，会变为活跃姐弟呐，周期性地联系其他节点，向其发送新数据，直到所有节点都存储了该新数据。
    • 适合节点数量比较多或者节点动态变化的场景

优势：

  • 相比较其他分布式协议 / 算法，理解简单
  • 能够容忍网络上节点随意地增加或减少、宕机或重启，因为 Gossip 协议下这些节点都是平等的，去中心化的。新增加的或者重启的节点在理想情况下最终是一定会和其他节点的状态达成一致。
  • 速度相对较快。节点数量比较多的情况下，扩散速度比一个节点向其他节点传播信息要快

缺陷：

  • 消息需要通过多个传播的轮次才能传播到整个网络中，因此必然会出现各个节点状态不一致的情况。并且各个节点的状态一致需要多长时间也不确定。
  • 由于拜占庭将军问题，不允许存在恶意节点
  • 可能出现消息冗余的问题。由于消息传播的随机性，同一个节点可能会重复收到相同的消息。

参考

  1. 拜占庭将军问题： 多个将军使用信使者如何达成一致。
  2. 分布式协议讲解