让我们从键值数据的索引开始。这不是你可以索引的唯一类型的数据，但它非常常见，而且它是构建更复杂索引的一个有用的模块。
键值存储与大多数编程语言中可以找到的dictionary类型非常相似，通常是作为散列表实现的。在许多算法教科书中都描述了哈希映射，因此我们不会详细讨论它们是如何工作的。既然我们已经有了内存数据结构的哈希映射，为什么不使用它们来索引磁盘上的数据呢?
假设我们的数据存储只包括追加记录到一个文件，就像前面的例子一样。然后，最简单的索引策略是:保存一个内存中的散列映射，其中每个键都映射到数据文件中的一个字节偏移位置，这个位置的值如图3-1所示可以被找到。当你在文件中添加新的键值对时，您还将更新散列映射以反映您刚刚编写的数据的偏移量（这既用于插入新键，也用于更新现有的键）。当您想查找一个值时，使用散列映射来查找数据文件中的偏移量，查找该位置，并读取该值。
图3-1 以类csv的格式存储键值对，并使用内存散列映射进行索引。
这听起来可能过于简单，但却是可行的方法。实际上，这就是Bitcask (Riak的默认存储引擎）所做的事情。Bitcask提供高性能的读写，根据要求，所有的键都可以放在可用的RAM中，因为哈希映射被完全保存在内存中。这些值可以使用比可用内存更多的空间，因为它们可以从磁盘上加载。如果数据文件的那一部分已经在文件系统缓存中，那么read不需要任何磁盘I/O。
像Bitcask这样的存储引擎非常适合于每个密钥的值经常更新的情况。例如，密钥可能是一只猫的视频URL，其值可能是它被播放的次数（每次有人点击播放按钮时递增）。在这种模式中，有很多写操作，但是没有太多不同的键——每个键有大量的写，但是将所有的键保存在内存中是可行的。
到目前为止，我们只讨论了追加记录到文件中，那么如何避免最终耗尽磁盘空间呢?一个好的解决方案是，当它达到一定的大小时，关闭一个segment文件，然后将其写入一个新的segment文件，从而将日志分割成一定大小的segment。然后我们可以对这些片段执行压缩，如图3-2所示。压缩意味着在日志中丢弃重复的键，并且只保留每个键的最新更新。
图3-2 键值更新日志的压缩(计算猫视频播放的次数)，只保留每个键的最新值
此外，由于压缩常常使segment更小（假设一个键在一个segment内平均覆盖了几次），我们还可以同时合并多个segment，同时执行压缩，如图3-3所示。segment在写入后不会被修改，因此合并的segment被写入到一个新文件中。历史segment的合并和压缩可以在后台线程中完成，而在进行的过程中，我们仍然可以使用旧的segment文件继续服务读和写请求。在合并过程完成之后，我们将读取请求改为使用新的合并segment而不是旧的segment，然后删除旧的segment文件。
图3-3 执行压缩和segment合并
每个segment现在都有自己的内存哈希表，映射键来进行文件偏移。为了找到密钥的值，我们首先检查最近segment的散列映射；如果密钥不存在，我们将检查第二个最近的部分。。。合并进程保持了segment的数量很少，所以查找不需要检查很多散列映射。
这个简单的想法在实践中有很多细节。简而言之，真正实施的一些重要问题是:
文件格式
CSV不是日志的最佳格式。使用二进制格式（以字节为单位编码字符串的长度）和原始字符串（不需要转义)会更快更简单。
删除记录
如果您想删除一个键及其相关值，则必须将一个特殊的删除记录附加到数据文件（有时称为tombstone）。当segment被合并时，tombstone告诉合并进程放弃删除键的任何先前值。
崩溃恢复
如果数据库重新启动，内存中的散列映射就会丢失。原则上，你可以通过从头到尾读取整个segment文件来恢复每个segment的哈希映射，并注意在进行过程中每个键的最新值的偏移量。但是，如果segment文件很大，这可能需要很长时间，这会使服务重启很痛苦。Bitcask通过在磁盘上存储每个segment的散列映射的快照来加速恢复，这可以更快地加载到内存中。
部分文字记录
数据库可能在任何时候崩溃，包括将记录追加到日志的过程中。Bitcask文件包括校验和，允许检测和忽略该日志中损坏的部分。
并发控制
由于写入是严格按顺序添加到日志中的，所以一个常见的实现选择是只有一个写线程。数据文件segment是只允许追加，而且是不可变的，以便于可以通过多个线程并发地读取它们。
一个只允许追加的文件第一眼看上去很浪费：为什么不更新文件，用新值重写旧值？但是只允许追加的设计是好的，有几个原因：
- 追加和segment合并是顺序写操作，通常比随机写快得多，特别是在magnetic spinning-disk硬盘上。在某种程度上，顺序写在基于闪存的固态硬盘（ssd）上也更可取。我们将在后面的“比较BTrees和LSM-Trees”中进一步讨论这个问题。
- 如果segment文件是只允许追加的或不可变的，那么并发和崩溃恢复要简单得多。例如，您不必担心发生崩溃时当一个值被覆盖，会留下一个包含旧值的一部分，同时又将新值的一部分拼接在一起的文件。
- 合并旧的segment可以避免数据文件随着时间的推移而变得支离破碎的问题。
然而，哈希表索引也有限制：
- 哈希表必须适合内存，所以如果你有非常多的键，你就不走运了。原则上，您可以在磁盘上维护一个散列映射，但不幸的是，很难使磁盘上的哈希映射执行良好。它需要大量的随机访问I/O，而且当它很大时，再增长的代价就比较昂贵了，并且散列冲突也需要复杂的逻辑。
- 范围查询无效。例如，您不能轻松地扫描kitty00000和kitty99999之间的所有key，您必须在散列映射中单独查找每个键。
在下一节中，我们将研究一个没有这些限制的索引结构。
网友评论