分布式共识算法

一份随时可能发生变化的数据如何在不同集群节点之间同步:

  • 状态转移:通过全同步复制的方式,只有所有节点都完成更改,数据才算写入成功
  • 操作转移:保证节点初始状态与接收到的操作序列一直 最终数据也能保持一致

一旦系统中过半数的节点中完成了状态的转换,就认为数据的变化已经被正确地存储在系统当中,这样就可以容忍少数(通常是不超过半数)的节点失联,使得增加机器数量对系统整体的可用性变成是有益的,这种思想在分布式中被称为“Quorum机制“

在分布式系统中,解决共识的复杂度在于:

  1. 网络各个节点通讯不可靠 消息可能会延迟或者丢失
  2. 系统对外提供的访问是可以并发的

当以下3根问题被同时解决,即达成共识:

  • 如何选主
  • 如何将数据复制到各个节点
  • 如何保证过程安全

Paxos

对多个节点产生的值,该算法能保证只选出唯一一个值

节点类型

  • 提议者(Proposer):提议一个值
  • 决策者(Acceptor):对每个提议进行投票
  • 记录者(Learner):被告知投票的结果,不参与投票过程

202031620538

屏幕截图 2020-11-18 144409

Paxos描述了这样一个场景,有一个叫做Paxos的小岛(Island)上面住了一批居民,岛上面所有的事情由一些特殊的人决定,他们叫做议员(Senator)。议员的总数(Senator Count)是确定的,不能更改。岛上每次环境事务的变更都需要通过一个提议(Proposal),每个提议都有一个编号(PID),这个编号是一直增长的,不能倒退。每个提议都需要超过半数((Senator Count)/2 +1)的议员同意才能生效。每个议员只会同意大于当前编号的提议,包括已生效的和未生效的。如果议员收到小于等于当前编号的提议,他会拒绝,并告知对方:你的提议已经有人提过了。这里的当前编号是每个议员在自己记事本上面记录的编号,他不断更新这个编号。整个议会不能保证所有议员记事本上的编号总是相同的。现在议会有一个目标:保证所有的议员对于提议都能达成一致的看法

一些paxos原型描述:https://www.douban.com/note/208430424/

最原先的Paxos被称为 Basic Paxos,但这个算法如果两个提案节点互不相让地争相提出自己的提案,抢占同一个值的修改权限,就会产生活锁问题

Multi Paxos

Multi Paxos对Basic Paxos的核心改进是增加了“选主”的过程

一旦系统有了主节点,用户的操作请求都将直接在主提案节点上操作:

屏幕截图 2020-11-18 145350

这就跟zk的算法很像了

实现数据的复制同步只需达到节点总数的一半就可以提交 数据将会生效

许多说法都会提出为了防止产生网络分区,也就说节点之间网络不通,但是还能够向外提供服务,产生脑裂问题,所以通过设置节点数不能小于总数的一半,但实际上这种情况十分少见。 本质上,容忍一半以下节点更多地是为了允许一定量的节点下线,是为了可用性

Raft

分布式一致性协议,主要是用来竞选主节点

有三种节点:Follower、Candidate 和 Leader。Leader 会周期性的发送心跳包给 Follower。每个 Follower 都设置了一个随机的竞选超时时间,一般为 150ms~300ms,如果在这个时间内没有收到 Leader 的心跳包,就会变成 Candidate,进入竞选阶段

竞选阶段Candidate会向其他节点发送投票请求,Follower同意投票则向该Candidate回复同意投票

当 Candidate获得超过半数票时,就成为Leader节点 如果有多个Candidate获得相同的票数,则重新开始投票 每个节点设置的随机竞选超时时间不同,因此下一次再次出现多个 Candidate 并获得同样票数的概率很低

数据同步

  • 自客户端的修改都会被传入 Leader。此时该修改还未被提交,只是写入日志中
  • Leader 会把修改复制到所有 Follower
  • Leader 会等待大多数的 Follower 也进行了修改,然后才将修改提交
  • 此时 Leader 会通知的所有 Follower 让它们也提交修改,此时所有节点的值达成一致

Goossip协议

最终一致性的分布式共识协议

  • 系统中不一致的状态有可能会在一定时间内被外部直接观察到

2020111815129

两种传播方式:

  • 反熵:全量同步数据
  • 传谣:只对外发送变更消息
MY all right reserved,powered by Gitbook该页面最后修改于: 2021-03-12 14:59:02

results matching ""

    No results matching ""

    results matching ""

      No results matching ""