什么是一致性
CAP理论，对于一个分布式系统，不能同时满足以下三点：
- 一致性(Consistency)
- 可用性(Availability)
- 分区容错性(Partition Tolerance)
一致性模型
- 弱一致性：最终一致性，DNS、Gossip(Cassandra通信协议)
- 强一致性：Paxos、Raft、ZAB
Zookeeper使用的ZAB（Zookeeper Atomic Broadcast）协议对Paxos进行了很多的改进与优化。
Raft是斯坦福的Diego Ongaro、John Ousterhout两个人以易懂（Understandability）为目标设计的一致性算法，在2013年发布了论文：《In Search of an Understandable Consensus Algorithm》
从2013年发布到现在不过只有两年，到现在已经有了十多种语言的Raft算法实现框架，较为出名的有etcd。
分布式共识问题
共识问题是指多个节点对某个事情达成一致的看法，即使是在部分节点故障、网络延时、网络分割的情况下。
Raft算法介绍
强一致性、去中心化、高可用、leader-based （与之对应的是leader-less算法）的分布式协议。Raft主要通过“问题分解”和“状态简化”来达到易于理解的目标。
Raft协议的工作原理简要概括：
Raft会先选举出leader，leader完全负责replicated log的管理。leader负责接受所有客户端更新请求，然后复制到follower节点，并在“安全”的时候执行这些请求。如果leader故障，followes会重新选举出新的leader。
三个子问题
1. Leader election
Leader election
节点的三个状态
- leader
- follower
- candidate
随机的election timeout：150ms ~ 300ms
通过随机的超时时间避免平票问题。
系统中只能有一个leader，如果一段时间内，发现没有leader，则大家通过选举投票选出leader，leader 会不停的给follower发送心跳消息，表示自己存活，如果leader故障，那么follower 会转为candidate，重新选举出leader。
term
term
Raft将时间划分成任意的长度周期。Terms可以理解为逻辑周期，用连续的整数表示。在分布式环境中，时间同步很重要，同时是一个难题。在Raft中使用了一个可以理解为周期（任期）的概念，用Term作为一个周期，每个Term都是一个连续递增的编号，每一轮选举都是一个Term周期，在一个Term中只能产生一个Leader。
每个term伴随着一次election，一个或多个Candidate试图成为leader。如果某个Candidate赢得了这次election，它将升级为剩余server的leader。在某些election的情形中，会产生平票（Split Votes）的结果 ，即投票结果无效，随后一次新的term开始。raft确保在某个term至多有一个leader。
选举过程
- 增加节点本地的 current term， 切换待candidate 状态
- 投自己一票
- 并行给其他节点发送 RequestVote RPCs
- 等待其他节点的回复
在上述过程中，根据来自其他节点的消息，可能出现三种情况：
- 收到majority(大多数)的投票（含自己的一票），则赢得选举，成为leader
- 被告知别人已经当选为，那么自行切换换为follower
- 一段时间内没有收到majority（大多数）投票，则保持candidate（候选者），重新发起选举
第一种情况，赢得选举后，新leader 会立刻给所有节点发消息，广而告之，避免其余节点出发新的选举。在这里我们回到投票者的视角，投票者如何决定是否给一个选举者投票的的呢？有以下约束：
- 在任意 term 内，每个节点最多只能投一票
- 候选人知道的信息不能比自己的少
- first-come-first-served 先来先得
第二种情况：比如有三个节点A B C。A B同时发起选举，而A的选举消息先到达C，C给A投了一票，当B的消息到达C时，已经不能满足上面提到的第一个约束，即C不会给B投票，而A和B显然都不会给对方投票。A胜出之后，会给B,C发心跳消息，节点B发现节点A的term不低于自己的term，知道有已经有Leader了，于是转换成follower。
第三种情况：没有任何节点获得 majority(大多数)投票--平票。 如果出现平票的情况，那么系统是不可用的（没有leader是不能处理客户端写请求的）。因此Raft 引入了randomized election timeouts来尽量避免平票的情况，同时，leader-based共识算法中，节点的数目都是奇数个，尽量保证majority 的出现。
2. Log replication
Log replication
只有主节点可以处理客户端的请求。
Each change is added as an entry in the node's log.
当系统（leader）收到一个来自客户端的写请求，到返回给客户端，整个过程从leader的视角来看会经历以下步骤：
- leader append log entry
- leader issue AppendEntries RPC in parallel
- leader wait for majority response
- leader apply entry to state machine
- leader reply to client
- leader notify follower apply log
Client处理结果的三种情况
成功、失败、Unknow(Timeout)
需要客户端自己处理Unknow(Timeout)的问题。
3. Safety
Election safety
选举安全性。 即任意 term内最多一个leader被选出。在一个复制集中，任何时刻只能有一个leader，系统中同时又多余一个leader， 称之为脑裂（brain spilt），这是非常严重的问题，会导致数据覆盖。
在Raft 中一下两点保证了这个属性：
- 一个节点某一任期内最多只能投一票
- 只能获得majority 投票的节点才能成为leader。
因此某一任期内一定只有一个leader。
Leader Completeness
这里所说的完整性是指Leader日志的完整性，当Log在Term1被Commit后，那么以后Term2、Term3…等的Leader必须包含该Log；Raft在选举阶段就使用Term的判断用于保证完整性：当请求投票的该Candidate的Term较大或Term相同Index更大则投票，否则拒绝该请求
Leader Completeness
这里所说的完整性是指Leader日志的完整性，当Log在Term1被Commit后，那么以后Term2、Term3…等的Leader必须包含该Log；Raft在选举阶段就使用Term的判断用于保证完整性：当请求投票的该Candidate的Term较大或Term相同Index更大则投票，否则拒绝该请求
Log matching
如果两个节点上的某一个log entry的log index相同且term相同，那么在该index之前所有log entry 应该都相同。
如何做到的只要依赖以下两点：
- If two entries in different logs have the same index and term, then they store the same command.
- If two entries in different logs have the same index and term, then the logs are identical in all preceding entries.
State Machine safety
If a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index.
所有节点在同一位置（index in log entriex）都应用同样的日志。
如何保证这一点呢？
在某个leader选举成功后，不会直接提交前任leader 时期的日志，而是通过提交当前任期的日志的时候，‘顺手’把之前的日志提交了。如果leader 选举之后没有收到客户端的请求呢？，在任期来时的时候立即尝试复制、提交一条空 log。
网友评论