基于存储系统SILT基本结构的详细解析

SILT存储系统通过使用多个基本的键值存储结构，每个针对不同的操作进行相应的优化：(1)键值的更新操作通过写优化的存储结构上进行。(2)大多数键值对存储在存储高效的结构中。虽然在存储结构之外的数据很少使用高效的存储索引，但是每个键的平均索引的代价是很低的。(3)SILT可以调整以应对极端情况，即查询在最后、最近的存储结构中。SILT通过使用内存的过滤器，允许所有的查询在1+（nbcl）flash读取时间内完成。

SILT的结构和基本存储结构(LogStore, HashStore, SortedStore)如图 1所示。

图1 SILT存储结构

LogStore对于写操作有很高的效率，其主要用来进行PUT和DELETE操作。为了达到很高的系统性能，写数据的结果直接添加到flash上log文件的末尾。因为这些记录是按照相应的时间进行排序的，LogStore通过内存中的hash表以键和相应在log文件中的偏移对其进行映射。SILT使用cuckoo hash从而在最小内存消耗的情况下，达到很高的性能。本文中提出的部分键的cuckoo hash在较低的计算代价和内存消耗的情况下，占用93%的空间。相比其他两个只读的存储结构，其数据存储紧凑，LogStore必须要存储4字节的指针。SILT因此只使用一个LogStore。

当LogStore中存储饱和之后，LogStore将转换成固定不变的HashStore。HashStore数据以hash表的形式存储在flash上，其不需要内存的索引对记录或数据进行检索。SILT在将其合并到SortedStore之前可以使用多个HashStore。每个HashStore使用一个高效的内存过滤器过滤掉不存在的键。

SortedStore在flash上按一个指定的顺序维护键值对数据，其使用一个非常简洁的形式对索引进行变化。因为对于排序的数据进行单个更新时，其代价是非常高的，因此SILT周期性的将HashStore表的内容合并的到SortedStore中。

LogStore顺序讲PUT和DELETE操作写入flash中，从而达到高的写吞吐量。其内存的部分键cuckoo hash索引可以高效的实现键到相应log文件中位置的映射（如图 2所示）。

LogStore使用一个基于cuckoo hash的hash表。其使用两个函数和实现键值到相应的位置的映射。在新的键加入hash表中是，如果两个位置中有一个是空的，则将其加入这个空的位置；否则新的键替换两个位置的一个，被替换的键按上述过程进行迭代，直到找到其可选的位置中。

图2 LogStore设计方案

为了使其尽可能的简洁，hash表并不存储整个键，而只是存储键的一个tag。只有当查询于相应的tag符合才继续进行后续操作，这样可以实现对不存在的键进行过滤。

虽然存储tag可以在一定程度上节约内存的空间，但是同样出现问题：将键移动到其可选的另一个位置需要事先知道其另一个hash值。但是，相应的键值存储在flash中，因此在这种情况下需要进行flash读取操作。为了解决这个问题，在相应的hash表中将其可选位置的索引作为tag。例如，如果键被放在位置，其另一个hash值将作为其tag存储在位置中，反之亦然。

当LogStore中内容达到饱和时，SILT将其转化成对于内存利用率更高的数据结构。直接对LogStore进行排序，并将其合并到SortedStore需要重写大量的数据。另外，保留大量的LogStore会造成很高的内存消耗。因此，为了解决这个问题，SILT首先将LogStore转化为一个不可变的HashStore。当HashStore的数量达到指定数值时，其被合并到SortedStore中(如图 3所示)。

HashStore通过修改索引的结构，对于flash上的(key, value)进行按hash顺序进行排序，可以节省大量的内存。

HashStore的过滤器非常简单，只是将LogStore中hash表中的tag复制，并去掉相应的指针。

图3 LogStore转换为HashStore

SortedStore是一个静态的键值存储结构。其存储按照flash上key的顺序进行排序的键值(key, value)，使用基于熵编码的trie树进行索引，平均每个键消耗0.4字节进行存储。

此外，SILT使用Flash上的排序数据(Using Sorted Data on Flash)，将大多数的键值保存在单个的SortedStore，但是其基于熵编码的trie树不允许进行插入和删除。因此，为了将HashStore合并到SortedStore中，SILT必须重新生成SortedStore。因此，SortedStore的构建速度成为SILT整体性能的一个重要的因素。

通过排序可以很快完成的构建工作：(1)排序允许新数据的加入：新的数据通过排序，按顺序合并到已排序的数据中。(2)排序的相关技术非常成熟：SILT可以使用高度优化的排序系统，如Nsort等。