共计 4796 个字符，预计需要花费 12 分钟才能阅读完成。
- 背景 ToplingDB 是 topling 开发的 KV 存储引擎，fork 自 RocksDB，进行了很多革新，其中最重要的部件是 ToplingZipTable, 是 BlockBasedTable 的代替品，性能更高而内存占用更低。ToplingZipTable 应用 CO-Index 与 PA-Zip 实现索引和数据的存储。CO-Index 指 Compressed Ordered Index, 是一类内存压缩的索引，无需解压，在压缩的状态下能够对索引间接搜寻，并且搜寻速度极快。从 String 类型的 Key，搜寻出一个密实 的 整数 ID。PA-Zip 指 Point Accessible Zip, 无需 BlockCache，能够十分疾速地 按 ID 定点拜访单条数据。本文形容 CO-Index 家族中最通用的索引：NestLoudsTrie2. Succinct 数据结构 Succinct Data Structure 是一种可能在靠近于信息论上限的空间内来表白对象的技术，通常应用位图来示意，用定义在位图上的 rank 和 select 操作来定位。rank 和 select 能够通过空间占用极少的索引来实现，实践上，只须要 �(�) 的索引空间就能够用 �(1) 的工夫复杂度实现 rank 和 select 操作，然而这个 O(1) 的常数项很大。在实践中，咱们会通过稍多一点的空间，换取更小的 O(1) 常数项。驰名的开源我的项目 SDSL-Lite 中有各种 Succinct 数据结构的实现，是一个大而全的 Succinct 我的项目。3. topling-zip 简介与 SDSL-Lite 相同，有着 10 余年历史的 ToplingDB 的底层外围库 topling-zip 在 Succinct 上并不谋求大而全，而是“小而精”，所有以实用为目标，性能优先。topling-zip 中的 Succinct 最后是专为 NestLoudsTrie 实现的，而 NestLoudsTrie 是 Topling FSA(DFA+NFA) 家族的一份子，同时也是自动机压缩算法的一个 Building Block 目前开源的 topling-zip 只蕴含 Topling FSA 中实用于数据库索引的局部，不蕴含正则表达式引擎及各种字符串匹配算法的局部（例如多正则引擎及专利的拼音纠错算法）topling 的所有数据结构在设计上都都反对 mmap: 数据在内存中的格局和在文件中的格局完全相同。不仅如此，topling 的所有构件在设计上都严格贯彻“高内聚”、“低耦合”的准则，这也是 Unix 哲学：每个构件只做一件事并且做好这件事。就最根底的 Succinct: 反对 rank select 的 bitmap 来看，topling 的性能远高于广为人知的 SDSL-LiteRank-Select Benchmark（比照 SDSL-Lite），这个比照是 5,6 年前测的，当初 Topling 比当初还有肯定晋升 4. Succinct Trie4.1. Succinct TreeTree 的传统实现中，每个结点蕴含两个指针：struct Node {Node firstChild, nextSibling; };
每个结点占用 2 ptr，如果咱们对传统办法进行优化，结点指针用最小的 bits 数来表白，N 个结点就须要 2∗⌈���2(�)⌉ 个 bits。比照传统根本版和传统优化版，假如共有 216 个结点（包含 null 结点），传统优化版须要 2 bytes，传统根本版须要 4/8 bytes。比照传统优化版和 Succinct，假如共有 10 亿 (~ 230) 个结点。传统优化版每个指针占用 ⌈���2(230)⌉=30 bits，总内存占用：2∗308∗230 ≈ 7.5GB。如果应用 Succinct，n 个结点的 Tree 空间占用是 O(2n) bits，这个例子中空间占用就是：2.58∗230 ≈ 312.5MB (每个结点 2.5 bits，其中 0.5 bits 是 rank-select 索引占用的空间），差距是 30 倍！4.2. Unary 编码 Succinct Tree 中，每个结点被编码为 111110 序列，其中 1 的个数代表该结点的孩子数量，叶节点没有孩子，所以叶节点的编码就只有单个 0。这叫做 Unary Degree Sequence。4.3. 深度优先 or 宽度优先 Tree 最常见的遍历程序是深度优先和宽度优先，相应地，Succinct Tree 也有深度优先和宽度优先编码，不论是深度优先还是宽度优先，单个结点的 bit 编码都是 Unary Degree Sequence。深度优先编码能反对更多的高级操作，然而须要 bitmap 反对除了 rank 和 select 之外的其它操作（findopen 和 findclose，这里不深刻开展）。宽度优先实际上是按层遍历，所以叫做 LOUDS (Level Order Unary Degree Sequence)，它的益处是只须要 rank 和 select 操作，能够实现很高的性能，害处是反对的高级操作少。侥幸的是，作为 DB 索引，LOUDS 反对的操作刚好够用 4.3. Trie 结点在 Tree 结点的根底上增加了 LabelTrie 结点的传统实现是 struct Node {Map<char, Node*> children;};
后面 Tree 的 firstChild + nextSibling 实际上就是个单向链表，Trie 为每个子节点增加了一个 Key。这个 map children 实现从概念上十分简洁明确，然而即使依照传统的实现形式，其冗余空间占比也过高。咱们留神到，作为 Tree，其结点数 == 边数 + 1，即 NodeNum == EdgeNum + 1，除了根节点，每个结点有且仅有一条入边。所以，咱们能够这样定义 Node:struct Node {
char incomingLabel;
Node firstChild, nextSibling;
};
这个 Node，编译器为了对齐，incomingLabel 实际上会占用一个指针宽度，很节约空间，然而相比后面的 map children 也小了很多。如果应用 Succinct，其 Tree 构造空间占用是 2.5n 个 bit，同时，其结点是用 [0,�) 的整数编号的，所以，咱们把 IncomingLabel 保留在一个独立的 char 数组中，从而，每个结点的空间占用就是 10.5 个 bit。 - Patricia Trie 作为字符串索引，Trie 树的大部分结点都只有一个孩子，所以不论是传统的 Trie 树，还是 Succinct Trie 树，这都是一个极大的节约，不光节约存储空间，还节约 CPU 工夫。所以，几十年以前，有人就提出了一个优化计划，把所有连贯的并且只有一个孩子的结点，压缩成一个结点，同时把这些结点上的 Label 也连接成一个字符串。这就是 Patricia Trie，这个压缩形式叫做门路压缩。6. 多层嵌套 Succinct Trie 还有一个神奇的能力，能够从孩子结点导航到父节点，更正式的形容：能够在 O(1) 的工夫内，从孩子结点的 id 计算出父节点的 id 有了这个能力，咱们就能够从任何一个结点 S 登程，向根节点行走，把行走门路上的 IncomingLabel 拼接起来，就失去了结点 S 所代表的字符串。这样，咱们就能够在 Patricia 的根底上，进一步升高存储空间：把 Patricia 中压缩门路上的字符串保留到另一个 Patricia 中，并且能够进行多层嵌套。这就是 NestLoudsTrie。
- Topling NestLoudsTrieTopling NestLoudsTrie 实现了作为 DB 索引须要的所有操作，并且进行了十分粗疏的优化，Benchmark 进行单项测试：每秒钟可执行 100 万次搜寻操作 Iterator 每秒可扫描 500 万个 KeySuccinct 始终被大家诟病性能低下，然而通过咱们的不懈努力，在 ToplingDB 中，实现了性能与空间的双重效力。8. ReorderNestLoudsTrie 中保留的 N 个 Key 会映射到整数区间 [0,�)，美中不足的是，因为宽度优先，所以 Key 和 n 的对应关系不是 Bytewise 字典序（深度优先的天然序就是字典序）。能够通过破费更多的 CPU 工夫，实现字典序映射的操作，然而咱们谋求的第一指标是性能。所以，在创立 ToplingZipTable 时，咱们须要一个 Reorder 操作，把 Value 程序重排成 NestLoudsTrie 的整数映射程序。这些计算都是在创立 SST 时实现的，进步读取 / 搜寻的性能。这个美中不足的侥幸之处在于，尽管不是字典序，然而靠近字典序，靠近字典序，对于空间局部性十分重要，特地是在 Iter 扫描时。9. 优化适配层如前所述，Topling 的所有组件均是“高内聚”，“低耦合”，NestLoudsTrie 本来属于 DFA 家族，与 ToplingDB 没有任何关系。要将它适配到 ToplingDB 的 CO-Index，适配层就须要肯定开销。9.1. memcpyNestLoudsTrie 的搜寻、扫描性能很高，这就使得哪怕适配层仅仅是把扫描进去的只有几十字节长的 key memcpy 到 ToplingDB，这个 memcpy 所占的工夫也相当可观（在火焰图中清晰可见）。ToplingDB/RocksDB 中须要在 UserKey 之后拼接上 8 字节的 Tag(Seq, ValueType) 失去 InternalKey，而 NestLoudsTrie 中保留的是 UserKey，所以须要将 UserKey 拷贝一次再进行拼接。所以，咱们为 NestLoudsTrie Iterator 的外部 buffer 预留一些额定空间（目前 16 字节），从而适配层就能够间接将 Tag 放到这个预留空间中，免去了这个额定的 memcpy。更进一步，因为 NestLoudsTrie 是 readonly 的，咱们能够确定 Iterator 的最大内存用量，从而 Iterator 就只须要一块内存，这并不是为了节俭内存用量，而是为了优化 CPU Cache，升高 CPU 耗费！在这个优化之后，本来不须要适配层，间接实现的 UintIndex 也享受到了这个优化，也在 Iterator 中预留额定空间，省掉 memcpy，把这个 buffer 间接 inline 在 UintIndex::Iter 中，整个 UintIndex::Iter 也只有一块内存。9.2. 虚函数 & Layout 优化 COIndex::Iterator 和 NestLoudsTrie::Iterator 是两套体系，两者之间进行适配，即使省去了 memcpy，接口转化的虚函数调用还是难以避免的。上面这个 key() 本来是个虚函数，在 Iterator scan 的火焰图中占比并非微不足道。
接下来的优化略微有点违反“高内聚”，“低耦合”了，所以必须在可控范畴之内。NestLoudsTrie::Iter 的 m_word 成员继承自 BaseDFA::Iter，相当于 vector<byte>，fstring 相当于 string_view/Slice，咱们精心设计对象布局，让所有 COIndex::Iter 派生类的 key 都在同一个偏移处，并且，针对 NestLoudsTrie::Iter，让其 m_word 成员的 ptr, len 正好对准到其它 COIndex 的 m_key{ptr,len} 成员。当然，这些数据成员的对准都要有编译期查看！这样，只须要 Iter::Next/Prev 是虚函数就能够了，实现这个优化还有更重要的一个起因：UintIndex 和 FixLenIndex 的扫描更快，扫描单条数据只须要几个纳秒，如果 key() 是虚函数，减少的开销相当可观。不能因为 NestLoudsTrie 不在 COIndex 体系而连累他人。最开始没有用当初这个对准 m_key 和 m_word 的计划，而是把 m_word 的 data 指针和 size 拷贝到 m_key，仍有一些不必要的开销，在火焰图中能够察看到。【完】
正文完