数据库内核的快照技术实现原理

"快照(Snapshot)"是数据库领域非常重要的一个概念, 最初是用于数据备份. 如今, 快照技术已经成为数据库内核(引擎)最核心的技术特性之一. 数据库内核的绝大多数操作, 都依赖于快照, 例如, LevelDB 的每一次读取操作和遍历操作, 其内部都必须创建一个快照, 所以, 对于一个请求量非常大的系统, 数据库内核每秒种就要创建和销毁几十万次快照. 因此, 如何快速地创建和销毁快照, 成为一个数据库内核(引擎)必须要解决的问题.

本文从源头出发, 逐步推演, 探讨数据库内核是如何实现快照技术的. 数据库内核创建快照, 将使用如下技术:

1. 全量拷贝(Full Clone)
2. 写时拷贝(Copy On Write)
3. 分区拷贝(Partitioning)
4. 多版本(Multi Versioning, Leveling, Zero Copy)

无论何种实现快照的技术, 数据 拷贝都不可避免, 差异点主要是不同的技术拷贝的数据量不同, 以及拷贝的数据含义不同(直接拷贝和间接拷贝). 直接拷贝意味着拷贝数据本身, 间接拷贝则拷贝数据的"指针".

拷贝意味着 互斥, 独占, 加锁, 因为拷贝需要保证数据的完整性. 硬盘数据拷贝速度是较慢的, 往往被认为不可接受, 应极力避免. 内存数据拷贝速度较快, 但仍然需要减少拷贝的数据量.

1: 全量拷贝(Full Clone)

全量拷贝技术是创建快照最本能的实现方法, 也是最低效的方法. 因为数据量往往非常多, 而且还常常在硬盘上, 拷贝成本高, 耗时长. 在进行全量拷贝的过程中, 需要排斥写操作, 所以数据库系统是无法提供写服务的.

2: 写时拷贝(Copy On Write)

全量拷贝低效速度慢, 那么, 一个可能的优化方向是在某些不需要拷贝的场景不做任何拷贝. 在某些场景, 例如读请求, 虽然需要创建一个快照并且去读快照, 但是, 读操作并不会修改快照数据和原来的数据, 如果这时整个系统也正好没有任何写操作请求, 那么, 就没有必要做全量拷贝.

同时, 为了应对某个时刻收到写操作请求, 需要随时做准备, 一旦有写操作请求时, 再做一次全量拷贝. 写时拷贝技术是一种 概率优化技术, 不像纯朴想法所认为地去优化全量拷贝本身的性能.

概率优化是一种 外部优化, 依赖于实际使用场景的概率分布, 在遇到 bad cases 时, 因为内部依然非常慢, 所以在 bad cases 场景不起作用. 所以, 仅仅写时拷贝技术并不能从根本上解决问题.

写时拷贝的关键是引入一个 单点标记和额外的一步 必要操作路径(单点), 所有的请求都必须走这条路径, 这样才能截获写操作请求, 在写操作请求之前进行数据拷贝.

3: 分区拷贝(Partitioning)

分区(Partitioning)技术是计算机领域非常重要的技术思想, 有点像"分而治之"思想, 和"并发"技术是统一的. 因为无论针对快照或是原始数据的修改, 在操作过程期间往往只修改很小的一个比例, 例如一个拥有一百万行记录的数据库表, 在创建完快照和销毁快照这段时间内, 也许只修改了两三行记录, 没有必要拷贝整个表.

分区拷贝将数据拆分为多个部分(Partition), 结合 Copy On Write 技术, 在有必要的时候, 才拷贝被修改的那部分数据. Partitioning 技术在计算机领域应用非常广泛, 像我们常说的"减小锁粒度", "分布式数据库 Sharding", "并发"等等, 这些都是 Partitioning.

4: 多版本(Multi Versioning)

多版本技术抛弃了纯朴观念里的"修改"一词, 当想要修改某项数据时, 只是简单地写新数据写到其它地方, 暂时不管旧数据是怎么样的. 然后, 引入一个成本极小的标记, 修改数据的指向(也即将旧数据标记为作废, 将新数据标记为有效). 这个标记和前文介绍写时拷贝技术时提到的"必要路径"是一个意思.

基于多版本技术, 创建快照时不再拷贝任何原始数据(Zero Copy), 只有成本极小的对标记的修改操作, 所以, 无论数据是在内存还是在极慢的硬盘里, 都不影响创建快照的速度. 如果这个标记是放在内存中的, 那么, 针对1TB的数据库每秒创建百万个快照也没有问题.

不过, 多版本技术也有缺点. 它虽然不影响创建快照的速度, 也很少影响写操作的速度, 但是, 它严重影响读操作的性能, 因为我们必须读取全部的版本出来, 才能知道哪个版本是我们需要的, 版本越多, 性能就越差. 所以, 使用多版本技术时, 都要结合 垃圾回收(GC)技术, 尽快删除不需要的版本.

和分区技术不同, 多版本技术的不同版本是指同一个对象, 不是独立的, 可以把版本理解为层(Level), 最终多个层合并(Merge), 形成最终的对象数据. 而分区是独立的, 不需要合并, 只需要连接(Chain)起来.

在实践中, 多版本技术往往要通过扩大数据对象的粒度来减少版本数量.

Related posts:

1. 并发编程的核心技术 – 多版本(Multi Version)
2. Redis 的作者狂喷某 NoSQL 数据库
3. 解决从github匿名获取只读repo错误
4. Linux 核心编程 – fsync, write
5. C# 中实现 FIFO 缓冲区–ArrayBuffer