LSM-trie阅读总结

image.png

这是第二篇Fast文章总结。为了更好的了解存储效率的提升方式，我对这篇LSM-trie结构进行了分析。这篇文章不如Wisckey好理解，所以在阅读的过程中我也存在一些待解决的问题，我会将问题在文中列出，方便自己之后的阅读。

这篇文章是美国高校实验室的一位华人学者发表的（不得不承认我们国人还是蛮厉害的！Orz崇拜的很）。我在阅读的过程中本打算像阅读Wisckey一样参考一下同行们的分析，不过我在Google于Baidu后均没有发现有类似的参考，所以我就将我自己的理解整理到这里，这其中肯定会存在大大小小的问题，欢迎读者们进行指正工作，也希望大神们能帮助解决相关的问题。

一、文章架构

本文分如下标题：

• 1 摘要：KV存储的重要性、现存KV系统的弊端、本文提出的方法、实验结果。

• 2 相关技术介绍：KV存储的三个特点、本文方法的简短介绍。

• 3 LSM-trie设计模式：LSM-tree中的写放大、如何减少写放大、设计SSTable-trie来减少写放大、LSM-trie的具体操作流程

• 4 性能评估：读、写测试。

• 5 相关工作

二、摘要

[1]首段重点说明了KV存储目前存在的几个不足之处：高写放大、索引空间大、当索引量急剧增大时，读效率降低。

[2]解释到LSM-trie能够成数据量级地减少写放大。

三、技术介绍

[1]介绍了kv存储在当今产品中的地位。

[2]kv存储的方便之处，包括kv的部分基础操作接口等。

[3]提到了kv存储中大部分的kv对均是小规模键。之后提出小键值对会使系统建造出更多的元数据（布隆过滤器）来进行存储。

[4]对kv存储系统的性能要求愈发的提升。尽量使用单机系统搭配相应的硬件去进行存储工作。

[5]对读写性能的要求提升。并提到如果大量的元数据没有存储在内存中，那么系统就需要在每次进行数据读取请求时耗费大量的时间来进行寻找。

[6]trie系统支持单机对百万级别的小型数据进行处理。并能够达到写操作500k/s，读操作50k/s。其使用了一种新型方法，将“指数”与“线性”LSM模式相融合，以便达到降低写放大并提升读写效率的要求。之后又提出使用了布隆过滤器集群来方便系统定位kv对。

[7]由于LSM-trie使用了哈希，所以它不支持范围查询。

四、LSM-trie的设计

设计的动机是为了减少写放大。

1 LSM-tree中的写放大问题

基于LSM-tree的kv存储共有两个设计理念：（1）新数据要能够快速写入（2）系统要支持快速查找。这里文章针对Level-db进行了对这两个理念的详细介绍。

Level-db维持了一个index在4kb的数据块中。然而这个index并没有解释kv对是否真正存在于块中（因为index只是标注了块的起始字典索引）。所以系统维持了一个布隆过滤器去查找该块是否具有相应的kv。

image.png

为了方便查找，level-db对table进行了合并操作。但是也会带来庞大的写放大问题。

2 LSM-tree在合并过程中的写放大问题

由于将数据从上一个级别合并到下一个级别中要重写许多数据，所以这个过程大量增加写放大。之后作者提出构想，如果仅仅只有上层数据参与合并的过程而下层数据不参与，那么将会极大减少写放大的水平。

为了实现作者的构想，作者设计了一个线性的合并模式。

image.png

在这里作者提出了sub-levels的概念。在L0中由于数据是直接顺序写入的，所以每个L0中包括了key-range相同的许多table，所以我们称每个table都是L0的sub-level。而除了L0之外，我们将这种设计引入到其他的level中。

简单来说，我们就是讲每一个Level均由多个sub-levels替代，以减少写放大。之后在合并的过程中将这些sub-level中的数据进行合并，并将合并后的内容作为下一个level。通过这种方法，我们就很好的减少了要重写的数据量，所以也就很好的减少了写放大。

image.png

文中交代到，为了实现线性模式，我们需要在每个sub-level中选择一个sstable，并将这些内容合并成排序成为下一个级别的非重叠序列。

不过在这里存在一处理解问题。如下图所示。从Lk到Lk+1的合并过程中，我们必须确保他们的key的范围是没有重叠的以用来避免Lk+1中存在两张表具有重叠的key范围。为什么这里要交代这个问题？难道我们在每个sub-level中选择的sstable均要使key不重叠吗？如果重叠了我在合并过程中把重叠部分放一起不就可以了？这里我还是不太理解。

image.png

除此之外，下面这个部分也同样存在理解上的困惑。它讲到在LevelDB中的kv存储是according to表的容纳大小（32MB）？难道说我的key range是要根据表的大小来存储的吗？这里同样需要进行更深入的探究。

image.png

3 SSTable-trie介绍

这里使用了哈希函数来划分table属于哪里。这里将LevelDB的多表结构划分成为了一个前缀树

image.png

根据图片，我们可以将每个节点看做一个table容器，每个容器中存储了大量的tables。每个节点拥有固定数量的子节点（具体的数量为AF，放大系数）。而节点的对应前缀设计如下：If the number is assumed to be 8, a node’s children can be distinguished by a three-bit binary (000, 001, . . . , or 111)。

而根据hash-key的具体二进制内容，我们可以很轻松的找到kv的所在container。而在同一个深度的所有节点组成了一个level。每一个容器都有一个table集合。一个trie-level由许多这样的table集合组成。

image.png

位于同一个level中，且在不同table集合的同一个位置的table们组成了trie的sub-level。

image.png image.png

kv对在level中的位置是通过hashkey进行前缀匹配的。

image.png

根据上图内容，我们将trie与level-db进行比较，trie的合并操作只存在于一个container中，即一个table集合。当合并后，在一个table集合中的kv对会根据其hash-key的值而分配到不同的子节点中。

image.png

根据上面这句话，我们可以大致理解合并的时候是将一个container中的tables进行合并，并将合并后的内容放到子level中。

不过下面这句话也同样存在疑问？

image.png

4 LSM-trie

在level-db中存储空间中为了了一个内存tree用来定位每一个level中的sstable。然而index和布隆过滤器会随着kv存储量的增加而变大。直到内存中装不下这些索引数据，到那时，硬盘读的次数就会增加，效率随之就会减慢。所以我们的目标就是如何减少每次数据请求所需要的元数据读取量。

image.png

不过对于LSM-tree这种结构来说，元数据与sstable相连，所以很难减少读取量。

所以我们这里引入了另外一种结构：LSM-trie ，并放弃了index这种元数据，并引入了布隆过滤器来进行数据查找操作。As we will show, LSM-trie removes indices and uses only one disk access to read Bloom filters。最后，只进行一次磁盘读便可以找到相应的过滤器内容。

Htable

这里在设计时使用了Htable来代替SSTable。

image.png

在SSTable中，我们需要存储索引数据以及kv数据。然而在HTable中，一个block被称为一个bucket并被用于存储kv对。（图中的黑色块块）

image.png

hashkey是由160bit的sha-1哈希生成的。并且其前缀用于识别SSTable的位置，其后缀用于识别在Htable中bucket（Disk block黑色块块）的位置。

image.png

Specifically, if there are m buckets in an HTable, a KV item with Hashkey h would be placed in Bucket (h mod m)——关于kv在m个block中是如何存储的

为了很好的放弃index，我们必须令bucket为固定大小（为了方便布隆过滤器进行查找）。

image.png

上图呈现了不同id的bucket的负载情况。我们保持存储量在95%，这样能够使过载和不足情况均不存在。

为了使每一个block中的数据保持在4kb以内，我们需要平衡过载块与不足块，并将过载数据用算法迁移到不足块中。（从最过载块移动到最不足块，之后继续移动直到所有块均满足要求）

image.png

对于那些kv对过大的数据，我们创建了一个新的Htable进行存储。在这个特殊HTable中的所有kv对均被进行索引。这些索引同样被保存在HTable中并被在查找数据时载入到内存。

下面，我们要着手解决如何高效查找块溢出的数据。我们使用哈希函数来对key进行处理，并对key进行逻辑存储。我们规定超过4kb的值均被标记为溢出数据。我们只需要记录存在于watermark处的kv对，以便我们之后能更容易了解此kv对是否被移动。哈希如下：

image.png

在该哈希中，我们选定了32bit来进行上述操作（from 64th bit to 95th bit）。然而一个溢出的kv对有可能会被不断的进行移动，所以为了减少kv对的移动次数，我们通过调整infix的特定位数来调整哈希函数。这样使得不同bucket有不同的哈希方法。

这里的具体操作过程也值得我进一步考虑。我认为infix就是用于对bucket的kv进行排序，所以如果使用了同一种hash方法，那么无论这个kv在哪个block中，都有可能是最后一个，均会溢出。所以要更换哈希方法。

而根据图四我们知道，HTable中存在index索引数据，而这个数据包括bucket ID (2 B), a migration des- tination ID (2 B), and a HashMark (4 B)。

不过我们在读取数据的时候需要将所有的index全部读入内存吗？当然不需要，根据图五的那个zipfian分布函数，我们知道只有20%的bucket有溢出数据，所以我们只需要缓存这20%的index，并直接去特定的目标bucket查找即可，并不需要磁盘读取。

而对于布隆过滤器来说，存在溢出的块也不需要更新布隆过滤器。这些kv对仅是逻辑存储在bucket中，而物理上存在其他地方。

Bloom Filters集群

当数据量提升后，查找布隆过滤器就成为了一个艰难的工作。trie假定所有同一个level的bloom都要在查找中使用，但是无法通过一次磁盘读将所有的布隆过滤器读入cach。为了解决这个问题，作者提出了一个方法：

image.png

将不同sub-level中的同一个位置（一列bucket）的布隆过滤器进行打包装入一个磁盘块中，并命名为BloomCluster。

不过对于具体的布隆过滤器的操作流程，这里我还不太清楚。

系统将所有sub-level的布隆过滤器放入BloomCluster中，并经过一次磁盘读就ok。而根据下表，16比特的布隆过滤器对于10TB（112个sub-level）的kv存储系统来说也就5%的错误率。平均1.05次磁盘读即可。

image.png