数据块哈希索引

当在数据块中执行点查找键时，RocksDB执行二进制搜索。但是，为了找到key可能驻留的正确位置，需要多个密钥解析和比较。 每个二分查找分支都会触发CPU缓存丢失，从而导致大量CPU利用率。我们已经看到，这种二进制搜索在生产用例中占用了相当大的CPU。

在RocksDB数据块中设计并实现了哈希索引，提高了点查找的CPU效率。使用db_bench进行的基准测试显示， 点查找代码路径中的一个主要函数DataBlockIter::Seek()的CPU利用率降低了21.8%，而在完全缓存的工作负载下，整个RocksDB吞吐量增加了10%，开销增加了4.6%。

如何使用

  1. 作为该特性的一部分，添加了两个新选项:BlockBasedTableOptions::data_block_index_type和BlockBasedTableOptions::data_block_hash_table_util_ratio。
  3. 默认情况下禁用哈希索引，除非将BlockBasedTableOptions::data_block_index_type设置为data_block_index_type = kDataBlockBinaryAndHash。
  4. 使用BlockBasedTableOptions::data_block_hash_table_util_ratio可调哈希表利用率，只有当data_block_index_type = kDataBlockBinaryAndHash时才有效。
  6. // the definitions can be found in include/rocksdb/table.h
  8. // The index type that will be used for the data block.
  9. enum DataBlockIndexType : char {
  10.   kDataBlockBinarySearch = 0,  // traditional block type
  11.   kDataBlockBinaryAndHash = 1, // additional hash index
  12. };
  14. DataBlockIndexType data_block_index_type = kDataBlockBinarySearch;
  16. // #entries/#buckets. It is valid only when data_block_hash_index_type is
  17. // kDataBlockBinaryAndHash.
  18. double data_block_hash_table_util_ratio = 0.75;

需要注意的事情

定制的比较器

哈希索引将不同的键(具有不同内容或字节序列的键)哈希到不同的哈希值。这假设如果不同的键具有不同的内容，比较器不会将它们视为相等的。

默认的bytewise比较器按字母顺序排列键，并且可以很好地处理散列索引，因为不同的键永远不会被认为是相等的。 不过，一些经过特别设计的比较器就可以了。例如，StringToIntComparator可以将字符串转换为整数，并使用整数执行比较。 键字符串”16”和”0x10”在这个StringToIntComparator中是相等的，但是它们可能散列到不同的值。 以后对一种形式的key的查询将无法找到以另一种格式存储的现有key。

我们在比较器接口中添加了一个新的函数成员:

  1. virtual bool CanKeysWithDifferentByteContentsBeEqual() const { return true; }

每个比较器实现都应该覆盖这个函数并指定比较器的行为。如果比较器可以将不同的键视为相等，则函数返回true，因此不会启用hash索引特性，反之亦然。

注意:要使用哈希索引特性，应该 1)有一个比较器，它永远不能将不同的键视为相等; 2)覆盖CanKeysWithDifferentByteContentsBeEqual()函数以返回false，这样就可以启用散列索引。

Util比率对数据块缓存的影响

在数据块末尾添加哈希索引实际上占用了数据块缓存空间，从而减小了有效数据块缓存的大小，并增加了数据块缓存的命中率。 因此，非常小的util比率将导致较大的数据块缓存遗漏率，额外的I/O可能会降低哈希索引查找所获得的吞吐量增益。 此外，当启用压缩时，cache miss还会导致数据块解压缩，这会消耗cpu资源。 因此，如果使用过小的util比率，CPU甚至可能增加。最佳的util比率取决于工作负载、缓存与数据的比率、磁盘带宽/延迟等。 在我们的实验中，我们发现util比值= 0.5 ~ 1是一个很好的范围，可以同时带来CPU和吞吐量的提高。

限制

由于我们使用uint8_t来存储二进制查找索引，即重启间隔索引，所以重启间隔的总数不能超过253(我们保留了255和254作为特殊标志)。 对于具有较大重启间隔的块，将不会创建哈希索引，而点查找将由传统的二进制查找完成。

数据块哈希索引只支持点查找。我们不支持范围查找。范围查找请求将返回到BinarySeek。

RocksDB支持多种类型的记录，如Put、Delete、Merge等(请访问这里获取更多信息)。目前我们只支持Put和Delete，不支持Merge。 在内部，我们有一组有限的受支持的记录类型:

  1. kPutRecord,          <=== supported
  2. kDeleteRecord,       <=== supported
  3. kSingleDeleteRecord, <=== supported
  4. kTypeBlobIndex,      <=== supported

对于不支持的记录，搜索过程将回到传统的二进制查找。