upstream/rocksdb
2
0 Fork 0
mirror of https://github.com/facebook/rocksdb.git synced 2026-11-07 03:22:34 -05:00
Code Releases 1 Activity
Files
main
rocksdb/table/block_based/block_cache.cc
T
Peter Dillinger ea5db0c142 Fix format_version=8 common prefix extending past a user key (#15556) 
Summary:
## Background / Motivation
With format_version=8 (not yet the default) and optimize_key_common_prefix, each data and index block stores one common prefix. The design and code intend that prefix to be a prefix of every user key in the block. Seek and SeekForPrev for bytewise and reverse bytewise comparators rely on that: they strip the prefix from the target and from the block's keys, then compare what remains (the "prefix-optimized seek"). That preserves ordering only if the stripped bytes are user key bytes.

Before this change, BlockBuilder limited the prefix to the user key of the first key and of each restart key. For other keys, it limited the prefix only to the internal key bytes shared with the previous key. ReverseBytewiseComparator orders a user key after longer user keys that extend it, so those shared bytes could reach past a user key into its internal key footer. For example, in a block with `ab\x01c` followed by a Put of `ab`, whose internal key begins `ab\x01` because the first footer byte is the value type, the stored prefix was `ab\x01`. Because internal keys are not bytewise comparable, the prefix-stripped comparisons then gave wrong results:
* Get, MultiGet and seeks could miss such a key. A missed deletion would expose an older value.
* Iteration could skip such a key or fail a debug assertion, because iterators seek internally after skipping many versions of a key and when changing direction.
* A compaction with subcompactions seeks to the start key of each subcompaction, and could skip versions of such a key there. The check of the number of input records (compaction_verify_record_count, on by default) then fails the compaction with Corruption; without that check, the skipped versions would likely be dropped from the compaction output.

Index blocks of internal keys with index_block_restart_interval > 1 could be affected the same way, theoretically including filter partition indexes. RocksDB 11.10 through 11.13 wrote such blocks.

Other comparators were not buggy:
* With BytewiseComparator, the prefix cannot extend past a user key, because a user key sorts before every longer user key that extends it.
* With other comparators (optimize_key_common_prefix=kEnabled), a prefix extending past a user key is apparently benign, at least for now, because their reads reconstruct full keys before comparing.

This bug was found by an agent in D126805261, but this solution is less deeply intrusive in the most performance-critical areas and generally improves performance with a bundled optimization.

## This Change
This change fixes the writer, makes the reader handle "bad" blocks that have already been written, and bundles an optimization of the prefix-optimized seek that offsets the cost of the reader fix.

### Write Path
BlockBuilder now also limits the prefix to the user key of each non-restart key, so new blocks store only a common user key prefix, with any comparator.

There is no format change. Blocks written with this change meet the invariant that all format_version=8 readers assume, so older versions read them correctly.

### Read Path
When a data or index block (including a filter partition index block) of a table opened with ReverseBytewiseComparator is loaded, the reader checks whether the stored prefix extends past a user key. If it does, seeks within that block use the existing full-key search (as for other comparators) instead of the prefix-optimized seek. BlockBasedTable::Open() enables the check; blocks inserted into the block cache while building a table (prepopulate_block_cache) come from the fixed writer and are not checked.

Checking only the block's last entry is enough. A user key shorter than the stored prefix is extended by every other user key in the block, so in reverse bytewise order its versions are the block's last entries. None of them can be a restart key, since the prefix was limited to each restart key's user key, so they all follow the last restart point. The check therefore costs:
* for a data block, decoding the entry headers of the last restart interval;
* for an index block of internal keys, reading the last entry with an iterator (a single entry with the default index_block_restart_interval of 1);
* for an index block of user keys, nothing: its prefix was computed from user key bytes.

The result is a new Block flag. Block's flags are now bit-fields so that sizeof(Block), allocated for every cached block, stays 96 bytes (one more bool would have made it 104).

Two other approaches to reading existing blocks were considered:
* Handling affected blocks within the prefix-stripped comparisons, as D126805261 did, adds work to every (reverse-)bytewise seek: 63 to 98 more instructions per block seek, and up to 12x slower seeks for reverse bytewise targets that sort outside a block's prefix.
* Rejecting affected blocks as corruption would keep the seek code unchanged. But reads that work today, such as lookups of other keys and most scans and compactions, would then fail. That includes the compactions by a fixed version that would rewrite the affected files without the problem (compaction by an unfixed version can write the same layout again).

### Bundled optimization: comparing without virtual calls
The reader fix needs a per-iterator decision of whether to use the prefix-optimized seek, which already requires knowing that the comparator is BytewiseComparator or ReverseBytewiseComparator. Each block iterator now records that decision, made once when it is initialized, as a PrefixOptimizedSeek value (none, bytewise, or reverse bytewise). Previously, every seek compared the comparator with BytewiseComparator() and ReverseBytewiseComparator() (out-of-line calls), and then compared keys through InternalKeyComparator and the virtual Comparator::Compare(), although the order was known to be bytewise or reverse bytewise.

Because the same value tells which of the two orders applies, the prefix-optimized seek now compares keys directly (BlockIter::CompareKeyForPrefixOptimizedSeek(): a byte comparison of the user key parts, negated for reverse bytewise, then the internal key footer, with the file's global sequence number applied as in CompareKey()). It still counts user_key_comparison_count.

This is bundled, rather than a separate change, so that the fix "pays as it goes": the reader fix alone added a small cost to seeks (and grew Block until the bit-field change), while this optimization reuses the state the fix introduces and more than offsets that cost in most measurements (below).

Pull Request resolved: https://github.com/meta/rocksdb/pull/15556

Test Plan:
## Unit Tests
New tests in db_etc3_test, all using ReverseBytewiseComparator and format_version=8. A test sync point in BlockBuilder restores the old prefix computation so that tests can write affected blocks. A sync point at detection lets tests confirm that affected blocks were detected.
* CommonKeyPrefixWithShorterKeyAfterLongerKey: the fixed writer with Put and Delete forms of the problematic key order; no block is detected as affected.
* CommonKeyPrefixReadsBlocksWithShorterKey: Get, MultiGet, Seek and SeekForPrev on a data block whose stored prefix extends past a user key, before and after a compaction with two subcompactions.
* CommonKeyPrefixIteratesBlocksWithShorterKey: forward and reverse scans, with and without a snapshot, that seek internally into such a block.
* CommonKeyPrefixIndexBlockWithShorterKey: an affected index block of internal keys.
* CommonKeyPrefixRandomizedReverse: random DBs whose user keys often extend each other, written with the old or new prefix computation and with varied block sizes, restart intervals, index types (including partitioned, with partitioned Bloom filters), separated KV storage, data block hash index, block_protection_bytes_per_key, cache_index_and_filter_blocks, prepopulate_block_cache (with the new writer), and snapshots, sometimes including an ingested file with a global sequence number, checked against a model before and after compaction. With the new writer, it also checks that no block is flagged for the full-key search.

I confirmed that the last four tests fail with the BlockBuilder change but without the reader changes, with missing or wrong results or debug assertion failures. The randomized test also fails without the filter partition index check (debug assertion in the comparison) and if blocks are checked while building a table (index blocks of user keys flagged). The direct comparisons are also covered by existing tests of format_version=8 tables and ingested files (e.g. table_test, block_based_table_reader_test, external_sst_file_test).

## Performance
Release builds from GCC 11 and clang 21, each with the default (-march=haswell) and with PORTABLE=0 (-march=native, here znver3 or newer); single thread pinned to one CPU; interleaved runs; median of paired time ratios vs. base (lower is better); user-space instructions per operation.

Block seeks (4KB blocks, 14-byte common prefix, 92 keys per data block, 128 entries per index block; ranges are over the two builds per compiler). "Re-initialized" means the block iterator is initialized before each seek, as for each block that a point lookup visits.

| Block seek | GCC: instructions, time | clang: instructions, time |
|---|---|---|
| Index seek | +49 to +50, 0.989 to 1.003 | -83, 0.974 |
| Index seek, re-initialized | +67 to +68, 0.997 to 1.009 | -38, 0.978 to 1.006 |
| Data seek | -241 to -259, 0.936 to 0.940 | -250, 0.913 to 0.926 |
| Data seek, re-initialized | -221 to -241, 0.946 to 0.956 | -206, 0.933 to 0.952 |
| Data SeekForPrev | -344 to -369, 0.925 to 0.941 | -290, 0.934 to 0.944 |
| Reverse bytewise index seek, re-initialized | +58 to +59, 1.003 to 1.009 | -45, 0.998 to 1.002 |
| Reverse bytewise data seek, re-initialized | -227 to -247, 0.944 to 0.969 | -216, 0.936 to 0.952 |

With GCC, the direct comparison is inlined into data block seeks but called out of line (three call sites) from IndexBlockIter::SeekImpl(), hence the small instruction increase there, with no measurable time change.

db_bench (10M entries, 16-byte keys, 100-byte values, fully cached), time:

| db_bench | GCC | clang |
|---|---|---|
| readrandom, bytewise | 0.975 to 1.013 | 1.001 |
| readrandom, reverse bytewise | 0.985 to 0.986 | 0.995 to 1.006 |
| seekrandom, bytewise | 1.007 to 1.018 | 0.980 to 0.983 |
| seekrandom, reverse bytewise | 1.005 to 1.023 | 0.971 to 0.973 |

Per operation, readrandom ran 47 to 81 fewer instructions with GCC and 261 to 275 fewer with clang; seekrandom ran 12 to 81 fewer with GCC and 188 to 315 fewer with clang.

With GCC, seekrandom (a new DB iterator per operation) was 0.3% to 3.4% slower than base across repeated runs (median about 1.8%), while running fewer instructions; with clang it was 2-3% faster. GCC seekrandom is front-end bound, with about 1300 L1 instruction cache misses per operation, and with GCC this change (and earlier versions of it, without the bundled optimization) adds 5-6% to those misses. Shifting code by 16 bytes to 3 KB left each build's miss count unchanged, and this change's hot functions are no larger in total than base's. So the GCC seekrandom difference is not from added work. It looks like an effect of GCC code generation and layout: a change with no behavior change, adding an unused field to BlockIter, moved base's misses by +3% (and its seekrandom time by -0.8%), though this change's effect is somewhat larger.

Parsing a 4KB data block on load (excluding I/O, checksum verification, decompression, and cache insertion), GCC default build: +8 instructions with bytewise (no check); with reverse bytewise, +415 instructions, time 1.194 (about +37 ns) at block_restart_interval=16 and +145 instructions, time 1.049 at block_restart_interval=4.

Reviewed By: xingbowang

Differential Revision: D129007823

Pulled By: pdillinger

fbshipit-source-id: d9ffa16ed31384dbd8fd5f883b5080b986f7539e
2026-11-02 10:55:17 -08:00

135 lines
5.9 KiB
C++
Raw Permalink Blame History

// Copyright (c) Meta Platforms, Inc. and affiliates.
// This source code is licensed under both the GPLv2 (found in the
// COPYING file in the root directory) and Apache 2.0 License
// (found in the LICENSE.Apache file in the root directory).
#include "table/block_based/block_cache.h"
#include "table/block_based/block_based_table_reader.h"
namespace ROCKSDB_NAMESPACE {
void BlockCreateContext::Create(std::unique_ptr<Block_kData>* parsed_out,
BlockContents&& block) {
parsed_out->reset(new Block_kData(std::move(block),
table_options->read_amp_bytes_per_bit,
statistics, data_block_restart_interval));
parsed_out->get()->InitializeDataBlockProtectionInfo(protection_bytes_per_key,
raw_ucmp);
if (check_common_prefix) {
parsed_out->get()->InitializeDataBlockCommonPrefixCheck();
}
}
void BlockCreateContext::Create(std::unique_ptr<Block_kIndex>* parsed_out,
BlockContents&& block) {
parsed_out->reset(new Block_kIndex(std::move(block),
/*read_amp_bytes_per_bit*/ 0, statistics,
index_block_restart_interval));
parsed_out->get()->InitializeIndexBlockProtectionInfo(
protection_bytes_per_key, raw_ucmp, index_value_is_full,
index_has_first_key, index_value_delta_escape);
if (check_common_prefix) {
parsed_out->get()->InitializeIndexBlockCommonPrefixCheck(
raw_ucmp, index_key_includes_seq, index_value_is_full,
index_has_first_key, index_value_delta_escape);
}
}
void BlockCreateContext::Create(
std::unique_ptr<Block_kFilterPartitionIndex>* parsed_out,
BlockContents&& block) {
parsed_out->reset(new Block_kFilterPartitionIndex(
std::move(block), /*read_amp_bytes_per_bit*/ 0, statistics,
index_block_restart_interval));
parsed_out->get()->InitializeIndexBlockProtectionInfo(
protection_bytes_per_key, raw_ucmp, index_value_is_full,
index_has_first_key, index_value_delta_escape);
if (check_common_prefix) {
// Same iterator parameters as
// PartitionedFilterBlockReader::NewFilterPartitionIndexIterator().
parsed_out->get()->InitializeIndexBlockCommonPrefixCheck(
raw_ucmp, index_key_includes_seq, index_value_is_full,
/*index_has_first_key=*/false, index_value_delta_escape);
}
}
void BlockCreateContext::Create(
std::unique_ptr<Block_kRangeDeletion>* parsed_out, BlockContents&& block) {
parsed_out->reset(new Block_kRangeDeletion(
std::move(block), /*read_amp_bytes_per_bit*/ 0, statistics));
}
void BlockCreateContext::Create(std::unique_ptr<Block_kMetaIndex>* parsed_out,
BlockContents&& block) {
parsed_out->reset(new Block_kMetaIndex(
std::move(block), /*read_amp_bytes_per_bit*/ 0, statistics));
parsed_out->get()->InitializeMetaIndexBlockProtectionInfo(
protection_bytes_per_key);
}
void BlockCreateContext::Create(
std::unique_ptr<Block_kUserDefinedIndex>* parsed_out,
BlockContents&& block) {
parsed_out->reset(new Block_kUserDefinedIndex(std::move(block)));
}
void BlockCreateContext::Create(
std::unique_ptr<ParsedFullFilterBlock>* parsed_out, BlockContents&& block) {
parsed_out->reset(new ParsedFullFilterBlock(
table_options->filter_policy.get(), std::move(block)));
}
void BlockCreateContext::Create(std::unique_ptr<DecompressorDict>* parsed_out,
BlockContents&& block) {
parsed_out->reset(new DecompressorDict(
block.data, std::move(block.allocation), *decompressor));
}
namespace {
// For getting SecondaryCache-compatible helpers from a BlockType. This is
// useful for accessing block cache in untyped contexts, such as for generic
// cache warming in table builder.
const std::array<const Cache::CacheItemHelper*,
static_cast<unsigned>(BlockType::kInvalid) + 1>
kCacheItemFullHelperForBlockType{{
BlockCacheInterface<Block_kData>::GetFullHelper(),
BlockCacheInterface<ParsedFullFilterBlock>::GetFullHelper(),
BlockCacheInterface<Block_kFilterPartitionIndex>::GetFullHelper(),
nullptr, // kProperties
BlockCacheInterface<DecompressorDict>::GetFullHelper(),
BlockCacheInterface<Block_kRangeDeletion>::GetFullHelper(),
nullptr, // kHashIndexPrefixes
nullptr, // kHashIndexMetadata
nullptr, // kMetaIndex (not yet stored in block cache)
BlockCacheInterface<Block_kIndex>::GetFullHelper(),
BlockCacheInterface<Block_kUserDefinedIndex>::GetFullHelper(),
nullptr, // kInvalid
}};
// For getting basic helpers from a BlockType (no SecondaryCache support)
const std::array<const Cache::CacheItemHelper*,
static_cast<unsigned>(BlockType::kInvalid) + 1>
kCacheItemBasicHelperForBlockType{{
BlockCacheInterface<Block_kData>::GetBasicHelper(),
BlockCacheInterface<ParsedFullFilterBlock>::GetBasicHelper(),
BlockCacheInterface<Block_kFilterPartitionIndex>::GetBasicHelper(),
nullptr, // kProperties
BlockCacheInterface<DecompressorDict>::GetBasicHelper(),
BlockCacheInterface<Block_kRangeDeletion>::GetBasicHelper(),
nullptr, // kHashIndexPrefixes
nullptr, // kHashIndexMetadata
nullptr, // kMetaIndex (not yet stored in block cache)
BlockCacheInterface<Block_kIndex>::GetBasicHelper(),
BlockCacheInterface<Block_kUserDefinedIndex>::GetBasicHelper(),
nullptr, // kInvalid
}};
} // namespace
const Cache::CacheItemHelper* GetCacheItemHelper(
BlockType block_type, CacheTier lowest_used_cache_tier) {
if (lowest_used_cache_tier > CacheTier::kVolatileTier) {
return kCacheItemFullHelperForBlockType[static_cast<unsigned>(block_type)];
} else {
return kCacheItemBasicHelperForBlockType[static_cast<unsigned>(block_type)];
}
}
} // namespace ROCKSDB_NAMESPACE
View Git Blame Copy Permalink