本
文
摘
要
BitDegradeTree的前身是CritBitTree, 这是一个十分冷门却又强力的数据结构.
引理1: 给定两组字符串, 如不同则必然存在差异.
比如, AAABB与ABABB是两组不同的字符串. 我们不考虑AAABB与AAABBB, 因为总是可以用一个不存在于实际内容的特殊符号来表示结束, 从而避免前缀包含关系. AAABB$与AAABBB$显然不同, $在这里就是休止符.
存在差异的字符串必然可以用一个整数来表示分歧位置. 我叫它分歧点. AAABB与ABABB的分歧点在位置2. 用分歧点进行分割之后, 树结构是这样的,
绿色部分是CBT真正记载的信息, 蓝色部分就是原有的数据, 箭头是指针. CBT不需要拷贝或者移动原有的数据, 这也是CBT可以做到在WAL上直接做索引的原因. 我们进一步推广开来, 将其用二进制表达, 左边是0, 右边是1. AAABB变为00011, ABABB变为01011, 有树如下,
假设现在来了一个请求是检测00011是否在树中, 根节点告诉我们第一个分歧点在位置2, 00011的位置2是0, 那么向左走, 发现已有00011, 全匹配成功.
如果请求是检测00010, 我们一样会先向左走遇到00011, 但最终全匹配时失败. 因此若key的长度为N bits, CBT至多进行N次基于分歧点的匹配(向左走或向右走), 并最终仅进行一次全匹配(蓝色节点, 也就是原值).
假设请求是插入01010呢? 照旧, 先看分歧点是2,01010在位置2是1, 向右走, 遇到了01011, 全匹配失败(memcmp!=0). 那么要插入的话, 发现01010与01011的分歧点在位置5, 树变为,
CBT还有可能触发回溯来插入值, 不过那也很容易明白. 比方说, 插入10011. 树中的值都是0开头的, 怎么办? 没关系! 继续走流程. 10011在位置2上是0, 向左走, 遇到00011, 最早分歧点在1, 回溯寻找合适的位置, 树变为,
这个操作的正确性由引理2保证,
即两个蓝色节点共享了一个绿色父节点, 则蓝色节点共享前缀, 长度为分歧位置减一.
怎么说呢? 可以看到01010蓝色节点和01011蓝色节点, 他们共享了数值为5的绿色节点, 说明他们的前4位都是相同的. 所以我们在插入10011时发现分歧点是1, 发生回溯时, 相当于已经和这个树中别的数值比较过了. 为啥? 因为它们都有共享的前缀.
CBT可以做成fine-grained locking的多线程小粒度锁并发的形式, 核心就是回溯插入时检查引理2是否成立, 不成立就重试. 我在这个问题上花了大量的时间踩了大坑, 因为对于多线程高性能编程了解不透彻, 最终这个效果很差劲. 在双核机器上, 多线程版本仅领先单线程版本20-30%. 这也是如何评价ffwd？尝试解释的. 大多数数据结构, 单线程版本如果很复杂, 即使存在着fine-grined locking的可能, 多线程表现也往往不尽如人意. 目前我最钟爱Skiplist, 如此简单实用, 问题是多线程下也好优化好使啊!
不知道CBT部分让各位明白了吗? 不明白的话, 评论本文或者看原发表者GitHub agl/critbit
那么BDT做了什么改进工作呢? 我们先看看CBT作为索引优越性在哪里?
首先, CBT是有序的, 又因为是trie-like, 存在支持正则表达式/前缀查询的可能性(我写过). 作为硬盘索引的话, CBT最最重要的是CBT本身的尺寸可以很小很小. 无论key有多长, CBT需要记录的数据仅仅就是一个整形, 表示分歧点在哪里. 这意味着很可能100MB的key, 1GB的value, 整个CBT索引就5MB, 甚至可以整个装进L3 cache.
除了小之外, CBT的IO需要量也远远低于B-Tree家族或者LSMT的SSTable的Skiplist. 拿平衡树来说, 1W的数据量, 最佳情况(完美平衡)也要跟13(log2(1W))个key做全匹配. CBT的绿色节点小, 且至多跟蓝色原数据key比较一次. 那么硬盘IO读需求量就是13:1的关系. 这难道不夸张吗? 至于写, CBT可以直接在WAL做, 那就是2:1的关系, 也不错了.
可以说CBT在我看来就是被遗失的上古神器!
CBT的问题也不是没有, 指针跳转太频繁, 既耗费性能又浪费空间. 如果说我的key长100 bits, 该死的正好有了100个分歧点. 那么为了找寻一个key, CPU要连续跳100个位置吗? 我们都知道链表远逊vector, C++老爹也明确表示他不喜欢链表.
我觉得B-Tree的思路完全可以引入进来啊. 我的设计是这样的,
这有着许许多多优良特性, 首先这很符合直觉, 就是把CBT直接拍匾就好了.
其次是有序的, 遍历方便是一方面, 还意味着我无论是插入还是删除, 直接memmove就搞定了! 天呐! Perfect! 我实现的时候, 4KB内可以装600多个key, 一般B-Tree/Skiplist能装多少呢?
大问题来了, 这个要怎么查询呢??? 我前后想了3套方案, 别的乱七八糟的想法还有一堆, 不放出来见笑了.
1. Naive解决方案, 这是我第一版用的, 不断找最小值法.
我要分辨01011在不在这个BDT Node中, 第一步是先遍历数组[2,5,1], 看最小值是多少? 哦, 是1. 那么01011的位置1是0, 向左走, 数组变为[2,5]. [2,5]的最小值是2, 01011在位置2上是多少? 1, 向右走, 数组变为[5], 仅有一个值, 最小值自然为5, 在位置5上, 值为1, 向右走, 遇到蓝色节点"01011", 全匹配成功, 返回存在.
这其实就是根据CBT有序性和前缀性来查询. 我们算一下复杂度, N个分歧点, N次最小值运算, 不用想了, 就是O(n^2). 我当时是觉得反正人人都说数据库瓶颈在IO, 那么CPU多花点时间无所谓.
现在我可以肯定说, 这都是放屁... 先不谈现在SSD一个跑得比一个快, 光说系统高度优化的缓存就不得了了. 无论是RocksDB还是LevelDB默认都是不开sync的, 也就说数据只要落到系统页就算完成了任务. 我就是SATA的硬盘, 1GB数据, 1秒多也写完了, 可能吗? 全都进系统页了而已. 甚至主要写入的瓶颈我看就是从用户空间内存刷到系统. 我不flush的写入速度是flush的2-3倍. 即使是数据库这种人云亦云重IO的程序, CPU占用也是重中之重.
我花了好长时间想明白我刚刚说的话, 才意识到为什么LSMT席卷了整个DB界? 因为memtable+immemtable+SST太符合现代操作系统的尿性了. 爆发性的写入你需要memtable立马吸收掉, 然后慢慢转化成硬性的硬盘IO慢慢写. 如果一开始就用硬盘上的索引, 系统缓存根本帮不上忙, 然后大家一起卡住. 这些经验如果不自己去做, 根本想不明白为什么别人要这么做.
2. O(n)解决方案, 还原法
我想起了刷LeetCode时, 经常不是做括号匹配嘛. 什么给你一大串((()()()()))), 然后最长的合法括号对是多长啊? 这种瞎Beta问题, 我曾经一度以为没用, 直到那时. 分歧点数组[2,5,1]可以用类似的手法, 开个栈, O(n)时间内还原成CBT.
T0: 栈: [空]
T1: 栈: [2] 入栈2
T2: 栈: [2,5] 入栈5, 因为5>2, 肯定在右边
T3: 栈: [2,5] => [1], 出栈2,5, 入栈1, 因为1<2<5, 2肯定在1的左边
看见没有, 从BDT的node到CBT的tree, O(n)就能解决了. 我以为这就够了. 现实又打了我一巴掌, 因为出栈入栈太花时间了, 常数项太大, 反而不如O(n^2)的naive算法. 尼玛啊!!! 工程和理论的差距有时候就是这么大.
3. 终极方案 SSE4.2 O(n)金字塔构建法 O(log n)单次查询
设CBT如下, 我省略了蓝色节点, 因为那不重要.
转化成BDT Node就是数组[3,2,3,1,3,4,6,5].
在此之上建立一个查询金字塔, 我是这么叫的, 如此简单的算法应该早有人想到了吧. 每n个作为一个小分区, 小分区记载两个值, 一是最小值, 二是下标.
我要查询[3,2,3,1,3,4,6,5]的最小值直接看最顶层的(Min 1 Pos 2, 纯白色), 得知最小值是1, 再沿着向下走还原位置. 如果向左走, 那么就要查询[3, 2, 3]的最小值, 这样会改动黄色的(Min 1 Pos 2)由此变成(Min 3, Pos 1), 就要更新上层到了灰 *** , 变为(Min 2, Pos 1).
小分区尺寸完全没必要是2, 我推荐是8. 这样构造操作可以用SSE 4.2的minpos来做, 速度是直接比较的8倍. 金字塔是完全对称的树, 自身又可以再次压缩成一个普通数组, 省掉指针空间和地址跳转开销. 本方法特别适合用于离线生成BDT. 至此, BDT所有能profile出来的瓶颈在这里都被我解决掉了.
不知道我有没有说明白呢? 你又有没有觉得excited呢? 反正我是excited了半年... 现在发出来是发现超过RocksDB, 路漫漫其修远兮.
我又又叕推翻了原有的设计方案. 上一次是我发现BDT动态构建根本承担不起memtable的职责转而抄了RocksDB的memtable. 这次, 我不准备推翻RocksDB了, 而要做RocksDB的缓存层. 数据进来之后, 先进InlineSkiplist, 满了之后直接离线打一个BDT, 配合原有的WAL做临时小数据库, 然后实在满了再直接一次性bulk load进RocksDB.
最后, 我实在是喵的写烦躁了! 我要换个方向了!
所以我不ZS了. 我又回来了. 我留下这篇文章, 还有一点点经验, 过去的六个月也不算虚度了吧.
