日志复制状态机, 也叫复制状态机, 是分布式数据库领域最重要的基石之一. 当前市面上所有实用的分布式数据库, 几乎都是用日志复制状态机技术来实现多副本. 像 MySQL 的主从同步, Redis 的主从同步, SSDB 的主从同步等, 是大家非常熟知的日志复制状态机的例子. 而更复杂的共识算法 Paxos, 以及最流行的分布式一致性协议 Raft, 前者的实现基本离不开日志复制状态机, 后者则是直接以日志复制状态机作为其核心组成.
那么, 什么是日志复制状态机呢? 首先, 我们先理解什么状态机. 状态机基于一个定理, 这个定理是显然的, 不需要证明的. 那就是, 如果两个被称为状态机的对象, 它们按相同的顺序执行(Apply)相同的指令序列, 那么, 指令执行完毕后, 这两个状态机的状态将必然是相同的(一致的).
指令序列也称为日志序列, 一般每一条日志带有一个唯一整数编号以确定顺序. 如果日志序列被复制到不同的地方, 然后由状态机执行, 那么分布在不同地方的状态机的状态就一致了. 这种技术便称为日志复制状态机. 状态机对象便是一个副本, 例如是一个数据库实例.
注意, 按顺序执行指令序列, 也即串行化执行指令, 是状态机的必要属性, 一旦违反此规定, 便不可称为日志复制状态机, 也无法保证状态必然一致. 另外, 既然是序列, 那就是连续的, 离散的多条日志不构成日志序列.
使用日志复制状态机技术的系统, 其内部结构大同小异, 基本都如图所示:
一次请求处理的完整流程是:
- 主节点(Leader)收到客户端请求(Request)
- 主节点往日志序列末尾追加(Append)一条日志(Log Entry)
- 主节点将日志复制(Replicate)给所有从节点(Follower)
- 主节点计算(Learn)共识结果(Consensus), 并确认(Commit)
- 主节点将共识结果通知(Broadcast)给所有从节点
- 对于已确认的日志序列, 所有节点的状态机按顺序执行(Apply)
- 主节点将状态机执行的结果(Response)返回给客户端
注意, 在工程实践上, 5 和 6 一般是并发执行的, 2 和 3 也可并发执行.
日志复制状态机在实践上遇到的第一个问题是, 由哪个节点来追加日志到日志序列中? 经典的主从同步架构, 由人来指定主节点, 只有主节点才能追加日志. Paxos 是另一个极端, 理论上在追加每一条日志前, 每一个节点需要先和其它节点协商(选主), 选出的节点作为"主"节点, 追加日志.
一条日志是否达成共识, 需要主节点根据与所有从节点通信交换信息之后进行计算才能发现, 例如对于多数派共识算法, 超过半数节点拥有一条日志即表示达成共识. 主节点计算得出结果之后, 把共识结果广播给所有从节点.
一种正确的共识算法, 应该能及时发现共识, 同时, 如果确实没有达成(稳定的)共识则不能报假. 例如, 某些错误的共识算法, 在不同的时间会计算出不同的共识结果, 这显然是不行的.
参考资料:
- https://en.wikipedia.org/wiki/State_machine_replication
- "全序"和"偏序"
- "必然"和"可能"
Loading ...