SILT: A Memory-Efficient, High-Performance Key-Value Store

论文地址  paper address (recommened by 煲仔)

This paper is from SOSP 2011, and introduces a Memory-Efficient, High-Performance key-value store system SILT (Small Index Large Table) . It requires only 0.7 bytes of DRAM per entry and retrieves key/value pairs using on average 1.01 flash reads each.

这篇文章来自于会议SOSP 2011,它介绍了一个节省内存且高性能的key-value 存储系统SILT。每个项平均在内存中只需要0.7 个bytes,检索每个key-value 对仅需要1.01 flash读放大。(这里的  读放大=应用程序所需数据/从磁盘或者SSD中读取的数据。文章假设以SSD 为存储介质,所以尽量减小读写放大。)

SILT is based on the three common key-value stores: LogStore, HashStore and SortedStore, while SILT combines their advantages and reduces the size of the keys as much as possible.

SILT 是基于三个普通的key-value 存储:LogStore,HashStore 和SortedStore,然而SILT 结合了他们的优点,并使得keys 大小被压缩到最小,在讲述SILT key-value操作过程同时,简述下这三个key-value存储方式。下图是三者的比较

threecompare

  • LogStore 是一个简单的将key-value 以日志方式按时间顺序保存,在查询时候按时间由新到旧的方式进行查询,直至查询到最新的key-value 进行返回,其他操作类似。

SILT 对所有的keys 进行cuckoo hash 处理(采用布谷鸟哈希是为了解决哈希冲突问题),对应的每个key 都有两个哈希函数,那么每个key 可以有两个候选的位置,如果两个位置都空的,那么任选一个位置保存,如果只有一个位置放在该位置,如果两个位置都是空的,则踢出去一个哈希值,让其去找这个被踢出key哈希的另一个哈希结果进行存放。如果没有空余的位置了,或者这个被踢出(置换)的过程反复次数过长,则认为这个Logstore 保存满了,则使用新的Logstore 进行保存。

为了节省内存,哈希表保存的不是整个key,而是key 的一部分—tag。当要进行查询的时候比对key 生成的tag 即可。而且tag 在LogStore 是唯一标识的。另外引用tag 带来的问题是当发生位置替换(被踢出)的时候,只有知道了整个key 才能得出对应的两个位置,这样被提出的tag 才能找到它的下家位置,文中是这样解释的:

To solve this costly displacement problem, our partial-key cuckoo hashing algorithm stores the index of the alternative bucket as the tag; in other words, partial-key cuckoo hashing uses the tag to reduce flash reads for non-existent key lookups as well as to indicate an alternative bucket index to perform cuckoo displacement without any flash reads.

为了解决位置置换耗费大的问题,部分键的cuckoo hashing 算法保存另一个哈希结果作为这个哈希位置的标签(tag);换句话说,部分键的cuckoo hashing 算法使用标签减少了对键不存在的flash 读以及位置置换时不再需要对其进行flash 读操作。

在SILT 中每个key 为 160 bits 的哈希值,使用其中15 bits 作为tag,所以哈希表的每条包括15 bits 的tag ,一个bit 的可用位,32 bits 的偏移指针。

logstore

  • HashStore 对flash 中保存的完整key 使用tag 顺序进行排序(K2,K4,K1,K3),这样key 原来是类似于LogStore 按时间的顺序排序的(K1, K2, K3, K4)。

hashstore

  • SortedStore 是一个静态(一旦产生就补修改)的key-value 存储,通过key 的顺序保存key-value 对,由一个称为Entropy-coded tire 作为索引,这个索引被尽可能的压缩,每个key 平均在索引中只占用0.4 bytes 。

这个Entropy 的索引是按照下图(Figure 5和6)顺序生成的:

  1. 通过每个key(文中用的是key,但我认为是tag,因为tag 已经就可以足够构造这个树了,key 又要在SSD 上读取)的最短不同前缀(shortest unique prefixes)构造了字典树
  2. 树的每个非叶子节点进行统计,格式为a/b ,a 为该节点左边叶子个数,b 为右边叶子个数,这里有两个规律,一个非叶子节点f 的 a/b 是其左边/右边所有非叶子节点a 与b 的总和(如果这个叶子f 有非叶子节点的话),另一个规律是所有最后一级的非叶子节点a/b形式都是1/1。这些规律为编码提供了方便
  3. 对树进行编码,(b)的编码规律为先根节点,再左右节点依次遍历,记录下所有节点的左节点数字得到(b)。
  4. (c)是通过(b)的Entropy coding 得到的,Entropy coding 是无损编码的总称,比如可以是Huffman 编码。

formtire

 

entropycoding

存在的问题就是每次查找都要解压整个字典树,当字典树大了时候非常耗时,可以采用分块(bucket)的方法。文中举了一个例子,一个216  大小的key-value 对,可以分为210 个块,每个块存储26 个key-value。这样解压的代价就小很多。

I think ‘batch’ and ‘compression’ are the main ideas of this paper.  

总结全文,我认为“批处理”和“压缩”是全文的主要思想,上面只是对key-value 在内存中的压缩进行了小结。所有key-value 操作被批量的进行hash、排序,批量的写入到flash。压缩是对key 排序结果的字典树进行最大限度的压缩。但是还是有两个问题:

Two Question:

1. If each item in the tire includes the offset of the key?字典树的每个叶子节点中包含了key-value 的指针吗?如果没有包含指针怎么读取?

2. How the items are partitioned into several buckets based on the first k bits  of their key to bound the lookup time?文中提到了最后树如果太大,查询时间会很长,使用key的前k 个bits 将字典树分成 2 的k 次方块,那么在查询的时候怎么能找到对应的是哪个树呢?(现在想想可以按这2的k 次方大小顺序排列即可)