浅谈一致性协议｜ 青训营笔记

这是我参与「第四届青训营 」笔记创作活动的第16天

浅谈分布式一致性协议

分布式系统

分布式系统面临的挑战包括：数据规模越来越大、服务的可用性要求越来越高、快速迭代的业务要求系统足够易用。

理想中的分布式系统目标包含：高性能（可拓展、低时延、高吞吐）、正确（一致性、易于理解）、可靠（容错、高可用）。

一致性与共识算法

从复制开始

主副本定期拷贝全量数据到从副本：代价太高

如何复制

• 主副本把所有的操作打包成Log
• 应用包装成状态机，只接收Log作为Input
• 主副本确认Log已经成功写入到副本机器上，当状态机apply后，返回客户端

读操作

• 方案一：直接读状态机，要求写操作进入状态机后再返回client
• 方案二：写操作复制完成后直接返回，读操作block等待所有pending log进入状态机

什么是一致性

对于KV，像操作一台机器一样，要读到最近写入的值

一致性是一种模型(语义)，来约定一个分布式系统如何向外界(应用)提供服务。KV中常见的一致性模型：最终一致性——读取可能暂时读不到但是总会读到；线性一致性——最严格、线性执行

共识算法

共识算法是指一个值一旦确定，所有人都认同

共识协议不等于一致性，应用层面不同的一致性，都可以用共识协议来实现，比如可以故意返回旧的值。简单的复制协议也可以提供线性一致性

一般讨论共识协议时提到的一致性，都指线性一致性，因为弱一致性往往可以使用相对简单的复制算法实现

Raft案例

Paxos

Raft

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

raft主节点失效

leader定期的发送AppendEntries RPCs给其余所有节点，如果follower有一段时间没有收到leader的AppendEntries，则转换身份成为candidate，candidate自增自己的term，同时使用requestVote RPCs向剩余节点请求投票，raft在检查自己是否可以投票时，会检查log是否outdated，至少不比本身旧才会投给对应的candidate，如果多数派节点投给它，则成为该term的leader

raft安全性——同term

对于term内的安全性，目标在于对于所有已经commited的<term,index>位置上至多只有一条log

由于raft的多数派选举，我们可以保证在一个term中只有一个leader，在任何<term,index>位置上，至多只有一条log

raft安全性——跨term目标

跨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。读操作直接读状态机。优化读时延。

• Raft不保证一直有一个leader，只保证一个term至多有一个leader，可能存在多个term的leader
• Split-brain

确定合法的leadership

方案一：通过一轮心跳确认leadership

方案二：通过上一次心跳时间来保证接下来的有段时间内follower不会timeout。同时follower在这段时间内不进行投票。如果多数follower满足条件，那么在这段时间内则保证不会有新leader产生