日志复制状态机, 也叫复制状态机, 是分布式数据库领域最重要的基石之一. 当前市面上所有实用的分布式数据库, 几乎都是用日志复制状态机技术来实现多副本. 像 MySQL 的主从同步, Redis 的主从同步, SSDB 的主从同步等, 是大家非常熟知的日志复制状态机的例子. 而更复杂的共识算法 Paxos, 以及最流行的分布式一致性协议 Raft, 前者的实现基本离不开日志复制状态机, 后者则是直接以日志复制状态机作为其核心组成.
那么, 什么是日志复制状态机呢? 首先, 我们先理解什么状态机. 状态机基于一个定理, 这个定理是显然的, 不需要证明的. 那就是, 如果两个被称为状态机的对象, 它们按相同的顺序执行(Apply)相同的指令序列, 那么, 指令执行完毕后, 这两个状态机的状态将必然是相同的(一致的).
指令序列也称为日志序列, 一般每一条日志带有一个唯一整数编号以确定顺序. 如果日志序列被复制到不同的地方, 然后由状态机执行, 那么分布在不同地方的状态机的状态就一致了. 这种技术便称为日志复制状态机. 状态机对象便是一个副本, 例如是一个数据库实例.
有不少对分布式系统感兴趣的同学问我:"Paxos 算法是最基础的分布式共识算法, 但是, 我看完之后, 似懂非懂. Paxos 到底应该如何进行工程落地呢?"
业界对 Paxos 算法有着非常高的美誉, 一方面是因为 Paxos 的开创性, 更多的原因, 至少我所知道的, 许多人之所以赞美 Paxos, 主要是因为"看不懂". 说看不懂似乎不对, 许多人有时觉得自己懂 Paxos, 有时觉得不懂, 今天懂, 明天不懂, 但是必须懂. 要命的是,没法落地, 即使看懂了学完了, 一行代码也写不出来, 写出来了, 代码也没实际意义, 说句俗话, 就是"没啥卵用".
回复那些对分布式共识算法(Consensus)和分布式系统感兴趣的同学的话: Paxos 的落地就是选主(Leader Election)和日志复制状态机(Log Replicated State Machine). 也就是我一直说, 不想再说, 但又不得不再重复一次的话: 就是 Raft 做的那样!
Paxos 所谓的日志空洞, 在讨论 Paxos 和 Raft 对比时出现的频率非常高, 非常显眼. Paxos 的日志空洞是什么? "日志空洞"对线性一致性有什么影响? 我认为大多数人都对 Paxos 日志空洞有误解, 包括我之前也是.
很多人认为 Multi Paxos 可以允许空洞, 但是 Paxos 论文提到:
To guarantee that all servers execute the same sequence of state machine commands, we implement a sequence of separate instances of the Paxos consensus algorithm, the value chosen by the ith instance being the ith state machine command in the sequence.
状态机必须严格按顺序执行(apply)命令, 所以, Multi Paxos 并不允许 apply 时出现所谓的日志空洞. 虽然会乱序 chosen(也即所谓的空洞), 但是, apply 一定是严格按顺序进行的. Apply 的时候, 如果不是严格按顺序的, 就不是日志复制状态机.
但是, 因为必须严格按顺序执行日志序列, 所以, 即使 Multi Paxos 乱序 chosen 日志, 也不会影响外部一致性.
日志复制状态机模型是 Raft 协议里的一个基础概念, 用于保障多副本一致性. 这个概念并非 Raft 独创, 而是由 Raft 具体总结和推广的, 在 Raft 之前, 像 MySQL 的 binlog 等等, 都是广义的日志复制状态机模型.
采用日志复制状态机模型的系统, 把多副本一致性问题分解成两个部分(模块), 第一部分是日志本身的一致性, 第二部分是状态机(例如数据库引擎)的数据一致性. 这两个系统模式是独立运行的, 它们之间的通信(Apply)也是异步的. 由此带来了广义的可靠通信问题: 有序, 最终到达(不丢包), Exactly Once(去重).
为了解决可靠通信问题, 系统至少需要保存 Apply 进度. 但是, 由于微观上"保存进度"和"Apply 日志"是两个独立的操作, 如果系统在两个操作之间宕机再重启, 就会导致断点位置的日志被 Apply 两次(去重问题, 如果先 Apply 再保存进度), 或者没有被 Apply(丢包问题, 如果先保存进度再 Apply).
要解决这个问题, 必须把 Apply 和保存进度两个操作作为一个完整的不可分割的整体, 就跟数据事务一样, 具有原子性, 要么同时成功, 要么全部失败, 这样就解决了去重和丢包问题. 如果状态机是 LevelDB 引擎, 那么我们可以利用其 WriteBatch 功能.
仔细借鉴 WriteBatch 的实现原理, 也许我们可以扩展思路, 把 Apply 进度保存在状态机之外, 不侵入状态机.
事务原子性的本质, 可以简单概括为: 增加 commit point, 重启时回滚.
针对两个独立对象, 我们增加一个单点标记(commit point), 当读取到对象时, 去检查单点标记的状态, 以判断对象是否有效, 如果无效则丢弃(读修复, 回滚). 正应了那句话:
All problems in computer science can be solved by another level of indirection.
到了这里, 我们不要求状态机(数据库引擎)提供原子性保证, 但要求它提供回滚能力. 回滚能力必然伴随着进度, 也即序列号, 引擎内部也要有全局递增的序列号.
我们把 Apply 进度 {raft.log_index, db.seq} 保存到独立的进度文件, 如果系统重启, 从进度文件中读取最新的 db.seq, 然后要求 db 回滚, 甚至进度文件也能回滚. 这样, 就保证了 Raft 日志 Apply Excatly Once.
另外, 再提一句"读修复"技术, 这项技术的应用非常广泛, 例如 Paxos 的核心之一就是读修复. 纯朴的思维认为所见即所得, 读就是只读一个地方, 读到什么就是什么, 不应该再读其它地方, 特别最重要的是, 读操作不应该修改数据. 但是, 如果技术思维想进阶, 一定要抛弃纯朴思维, 拓展到多版本, 多副本, 读修复, 读即是写.
|
带有此标志, 表示本博客已经被加入到IT牛人博客聚合网站. |
Loading ...