存储与检索 -- 为数据库提供动力的数据结构(SSTables
在图3-3中，每个日志结构的存储段（Segment）都是键-值对的序列。这些成对出现在它们被写入的顺序中，并且在日志中靠后的值优先于之前相同键的值。除此之外，文件中键值对的顺序无关紧要。
现在，我们可以对分段文件的格式做一个简单的更改：我们要求键-值对的顺序按键排序。乍一看，这个需求似乎破坏了我们使用顺序写的能力，但是我们马上就会讲到。
我们称这种格式为排序的字符串表，简称SSTable。我们还要求每个密钥只在每个合并段文件中出现一次（压缩过程已经确保了这一点）。与哈希索引的日志片段相比，SSTable有几个大的优势：
- 1.合并段(Segment)是简单和有效的，即使文件比可用内存大。该方法类似于mergesort算法中使用的方法，如图3-4所示：您开始逐个读取输入文件，查看每个文件中的第一个键，将最低键（根据排序顺序）复制到输出文件，然后重复。这会产生一个新的合并文件，也按键排序。
图3-4 合并几个SSTable的Segment，只保留每个键的最新值。
如果相同的键出现在几个输入段（Segment）中会怎样？请记住，每个段（Segment）包含在一段时间内写入数据库的所有值。这意味着一个输入段（Segment）中的所有值必须比其他段（Segment）中的所有值都要近（假设我们总是合并相邻段）。当多个段（Segment）包含相同的键时，我们可以将值保存在最近的段（Segment）中，并丢弃旧段（Segment）中的值。
- 2.为了在文件中找到一个特定的键，你不再需要保存内存中所有键的索引。请参见图3-5中的示例：假设你正在寻找关键的手工制品，但你不知道该段（Segment）文件中该键的确切偏移量。然而，你确切知道钥匙手提包和漂亮东西的偏移量，而且因为分类，你知道手工制品肯定在这两者之间。这意味着你可以跳转到手提包的偏移量，然后从那里扫描直到你找到手工制品（当然如果它不在文件中也可能找不到）。
图3-5 一个带有内存索引的SSTable。
你仍然需要一个内存索引来告诉你一些键的偏移量，但是它可能是稀疏的：每几kb的段（Segment）文件的一个键就足够了，因为可以很快地扫描几个千字节。
- 3.由于读请求需要在请求的范围内扫描多个键-值对，所以可以将这些记录分组到一个块中，并在将其写到磁盘之前压缩它（如图3-5所示的阴影区域）。稀疏内存索引的每个条目都指向一个压缩块的开始。除了节省磁盘空间，压缩还减少了i/o带宽的使用。
构建和维护SSTables
到目前为止还不错——但是如何让你的数据首先按键排序呢？我们的写操作可以以任意顺序出现。
在磁盘上维护一个排序结构是可能的（详见后面的BTree），但是在内存中维护它要容易得多。有许多众所周知的树数据结构，比如红黑树或AVL树。有了这些数据结构，你可以按任意顺序插入键，并按顺序读取它们。
我们现在可以让我们的存储引擎工作如下：
- 当一个写入进来时，将其添加到内存中平衡的树数据结构中（例如，红黑树）。这个内存中的树有时也被称为memtable。
- 当memtable大于某个阈值时——通常是几兆字节——将其写到磁盘上作为一个SSTable文件。这可以有效地完成，因为树已经维护了按键排序的键值对。新的SSTable文件成为数据库中最新的部分。当SSTable被写到磁盘上时，写操作可以继续写到一个新的memtable实例。
- 为了服务于读请求，首先要在memtable中找key，然后在最近的磁盘段（Segment）中找key，然后在下一个较新的段（Segment）中找key.....
- 通常，在后台运行合并和压缩过程，用来合并段（Segment）文件并丢弃被覆盖或删除的值。
这个计划很有效。它只会遇到一个问题：如果数据库崩溃，最近的写入（在memtable中，但还没有写到磁盘）就会丢失。为了避免这个问题，我们可以在磁盘上保留一个单独的日志，每一个写入都立即被追加，就像在前一节中一样。该日志不是按顺序排列的，但这并不重要，因为它的唯一目的是在崩溃后恢复表。所以每当memtable被写到一个SSTable时，相应的日志就会被丢弃。
用SSTables实现LSM-Tree
这里描述的算法是在LevelDB和RocksDB中使用的，键值存储引擎库被设计成嵌入到其他应用程序中。除此之外，LevelDB可以在Riak中作为Bitcask的替代品。在Cassandra和HBase中也使用了类似的存储引擎，这两种引擎都受到了Google的Bigtable paper的启发（它引入了SSTable和memtable的术语）。
最初，这个索引结构是由Patrick o'neil等人在“Log-Structured Merge-Tree ”（或LSM-Tree）中描述的，它建立在早期的日志结构文件系统的工作基础上。而基于合并和压缩排序文件的存储引擎通常被称为LSM存储引擎。
Lucene，是Elasticsearch和Solr全文搜索索引引擎的内核，它使用了一种类似的方法来存储它的词汇字典。全文索引要比键值索引复杂得多，但它基于一个类似的想法：在搜索查询中给定一个单词，找到提到这个单词的所有文档（web页面、产品描述等）。这是用一个键值结构来实现的，其中键是一个单词（一个术语），值是包含单词的所有文档的id列表（term）。在Lucene中，从term到发布列表的映射保存在类似于SSTable的排序文件中，这些文件在需要的时候被合并到后台。
性能优化
和通常一样，在实践中，存储引擎的性能很好。例如，LSM-tree算法在查找一个数据库中不存在的键时是可以非常缓慢的：你必须检查memtable，然后检查段（Segment）直到追溯到最古老（可能需要从磁盘读取每一个）的，可以肯定的是，键是不存在的。为了优化这种访问方式，存储引擎通常使用额外的Bloom过滤器 。（Bloom过滤器是一种内存高效的数据结构，用于近似一组内容。它可以告诉你，如果一个键没有出现在数据库中，这样就可以为不存在的键节省许多不必要的磁盘读取）。
也有不同的策略来确定压缩和合并SSTables的顺序和时间。最常见的选择是size-tiered和leveled compaction。LevelDB和RocksDB使用了leveled compaction（所以叫LevelDB嘛），HBase使用size-tiered，而Cassandra支持两者。在size-tiered，更新的和较小的SSTables相继合并成更久的、更大的SSTables。在leveled compaction中，关键的范围被分割成更小的SSTables，旧的数据被移动到单独的“级别”中，这使得压缩可以更增量地进行，并且使用更少的磁盘空间。
尽管有许多微妙之处，但lsm的基本理念——保持在后台融合的一系列的SSTables——是简单而有效的。即使数据集比可用内存大得多，它仍然可以很好地工作。由于数据是以排序的顺序存储的，所以你可以有效地执行范围查询（扫描最小值以上和最大值一下的键），并且由于磁盘写的顺序是连续的，因此lsm可以支持非常高的写吞吐量。
