rocksdb-doc-cn

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,      <=== 支持

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

看到这里或许你有建议或者疑问或者指出错误,请留言评论! 多谢! 你的评论非常重要!也可以帮忙点赞收藏转发!多谢支持! 觉得写的不错那就给点吧, 在线乞讨 微信转账