阅读笔记（二十四）Raft算法《in search of an understandable consensus algorithm》

r囧r小猫 2023-07-06 04:53 4阅读 0赞

### 一. 简介 ###

paxos算法是Lamport大神提出的共识算法，在众多分布式系统中均有使用，在前文中有对[Paxos算法的分析][Paxos]，以及谷歌运用该算法遇到的问题。但是paxos本身实现起来较为复杂，因此业界出现了另一种更为方便实现的共识算法:Raft。

首先要推荐一个[动画网页][Link 1]，该网页将raft的七八成内容以动画的形式展示了出来，还剩一些细节无法展现或者有所疏漏，但是可以大体上了解该算法的整个原理了。本文不再复述共识算法的背景、原理，也不复述Paxos或者Raft简单的原理，而是重点分析Raft的一些重要的细节以及和Paxos的区别。

### 二. Raft的改变 ###

相对于Paxos，Raft主要做了如下改变：

##### 1. 问题分解 #####

Raft为了更容易的解决共识问题，将问题分解为几个子问题：

*  如何选举leader
 *  如何做日志复制
 *  如何保障安全性
 *  会员(membership)改变问题

除此之外，作者在开发Raft中体现了一个精美的哲学思想：**自由的算法会带来更复杂的实现问题，而严格的限制则相反，可以带来更为简洁精美的算法实现。** 究竟该采取何种方式其实无法直接论断，而是要根据实际场景决定。这是每一个开发者都应该有的思想。

##### 2. 更严格的leader选举策略 #####

类似于Paxo，Raft的节点也有着三种状态：Leader，Candidate和Follower。关系如下图所示，简单总结为：

1.  没有Leader的时候Follower在time out后进阶为Candidate，发出选举申明
2.  Candidate发起选举，得到多数票则成为Leader，发送选举成功申明
3.  其他收到选举成功消息的则进入Follower的状态，直到Leader过期  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70]

整个过程易于理解，而且和Paxos类似，在动图网页中可以很清晰地看到整个过程。下面着重说一下和Paxos的区别所在：

*  Paxos中众生平等，只要你拥有一个序列号，你就可以参与选举，而你的序列号比较小被拒绝了，你可以很快的提出一个更大的序列号继续参与选举。
 *  Raft中定义了term，并且会根据term比较log的数量，当数量超过其他Follower的时候，才能被推选成功，结合下图可以进行清楚地说明。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70 1]

图中从左到右为时间顺序，五个节点中加粗的为Leader，Leader将复制自身日志给其他Follower更新。其中可能更新到一半就断开了，发起了新的选举。而进行到c的时候，如果是Paxos，则可能会进入d也可能会进入e。如果进入了d，则会出现3的日志覆盖了2和4term的日志，从而导致了日志的丢失。而在Raft中，则仅可能出现e的情况，因为只有S1有可能选举成功。这样一来就可以极大的避免了更多更新的日志丢失现象。

##### 3. 日志复制 #####

关于日志复制其实上面已经大概说明了，这里再详细补充一下。如下图所示为Raft的日志复制图。其中第一个是leader，下面是follower。log index指的是日志以索引的形式挨个存放，因此不会出现碎片问题。不同颜色表示不同的term，即不同的leader时代。可以看到，当leader选举成功的时候，有些节点会缺漏了很多日志，这里leader会让他们先通过复制尽快跟上 leader的状态，在这个过程中不参与其他读写活动。这和chain replication也很相似。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70 2]

##### 4. 安全性 #####

这里的安全性理解为以下几点

*  保障选举的leader具有最权威的数据：因此Follower只接受term最新，log的index最多的Candidate
 *  避免出现多个leader的情况：每个Follower仅仅有一次投票机会，投完票之后在该段期间内不允许重复投票。

##### 5. membership change #####

### 总结 ###

本文着重分析了Paxos和Raft的不同，并探讨了Raft一些独到的做法和技术细节，更深入研究该算法还是请阅读原文细细品味。

[Paxos]: https://blog.csdn.net/u013354486/article/details/104081997
[Link 1]: http://thesecretlivesofdata.com/raft/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200315215802550.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200315220430678.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200315222222202.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY=,size_16,color_FFFFFF,t_70