每天净瞎搞

关注:AI/CS/数学/自我提升等

0%

《分布式协议与算法实战》协议和算法篇上 学习笔记

05 | Paxos算法(一):如何在多个节点间确定某变量的值?

  • Q:Basic Paxos的三种角色
    • 提议者(Proposer):提议一个值用于投票表决,可把客户端当成提议者。但在绝大多数场景中,集群中收到客户端请求的节点,才是提议者。好处是对业务代码没有入侵性,即不需要再业务代码中实现算法逻辑,可像使用数据库一样访问后端数据。代表的是接入和协调功能,收到客户端请求后,发起二阶段提交,进行共识协商
    • 接受者(Acceptor):对每个提议的值进行投票,并存储接受的值。一般集群中的所有节点都在扮演接受者的角色,参与共识协商,并接受和存储数据。代表投票协商和存储数据,对提议的值进行投票,并接受达成共识的值,存储保存
    • 学习者(Learner):被告知投票的结果,接受达成共识的值,存储保存,不参与投票的过程。通常学习者是数据备份节点,如「Master-Slaev」模型中的Slave,被动地接受数据,容灾备份。代表存储数据,不参与共识协商,值接受达成共识的值,存储保存
  • Q:Basic Paxos如何达成共识
    • 假设客户端 1 的提案编号为 1,客户端 2 的提案编号为 5,并假设节点 A、B 先收到来自客户端 1 的准备请求,节点 C 先收到来自客户端 2 的准备请求
    • 准备(Prepare)阶段
      • 客户端1、2作为提议者,分别向所有接受者发送包含提案编号的准备请求
      • 在准备请求中是不需要指定提议的值的,只需要携带提案编号即可
      • 当节点A、B收到提案编号为1的准备请求,节点C收到提案编号为5的准备请求后,将这样处理:
      • 由于之前没有通过任何提案,所以结点A、B将返回一个「尚无提案」的相应,并以后不再响应提案编号小于等于1的准备请求,不会通过编号小于1的提案
      • 结点C则返回「尚无提案」的响应并以后不再响应提案编号小于等于5的准备请求,不会通过编号小于5的提案
      • 另外,当节点 A、B 收到提案编号为 5 的准备请求,和节点 C 收到提案编号为 1 的准备请求的时候,将这样处理:
      • 当节点A、B收到提案编号为5的准备请求的时候,因为提案编号5大于它们之前响应的准备请求的提案编号1,而且两个节点都没有通过诺任何提案,所以它将返回一个「尚无提案」的响应,并承诺以后不再响应提案编号小于等于5的准备请求,不会通过编号小于5的提案
      • 当节点C收到提案编号为1的准备请求的时候,由于提案编号1小于它之前响应的准备请求的提案编号5,所以丢弃该准备请求,不做响应
    • 接受(Accept)阶段
      • 首先客户端1、2在收到大多数节点的准备响应之后,会分别发送接受请求:
      • 当客户端1收到大多数的接受者(节点A、B)的准备响应后,根据响应中提案编号最大的提案的值,设置接受请求中的值。因为该值在来自节点A、B的准备响应中都为空,所以就把自己的提议值3作为提案的值,发送接受请求[1, 3]
      • 当客户端2收到大多数的接受者的准备响应后(节点A、B和节点C),根据响应中提案编号最大的提案的值,来设置接受请求中的值。因为该值来自节点A、B、C的准备响应中都为空,所以就把自己的提议值7作为提案的值,发送请求[5, 7]
      • 当三个节点收到2 个客户端的接受请求时,会这样处理:
      • 当节点A、B、C收到接受请求[1, 3]时,由于提案的提案编号1小于三个节点承诺能通过的提案的最小提案编号5,所以提案[1, 3]将被拒绝
      • 当节点A、B、C收到接受请求[5, 7]的时候,由于提案的提案编号 5 不小于三个节点承诺能通过的提案的最小提案编号 5,所以就通过提案[5, 7],也就是接受了值 7,三个节点就 X 值为 7 达成了共识
    • 如果集群中有学习者,当接受者通过了一个提案时,就通知给所有的学习者。当学习者发现大多数的接受者都通过了某个提案,那么它也通过该提案,接受该提案的值
    • Basic Paxos的容错能力,源自「大多数」的约定,即当少于一半的节点出现故障的时候,共识协商仍然在正常工作
    • 本质上而言,提案编号的大小代表着优先级,根据提案编号的大小, 接受者保证三个承诺
      • 如果准备请求的提案编号,小于等于接受者已经响应的准备请求的提案编号,那么接受者将承诺不响应这个准备请求
      • 如果接受请求中的提案的提案编号,小于接受者已经响应的准备请求的提案编号,那么接受者将承诺不通过这个提案
      • 如果接受者之前有通过提案,那么接受者将承诺,会在准备请求的响应中,包含已经通过的最大编号的提案信息

07 | Raft算法(一):如何选举领导者?

  • Q:Raft算法的成员身份(服务器节点状态)
    • 领导者(Leader):主要工作有处理写请求、管理日志复制和不断地发送心跳信息
    • 跟随者(Follower):默默接收和处理来自领导者的消息,当等待领导者心跳信息超时的时候,主动站出来,推荐自己当候选人
    • 候选人(Candidate):候选人将向其它节点发送请求投票(RequestVote) RPC消息,通知其它节点来投票,如果赢得了大多数选票,就晋升当领导者
    • Raft算法是强领导者模型,集群中只能有一个领导者
  • Q:Raft算法选举领导者的过程
    • 在初始状态下,集群中所有的节点都是跟随者的状态
    • Raft算法实现了随机超时时间的特性,即每个节点等待领导者节点心跳信息的超时时间间隔是随机的。如上图,集群中没有领导者,而节点A的等待超时时间最小(150ms),它会最先因为没有等到领导者的心跳信息,发生超时
    • 这时,节点A就增加自己的任期编号,推举自己为候选人,先给自己投上一张选票,然后向其他节点发送请求投票 RPC 消息,请它们选举自己为领导者
    • 如果其它节点接收到候选人A的请求投票RPC消息,在编号为1的这届任期内,也还没有进行过投票,那么它将把选票投给节点A,并增加自己的任期编号
    • 如果候选人在选举超时时间内赢得了大多数的选票,那么它就会成为本届任期内的新领导者
    • 节点A当选领导者后,将周期性地发送心跳消息,通知其他服务器我是领导者,阻止跟随者发起新的选举,篡权
  • Q:节点间如何通讯?
    • 在Raft算法中,服务器节点间的沟通联络采用的是远程过程调用(RPC),在领导者选举中,需要用到两类RPC:
      • 1.请求投票(RequestVote) RPC,由候选人在选举期间发起,通知各节点进行投票
      • 2.日志复制(AppendEntries) RPC,由领导者发起,用来复制日志和提供心跳信息
    • 注意:日志复制 RPC 只能由领导者发起,这是实现强领导者模型的关键之一
  • Q:什么是任期?
    • Raft算法中的领导者也是有任期的,每个任期由单调递增的数字(任期编号)标识,如节点A的任期编号是1。任期编号是随着选举的举行而变化的
      • 1.跟随者在等待领导者心跳信息超时后,推举自己为候选人时,会增加自己的任期号,如节点A的当前任期编号为0,那么在推举自己为候选人时,会将自己的任期编号加1
      • 2.如果一个服务器节点,发现自己的任期编号比其它节点小,那么它会更新自己的编号到较大的编号值。如节点B的任期编号是0,当收到来自节点A的请求投票RPC消息时,因为信息中包含了结点A的任期编号,且编号为1,那么节点B将把自己的任期编号更新为1
    • Raft 算法中的任期不只是时间段,而且任期编号的大小,会影响领导者选举和请求的处理
      • 1.在Raft算法中约定,如果一个候选人或领导者,发现自己的任期编号比其它节点小,那么它会立即恢复成跟随者状态。比如分区错误恢复后,任期编号为3的领导者节点B,收到来自新领导者的,包含任期编号为4的心跳信息,那么节点B将立即恢复成跟随者状态
      • 2.还约定如果一个节点接收到一个包含较小的任期编号值的请求,那么它会直接拒绝这个请求。如节点C的任期编号为4,收到包含任期编号为3的请求投票RPC消息,那么它将拒绝这个消息
  • Q:选举有哪些规则?
    • 1.领导者周期性地向所有跟随者发送心跳信息(即不包含日志项的日志复制RPC消息),通知大家我是领导者,阻止跟随者发起新的选举
    • 2.如果在指定时间内,跟随者没有接收到来自领导者的消息,那么它就认为当前没有领导者,推举自己为候选人,发起领导者选举
    • 3.在一次选举中,赢得大多数选票的候选人,将晋升为领导者
    • 4.在一个任期内,领导者一直都会是领导者,直到它自身出现问题(如宕机),或者因为网络延迟,其它节点发起一轮新的选举
    • 5.在一次选举中,每一个服务器节点最多会对一个任期编号投出一章选票,并且按照「先来先服务」的原则进行投票。如节点C的任期编号为3,先收到了1个包含任期编号为4的投票请求(来自节点A),然后又收到了1个包含任期编号为4的投票请求(来自节点B)。那么节点C将会把唯一一张选票投给节点A,当再收到节点B的投票请求RPC 消息时,对于编号为 4 的任期,已没有选票可投了
    • 6.当任期编号相同时,日志完整性高的跟随者(即最后一条日志项对应的任期编号值更大,索引号更大),拒绝投票给日志完整性低的候选人。比如节点B、C的任期编号都是3,节点B的最后一条日志项对应的任期编号为3,而节点C为2,那么当节点C请求节点B投票给自己时,节点B将拒绝投票
    • 注意:选举时跟随者发起的,推举自己为候选人;大多数选票是指集群成员半数以上的选票;大多数选票规则的目标,是为了保证在一个给定的任期内最多只有一个领导者
    • 除了选举规则外,还需要避免一些会导致选举失败的情况,如同一任期内,多个候选人同时发起选举,导致选票被瓜分,选举失败。在Raft使用随机超时时间来避免这个问题
  • Q:如何理解随机超时时间?
    • Raft 算法巧妙地使用随机选举超时时间的方法,把超时时间都分散开来,在大多数情况下只有一个服务器节点先发起选举,而不是同时发起选举,这样就能减少因选票瓜分导致选举失败的情况
    • Raft算法的随机超时时间的 2 种含义
      • 1.跟随者等待领导者心跳信息超时的时间间隔,是随机的
      • 2.当没有候选人赢得过半票数,选举无效了,这时需要等待一个随机时间间隔,即等待选举超时的时间间隔,是随机的

08 | Raft算法(二):如何复制日志?

  • Q:Raft算法中的日志是什么?
    • 在Raft算法中,副本数据以日志的形式存在,日志是由日志项组成,日志项是一种数据格式,主要包含用户指定的数据,即指令(Command),和一些附加信息,如索引值(Log index)、任期编号(Term)
    • 指令:一条由客户端请求指定的、状态机需要执行的指令。可理解成客户端指定的数据
    • 索引值:日志项对应的整数索引值,用来标识日志项,是一个连续的、单调递增的整数号码
    • 任期编号:创建这条日志项的领导者的任期编号
    • 注意:一届领导者任期,往往有多条日志项。而且日志项的索引值是连续的
  • Q:如何复制日志?
    • 可把Raft 的日志复制理解成一个优化后的二阶段提交(将二阶段优化成了一阶段),减少了一半的往返消息,也就是降低了一半的消息延迟
    • 1.领导者进入第一阶段,通过日志复制(AppendEntries) RPC消息,将日志项复制到其它节点上
    • 2.如果领导者接收到大多数的「复制成功」响应后,它将日志项提交到它的状态机,并返回成功给客户端。如果领导者没有接收到大多数的“复制成功”响应,那么就返回错误给客户端
  • Q:领导者将日志项提交到它的状态机,为什么没通知跟随者提交日志项?
    • 这是 Raft 中的一个优化,领导者不直接发送消息通知其它节点提交指定日志项。因为领导者的日志复制RPC消息或心跳消息,包含了当前最大的,将会被提交的日志项索引值。所以通过日志复制RPC消息或心跳消息,跟随者就可以知道领导者的日志提交位置信息
    • 因此,当其它节点接受领导者的心跳信息,或者新的日志复制RPC消息后,就会将这条日志项提交到它的状态机。这个优化,降低了处理客户端请求的延迟,将二阶段提交优化为一阶段提交,降低了一半的消息延迟
  • Q:日志复制过程?
    • 1.接收到客户端请求后,领导者基于客户端请求中的指令,创建一个新日志项,并附加到本地日志中
    • 2.领导者通过日志复制RPC,将新的日志项复制到其它的服务器
    • 3.当领导者将日志项,成功复制到大多数服务器上的时候,领导者会将这条日志项提交到它的状态机中
    • 4.领导者将执行的结果返回给客户端
    • 5.当跟随者接收到心跳信息,或者新的日志复制RPC消息后,如果跟随者发现领导者已经提交了某条日志项,而它还没提交,那么跟随者就将这条日志项提交到本地的状态机中
  • Q:如何实现日志的一致?
    • 在Raft算法中,,领导者通过强制跟随者直接复制自己的日志项,处理不一致日志。即Raft是通过以领导者的日志为准,来实现各节点日志的一致的
    • 1.领导者通过日志复制RPC的一致性检查,找到跟随者节点上,与自己想通日志项的最大索引值。即在这个索引值之前的日志,领导者和跟随者是一致的,之后的日志是不一致的了
    • 2.领导者强制跟随者更新覆盖不一致的日志项,实现日志的一致
  • Q:Raft实现日志的一致的详细过程
    • 引入2个新变量
      • PrevLogEntry:表示当前要复制的日志项,前面一条日志项的索引值。如在图中,如果领导者将索引值为8的日志项发送给跟随者,那么此时 PrevLogEntry 值为7
      • PrevLogTerm:表示当前要复制的日志项,前面一条日志项的任期编号,如在图中,如果领导者将索引值为8的日志项发送给跟随者,那么此时PrevLogTerm值为4
    • 1.领导者通过日志复制RPC消息,发送当前最新日志项到跟随者,这个消息的PrevLogEnetry值为7,PrevLogTerm值为4
    • 2.如果跟随者在它的日志中,找不到与PrevLogEntry值为7、PrevLogTerm值为4的日志项,即它的日志和领导者的不一致了,那么跟随者者就会拒绝接收新的日志项, 并返回失败信息给领导者
    • 3.这时,领导者会递减要复制的日志项的索引值,并发送新的日志项到跟随者,这个消息的 PrevLogEntry 值为 6,PrevLogTerm 值为 3
    • 4.如果跟随者在它的日志中,找到了 PrevLogEntry 值为 6、PrevLogTerm 值为 3 的日志项,那么日志复制 RPC 返回成功,这样一来,领导者就知道在 PrevLogEntry 值为 6、PrevLogTerm 值为 3 的位置,跟随者的日志项与自己相同
    • 5.领导者通过日志复制RPC,复制并更新覆盖索引值后的日志项(即不一致的日志项),最终实现了集群各节点日志的一致
    • 从上面步骤中可以看到,领导者通过日志复制 RPC 一致性检查,找到跟随者节点上与自己相同日志项的最大索引值,然后复制并更新覆盖该索引值之后的日志项,实现了各节点日志的一致。注意,跟随者中的不一致日志项会被领导者的日志覆盖,而且领导者从来不会覆盖或者删除自己的日志

10 | 一致哈希算法:如何分群,突破集群的“领导者”限制?

  • Q:使用哈希算法实现哈希寻址时,有什么问题?
    • 通过哈希算法,每个 key 都可以寻址到对应的服务器,比如,查询 key 是 key-01,计算公式为 hash(key-01) % 3 ,经过计算寻址到了编号为 1 的服务器节点 A
    • 但如果服务器数量发生变化,基于新的服务器数量来执行哈希算法的时候,就会出现路由寻址失败的情况,Proxy 无法找到之前寻址到的那个服务器节点
    • 假如 3 个节点不能满足业务需要了,这时我们增加了一个节点,节点的数量从 3 变化为 4,那么之前的 hash(key-01) % 3 = 1,就变成了 hash(key-01) % 4 = X,因为 取模运算发生了变化,所以这个 X 大概率不是 1(可能 X 为 2),这时你再查询,就会找 不到数据了,因为 key-01 对应的数据,存储在节点 A 上,而不是节点 B
    • 同样的道理,如果我们需要下线 1 个服务器节点(也就是缩容),也会存在类似的可能查询不到数据的问题
    • 而解决这个问题的办法,在于我们要迁移数据,基于新的计算公式 hash(key-01) % 4 ,来重新对数据和节点做映射。需要你注意的是,数据的迁移成本是非常高的
    • 对于 1000 万 key 的 3 节点 KV 存储,如果我们增加 1 个 节点,变为 4 节点集群,则需要迁移 75% 的数据
  • Q:如何使用一致哈希实现哈希寻址
    • 一致哈希算法是对 2^32 进行取模运算,将整个 哈希值空间组织成一个虚拟的圆环,即哈希环
    • 哈希环的空间是按顺时针方向组织的,圆环的正上方的点代表0,0点右侧的第一个点代表1,以此类推,2、3、4、5、6……直到 2^32-1,即 0 点左 侧的第一个点代表 2^32-1
    • 在一致哈希中,通过执行哈希算法将节点映射到哈希环上,比如选择节点的主机名作为参数执行 c-hash(),那么每个节点就能确定其在哈希环上的位置了
  • Q:对指定 key 的值进行读写的时候,通过哪 2 步进行寻址?
    • 1.将key作为参数执行 c-hash() 计算哈希值,并确定此 key 在环上的位置
    • 2.从这个位置沿着哈希环顺时针“行走”,遇到的第一节点就是 key 对应的节点
  • Q:有一个节点故障了(如节点C),一致哈希是怎么处理的
    • key-01 和 key-02 不会受到影响,只有 key-03 的寻址被重定位到 A。一般来说,在一致哈希算法中,如果某个节点宕机不可用了,那么受影响的数据仅仅是,会寻址到此节点和前一节点之间的数据
    • 如当节点 C 宕机了,受影响的数据是会寻址到节点 B 和节点 C 之间的数据(例如 key-03),寻址到其他哈希环空间的数据(例如 key-01),不会受到影响
  • Q:需要扩容一个节点,一致哈希是怎么处理的
    • key-01、key-02 不受影响,只有 key-03 的寻址被重定位到新节点 D。一般 而言,在一致哈希算法中,如果增加一个节点,受影响的数据仅仅是,会寻址到新节点和前 一节点之间的数据,其它数据也不会受到影响
  • Q:在一致哈希中,客户端访问请求集中在少数的节点上,为什么会出现有些机器高负载,有些机器低负载的情况
    • 在一致哈希中,如果节点太少,容易因为节点分布不均匀造成数据访问的冷热不均,即大多数访问请求都会集中少量几个节点上
  • Q:如何通过虚拟节点解决冷热不均的问题?
    • 对每一个服务器节点计算多个哈希值,在每个计算结果位置上,都放置一个虚拟 节点,并将虚拟节点映射到实际节点。比如,可以在主机名的后面增加编号,分别计算 “Node-A-01”“Node-A-02”“Node-B-01”“Node-B-02”“Node-C01”“Node-C-02”的哈希值,于是形成 6 个虚拟节点
    • 增加了节点后,节点在哈希环上的分布就相对均匀了。这时,如果有访问请求寻址到“Node-A-01”这个虚拟节点,将被重定位到节点 A。这样我们就解决了冷热不均的问题

11 | Gossip协议:流言蜚语,原来也可以实现一致性

  • Q:Gossip的三板斧是什么?
    • 直接邮寄(Direct Mail)
    • 反熵(Anti-entropy)
    • 谣言传播(Rumor mongering)
  • Q:直接邮寄是什么?
    • 直接发送更新数据,当数据发送失败时,将数据缓存下来,然后重传。直接邮寄虽然实现起来比较容易,数据同步也很及时,但可能会因为缓存队列满了而丢数据。即只采用直接邮寄是无法实现最终一致性的
  • Q:反熵是什么?
    • 集群中的节点,每隔段时间就随机选择某个其它节点,然后通过互相交换自己的所有数据来消除两者之间的差异,实现数据的最终一致性
    • 如上图,节点A通过反熵的方式,修复了节点 D 中缺失的数据
    • 注意,因为反熵熵需要节点两两交换和比对自己所有的数据,执行反熵时通讯成本会很高,不建议频繁执行,可通过引入校验和(Checksum)等机制,降低需要对比的数据量和通讯消息
    • 执行反熵时相关的节点都是已知的,而且节点数量不能太多,如果是一个动态变化或节点数比较多的分布式环境,这时反熵就不适用了,该用谣言传播
  • Q:反熵修复节点缺失数据的3种方式
    • 以下图中,2 个数据副本的不一致为例
    • 推:将自己的所有副本数据,推给对方,修复对方副本中的熵
    • 拉:拉取对方的所有副本数据,修复自己副本中的熵
    • 推拉:同时修复自己副本和对方副本中的熵
  • Q:谣言传播是什么?
    • 当一个节点有了新数据后,这个节点编程活跃状态,并周期性地联系其他节点向其发送新数据,直到所有的节点都存储了该新数据
    • 如图,节点 A 向节点 B、D 发送新数据,节点 B 收到新数据后,变成活跃节点,然后节点 B 向节点 C、D 发送新数据。谣言传播非常具有传染性,它适合动态变化的分布式系统

12 | Quorum NWR算法:想要灵活地自定义一致性,没问题!

  • Q:最终一致性和强一致性有什么区别
    • 强一致性能保证写操作完成后,任何后续访问都能读到更新后的值
    • 最终一致性只能保证如果对某个对象没有新的写操作了,最终所有后续访问都能读到相同的最近更新的值,即写操作完成后,后续访问可能会读到旧数据
  • Q:Quorum NWR的三要素
    • N:副本数,又叫复制因子(Replication Factor)
    • W:写一致性级别(Write Consistency Level),表示成功完成W个副本更新,才完成写操作
    • R:读一致性级别(Read Consistency Level),表示读取一个数据对象时需要读R个副本,即,读取指定数据时,要读 R 副本,然后返回 R 个副本中最新的那份数据
    • 注意:无论客户端如何执行读操作,哪怕它访问的是写操作未强制更新副本数据的节点(比如节点 B),但因为 W(2) + R(2) > N(3),也就是说,访问节点 B,执行读操作时,因为要读 2 份数据副本,所以除了节点 B 上的 DATA-2,还会读取节点 A 或节点 C 上的 DATA-2,就像上图的样子(比如节点 C 上的 DATA-2),而节点 A 和节点 C 的 DATA-2 数据副本是强制更新成功的。这个时候,返回给客户端肯定是最新的那份数据
  • Q:N、W、R 值的不同组合,会产生哪两种不同的一致性效果?
    • 当 W + R > N 时,对于客户端来说,整个系统能保证强一致性,一定能返回更新后的那份数据
    • 当 W + R < N 时,对于客户端来说,整个系统只能保证最终一致性,可能会返回旧数据
  • Q:any、one、quorum、all 这4种写一致性级别,具体的含义
    • any:任何一个节点写入成功后,或者接收节点已将数据写入Hinted-handoff缓存(即写其他节点失败后,本地节点上缓存写失败数据的队列) 后,就会返回成功给客户端
    • one:任何一个节点写入成功后,立即返回成功给客户端,,不包括成功写入到 Hinted-handoff 缓存
    • quorum:当大多数节点写入成功后,就会返回成功给客户端。此选项仅在副本数大于 2 时才有意义,否则等效于 all
    • all:仅在所有节点都写入成功后,返回成功