setse 2020-05-04
分布式系统除了提升整个体统的性能外还有一个重要特征就是提高系统的可靠性。提供可靠性可以理解为系统中一台或多台的机器故障不会使系统不可用(或者丢失数据)。保证系统可靠性的关键就是多副本(即数据需要有备份),一旦有多副本,那么久面临多副本之间的一致性问题。一致性算法正是用于解决分布式环境下多副本之间数据一致性的问题的。业界最著名的一致性算法就是大名鼎鼎的Paxos(Chubby的作者曾说过:世上只有一种一致性算法,就是Paxos)。但Paxos是出了名的难懂,而Raft正是为了探索一种更易于理解的一致性算法而产生的。
raft会先选举出leader,leader完全负责replicated log的管理。leader负责接受所有客户端更新请求,然后复制到follower节点,并在“安全”的时候执行这些请求。如果leader故障,followes会重新选举出新的leader。
Raft将一致性拆分为几个关键元素:
Raft将系统中的角色分为领导者(Leader)、跟从者(Follower)和候选者(Candidate)。
Raft要求系统在任意时刻最多只有一个Leader,正常工作期间只有Leader和Followers。Raft算法将时间分为一个个的任期(term),每一个term的开始都是Leader选举。在成功选举Leader之后,Leader会在整个term内管理整个集群。如果Leader选举失败,该term就会因为没有Leader而结束。
Raft 算法将时间划分成为任意不同长度的任期(term)。任期用连续的数字进行表示。每一个任期的开始都是一次选举(election),一个或多个候选人会试图成为领导人。如果一个候选人赢得了选举,它就会在该任期的剩余时间担任领导人。在某些情况下,选票会被瓜分,有可能没有选出领导人,那么,将会开始另一个任期,并且立刻开始下一次选举。Raft 算法保证在给定的一个任期最多只有一个领导人。
Raft 算法中服务器节点之间通信使用远程过程调用(RPC),并且基本的一致性算法只需要两种类型的 RPC,为了在服务器之间传输快照增加了第三种 RPC。
【RPC有三种】:
Raft 使用心跳(heartbeat)触发Leader选举。当服务器启动时,初始化为Follower。Leader向所有Followers周期性发送heartbeat。如果Follower在选举超时时间内没有收到Leader的heartbeat,就会等待一段随机的时间后发起一次Leader选举。
每一个follower都有一个时钟,是一个随机的值,表示的是follower等待成为leader的时间,谁的时钟先跑完,则发起leader选举。(众生平等,每个人都有被选举的权利)
具体过程:
在这个过程中,根据来自其他节点的消息,可能出现三种结果
当有了leader,系统应该进入对外工作期了。客户端的一切请求来发送到leader,leader来调度这些并发请求的顺序,并且保证leader与followers状态的一致性。raft中的做法是,将这些请求以及执行顺序告知followers。leader和followers以相同的顺序来执行这些请求,保证状态一致。leader把请求作为日志条目(Log entries)加入到它的日志中,然后并行的向其他服务器发起 AppendEntries RPC复制日志条目。当这条日志被复制到大多数服务器上,Leader将这条日志应用到它的状态机并向客户端返回执行结果。
共识算法的实现一般是基于复制状态机(Replicated state machines) 。
简单来说:相同的初识状态 + 相同的输入 = 相同的结束状态。引文中有一个很重要的词deterministic
,就是说不同节点要以相同且确定性的函数来处理输入,而不要引入一下不确定的值,比如本地时间等。如何保证所有节点 get the same inputs in the same order
,使用replicated log是一个很不错的注意,log具有持久化、保序的特点,是大多数分布式系统的基石。
因此,可以这么说,在raft中,leader将客户端请求(command)封装到一个个log entry,将这些log entries复制(replicate)到所有follower节点,然后大家按相同顺序应用(apply)log entry中的command,则状态肯定是一致的。
日志在每个节点上是什么样子的呢 :
上图显示,共有 8 条日志,提交了 7 条。提交的日志都将通过状态机持久化到磁盘中,防止宕机。
一般情况下,Leader和Followers的日志保持一致,因此 AppendEntries 一致性检查通常不会失败。然而,Leader崩溃可能会导致日志不一致:旧的Leader可能没有完全复制完日志中的所有条目。
下图阐述了一些Followers可能和新的Leader日志不同的情况。一个Follower可能会丢失掉Leader上的一些条目,也有可能包含一些Leader没有的条目,也有可能两者都会发生。丢失的或者多出来的条目可能会持续多个任期。
Leader通过强制Followers复制它的日志来处理日志的不一致,Followers上的不一致的日志会被Leader的日志覆盖。Leader为了使Followers的日志同自己的一致,Leader需要找到Followers同它的日志一致的地方,然后覆盖Followers在该位置之后的条目。
具体的操作是:Leader会从后往前试,每次AppendEntries失败后尝试前一个日志条目,直到成功找到每个Follower的日志一致位置点(基于上述的两条保证),然后向后逐条覆盖Followers在该位置之后的条目。
详细过程如下:
总结一下就是:当 leader 和 follower 日志冲突的时候,leader 将校验 follower 最后一条日志是否和 leader 匹配,如果不匹配,将递减查询,直到匹配,匹配后,删除冲突的日志。这样就实现了主从日志的一致性。
上图按时间序列展示了Leader在提交日志时可能会遇到的问题。
究其根本,是因为term4时的leader s1在(C)时刻提交了之前term2任期的日志。为了杜绝这种情况的发生:
某个leader选举成功之后,不会直接提交前任leader时期的日志,而是通过提交当前任期的日志的时候“顺手”把之前的日志也提交了,具体怎么实现了,在log matching部分有详细介绍。那么问题来了,如果leader被选举后没有收到客户端的请求呢,论文中有提到,在任期开始的时候发立即尝试复制、提交一条空的log .