文章主要是从数学模型作为切入点,对lsm-tree做了各种优化,那么这篇文章则重点选择了几篇关于内存的优化文章.我们都明白,如果能够尽可能多的把索引放在内存中,那么对于提升性能无疑是巨大的帮助,所以这块也是lsm-tree存储引擎的研究热点.
SlimDB:ASpaceEfficientKey-ValueStorageEngineForSemi-SortedData
这篇论文来自年的VLDB会议.我们知道,传统的LSM-tree存储引擎,存在写放大和空间放大问题,因此LSM-tree的研究往往在读放大,写放大和空间放大之间进行折中.这篇论文观察到有很多workload,他们的key存在所谓的semi-sorted特点,具体的来说就是很多key存在共同的前缀,比如推荐系统的特征存储,文件系统的元数据存储,图数据库存储等.针对semi-sorted特点,这篇论文提出了更优的索引和filter设计方法.核心是提出了两个新技术:three-levelblockindex和multi-levelcuckoofilter.在介绍他们之前,先科普下cuckoohash和cuckoofilter.
cuckoohash和cuckoofilter
bloomfilter相信大家都比较熟悉了,cuckoofilter的作用和bloomfilter类似,但是相比于bloomfilter可以提供更低的FalsePositiveRate.cuckoofilter的原理耗子哥写过一篇非常详细的中文材料,大家可以从coolshell上找到.我简单总结下核心思想.首先说说cuckoohash,cuckoohash采用两个hash表存储数据,设置两个hash函数,对于每个key,如果第一个hash表有空闲位置,就插入到第一个hash表,否则就插入到第二个hash表.如果第二个hash表也被占用了,那么需要把这个数据踢走,反复上述过程,直到踢的次数达到一个上限,就认为hash表已经满了,需要rehash了.cuckoo的名字也是由此而来,因为cuckoo(布谷鸟)有一个恶习,就是他自己不筑巢,把蛋生在其他鸟类的鸟巢里,但是他的蛋会先孵化出来,从而挤占掉其他鸟.虽然看上去cuckoohash需要很多次数据踢出,但是平均的插入开销却是O(1)的,并且cuckoohash的满载率可以达到80%以上,所以是一个性价比很高的hash算法.用cuckoohash就可以直接起到filter的作用,但是如果因为会涉及key的替换,所以必须存储完整的key来计算hash值,但是存储全部的key还是比较占用内存空间的.在论文CuckooFilter:PracticallyBetterThanBloom中,给出了partial-keycuckoohashing算法,为了节省存储空间,只存储key的fingerprint值,不存储原始的key来节省存储空间.但是因为不存储完整的key,那么就必须找到一种方法二次计算hash值.为此partial-keycuckoohash算法设计了一个很巧妙的hash函数,下图是插入算法,查找和删除算法参见论文.论文中对cuckoofilter的存储空间和FRP之间的关系进行了数学建模,每个bucket的slot数量越多,hashtable的负载越高,fingerprint的bit越多,FPR越小.当bucketsize=4的时候,装载率可以到95%,在相同FPR条件下,bloomfilter的存储空间是cuckoofilter的1.44倍.
Entropy-EncodedTriedatastructure
针对已经排序好的数据,通常的做法是使用二分查找来查询具体的key.进一步来说,因为key有序,所以可以用更高效的编码方式对key进行编码来构建一个索引,加速查找.trie树,也叫做前缀树,可以作为这样的数据结构来使用,如果key-value都是固定长度的,那么可以针对key的最短unique前缀来构建索引,而无须完整的key.下图上半部分就是一个trie树的例子.然而使用树形结构在持久化是非常消耗存储空间的,因为有大量的指针,所以需要对树形结构进行相应的编码.编码的基本思路是递归:Repr(T)=
L
Repr(L)Repr(R),其中
L
代表左子树叶子节点的个数详细方法参加论文:SILT:AMemory-Efficient,High-PerformanceKey-ValueStore.基本上编码完之后的效果就是下图下半部分所示.论文中还给出了进一步的优化方法.
但是ECT仅仅对固定长度的key和value有效,如果key和value长度不固定,那么需要进行一定的变种,一种方法是存储把(key,value)替换成(offset,paitialofkeyvalue),然后其余的部分,存储在单独的地方,但是这种方法需要多引入一次IO操作.如果value足够小,那么可以和key存储到一起,减少二次IO的开销.使用ECT编码,论文中给出平均每个entry占用0.4bytes,但是没有找到证明过程.
three-levelblockindex
利用three-levelblockindex技术,替换掉rocksdb原生的blockindex之后,可以优化index的存储空间到平均每个key0.7bits.下面来看看three-levelblockindex的核心设计.在leveldb里,每个SSTable的最后都有一个indexblock,存储每个datablock的lastkey,这样每次查找都需要基于indexblock做一次二分查找来定位到具体的数据.在作者观测到的典型的workload中,每个entry的大小不超过bytes,如果blocksize是4KB的话,每个block最多16个entry(4KB/=16),indexblock里存储的是fullkey,平均大小为16bytes,所以平均每个entry的index需要16B/16=8bits.和leveldb不同,leveldb存储的key是全部有序的,但是semi-sorteddata只要求key的前缀有序,所以这就让我们可以使用ECT编码来更高效的进行index的压缩,ECT平均每个entry使用0.4bytes.在semi-sorteddata环境下,ECT可以达到平均每个key只存储2.5bits的效果,论文中进一步优化到了1.9bits.
但是ECT是为了indexhashtable设计的,对于semi-sortedkey来说,单纯使用ECT不够高效,所以这里设计了Three-levelindex.Three-levelindex的原理如下图所示:
将每个block的firstkey和lastkey组成一个数组,这个数组的前缀进行ECT编码,重复的前缀会删除,这就是第一个level第二个level存储第一个数组中的下标,这样当给定一个key查询时,就能筛选出一组可能存在这个key得SSTable为了进一步缩小查找范围,每个blocklastkey的后缀组成一个数组,共享公共前缀的suffix仍然采用ECT编码,这样就可以采用二分查找的方式定位具体的block了.当然如果为了加速查找,不使用ECT编码也可以.因为ECT必须针对key-value定长的情况,所以这里使用所有key的最长公共前缀进行ECT编码的,但是不知道对于所有的key的后缀是否需要补齐长度,论文里没有写,我估计是需要的.
简单分析下three-levelblockindex的开销,对于第一层,每个block使用first和last两个key,使用ECT之后,平均每个key2.5bit,所以每个block需要5bit.第二层存储的是个数,可以使用差分编码,平均每个block也是2.5bit.第三层仍然是ECT编码,每个block一个key,那么平均每个block占用2.5bit.所以平均每个block需要占用10bit(5+2.5+2.5).如果每个block平均存储16个entry,那么每个entry相当于10/16=0.7bit,远远小于leveldb的8bit.
multi-levelcuckoofilter
因为cuckoofilter中存储的是key的fingerprint,所以存在一定冲突的可能,而冲突就会产生FalsePositive的读请求.为了降低在冲突情况下的读延迟,引入了maintable和secondarytable.maintable存储fingerprint和level,这样可以快速定位key所属于的level.secondarytable中存储了maintable中冲突的entry的fullkey和对应的level,基本逻辑如下图所示.
下面这幅图显示了SlimDB和原生levelDB的性能对比,可以看出来SlimDB的内存节省还是挺明显的,详细的测试数据大家看论文吧.
LSM-trie:AnLSM-tree-basedUltra-LargeKey-ValueStoreforSmallData
既然提到了trie树,就一起来看看这篇论文吧.这篇论文发表自年的ATC(USENIXAnnualTechnicalConferene),核心出发点就是希望用trie树结构来精简索引的大小,来降低大量小key-value数据而造成的内存膨胀问题.但是为了使用trie树,就必须采用类似sha-1的hash算法,将原始的key计算出来的hash值来替换掉原始的key,因为sha-1hash之后,key是定长的而且公共前缀更多了,trie树的优势才能充分发挥出来.下图所示的结构就是一种所谓SSTable-trie的结构,和SSTable相比就是把hashkey存在levelDB里了.但是这还不够高效,毕竟还是存在索引的,将原始key转换成hashkey之后,就无法保证key有序的特性了,所以论文干脆引入了HTable的思路,这就是LSM-trie.简单点说,就是在给item分配block的时候,使用hash而不是基于hashkey排序了,不过使用hash就容易导致不同的block之间数据不均衡,所以还需要对特别不均衡的block进行一定程度的修正,这里面细节比较多.同时还需要引入一种新的bloomfilter算法,这块大家感兴趣就去看论文吧.
OptimizingSpaceAmplificationinRocksDB
这篇论文比较简单,论文的核心内容是基于rocksdb研发了MySQL的存储引擎,在facebook的workload下,替换InnoDB之后大约降低了50%的存储空间.论文中介绍了RocksDB使用的一些空间压缩技术,主要包括:
为不同的层设置不同的压缩算法.比如最后一层包含90%的数据,但是被读取的概率相比其他层要小一些,所以最后一层设置更高压缩率的算法,相对来说性价比更高,而低层因为数据量少,访问频率可能更高,可以采用相对低压缩率的算法,节省压缩和解压缩的CPU开销,提高访问性能.动态条件每个level的size.我们知道传统的leveldb实现中,每个level的size是固定配置的,但是在最坏情况下,最后一层可能不是上一层的10倍,因为最后一层可能数据不满,这时候空间放大就不是1.1倍了.RocksDB引入了动态调整每个levelsize的技术,仍然保证上下两层的size在固定的倍数,比如10,这样可以保证空间用于是1.1倍.Key的前缀压缩,sequenceID的垃圾回收,基于词典的压缩算法等.前缀bloomfilter.对于scan来说,传统的bloomfilter就起不到作用了,然而很多scan请求都是基于共同前缀的,比如如果key是(userid,timestamp),那么userid很可能会成为前缀.rocksdb开发了prefixbloomfilter,由用户传入一个prefixextractor,来实现prefixbloomfilter,在facebook的workload上可以降低64%的读放大.论文的实验环节介绍了很多在facebookworkload下的实验数据和参数,来证明使用RocksDB替换innodb之后的效果,详细数据可以参考论文原文.
Accordion:BetterMemoryOrganizationforLSMKey-ValueStores
这篇论文发表于年的VLDB,论文提出了优化内存分配和使用的方法.这篇论文主要针对HBase做了内存方面的优化,核心思路是一方面在memtable中提前做