原文

如果 Protocol Buffers 是 Google 个人数据记录的通用语言，那么排序字符串表 (SSTable) 是用于存储、处理和交换数据集的最流行的输出之一。 顾名思义，SSTable 是一种简单的抽象，可以有效地存储大量键值对，同时针对高吞吐量、顺序读/写工作负载进行优化。

不幸的是，SSTable 名称本身也被行业重载以指代远远超出排序表的服务，这只会给本身非常简单且有用的数据结构增加不必要的混淆。 让我们仔细看看 SSTable 的背后以及 LevelDB 如何使用它。

SSTable: Sorted String Table

想象一下，我们需要处理输入大小为 GB 或 TB 的大型工作负载。 此外，我们需要在其上运行多个步骤，这些步骤必须由不同的二进制文件执行——换句话说，假设我们正在运行一系列 Map-Reduce 作业！ 由于输入的大小，读取和写入数据可以支配运行时间。 因此，随机读取和写入不是一种选择，相反，我们希望将数据流式传输，完成后，将其作为流式操作刷新回磁盘。 这样，我们可以分摊磁盘 I/O 成本。 没有什么革命性的，继续前进。

Sorted String Table，“排序字符串表”就是它听起来的样子，它是一个文件，其中包含一组任意的、排序的键值对。 重复键很好，键或值不需要“填充”，键和值是任意的 blob。 按顺序读入整个文件，你就有了一个排序的索引。 或者，如果文件非常大，我们也可以预先添加或创建一个独立的 key:offset 索引以进行快速访问。 这就是 SSTable ：非常简单，但也是一种非常有用的交换大型排序数据段的方法。

SSTable and BigTable: Fast random access?

一旦 SSTable 在磁盘上，它实际上是不可变的，因为插入或删除将需要对文件进行大量 I/O 重写。 话虽如此，对于静态索引，这是一个很好的解决方案：读入索引，你总是一个磁盘搜索，或者只是将整个文件 memmap 到内存。 随机读取既快速又容易。

随机写入更加困难和昂贵，也就是说，除非整个表都在内存中，在这种情况下我们又回到了简单的指针操作。 事实证明，这正是 Google 的 BigTable 着手解决的问题：对 PB 级数据集的快速读/写访问，由底层的 SSTables 支持。 他们是如何做到的呢？

SSTables and Log Structured Merge Trees

我们希望保留 SSTable 为我们提供的快速读取访问，但我们也希望支持快速随机写入。 事实证明，我们已经拥有了所有必要的部分：当 SSTable 在内存中时（我们称之为 MemTable），随机写入速度很快，如果表是不可变的，那么磁盘上的 SSTable 也可以快速读取。 现在让我们介绍以下约定：

• 磁盘上的 SSTable 索引总是加载到内存中
• 所有写入都直接进入 MemTable 索引
• 读取首先检查 MemTable，然后检查 SSTable 索引
• 定期将 MemTable 作为 SSTable 刷新到磁盘
• 磁盘上的 SSTable 会定期“折叠在一起”

我们在这里做了什么？ 写入总是在内存中完成，因此总是很快。 一旦 MemTable 达到一定大小，它就会作为不可变的 SSTable 刷新到磁盘。 但是，我们会在内存中维护所有的 SSTable 索引，这意味着对于任何读取，我们可以先检查 MemTable，然后遍历 SSTable 索引的序列来找到我们的数据。 事实证明，我们刚刚重新发明了 Patrick O’Neil 描述的“日志结构合并树”（Log-Structured Merge-Tree, LSM 树），这也是“BigTable Tablets”背后的机制。

LSM & SSTables: Updates, Deletes and Maintenance

这种“LSM”架构提供了许多有趣的行为：无论数据集的大小如何，写入总是很快（仅附加），随机读取要么从内存中提供，要么需要快速磁盘搜索。 但是，更新和删除呢？

一旦 SSTable 在磁盘上，它就是不可变的，因此更新和删除不能触及数据。 取而代之的是，更新的值只是存储在 MemTable 中，并在删除时附加“墓碑”记录。 因为我们按顺序检查索引，未来的读取将找到更新的或墓碑记录，而不会到达旧值！ 最后，拥有数百个磁盘 SSTables 也不是一个好主意，因此我们会定期运行一个过程来合并磁盘上的 SSTables，此时更新和删除记录将覆盖并删除旧数据。

SSTables and LevelDB

拿一个 SSTable，添加一个 MemTable 并应用一组处理约定，你会得到一个很好的数据库引擎，用于某些类型的工作负载。事实上，Google 的 BigTable、Hadoop 的 HBase 和 Cassandra 等都在使用这种架构的变体或直接副本。

表面上很简单，但像往常一样，实现细节很重要。值得庆幸的是，谷歌 SSTable 和 BigTable 基础设施的原始贡献者 Jeff Dean 和 Sanjay Ghemawat 在去年早些时候发布了 LevelDB，它或多或少是我们上面描述的架构的精确复制品：

• 引擎盖下的 SSTable，用于写入的 MemTable
• 键和值是任意字节数组
• 支持 Put、Get、Delete 操作
• 数据的前向和后向迭代
• 内置 Snappy 压缩

设计为 WebKit 中 IndexDB 的引擎（嵌入在浏览器中），它易于嵌入、快速，最重要的是，它负责处理所有 SSTable 和 MemTable 刷新、合并和其他粗糙的细节。

Working with LevelDB: Ruby

LevelDB 是一个库，而不是一个独立的服务器或服务——尽管您可以轻松地在上面实现一个。 首先，获取您最喜欢的语言绑定 (ruby)，让我们看看我们可以做什么：

require 'leveldb' # gem install leveldb-ruby

db = LevelDB::DB.new "/tmp/db"
db.put "b", "bar"
db.put "a", "foo"
db.put "c", "baz"

puts db.get "a" # => foo

db.each do |k,v|
 p [k,v] # => ["a", "foo"], ["b", "bar"], ["c", "baz"]
end

db.to_a # => [["a", "foo"], ["b", "bar"], ["c", "baz"]]

我们可以通过几行代码存储密钥、检索它们并执行范围扫描。 维护 MemTables、合并 SSTables 以及其余的机制由 LevelDB 为我们处理 - 很好而且简单。

LevelDB in WebKit and Beyond

SSTable 是一种非常简单且有用的数据结构——一种很棒的批量输入/输出格式。 然而，使 SSTable 快速（排序且不可变）的原因也暴露了它的局限性。 为了解决这个问题，我们引入了 MemTable 的概念，以及一组用于管理许多 SSTable 的“日志结构化”处理约定。

所有简单的规则，但一如既往，实现细节很重要，这就是为什么 LevelDB 是开源数据库引擎堆栈的一个很好的补充。 很有可能，您很快就会发现 LevelDB 嵌入在您的浏览器、手机和许多其他地方。