RAFT

http://thesecretlivesofdata.com/raft/

非拜占庭模型,可以挂,但不能发送坏消息。

每个节点都可能在三个状态之一: - follower - candidate - leader

all out nodes start in followers, if followers don’t hear from a leader then they can be candidate, request for vote, become leader.

All changes to the system now go through the leader.

所有写请求都会先路由到 leader, lear 先写 log,分发 log,其他 node ack log 后,leader 写数据,the others 写数据。

领导租约

election timeout - a follower waits until becoming a candidate,每个节点的 election timeout 是一个随机值,150-300ms。

-> become candidate

-> request for vote

-> other nodes vote 后 reset election timeout.

收到票数超过约定后,broadcast to the others:我是 modex, 收到了几条 vote,become leader.

heartbeat timeout

Append Entries Timeout

headerbeat timeout 后重复上述过程产生新的 leader,term 2,第二个任期。

split vote

多等一轮,等其他人 election timeout 成为 candidate - vote - leader

append entry

更新 log 后就可以给 client response 了。

partial networks 也可以保持一致性

多数派更新 log 后才给 response,否则只写 log 不给 response

为什么有复杂的一致性算法?

分布式系统的核心问题:没有统一时钟。不然可以简单按时序处理。

extensions

DC awareness 跨机房处理

sharding

split is idempotent ?

可用性

保障四个九,不是通过不出错,而是错误可以自动恢复。