面向键值存储的日志结构合并树优化技术

吴尚宇 谢婧雯 王 毅

(深圳大学计算机与软件学院 广东深圳 518060)(shangyuwu1006@gmail.com)

大数据时代互联网产生了海量多样化的信息资产，对现有数据库存储以及管理数据的能力提出了更高的要求[1].传统关系型数据库难以再支持对海量数据的高效读写等需求，这使得具有优异扩展性能的非关系型数据库逐渐入驻存储的世界.

键值存储是非关系型存储的一种常见方式，模式简单、易于扩展[2].键值存储通过去除关系型数据库中一些不必要的特性，有效地提升了自身的存储性能，降低了数据之间的耦合度[3]，越来越广泛地应用于现代数据中心.目前键值存储系统采用的主流架构是日志结构合并树(log-structured merge tree, LSM-Tree)[4].LSM-Tree的基本思想是通过聚合内存中的多个写操作，将它们以批处理的形式转储到文件中，再按顺序将这些文件写入磁盘.同时，LSM-Tree通过压缩操作使这些文件按多级分层存储，以便于快速查找.与传统B-Tree[5]相比，LSM-Tree将随机写转换为顺序写，极大地提高了写效率.LSM-Tree是目前数据库系统采用的主要存储引擎之一，是众多分布式组件的存储基石[6].许多的企业都采用它来搭建存储应用，如谷歌的BigTable[7]和LevelDB[8]、Facebook的RocksDB[9]和Cassandra[10]、Apache的HBase[11]和雅虎的PNUTS[12]等.

在现实世界中，键值存储的请求模式往往都是读多写少的，如在Facebook的Memcached系统中，请求的读写比已经高达30∶1[13].LSM-Tree结构为了提升写效率牺牲了一部分读效率，从而使得读放大问题更为严重.现在国内外面向LSM-Tree的研究主要都是针对写性能的提升，在读性能方面上的研究较少.Zhang等人[14]提出ElasticBF，为每个文件更细粒度地划分了多个小过滤器.这些小过滤器通过动态算法载入内存，减少了不必要的查找，提高了LSM-Tree的读吞吐性能；Teng等人[15]提出LSbM-Tree，通过增加1个压缩缓冲区来减少由压缩操作引起的缓冲区的失效问题；Wu等人[16]提出LSM-trie，通过构造1棵字典树或前缀树来加速查找.Sears等人[17]提出了bLSM，bLSM结合了B-Tree的优点，通过增加弹簧和齿轮(spring and gear)调度器来决定LSM-Tree中不同层级的压缩操作的执行顺序.bLSM有效地提高了LSM-Tree的读性能，同时减缓了因压缩操作导致的写暂停问题.这些研究工作都增加了额外的数据结构，显著地提升LSM-Tree的读效率.我们的方法旨在从LSM-Tree的数据流向上考虑，通过改变数据流向来减小读放大问题.

本文从LSM-Tree的数据流向出发，对冷热数据进行区分，提出一种基于访问频率的上浮式键值存储结构(floating key-value, FloatKV).FloatKV在内存中提出了一种新的数据存储结构LRFO(LRU and FIFO).LRFO能够使高频访问的数据在内存中驻留更长的时间，以减少不必要的IO操作.FloatKV在外存中统计了数据的访问频率，并设计了一种基于访问频率的上浮式键值存储策略.它能够根据数据当前的访问频率自适应地调整数据存储的位置，以减少读延迟和读放大问题.为了验证FloatKV的可行性及性能，我们使用标准数据库性能测试工具YCSB(yahoo! cloud serving benchmark)来进行评估，并将FloatKV与当前主流的键值数据库LevelDB及显著提升LSM-Tree性能的Wisckey算法进行了比较.实验结果显示，相比LevelDB和Wisckey，FloatKV显著地提升了读效率，平均减少了77%的操作总延迟，有效地减少了读放大问题，平均减少了95%的读放大.

1 背景知识

1.1 LSM-Tree

LSM-Tree的基本结构为多棵树的集合，其中最小的1棵在内存中，其他都在外存中.如图1所示，以2棵树为例，较小的1棵C0树在内存中，而磁盘上较大的1棵C1树则由内存部分持久化得到.C0树和C1树的具体结构类似于B-Tree.C1树所有节点的大小为磁盘块大小.C0树和C1树共同维护一个键值有序的键空间.

Fig. 1 The architecture of LSM-Tree

当写入1条新数据到LSM-Tree中时，根据数据的索引值将数据插入C0树中.内存中C0树的大小存在一个阈值.当C0树的大小达到阈值时，一部分数据将从C0树通过滚动合并的方式被持久化到C1树中，即批量地把这些数据写入磁盘.

LSM-Tree对比传统B-Tree来说，它的优势在于在一定程度上优化了磁盘写入问题，但在进行读操作的时候可能要访问比较多的磁盘文件[11].

1.2 LevelDB

Fig. 2 The architecture and operations of LevelDB

LevelDB是基于LSM-Tree实现的非常高效的键值存储系统.它将随机写请求转换为顺序写请求，保持了数据高效的持久化存储.图2展示了经典的LevelDB结构.LevelDB将内存分为2个部分：MemTable，Immutable MemTable.它们都是基于跳表实现的，均能达到O(logn)的查询和插入效率；外存主要以SSTable(sorted string table)文件的形式来存储键值对，同时还包括了一些辅助文件：Log文件、Manifest文件以及Current文件.外存中的SSTable文件在逻辑上被分为多层结构，称为L0,L1,…,L6.每层都设有文件的上限个数或大小，除L0层以外，其他各层的SSTable之间均不存在键值范围的重叠.Log文件记录了已经进行的所有操作，用于恢复崩溃的LevelDB；Manifest文件记录了所有SSTable文件的meta信息；Current文件记录了当前最新的数据库状态.

当往LevelDB写入1对键值对时，LevelDB首先将操作日志写入Log文件，然后再将键值对插入MemTable.为了能够快速存储新数据以支持内存中的高吞吐量写入[18]，MemTable在大小达到阈值后会被转换成1个Immutable MemTable.同时，LevelDB会创建1个新的MemTable来迎接新请求.当有2个Immutable MemTable同时存在或其他主动触发的情况发生时，Immutable MemTable中的键值对将被以SSTable的形式持久化到磁盘中.随后，LevelDB会将新产生的SSTable插入到多层文件结构的L0层中.当存储在L0层中的SSTable文件的个数达到上限时，LevelDB开始进行压缩(compaction)操作，将键值对往低层移动.具体来说，对Li层的压缩操作，首先从Li层选择出1个目标SSTable，再从Li+1层中选择与其键值范围重叠的所有SSTable；然后，将这些SSTable都读入到内存，通过多路合并算法得到新的SSTable；最后，将这些新的SSTable重新插入到Li+1层中.当LevelDB需要读取1个键对应的值时，它需要依次从MemTable，Immutable MemTable以及L0～L6层的SSTable中查找.

LevelDB中最突出的问题就是写放大和读放大问题.写(读)放大倍数被定义为写入(读取)底层存储设备数据量与用户请求的数据量之比.造成写放大的原因是：1)SSTable文件中的索引部分以及其他加速查找的部分如过滤器造成了额外的写开销；2)压缩操作写入的新SSTable也会带来额外的写开销.造成读放大的原因是：1)LevelDB的试探性查找机制需要检查多个文件才能找到真正包含键的SSTable；2)确定SSTable后仍需要读取索引等部分才能确定键值对；3)压缩操作读取的SSTable会造成额外的读开销.最差情况下，LevelDB需要检查14个SSTable(在L0层检查8个SSTable，L1～L6层每层各检查1个)才能找到真正的键[19].同时，压缩操作在一般情况下会读取至少5个甚至更多的SSTable[20].

1.3 键值分离

Lu等人[19]认为不断重新排序SSTable的压缩操作是影响LSM-Tree性能的主要原因.在压缩操作的进行过程中，SSTable被读进内存，重新排序，再写回外存，这一系列操作极大地影响了LevelDB的读写性能.通过观察这一系列操作，Lu等人发现压缩操作只是根据键(key)来进行的，值(value)并不影响压缩操作的进行.同时，在多数情况下值的大小都远远大于键的大小.所以，Lu等人得出结论：压缩操作所带来的额外的写开销主要是因为值在压缩过程中的反复读取和写入.

根据观察得出的结论，Lu等人提出Wisckey，一种键和值分开存储的思想.它主张将键存在LSM-Tree中，将值单独存在1个日志形式的文件vLog中.当往数据库插入1个键值对时，Wisckey首先将值追加在vLog尾部，记录值在vLog中对应的地址.然后，Wisckey将值的地址与原来的键组成新的“键值对”.最后，将这个“键值对”插入LSM-Tree中.当读取1个键对应的值时，Wisckey首先在LSM-Tree中查找到对应的“键值对”，再根据“值”(地址)去vLog中查找真正的值.由于地址的大小很小，基本可以忽略不计，这使得Wisckey中LSM-Tree远远小于LevelDB中的LSM-Tree.LSM-Tree大小的减小显著地降低了压缩操作的开销，也减小了写放大和读放大问题.当运行一段时间后，Wisckey中的vLog会包含许多无效数据，这时候Wisckey就需要对它进行垃圾回收操作.对vLog的垃圾回收操作需要将vLog头部已经过期的值删除，并重新在LSM-Tree中更新这些值里的有效值的地址.特别地，当vLog回收的所有值均为无效值时，Wisckey的吞吐量将会有10%的降低.

2 FloatKV

2.1 设计目标与动机

LevelDB以及Wisckey已经具有极高的写性能，但读性能仍有待提升.而现实世界中大部分应用的请求模式都是读多写少的，我们希望能够在不损失大量写效率的基础上，提高LSM-Tree的读效率，减少读放大问题.

通过对LSM-Tree结构以及查找机制的分析，我们得出2个限制LSM-Tree读性能的因素：一是LSM-Tree的查找机制决定了在查找1个键时需要额外检查多个文件；二是压缩操作也会退化LSM-Tree的读效率.而更换查找机制或压缩操作可能需要改变整个LSM-Tree的结构，这样做的开销过大.于是，我们考虑通过往LSM-Tree结构中添加新的操作和策略，在保留原有结构和操作的基础上减少LSM-Tree的读放大，提高读效率.以LevelDB为例，我们观察到在LSM-Tree中的数据流动方向是单向的：数据从MemTable流动到Immutable MemTable，再从Immutable MemTable被持久化到外存，在外存中渐渐向L6层移动.LSM-Tree这样的数据流动方向能在新旧数据同时存在的情况下保证数据读取的正确性.但是，不同数据的访问频率是不同的，新加入的数据靠近内存，但不一定具有高访问频率.因此，我们在内存中提出一个新的存储结构，在外存中添加了一个新的策略.它们既能保证数据读取的正确性，又能够根据数据访问频率来自适应地调整数据的位置，使得高频数据尽可能长时间地驻留在内存中或尽可能地靠近内存.

2.2 内存结构

对内存部分来说，原来的结构中Immutable MemTable的数据在触发持久化操作之前仍可以被访问.当持久化后，对之前在Immutable MemTable中热数据的访问需要产生IO操作到外存进行读取.针对这种数据单向流动的特点，我们提出LRFO，即使用1个最近最少使用(LRU)队列和1个先进先出(FIFO)队列来替换原来的结构，以增加数据在内存中的驻留时间.LRFO占用的内存空间和原来的MemTable和Immutable MemTable占用的内存空间相同，其中LRU和FIFO分别占用的内存空间相同.

当有新数据插入到内存中时，LRFO首先将其插入到LRU队列的头部；当LRU队列的大小达到阈值时，LRFO从LRU队列的尾部淘汰数据.同时，LRFO将被淘汰的数据加入到FIFO队列的头部.当FIFO队列的大小达到阈值时，持久化操作被触发，此时的FIFO队列和Immutable MemTable一样被限制写操作.同时，LRFO创建1个新的FIFO队列用于接收LRU队列淘汰的数据.当查询数据时，LRFO依次在LRU队列、FIFO队列中查询.若在内存中查找到数据，LRFO返回结果，并将被查询的数据移动到LRU队列的头部.通过这样易实现的结构，LRFO算法有效地提高了热数据在内存中的驻留时间，减少了到外存查找的读延迟.特别地，LRU队列并不是固定的，它可以被其他的缓存替换算法所替代，如LRU2Q或LIRS[21]等.

Fig. 3 Example of read and write in memory

图3展示了LevelDB和LRFO在内存中的读写操作.图3(a)首先读取键c.不同于LevelDB，当读完键c后，LRFO将FIFO队列中键c移动到LRU队列的头部.同时，LRU队列尾部的键e被淘汰到FIFO队列中.图3(b)依次更新键b和键c.LRFO更新完后，依次将键b和键c挪到LRU队列头部，同时按照规则淘汰尾部键值对.在LevelDB中，因为旧的键b存储在Immutable MemTable中，所以新的键b被插入至MemTable.又因为MemTable的大小已经达到了阈值，所以LevelDB需要先将Immutable MemTable持久化到外存，同时，将当前的Mem-Table转换为Immutable MemTable，并创建1个新的MemTable接收新的键b.接着，键c直接被插入MemTable中.图3(c)依次读取键f和键d.对于LRFO，读取完成后，将它们依次移动到LRU队列的头部，并按规则淘汰尾部数据.LevelDB在Immutable MemTable中读取到键f，但键d已经随着之前的持久化操作进入到了外存，所以需要通过IO操作到外存中读取.

2.3 外存部分

通过观察外存中的存储机制，我们发现了导致LSM-Tree读效率下降的关键因素：LSM-Tree中的多级存储结构和压缩操作.LSM-Tree的多级存储结构决定了LSM-Tree的查找机制，而压缩操作逐渐将文件往低层移动，使得这些文件的读开销逐渐增加.针对这些机制，我们提出通过增加新的操作来改变数据的流向，使LSM-Tree中低层的部分文件能够向高层移动，以降低读开销.

在我们提出的策略中，有2个主要问题需要被解决：

1) 如何确定需要被上浮的文件?

2) 如何进行上浮操作?

(1)

在进行上浮操作之前，我们观察到LevelDB的存储结构中具有2个重要的性质：

1) SSTable中数据的新旧程度从L0层到L6层依次递减，L0层的数据最新，L6层中的数据最旧.

2) 除了L0层以外，其余各层中的SSTable之间不存在键值范围重叠.

这2个性质分别保证了数据读取的正确性和高效性.若要将上浮1个SSTable，这2个性质不能被破坏，否则将产生更大的开销甚至是错误读取.在上浮的过程中，上浮操作每次都将与目标SSTable存在键值范围重叠的SSTable均读出来，根据它们过滤掉自己所存储的旧数据.具体对于Li层的操作为：1)找出所有与目标SSTable存在键值范围重叠的该层的所有SSTable；2)使用类似多路合并的方法，去除目标SSTable中重复键的旧键值对；3)当去除完目标SSTable中所有旧键值后，继续往上一层进行重复操作，直至到目标层，则直接将目标SSTable以多路合并的方式插入目标层中.

图4展示了LevelDB和FloatKV在外存中的读取键值对的示例.图4(a)首先读取键e，FloatKV经过多级查找，最终在L6层中找到了对应的SSTable.FloatKV返回键e的结果，同时，更新键e所在SSTable的访问频率.然后，FloatKV判断该SSTable的访问频率是否满足上浮条件，若满足，则触发上浮操作.该SSTable开始上浮，分别与每层比较，删除其中的旧数据.例如，在L1层，键f已经存在，则该SSTable去除其中的键f.最后，该SSTable合并插入到L0层中.图4(b)读取键g，LevelDB依旧是经过多级查找，最终在L6层中找到了对应的SSTable.而FloatKV因为前一步将键e所在的SSTable上浮到了L0层，所以只需1次文件检查就找到键g.

Fig. 4 Example of read in external memory

2.4 开销分析

本节将分析本文提出的内存结构及上浮过程可能会产生的额外开销.对于内存结构LRFO，在LRU队列及FIFO队列中查找键值对的时间复杂度是O(n)，高于LevelDB中基于跳表实现的Mem-Table的时间复杂度O(logn).虽然我们可以通过增加额外的Hash表来降低LRFO的时间复杂度，达到O(1)的时间复杂度，但这会占用额外的内存空间，从而提高空间复杂度.同时，考虑到内存中的查找时间远远小于进行IO操作的时间以及在外存查找的时间，故FloatKV仅仅采用简单的LRFO结构.对于外部部分，额外开销主要来自于FloatKV提出的上浮操作.相比LevelDB，FloatKV每进行1次上浮操作，都需要消耗IO和计算资源.为了避免过多的IO操作引发写暂停问题，类比LevelDB，FloatKV也可以通过一定的策略来提高系统性能.具体的做法是当上浮操作被触发时，FloatKV创建1个后台进程单独进行上浮操作.这个后台进程不会立即修改当前的数据库，而是根据LevelDB中的Current文件，创建1个包含该上浮操作改变当前数据库所需要进行的所有操作的集合.当上浮操作完成后，这个集合再与当前的数据库进行合并，得到新的数据库.最后，Current文件中的内容将被更新，指向最新的数据库.这样的策略可以隐式地执行上浮操作，同时又不会破坏数据读取的正确性，尽可能小地减少了对数据库前端操作所产生的影响.

3 实验与结果

为了评估我们提出的FloatKV的性能，我们设计了一系列实验和6个评价指标(读写放大、操作总延迟、内存中读取键值的数量、压缩总数据量和查找1个键所需平均检查的文件次数、从内存向LSM-Tree刷入的数据量)来检验FloatKV.我们选择了当前主流的数据库LevelDB和显著提升LSM-Tree性能的Wisckey作为对照组.

3.1 实验配置及环境

我们采用阿里云的服务器进行本次的仿真实验，基本参数为1核、2 GB内存、64位的Ubuntu16.04.我们使用标准数据库性能测试工具YCSB[22]进行测试.YCSB可以用于评估新生代数据库及云数据服务的性能.数据的测试分为2个阶段：加载阶段和运行阶段.YCSB通过设置read，update，insert等参数来调节不同测试样例的读写比例，如表1所示，我们共设计了8个不同的测试样例.

在所有的测试样例中，键的大小均为16 B，值的大小均为1 KB.对于每个测试样例，我们均预先加载了100 000条键值对，随后进行1 000 000次操作，并记录1 000 000次操作后对应的实验结果.我们的实验模拟了单片Intel 3D NAND flash.该flash包含2 192个块，每个块包含1 024个页，每个块的大小是16 MB.该flash读取1个页、写入1个页和擦除1个块的时间分别是75μs，1,250μs和5 ms.分配给MemTable和Immutable MemTable或LRFO的内存大小模拟为8 MB.LevelDB的SSTable大小设置为2 MB.FloatKV和Wisckey均采用了键值分离，故它们的SSTable大小会远远小于LevelDB的SSTable大小，为了适应键值分离后的SSTable大小，我们减小了采用键值分离策略时对应算法的SSTable大小，默认设置为8 KB.

Table 1 Benchmarks

3.2 实验结果及分析

读写放大问题是我们首要关心的结果，它们反映了写入(读取)底层存储设备数据量与用户请求的数据量之比.图5展示了FloatKV，Wisckey，LevelDB在不同测试样中的读写放大.

Fig. 5 The read and write amplification of FloatKV, Wisckey, LevelDB

实验结果可以发现，FloatKV显著地减少了读放大，相比Wisckey和LevelDB分别平均减少了66.49%和90.36%的读放大.在写放大方面，FloatKV有所增加，平均是Wisckey的2.29倍，但平均仅是LevelDB的0.24倍.FloatKV通过调整文件的存储位置以减少了LSM-Tree检查文件读取的数据量，从而有效地降低了读放大.但因为上浮移动的原因，FloatKV将会触发更多的压缩操作，这些压缩操作所带来的额外写开销会增加FloatKV的写放大.

我们通过比较查找1个键平均所需检查的文件次数来反映FloatKV, Wisckey, LevelDB在查找1个键时所进行的试探次数.每次的试探需要读取文件的多个部分(过滤器部分、索引部分等)才能确定键是否存在或在文件中的位置，减少试探次数能够有效地提高读效率.

表2展示了3种算法查找1个键平均所需检查的文件次数.实验结果反映FloatKV极大地减少了查找1个键平均需要检查的文件次数，平均仅仅需要检查2.00次文件就可以查找到结果，而Wisckey和LevelDB分别需要平均检查4.75次和4.87次.测试样例G和H为写多读少的情况，FloatKV的上浮频率相对降低，所以对应的平均查找次数也与Wisckey和LevelDB相差不多.

Table 2 Average Time to Check Files When Looking up a Key

我们还比较了FloatKV, Wisckey, LevelDB在不同测试样例上的操作总延迟.操作总延迟反映了算法执行完所有操作的时间花费，包括读操作延迟和写操作延迟.图6展示了FloatKV, Wisckey, LevelDB在不同测试样例中的操作总延迟.

Fig. 6 Operation latency of FloatKV, Wisckey, LevelDB

实验结果表明，FloatKV有效地降低了操作总延迟，相比Wisckey和LevelDB平均降低了26.18%和66.34%的操作总延迟.FloatKV将高频访问的数据在向高层移动，使其更靠近内存，查询到真正数据时所需要花费的IO操作更少，从而使得操作总延迟更低.

表3展示了FloatKV，Wisckey，LevelDB在内存中读取键值对的个数.这个评价指标能够直接反映出查询数据时内存的命中率，在内存中读取键值对的个数越多，说明命中率越高.

Table 3 Number of Key-Value Pairs Read in Memory

实验结果表明，在读取操作个数相同的情况下，FloatKV能够有效地提高在内存中的命中次数，反映了热数据被尽可能久地留在内存中.Wisckey和LevelDB在内存中采用相同的结构，它们的实验结果是相同的.FloatKV相比它们平均增加了3.08倍的内存命中次数.FloatKV采用LRU+FIFO队列的形式，有效区分出冷热数据，提高数据在内存的驻留时间.

表4展示了FloatKV，Wisckey，LevelDB在运行阶段从内存向LSM-Tree刷入的数据量.这个指标能够有效地反映内存结构对LSM-Tree的压缩操作减少的效果.若内存结构的缓存能力高，则从内存向LSM-Tree刷入的数据量将会有所降低，从而减少LSM-Tree中的数据量，降低了压缩操作的触发次数及涉及的数据量.

Table 4 The Total Amount of Data Flushed from Memory into LSM-Tree

实验结果表明，FloatKV有效地降低了从内存向LSM-Tree刷入的数据量，相比Wisckey，平均减少了3.87%的数据量.FloatKV和Wisckey均采用了键值分离的策略，键值对中的值均以日志文件的形式存储，不参与LSM-Tree中的压缩操作，仅仅只有键被刷入LSM-Tree，所以刷入的数据量比LevelDB有极大地减少.

最后，我们比较了3种算法在压缩操作进行时涉及的总数据量.其中，FloatKV算法的实验结果包括了上浮操作进行时涉及的数据量.当压缩操作被触发时，大量的计算和IO资源将被用于合并、排序、持久化数据.表5展示了FloatKV，Wisckey，LevelDB在进行压缩操作时涉及的总数据量.若总数据量越大，则说明算法因压缩操作而产生的读写开销越大.实验结果显示，FloatKV相比LevelDB显著减少了压缩时涉及的总数据量，平均仅仅为LevelDB的0.15倍，但相比Wisckey却增加了3.16倍.主要原因是FloatKV添加的上浮操作会产生额外的IO操作，同时，在读比例大的情况下，频繁的上浮操作将多次触发向下的压缩操作.但对高频文件的上浮操作将有效地减少后续读这些文件产生的读开销，这些读优化足以抵消额外的压缩操作所带来的开销.

Table 5 The Total Amount of Data Involved with Compaction Operation

4 总 结

本文提出了一种基于访问频率分布的上浮式键值存储结构FloatKV，不仅在内存中提出了新的数据存储结构，在外存中也设计了一种基于访问频率分布的上浮式键值存储策略.实验结果表明FloatKV能够在不恶化写放大问题的情况下极大地减少读放大问题，同时有效地降低了操作总延迟.未来我们将针对LSM-Tree中的其他限制进行重新设计灵活可变的自适应存储结构和策略，并将我们的技术置于其他不同特性的应用之上.