RocksDB 在一个数据块中查找一个 key 的时候，使用二分搜索。然而，为了找到数据所在的正确的位置，需要多次 key 解析和压缩。每个二分搜索导致的 CPU 缓存未命中，都会导致更高的 CPU 使用率。在生产环境，我们曾发现这个二分搜索占用了非常可观的 CPU 使用量。

一个数据块中的哈希索引被设计和开发出来，用于优化点查询中的 CPU 使用率。使用 db_bench 的性能测试显示，点查询中的一个主要方法，DataBlockIter::Seek()，的 CPU 使用率减低了 21.8%，在纯缓存压力下，RocksDB 的总体吞吐增加了 10%，带来的额外开销是 4.6% 的内存。

如何使用¶

这个功能加入了两个新的选项：BlockBasedTableOptions::data_block_index_type 和 BlockBasedTableOptions::data_block_hash_table_util_ratio。

哈希索引默认是关闭的，除非设置了 BlockBasedTableOptions::data_block_index_type 为 kDataBlockBinaryAndHash。哈希表的使用率通过 BlockBasedTableOptions::data_block_hash_table_util_ratio 来配置，同样只有 data_block_index_type = kDataBlockBinaryAndHash 的时候有效。

// the definitions can be found in include/rocksdb/table.h

// The index type that will be used for the data block.
enum DataBlockIndexType : char {
  kDataBlockBinarySearch = 0,  // traditional block type
  kDataBlockBinaryAndHash = 1, // additional hash index
};

DataBlockIndexType data_block_index_type = kDataBlockBinarySearch;

// #entries/#buckets. It is valid only when data_block_hash_index_type is
// kDataBlockBinaryAndHash.
double data_block_hash_table_util_ratio = 0.75;

需要注意的事情¶

自定义比较器¶

哈希索引会哈希不同的 key（不同的内容，以及字节序列）到不同的哈希值。这就假设了比较器不会把两个内容不同的 key 认为是相等的。

默认的字节比较器把 key 按照字典序排列，并且能跟哈希索引友好合作，因为不同的 key 不会被认为是相等的。然而，有些特别构造的比较器可能会这么做。例如，比如说 StringToIntComparator 可以把一个字符串转换成整形，然后使用整形来进行比较，key "16" 和 "0x10" 在 StringToIntComparator 看来是相等的，但是他们大概率有两个不同的哈希值。后续的查找其中一种格式的 key 可能无法找到另一种格式的 key。

我们加入了一个新的方法给比较器接口：

virtual bool CanKeysWithDifferentByteContentsBeEqual() const { return true; }

每个比较器的实现应该覆盖这个函数，并且声明这个比较器应该有的行为。如果一个比较器可能认为不同的 key 是相等的，这个函数返回 true，这样，哈希索引的功能就不会打开了，反之亦此。

注意：为了使用哈希索引功能，你应该 1) 有一个比较器，不会认为两个不同的 key 相等 2) 覆盖 CanKeysWithDifferentByteContentsBeEqual 方法，返回 false，这样才能打开哈希索引

小 util_ratio 对数据块缓存的影响¶

把哈希索引加入到数据块的末尾会消耗数据块缓存的空间，导致实际有效的数据块大小变小，并且增加数据块缓存未命中率。因此，一个非常小 util_ratio 会导致在一个巨大的数据块缓存未命中，额外的 IO 会抵消通过哈希缓存索引带来的吞吐增长。另外，当允许压缩（compression），哈希未命中率会增加数据块的解压缩操作，同样也会消耗 CPU。因此，如果 util_ratio 过小，CPU 可能反而会增长。最好的 util_ratio 根据工作压力，数据缓存比率，磁盘贷款，延迟而定。在我们的经验，我们认为 util_ratio 在 0.5 ~ 1 之间是比较好的范围，既减小 cpu 使用，又增加吞吐

限制¶

由于我们用 uint8_t 来存储二分搜索索引，比如，重启间隔索引，重启间隔的总大小不能大于 253（我们保留 255 和 254 作为特别标记）。对于有大量重启间隔的块，哈希索引不会被创建，点查询不会使用传统的二分搜索进行。

数据块索引只支持点查询。我们不支持区间查询。区间查询会下推到 BinarySeek。

RocksDB 支持非常多类型的记录，比如 Put,Delete,Merge 等等（参考这里了解更多）。目前我们只支持 Put 和 Delete，不支持 Merge。我们内部有一个限制的支持记录类型集合：

kPutRecord,          <=== 支持
kDeleteRecord,       <=== 支持
kSingleDeleteRecord, <=== 支持
kTypeBlobIndex,      <=== 支持

对于不支持的记录，搜索过程会下降到传统的二分搜索。