感谢作者，原文链接：https://www.sohu.com/a/255558996_775361
SuRF获得了SIGMOD 2018 的最佳论文奖[1]，必有独特之处，学习一下。
在现在KV已经泛滥成灾的年代，随手写一个KV玩一玩也越来越流行了，但是真正能解决KV里面一些典型问题的并不多，SuRF很接地气，思路也很新颖。
做过KV的同学都知道，bloomfilter索引[2]对于判断某个key是否存在是非常高效的，其能用极少的空间（与key长度无关），极低的出错概率判断key的存在性。
但是对于range查询，比如Scan(begin = 'a', end = 'd'), 目前典型的做法还是基于树（B+Tree等），树结构易于理解、速度也比较快，但是太耗费内存，那么是否能有一种结构像树一样快（甚至更快），又占用很少的内存呢？抽象的说，这是本文要解决的核心问题。
本文的思路是基于succinct data structure[3]，将Tree或者说Trie进行合理的编码，从而在降低内存的同时保留查询能力（Succinct的核心理念），这样就在某种程度上将单key查询和range查询合二为一，做到了查询速度持平（甚至更快），且节约内存。
先来看一下succinct data structure，这并非一个具体的数据结构，而是一个约束，即消耗的空间接近信息论下限且提供查询能力的数据结构。来自wiki：succinct data structure is a data structure which uses an amount of space that is "close" to the information-theoretic lower bound, but (unlike other compressed representations) still allows for efficient query operations。不过文中还特别强调其提出的Fast Succinct Tree本质上不算succinct，而只是compact，因为其空间耗费是O(Z)，而Succinct要求Z+o(Z)。
在Succinct思想的指导下，30年前Jacobson提出了一种Level-Ordered Unary Degree Sequence(LOUDS)的编码方式，该编码是理解SuRF的基础，简介如下。
下面的介绍是从思路上介绍LOUDS，不会提到其中的操作如rank0/1，select0/1等，避免陷入细节中而忽略问题本身。让我们从最基础的开始想，对一个树，我们需要什么操作？父亲找孩子，孩子找父亲，广度或者深度遍历的表达式里面给一个位置找到节点，就是这么几个典型操作，对树编码后必须满足这些能力。LOUDS的编码方式有两个核心，一个是广度遍历，一个是节点编码等于孩子个数+0，比如下面图1，根节点2个孩子，编码110。为了下面方便说明，我们假设广度遍历后的编码序列是SS。抽象一点理解，在LOUDS编码序列SS里面，对任何一个位置，开始到该点的bit 0出现的个数表示前面有多少个节点，开始到该点的bit 1出现的个数表示前面的节点加上其直接孩子的节点。如图2示例，4前面有0 1 2 3四个节点，所以在编码序列SS中，4的编码（110）前面有4个0；也可以看到，在编码序列SS中，4的编码位置前面有8个1，所以节点4左边的节点以及其第一层孩子节点加起来是8（包括4或者-1不包括4）。在这种思想指导下，我们看看上面提到的树操作是否是容易被满足的。
父亲找孩子：比如4如何找第一个孩子节点（9）？在编码序列SS中，4编码前面的bit 1出现次数表示4前面的节点以及其孩子节点的个数，这个值是8（从编码序列开头数1的个数到4的编码位置），然后我们又知道bit 0出现次数代表所有左边的节点个数，那么在编码序列SS里面找第8个0，边界处理下就可以了
孩子找父亲：比如9找父亲节点（4）。类似父亲找孩子，只是反过来了，先看编码序列SS中9（0）编码位置前有8个0，表示9前面有8个广度遍历经过的节点，然后从编码序列开始数8个1，表示经过的节点及其直接子节点的个数，这时候也就找到了9的父亲
编码序列里面的位置找节点：非常容易，看其前面有几个0就可以了
我们可以看到succinct解决的核心问题是如何对树编码且保持基本操作能力，同时我们也看到，succinct是对结构进行编码，树里面放什么东西并不关心，比如对图1，树里面是否包含0138这个序列？上面的3个基本操作无法回答。这也是SuRF重点要讲的，即如何让将结构编码和内容搜索结合起来？
假设内存无限，如何在庞大的字符串集合里面快速搜索到一个具体的字符串（想象一下搜索引擎的关键词提示）？trie是一个思路，第一层有256个字符，向下每个字符都有256个字符空间，在这个巨大的空间里面所有的字符串都包含，而且通过一次index就可以直接定位。我们很快会发现这样做不现实，因为第一层32B（bit编码），第二层32*32，第三层32*32*32...，内存消耗增长速度会非常快。常见的做法是空间压缩，如使用链表，而不是数组，这样那些不出现的序列就不会占用空间，这样整棵树就很接近上面LOUDS可以编码的结构了，再取一个byte数组DataArray记录广度优先遍历的每个节点的字符即可。这时候，比如我们要查0138，
从根节点开始，发现0匹配
找到根节点的孩子节点，到DataArray取相应的值，看看是否相等
继续上面的流程，直到发现或者不匹配
上面提示了两个极端，一个是全部使用trie，最快空间耗费最大，一个是全部编码，最慢（在一个巨大的数组里面反复跳跃查找也是很慢的）空间最小。那么能否结合呢？作者观察到字符串的前几个字符是高频的（很多key的共同前缀），应该采用裸trie方式，空间耗费可控，速度快；而后的字符可以采用LOUDS编码，节约空间。而且，文中还设计了一个R调节器，可以自由的控制两者的比例，从而在性能和空间方面达到最佳平衡。
上面只是说了文章的核心思想，并没有完整的描述算法。从图2可以看到，LOUDS-Dense是用空间换时间的部分，而LOUDS-Sparse是时间换空间的部分，具体的细节数据结构都是为了工程实现的，略过。
上面说到了tune，其实除了这个最大的tune因素R之外，还有不少，比如使用look-up table，预取部分字段，为每层保留iterator；比如字符太长，可以截掉中间的部分将尾部放上来，因为尾部更有区分性，比如将字符的hash放到尾部等等细节问题，作者也做了较好的profile。
试验结果分两个部分，一个是基于RocksDB，100G数据做开放和封闭搜索（是否指定结束位置），有1.5到5倍的提升；二是和其他数据结构的对比，见下图，比较有意思的是，C-ART（CompressedAdaptive Radix Tree）和FST（Fast Succinct Tree，本文方法）始终很接近（10%差别可以tune出来，best大概是授予这种新思路），当然，他们都比另外的好太多了。
欢迎纠正、讨论。
[1]. https://sigmod2018.org/sigmod_awards.shtml
[2]. https://en.wikipedia.org/wiki/Bloom_filter
[3]. https://en.wikipedia.org/wiki/Succinct_data_structure
相关资料
https://zhuanlan.zhihu.com/p/38385054
https://zhuanlan.zhihu.com/p/38194127
https://zhuanlan.zhihu.com/p/264173622
https://zhuanlan.zhihu.com/p/31271788
网友评论