Raft论文读书笔记

Raft是当前分布式领域最重要的一致性算法之一,今天我们就来好好研究研究这个算法的[论文][1], 还有对应[网站][2], [动画][3], 不想看英文的也有中文的[翻译][4],所以我这边就不翻译了,主要还是记录一下论文重点和自己的心得。

Raft算法作者的初衷是对标Paxos算法(过去十年分布式一致性的事实标准),但是要比它更易理解,主要手段有:
1. 分解,把整个一致性问题拆分为**Leader选举**、**日志复制**和**安全机制**这**三大方面**还有**角色改变**这个小方面。所以**模块化**是一个软件系统可维护、理解和扩展的不二手段。
2. 减少状态空间的状态,相比于Paxos,Raft减少了非确定性和服务器之间可以处于不一致的方式。所以在复杂的问题上**做减法**,可以减少很多不必要的繁琐的步骤。

Raft使用了更强的Leader,感觉这和我之前看的[OceanBase][5]是相似的,就是增强Leader(UpdateServer)或者说**单点**的作用,加重中心化(这也是社会的运作方式,没有Leader就是大家一盘散沙,文明是达不到今天这个程度的),要做决策就先选择一个Leader,然后让他去协调所有的决议,会更加简单快速,而Paxos就是P2P或者说弱Leader的方式。事实上,我们之所以使用分布式系统也是迫不得已,如果单台机器能搞定还要这么多系统干嘛?所以我们也要看到单点系统的好处,那就是一致性很容易保证,所以在**分布式系统中使用一个增强(能力和责任)的单点**既利于一致性的保证也能获得分布式的优势。

Leader全权负责管理日志复制,从而实现一致性,所以有了Leader这一机制,一致性问题就可以被分解为上述三大方面了,下面分别说明。

1. Raft 的 Leader 是有 Term 时间限制的,类似于[租约机制][6],这个机制能完善单纯的心跳(因为有的机器太忙可能发不出或没法响应心跳)。
随机的选举超时时间可以使得 **Leader 选举**很少有选票平分的时候,按 `Term number` 最大和先来先服务原则可以使得每一个 Term 内最多有一个 Leader(如果没有 Leader 就会超时进入下一个 Term 进行新的选举)。Leader 保持身份并阻止其他节点成为 Leader 的方法是不停地向其他节点发送心跳消息(也包含需要复制的日志)。

2. Leader 为客户端服务,处理所有客户端请求亦即**所有的系统变更**,并把**日志复制**分发给其他节点(包含失败重试),leader 处理日志不一致的手段是强制follower 复制自己的日志,所以 follower 中与 leader 冲突的日志会被覆盖,leader 不删除自己的日志(只附加原则)。

3. leader选举和日志复制都需要一些**安全机制**来保证每个状态机都按照相同的顺序来执行相同的指令:
①. 选举限制,除了1中的条件,还要求 candidate 具有已经提交的所有日志条目,所以 voter 会主动拒绝日志没有自己新(通过Term Number 和 日志长度 两个指标进行比较)的候选人的投票请求。
②. 提交之前Term内的日志条目时,Leader 会使用这个条目的原始Term Number,而不是使用当前的Term Number,这样更容易辨别日志,而且要提交之前Term(如 2 )的日志时必须同时提交当前Term(如 4)的日志,保证得到复制日志的 follower A 下次更有可能成为Leader而不是那些只有较旧日志但是新于A得到的旧日志(如 3 新于 2 )的follower

如果 follower 或者 candidate 崩溃了,那么后续发送给他们的请求都会失败。Raft 中处理这种失败就是简单的通过无限的重试,因为Raft的这种请求都是幂等的,所以这样重试不会造成任何问题。比如,一个follower如果收到附加日志请求但是他已经包含了这一日志,那么他就会直接忽略这个新的请求。

Leader 选举是 Raft 中对时间要求最为关键的方面。只要系统满足下面的时间要求:

> 广播时间(broadcastTime) << 选举超时时间(electionTimeout) << 平均故障间隔时间(MTBF)

Raft 就可以选举并维持一个稳定的Leader。当**Leader崩溃后,整个系统会大约相当于选举超时的时间里不可用**,广播时间和平均故障间隔时间是由系统决定的,但是选举超时时间是我们自己选择的, Raft的请求 要接收方将信息持久到存储中去,所以广播时间大约是 0.5 毫秒到 20 毫秒,取决于存储的技术。因此,选举超时时间可能需要在 10 毫秒到 500 毫秒之间。大多数的服务器的平均故障间隔时间都在几个月甚至更长,很容易满足时间的需求。

集群状态切换通过一个**共同一致**(新老配置的结合)的中间状态转换实现,这样**基于两阶段**的做法可以使得集群平滑地进行状态迁移。

阅读原文:[Mageekchiu][7]

[1]: https://ramcloud.atlassian.net/wiki/download/attachments/6586375/raft.pdf
[2]: https://raft.github.io/
[3]: http://thesecretlivesofdata.com/raft/
[4]: https://github.com/maemual/raft-zh_cn
[5]: https://segmentfault.com/a/1190000013522687#articleHeader4
[6]: https://segmentfault.com/a/1190000014503967#articleHeader8
[7]: http://mageek.cn/archives/101/

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: Raft论文读书笔记


FavoriteLoading添加本文到我的收藏
  • Trackback 关闭
  • 评论 (1)
    • 8zu
    • 2018/08/15 6:49上午

    maybe you need a markdown plugin

您必须 登陆 后才能发表评论

return top