分布式协议与算法

这是一篇关于分布式协议与算法的思维导图，详细的归类了理论和协议与算法两大方面的内容，学习计算机的你科不能错过哦！

分布式协议与算法

• 理论
  • 拜占庭将军问题（存在恶意节点）
    • 口信消息型
      • 如果叛将人数为m,将军人数不能少于3m+1，协商次数为m+1
    • 签名消息型
      • 签名无法伪造
      • 任何人都能验证签名的真伪
      • n位将军能够容忍n-2数量的叛徒，只有一位忠将没有意义
      • 协商次数也为m+1
  • 共识与一致性
    • 一致性往往指分布式系统中多个副本对外呈现的数据的状态。如前面提到的顺序一致性、线性一致性，描述了多个节点对数据状态的维护能力。
    • 共识性则描述了分布式系统中多个节点之间，彼此对某个状态达成一致结果的过程。
    • 一致性描述的是结果状态，共识则是一种手段。达成某种共识并不意味着就保障了一致性（这里的一致性指强一致性）。只能说共识机制，能够实现某种程度上的一致性。因此，实践中，要保障系统满足不同程度的一致性，核心过程往往需要通过共识算法来达成。
  • 容错算法
    • 非拜占庭容错算法(CFT)
      • Paxos
      • Raft
      • ZAB
    • 拜占庭容错算法(BFT)
      • PBFT
      • PoW
  • CAP 理论
• 协议与算法
  • Paxos算法
    • Basic Paxos
      • 功能：多节点之间如何就某个值（提案 Value）达成共识
        • “大多数节点都同意”的原则，赋予了 Basic Paxos 容错的能力，让它能够容忍少于一半的节点的故障
      • 角色
        • 提议者（Proposer）
          • 集群中收到客户端请求的节点，才是提议者
          • 提议者代表的是接入和协调功能，收到客户端请求后，发起二阶段提交，进行共识协商
        • 接受者（Acceptor）
          • 一般来说，集群中的所有节点都在扮演接受者的角色
          • 接受者代表投票协商和存储数据，对提议的值进行投票，并接受达成共识的值，存储保存
        • 学习者（Learner）
          • 一般来说，学习者是数据备份节点，被动地接受数据，容灾备份
          • 学习者代表存储数据，不参与共识协商，只接受达成共识的值，存储保存
      • 
      • 过程
        • 1.准备阶段
          • 客户端作为提议者，分别向所有接受者发送包含提案编号1的准备请求[1,]
            • 准备请求中不需要指定提议的值，只需要携带提案编号
          • 如果之前未响应过提案，接受者返回“尚无提案”的响应，并承诺以后不再响应提案编号小于等于 1 的准备请求，不会通过编号小于 1 的提案
          • 如果提案编号 1 小于接受者之前响应的准备请求的提案编号 (比如5)，所以丢弃该准备请求，不做响应
          • 如果接受者之前有通过提案，那么接受者将承诺，会在准备请求的响应中，包含已经通过的最大编号的提案信息
        • 2.接受阶段
          • 当客户端收到大多数的接受者的准备响应后，根据响应中提案编号最大的提案的值，设置接受请求中的值(比如3），发送接受请求[1, 3]
          • 当接受者A、B、C等收到接受请求
            • 如果提案编号小于接受者中承诺能通过的最小提案编号，就拒绝该提案
            • 如果提案编号不小于接受者中承诺能通过的最小提案编号，就通过提案，达成共识
          • 如果集群中有学习者，当接受者通过了一个提案时，就通知给所有的学习者。当学习者发现大多数的接受者都通过了某个提案，那么它也通过该提案，接受该提案的值
    • Multi-Paxos
      • 功能：执行多个 Basic Paxos 实例，就一系列值达成共识
        • Multi-Paxos 算法是一个统称，它是指基于 Multi-Paxos 思想，通过多个 Basic Paxos 实例实现一系列数据的共识的算法
      • 引入领导者节点，领导者节点作为唯一提议者，这样就不存在提案冲突的情况
        • 兰伯特没有说如何选举领导者，需要我们在实现 Multi-Paxos 算法的时候自己实现
      • 优化 Basic Paxos 执行
        • 当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段
  • Raft算法
    • Raft 算法属于 Multi-Paxos 算法。从本质上说，Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致
      • Raft 算法是强领导者模型
    • http://thesecretlivesofdata.com/raft/
    • 成员身份
      • 领导者（Leader）
        • 平常的主要工作内容就是 3 部分，处理写请求、管理日志复制和不断地发送心跳信息
      • 跟随者（Follower）
        • 当等待领导者心跳信息超时的时候，就主动站出来，推荐自己当候选人
      • 候选人（Candidate）
        • 候选人将向其他节点发送请求投票，如果赢得了大多数选票，就晋升当领导者
    • 一、领导选举
      • Leader选举流程
        • 随机超时时间
          • 1.每个节点等待领导者节点心跳信息的超时时间间隔是随机的
          • 2.如果候选人在一个随机时间间隔内，没有赢得过半票数，那么选举无效了，然后候选人发起新一轮的选举，也就是说，等待选举超时的时间间隔，是随机的
        • 1.等待超时时间最小的节点A会最先因为没有等到领导者的心跳信息，发生超时。这个时候，节点 A 就增加自己的***编号，并推举自己为候选人，先给自己投上一张选票，然后向其他节点发送请求投票 RPC 消息，请它们选举自己为领导者
        • 2.如果其他节点接收到候选人 A 的请求投票 RPC 消息，在这届***内，也还没有进行过投票，那么它将把选票投给节点 A，并增加自己的***编号
        • 3.如果候选人在选举超时时间内赢得了大多数的选票，那么它就会成为本届***内新的领导者
        • 4.节点 A 当选领导者后，他将周期性地发送心跳消息，通知其他服务器我是领导者，阻止跟随者发起新的选举
      • 节点通讯
        • 请求投票（RequestVote）RPC
          • 由候选人在选举期间发起，通知各节点进行投票
        • 日志复制（AppendEntries）RPC
          • 由领导者发起，用来复制日志和提供心跳消息
      • ***
        • 选举中的领导者是有***的，领导者任命到期后，要重新开会再次选举
        • 跟随者在等待领导者心跳信息超时后，推举自己为候选人时，会增加自己的***号
        • 如果一个服务器节点，发现自己的***编号比其他节点小，那么它会更新自己的编号到较大的编号值
        • 在 Raft 算法中约定，如果一个候选人或者领导者，发现自己的***编号比其他节点小，那么它会立即恢复成跟随者状态
        • 还约定如果一个节点接收到一个包含较小的***编号值的请求，那么它会直接拒绝这个请求
      • 选举规则
        • 领导者周期性地向所有跟随者发送心跳消息（即不包含日志项的日志复制 RPC 消息），通知大家我是领导者，阻止跟随者发起新的选举
        • 如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起领导者选举
        • 在一次选举中，赢得大多数选票的候选人，将晋升为领导者
        • 在一个***内，领导者一直都会是领导者，直到它自身出现问题（比如宕机），或者因为网络延迟，其他节点发起一轮新的选举
        • 在一次选举中，每一个服务器节点最多会对一个***编号投出一张选票，并且按照“先来先服务”的原则进行投票
        • 日志完整性高的跟随者（也就是最后一条日志项对应的***编号值更大，索引号更大），拒绝投票给日志完整性低的候选人
          • 
      • Raft与Paxos的区别
        • 在 Raft 中，不是所有节点都能当选领导者，只有日志较完整的节点（也就是日志完整度不比半数节点低的节点），才能当选领导者
        • 在 Raft 中，日志必须是连续的
        • Raft 算法通过***、领导者心跳消息、随机选举超时时间、先来先服务的投票原则、大多数选票原则等，保证了一个***只有一位领导，也极大地减少了选举失败的情况
        • Raft 算法以领导者为中心，选举出的领导者，以“一切以我为准”的方式，达成值的共识，和实现各节点日志的一致
    • 二、日志复制
      • 日志项
        • 指令
          • 一条由客户端请求指定的、状态机需要执行的指令。你可以将指令理解成客户端指定的数据
        • 索引值
          • 日志项对应的整数索引值。它其实就是用来标识日志项的，是一个连续的、单调递增的整数号码
        • ***编号
          • 创建这条日志项的领导者的***编号
      • Multi-Paxos 不要求日志是连续的，Raft 中日志必须是连续的。
        • 在 Raft 中，日志不仅是数据的载体，日志的完整性还影响领导者选举的结果。也就是说，日志完整性最高的节点才能当选领导者
      • 
      • 日志复制过程
        • 1.接收到客户端请求后，领导者基于客户端请求中的指令，创建一个新日志项，并附加到本地日志中。
        • 2.领导者通过日志复制 RPC，将新的日志项复制到其他的服务器。
        • 3.当领导者将日志项，成功复制到大多数的服务器上的时候，领导者会将这条日志项应用到它的状态机中
        • 4.领导者将执行的结果返回给客户端
        • 5.当跟随者接收到心跳信息，或者新的日志复制 RPC 消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没应用，那么跟随者就将这条日志项应用到本地的状态机中
      • 领导者通过强制跟随者直接复制自己的日志项，处理不一致日志
        • 领导者通过日志复制 RPC 一致性检查，找到跟随者节点上与自己相同日志项的最大索引值，然后复制并更新覆盖该索引值之后的日志项，实现了各节点日志的一致
    • 三、成员变更
      • 成员变更的问题
        • 
          • 成员变更的问题，主要在于进行成员变更时，可能存在新旧配置的 2 个“大多数”，导致集群中同时出现两个领导者，破坏了 Raft 的领导者的唯一性原则，影响了集群的稳定运行
        • 绝大多数 Raft 算法的实现，采用的都是单节点变更的方法
        • 单节点变更，就是通过一次变更一个节点实现成员变更。如果需要变更多个节点，那你需要执行多次单节点变更。
        • 单节点变更是利用“一次变更一个节点，不会同时存在旧配置和新配置 2 个‘大多数’”的特性，实现成员变更
  • Gossip协议
    • 功能：利用一种随机、带有传染性的方式，将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致
    • 方式
      • 直接邮寄
        • 直接发送更新数据，当数据发送失败时，将数据缓存下来，然后重传
          • 可能会因为缓存队列满了而丢数据
      • 反熵
        • 反熵指的是集群中的节点，每隔段时间就随机选择某个其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异，实现数据的最终一致性
          • 反熵中的熵是指混乱程度，反熵就是指消除不同节点中数据的差异，提升节点间数据的相似度，降低熵值
        • 执行反熵时，相关的节点都是已知的，而且节点数量不能太多，如果是一个动态变化或节点数比较多的分布式环境，这时反熵就不适用了
        • 实现方式
          • 推
            • 将自己的所有副本数据，推给对方，修复对方副本中的熵
              • 
          • 拉
            • 拉取对方的所有副本数据，修复自己副本中的熵
              • 
          • 推拉
            • 同时修复自己副本和对方副本中的熵
              • 
        • 落地实现
          • 实现反熵时，实现细节和最初算法的约定有些不同。比如，不是一个节点不断随机选择另一个节点，来修复副本上的熵，而是设计了一个闭环的流程，一次修复所有节点的副本数据不一致
            • 数据修复是按照顺时针顺序，循环修复的
              • 
            • 因为我们希望能在一个确定的时间范围内实现数据副本的最终一致性，而不是基于随机性的概率，在一个不确定的时间范围内实现数据副本的最终一致性
      • 谣言传播
        • 指的是当一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据
  • NWR算法
    • 通过 Quorum NWR，你可以自定义一致性级别，通过临时调整写入或者查询的方式，当 W + R > N 时，就可以实现强一致性
    • NWR 是非常实用的一个算法，能有效弥补 AP 型系统缺乏强一致性的痛点，给业务提供了按需选择一致性级别的灵活度
    • 三要素
      • N
        • 副本数
          • 表示集群中同一份数据有多少个副本
            • 副本数可以不等于节点数，不同的数据可以有不同的副本数
      • W
        • 一致性级别
          • 表示成功完成 W 个副本更新，才完成写操作
      • R
        • 读一致性级别
          • 表示读取一个数据对象时需要读 R 个副本，然后返回 R 个副本中最新的那份数据
    • N 决定了副本的冗余备份能力；如果设置 W = N，读性能比较好；如果设置 R = N，写性能比较好；如果设置 W = (N + 1) / 2、R = (N + 1) / 2，容错能力比较好，能容忍少数节点（也就是 (N - 1) / 2）的故障
  • PBFT算法（Practical Byzantine-Fault-Tolerant）
    • PBFT 算法是通过签名（或消息认证码 MAC）约束恶意节点的行为，采用三阶段协议，基于大多数原则达成共识的
      • 每个节点都可以通过验证消息签名确认消息的发送来源，一个节点无法伪造另外一个节点的消息。最终，基于大多数原则（2f + 1）实现共识的(f为叛徒数)
      • 最终的共识是否达成，客户端是会做判断的，如果客户端在指定时间内未收到请求对应的 f + 1 相同响应，就认为集群出故障了，共识未达成，客户端会重新发送请求
    • PBFT 算法能容忍 (n - 1)/3 个恶意节点 (也可以是故障节点)
      • f = (n - 1)/3
    • PBFT 算法相比口信消息型拜占庭之解已经有了很大的优化，将消息复杂度从 O(n ^ (f + 1)) 降低为 O(n ^ 2)
      • 推荐中小型分布式系统中使用 PBFT 算法
    • 主节点作恶
      • 情况
        • 主节点接收到客户端请求后，它不做任何处理
        • 主节点接收到客户端请求后，给不同的预准备请求分配不同的序号
        • 主节点只给部分节点发送预准备消息
      • 解决方式：视图变更
        • 客户端通过等待 f+1 个相同响应消息超时，来发现主节点可能在作恶，此时客户端发送客户端请求给所有集群节点，从而触发可能的视图变更
  • ZAB协议
    • 定义：能保证操作顺序性的，基于主备模式的原子广播协议
    • 在 ZAB 中，写操作必须在主节点上执行。如果客户端访问的节点是备份节点，它会将写请求转发给主节点
    • 事务标识符是 64 位的 long 型变量，有***编号 epoch 和计数器 counter 两部分组成<epoch, counter>
      • ***编号
        • 创建提案时领导者的***编号
      • 计数器
        • 具体标识提案的整数,每次领导者创建新的提案时，计数器将递增
      • 事务标识符必须按照顺序、唯一标识一个提案，也就是说，事务标识符必须是唯一的、递增的
    • 顺序性保证
      • 当主节点接收到写请求后，它会基于写请求中的指令，来创建一个提案（Proposal），并使用一个唯一的 ID (事务标识符zxid)来标识这个提案
      • 在创建完提案之后，主节点会基于 TCP 协议，并按照顺序将提案广播到其他节点
        • 如果用同一个tcp连接发送，应用层收到的数据一定是先发先到的。tcp内部会给每个包编号，就算收到的不是顺序的，tcp也会按编号调整顺序，最终抛给应用层的数据一定是按顺序的
        • 保证先发送的消息，会先被收到，保证了消息接收的顺序性
      • 当主节点接收到指定提案的“大多数”的确认响应后，该提案将处于提交状态（Committed），主节点会通知备份节点提交该提案
        • 主节点提交提案是有顺序性的。主节点根据事务标识符大小，按照顺序提交提案，如果前一个提案未提交，此时主节点是不会提交后一个提案的
      • 最后，主节点返回执行成功的响应给节点 B，节点 B 再转发给客户端
    • 领导者选举
      • ZAB 的领导者选举，选举出的是大多数节点中数据最完整的节点
      • 成员身份
        • 领导者
          • 作为主（Primary）节点，在同一时间集群只会有一个领导者。需要你注意的是，所有的写请求都必须在领导者节点上执行
        • 跟随者
          • 作为备份（Backup）节点， 集群可以有多个跟随者，它们会响应领导者的心跳，并参与领导者选举和提案提交的投票
          • 跟随者可以直接处理并响应来自客户端的读请求，但对于写请求，跟随者需要将它转发给领导者处理
        • 观察者
          • 作为备份（Backup）节点，类似跟随者，但是没有投票权，不参与领导者选举和提案提交的投票
      • 在 ZAB 中，选举出了新的领导者后，该领导者不能立即处理写请求，还需要通过成员发现、数据同步 2 个阶段进行故障恢复
      • 选举流程
        • 当跟随者检测到连接领导者节点的读操作等待超时了，跟随者会变更节点状态，将自己的节点状态变更成 LOOKING，然后发起领导者选举
        • 每个节点会创建一张选票，这张选票是投给自己的，也就是推荐自己为领导者，然后各自将选票发送给集群中所有节点
        • 一般而言，节点会先接收到自己发送给自己的选票
        • 集群的各节点收到选票后，为了选举出数据最完整的节点，对于每一张接收到选票，将选票提议的领导者和自己提议的领导者进行比较，找出更适合作为领导者的节点，并更新自己的选票，将选票重新发送
          • 优先检查***编号（Epoch），***编号大的节点作为领导者
          • 如果***编号相同，比较事务标识符的最大值，值大的节点作为领导者
          • 如果事务标识符的最大值相同，比较集群 ID，集群 ID 大的节点作为领导者
        • 提议的领导者赢得大多数选票后，各节点变更节点状态，并退出选举。
    • 成员发现与数据同步
      • 节点的运行状态
        • ELECTION（选举状态）
          • 表明节点在进行领导者选举
        • DISCOVERY（成员发现状态）
          • 表明节点在协商沟通领导者的合法性
        • SYNCHRONIZATION（数据同步状态）
          • 表明集群的各节点以领导者的数据为准，修复数据副本的一致性
        • BROADCAST（广播状态）
          • 表明集群各节点在正常处理写请求
            • 只有当集群大多数节点处于广播状态的时候，集群才能提交提案
      • 成员发现，是为了建立跟随者和领导者之间的领导者关系，并通过***编号来确认这个领导者是否为最合适的领导者
        • 确立领导关系
          • 在当选后，领导者会递增自己的***编号，并基于***编号值的大小，来和跟随者协商，最终建立领导关系
            • 跟随者会选择***编号值最大的节点，作为自己的领导者，而被大多数节点认同的领导者，将成为真正的领导者
        • 成员发现流程
          • 1.选举阶段结束，所有活跃节点进入DISCOVERY状态。领导者进入到DISCOVERY阶段后，会对***编号加 1，创建新的***编号，然后基于新***编号，创建新的事务标识符
          • 2.各个跟随者会主动联系新选举出来的领导，发送给它包含自己接收过的领导者***编号最大值的 FOLLOWINFO 消息
          • 3.领导者接收到信息后，它会将包含自己事务标识符最大值的 LEADINFO 消息发给跟随者
          • 4.当接收到领导者的响应后，跟随者会判断领导者的***编号是否最新，如果不是，就发起新的选举；如果是，跟随者返回 ACKEPOCH 消息给领导者。
          • 5.当领导者接收到来自大多数节点的 ACKEPOCH 消息时，就设置 ZAB 状态为数据同步。之后领导者就可以行使领导职能了
          • 
      • 数据同步，是通过以领导者的数据为准的方式，来实现各节点数据副本的一致
        • 在 ZooKeeper 中，被复制到大多数节点上的提案，最终会被提交，并不会再改变；而只在少数节点存在的提案，可能会被提交和不再改变，也可能会被删除
          • 在 ZooKeeper 的设计中，在节点退出跟随者状态时（在 follower.shutdown() 函数中），会将所有本地未提交的提案都提交。需要你注意的是，此时提交的提案，可能并未被复制到大多数节点上，而且这种设计，就会导致 ZooKeeper 中出现，处于“提交”状态的提案可能会被删除（也就是接收到领导者的 TRUNC 消息而删除的提案）
        • 数据同步流程
          • 1.当进入到数据同步状态后，领导者会根据跟随者的事务标识符最大值，判断以哪种方式处理不一致数据（DIFF、TRUNC、SNAP）
            • TRUNC
              • 领导者会通知跟随者丢弃超出的那部分提案
            • DIFF
              • 领导者会同步给跟随者缺失的已提交的提案
            • SNAP
              • 跟随者缺失的提案比较多，领导者同步快照数据给跟随者，并直接覆盖跟随者本地的数据
          • 2.新领导者 会返回差异数据和 NEWLEADER 消息给 跟随者
          • 3.跟随者修复不一致数据，返回 NEWLEADER 消息的确认响应给领导者
          • 4.当领导者接收到来自大多数节点的 NEWLEADER 消息的确认响应，将设置 ZAB 状态为广播状态，并发送 UPTODATE 消息给所有跟随者，通知它们数据同步已经完成
          • 5.跟随者接收到 UPTODATE 消息时，它就知道数据同步完成，就设置 ZAB 状态为广播。这样集群就可以正常处理写请求了
          • 
  • Raft与ZAB对比
    • 领导者选举
      • ZAB 采用的“见贤思齐、相互推荐”的快速领导者选举（Fast Leader Election），Raft 采用的是“一张选票、先到先得”的自定义算法。在我看来，Raft 的领导者选举，需要通讯的消息数更少，选举也更快
    • 日志复制
      • Raft 和 ZAB 相同，都是以领导者的日志为准来实现日志一致，而且日志必须是连续的，也必须按照顺序提交
    • 读操作和一致性
      • ZAB 的设计目标是操作的顺序性，在 ZooKeeper 中默认实现的是最终一致性，读操作可以在任何节点上执行；而 Raft 的设计目标是强一致性（也就是线性一致性），所以 Raft 更灵活，Raft 系统既可以提供强一致性，也可以提供最终一致性。
    • 写操作
      • Raft 和 ZAB 相同，写操作都必须在领导者节点上处理
    • 成员变更
      • Raft 和 ZAB 都支持成员变更，其中 ZAB 以动态配置（dynamic configuration）的方式实现的。那么当你在节点变更时，不需要重启机器，集群是一直运行的，服务也不会中断
    • 其他
      • 相比 ZAB，Raft 的设计更为简洁，比如 Raft 没有引入类似 ZAB 的成员发现和数据同步阶段，而是当节点发起选举时，递增***编号，在选举结束后，广播心跳，直接建立领导者关系，然后向各节点同步日志，来实现数据副本的一致性