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了,那么它重启后会收到相同的请求。

集群成员变动

raft