0
0

什么是日志复制状态机?

ideawu 发表于 2021年08月05日 21:37 | Hits: 159
Tag: 分布式 | 数据库 | Paxos | Raft | 日志复制状态机

日志复制状态机, 也叫复制状态机, 是分布式数据库领域最重要的基石之一. 当前市面上所有实用的分布式数据库, 几乎都是用日志复制状态机技术来实现多副本. 像 MySQL 的主从同步, Redis 的主从同步, SSDB 的主从同步等, 是大家非常熟知的日志复制状态机的例子. 而更复杂的共识算法 Paxos, 以及最流行的分布式一致性协议 Raft, 前者的实现基本离不开日志复制状态机, 后者则是直接以日志复制状态机作为其核心组成.

那么, 什么是日志复制状态机呢? 首先, 我们先理解什么状态机 . 状态机基于一个定理, 这个定理是显然的, 不需要证明的. 那就是, 如果两个被称为状态机的对象, 它们按相同的顺序执行(Apply)相同的指令序列, 那么, 指令执行完毕后, 这两个状态机的状态将必然 是相同的(一致的).

指令序列也称为日志序列 , 一般每一条日志带有一个唯一整数编号以确定顺序. 如果日志序列被复制到不同的地方, 然后由状态机执行, 那么分布在不同地方的状态机的状态就一致了. 这种技术便称为日志复制状态机. 状态机对象便是一个副本, 例如是一个数据库实例.

注意, 按顺序执行指令序列, 也即串行化执行指令, 是状态机的必要属性, 一旦违反此规定, 便不可称为日志复制状态机, 也无法保证状态必然 一致. 另外, 既然是序列 , 那就是连续的 , 离散的多条日志不构成日志序列.

使用日志复制状态机技术的系统, 其内部结构大同小异, 基本都如图所示:

zhuangtaiji

一次请求处理的完整流程是:

  1. 主节点(Leader)收到客户端请求(Request)
  2. 主节点往日志序列末尾追加(Append)一条日志(Log Entry)
  3. 主节点将日志复制(Replicate)给所有从节点(Follower)
  4. 主节点计算(Learn)共识结果(Consensus), 并确认(Commit)
  5. 主节点将共识结果通知(Broadcast)给所有从节点
  6. 对于已确认的日志序列, 所有节点的状态机按顺序执行(Apply)
  7. 主节点将状态机执行的结果返回给客户端(Response)

注意, 在工程实践上, 5 和 6 一般是并发执行的, 2 和 3 也可并发执行.

日志复制状态机在实践上遇到的第一个问题是, 由哪个节点来追加日志到日志序列中? 经典的主从同步架构, 由人来指定主节点, 只有主节点才能追加日志. Paxos 是另一个极端, 理论上在追加每一条日志前, 每一个节点需要先和其它节点协商(选主), 选出的节点作为"主"节点, 追加日志.

一条日志是否达成共识, 需要主节点根据与所有从节点通信交换信息之后进行计算才能发现, 例如对于多数派共识算法, 超过半数节点拥有一条日志即表示达成共识. 主节点计算得出结果之后, 把共识结果广播给所有从节点.

一种正确的共识算法, 应该能及时发现共识, 同时, 如果确实没有达成(稳定的)共识则不能报假. 例如, 某些错误的共识算法, 在不同的时间会计算出不同的共识结果, 这显然是不行的.

参考资料:

Related posts:

  1. 什么是 Paxos 的日志空洞?
  2. Raft日志复制状态机模型的Apply进度问题
  3. 为什么极少有开源的Paxos库?
  4. Paxos和Raft读优化 – Quorum Read 和 Read Index
  5. Paxos 算法实现和工程落地: 选主与复制状态机

原文链接: https://www.ideawu.net/blog/archives/1196.html

0     0

我要给这篇文章打分:

可以不填写评论, 而只是打分. 如果发表评论, 你可以给的分值是-5到+5, 否则, 你只能评-1, +1两种分数. 你的评论可能需要审核.

评价列表(0)