Why Prefix Seek?
Normally, when an iterator seek is executed, RocksDB needs to place the position at every sorted run (memtable, level-0 file, other levels, etc) to the seek position and merge these sorted runs. This can sometimes involve several I/O requests. It is also CPU heavy for decompression of several data blocks and other CPU overheads.
Prefix seek is a feature for mitigating these overheads for some use cases. The basic idea is that, if users know the iterating will be within one key prefix, the common prefix can be used to reduce costs. The most commonly used prefix iterating technique is prefix bloom filter. If many sorted runs don't contain any entry for this prefix, it can be filtered out by a bloom filter, and some I/Os and CPU for the sorted run can be ignored.
A motivating use case for prefix seek is representing multi-maps, such as secondary indexes in MyRocks, where the RocksDB prefix is the key for the multimap and a RocksDB iterator finds all the entries associated with that prefix (multimap key).
Whether prefix seek can improve performance is workload dependent. It's more likely to be effective for very short iterator queries than longer ones.
Defining a "prefix"
"Prefix" is defined by options.prefix_extractor, which is a shared_pointer of a SliceTransform instance. By calling SliceTransform.Transform() against a key, we extract a Slice representing a substring of the Slice, usually the prefix part. In this wiki page, we use "prefix" to refer to the output of options.prefix_extractor.Transform() of a key. You can use fixed length prefix transformer, by calling NewFixedPrefixTransform(prefix_len), a capped length prefix transformer, by calling NewCappedPrefixTransform(prefix_len), or you can implement your own prefix transformer in the way you want and pass it to options.prefix_extractor. Prefix extractor is related to comparator. A prefix extractor needs to be used with a comparator where keys with the same prefix are close to each others in the total order defined by the comparator.
The recommendation is to use capped prefix transform with bytewise or reverse bytewise comparators when possible. It will maximize features supported with relatively good performance.
Configure prefix bloom filter
Although it is not the only way users can take advantage of prefix iterating, prefix bloom filter in block-based SST file is the most commonly used and effective one. Here is an example how you can set up prefix bloom filters in SST files.
Options options; // Set up bloom filter rocksdb::BlockBasedTableOptions table_options; table_options.filter_policy.reset(rocksdb::NewBloomFilterPolicy(10, false)); table_options.whole_key_filtering = false; // If you also need Get() to use whole key filters, leave it to true. options.table_factory.reset( rocksdb::NewBlockBasedTableFactory(table_options)); // For multiple column family setting, set up specific column family's ColumnFamilyOptions.table_factory instead.// Define a prefix. In this way, a fixed length prefix extractor. A recommended one to use. options.prefix_extractor.reset(NewCappedPrefixTransform(3)); DB* db; Status s = DB::Open(options, "/tmp/rocksdb", &db);How this bloom filter is used depends on ReadOptions setting in read queries. See the section below for details.
options.prefix_extractor can be changed when DB is restarted. Usually the end result would be that bloom filters in existing SST files will be ignored in reads. In some cases, old bloom filters can still be used. This will be explained in following sections.
Configure reads while prefix bloom filters are set up
How to ignore prefix bloom filters in read
Users can only use prefix bloom filter to read inside a specific prefix. If iterator is outside a prefix, the feature needs to be disabled for specific iterators to prevent wrong results:
Here is an example how this feature can be used: for a fixed length prefix extractor of 3, following queries will take advantage of bloom filters:
options.prefix_extractor.reset(NewCappedPrefixTransform(3)); options.comparator = BytewiseComparator(); // This is the default// ...... ReadOptions read_options; read_options.auto_prefix_mode = true; std::string upper_bound; Slice upper_bound_slice; // "foo2" and "foo9" share the same prefix "foo". upper_bound = "foo9"; upper_bound_slice = Slice(upper_bound); read_options.iterate_upper_bound = &upper_bound_slice; Iterator* iter = db->NewIterator(read_options); iter->Seek("foo2"); // "foobar2" and "foobar9" share longer prefix than "foo". upper_bound = "foobar9"; upper_bound_slice = Slice(upper_bound); read_options.iterate_upper_bound = &upper_bound_slice; Iterator* iter = db->NewIterator(read_options); iter->Seek("foobar2"); // "foo2" and "fop" doesn't share the same prefix, but "fop" is the successor key of prefix "foo" which is the prefix of "foo2". upper_bound = "fop"; upper_bound_slice = Slice(upper_bound); read_options.iterate_upper_bound = &upper_bound_slice; Iterator* iter = db->NewIterator(read_options); iter->Seek("foo2");This feature has some limitations:
- It only supports fixed and capped prefix extractor
- The comparator needs to implement
IsSameLengthImmediateSuccessor(). The built-in byte-wise and reverse byte-wise comparators have it implemented. - Right now only
Seek()can automatically take advantage of the feature by comparing seek key with iterator upper bound.SeekForPrev()never uses prefix bloom filter. (no fundamental reason why it can't be done. You are welcome to finish the feature) - Some extra CPU is used to determine qualification of prefix bloom filter in each SST file to query.
Manual prefix iterating
With this option, users determine their use case qualifies for prefix iterator and are responsible of never iterating outside iterator. RocksDB will not return error when it is misused and the iterating result will be undefined. Note that, when iterating outside the iterator range, the result might not be limited to missing keys. Some undefined result might include: deleted keys might show up, key ordering is not followed, or very slow queries. Also note that even data within the prefix range might not be correct if the iterator has moved out of the prefix range and come back again.
Right now this mode is the default for backward compatible reason, but users should be extra careful when using this mode.
How to use the manual mode:
When options.prefix_extractor is not nullptr and with default ReadOptions, iterators are not guaranteed a total order of all keys, but only keys for the same prefix. When doing Iterator.Seek(lookup_key), RocksDB will extract the prefix of lookup_key. If there is one or more keys in the database matching prefix of lookup_key, RocksDB will place the iterator to the key equal or larger than lookup_key of the same prefix, as for total ordering mode. If no key of the prefix equals or is larger than lookup_key, or after calling one or more Next(), we finish all keys for the prefix, we might return Valid()=false, or any key (might be non-existing) that is larger than the previous key. Setting ReadOptions.prefix_same_as_start=true guarantees the first of those two behaviors.
From release 4.11, we support Prev() in prefix mode, but only when the iterator is still within the range of all the keys for the prefix. The output of Prev() is not guaranteed to be correct when the iterator is out of the range.
When prefix seek mode is enabled, RocksDB will freely organize the data or build look-up data structures that can locate keys for specific prefix or rule out non-existing prefixes quickly. Here are some supported optimizations for prefix seek mode: prefix bloom for block based tables and mem tables, hash-based mem tables, as well as PlainTable format. One example setting:
Options options; // Enable prefix bloom for mem tables options.prefix_extractor.reset(NewFixedPrefixTransform(3)); options.memtable_prefix_bloom_size_ratio = 0.1; // Enable prefix hash for SST files BlockBasedTableOptions table_options; table_options.index_type = BlockBasedTableOptions::IndexType::kHashSearch; DB* db; Status s = DB::Open(options, "/tmp/rocksdb", &db); ...... auto iter = db->NewIterator(ReadOptions()); iter->Seek("foobar"); // Seek inside prefix "foo"From release 3.5, we support a read option to allow RocksDB to use total order even if options.prefix_extractor is given. To enable the feature set ReadOption.total_order_seek=true to the read option passed when doing NewIterator(), example:
From release 6.8, we support a similar option while allowing underlying implementation to take advantage of prefix specific information when not impacting results.
auto iter = db->NewIterator(ReadOptions()); Slice key = "foo_bar"; iter->Seek(key);Not all table formats support total order seek. For example, the newly introduced PlainTable format only supports prefix-based seek() unless it is opened in total order mode (Options.prefix_extractor == nullptr).
Use ReadOptions.prefix
This is the least flexible way to do a seek. Prefix needs to be supplied when creating an iterator.
Slice prefix = "foo"; ReadOptions ro; ro.prefix = &prefix; auto iter = db->NewIterator(ro); Slice key = "foo_bar" iter->Seek(key);Options.prefix_extractor is a prerequisite. The Seek() is constrained to the prefix provided by ReadOptions, which means you will need to create a new iterator to seek a different prefix. The benefit of this approach is that irrelevant files are filtered out at the time of building the new iterator. So if you want to seek multiple keys with the same prefix, it might perform better. However, we consider this is a very rare use case.
Use ReadOptions.prefix_seek
This mode is more flexible than ReadOption.prefix. No pre-filtering is done at iterator creation time. As a result, the same iterator can be reused for seek of different key/prefix.
ReadOptions ro; ro.prefix_seek = true; auto iter = db->NewIterator(ro); Slice key = "foo_bar"; iter->Seek(key);Same as ReadOptions.prefix, Options.prefix_extractor is a prerequisite.
What's Changed
It becomes obvious that 3 modes of seek are confusing:
- One mode would require another option to be set (e.g.
Options.prefix_extractor); - It is not obvious to our users which mode of the last two is preferred under different circumstances
This change tries to address this issue and makes things straight: by default, Seek() is performed in prefix mode if Options.prefix_extractor is defined and vice versa. The motivation is simple: if Options.prefix_extractor is provided, it is a very clear signal that underlying data can be sharded and prefix seek is a natural fit. Usage becomes unified:
auto iter = db->NewIterator(ReadOptions()); Slice key = "foo_bar"; iter->Seek(key);Transition to the New Usage
Transition to the new style should be simple: remove the assignment to Options.prefix or Options.prefix_seek, since they are deprecated. Now, seek directly with your target key or prefix. Since Next() can go across the boundary to a different prefix, you will need to check the end condition:
auto iter = DB::NewIterator(ReadOptions()); for (iter.Seek(prefix); iter.Valid() && iter.key().starts_with(prefix); iter.Next()) { // do something }本文档中文部分由 johnzeng 翻译完成，在此表示感谢。 欢迎大家贡献力量，加QQ群联系。