raft协议
2014-09-10
今天把raft协议的论文看了，蛮不错。记录一下。
先说搞笑的，记得好像是paxos论文中说到，“过去的十几年里，把分布式一致性协议做对了的只有一个，那就是paxos”(不一定是原话，大致是这个意思)。事实上paxso确实几乎是一个工业标准，像chubby以及它的开源实现zookeeper，等等都是用的paxos，直到raft出现。这篇论文好像是13年的。
不得不提一下，paxos论文刚投稿的时候，没人看得懂，于是它像垃圾论文无人问津。直到有一天，google的人发现了这篇论文，在工程上使用了它，然后paxos才出名了。于是作者便再写一篇论文paxos make simple阐述一下，以前我读过，只有一个感觉：simple你妹呀！
raft论文的开头是这么写的，“paxos即难懂，又难实现。无论对于教育还是工程角度都它妈蛋疼的要死，还它妈的统治了业界这么多年。现在我要提出一个牛逼的协议，比paxos好理解又好实现”（我知道作者就是要表达这个意思）。赤祼祼地打脸啊~
进入正题了。
基础
一般是5台机器。任一时间有处于3种状态之一：leader,follower,candidate。正常情况下只有一个leader
选主
leader周期性地heartbeat到所有的follower。follower如果能收到leader发来的消息，那么就保持follower状态。如果follower一段时间收到不消息了，则开始新的选主。
首先当前term计数加1，然后给自己投票并向其它结点发投票请求。直到以下三种情况：
- 它赢得选举
- 另一个服务器成为leader
- 持续一段时间没有主机胜出
在选主期间，candidate可能收到来自其它自称为leader的写请求，如果该leader的term不小于candidate的当前term，那么candidate承认它是一个合法的leader并回到follower状态，否则拒绝请求。
如果出现两个candidate得票一样多，则它们都无法获取超过半数投票。这种情况会持续到超时。然后进行新一轮的选举。
使用随机的选举超时，这样不容易发生上面情况。
日志复制
leader收到client写请求后，先写自己的log，然后发到所有服务器，当确认记录已安全复制后，回应client。
每条日志记录会存命令以及term编号，term编号用于检测日志的不一致。
每个提交的记录都是持久的，并且是最终一致的。当log记录成功复投票请求中包含了这个限制：请求中有关于candidate的log信息制到大多数服务器时，记录被提交。如果投票者的log比它新，则拒绝请求。
冲突解决，leader通过强制follower复制自己的log来处理不一致。
安全
举个例子，一个follower可能一段时间不可用，期间leader持续提交了多次log，然后这个follower被选为leader了，那么它会覆盖掉提交的记录。
所以要限制哪些服务器可以被选为leader。使用投票过程阻止candidate选举中获胜，除非它的log包含了所有已提交的记录。
因为要获得超过半数的投票，那么candidate至少要跟大多数的log一样新。这样它拥有所有提交的记录。投票请求中包含了这个限制：请求中有关于candidate的log信息，如果投票者的log比它新，则拒绝请求。
如果follower或candidate崩溃了，那么发给它的请求会失败，raft将无限次的重试。当它恢复后，会继续收到未完成的请求。如果一个服务器完成了请求但尚未回复，接着crash了，那么它重启后会收到相同的请求。