In Search of an Understandable Consensus Algorithm (Extended Version)
一致性算法
从之前GFS论文中，可以看出对于有状态服务，single master with state replicated、lease、 transaction operation是个通用的过程。GFS论文描述神似隐含了一个相关基础组件的描述。
Google内部分布式锁组件的论文The Chubby lock service for loosely-coupled distributed systems 待读
consensus algorithm即解决该问题的算法。最常被提及的两个算法paxos、raft，本篇先看raft。
raft
paxos过于复杂，多数工程上的实践都使用改进版本的paxos，然而任然很复杂。论文提出一种简化版的consensus algorithm。
safety
node的角色：leader、follow、candidate
raft是以一个replicated state machine作为驱动，类数据库事务，使用log + snapshot，log index是连续递增的
term是递增的数，用来作为逻辑上的时钟
限制：
- 任何时刻最多只有一个leader
- leader只做append-only的操作
- 如果两个log有相同的index和term，那么index及之前的entry在两个log中是相等的
- leader completeness: 如果一个entry已经在某个term中commited，那么在更高的term中一定也是commited
- state machine safety: 如果一个server apply了一个log到它的state machine里，其它server apply的对应的log一定是一样的
leader election
- follower如果没有收到leader或candidate的rpc请求超过election timeout时间之后，会从follower转换成candidate
- 然后发起选主流程，increment持有的term，然后向其它server发RequestVote请求
- 接收端check term和log index，如果term > currentTerm && log index >= currentIndex，接受，更新currentTerm、voteFor
AppendEntries
leader将entries发送到半数其它node上之后即可将log更改为commited状态
其它
对比GFS论文中master状态的更新，可以看到两者有很多相似的过程，raft巧妙的设计使其很适合应用在这类scene中
