一分布式共识算法(ConsensusAlgorithm)
1如何理解分布式共识?
多个参与者针对某一件事达成完全一致:一件事,一个结论。
已达成一致的结论,不可推翻。
2有哪些分布式共识算法?
Paxos:被认为是分布式共识算法的根本,其他都是其变种,但是paxos论文中只给出了单个提案的过程,并没有给出复制状态机中需要的multi-paxos的相关细节的描述,实现paxos具有很高的工程复杂度(如多点可写,允许日志空洞等)。
Zab:被应用在zookeeper中,业界使用广泛,但没用抽象成通用library。
Raft:以容易理解著称,业界也涌现出很多raft实现,比如etcd、braft、tikv等。
二Raft介绍
1特点:StrongLeader
系统中必须存在且同一时刻只能有一个leader,只有leader可以接受clients发过来的请求。
Leader负责主动与所有followers通信,负责将“提案”发送给所有followers,同时收集多数派的followers应答。
Leader还需向所有followers主动发送心跳维持领导地位(保持存在感)。
另外,身为leader必须保持一直heartbeat的状态。
2复制状态机
对于一个无限增长的序列a[1,2,3…],如果对于任意整数i,a的值满足分布式一致性,这个系统就满足一致性状态机的要求。
基本上所有的真实系统都会有源源不断的操作,这时候单独对某个特定的值达成一致显然是不够的。为了让真实系统保证所有的副本的一致性,通常会把操作转化为write-ahead-log(WAL)。然后让系统中所有副本对WAL保持一致,这样每个副本按照顺序执行WAL里的操作,就能保证最终的状态是一致的。
Client向leader发送写请求。
Leader把“操作”转化为WAL写本地log的同时也将log复制到所有followers。
Leader收到多数派应答,将log对应的“操作”应用到状态机。
回复client处理结果。
3Raft中的基本概念
Raft-node的3种角色/状态
Follower:完全被动,不能发送任何请求,只接受并响应来自leader和candidate的message,node启动后的初始状态必须是follower。
Leader:处理所有来自客户端的请求,以及复制log到所有followers。
Candidate:用来竞选一个新leader(candidate由follower触发超时而来)。
Message的3种类型
RequestVoteRPC:Candidate发出。AppendEntries(Heartbeat)RPC:Leader发出。InstallSnapshotRPC:Leader发出。
任期逻辑时钟
时间被划分为一个个任期(term),termid按时间轴单调递增。
每一个任期的开始都是leader选举,选举成功之后,leader在任期内管理整个集群,也就是“选举+常规操作”。
每个任期最多一个leader,可以没有leader(spilt-vote导致)。
4Raft功能分解
Leader选举
超时驱动:Heartbeat/Electiontimeout
随机的超时时间:降低选举碰撞导致选票被瓜分的概率
选举流程:Follower--Candidate(选举超时触发)
赢得选举:Candidate--Leader另一个节点赢得选举:Candidate--Follower一段时间内没有任何节点器赢得选举:Candidate--Candidate
选举动作:
Currentterm++发送RequestVoteRPC
NewLeader选取原则(最大提交原则):
CandidatesincludeloginfoinRequestVoteRPCs(indextermoflastlogentry)
Duringelections,choosecandidatewithlogmostlikelytocontainall