[toc]
三个角色
- Leader:接受客户端请求,并向Follower同步请求日志,当日志同步到大多数节点上后告诉Follower提交日志。
- Follower:接受并持久化Leader同步的日志,在Leader告之日志可以提交之后,提交日志。
- Candidate:Leader选举过程中的临时角色。
Follower只响应其他服务器的请求。如果Follower超时没有收到Leader的消息,它会成为一个Candidate并且开始一次Leader选举。收到大多数服务器投票的Candidate会成为新的Leader。Leader在宕机之前会一直保持Leader的状态。
优化的角色会加上learner
learner设计 https://www.jianshu.com/p/1037fb5a63ac
解决的问题: 分区,leader负载高

Leader选举(Leader Election)
Raft 使用心跳(heartbeat)触发Leader选举。当服务器启动时,初始化为Follower。Leader向所有Followers周期性发送heartbeat。如果Follower在选举超时时间内没有收到Leader的heartbeat,就会等待一段随机的时间后发起一次Leader选举。
Follower将其当前term加一然后转换为Candidate。它首先给自己投票并且给集群中的其他服务器发送 RequestVote RPC
- 赢得了多数的选票,成功选举为Leader;
- 收到了Leader的消息,表示有其它服务器已经抢先当选了Leader;
- 没有服务器赢得多数的选票,Leader选举失败,等待选举时间超时后发起下一次选举。
Q: 时间过长?
两个超时设定
- 心跳超时:Leader周期性的向Follower发送心跳(0.5ms – 20ms),如果Follower在选举超时时间内没有收到心跳,则触发选举。
- 选举超时:如果存在两个或者多个节点选主,都没有拿到大多数节点的应答,需要重新选举,Raft引入随机的选举超时时间(150ms – 300ms),避免选主活锁。
心跳超时要小于选举超时一个量级,Leader才能够发送稳定的心跳消息来阻止Follower开始进入选举状态。可以设置:心跳超时=peers max RTT(round-trip time),选举超时=10 * 心跳超时。
日志同步(Log Replication)
multi-paxos允许日志乱序提交,也就是说允许日志中存在空洞。
raft协议增加了日志顺序性的保证,每个节点只能顺序的commit日志。顺序性日志简化了一致性协议复杂程度,当然在性能上也有了更多的限制,为此,工程上又有了很多对应的优化,如:batch、pipline、leader stickness等等。
约定
- Raft要求所有的日志不允许出现空洞。
- Raft的日志都是顺序提交的,不允许乱序提交。
- Leader不会覆盖和删除自己的日志,只会Append。
- Follower可能会截断自己的日志。存在脏数据的情况。
- Committed的日志最终肯定会被Apply。
- Snapshot中的数据一定是Applied,那么肯定是Committed的。
- commitIndex、lastApplied不会被所有节点持久化。
- Leader通过提交一条Noop日志来确定commitIndex。
- 每个节点重启之后,先加载上一个Snapshot,再加入RAFT复制组
Leader选出后,就开始接收客户端的请求。Leader把请求作为日志条目(Log entries)加入到它的日志中,然后并行的向其他服务器发起 AppendEntries RPC 复制日志条目。当这条日志被复制到大多数服务器上,Leader将这条日志应用到它的状态机并向客户端返回
Followers可能没有成功的复制日志,Leader会无限的重试 AppendEntries RPC直到所有的Followers最终存储了所有的日志条目。
Q:掉线永远复制不成功
Raft日志同步保证如下两点:
- 如果不同日志中的两个条目有着相同的索引和任期号,则它们所存储的命令是相同的。
- 如果不同日志中的两个条目有着相同的索引和任期号,则它们之前的所有条目都是完全一样的。
第一条特性源于Leader在一个term内在给定的一个log index最多创建一条日志条目,同时该条目在日志中的位置也从来不会改变。
第二条特性源于 AppendEntries 的一个简单的一致性检查。当发送一个 AppendEntries RPC 时,Leader会把新日志条目紧接着之前的条目的log index和term都包含在里面。如果Follower没有在它的日志中找到log index和term都相同的日志,它就会拒绝新的日志条目。
Q:pipline的优化
multi-raft复用心跳/通信socket
Q:leader切换导致多个不同
Leader通过强制Followers复制它的日志来处理日志的不一致,Followers上的不一致的日志会被Leader的日志覆盖。
Leader为了使Followers的日志同自己的一致,Leader需要找到Followers同它的日志一致的地方,然后覆盖Followers在该位置之后的条目。
Leader会从后往前试,每次AppendEntries失败后尝试前一个日志条目,直到成功找到每个Follower的日志一致位点,然后向后逐条覆盖Followers在该位置之后的条目。
流程
-
Leader 先将该命令追加到自己的日志中;先持久化再传播
-
Leader 并行地向其它节点发送 AppendEntries RPC
,等待响应;
- 收到超过半数节点的响应,则认为新的日志记录是被提交的:
- Leader 将命令传给自己的状态机,然后向客户端返回响应
- 此外,一旦 Leader 知道一条记录被提交了,将在后续的
AppendEntries RPC
中通知已经提交记录的 Followers
- Follower 将已提交的命令传给自己的状态机
-
如果 Follower 宕机/超时:Leader 将反复尝试发送 RPC;
- 性能优化:Leader 不必等待每个 Follower 做出响应,只需要超过半数的成功响应(确保日志记录已经存储在超过半数的节点上)——一个很慢的节点不会使系统变慢,因为 Leader 不必等他
AppendEntries
一致性检查
Raft 通过 AppendEntries RPC
来检测这两个属性。
- 对于每个
AppendEntries RPC
包含新日志记录之前那条记录的索引(prevLogIndex
)和任期(prevLogTerm
);
- Follower 检查自己的 index 和 term 是否与
prevLogIndex
和 prevLogTerm
匹配,匹配则接收该记录;否则拒绝;
- Leader 通过
nextIndex
来修复日志。当 AppendEntries RPC
一致性检查失败,递减 nextIndex
并重试。
Log Compaction
崩溃恢复(Crash Recovery)
成员变更(Membership Change)
Raft成员变更的工程实践
新成员先加入再同步数据还是先同步数据再加入
|
优点 |
缺点 |
新成员先加入再同步数据 |
简单并且快速,能加入还不存在的成员 |
可能降低服务的可用性 |
新成员先同步数据再加入 |
不会影响服务可用性 |
复杂并且较慢,不能加入还不存在的成员 |
新成员先加入再同步数据,成员变更可以立即完成,并且因为只要大多数成员同意即可加入,甚至可以加入还不存在的成员,加入后再慢慢同步数据。但在数据同步完成之前新成员无法服务,但新成员的加入可能让多数派集合增大,而新成员暂时又无法服务,此时如果有成员发生Failover,很可能导致无法满足多数成员存活的条件,让服务不可用。因此新成员先加入再同步数据,简化了成员变更,但可能降低服务的可用性。
新成员先同步数据再加入,成员变更需要后台异步进行,先将新成员作为Learner角色加入,只能同步数据,不具有投票权,不会增加多数派集合,等数据同步完成后再让新成员正式加入,正式加入后可立即开始工作,不影响服务可用性。因此新成员先同步数据再加入,不影响服务的可用性,但成员变更流程复杂,并且因为要先给新成员同步数据,不能加入还不存在的成员。
https://zhuanlan.zhihu.com/p/359206808
优化点
SetPeer
Raft只能在多数节点存活的情况下才可以正常工作,在实际环境中可能会存在多数节点故障只存活一个节点的情况,这个时候需要提供服务并修复数据。因为已经不能达到多数,不能写入数据,也不能做正常的节点变更。Raft库需要提供一个SetPeer的接口,设置每个节点的复制组节点列表,便于故障恢复。
假设只有一个节点S1存活的情况下,SetPeer设置节点列表为{S1},这样形成一个只有S1的节点列表,让S1继续提供读写服务,后续再调度其他节点进行AddPeer。通过强制修改节点列表,可以实现最大可用模式。
Noop
在分布式系统中,对于一个请求都有三种返回结果:成功、失败、超时。
在failover时,新的Leader由于没有持久化commitIndex,所以并不清楚当前日志的commitIndex在哪,也即不清楚log entry是committed还是uncommitted状态。通常在成为新Leader时提交一条空的log entry来提交之前所有的entry。
RAFT中增加了一个约束:对于之前Term的未Committed数据,修复到多数节点,且在新的Term下至少有一条新的Log Entry被复制或修复到多数节点之后,才能认为之前未Committed的Log Entry转为Committed。即最大化commit原则:Leader在当选后立即追加一条Noop并同步到多数节点,实现之前Term uncommitted的entry隐式commit。
- 保证commit的数据不会丢。
- 保证不会读到uncommitted的数据。
MultiRaft
元数据相比数据来说整体数据量要小的多,通常单台机器就可以存储。我们也通常借助于Etcd等使用单个Raft Group来进行元数据的复制和管理。但是单个Raft Group,存在以下两点弊端:
- 集群的存储容量受限于单机存储容量(排除使用分布式存储)。
- 集群的性能受限于单机性能(读写都由Leader处理)。
对于集群元数据来说使用单个Raft Group是够了,但是如果想让Raft用于数据的复制,那么必须得使用MultiRaft,也即有多个复制组,类似于Ceph的PG,每个PG、Raft Group是一个复制组。
多个复制组共用心跳
还需解决的问题
- 负载均衡:可以通过Transfer Leadership的功能保持每个物理节点上Leader个数大致相当。
- 链接复用:一个物理节点上的所有Raft Group复用链接。会有心跳合并、Lease共用等。
- 中心节点:用来管理集群包括MultiRaft,使用单个Raft Group做高可靠,类似Ceph Mon。
性能优化
Batch
- Batch写入落盘:对每一条Log Entry都进行fsync刷盘效率会比较低,可以在内存中缓存多个Log Entry Batch写入磁盘,提高吞吐量,类似于Ceph FileStore批量的写Journal。
- Batch网络发送:Leader也可以一次性收集多个Log Entry,批量的发送给Follower。
- Batch Apply:批量的Apply已经commit的Log到业务状态机。
Batch并不会对请求做延迟来达到批量处理的目的,对单个请求的延迟没有影响。
PipeLine
Raft依赖Leader来保持集群的数据一致性,数据的复制都是从Leader到Follower。一个简单的写入流程如下,性能是完全不行的:
- Leader收到Client请求。
- Leader将数据Append到自己的Log。
- Leader将数据发送给其他的Follower。
- Leader等待Follower ACK,大多数节点提交了Log,则Apply。
- Leader返回Client结果。
- 重复步骤1。
Leader跟其他节点之间的Log同步是串行Batch的方式,如果单纯使用Batch,每个Batch发送之后Leader依旧需要等待该Batch同步完成之后才能继续发送下一个Batch,这样会导致较长的延迟。可以通过Leader跟其他节点之间的PipeLine复制来改进,会有效降低延迟。
Parallel
顺序提交
将Leader Append持久化日志和向Followers发送日志并行处理。Leader只需要在内存中保存未Committed的Log Entry,在多数节点已经应答的情况下,无需等待Leader本地IO完成,直接将内存中的Log Entry直接Apply给状态机即可。
乱序提交
Out-of-Order
参考:PolarFS: ParallelRaft、BlueStore源码分析之事物状态机:IO保序
乱序提交要满足以下两点:
- Log Entry之间不存在覆盖写,则可以乱序Commit、Apply。
- Log Entry之间存在覆盖写,不可以乱序,只能顺序Commit、Apply。
上层不同的应用场景限制了提交的方式:
- 对IO保序要求比较严格,那么只能使用顺序提交。
- 对IO保序没有要求,可以IO乱序完成,那么可顺序提交、乱序提交都可以使用。
不同的分布式存储需要的提交方式:
- 分布式数据库(乱序提交):其上层可串行化的事物就可以保证数据一致性,可以容忍底层IO乱序完成的情况。
- 分布式KV存储(乱序提交):多个KV之间(排除上层应用语义)本身并无相关性,也不需要IO保序,可以容忍IO乱序。
- 分布式对象存储(乱序提交):本来就不保证同一对象的并发写入一致性,那么底层也就没必要顺序接收顺序完成IO,天然容忍IO乱序。
- 分布式块存储(顺序提交):由于在块存储上可以构建不同的应用,而不同的应用对IO保序要求也不一样,所以为了通用性只能顺序提交。
- 分布式文件存储(顺序提交):由于可以基于文件存储(Posix等接口)构建不同的应用,而不同的应用对IO保序要求也不一样,所以为了通用性只能顺序提交,当然特定场景下可以乱序提交,比如PolarFS适用于数据库。
- 分布式存储:具体能否乱序提交最终依赖于应用语义能否容忍存储IO乱序完成。
简单分析
单个Raft Group只能顺序提交日志,多个Raft Group之间虽然可以做到并行提交日志,但是受限于上层应用(数据库等)的跨Group分布式事物,可能导致其他不相关的分布式事物不能并行提交,只能顺序提交。
上层应用比如数据库的分布式事物是跨Group(A、B、C)的,Group A被阻塞了,分布式事物不能提交, 那么所有的参数者Group(B、C)就不能解锁,进而不能提交其他不相关的分布式事物,从而引发多个Group的链式反应。
Raft不适用于多连接的高并发环境中,Leader和Follower维持多条连接的情况在生产环境也很常见,单条连接是有序的,多条连接并不能保证有序,有可能发送次序靠后的Log Entry先于发送次序靠前的Log Entry达到Follower,但是Raft规定Follower必须按次序接受Log Entry,就意味着即使发送次序靠后的Log Entry已经写入磁盘了(实际上不能落盘得等之前的Log Entry达到)也必须等到前面所有缺失的Log Entry达到后才能返回。如果这些Log Entry是业务逻辑顺序无关的,那么等待之前未到达的Log Entry将会增加整体的延迟。
其实Raft的日志复制和Ceph基于PG Log的复制一样,都是顺序提交的,虽然可以通过Batch、PipeLine优化,但是在并发量大的情况下延迟和吞吐量仍然上不去。
具体Raft乱序提交的实现可参考:PolarFS: ParallelRaft
Asynchronous
我们知道被committed的日志肯定是可以被Apply的,在什么时候Apply都不会影响数据的一致性。所以在Log Entry被committed之后,可以异步的去Apply到业务状态机,这样就可以并行的Append Log和Apply Log了,提升系统的吞吐量。
其实就和Ceph BlueStore的kv_sync_thread
和kv_finalize_thread
一样,每个线程都有其队列。kv_sync_thread
去写入元数据到RocksDB(请求到此已经成功),kv_finalize_thread
去异步的回调上层应用通知请求成功。
ReadIndex
Raft的写入流程时走一遍Raft,保证了数据的一致性。为了实现线性一致性读,读流程也可以走一遍Raft,但是会产生磁盘IO,性能不好。Leader具有最新的数据,理论上Leader可以读取到最新的数据。但是在网络分区的情况下,无法确定当前的Leader是不是真的Leader,有可能当前Leader与其他节点发生了网络分区,其他节点形成了一个Group选举了新的Leader并更新了一些数据,此时如果Client还从老的Leader读取数据,便会产生Stale Read。
读流程走一遍Raft、ReadIndex、Lease Read都是用来实现线性一致性读,避免Stale Read。
- 当收到读请求时,Leader先检查自己是否在当前Term commit过entry,没有否则直接返回。
- 然后Leader将自己当前的commitIndex记录到变量ReadIndex里面。
- 向Follower发起Heartbeat,收到大多数ACK说明自己还是Leader。
- Leader等待 applyIndex >= ReadIndex,就可以提供线性一致性读。
- 返回给状态机,执行读操作返回结果给Client。
线性一致性读:在T1时刻写入的值,在T1时刻之后读肯定可以读到。也即读的数据必须是读开始之后的某个值,不能是读开始之前的某个值。不要求返回最新的值,返回时间大于读开始的值就可以。
注意:在新Leader刚刚选举出来Noop的Entry还没有提交成功之前,是不能够处理读请求的,可以处理写请求。也即需要步骤1来防止Stale Read。
原因:在新Leader刚刚选举出来Noop的Entry还没有提交成功之前,这时候的commitIndex并不能够保证是当前整个系统最新的commitIndex。考虑这个情况:w1->w2->w3->noop| commitIndex在w1;w2、w3对w1有更新;应该读的值是w3
因为commitIndex之后可能还有Log Entry对该值更新,只要w1
Apply到业务状态机就可以满足applyIndex >= ReadIndex,此时就可以返回w1的值,但是此时w2、w3
还未Apply到业务状态机,就没法返回w3,就会产生Stale Read。必须等到Noop执行完才可以执行读,才可以避免Stale Read。
Follower Read
如果是热点数据么可以通过提供Follower Read来减轻Leader的读压力,可用非常方便的通过ReadIndex实现。
- Follower向Leader请求ReadIndex。
- Leader执行完
ReadIndex章节
的前4步(用来确定Leader是真正的Leader)。
- Leader返回commitIndex给Follower作为ReadIndex。
- Follower等待 applyIndex >= ReadIndex,就可以提供线性一致性读。
- 返回给状态机,执行读操作返回结果给Client。
Lease Read
Lease Read相比ReadIndex更近了一步,不仅省去了Log的磁盘开销,还省去了Heartbeat的网络开销,提升读的性能。
基本思路:Leader获取一个比election timeout
小的租期(Lease),因为Follower至少在election timeout
时间之后才会发送选举,那么在Lease内是不会进行Leader选举,就可以跳过ReadIndex心跳的环节,直接从Leader上读取。但是Lease Read的正确性是和时间挂钩的,如果时钟漂移比较严重,那么Lease Read就会产生问题。
- Leader定时发送(心跳超时时间)Heartbeat给Follower, 并记录时间点start。
- 如果大多数回应,那么新的Lease到期时间为
start + Lease(<election timeout)
。
- Leader确认自己是Leader后,等待applyIndex >= ReadIndex,就可以提供线性一致性读。
- 返回给状态机,执行读操作返回结果给Client。
Quorum read
Raft
的读虽然可以发送给 follower
,但还是要从 leader
获取 readIndex
,leader
的压力会很大。使用 quorum read
可以利用 follower
读,减小 leader
的压力, 提高读的吞吐量和性能: Improving Read Scalability in Raft-like consensus protocols
Double Write-Store
我们知道Raft把数据Append到自己的Log的同时发送请求给Follower,多数回复ACK就认为commit,就可以Apply到业务状态机了。如果业务状态机(分布式KV、分布式对象存储等)也把数据持久化存储,那么数据便Double Write-Store,集群中存在两份相同的数据,如果是三副本,那么就会有6份。
接下来主要思考元数据、数据做的一点点优化。
通常的一个优化方式就是先把数据写入Journal(环形队列、大小固定、空间连续、使用3D XPoint、NVME),然后再把数据写入内存即可返回,最后异步的把数据刷入HDD(最好带有NVME缓存)。
元数据
元数据通常使用分布式KV存储,数据量比较小,Double Write-Store影响不是很大,即使存储两份也不会浪费太多空间,而且以下改进也相比数据方面的改进更容易实现。
可以撸一个简单的Append-Only的单机存储引擎WAL来替代RocksDB作为Raft Log的存储引擎,Apply业务状态机层的存储引擎可以使用RocksDB,但是可以关闭RocksDB的WAL,因为数据已经存储在Append-Only的Raft Log了,细节仍需考虑。
数据
这里的数据通常指非结构化数据:图片、文档、音视频等。非结构化数据通常使用分布式对象存储、块存储、文件存储等来存储,由于数据量比较大,Double Store是不可接受的,大致有两种思路去优化:
- Raft Log、User Data分开存:Raft Log只存op-cmd,不存data,类似于Ceph的PG Log。
- Raft Log、User Data一起存:作为同一份数据来存储。Bitcask模型天然Append更容易实现。
ref
- https://shimingyah.github.io/2020/03/浅谈分布式存储之raft/#
- raft论文中文翻译 https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md
- https://github.com/hashicorp/raft
- http://www.philipotoole.com/
- https://github.com/otoolep/hraftd
- https://github.com/RaftLib/RaftLib/wiki/Getting-Started
- https://github.com/feixiao/Distributed-Systems
- https://github.com/happyfish100/fastdfs
- http://www.cs.utexas.edu/~vijay/papers/pebblesdb-sosp17-slides.pdf
- http://www.philipotoole.com/building-a-distributed-key-value-store-using-raft/
- https://www.nosuchfield.com/2019/01/26/Distributed-systems-for-fun-and-profit-study-notes/
- braft https://github.com/baidu/braft/blob/master/docs/cn/raft_protocol.md
- etcd 源码解析 https://jiajunhuang.com/articles/2018_11_20-etcd_source_code_analysis_raftexample.md.html
- https://zhuanlan.zhihu.com/p/348680213
- https://youjiali1995.github.io/raft/raft-todo/
- leader lease https://www.jianshu.com/p/072380e12657