本文转载自微信公众号《代码农桃花源》，作者冉小龙。转载本文请联系码农桃花源公众号。最近看了WiscKey的论文，感触很深，特写这篇文章表达一下自己的观点。说句废话就是：任何软件的发展其实都依赖于硬件的设计和进步，所以从这个角度来看，LSMtree诞生于1980年代，而那个时代，还是机械硬盘的时代。因此可以看出，整个LSMtree最初的构建思路是基于机械硬盘的设计思路，但是需求是无穷无尽的。WiscKey感觉是在LSMtree的基础上基于SSD的设计思想进行的优化。基于这个思路，我们来简单分析一下论文中的观点。让我解释一下LSMtree的几个概念：读取放大是满足特定查询所需的I/O数量写入放大是写入存储的数据量与应用程序写入的数据量之比。空间放大是数据结构所需的空间可以通过碎片或数据临时副本的要求而膨胀。读写放大就不说了。了解LSMtree的人基本都懂。现在我们来说说空间放大的问题。空间扩大一般是指用于存储的数据结构由于拆分或临时数据复制而扩大。LSMtree从诞生之日起，就不是为了存储这些大的值。在这么大的值的情况下，LSMtree的性能会迅速下降。所以，其实数据库有自己的保护机制来限制每一行值可以存储的最大值。下面是wisckey和LSMtree的对比。可以看出，当取值较大时，wisckey的性能远大于LSMtree。下面是wisckey和LSMtree经过随机化排序后的对比：其次，LSMtree有这种compaction操作。在做compaction的时候，磁盘IO的压力比较大。再者，LSMtree不能很好的利用SSD的并行计算能力也是可以理解的。不过在目前的存储引擎中，LSMtree还是很流行的。从性能上看，读写扩大就算是空间扩大（这三者不能共存）。在最坏的情况下，我会放大10-50放大成本大约是10倍，但我可以在性能上带来千倍的速度提升（将随机写入转换为顺序写入），所以，在性能方面，这些都可以忍受。SSD和SATA的区别顺序IO和随机IO并行计算能力大量的重新读写会减少SSD的寿命。当值很大时，LSMtree的值越大，越容易触发compaction。LSMtree的每一层都可以简单理解为下一层的缓存。该值越大，缓存效果越差。到达较低级别的可能性会增加。每合并一条数据，写入量都会增加。wisckey诞生的前景其实我们可以仔细回忆一下，在LSMtree中，我们并不需要values是有序的，只要key是有序的就可以满足我们的需求。那么，是否可以考虑继续将key存放在LSMtree中，将value单独存放在日志文件中，然后将value的指针一起存放在LSMtree中呢？是的，这也是wisckey的思路：分离模型大致如下：这时候我访问数据的方式是这样的：insert:先append到valuelog的末尾，然后insertaddress刚刚附加到LSMtree中的值。delete：从LSMtree中删除键。在compaction的时候，如果找不到对应的key，那么在垃圾回收的时候一起回收就可以了。select：将LSMtree中的key+addr直接获取到value对应的地方，取出即可。wisckeykey/value分离的优势首先，与原有的存储模型相比，key存储数据量减少了一个数量级以上。因此，可以充分利用LSMtree的特性。其次，value分离后，避免了compaction操作过程中的无效value移动，从而大大降低了读写放大，增加了SSD的使用寿命。此外，由于密钥存储级别的降低，缓存可以达到更好的效果。可能出现的问题以前operatingrange时，只需要顺序读，k/v分离后，可能需要顺序读+多次随机读才能达到目的。论文中提到，这可以充分利用SSD的Parallel能力来解决，但能解决多少还有待进一步追踪。上面说了lsmtree中value的delete操作在compaction时依赖于GC，但是k/v分离导致这个rec??overy是异步进行的。基于此，我们来看看wisckey的处理思路：whiskey优化了原有的垃圾回收方式，head指向插入最新块的位置，tail表示回收值操作开始的位置。GC触发后，我们从tail开始扫描，将有效块移动到head后面，清除tail到head的section，重新设置tail和head标记。不难看出，将有效块后移的操作在一定程度上也带来了写放大，但确实提高了效率。简而言之，它是时间和空间之间的权衡。Wisckey会根据删除操作请求的数量来决定何时触发GC。崩溃一致性。由于操作分离，一旦发生意外，wisckey如何保证崩溃的一致性？对key和value的操作是原子的，一共有三种情况：key/value都写入成功，OK，这就是我们想要的效果。如果key写入成功，value写入失败，LSMtree中的key会被删除，返回值不存在。key写入失败，value写入成功，返回不存在。写入的值在后续的垃圾回收中被回收，就OK了。如果遇到宕机重启，在恢复过程中会依次恢复。可能出现的问题如果我的valuelog存储的是一些比较短的值，每次都需要和磁盘进行交互，对磁盘的吞吐量是一个考验。可不可以考虑在这里加一层缓存结构，合并后写入多个小值。未完待续，向外国同行致敬。关于这篇论文有一个100页的幻灯片[1]和PDF[2]，非常详细地描述了这篇论文的思想。参考文献[1]WiscKey：幻灯片：https://www.usenix.org/sites/default/files/conference/protected-files/fast16_slides_lu.pdf[2]WiscKey：pdf：https://www.usenix.org/system/files/conference/fast16/fast16-papers-lu.pdf作者简介：ApachePulsarcommitterApacheBookKeepercontributorApachePulsarGoclient作者及国内主要维护者ApachePulsarGoFunctions作者及国内主要维护者stremnative/pulsarctl作者及国内主要维护者streamnative/rop作者及国内主要维护者【责任编辑：吴晓燕电话：（010）68476606】
