The Consensus Algorithm - Raft
There is only one consensus protocol, and that’s Paxos - all other approaches are just broken versions of Paxos. Ironic, hard enough to understand compared to the Raft. There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system. . . . the final system will be based on an un-proven protocol.
--Chubby Implementer
拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。这10支军队在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队（一半以上）同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵骑马相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们才能保证有多于6支军队在同一时间一起发起进攻，从而赢取战斗？
拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信道绝无问题。Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以，在研究拜占庭将军问题的时候，已经假定了信道是没有问题的。
共识算法分为两类：Crash Fault Tolerance（CFT）和Byzantine Fault Tolerance（BFT）；
对于大部分分布式集群来说，集群节点和网络消息一般是可控的，只会出现节点故障而不会出现拜占庭错误那样的伪造和欺骗的网络消息。
并发控制
服务器节点对于资源的管理需要满足并发控制的机制，事务T对某一个服务器节点的资源对象S的并发访问在事务U之前， 需要保证所有服务器节点上对S和其他资源对下那个的冲突访问，T始终在U之前。
-
锁并发控制
-
事务T锁住了服务器节点X上的资源A，进行写操作
-
事务U锁住了服务器节点Y上的资源B，进行写操作
-
事务T尝试读取服务器节点Y上的资源B，此时B被事务U锁住，因而事务T等待锁释放；
-
事务U尝试读取服务器节点X上的资源A，此时A被事务T锁住，因而事务U等待锁释放；
上述出现分布式事务之间的循环依赖导致死锁的场景，需要有机制检测死锁，然后通知协调者，放弃某个事务；
-
-
时间戳并发控制
- 协调者在每个事务启动的时候会分配一个全局唯一的时间戳，所有的事物均在统一的时间轴上运行，通过按照访问对象的事务时间戳顺序提交资源对象的版本来强保证事务执行的串行等价性。
-
乐观并发控制
- 各个并发事务在执行完成之后执行检测是否冲突，如果确实冲突就放弃一些事务，然后让客户端重新启动这些事务进行重试。每个事务在提交前检测验证
-
多版本并发控制
- 多版本是MVCC实现的基础。
What is Raft
Raft is a consensus algorithm that is designed to be easy to understand. It’s equivalent to Paxos in fault-tolerance and performance. The difference is that it’s decomposed into relatively independent sub-problems, and it cleanly addresses all major pieces needed for practical systems. We hope Raft will make consensus available to a wider audience, and that this wider audience will be able to develop a variety of higher quality consensus-based systems than are available today.
tl;dr: Raft (thesecretlivesofdata.com)
Raft decomposes the consensus problem into three relatively independent sub-problems:
- Leader election: a new leader must be chosen when starting the cluster and when an exsiting leader fails.
- Log replication: the leader must accept log entries from clients and replicate them across the cluster, forcing the other logs to agree with its own.
- Safety: if any server has applied a particular log entry to its state machine, then no other server may apply a different command for the same log index. (the State Machine Safety Property)
The basic elements of Raft show as belows:
The main procedure of Raft depicted as follows:
Five things to be determinately implemented:<br/>
Election safety, at most one leader can be elected in a given term.
Leader append-only, never delete or overwrites entries, only append entries.
Log matching, to be perfect
Leader completeness, to be complete
State machine safety, the only entry for the a given index.
ensure above the five properties are correctly executed, then the Raft is achieved.
A Raft cluster contains several servers, five is a typical number and tolerates two failures at the same time.
At a given time, each server is one of three states: leader, follower, or candidate. In normal operation, only one leader and the others followers. Followers only respond to leader and candidates. Leader handles all the client requests. If a client contacts a follower, the follower will redirects it to the leader. Candidates work when electing a new leader.
Time is divided into terms, and each term begins with election. After election, the leader works for the rest of the term. A new election will begin shortly after a split vote. Raft ensures at most one leader in a given term.
Different severs may observer the transitions between terms at different time, and in some situations a server may not observe an election or entire terms. Terms act a logical clock, which allows servers to detect obsolete information such as stale leaders. Each server stores a current-term number, which increases monotonically.
Raft servers communicate use remote procedure calls (RPCs), two type of RPCs is need for the consensus algorithm: RequestVote RPCs and AppendEntries RPCs.
