分布式一致性协议 ｜ 青训营笔记
基础术语
- 远程过程调用(RPC)
- 分布式系统中通常将不同组件，或者不同节点的交互使用 RPC 的方式进行封装，在调用方的视角一次远程过程调用不需要关心如何对请求和响应进行编码，也不用关心具体的网络传输。
- 状态机(State Machine)
- 一种编程架构，状态机只取决于当前的状态与的输入，确定下一个状态
- 并发/并行
- 并发：多个任务可以在重叠的实践中启动、运行、完成，并发不一定意味着并行，可以通过切换的方式做到在一个执行单元上实现并发任务
- 并行：真正的多个任务同时运行，如多核CPU
- 容错
- 通常指一种软件架构，架构可以容许一定数目的节点失效，同时保证系统正常或降级运行
- 高可用
- 指系统可以达到较高的可用时间，如系统保证一年中只有若干分钟不可用，通常以 SLA（Service-level agreement） 进行描述，容错架构是实现高可用系统的一种方式
分布式系统
- 各种各样的错误
- 网络
- 磁盘
- CPU
如果一台机器会挂，那么不妨复制一台
两个副本都能接收请求：
如何复制呢？
- 主副本定期拷贝全量数据到从副本
- 主副本拷贝操作到从副本
复制的步骤：
- 主副本把所有的操作打包成log（所有的log写入都是持久化的保存在磁盘上）
- 应用包装成状态机，只接受log作为input
- 主副本确认log已经成功写入到副本机器上，当状态机apply后，返回客户端。
关于读操作
- 方案一:直接读状态机，要求写操作进入状态机后再返回client
- 方案二:写操作复制完成后直接返回，读操作Block等待所有pending log进入状态机
一致性模型
一致性是一种模型（或语义），用于约定一个分布式系统如何向外界提供服务。
KV中常见的一致性模型
- 最终一致性：读取可能暂时读不到但是总会读到
- 线性一致性：最严格，线性执行
共识算法：
一个值一旦确定，所有人都认同
➢共识协议不等于一致性，应用层面不同的一致性，都可以用共识协议来实现。比如可以故意返回旧的值。
简单的复制协议也可以提供线性一致性
➢一般讨论共识协议时提到的一致性，都指线性一致性。因为弱一致性往往可以使用相对简单的复制算法实现
案例：Raft
- Raft 是在 paxos 的基础上的基础上，着重于易于理解
- 协议接口直接暴露 Log 给用户
- 强 Leader 简化 Paxos 中的二阶段
- 使用随机事件简化选主逻辑
- Raft 的基本工作原理
- 各个节点的角色
- Log 同步
- 失效节点如何恢复 Log
- 如何选举新 Leader
- Term 以及安全性的保证
- Raft 在工程中的优化
- Prevote 的应用，防止离群 Leader 重加入时引发的切主
Raft日志复制
Raft Term
每个Leader服务于一个term；每个term至多只有一个leader；每个节点存储当前的term；每个节点term从一开始，只增不减；所有rpc的request reponse都携带term；只commit本term内的log。
Raft主节点失效
- Leader定期的发送AppendEntries RPCs给其余所有节点
- 如果Follower有一段时间没有收到L eader的AppendEntries,则转换身份成为Candidate
- Candidate自增自己的term,同时使用RequestVote RPCs向剩余节点请求投票。raft在检查是否可以投票时，会检查log是否outdated,至少不比本身旧才会投给对应的Candidate
- 如果多数派节点投给它，则成为该term的leader
Raft安全性
Term内的安全性：
目标：对于所有已经的commited的<term, index>位置上至多只有一条log
由于Raft的多数派选举，我们可以保证在一个term 中只有一个leader
我们可以证明一条更严格的声明:在任何<term,index>位置上，至多只有一条log
跨Term的安全性：
目标：如果一个log被标记commited,那这个log一定会在未来所有的leader中出现L eader completeness
Raft选举时会检查Log的是否outdated,只有最新的才能当选Leader
选举需要多数派投票，而commited log也已经在多数派中(必有overlap)
新Leader一定持有commited log,且Leader永远不会overwrite log
Raft算法在KV中的应用
一致性读写的定义：
- 方案一
- 写log被commit了，返回客户端成功，
- 读操作也写入一条log,状态机apply时返回client
- 增加Log量
- 方案二
- 写log被commit了，返回客户端成功
- 读操作先等待所有commited log apply,再读取状态机
- 优化写时延
- 方案三
- 写Log被状态机apply,返回给client
- 读操作直接读状态机
- 优化读时延
Raft不保证一直有一 个leader，只保证一个term至多有一个leader，可能存在多个term的leader。
确定合法的Leadership
- 方案一:
- 通过一轮Heartbeat确认Leadership (获取多数派的响应)
- 方案二:
- 通过上一次Heartbeat时间来保证接下来的有段时间内follower不会timeout
- 同时follower在这段时间内不进行投票
- 如果多数follower满足条件，那么在这段时间内则保证不会有新的Leader产生
一致性协议的限制
- 对于分布式系统
- 拓展性：写入性能不能水平拓展
- 性能：强 Leader 的一致性协议跨地域部署时带来的额外网络开销
- 对于 KV 系统，解决方案一般是通过分片的方式水平拆组
- 引入了事务的概念
- 常见二阶段提交
发展方向
- 一致性协议作为系统
- 分布式日志：暴露日志的接口提供给上层应用，提供灵活高可用的一致性服务
- 高性能一致性协议
- 低延时：结合 RDMA 网络以及可编程交换机，实现 us 级别操作。
- LeaderLess：节点就地提交，降低 WAN 网络下 RTT 开销
- Paxos 与 Raft 的相互关联
- 移植 Paxos 的研究到成熟
