前缀查找API更改

前缀查找API

当options.prefix_extractor 指定了数据库或列族，RocksDB处于”prefix seek”模式，解释如下。如何使用它的例子:

  1. Options options;
  3. // <---- Enable some features supporting prefix extraction
  4. options.prefix_extractor.reset(NewFixedPrefixTransform(3));
  6. DB* db;
  7. Status s = DB::Open(options, "/tmp/rocksdb",  &db);
  9. ......
  11. auto iter = db->NewIterator(ReadOptions());
  12. iter->Seek("foobar"); // Seek inside prefix "foo"
  13. iter->Next(); // Find next key-value pair inside prefix "foo"

options.prefix_extractor 是一个SliceTransform实例的shared_pointer。 通过调用SliceTransform.Transform()，我们提取了一个表示片的子字符串的片，通常是前缀部分。 在这个wiki页面中，我们使用”prefix”来引用键的options.prefix_extractor.Transform()的输出。 您可以通过调用NewFixedPrefixTransform(prefix_len)来使用固定长度的前缀转换器，或者您可以按照自己的方式实现前缀转换器，并将其传递给options.prefix_extractor。

当options.prefix_extractor不是nullptr, 迭代器能保证所有键的总顺序，只能保证键的前缀相同。 当执行Iterator.Seek(lookup_key)时，RocksDB将提取lookup_key的前缀。 如果在lookup_key的数据库匹配前缀中有一个或多个键，则RocksDB将迭代器放置到与相同前缀的键相等或大于lookup_key的键上，用于总排序模式。 如果前缀的键不等于或大于lookup_key，或者在调用一个或多个Next()之后，我们完成前缀的所有键，我们可能返回Valid()=false，或者任何大于前一个键的键，这取决于ReadOptions.prefix_same_as_start=true。 从4.11版开始，我们支持前缀模式下的Prev()，但是只有当迭代器仍然在前缀的所有键的范围内时才支持。当迭代器超出范围时，不能保证Prev()的输出是正确的。

当启用前缀查找模式时，RocksDB将自由地组织数据或构建查找数据结构，这些数据结构可以为特定的前缀定位键或快速排除不存在的前缀。 以下是一些受支持的前缀搜索模式优化:基于块的表和mem表的前缀bloom、基于散列的mem表以及纯表格式。 设置一个例子:

  1. Options options;
  3. // Enable prefix bloom for mem tables
  4. options.prefix_extractor.reset(NewFixedPrefixTransform(3));
  5. options.memtable_prefix_bloom_bits = 100000000;
  6. options.memtable_prefix_bloom_probes = 6;
  8. // Enable prefix bloom for SST files
  9. BlockBasedTableOptions table_options;
  10. table_options.filter_policy.reset(NewBloomFilterPolicy(10, true));
  11. options.table_factory.reset(NewBlockBasedTableFactory(table_options));
  13. DB* db;
  14. Status s = DB::Open(options, "/tmp/rocksdb",  &db);
  16. ......
  18. auto iter = db->NewIterator(ReadOptions());
  19. iter->Seek("foobar"); // Seek inside prefix "foo"

从3.5版开始，我们支持一个read选项，允许RocksDB使用total order，即使是options.prefix_extractor。 要启用特性集ReadOption.total_order_seek=true 执行NewIterator()时传递的read选项, 例如:

  1. ReadOptions read_options;
  2. read_options.total_order_seek = true;
  3. auto iter = db->NewIterator(read_options);
  4. Slice key = "foobar";
  5. iter->Seek(key);  // Seek "foobar" in total order

在这种模式下，性能可能会更差。请注意，并非所有的prefix实现都支持此选项。例如，一些明文实现不支持它，当您尝试使用它时，您将在状态代码中看到一个错误。 如果使用基于散列的mem表，它可能会执行非常昂贵的在线排序。这种模式在基于块的表的前缀bloom和hash索引中得到了支持。

限制

前缀迭代不支持SeekToLast()。SeekToFirst()只受到一些配置的支持。如果要对迭代器执行这些类型的查询，应该使用total order模式。

使用前缀迭代的一个常见错误是使用前缀模式以相反的顺序进行迭代。但它还没有得到支持。 如果反向迭代是常见的查询模式，则可以重新排序数据，使迭代顺序向前。您可以通过实现定制的比较器来实现，或者以不同的方式编码key。

API 更改 从 2.8 -> 3.0

在本节中，我们将解释2.8版本的API和3.0版本的更改。

在改变之前

在RocksDB 2.8中，有3种寻道模式:

排序查找总计

这是传统的搜索行为。seek在一个总的有序键空间上执行，将迭代器定位为大于或等于您所查找的目标键的键。

  1. auto iter = db->NewIterator(ReadOptions());
  2. Slice key = "foo_bar";
  3. iter->Seek(key);

并不是所有的表格式都支持total order seek。 例如，新引入的明文格式只支持基于前缀的seek()，除非它以完全顺序模式打开(选项)。prefix_extractor == nullptr)。

使用 ReadOptions.prefix

这是最不灵活的搜索方法。创建迭代器时需要提供前缀。

  1. Slice prefix = "foo";
  2. ReadOptions ro;
  3. ro.prefix = &prefix;
  4. auto iter = db->NewIterator(ro);
  5. Slice key = "foo_bar"
  6. iter->Seek(key);

Options.prefix_extractor 先决条件。Seek()受ReadOptions提供的前缀限制，这意味着您需要创建一个新的迭代器来寻找不同的前缀。 这种方法的好处是在构建新的迭代器时过滤掉了不相关的文件。因此，如果您希望查找具有相同前缀的多个键，那么它的性能可能会更好。 然而，我们认为这是一个非常罕见的用例。

使用 ReadOptions.prefix_seek

这种模式比ReadOption.prefix更灵活。在迭代器创建时不进行预过滤。 因此，可以重用同一个迭代器来搜索不同的键/前缀。

  1. ReadOptions ro;
  2. ro.prefix_seek = true;
  3. auto iter = db->NewIterator(ro);
  4. Slice key = "foo_bar";
  5. iter->Seek(key);

和ReadOptions一样。Options.prefix_extractor是先决条件。

改变了什么？

很明显，三种寻求模式是令人困惑的:

  • 一种模式需要设置另一种选项(例如Options.prefix_extractor);
  • 对于我们的用户来说，在不同的情况下，后两种模式的选择并不明显

这个更改试图解决这个问题，并使事情变得简单: 默认情况下，如果Options.prefix_extractor定义了，Seek()是在前缀模式中执行的，反之亦然。 动机很简单: 如果Options.prefix_extractor提供，这是一个非常明确的信号，底层数据可以分片，前缀搜索是一个自然的匹配。 使用变得统一:

  1. auto iter = db->NewIterator(ReadOptions());
  2. Slice key = "foo_bar";
  3. iter->Seek(key);

转换到新的用法

转换到新样式应该很简单: 删除对选项的赋值。Options.prefix or Options.prefix_seek，因为它们是不受欢迎的。

现在，直接使用目标键或前缀进行搜索。

因为Next()可以跨越边界到另一个前缀，

你需要检查结束条件:

  1. auto iter = DB::NewIterator(ReadOptions());
  2. for (iter.Seek(prefix); iter.Valid() && iter.key().starts_with(prefix); iter.Next()) {
  3.    // do something
  4. }