这是我参与「第四届青训营 」笔记创作活动的第16天
分布式系统面临的挑战包括:数据规模越来越大、服务的可用性要求越来越高、快速迭代的业务要求系统足够易用。
理想中的分布式系统目标包含:高性能(可拓展、低时延、高吞吐)、正确(一致性、易于理解)、可靠(容错、高可用)。
主副本定期拷贝全量数据到从副本:代价太高
如何复制
对于KV,像操作一台机器一样,要读到最近写入的值
一致性是一种模型(语义),来约定一个分布式系统如何向外界(应用)提供服务。KV中常见的一致性模型:最终一致性——读取可能暂时读不到但是总会读到;线性一致性——最严格、线性执行
共识算法是指一个值一旦确定,所有人都认同
共识协议不等于一致性,应用层面不同的一致性,都可以用共识协议来实现,比如可以故意返回旧的值。简单的复制协议也可以提供线性一致性
一般讨论共识协议时提到的一致性,都指线性一致性,因为弱一致性往往可以使用相对简单的复制算法实现
Raft是在2014年发布,易于理解作为算法的设计目标,使用了RSM、Log、RPC的概念,直接使用RPC对算法进行了描述,Strong Leader-based,使用了随机的方法来减少约束
正确性:形式化验证、拥有大量成熟系统
RSM
RSM(replicated state machine):raft中所有的consensus都是直接使用Log作为载体的
Commited Index:一旦raft更新commited index,意味着这个index前的所有log都可以提交给状态机了,commited index是不持久化的,状态机也是volatile的,重启后从第一条log开始
raft角色
leader:所有操作的发起者
candidate:参与竞选leader
follower:不接收用户的请求,无主时成为candidate发起选主请求
raft term逻辑时钟
特点是每个leader服务于一个term、每个term至多只有一个leader、每个节点存储当前的term、每个节点term从一开始,只增不减、所有rpc的request response都携带term、只commit本term内的log
leader定期的发送AppendEntries RPCs给其余所有节点,如果follower有一段时间没有收到leader的AppendEntries,则转换身份成为candidate,candidate自增自己的term,同时使用requestVote RPCs向剩余节点请求投票,raft在检查自己是否可以投票时,会检查log是否outdated,至少不比本身旧才会投给对应的candidate,如果多数派节点投给它,则成为该term的leader
对于term内的安全性,目标在于对于所有已经commited的<term,index>位置上至多只有一条log
由于raft的多数派选举,我们可以保证在一个term中只有一个leader,在任何<term,index>位置上,至多只有一条log
跨term目标的安全性,目标在于如果一个log被标记commited,那这个log一定会在未来所有的leader中出现leader completeness
证明:raft选举时会检查log是否outdated,只有最新的才能当选leader,选举需要多数派投票,而commited log也已经在多数派中(必有overlap),新leader一定持有commited log,且leader永远不会overwrite log
方案一:写log被commit了,返回客户端成功。读操作也写入一条log,状态机apply时返回client。增加log量
方案二:写log被commit了,返回客户端成功。读操作先等待所有commited log apply,再读状态机。优化写时延
方案三:写log被状态机apply,返回给client。读操作直接读状态机。优化读时延。
方案一:通过一轮心跳确认leadership
方案二:通过上一次心跳时间来保证接下来的有段时间内follower不会timeout。同时follower在这段时间内不进行投票。如果多数follower满足条件,那么在这段时间内则保证不会有新leader产生