Wisckey阅读总结

最近阅读了Lanyue Lu等作者于2016年Fast上发表的《WiscKey: Separating Keys from Values in SSD-Conscious Storage》。在这里我将文章中的各个章节的各个内容进行一些简略的总结。

image.png

paper原文的话大家可以百度or谷歌title，然后点开就能下载。

文章架构

在开始分析文章前，我先将目录架构给读者交代一下。

- 一、摘要

- 二、简介

- 三、背景以及写作目的

1 LSM介绍
2 LevelDB介绍
3 读写放大介绍
4 快速存储的硬件介绍

- 四、WiscKey

1 设计思路
2 键值对分离
3 设计挑战（包括并行查找难度、垃圾回收挑战、碰撞一致性挑战）

- 五、性能优化

1 value日志写区块

2 LSM日志的性能提升

- 六、评估

1 微性能评估（包括数据加载性能、查询性能、垃圾回收性能、碰撞一致性性能、空间放大评估、CPU使用情况）

2 YCSB测评

- 七、相关工作

- 八、结论

文章解读

由于我的水平有限，所以在对文章的理解上或许有些偏差，有不同看法的读者可以相互交流。

一、 摘要

摘要交代了wisckey是基于LSM-tree的键值对的设计思想，并将LSM中的建值分离，并综合利用了不同硬件设备的连续、随机读写特性。最后交代了Wisckey在综合测试中的优势。

二、文章简要介绍

[x]表示第x段讲述了什么什么。

这里[1]首先交代了键值对的存储系统在当前生产生活的重要性。之后交代了[2]LSM-tree在“写”数据上的连续性优势。（与B树进行比较）

image.png

[3]下一段很明显的交代了LSM-tree是如何在“写”操作上具有高性能的。包括连续写、在后台进行排序等，以及IO放大问题。

[4]下面交代了HDD（机械硬盘）对LSM-tree的影响。

image.png

于是最好使用连续读与写来操作数据。

[5]第五段讲述了三点SSD与HDD的不同。下面我们详细说明下。

①首先是对于SSD来说，随机读与顺序读的差别没有那么大。因此LSM-tree会在写操作的时候就进行了大量的IO操作以减少读的时候的IO操作。

image.png

②SSD内部有高度并行机制。所以我们设计的LSM需要能够适应SSD的机制。

image.png

③SSD会因为重复写而导致损害。所以LSM中的高写入会影响SSD的寿命。

image.png

[6]wisckey降低了写放大，减少了LSM的大小并且在查询数据的时候能更好的利用cach。

[7]简单交代了一些key-value分离后的弊端。

三、技术背景以及设计动机

1 LSM介绍

LSM为顺序写，所以比B树要快。具体的LSM树我会在其他文章中单独写出来。

最后，文章比较了LSM与B树，并交代了LSM多用于写>读的系统中。

image.png

2 LevelDB介绍

在这里文章讲述了LevelDB的核心设计。其包括一个磁盘日志文件、两个内存表、七个level0~level6的磁盘存储表。在后台，这些写入的数据都会自行排序。然后从memtable -> immutable memtable -> level0~level6。最后讲述了一些合并上的细节。

3 读写放大介绍

[1]首段讲述了读写放大问题是LSM中最主要的问题。

LSM-Tree 能将离散的随机写请求都转换成批量的顺序写请求，以此提高写性能。

• 读放大（Read Amplification）。LSM-Tree 的读操作需要从新到旧（从上到下）一层一层查找，直到找到想要的数据。这个过程可能需要不止一次 I/O。特别是 range query 的情况，影响很明显。

• 空间放大（Space Amplification）。因为所有的写入都是顺序写（append-only）的，不是 in-place update ，所以过期数据不会马上被清理掉。
  RocksDB 和 LevelDB 通过后台的 compaction 来减少读放大（减少 SST 文件数量）和空间放大（清理过期数据），但也因此带来了写放大（Write Amplification）的问题。

• 写放大。实际写入磁盘的数据大小和程序要求写入数据大小之比。正常情况下，HDD/SSD 观察到的写入数据多于上层程序写入的数据。原因是在compact的过程中，我需要额外的进行写操作以便能够将数据从一个level写入到另一个level，所以这个过程就增加了写入量。

而这里我们放上我引入的一段对HHD和SSD的读写放大说明。

9B2FCB5C-A5D1-4C8A-86D2-15B7505F42D3.png

[2]写放大在两个level之间能够达到10以上。又因为这里有7个level，所以从level1~level6可能会使写放大达到50 。

Since the size limit of Li is 10 times that of Li−1, when merg- ing a file from Li−1 to Li during compaction, LevelDB may read up to 10 files from Li in the worst case, and write back these files to Li after sorting.

[3]这一段讲述了读放大的问题与原因。第一个原因就是在LevelDB中进行查找操作时需要查找很多个文件。

image.png

第二个原因是在SSTable中查找需要读取大量的元数据。

image.png

[4]这里作者进行了一个实验，使用16b的键，1kb值分别在1G与100G的系统中做操作。结果如下图。

image.png

写放大的原因是：当写入的数据越多，系统在从低level到高level的过程中的compact过程中需要写更多次。

读放大的原因：当database越小，索引块和布隆过滤器可以很好的放入到cach中，当变大的时候，那么就需要不断的将这些块放入到cach中，消耗了替换的过程。

image.png

4 快速存储硬件介绍

[1]在SSD中初始随机写的效率还算正常，不过当写入的次数增加后，效率就会随之而来降低的很快了。所以对于SSD来说，使用LSM能多次进行顺序写从而有利于SSD。

[2]在某些情况下，SSD中的随机读的效率与顺序读几乎一致。

image.png

最后的结论是，在读取数据量达到16kb以上的时候，32线程的随机读吞吐量==顺序读。

image.png

四、Wisckey的详细介绍

开篇提出LSM更适合于传统的硬盘，然而对于SSD它并不适合。之后第二段提出了四个核心观点：键值对分离、使用SSD的并行特性进行随机查询、使用碰撞一致性已经垃圾回收机制去管理log、移除LSM日志文件。

image.png

1 设计目标

[1]Wisckey可以被部署为关系型数据库和键值对类型数据库。之后又从五点分别介绍Wisckey的设计目标。

2 键值对分离

[1]讲述了LSM中最大的性能限制就是compact过程。它会持续的对文件进行后台排序（需要进行大量的IO操作），不过这个过程会对查询有帮助。

[2]第二段讲述了设计中比较核心的一点，就是只在LSM中存储key，而value存储在其他位置。又因为现在的键值对特征就是键很小，值很大所以这种设计思路有助于减小写放大。

image.png

[3]交代了wisckey由于采用了键值存储位分离，所以它在lookup的过程中会查询更少的levelx，且更容易放入cach中，所以会更为迅速。

[4]解释了Wisckey的存储模式。

image.png

[5]先插入value于vlog中，然后再将key插入LSM中。删除的时候只删除LSM中即可，剩下的内容在垃圾回收的时候删除。

五、挑战

这里提出了垃圾回收挑战、碰撞一致性挑战的解决办法。

1 并行范围查询

[3]在LevelDB中，由于键值在一起，所以查询可以进行连续读。然而在Wisckey中，这里就需要随机读操作了。不过根据我们上面的“SSD中顺序、随机读吞吐量比较”我们知道SSD中的并行读取操作可以在请求量大于16kb的时候与顺序读效率接近。

不过在这里我不是特别理解这里的“prefetch（预取）”是如何进行的。

image.png

[5]这里应该是讲述了预取是如何进行的。如果用户进行一个范围查询，那么系统会首先把LSM中的key全部找到，并依次将value的地址添加到一个队列当中。然后后台就会根据队列的值进行多线程的查询操作。

2 垃圾回收机制

[1]LSM在做删除操作的时候不会立即清空空间。空间只会在compact的时候清理。然而在wisckey中，我们只会清理LSM中的key，所以对于value来说，我们并不会进行常规的空间清理操作。所以这里需要一个特殊的垃圾清除机制。

[2]交代了一种常用的很笨重的清理方法。这里不做叙述。

[3]Wisckey目的是需要一种轻量级并且在线删除的机制。我们在vlog中存储value的同时也会存储相应的key。

image.png

[4]上图中head是新加入值的位置，而tail是垃圾释放空间的起始位置。两个指针中间的存储的包含有效值。

[5]此处详细的讲述了垃圾回收机制。首先从tail处读取一个简直对，然后同过查找LSM来检验这些value哪些是合法的（没有被覆盖或者删除）。然后会把合法的值加入到log的head处。最后释放空间并更新tail的位置。

[6]为了避免在垃圾回收的时候出现碰撞从而使数据丢失，所以这里需要：在将value加入到vlog后，回收机制会调用fsync()函数，（后面的这些步骤就是这个函数的具体操作）然后用同步方式将这些新的value地址与当前tail添加到LSM中（<‘‘tail’’, tail-vLog-offset>），最后释放vlog中的空间。

不过这里我一直对这个crash有些疑问，我们提前将tail和value的地址加入LSM是如何避免数据丢失的呢？？

3 碰撞一致性

其实我在这里不是特别清楚这个碰撞的具体含义，需要更加清晰一下

[1]给出了一个结论是，如果一个X值在碰撞中丢失，那么它后面的值同样也会丢失。

[2]碰撞发送后，Wisckey需要验证是否value的地址在vlog的有效区域内，然后验证是否key与value对应。如果验证失败，那么可以肯定数据在碰撞中存在丢失，然后从LSM中删除这个key并对用户进行通知。

在vlog中，每个新加入的value都有其对应的key的位置，所以上述验证过程十分容易。

六、性能最优化

感觉这一部分偏重于解释为何我们这样设计会提升性能balabala，然后穿插讲解各个部分是如何工作的。

1 vLog的写入操作块

[1]还是在说老事情，就是对于Wisckey来说，写小内容的操作增多会导致overhead。所以还是要想办法解决如何避免大量写入小规模数据的问题。

[2]为了减少overhead的问题，wisckey采用了一个新的机制。这里是我个人的理解。

我们在上面提出了，大量的小规模value写入会导致大量的write()函数调用。这也会导致插入密集性工作降低系统的效率。所以为了减少write()函数的调用，我们可以在用户的空间中开辟一片区域，然后将大量数据提前写入到此处，并以此来减少write()的调用。

对于读操作，系统会首先查找这片区域，这里找不到则再去找vlog。（不过此处还补充到这种机制可能会提高crash的几率，导致数据丢失，这没办法了有利有弊emmm）

2 LSM-tree日志文件的性能提升

[1]这里又重申了vlog里面存key的事实。

[2]此处讲述了如果在存入vlog后但是还没来得及存入LSM时发生了碰撞，需要如何恢复。传统方法就是便利所有，但是很花时间。所以这里在LSM中定期记录了vLog的head地址<‘‘head’’, head-vLog-offset>。每次恢复都从记录处开始，并按照插入顺序进行恢复（以vlog为参照恢复LSM）。所以这就是为什么我们可以放弃LSM的log。

七、实验部署环境

讲述了Wisckey是基于什么而搭建的。

然而这里讲述了在垃圾回收机制运行的过程中使用了hole机制。

这里需要更多的研究。

image.png

八、性能测试

所有的实验都是在two Intel(R) Xeon(R) CPU E5-2667 v2 @ 3.30GHz pro- cessors and 64-GB of memory上进行的。操作系统是64-bit Linux 3.14。存储设备是500-GB Samsung 840 EVO SSD，达到了500 MB/s的顺序读以及400 MB/s的顺序写速度。

下面的性能测试均没有使用压缩算法。

1 写入性能

[2]这里对LevelDB和wisckey分别进行测试，并发现吞吐量会随着value不断增加而增加。但是wisckey的上限远远大于levelDB。

image.png

而后对其原因进行了分析，得出在LevelDB中，时间花费在三个方面：①将数据写入log文件、②将数据写入memtable、③等待memtable刷新

image.png

而当key-value的规模比较小时，会花费更多时间。下面是相关测试。

image.png

而对于较大的键值对来说，写入和排序过程更为迅速。

[3]这里对随机写入进行了测试。

image.png

这里我们能很明显的看到LevelDB有很低的吞吐量，因为带宽在compact过程中消耗巨大。

而后又介绍了随机写当中的写放大测试。Wisckey的写放大在1k之后就降到了1左右，原因是其LSM-tree比LevelDB中的要小的多。

image.png

2 查询效率

[1]虽然在Wisckey中查询时需要先查询LSM再去获取value的地址，但是它仍然比LevelDB的效率要高。其原因归结于LSM-tree小、compact操作过程中处理的数据小，也就意味着后台的读写规模都要小。

image.png

[2]之后对不同系统的随机和顺序读写进行了测试工作。

由图可知在4K前，所有的类别均呈现上升趋势。然而对于大于4K的情况，wisckey由于其本身特性所以会大于levelDB，而在4K以下却相反。（这里在前文的对SSD测试的部分中有所介绍）

image.png

[3]此段落交代了在64B处，wisckey-seq要比leveldb-seq慢百分之25的原因。wisckey需要从key和value两处进行查询才能获取到内容，所以当vlaue变小的时候，这种活动就变的更多了，所以就更占用贷款。所以还是value较大会更对wisckey更为友好。

3 垃圾回收

[1]垃圾回收测试分三步：

• 使用随机写的方式建立数据库。
• 删除一部分比例的键值对。
• 运行系统并进行测试。

[2]如果垃圾回收中的数据全部都是丢失的，那么只会影响百分之十。因为如果全部都不合法，那么数据就没有必要写入了。

image.png

4 碰撞一致性

是个狠人。

5 空间放大

[1]交代了放大的概念。

[3]WiscKey比WiscKey-GC大的原因就是因为前者没有进行垃圾回收，所以占用的空间大（包括了多余的value和元数据）。

image.png

[4]交代了一个世界难题。LevelDB中排序和垃圾回收在compact中进行了，所以用写放大来减小空间放大。而Wisckey用空间换取时间，减少IO操作。

image.png

而后面就是一些标准的测试工作。本文重点讲解架构已经设计思路，所以这部分就不写了吧。

这个文章真的是写了好久好久，边理解边分析。第一篇文章到此结束，后期会有更多相关的文章分析的。欢迎读者们指正！