论文地址  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存储方式。下图是三者的比较

• 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 的偏移指针。

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

• 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 编码。

存在的问题就是每次查找都要解压整个字典树，当字典树大了时候非常耗时，可以采用分块（bucket）的方法。文中举了一个例子，一个2¹⁶  大小的key-value 对，可以分为2¹⁰ 个块，每个块存储2⁶ 个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 次方大小顺序排列即可）