Binlog, Redolog 在分布式数据库系统中的应用

系统结构

         request
client -------> server

在一个系统中, 有 client 和 server 两个角色, client 向 server 发起请求(request), 这里的请求指写数据请求, 例如某条类似 "update table set a=1" 这样的 SQL 语句. 我们把 server 进行拆分, 得到下面这个更细化一些的系统结构:

         request         write
client -------> server -----> database

Server 的内部其实有一个数据库存储引擎, 例如可以使用 sqlite, 或者 LevelDB. 这个结构还可以继续拆分, 在分布式数据库, 需要有多副本, 所以会引入 binlog 技术(日志复制状态机), 把用户的请求保存下来(持久化), 然后复制到其它机器上. 因此, 系统的架构就变成:

         request         apply
client -------> binlog -----> database

Server 会把 client 发来的每一个请求, 按顺序排队, 保存到 binlog 中, binlog 是一个 列表(链表), 链表的每一个节点表示一条 SQL 语句.

Raft 技术会用来复制 binlog 到其它机器上, 以解决多副本所面临的最基本问题: 让多台机器上的 binlog 列表是完全相同的(一致). Binlog 复制之后, 便会应用(apply)到数据库里, 也即真正地执行 SQL 语句.

我们继续分析 database 的内部结构, 发现其内部有一种叫 redo log 的东西, 我们把 redo log 拆分出来:

         request         apply          compact
client -------> binlog -----> redolog -------> layout

把 redolog 拆分出来之后, 数据库换了个名字叫 layout, 因为剩下的那部分, 主要的功能是组织数据在硬盘上的存储结构, 决定数据如何平铺(layout).

为什么要引入 redolog, 而不是直接从 binlog apply 到 disk layout 呢? 因为, 本质上 disk io 是 append only 的, 根本就没有我们纯朴观念所理解的 in-place. 当我们想修改磁盘上的某块数据时, 我们并不是直接原地修改, 而是换一个地方写入新的数据, 然后修改指向旧数据的" 指针". 如果确实想原地修改(将旧数据擦除再写, 或者直接覆盖写), 那么必须引入所谓的 undo log, 先将旧数据备份到其它地方, 然后才能原地修改.

由于 redolog 也是一种列表结构, 对查询不友好, 我们需要把数据进行排序聚簇, 也就是把可能连续访问的数据放到相邻的地方, 这个过程称为 compact.

模块详解

blogs

Binlogs, 加上复数形式, 表明这是一个列表, 否则, 是单数形式, 表示一项 binlog. Binlogs 列表中的每一项记录, 都有一个 index 序号, 是 连续单调递增的, 不能有空洞. 列表必须按顺序保存到硬盘上(持久化), 当一项记录被持久化之后, 就称为已 accepted 了. 如果某一项记录已经在多台机器上持久化, 就称为 committed 了. Accepted 的数据可以被擦除(回滚), 但已经 committed 的数据不能被回滚, 需要 apply 成为 redolog.

rlogs

Redologs, 有递增的序号, 称为 seq, 但是序号不是连续的, 有空洞. Redologs 也可回滚. binlog 转成 redolog 是一对多的, 也即一条 binlog 可能产生多条(也可能0条) redolog. 正常来说, seq 也应该是连续单调递增的, 但基于性能优化考虑, 会对 redolog 进行合并, 所以某些 seq 被消除了没有被持久化, 从而造成空洞.

alogs

Apply logs, binlog 转成 redolog 的过程, 要求每一条 binlog 只能 apply 一次, 且仅能 apply 一次, 也即所谓的 Exactly Once, 不丢包, 不重复. Alogs 便是记录 apply 进度的地方, 一条 apply 进度是 {index, seq} 组合. 所以, alogs 中的 index 是递增的, 但 index 有可能重复, 无空洞(连续递增, 非单调?). Seq 也是递增的, 也有可用重复, 但有空洞. Alogs 可根据 seq 回滚.

layout

排序, 聚簇.

关系

blogs 和 alogs 一一对应, 每一条 blogs 队列产生一条 alogs 队列.

blogs 和 rlogs 多对一, 多条 blogs 共同产生一条 alogs 队列.

各种 logs 除了有回滚功能(rollback), 还要有淘汰功能(purge).

Binlog 用于共识和线性一致性, 也可用于最终一致性, 但一般不用. Redolog 用于最终一致, 效果更佳.

Related posts:

1. Raft Read Index 的实现
2. Raft日志复制状态机模型的Apply进度问题
3. 数据库事务的原子性与隔离级别
4. Paxos和Raft读优化 – Quorum Read 和 Read Index
5. 一个 Paxos 库的功能模块划分