用可持久化 B+ 树优化 OFFSET 子句

分页功能是网站常见的需求之一，对应到数据库中的实现，通常会用 LIMIT ? OFFSET ? 的子句来实现，然而这是很多网站被攻击的潜在原因之一。在主流的数据库实现中，这种查询的效率往往非常的低下。本文脑洞了一种高效支持 OFFSET LIMIT 的方法。

首先让我们看看到底有多慢。以 MySQL 为例：

首先我们在 mysql 中创建一张简单的表，并用 sysbench 导入 10M 条数据：

sysbench --mysql-host=127.0.0.1 --mysql-db=test --mysql-user=root oltp_point_select prepare --table-size=10000000

这并不是很大的一个数据量，然后我们执行一条简单查询：

select * from test.sbtest1 limit 10 offset 9000000;

10 rows in set
Time: 7.993s

这样一个简单的查询需要花费 8 秒左右的时间，而且当我用 sysbench 去压这条 SQL 的时候它直接挂了。在具体的实现，OFFSET LIMIT 这种操作基本都是通过扫描来实现的，很难跳过前序的行数，而 OFFSET 越大意味着需要扫描的数据越多。一个正常的用户通常只会刷前几页的数据，但是被 hack 的时候就很难说了，也许只需要把 url 里的 pageNo=1 改成 pageNo=10000 并且高并发请求一下，一些网站就挂了，当然现在这种场景已经很少了。

很难跳过不代表无法跳过，我们从 MySQL 底层的索引数据结构 B+ 树说起。

上图是一个简单的两层4阶 B+ 树，由一个非叶节点和四个叶节点组成，叶节点之间通过链表连接，用于提高 scan 性能。

我们想做一个分页查询

SELECT * FROM t OFFSET 4 LIMIT 2;

对应到存储结构上，就是希望找到这个索引树上第四个到第五个元素 btree.range(4, 6)，20 和 24。目前的实现里，我们显然只能左到右扫描，在无意义地访问了连个不需要的节点后，我们才能找到正确的节点和对应的数据。很显然，如果我们在每个非叶节点上实时维护所有子树的 count 的话，我们就能更快地找到结果。

通过非叶节点上的 count 记录，我们就可以先通过 root 节点的 count，确认第四条纪录从第三个叶节点开始，然后直接找到数据并开始扫描，总体时间是 $log(n)$ 的复杂度。当然，这会导致我们每次插入或者删除数据的时候也需要更新一整条树路径上的所有非叶节点。

MVCC

在支持事务的数据库里，往往使用 MVCC 来减少读写之间的锁冲突。MVCC 在叶节点中的数据，存的是一串链表（O2N），代表了数据的更新记录，而 seq 代表了。支持了 MVCC 后，我们很快发现我们的 count-B+ tree 不好使了。

我们分别进行了一次插入，一次修改和一次删除，这也就导致了我们查询不同 version 的时候，正确的结果是不一样的。

insert(18, "j1", version=3)
update(16, "d2", version=5)
delete(20, version=7)

SELECT * FROM t OFFSET 4 LIMIT 2; // version = 2
|key|value|
|20 |e1   |
|24 |f1   |
SELECT * FROM t OFFSET 4 LIMIT 2; // version = 4
|key|value|
|18 |j1   |
|20 |e1   |
SELECT * FROM t OFFSET 4 LIMIT 2; // version = 8
|key|value|
|18 |j1   |
|20 |e1   |

我们的计数只能支持对最新数据的查询，而在修改发生之前已经创建好的 ReadView，我们就无能为力了。

多版本计数

既然数据可以做多版本，那么我们的计数理所当然也可以。

在多版本计数上，我们“如愿以偿”地查到了我们想要的结果。

B+ 树的分裂

insert(37, "k1", version=9)

上面的思路依然是死路一条，我们考虑 B+ 树的分裂和合并，多版本计数是完全不可维护的。

可持久化数据结构

我们先直接看一下我们用可持久化 B+ 树优化后的结果，为了简化做图，我们假设我们仅做了两次插入：

insert(18, "j1", version=2)
insert(37, "k1", version=3)

可以看到，相比于原来的 B+ 树，我们引入了两个变化：

1. 不再就地修改数据。
2. 删除了叶节点之间的指针（这删了还能叫 B+ 树吗？-_-）

在第一次进行插入后，我们直接 copy 了一份根节点和第二个叶节点，并插入数据，新的节点（黄色）另外三个指针依然指向原来的叶节点，只有第二个指针指向了新的节点。

而第二次插入直接引发了分裂，因此我们一共创建了五个新节点， 包括：

1. 原先的第四个节点分裂后的新的叶节点（30，37 开头）
2. 原先的 root 节点分裂后的两个非叶节点上（10、30 开头的绿色节点）
3. 新的 root 节点

可以看到一波操作之后，我们拥有了三个版本的 B+ 树！每个版本都是一个符合我们预期的全局快照，我们查找的时候可以先快速找到需要的版本，然后在每个版本上快速地进行符合我们优化预期分页查询。与此同时，我们也并没有占用三倍的空间，理论的空间复杂度是 $n+m log(n)$ 其中 n 是树的大小，m 是维护的版本数。

可持久化数据结构 是一个数据结构上的概念，但跟 MVCC 不谋而合。而当我们尝试在数据库上使用了可持久化B+树后，我们事实上是把 MVCC 做到了整个索引的数据结构里，而非行记录里。整个索引结构从 BPTree<Key, PersistentList<Value>> 转变为了 List<PersistentBPTree<Key, Value>>。

另一个问题是，为什么我把叶节点之间的连接指针删掉了，因为不删没法做，原因可以留给读者思考一下，这也是可持久化数据结构的局限性之一。

Mixing mode

考虑到这种实现的 clone 代价还是太高，也许可以混合三种方式做这个优化：

1. UPDATE 时，只添加行记录，做行级 MVCC。
2. INSERT/DELETE 但不涉及树的结构变更时，使用多版本计数（可以记在内存里，反正可以恢复出来）。
3. 发生树结构的变更时，直接创建一个新版本的 B+ 树。

查询时：

1. 先通过全局的版本链表找到一个 B+ 树。
2. 通过 B+ 树非叶节点上的多版本计数，快速定位到行记录。
3. 通过行记录上的多版本 MVCC，定位到需要读取的数据。

（实现上想想就很恶心，所以连图都不想画了）

后记

后来还写了个 Rust 的实现，但写得不太好不想开源了，反正可持久化数据结构无脑 Arc 就对了

分页其实是个很小众的需求，在数据库支持不佳的情况下，业务上也有了很多替换解决方案，完全没有必要花很大代价去做优化，所以这篇文章还是搞笑为主的（不搞笑我肯定发 paper 了谁写 blog 啊），但仔细想想发现这个 idea 居然还挺 novel 的。。。

1. 一种不同于 LSM 的 append only B+ 树存储引擎方案
2. 不修改数据结构，天然无锁并发，不需要处理 B+ 树复杂的细粒度锁逻辑
3. 可以在非叶节点上支持很多满足事务隔离要求的预聚合，不局限于分页
4. 做 interval GC 很容易

当然代价也是很明显的，写放大和空间放大前所未有的大，所以还是没有意义 ：）

好玩为主，很久没有 follow 过存储引擎的东西了，idea 如有雷同都是巧合（