共识算法zk和raft学习笔记

作者: DayDayUpppppp | 来源:发表于2021-06-20 14:27 被阅读0次

还在整理中，还是乱七八糟的状态.... （哎，先就这样吧...

分布式一致性协议的目的

分布式一致性涉及的目的源于，为了避免单点故障导致系统无法使用。于是，把数据复制到多个节点。一旦数据出现了多份，就会引入数据在多个节点之间的一致性问题。

(省略了概念，先整理了zk和raft选举流程...）

1. zk选举流程

zk有两种模式，分别是恢复模式和广播模式。当一个集群没有选举出leader或者leader心跳丢失，需要重新选举。系统会进入恢复模式，选举leader。zk的选举规则是：每个节点的投票包含（server-id，zxid），投票规则是：

1. zxid不同的话，选择zxid大的
2. 如果zxid相同的话，选择server-id大的

sid：每个机器都不相同，解决zxid相同时，尽量快速收敛投票，完成选举。
zxid：被推举的Leader事务ID，类似于raft中的任期id。
任期id约大，表示自己的同步到的信息越多，越应该成为leader。

leader选举完成之后，会进入同步模式。leader把自己的数据同步给follow节点。保持一个集群中的数据是不断同步的。

2. zk的数据读写流程

客户端读数据流程：
客户端发起读请求，leader或follower都可以响应此请求，斌不需要一定由leader处理，返回自己的数据。
客户端写数据流程：
1. 客户端发起写请求
2. 如果请求发送给leader，那么leader开始写操作；如果请求发送到follower节点，请求被转发到leader节点。
3. leader节点发起一次quorum写入，确保数据被写入集群中的大多数节点。
4. 返回给客户端ack，表示数据接入成功。

按照zk的规则，是可能出现两个不同的客户端在zk的集群上读到不同的数据的。比如，一个集群有10个节点，客户端a的写请求被更新到其中的6个节点之后，leader通知客户端a数据写入成功。客户端b发起读请求，读请求发送到了还没有更新到的另外4个节点上。于是，客户端b就会读到未更新的数据。如果客户端A和客户端B读取相同的值很重要，则客户端B应该在执行读取之前从ZooKeeper API方法调用sync()方法。

zk的官方文档也提到了这一点

raft算法

raft算法的基本规则，raft也是zk类似的思路，分为两步，选举和同步。用raft的官方名词是：leader选举和日志复制。当集群没有leader的时候，或者心跳出问题的时候会触发leader选举。每个节点都会随机出一个timeout，在这个timeout内没有收到leader的心跳，就认为leader失效，开始选举。（随机timeout为了让投票尽快收敛选出leader，和zk每个节点不同的sid本质是一个思路）

完成选举之后，会进入日志复制的阶段。raft的一致性的设计想法是，每个节点都是被看作一个状态机，外部的命令视为输入。如果每个阶段的输入一致的话，那么它们的状态就一定是一致的。在raft的集群中，leader节点把客户端的请求同步转化为命令日志操作，然后转发给其他节点，其余的节点收到日志命令之后，作为输入修改自己的状态机。如果输入一致，那么每个节点的状态必然是一致的。

raft的数据读写流程如下，和zk不同的是，raft的leader是一个强leader，读写请求都必须都要有leader来处理。raft是满足读写的线性一致性的，而zk由于读可以到任意一个follow节点去读，优点是提高了zk集群的读性能，但是可能出现数据不一致case。上面已经提到了这一点。而在raft的设计中，follower的作用是保持自己和leader是同步的，一旦leader出问题触发选举，由其余的follower担任leader。

收到写请求时：
1. leader收到写请求，leader把操作改为同步命令，发送到其他的follow节点
2. follow节点收到之后，回复rsp。
3. leader收到rsp超过半数之后，完成了一些quorum写入，认为拥有数据的节点已经过半，于是commit记录。commit idx++。
4. commit idx++同步给其他follow节点，follow节点收到之后，在自己的状态机应用这条命令，改变自己的状态。follow节点的apply index++。
当收到读请求的时(ReadIndex 算法)：
1. leader收到写请求的时候，把自己的read idx = commit idx
2. leader发起给其他的follow发起一次心跳，收到超过半数的rsp（确认自己是leader）
3. 自己的apply idx 超过commit idx（保证读到的数据是leader，而且满足线性一致性）
4. Leader 执行 read 请求，将结果返回给 client

更加具体的细节问题：

在raft算法中，提供的是线性一致性。什么是线性一致性？
具体可以推荐简单的来说，就是强一致性。让多个副本对应用来说就像一个副本。
日志复制具体是怎么做的？

每个日志复制请求包括状态机命令 & 任期号，同时还有前一个日志的任期号和日志索引。状态机命令表示客户端请求的数据操作指令，任期号表示leader的当前任期。

基于以上这个原因，要想实现线性一致性读，一个较为简单通用的策略就是：每次读操作的时候记录此时集群的 commited index，当状态机的 apply index 大于或等于 commited index 时才读取数据并返回。由于此时状态机已经把读请求发起时的已提交日志进行了 apply 动作，所以此时状态机的状态就可以反应读请求发起时的状态，符合线性一致性读的要求。这便是 ReadIndex 算法。

不过，我们在叙述的过程中忽略了一个很重要的点：如何准确获取集群的 commited index ？如果获取到的 committed index 不准确，那么以不准确的 committed index 为基准的 ReadIndex 算法将可能拿到过期数据。

为了确保 committed index 的准确，我们需要：让 leader 来处理读请求；如果 follower 收到读请求，将请求 forward 给 leader；确保当前 leader 仍然是 leader；

leader 发起一次广播请求，如果还能收到大多数节点的应答，则说明此时 leader 还是 leader。这点非常关键，如果没有这个环节，leader 有可能因网络分区等原因已不再是 leader，如果读请求依然由过期的 leader 处理，那么就将有可能读到过去的数据（我们将在下一个小节聊聊这个细节）；这样，我们从 leader 获取到的 commited index 就作为此次读请求的 ReadIndex。

https://zhengyinyong.com/post/etcd-linearizable-read-implementation/