Raft算法学习（一）

今天要写的一切都来自于这篇论文：

In Search of an Understandable Consensus Algorithm

1. 拉贝什岛的民主尝试

话说有一天，川普带着几个人去拉贝什（The rubbish island）岛晒太阳，原本计划一天就走，可天有不测风云，人有旦夕祸福。飓风爱思霍（asshole）袭击了拉贝什岛，他们的船沉了，自此他们失去了所有回到美国的办法。

“放心，我的人民会很快就来救我的”，川普自信满满的对其他人说。

可是于此同时的美国人民在cctv上看到了这一条新闻之后，全都上街游行庆祝去了，一个不愿意透露姓名的海皮（Mr Happy）先生对cctv的记者说：“这他妈的比感恩节还让人想去吃火鸡！（oh，shit，shit，shit！I'm so happy that I want to fXXk!）”

等了很久，川普也没有见到来救他的人。岛上开始出现了抱怨的声音，这个时候陕普提了一个意见：

“我们应该选出一个人来站在最高的地方每天看着有没有过往的船只，然后向他们发求救信号！”

大家都想去做这个事情，因为最高的山峰上有一颗果树，其他地方的果树上结的果子小且酸涩，山顶上的果子却很甜美。

于是，川普，还有另外的几位幸存者陕普，豫普，晋普，粤普，坐在一起商量了一个选举的办法：

1. 每次选出的人，叫做leader，负责坐在山顶上观察来往船只，当然可以吃桃子，但是必须每个一段时间吹响呜呜祖拉告诉我们你还活着；

2. 每个人当leader都有一个任期，任期结束之后开始新的一轮选举；

3. 没有当leader人都叫做follower，follower不用坐在山顶上看船，只需要接受leader发来的信息，并注意呜呜祖拉的声音即可；

4. 如果一段时间内没有接收到呜呜祖拉的声音，follower则会认为leader死了，此时follower不会去营救leader，而是把自己变成candidate，发起选举，并且投给自己一票，然后等待着别人投票给自己；

5. 一旦有candidate获得了多数选票，则成为新的leader，爬上山顶，开始自己的任期；

6. 遵循先来先得和一人一票的精神。

川普觉得还不错，完美的符合了美国的民主选举精神，于是立刻宣布了开始选举，并投了自己一票，其他人还没有反应过来，有的人还没有想好要不要去山顶吹冷风，听到川普的“vote me”之后，懵懵懂懂的投了他一票。

计票结束，川普拿到了包括自己在内的4票，豫普得到了自己的1票，川普登上了山顶，开始了自己的任期，成为了第一任，其他人则坐在平地上晒太阳，听着每隔一段时间就会吹响的呜呜祖拉。

但是任期还没结束，川普的呜呜祖拉突然五分钟还没有响了，这已经过了约定时间了。

这个时候粤普最先反应过来了，吼出了那句振聋发聩的“vote me”，并果断的投了自己一票，陕普也紧随其后喊出了“vote me”。当然了，豫普和晋普因为先听到了粤普的吼声，就把手上的票投给了粤普，选举结束，粤普3票，陕普1票，粤普当选，开始自己的任期，其他人继续成为follower。

陕普问豫普和晋普：“咱三个都是喝着耶露河（The Yellow River）的水长大的同乡，你们为啥要把票投给南方来的小子？”

豫普说：“你恐怕要去学学什么叫做先来先得和一人一票了，我俩先收到了粤普的要求，自然就投了他了，这是规矩。”

川普就此失踪了，再也不见了，剩下四个人，维持着选举制度，虽然经常会出现平票的状态，不过日子还能过。后来他们在这个岛上发现了一个土著叫做星期六的，就把星期六也加入到了选举小组中，从此选举制度就完美的运行下去了。

至于故事后面怎么发展了，我也不知道。

2. 严肃点说问题

现代的分布式数据库带来了海量数据存储计算能力的同时也带来了不少问题，其中最麻烦的就是所谓分布一致性。当然了，聪明的大脑总能想出解决办法，那就是Paxos，但是所有的人都说这个算法太难以理解了。难以理解就代表着这种算法很难走出校园，走出实验室，有时候工程上使用的东西并不是那么的先进，但是足够好用，这就可以了。

于是Raft应运而生。先来看看论文里如何描述Raft：

Raft is a consensus algorithm for managing a replicated
log. It produces a result equivalent to (multi-)Paxos, and
it is as efficient as Paxos, but its structure is different
from Paxos; this makes Raft more understandable than
Paxos and also provides a better foundation for building
practical systems.

Raft是一种用于管理复制日志的一致性算法。它提供和Paxos一样的效果和性能，但是它的结构却和Paxos不同；Raft比Paxos更容易理解，并且同样能为构建实用系统的基础。

其实关键点就一点：

• Paxos太难了，Raft又简单又好用。

就上面的故事，我今天先从选举算法开始写，选举只是Raft的一部分，绝对不是全部。

状态

上面这张图表示了状态的转换过程，画的比较符合美国人的思维，乱七八糟的。

• 最开始的时候，所有人都是Follower；
• 选举开始后，所有人都变成了candidate，并增加自己的任期号；
• 紧接着投票给自己并向集群内发送广播要求投票给自己；
• 获得多数选票的candidate变成leader，开始自己的任期，其他的人变成follower。

选举什么时候结束呢？论文中描述了三种条件：

1. candadiate变成了leader；
2. 它发现了集群中又一个节点已经是leader了；
3. 这一轮选举没有人获胜，只能停下，等待下一轮选举。

这里还有一个概念叫做任期：

任期

这是一段任意划分的时间，每个任期都是由选举开始的，任期都有任期号，是连续的整数。

选举开始以后，节点A发起了请求：

选举开始

这样的得到的结果无非几种：

A当选，如图：

A当选 A当选

平票，如图：

选举失败

Raft算法还有很多部分，选举只是启动一部分，但是也很重要，因为只有leader才能处理请求，提供服务，因此选主是很重要的，没有了主集群也就没有办法使用了。

3. 小结

Raft算法广泛运用在很多分布式系统上，因为其理解起来简单，不过理解简单和实现又是两回事，优秀的实现带来的性能也更优秀。

我计划学习研究吃透Raft算法之后，再看看几个现成的分布式数据库的具体实现。