Abstract

• SILT (Small Index Large Table) 是一种基于闪存的高效内存、高性能键值存储系统，可扩展到在单个节点上服务数十亿个键值项。它每个条目只需要 0.7 字节的 DRAM，并且每次平均使用 1.01 次闪存读取来检索键/值对。SILT 结合了新的算法和系统技术来平衡内存、存储和计算的使用。我们的贡献包括: (1) 设计了三个基本的键值存储，每个存储对内存效率和写友好性的重点不同; (2) 这些基本的键值存储组合在一起构成了 SILT；(3) 为满足不同工作负载的需要而精心调整系统参数的分析模型。SILT 需要少一到两个数量级的内存，以提供与当前具有闪存的商用桌面系统上的高性能键值系统相当的吞吐量

Introduction

• 内存昂贵，内存效率成为数据规模越来越大后面临的严峻问题，有一些工作来减小索引开销到每个 KV 对几个 Byte，或者保存部分索引到盘上来拖鞋性能，但也就需要更多的读取，造成读放大。

• 本文提出的 SILT 显著见笑了每个键的内存开销到 0.7B，而且只用平均 1.01 次读盘就能处理查询。也提供了一些权衡。

• 贡献：
• 三种基本存储的实现，LogStore, HashStore 和 SortedStore。使用新的快速压缩索引数据结构（部分 key 布谷鸟哈希和基于熵编码的 trie 树），每个基本存储在内存和写友好方面的侧重不同。
• 三种存储组合起来构成了 SILT
• 建立一个分析模型来实现内存、存储、计算的权衡，提供系统性能、盘寿命以及内存效率的精准预测。

SILT

• 一些前期为了简化的假设，键 160bit 的哈希值，值定长。

• 五个目标：
• 低读放大；1+ε，其中 ε 可以通过参数调整配置，比如 0.01
• 可控写放大且支持顺序写；一个键值对在盘上的写次数对应了写放大，影响 SSD 寿命。同时对于 SSD 的小于 4K 的写入可能造成额外的写流量。
• 内存高效的索引：尽可能使用少量内存
• 计算高效的索引：需要足够快能够充分利用盘 I/O
• 闪存空间高效利用：一些数据布局选项更稀疏地使用闪存空间以提高查找或插入速度，但任何此类选择的总空间开销都应该保持在 20% 以下

• 传统的单个存储的方式，采用内存 filter、index 和盘上布局，无法同时实现上述目标。
• 要么内存索引设计的好，读好，但是引入了随机写。
• 要么利用顺序写的优势但是需要内存哈希索引来加速，内存开销大。维护部分索引就读开销大

• 多个存储的方式 BigTable, Anvil 和 BufferHash 把多个存储链接起来，每个使用不同的属性。但是引入了两个挑战：
• 每个独立的存储需要高效设计和实现，需要能很好地组合在一起，从一种数据转换成另一种也需要很高效。
• 查询多个存储的时候需要足够高效，保证读放大尽可能低而不会每个存储发起 i/O。
• 使用 compact in-memory filter 来检查是否存在，但是内存开销可能很大

• SILT 多存储设计：
• 键值对插入到一个写优化的存储，随着时间流逝录像了内存高效的存储；
• 大部分数据都存储在内存高效的存储，尽管该存储外的数据还是会用少量内存，但是足够小
• SILT 可以针对不同场景调优，比如对于最近的和最大的存储的查询。所以也用了个内存 filter 在最近的存储中过滤

• 具体存储
• LogStore 顺序追加写入，使用内存哈希表映射键和日志偏移，同时该哈希表作为了 filter。
• SILT 用了一个基于布谷鸟哈希的哈希表，部分键布谷鸟哈希实现了 93% 的占有率，且计算开销和内存开销很低。远好于其他的 50% 的占有率。
• LogStore 在后台被转换成 HashStore，HashStore 不需要内存索引，只用一个高效的内存 Filter。然后可能同时存在多个 HashStore。
• SortedStore 维护了有序的键值对数据，所以可以用紧凑的索引表示，基于熵编码前缀树实现。因为差人单个数据到有序数据中开销太大，所以周期性批量合并多个 HashStore 的数据到 SortedStore 中，形成一个新的 Sortedstore。

• 分区：每个物理节点运行了多个 SILT 实例，负责不同的范围，每个都有自己的三种存储。分区可以通过虚拟节点来提升负载均衡，减小 flash 的开销，促进调优。

基本存储设计

LogStore

• 使用布谷鸟哈希，两个哈希算法选 slot。如果找不到候选的或者取代次数超过了阈值 128 次就认为哈希表满了，所以此时冻结 LogStore 并初始化一个新的，而不需要重哈希。

• 哈希表不存储整个 key 20B，只用一个 tag，所以实际读的时候还需要检查一下 key。虽然节省了内存也引入了别的问题，要想知道这个 key 的另一个可选 slot 就需要完整 key，但是再去读开销太大了，而且可能驱逐另一个 key，每次驱逐都需要一次读。

• 所以选择把 bucket 索引记下来作为 tag。所以在哈希函数 1 计算得到的 slot 位置存储的是哈希函数 2 计算的 slot index，反之亦然，如下图所示。所以驱逐的时候直接根据 tag 就知道在哪。

• 查询操作的话，检查哈希函数 1 对应的值是否匹配存储在 h2 对应的 bucket 的 tag，或者检查 h2 de 值是否匹配哈希函数 1 对应的 tag。如果 tag 匹配，就从相应的 offset 中去取键值对。

• SILT 让每个 Bucket 允许存储四个键值对，还是控制一个 bucket 的大小在一个 cacheline 里。

• 哈希函数：默认情况下，SILT 使用 15 位的键片段作为标签。每个哈希表条目为 6 字节，由一个 15 位的标签、一个单独的有效位和一个 4 字节的偏移指针组成。误检（false positive retrieval）的概率为 0.024%（推导过程见第5节），也就是说，平均每 4096 次闪存检索中就有 1 次是不必要的。哈希桶（而非条目）的最大数量受键片段长度的限制。给定 15 位的键片段，哈希表最多有 2^15 个桶，或 4×2^15 = 128 Ki 个条目。为了在 LogStore 中存储更多的键，可以增加键片段的大小以拥有更多的桶，增加关联性以将更多的条目打包到一个桶中，和/或将键空间划分为更小的区域，并将每个区域分配给一个带有 LogStore 的 SILT 实例。与这些决策相关的权衡在第5节中介绍。

HashStore

• 直接对相对较小的 LogStore 进行排序并将其合并到更大的 SortedStore 中需要重写大量数据，导致高写放大。另一方面，在合并之前保留大量的 LogStore 可以分摊重写的成本，但会不必要地因 LogStore 的索引而导致高内存开销。为了弥补这一差距，SILT 首先将 LogStore 转换为具有更高内存效率的不可变 HashStore。

• HashStore 通过消除索引并将 on-flash (键、值)对从插入顺序重新排序到哈希顺序(见图4)，从而节省了比 LogStore 更多的内存。因此，HashStore 是一个 on-flash cuckoo 哈希表，并且与 LogStore 中的内存版本具有相同的占用率 (93%)。HashStores 也有一个内存组件，一个用于概率测试键是否存在于存储中而不执行 flash 查找的过滤器

• 内存高效的哈希 filter
• 尽管先前的方法[1]使用布隆过滤器[12]进行概率成员测试，但SILT使用基于部分键布谷鸟哈希的哈希过滤器。在低误报率的情况下，哈希过滤器比布隆过滤器更具内存效率。在一个4路集合关联布谷鸟哈希表中，给定一个15位的标签，如第3.1节所计算的，误报率为f = 2^(-12) = 0.024%。在表占用率为93%的情况下，使用哈希过滤器时每个键的有效位数为15 / 0.93 = 16.12。相比之下，为优化空间消耗而设置哈希函数数量的标准布隆过滤器，至少需要1.44log2(1 / f) = 17.28位的内存来达到相同的误报率。
• HashStore的哈希过滤器创建起来也很高效：SILT只需按顺序从LogStore的哈希表中复制标签，丢弃偏移指针；相反，布隆过滤器则需要从头开始构建，再次对 LogStore 中的每个项目进行哈希计算。

SortedStore

• SortedStore 是一个静态键值存储，内存占用非常低。它在闪存上按键排序存储（键，值）条目，并由一个新的熵编码特里数据结构进行索引，该结构构建速度快，平均每个键使用 0.4 字节的索引内存，并通过直接指向闪存上的正确位置来保持低读放大（确切为 1）。

• 在闪存上使用排序数据：由于这些理想的特性，SILT 将大部分键值条目保存在一个 SortedStore 中。然而，熵编码 trie 不允许插入或删除；因此，为了将 HashStore 条目合并到 SortedStore 中，SILT 必须生成一个新的 SortedStore。因此，SortedStore 的构建速度是 SILT 整体性能的一个重要因素。排序提供了一种实现快速构建的自然方式：
• 排序允许高效地批量插入新数据。新数据可以进行排序，并顺序地合并到现有的已排序数据中。
• 排序是一个被充分研究的领域。SILT可以使用高度优化和经过测试的排序系统，比如 Nsort

使用 Trie 索引

• 用前缀树对排序数据进行索引：Trie，或称前缀树，是一种树形数据结构，它存储一个键的数组，其中每个叶节点代表数组中的一个键，每个内部节点代表其子孙节点所表示的键的最长公共前缀。

• 当固定长度的键值条目在闪存上按键进行排序时，对于键的最短唯一前缀的特里树可作为这些排序数据的索引。键的最短唯一前缀是指能够将该键与其他键区分开来的最短前缀。在这样的特里树中，查找键的某些前缀会将我们引导至一个叶节点，该叶节点具有闪存上排序数据中被查找键的直接索引。

• 下图展示的例子，没有阴影部分对应的就是数据的索引，没有阴影的键前缀是用于索引的最短唯一前缀。阴影部分在索引时被忽略。因为后缀部分的任何值都不会改变键的位置。例如，查找一个键，比如 10010，会向下追踪到代表 100 的叶节点。由于前面有 3 个叶节点，该键的索引为 3。对于闪存上固定长度的键值对，数据的确切偏移量是所获得的索引乘以键值对的大小（有关可变长度键值对的扩展，请参阅第 4 节）。请注意，查找具有相同前缀 100 的类似键（例如 10000、10011），即使它们不在数组中，也会返回相同的索引；trie 树保证对存储的键进行正确的索引查找，但对于查找键是否存在未作说明。

表示一个 Trie 树

• 典型的树数据结构不适用于 SILT，因为每个节点都需要昂贵的内存指针，每个指针长度为 2 到 8 个字节。如果使用指针，常见的 Trie 树表示形式，如 level-compressed tries，也是不够的。

• SortedStore 使用紧凑的递归表示来消除指针。具有左子树 L 和右子树 R 的特里树 T 的表示定义如下：
• Repr(T ) := |L| Repr(L) Repr(R)
• 其中 |L| 是左子树中的叶节点数量。当 T 为空或为叶节点时，T 的表示为一个空字符串。（在简化的算法描述中，为简洁起见，我们使用特殊标记 (-1) 代替空字符串，但完整算法不需要使用此特殊标记。）

• 图 6（a，b）展示了图 5 中特里树的未压缩递归表示。由于有 3 个以 0 开头的键，所以 |L| = 3 。在其左子树中，|L| = 2 ，因为有 2 个键在第二位是 0 ，所以表示中的下一个数字是 2 。它再次递归到其左子树，得到 1 。这里不再有非叶节点，所以它返回根节点，然后生成根节点右子树的表示，即 3 1 1 1 。

• 算法 1 展示了一个从已排序的键构建（非熵编码的）特里树表示的简化算法。它类似于快速排序，因为它找到键的分区，并对两个子集进行递归。索引生成速度很快（在现代英特尔台式机 CPU 上≥ 700 万个键/秒，第 6 节）。

查询键

• 键查找通过逐步读取前缀树表示（算法 2）来实现。该函数接收查找键和前缀树表示字符串。通过解码编码的下一个数字，SortedStore 知道当前节点是否为内部节点，从而可以递归进入其子树。如果查找键进入左子树，SortedStore 递归进入左子树，其表示紧跟在给定的前缀树表示中；否则，SortedStore 递归解码并丢弃整个左子树，然后递归进入右子树。SortedStore 在每次递归进入右子树的节点处累加偏移量；如果查找键存在，偏移量的总和就是存储查找键的偏移位置。

• 例如，要查找 10010，SortedStore 首先从表示中获取 3。然后，由于该键的第一位是 1，它跳过接下来的数字（2 1），这些是左子树的表示，并继续处理右子树。在右子树中，SortedStore 读取下一个数字（3；不是叶节点），检查键的第二位，并继续递归进入其左子树。在读取当前子树的下一个数字（1）后，SortedStore 通过选择左子树到达叶节点。直到到达叶节点，它仅在根节点处选择右子树；从根节点的 n = 3 ，SortedStore 知道 10010 的数据在闪存上的偏移量是（3×键值大小）。

压缩表示

• 尽管上述未压缩的表示平均每个键最多使用 3 个整数 Repr(T ) := |L| Repr(L) Repr(R)，但对于哈希键，SortedStore 可以通过使用熵编码压缩每个 |L| 值（图 6（c）），轻松将平均表示大小减少到 0.4 字节/键。
• 由于固定长度的哈希键在键空间上均匀分布，所以 |L| 的值往往接近 |T|（T 中的叶节点数量）的一半，因此两个子树存储键的概率相同。更正式地说，|L| ∼ 二项分布(|T|, 1/2) 。当 |L| 足够小（例如，≤ 16）时，SortedStore 使用静态的、全局的基于二项分布使用全局共享的哈夫曼表。如果 |L| 较大，SortedStore 使用 Elias gamma 编码[23]对 |L| 与其期望值（即 |T|/2）之间的差值进行编码，以避免用大型哈夫曼表填满 CPU 缓存。通过针对哈希键优化的这种熵编码，我们的熵编码特里树表示比之前最好的递归树编码[16]紧凑约两倍。

• 在处理压缩特里树时，算法 1 和算法 2 进行了扩展，以在每个递归步骤跟踪叶节点的数量。这在表示中不需要任何额外的信息，因为叶节点的数量可以使用 |T| = |L| + |R| 递归计算。基于 |T|，这些算法选择一个熵编码器来对 len(L) 进行编码和解码偏移量。值得注意的是，特殊标记（-1）在熵编码中不占用空间，因为其熵为零。

确保恒定时间的索引查找

• 如前所述，一次查找可能必须解压整个字典树，因此随着键值存储中条目的数量增加，查找的成本会大幅增加。

• 为了限制查找时间，根据项的键的前 k 位将其划分为 2^k 个桶。每个桶都有自己的字典树索引。例如，对于一个包含 2^16 个项的键值存储，使用 k = 10，每个桶平均将包含 2^(16 - 10) = 2^6 个项。很有可能，没有桶包含超过 2^8 个项，因此解压桶的字典树的时间既受一个常数值限制，又很小。

• 这种分桶方式需要在内存中存储额外的信息：（1）指向每个桶的字典树表示的指针，以及（2）每个桶中的条目数量。SILT 通过使用更简单版本的紧凑选择数据结构（半直接-16），将这种分桶信息的量保持在较小水平（每个键少于 1 位），通过分桶，我们基于字典树的索引属于被称为单调最小完美哈希[10, 13]的数据结构类别（第 7 节）。

对于小键值大小的进一步空间优化

• 对于小的键值条目，SortedStore 可以通过应用稀疏索引[22]来减小字典树的大小。稀疏索引定位包含条目的块，而不是条目的精确偏移量。此技术需要在块内进行扫描或二分查找，但它减少了索引信息的数量。当存储介质具有要读取的最小有用块大小时，它特别有用；例如，许多闪存设备随着块大小的减小每秒提供的 I/O 次数增加，但不会超过某个限制（例如 512 或 4096 字节）[31, 35]。当配置为 64 字节或更小的键值大小时，SILT 使用稀疏索引。

• SortedStore 通过修剪其中的一些子字典树来获得字典树的稀疏索引版本。当一个字典树的子字典树中的条目都在同一个块中时，该字典树可以省略这些子字典树的表示，因为省略的数据仅提供条目之间的块内偏移信息。如果每个块包含 16 个或更多的键值条目，修剪可以将字典树的大小减少到每个键 1 位或更少。

HashStore 合并到 SortedStore

• SortedStore 是一个不可变的存储，不能被更改。因此，合并过程会根据给定的 HashStore 和现有的 SortedStore 生成一个新的 SortedStore。与从 LogStore 转换到 HashStore 类似，在合并期间，HashStore 和旧的 SortedStore 可以用于查找。

• 合并过程包括两个步骤：（1）对 HashStore 进行排序，（2）顺序合并已排序的 HashStore 数据和 SortedStore。首先，SILT 对要合并的 HashStore 中的所有数据进行排序。此任务通过枚举 HashStore 中的每个条目并对这些条目进行排序来完成。然后，来自 HashStore 的已排序数据与 SortedStore 中已排序的数据顺序合并。顺序合并选择最新的有效条目，如表 3 所总结；对一个键的复制或删除操作会消耗该键（即，通过在相应的存储中推进“合并指针”），而如果未对当前键应用任何操作，则该键仍可用于下一次比较。在两个步骤都完成后，旧的 SortedStore 会被新的 SortedStore 原子性地替换。在合并过程中，旧的 SortedStore 和新的 SortedStore 都存在于闪存中；然而，通过在同一时间对单个 SILT 实例执行合并过程，暂时拥有两个 SortedStore 所产生的闪存空间开销被保持在较小水平。

• 使用误报过滤器来减少不必要的 I/O。然而，SILT 架构的扩展可能有多个 SortedStore。在这种情况下，字典树索引可以轻松容纳误报过滤器；该过滤器是通过从已排序的键中提取键片段生成的。键片段可以存储在内存数组中，以便它们与闪存上的已排序数据具有相同的顺序。扩展的 SortedStore 可以在从闪存读取数据之前参考键片段。

EXTENDING SILT FUNCTIONALITY

变长

• 为简单起见，到目前为止我们介绍的设计重点是固定长度的键值数据。实际上，SILT 可以通过使用内联间接轻松支持变长键值数据。此方案遵循现有的具有固定大小槽位的 SILT 设计，但在 HashStore 和 SortedStore 中存储（偏移量，（键，值）的第一部分）对，而不是实际的（键，值）（LogStore 本身可以处理变长数据）。这些偏移量指向存储在其他位置（例如，第二个闪存设备）的键值数据的其余部分。如果整个项足够小以适合固定长度的槽位，则可以避免间接；因此，大数据需要额外的闪存读取或写入。但是小数据不会产生额外的 I/O 成本。图 7 绘制了该方案与不同槽位大小的权衡分析结果。它使用大小在 4B 到 1MiB 之间且遵循 Zipf 分布的键值对，假设一个 4 字节的头（用于键值长度），一个 4 字节的偏移指针，以及一个统一的访问模式。

• 对于特定的应用程序，SILT 可以选择使用隔离存储以进一步提高效率。类似于简单隔离存储的理念[39]，系统可以为不同的固定键值大小组合实例化多个 SILT 实例。应用程序可以像在 Dynamo [21] 中那样选择具有最合适键值大小的实例，或者 SILT 可以为新键选择最佳实例，并向应用程序返回包含实例 ID 的不透明键。由于每个实例都可以针对其自身的数据集优化闪存空间开销和额外的闪存读取，使用隔离存储可以将支持变长键值的成本降低到接近固定长度键值的水平。

Fail-Graceful Indexing

• 在内存压力较大的情况下，SILT 可能会暂时以降级的索引模式运行，允许更高的读取放大（例如，每次查找超过 2 次闪存读取），以避免因内存不足而停止或崩溃。
• （1）丢弃内存中的索引和过滤器。HashStore 的过滤器和 SortedStore 的索引存储在闪存中以实现容错，这使得 SILT 可以将它们从内存中丢弃。此选项节省了内存，但 SortedStore 需要额外进行一次闪存读取，HashStore 则需要额外进行两次闪存读取。

• 这些技术还有助于加快 SILT 的启动速度。通过对闪存上的索引文件进行内存映射或执行二分查找，SILT 可以在后台将索引加载到内存之前就开始处理请求。

分析

• 权衡 改进写放大、读放大或内存放大中的任何一项，都要以另外两项指标中的一项为代价。例如，使用更大的标签 tag（即增加 k）可通过降低每个存储的误报率 f 和 HashStore 的数量 H 来减少读放大。然而，由于标签变大，HashStore 随后会消耗更多的 DRAM，从而增加了内存开销。同样，通过增加 d (maximum number of entries to merge)，SILT 可以减少将 HashStore 合并到 SortedStore 的频率以降低写放大，但这样做会增加 HashStore 过滤器消耗的 DRAM 量。图 8 说明了当 HashStore 条目的最大数量 d 变化时，写放大和读放大如何随内存开销而变化。

• 更新速率与闪存寿命 每秒处理 U 次更新的 SILT 实例的设计者希望确保闪存至少持续 T 秒。假设闪存设备在接收一系列大型顺序写入时具有完美的磨损均衡[15]，写入的总数乘以写放大 WA ，必须不超过闪存设备的大小乘以其擦除周期预算。这就在寿命、设备大小、更新速率和内存开销之间建立了一种关系：.