mirror of
https://github.com/facebook/rocksdb.git
synced 2026-10-24 19:59:35 +03:00
fix_codex_review_command
1783 Commits
| Author | SHA1 | Message | Date | |
|---|---|---|---|---|
Xingbo Wang
|
cbd61a3165 |
Add parser for raw table iterator keys (#14726)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14726 Add SstFileReader::ParseTableIteratorKey() so callers of NewTableIterator() have a public way to decode raw table keys without duplicating RocksDB internal-key layout. The implementation delegates to the existing public ParsedEntryInfo parser using the reader comparator. Reviewed By: pdillinger Differential Revision: D104584393 fbshipit-source-id: 98e21c4d6676fbba69e533376b3da67539dd8fad |
||
|
Xingbo Wang
|
4707775ae9 |
Fix GetContext status propagation and blob-backed wide-column merge operands (#14640)
Summary: - propagate lower-level read and merge failures through `GetContext` via `read_status`, so `Get` and `GetEntity` preserve the original error instead of synthesizing `Corruption` when blob-backed reads or merge resolution fail - teach `GetMergeOperands` to resolve blob-backed default columns from wide-column entities, covering both the direct base-value path and the merge-plus-base path - add regression coverage for blob-read IO errors during `Get`/`GetEntity` merge resolution and for `GetMergeOperands` on blob-backed wide-column entities - fix the `DBFlushTest.MemPurgeCorrectLogNumberAndSSTFileCreation` test race by waiting for flush callbacks and cleaning up sync points ## Testing - `make db_blob_basic_test -j14` - `/usr/bin/perl -e 'alarm shift; exec ARGV' 60 ./db_blob_basic_test --gtest_filter='DBBlobBasicTest/DBBlobBasicIOErrorTest.GetBlob_IOError/*:DBBlobBasicTest/DBBlobBasicIOErrorTest.GetEntityMergeWithBlobBaseIOError/*'` ## Task T265824017, T265415808 Pull Request resolved: https://github.com/facebook/rocksdb/pull/14640 Reviewed By: anand1976 Differential Revision: D101690700 Pulled By: xingbowang fbshipit-source-id: 2b6fc357b37a01efa72a2d54dcff55be8992f42a |
||
Peter Dillinger
|
795f3bd61f |
Fix check-sources.sh non-ASCII check and remove non-ASCII from sources (#14729)
Summary: The non-ASCII character check in check-sources.sh used git grep -P (Perl regex), which requires git compiled with PCRE support. On systems without it, the command fails with exit code 128, which is != 1 (no match), so the check always reported a violation -- effectively dead. Even in CI where git has PCRE2 support, the check was silently broken: git grep -P uses PCRE2 in UTF mode by default, which interprets [\x80-\xFF] as a Unicode codepoint range (U+0080 to U+00FF). Characters like em-dash (U+2014), arrows (U+2192), and math symbols (U+2248, etc.) fall outside that range and were not detected. Only Latin-1 Supplement characters (U+0080-U+00FF) would have been caught. Replace with LC_ALL=C git grep using bash $'[\x80-\xff]' literal byte range, which works with basic regex in the C locale, and replace all non-ASCII characters in non-excluded source files: - em-dash to -- - arrow to -> - math symbols to ASCII equivalents (~=, <=, >=) - box-drawing characters to ASCII art Also exclude .github/ from the check, as scripts there can use non-ascii without disrupting RocksDB builds on non-UTF-8 systems. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14729 Test Plan: manual / CI (make check-sources passes clean) Reviewed By: hx235 Differential Revision: D104692574 Pulled By: pdillinger fbshipit-source-id: 1d884c21056dcd83558b825a04b867f1c08e3f45 |
||
Josh Kang
|
a4045b0a5f |
ExternalTable Iterator Prefer IterKey over InternalKey (#14695)
Summary: Reduces per-step heap allocations in the external table iterator's hot path by replacing the `InternalKey` member of `ExternalTableIteratorAdapter` with `IterKey`. `InternalKey` stores its bytes in a `std::string`, which heap-allocates whenever a key exceeds the small-string threshold. `IterKey` keeps a 39-byte inline buffer and only spills to the heap for larger keys. `UpdateKey` runs on every `Next` / `Prev` / `Seek*`, so this swap removes a recurring per-step allocation for typical key sizes. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14695 Test Plan: CI Reviewed By: anand1976 Differential Revision: D103440780 Pulled By: joshkang97 fbshipit-source-id: deb0a8ea04110e3dff0a1bcad767e7136192fdc6 |
||
anand76
|
c1dbe0a6ac |
Disable MultiScanAsyncIOTest.MultiScanPrepare test (#14707)
Summary: This test is failing in CI. Disable until root caused. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14707 Reviewed By: mszeszko-meta Differential Revision: D103888323 Pulled By: anand1976 fbshipit-source-id: d2639ddda10a8caa2f36ae2ba529d65cb8bd2ea9 |
||
|
Josh Kang
|
a12bd7d641 |
ExternalTable support FS (#14629)
Summary: Extends the `ExternalTable` plug-in interface so external table implementations have access to the same `FileSystem` RocksDB itself uses. Previously only `ExternalTableOptions` (read path) had `fs`. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14629 Test Plan: - Existing tests pass Reviewed By: anand1976 Differential Revision: D101384103 Pulled By: joshkang97 fbshipit-source-id: cade6f4699337e07bdd4875d070f629058fd6795 |
||
|
Peter Dillinger
|
b3b7668bf5 |
Convert some ROCKSDB_GTEST_SKIP to BYPASS (#14679)
Summary: Fix false internal warnings about skipped tests (seen on D102718613). ROCKSDB_GTEST_SKIP signals a gap in test coverage due to the build/execution environment, while ROCKSDB_GTEST_BYPASS is for intentionally and permanently omitting certain parameterizations. These six tests skip based on the test parameterization (forward vs reverse, primary vs secondary mode), not due to any environment limitation, so BYPASS is the correct macro. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14679 Test Plan: these are tests, look at internal signals Reviewed By: joshkang97 Differential Revision: D102833346 Pulled By: pdillinger fbshipit-source-id: e57bd1e217ca63aaf418b68c788563e67bbb07e3 |
||
|
Josh Kang
|
b12d3a6da6 |
External Table Get Optimizations (#14673)
Summary: - External Table is only PUTs with no seqno, so we can route it to the simpler more efficient `GetContext::SaveValue`. - `SstFileReader::Get` was allocating a string to append key footer, instead use LookUpKey to allocate on stack for short keys. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14673 Test Plan: CI passes Reviewed By: anand1976 Differential Revision: D102659533 Pulled By: joshkang97 fbshipit-source-id: e55127548c9e4b7bdeb63c46acfdb8eb5883db14 |
||
Yoshinori Matsunobu
|
3cdf942192 |
Make ParseCompressionNameForDisplay manager-aware (#14658)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14658 Follow up to D101463511. Add a hook and a manager-aware overload of so custom CompressionManagers can provide human-readable names for custom compression types while preserving the existing generic fallback when no compatible manager is available. Reviewed By: pdillinger Differential Revision: D102201365 fbshipit-source-id: 0c7456bb9db2e54927a4349d12c035fc8b5ad562 |
||
|
Yoshinori Matsunobu
|
763401b595 |
Add ParseCompressionNameForDisplay API (#14637)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14637 Add public API ParseCompressionNameForDisplay() to render TableProperties::compression_name in human-readable form for both legacy and format_version >= 7 SST metadata, including BuiltinV2/compression-manager encodings and filtered no-compression markers for display. Reviewed By: xingbowang Differential Revision: D101463511 fbshipit-source-id: 51c44850183cb9757644a323376844adffc7a8c2 |
||
Anand Ananthabhotla
|
b374ba5968 |
Rocksdb Unit Test failed: Unit test failed (#14643)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14643 Reviewed By: xingbowang Differential Revision: D101559659 fbshipit-source-id: 56d405f36bfe83c009053796c0d065f4032522b1 |
||
Andrew Chang
|
3ef8b1b743 |
Guard auto-readahead against exhausted index iter (#14631)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14631 Observed crash from ZippyDB iterate scans: ``` onFatalError: unexpected error : Invariant SignalFatal: fbcode/zippydb/server/Main.cpp:handleSigToFatalCommon:281:FATAL false failed: Signal 11 (SIGSEGV) at address 0x0 ... method: MultiIterate ... RocksDB Activity: iterate ``` Key stack frames: rocksdb::BlockBasedTableIterator::IsNextBlockOutOfReadaheadBound() fbcode/rocksdb/src/table/block_based/block_based_table_iterator.h:471 rocksdb::BlockBasedTableIterator::BlockCacheLookupForReadAheadSize() fbcode/rocksdb/src/table/block_based/block_based_table_iterator.cc:878 rocksdb::FinalizeAsyncRead() rocksdb::FilePrefetchBuffer::PollIfNeeded() rocksdb::BlockFetcher::ReadBlockContents() rocksdb::BlockBasedTableIterator::InitDataBlock() rocksdb::DBIter::Next() Reviewed By: xingbowang Differential Revision: D101217429 fbshipit-source-id: e7657909a0f07526d070b214cb783f581b8e98ca |
||
|
Peter Dillinger
|
9f474a1034 |
Enforce < 4GB sizes for keys, values, and some BlockBuilder inputs (#14461)
Summary: BlockBuilder was somewhat inconsistent in its treatment of Slices whose size exceeds 4GB, which in a random corruption case could lead to (for example) serializing only the bottom 32 bits of a value size (uncorrupted) but appending the full multi-GB (corrupted) size. Because this is inner loop code, we don't want to pay CPU for extra conversions, data movements, or Status plumbing (already ruled out by Xingbo). In this change we make BlockBuilder more internally consistent and lift the 32-bit size requirement to callers (of a few functions specifically, for now). To ensure that's satisfied, I've added additional checks near the perimeter of RocksDB to ensure keys and values do not exceed 4GB, plus an extra random corruption or backstop check in BlockBasedTableBuilder. In detail, BlockBuilder (block_builder.cc/h): * Add API comments documenting the < 4GB assumption on Add/AddWithLastKey * Add debug assertions verifying input slice sizes < 4GB * Simplify AddWithLastKeyImpl to use uint32_t locals, reducing static_cast * Use only bottom 32 bits when appending derivative slices for consistency * Update MaybeStripTimestampFromKey to also truncate to 32-bit size * Add FIXME comments where buffer_/values_buffer_ sizes are truncated BlockBasedTableBuilder (block_based_table_builder.cc): * Add value size check (> uint32_t max) as a safety net against random corruption, since we have seen such corruptions in production WriteBatch (write_batch.cc): * Tighten existing key size checks to account for kNumInternalBytes (8-byte internal key suffix), using new kMaxWriteBatchKeySize constant * Add missing size checks to Delete, SingleDelete, and DeleteRange (both Slice and SliceParts variants) SstFileWriter (sst_file_writer.cc): * Add key and value size checks in AddImpl and DeleteRangeImpl, which bypass WriteBatch and go directly to the table builder MergeHelper (merge_helper.cc): * Add merge result size check (> uint32_t max) in both overloads of TimedFullMergeImpl, returning Corruption if exceeded * Add PartialMergeMulti result size check in MergeUntil CompactionIterator (compaction_iterator.cc): * Add size check on compaction filter output values (kChangeValue and kChangeWideColumnEntity), returning Corruption if > 4GB meta_blocks.cc: * Use Slice with uint32_t-truncated sizes in PropertyBlockBuilder::Finish to handle potentially oversized user property collector output Needed follow-up: * Check for blocks that are mis-encoded due to overflowing 32 bits for restart point offsets (and similar). See FIXME comments in block_builder.cc for why this is tricky. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14461 Test Plan: New extreme-size unit tests, along with some testing infrastructure improvements: Added test::HasBigMem() (in test_util/testharness.h) which returns true when the system has ≥128GB RAM (via sysconf(_SC_PHYS_PAGES) on Linux/macOS) or when ROCKSDB_BIGMEM_TESTS is set. All extreme-size tests use HasBigMem() to skip gracefully on smaller machines rather than being permanently disabled. Where possible, tests use MemMapping::AllocateLazyZeroed() to supply large keys/values as Slices backed by anonymous mmap (cleaner with new MemMapping::AsSlice()). On Linux, read-only access to these pages maps to the shared kernel zero page, so the source data consumes no physical RAM — only the destination copy (e.g., WriteBatch::rep_) materializes, cutting peak memory roughly in half vs. std::string. Tests (all enabled, skip via HasBigMem()): ./write_batch_test --gtest_filter='*LargeKeyValueSizeLimit*' ./external_sst_file_basic_test --gtest_filter='*LargeSizeSstFileWriter*' ./merge_test --gtest_filter='*LargeMergeResultRejected*' ./merge_helper_test --gtest_filter='*LargePartialMergeResultRejected*' ./db_compaction_test --gtest_filter='*CompactionFilterLargeValueRejected*' All 5 pass (verified on a 128GB+ machine). On smaller machines, all 5 bypass cleanly with "insufficient memory for reliable continuous testing". Reviewed By: xingbowang Differential Revision: D96521899 Pulled By: pdillinger fbshipit-source-id: 70f4b5e6a23ab074d60e653fbb7ddc5edbe162ab |
||
|
Peter Dillinger
|
b7395b3fa4 |
Allow Compressor to override parallel_threads for SST building (#14580)
Summary:
Add Compressor::GetRecommendedParallelThreads() virtual method so that the compression subsystem can influence the parallel compression thread count used when building SST files. The base Compressor returns 0 (no opinion), while built-in compressors (via CompressorBase) return the parallel_threads value from their CompressionOptions. This gives CompressionManager a clean mechanism to override parallel_threads by customizing the CompressionOptions passed to GetCompressor() in its GetCompressorForSST() implementation.
The table builder now reads the thread count from the compressor after creation, rather than only from CompressionOptions directly. Hard structural constraints (partition_filters without decoupled mode, user_defined_index_factory) still force single-threaded compression regardless of the compressor's recommendation.
Also adds a sync point in MaybeStartParallelCompression for test observability, and compression_test coverage for the new functionality.
Bonus: extends CompressionManagerCustomCompression test to cover re-opening a DB at format_version=7 with a non-default compression manager that uses the built-in CompatibilityName ("BuiltinV2"). Verifies that data is readable after re-opening without the original manager, and that neither GetId() nor CompatibilityName() resolves to the custom manager via CreateFromString.
Pull Request resolved: https://github.com/facebook/rocksdb/pull/14580
Test Plan:
New unit tests in compression_test:
- GetRecommendedParallelThreads: verifies built-in compressors return the parallel_threads from their CompressionOptions for all supported compression types.
- CompressionManagerOverridesParallelThreads: end-to-end test with a custom CompressionManager that overrides parallel_threads from 1 to 4 in GetCompressorForSST, verified via sync point that parallel compression actually activates with the overridden thread count, plus data readback verification.
Existing parallel compression tests (DBCompressionTestMaybeParallel) continue to pass.
Reviewed By: xingbowang
Differential Revision: D99896343
Pulled By: pdillinger
fbshipit-source-id: 6b3a30856a78641714d33ec7ba2099f33533d3af
|
||
zaidoon
|
3b38fde293 |
Support UDI as primary index (#14547)
Summary: Add `use_udi_as_primary_index` option to `BlockBasedTableOptions`. When enabled, the UDI becomes the primary index — all reads (including internal operations like compaction and VerifyChecksum) automatically route through the UDI without needing `ReadOptions::table_index_factory`. Both the standard binary search index and the UDI are always fully built. The standard index serves as a safety fallback (e.g., for backup/restore or rollback to a non-UDI configuration). A future refactor will extract the index abstraction to allow skipping the standard index build when the UDI is primary (see discussion below). ## Write path - `UserDefinedIndexBuilderWrapper` always forwards `AddIndexEntry` and `OnKeyAdded` to both the internal standard builder and the UDI builder - New `udi_is_primary_index` table property marks primary-mode SSTs - Validates incompatible options at `DB::Open` and builder creation: partitioned index, partitioned filters, missing `user_defined_index_factory` ## Read path - `UserDefinedIndexReaderWrapper` defaults to UDI when `udi_is_primary_`, even when `ReadOptions::table_index_factory` is null — this handles the 15+ internal call sites that don't set `table_index_factory` - `use_udi_as_primary_index` automatically enforces `fail_if_no_udi_on_open` to prevent silent data loss if SSTs are opened without UDI support ## Rollback Since the standard index is always fully populated, rollback from primary mode is straightforward: set `use_udi_as_primary_index=false`. No compaction required — SSTs written in primary mode are immediately readable through the standard index. ## Public API - `BlockBasedTableOptions::use_udi_as_primary_index` (default: false) - `UserDefinedIndexBuilder::EstimatedSize()` — pure virtual, O(1) via running counter in the trie implementation ## Bug fixes (issues https://github.com/facebook/rocksdb/issues/14560, https://github.com/facebook/rocksdb/issues/14561, https://github.com/facebook/rocksdb/issues/14562) Fixed trie index correctness bugs that caused crash test failures: - **Always-on seqno encoding**: `must_use_separator_with_seq_` is now unconditionally true. Non-boundary separators store tag=0 (sentinel), same-user-key boundaries store the real tag, and the last block stores its real last-key tag. This fixes the `NonBoundaryTag` bug where non-boundary separators with `kMaxSequenceNumber` caused the post-seek correction to incorrectly advance past the correct block. - **Standard index always built in primary mode**: An empty (stub) standard index block caused behavioral divergence in `BlockBasedTableIterator` under concurrent flush/compaction, leading to `test_batches_snapshots` prefix scan inconsistencies. ## Stress test - `use_udi_as_primary_index` flag randomized by `db_crashtest.py` - Both primary and secondary UDI modes exercised in crash tests - Trie index probability halved (~6%) per reviewer request - Re-enables trie crash tests (disabled by https://github.com/facebook/rocksdb/issues/14559) ## Tests - Parameterized `TrieIndexDBTest` on UDI mode (secondary vs primary) - New factory-level tests: non-boundary separator seek, Prev within overflow, SeekToLast with overflow, empty trie, overflow exhaustion, all-scans-exhausted - New DB-level tests: multi-CF coalescing iterator, GetEntity with explicit snapshot, reverse iteration across same-user-key blocks, non-boundary separator seek correctness, rollback from primary Pull Request resolved: https://github.com/facebook/rocksdb/pull/14547 Reviewed By: anand1976 Differential Revision: D99494181 Pulled By: xingbowang fbshipit-source-id: ca52a0d5c0e523770c80e1fe2b9b5d50406b67bc |
||
|
Xingbo Wang
|
3070f73e97 |
Wide-column blob separation: lazy resolution through read, compaction, and write paths (#14386)
Summary: Wide-column blob separation: lazy resolution through read, compaction, and write paths Extend blob direct write to support wide-column entities (PutEntity), and add lazy blob resolution for wide-column values across all read and compaction paths. **Write path -- PutEntity blob separation:** - BlobWriteBatchTransformer::PutEntityCF now extracts large column values (>= min_blob_size) to blob files and serializes V2 entities with BlobIndex references, matching the existing Put behavior. - Add MaybePreprocessWideColumns() static helper to share blob extraction logic between the WriteBatch transformer and the new PutEntity fast path. - Add PutEntityFastPath() in DBImpl that preprocesses columns (sort, blob extract, serialize) before calling WriteImpl, skipping the redundant WriteBatch transformation pass. Trace batch preserves the original columns. **Read path -- blob resolution for Get/MultiGet/Iterator:** - GetContext::SaveValue resolves V2 entity blob columns eagerly: for value (Get), resolves the default column's blob reference; for columns (GetEntity), resolves all blob columns and re-serializes as V1. - DBIter::SetValueAndColumnsFromEntity detects V2 entities, deserializes with DeserializeV2, and eagerly resolves all blob columns via a new ReadPathBlobResolver. Resolved values are cached in the resolver and wide_columns_ Slices point into the cache, avoiding copies. - Add ReadPathBlobResolver (new file) -- on-demand blob fetcher for the read path with per-column caching, used by both DBIter and GetContext. - BlobFetcher gains allow_write_path_fallback to read from in-flight direct-write blob files not yet visible through Version (pre-flush reads). - Memtable lookups for Get(key) on V2 entities with a blob default column now return the blob index with is_blob_index=true, triggering the existing BDW resolution in MaybeResolveWritePathValue. - MaybeResolveWritePathValue (renamed from MaybeResolveDirectWriteBlobIndex) now also resolves V2 entity blob columns for GetEntity/MultiGetEntity, re-serializing as V1 after resolution. **Compaction path -- filter, GC, and extraction:** - CompactionIterator::InvokeFilterIfNeeded handles V2 entities: FilterV3 gets eagerly-resolved column values for backward compatibility; FilterV4 gets a CompactionBlobResolver for lazy on-demand resolution. - Add CompactionFilter::FilterV4 with WideColumnBlobResolver* parameter and SupportsFilterV4() opt-in. Default delegates to FilterV3. - CompactionBlobResolver (new class) implements WideColumnBlobResolver for the compaction path with stats tracking. - ExtractLargeColumnValuesIfNeeded extracts inline columns to blob files during compaction (entities without existing blob columns only). - GarbageCollectEntityBlobsIfNeeded relocates blob values from old blob files to new ones during compaction GC, with helpers FetchBlobsNeedingGC, RelocateBlobValues, and SerializeEntityAfterGC. - PrepareOutput unified entity deserialization: single DeserializeV2 call reused by both filter and GC/extraction paths via entity_deserialized_ flag, avoiding redundant parsing. **Merge path -- V2 entity base value resolution:** - MergeHelper::MergeUntil, GetContext::MergeWithWideColumnBaseValue, and DBIter::MergeWithWideColumnBaseValue resolve V2 blob columns before calling TimedFullMerge, using ResolveEntityForMerge. **Blob garbage accounting:** - BlobGarbageMeter tracks blob file in/out flow for V2 entity blob columns via ForEachBlobFileNumber, used for accurate GC decisions. - FileMetaData::UpdateBoundaries tracks oldest_blob_file_number for V2 entities, ensuring blob files referenced by entities are not prematurely deleted. **Serialization improvements:** - WideColumnSerialization::SerializeV2Impl allocates serialized_blob_indices only for actual blob columns (not all columns) and uses autovector for name/value sizes. - Add ForEachBlobFileNumber for lightweight blob file number extraction without full deserialization. - Add ResolveEntityForMerge helper for merge-path resolution. - Add section-size validation in DeserializeV2Impl. - Add empty blob index and column type validation. - blob_column_resolver_util.h -- shared helpers (FindBlobColumn, FindInCache, CacheInlinedBlob) used by both ReadPathBlobResolver and CompactionBlobResolver. **Testing:** - db_blob_direct_write_test: end-to-end PutEntity with BDW before/after flush, verifying Get, GetEntity, MultiGetEntity, and Iterator. - db_blob_index_test: ~1550 lines covering V2 entity blob resolution through Get, GetEntity, MultiGet, Iterator, compaction filter (V3 compat and V4 lazy), merge with blob base, and compaction GC/extraction. - compaction_iterator_test: ~950 lines testing entity blob GC, extraction, filter interaction, and combined GC+filter scenarios. - db_wide_basic_test: ~1200 lines for wide-column lazy blob resolution through all read paths plus compaction round-trips. - db_open_with_config_test: ~450 lines for BDW entity config validation. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14386 Reviewed By: anand1976 Differential Revision: D99739701 Pulled By: xingbowang fbshipit-source-id: 6badd89b577f3054802eaaa654738468efb9dbdb |
||
|
Anand Ananthabhotla
|
9d609dd6fe |
Fix MultiScanIndexIterator crash on reseek after exhaustion (#14581)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14581 In `MultiScanIndexIterator::Seek()` Case 3, when re-entering a scan range after all ranges were exhausted, `block_idx = std::max(cur_scan_start_idx, cur_idx_)` could produce an out-of-bounds value because `cur_idx_` was left at `block_handles_.size()` from previous exhaustion. `SeekToBlockIdx()` unconditionally set `valid_ = true` without checking bounds, causing the subsequent `value()` call to hit the assertion `cur_idx_ < block_handles_.size()`. Added bounds check before `SeekToBlockIdx()` in Case 3 to correctly report exhaustion instead of crashing. Reviewed By: joshkang97 Differential Revision: D99604049 fbshipit-source-id: 9d5d91afde7c0984a7b4c2f62604f27f19b07922 |
||
Jialiang Tan
|
65e77282ce |
Add block_decompress_count to PerfContext (#14557)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14557 RocksDB's PerfContext tracks block_decompress_time but has no counter for the number of block decompressions. The global Statistics ticker NUMBER_BLOCK_DECOMPRESSED exists but is not accessible through PerfContext, which is the thread-local, per-operation metric system used by benchmarks. Add block_decompress_count as a new PerfContext counter (gated at kEnableCount level) incremented in DecompressBlockData alongside the existing NUMBER_BLOCK_DECOMPRESSED ticker. This enables benchmarks and applications to observe how many blocks required decompression per operation, complementing the existing block_read_count. Reviewed By: anand1976 Differential Revision: D99233514 fbshipit-source-id: 40a68c1d9321f560cebdb7c30a544a0c62ae64f0 |
||
|
Jialiang Tan
|
a0ff5b143f |
Add num_data_blocks_compression_rejected/bypassed to TableProperties (#14551)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14551 Add two new per-SST TableProperties fields that track how many data blocks were stored uncompressed: - `num_data_blocks_compression_rejected`: blocks where compression was attempted but the compressed output exceeded the ratio limit set by `CompressionOptions::max_compressed_bytes_per_kb`. - `num_data_blocks_compression_bypassed`: blocks where compression was never attempted (e.g., kNoCompression type, no compressor available). Together with `num_data_blocks`, these give a full decomposition: num_data_blocks = compressed + rejected + bypassed Previously this information was only available via global Statistics tickers (NUMBER_BLOCK_COMPRESSION_REJECTED / BYPASSED) which aggregate across all SSTs. Now it is persisted per-SST in the properties block and visible via sst_dump --show_properties. Reviewed By: anand1976 Differential Revision: D99229339 fbshipit-source-id: 8333f51acff30a759d725e5e94bd80f4fcb18b57 |
||
|
zaidoon
|
41e5eb1a4d |
Support reverse iteration in UDI/trie index and optimize hot paths (#14466)
Summary: The following performance optimizations are included in this PR: - Inline NextSetBit/PrevSetBit into header (called on every trie level) - Unroll Rank1 popcount loop (the single hottest function) - Advance/Retreat: replace path stack top in-place instead of pop+push - std::swap for prev_key_scratch_ instead of O(n) string copy - assign() instead of ToString() to reuse buffer capacity - Cache IndexValue in wrapper to avoid repeated virtual dispatch - Mark TrieIndexIterator/TrieIndexBuilder as final for devirtualization Part of https://github.com/facebook/rocksdb/issues/12396 Pull Request resolved: https://github.com/facebook/rocksdb/pull/14466 Reviewed By: anand1976 Differential Revision: D97979699 Pulled By: xingbowang fbshipit-source-id: 7ec56ecc8b6d68548a336dd1aaccfb215189eff0 |
||
|
Josh Kang
|
f897c1b2ef |
Add uniform block tracking stats (#14513)
Summary: Add tracking of uniform index blocks as a table property (`num_uniform_blocks`). When `uniform_cv_threshold` is set, the block builder detects uniformly distributed keys via coefficient of variation of key gaps. This information is now surfaced end-to-end: from block building through index builders to SST table properties. ## Key changes - **BlockBuilder**: Persist the uniformity result from `ScanForUniformity()` as a member (`is_uniform_`) exposed via `IsUniform()`, rather than a local variable discarded after `Finish()`. - **Index builders**: All three index builder types (`ShortenedIndexBuilder`, `HashIndexBuilder`, `PartitionedIndexBuilder`) implement `NumUniformIndexBlocks()`. For partitioned indexes, the count accumulates across partition `Finish()` calls. - **Table property serialization**: Added `TablePropertiesNames::kNumUniformBlocks` (`"rocksdb.num.uniform.blocks"`) with full serialization/deserialization support. Without this, the property was computed in memory but never persisted to SST files. - **Table property aggregation**: `num_uniform_blocks` included in `Add()` and `GetAggregatablePropertiesAsMap()` for correct cross-SST aggregation. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14513 Test Plan: - **Unit tests**: `block_test` (7504 passed), `table_test` (6917 passed), `table_properties_collector_test` (8 passed). - **End-to-end verification via db_bench + sst_dump**: - Positive: `./db_bench --benchmarks=fillseq,compact --num=10000 --uniform_cv_threshold=0.2 --index_shortening_mode=0 --compression_type=none` produces SST with `# uniform blocks: 1`. - Negative: Same with `--uniform_cv_threshold=-1` (disabled) produces `# uniform blocks: 0`. Reviewed By: xingbowang Differential Revision: D98343170 Pulled By: joshkang97 fbshipit-source-id: ed08e83b2dcfb70f074bfb0f7bb5c31d75dc6da9 |
||
|
Josh Kang
|
f620a6d039 |
Support Pinnable Reads In SstFileReader (#14500)
Summary: Add `SstFileReader::Get` (single-key) and `SstFileReader::MultiGet` (PinnableSlice) overloads to enable zero-copy point lookups directly from SST files. The existing `MultiGet(std::string*)` is refactored to delegate to the new `MultiGet(PinnableSlice*)`, which writes results directly into caller-provided `PinnableSlice` values instead of copying through an intermediate buffer. The single-key `Get` uses `TableReader::Get` with a `GetContext` for efficient single-key lookups without the overhead of MultiGet's sorting and batching machinery. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14500 Test Plan: - New unit tests Reviewed By: xingbowang Differential Revision: D97825648 Pulled By: joshkang97 fbshipit-source-id: 17f3edd59bbf4747d17309c44ef12f0d952ea4eb |
||
|
Josh Kang
|
304ae7190a |
Support ExternalTable PinnableSlice Get (#14497)
Summary: The ExternalTableReader `Get` API has been modified to use PinnableSlice instead of std::string, this will allow implementations to utilize zero-copy Gets (e.g. reading from mmap or a cache). This is not a compatible change, but the API is marked as experimental, so should be allowed. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14497 Test Plan: - New unit tests Reviewed By: xingbowang Differential Revision: D97782011 Pulled By: joshkang97 fbshipit-source-id: 8a9e8c5bc5ff5e8dee6c0f2ee745521f09042cef |
||
|
Yoshinori Matsunobu
|
b23fc77aca |
Add per-block-type block read byte perf counters (#14473)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14473 Add separate PerfContext byte counters for data, index, filter, compression-dictionary, and metadata block reads while preserving block_read_byte as the aggregate. Wire the new counters through the block fetch and multi-read data block paths, expose them via the C perfcontext API, and extend table tests to verify byte attribution and that the classified counters sum back to block_read_byte. Reviewed By: xingbowang Differential Revision: D97333746 fbshipit-source-id: 3411844d7fa9c76c9ff28af477b3a72a5d6e5d9b |
||
|
zaidoon
|
ec22903914 |
Support all operation types in User Defined Index (UDI) interface (#14399)
Summary: Remove the restriction that limited UDI to ingest-only, Puts-only use cases. This enables UDI plugins (including the trie index from https://github.com/facebook/rocksdb/issues/14310) to work with all operation types: Put, Delete, Merge, SingleDelete, PutEntity, etc. Part of https://github.com/facebook/rocksdb/issues/12396 Pull Request resolved: https://github.com/facebook/rocksdb/pull/14399 Reviewed By: pdillinger Differential Revision: D96392636 Pulled By: xingbowang fbshipit-source-id: 0f1e6c38531fa72539a0e2c6a3dffff333392b4c |
||
Maciej Szeszko
|
1ed5052486 |
Prepopulate block cache during compaction (#14445)
Summary:
When RocksDB operates with tiered or remote storage (e.g., Warm Storage, HDFS, S3), reading recently compacted data incurs high-latency remote reads because compaction output files are not present in the block cache. The existing `prepopulate_block_cache = kFlushOnly` avoids this for flush output but leaves compaction output cold until first access.
Add a new `PrepopulateBlockCache::kFlushAndCompaction` enum value that warms all block types (data, index, filter, compression dict) into the block cache during both flush and compaction. Flush-warmed blocks use `LOW` priority (unchanged from kFlushOnly behavior), while compaction-warmed blocks use `BOTTOM` priority — compaction data is less temporally local than freshly flushed data, so it should be the first to be evicted when the cache is full. This gives the remote-read avoidance benefit without risking cache thrashing.
The enum uses `kFlushAndCompaction` rather than separate `kCompactionOnly` + `kFlushAndCompaction` values because there is no practical use case for warming compaction output without also warming flush output. Flush output is by definition the hottest data (just written by the user), so if a workload benefits from warming the colder compaction output, it would always benefit from warming flush output too.
The implementation reuses the existing `InsertBlockInCacheHelper` / `WarmInCache` infrastructure in `BlockBasedTableBuilder`. The only internal change is adding a `warm_cache_priority` field to `Rep` alongside the existing `warm_cache` bool, and plumbing it through to the `WarmInCache` call instead of the previously hardcoded `Cache::Priority::LOW`.
### Key changes
- New `PrepopulateBlockCache::kFlushAndCompaction` enum value in table.h
- `Rep::warm_cache_priority` field in BlockBasedTableBuilder for per-reason priority control
- Serialization support ("kFlushAndCompaction" in string map)
- db_bench support (--prepopulate_block_cache=2)
- Crash test coverage (random choice includes new value)
**NOTE:** Unlike flush output (which is inherently hot — just written by the user), it is hard to distinguish hot from cold blocks in compaction output. Warming all compaction output therefore risks polluting the block cache and evicting genuinely hot entries. The kFlushAndCompaction mode is recommended only for use cases where most or all of the database is expected to reside in cache (e.g., the working set fits in cache). For workloads where only a fraction of the data is hot, kFlushOnly remains the safer choice.
Pull Request resolved: https://github.com/facebook/rocksdb/pull/14445
Test Plan:
- New `WarmCacheWithDataBlocksDuringCompaction` test: verifies data blocks from compaction output are present in the block cache and served without misses
- Extended `DynamicOptions` test: verifies dynamic switching through kDisable -> kFlushAndCompaction -> kFlushOnly -> kDisable via SetOptions
- Existing `WarmCacheWithDataBlocksDuringFlush` and parameterized `WarmCacheWithBlocksDuringFlush` tests continue to pass (kFlushOnly behavior unchanged)
- db_block_cache_test: 81/81 passed
- options_test: 74/74 passed
- table_test: 6910/6910 passed
Reviewed By: xingbowang
Differential Revision: D95997952
Pulled By: mszeszko-meta
fbshipit-source-id: 4ad568264992532053947df298e63e343821ddb5
|
||
|
Josh Kang
|
42eff8b632 |
Add new heauristic 'num_collapsible_entry_reads_sampled' (#14434)
Summary: Add per-file sampling of "collapsible" entry reads (single deletions, merges, and kNotFound results) that may later be used to help inform read-triggered compactions. This is a better metric than `num_reads_sampled` as it is more targeted towards reads that could be avoided via compaction. The existing behavior of `num_reads_sampled` is that reads only gets sampled on iterator creation for a file. It is problematic because next/prev() calls are not sampled, nor are additional seeks(). This PR moves sampling to per-seek/next granularity within `LevelIterator` and adds a new `num_collapsible_entry_reads_sampled` counter that tracks how often a file serves entries that could be eliminated by compaction. Note only L1+ files have iterator seeks/nexts/prevs sampled. Introducing this at L0 would require wrapping table reader iterators, introducing a performance cost. ## Key changes - **New counter `num_collapsible_entry_reads_sampled`** in `FileSampledStats` tracks sampled reads that encounter deletions, single deletions, merges, or kNotFound results in both Get and Iterator paths. - **Moved sampling from file-open to per-operation** in `LevelIterator`: sampling now happens in `SampleRead()` called from `Seek()`, `SeekForPrev()`, `SeekToFirst()`, `SeekToLast()`, `Next()`, `NextAndGetResult()`, and `Prev()`. The `should_sample` parameter was removed from `LevelIterator`'s constructor. - **Differentiated sampling rate for Next() vs Seek()**: `should_sample_file_read_next()` uses a 64x lower sampling rate (`kFileReadSampleRate * 64`) since Next() is cheaper than Seek() and called more frequently. - **Collapsible tracking in Get path**: `Version::Get()` now increments the collapsible counter when `GetContext::State()` is `kNotFound`, `kMerge`, or `kDeleted`. - **Collapsible tracking in MultiGet path**: `MultiGetFromSST` also increments the collapsible counter for the same states. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14434 Test Plan: - Added new DB tests for both num_reads_sampled and num_collapsible_entry_reads_sampled ### Benchmark results (readrandom, readseq) Setup: 1M keys, 16-byte keys, 100-byte values, no compression, fillrandom+compact | Benchmark | Params | ops/s (main) | ops/s (feature) | % change | |------------|--------------------|-------------|--------------------------|----------| | readrandom | seed=1, threads=1 | 387,194 | 389,449 | +0.6% | | readseq | seed=1, threads=1 | 5,598,371 | 5,572,975 | -0.5% | No meaningful performance regression observed — differences are within run-to-run noise. Reviewed By: xingbowang Differential Revision: D95613793 Pulled By: joshkang97 fbshipit-source-id: 9dd09c9b7527b148424bde5686f4157c7a9e1214 |
||
|
Josh Kang
|
3ad23b2d94 |
Support automated interpolation search (#14383)
Summary: Add automatic per-block interpolation search selection (`kAuto` mode) for index blocks. During SST construction, each index block's key distribution is analyzed using the coefficient of variation (CV) of gaps between restart-point keys. Blocks with uniformly distributed keys are flagged via a new bit in the data block footer, and at read time, `kAuto` resolves to interpolation search for uniform blocks and binary search otherwise. ## Key changes - **New `BlockSearchType::kAuto` enum value**: Resolves per-block at read time to either `kInterpolation` or `kBinary` based on the block's uniformity flag. Falls back to `kBinary` on older versions that don't recognize it. - **Write-path uniformity analysis**: `BlockBuilder::ScanForUniformity()` uses Welford's online algorithm to incrementally compute the CV of key gaps at restart points. The result is stored in a new bit (bit 30) of the data block footer's packed restart count. - **New table option `uniform_cv_threshold`** (default: -1 `disabled`): Controls how strict the uniformity check is. Set to negative to disable. Exposed in C++, Java (JNI), and `db_bench`. - **Code reorganization**: Block entry decode helpers (`DecodeEntry`, `DecodeKey`, `DecodeKeyV4`, `ReadBe64FromKey`) moved from `block.cc` to a new shared header `block_util.h` so they can be reused by `BlockBuilder` on the write path. - **New histogram `BLOCK_KEY_DISTRIBUTION_CV`**: Records the CV (scaled by 10000) of each index block's key distribution for observability. - **Java bindings**: `IndexSearchType.kAuto`, `uniformCvThreshold` getter/setter, JNI portal constructor signature updated, and `HistogramType.BLOCK_KEY_DISTRIBUTION_CV` added. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14383 Test Plan: - `IndexBlockTest.IndexValueEncodingTest` parameterized to include `kAuto` search type alongside `kBinary` and `kInterpolation`, verifying correct seek/iteration behavior across all combinations of key distributions, restart intervals, and key lengths. - Uniformity detection validated: blocks with uniform key distribution correctly set `is_uniform = true`, blocks with clustered/non-uniform keys set `is_uniform = false`. - Stress test coverage - Updated check_format_compatible to also include a "uniform" dataset. By default using uniform_cv_threshold=-1 does not result in an incompatibility issues. When manually changing the threshold (e.g. `uniform_cv_threshold=1000`), I see `bad block contents`, which is expected ## Benchmark readrandom with `fillrandom,compact -seed=1 --statistics`: | Benchmark | Branch | Params | avg ops/s | % change vs main | CV P50 | |-----------|--------|--------|-----------|------------------|--------| | readrandom | main | `binary_search, shortening=1` | 335,791 | baseline | N/A | | readrandom | feature | `binary_search, shortening=1` (default) | 335,749 | -0.0% | 1,500 | | readrandom | feature | `auto_search, shortening=1` (kAuto) | 366,832 | **+9.2%** | 1,500 | | readrandom | feature | `interpolation_search, shortening=1` | 366,598 | **+9.2%** | 1,500 | | readrandom | feature | `auto_search, shortening=2` (kAuto) | 344,631 | **+2.6%** | 1,030,000 | | readrandom | feature | `interpolation_search, shortening=2` | 201,178 | **-40.1%** | 1,030,000 | As seen with shortening=2, a non-uniform distribution produces a high CV, which does not use interpolation search. ## Write benchmark There is a write overhead which scans each restart entry for a block upon Finish. In practice this is very low because currently it is only applied to index blocks. See cpu profile (https://fburl.com/strobelight/io5hwj9h) here of `-benchmarks=fillseq,compact -compression_type=none -disable_wal=1`. Only 0.08% attributed to `ScanForUniformity`. Reviewed By: pdillinger Differential Revision: D94738890 Pulled By: joshkang97 fbshipit-source-id: 9661ac593c5fef89d49f3a8a027f1338a0c96766 |
||
|
Xingbo Wang
|
8a86620653 |
Disable more features in stress test when trie UDI is enabled (#14432)
Summary: Address 2 compatibility issue of UDI: A: Trie UDI (UserDefinedIndex) does not support SeekToFirst/SeekToLast. The crash test already disabled prefix scanning (prefixpercent=0) when use_trie_index=1, but iteration (iterpercent) was still enabled. During iteration, LevelIterator::SkipEmptyFileForward() internally calls file_iter_.SeekToFirst() when Next() crosses SST file boundaries within a level. This propagates to UserDefinedIndexIteratorWrapper::SeekToFirst() which returns NotSupported, causing "Iterator diverged from control iterator" / "VerifyIterator failed" errors across many crash test variants. B: BlobDB is incompatible with trie UDI (user-defined index). When BlobDB is enabled (`enable_blob_files=1`), the flush job stores large values in separate blob files and writes `kTypeBlobIndex` entries in the SST instead of `kTypeValue`. The UDI builder (`UserDefinedIndexBuilderWrapper::OnKeyAdded()`) rejects any entry whose type is not `kTypeValue`, causing the flush to fail with `"user_defined_index_factory only supported with Puts"`. Once the flush fails, the DB enters background error state, and all subsequent `Write()` calls fail with the same error -- printed as the repeated `"multiput error: ..."` messages from `BatchedOpsStressTest::TestPut`. Eventually, `ProcessStatus` encounters this error and triggers `assert(false)`. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14432 Reviewed By: pdillinger Differential Revision: D95457462 Pulled By: xingbowang fbshipit-source-id: bf2bc47bd1ed75926765b2e3ff068f99f89a7793 |
||
|
Xingbo Wang
|
2dc6d6f765 |
Propagate builder error when flush produces empty output (#14418)
Summary:
Propagate builder error when flush produces empty output
When write fault injection causes the table builder to enter an error
state during flush, all subsequent Add() calls return early (ok() is
false), leaving the builder empty (IsEmpty() == true). Previously,
BuildTable() would call builder->Abandon() but not propagate the
builder's error status to 's', leaving it OK. This caused the downstream
key count validation in flush_job.cc to fire a misleading Corruption
error ('Number of keys in flush output SST files does not match...'),
which the stress test harness couldn't identify as a retryable injected
fault error, leading to SafeTerminate().
This started failing recently because ('Separate keys and
values in data blocks', ) introduced a new SST
block format (separate_key_value_in_data_block) that stores keys and
values in separate sections within data blocks. This format requires
additional write operations during Flush() inside the table builder,
increasing the probability that write fault injection
(--write_fault_one_in=128) hits a data block write and puts the builder
into an error state before any entries are committed. The bug in
BuildTable() existed before, but was rarely triggered because the old
interleaved block format had fewer write points susceptible to fault
injection during the critical Add() path.
Fix: After builder->Abandon(), propagate the builder's error status to
's' when the builder is empty due to an internal error. This ensures the
actual IOError from write fault injection is reported, which the stress
test can properly handle via IsErrorInjectedAndRetryable().
The analysis was based on stack trace. However, it would be great
if we could get direct evidence from fault injection.
Pull Request resolved: https://github.com/facebook/rocksdb/pull/14418
Test Plan: Unit test
Reviewed By: hx235
Differential Revision: D95121070
Pulled By: xingbowang
fbshipit-source-id: cfb513bd744ac34ac90cda11c1cbe49a9d0a7c6c
|
||
|
Anand Ananthabhotla
|
3b5cb114e3 |
Refactor MultiScan to use MultiScanIndexIterator (#14401)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14401 Unify the MultiScan and regular iterator codepaths in BlockBasedTableIterator by introducing a MultiScanIndexIterator that implements InternalIteratorBase<IndexValue>. During Prepare(), the original index iterator is swapped out for a MultiScanIndexIterator that wraps the prefetched block handles and scan range metadata. This allows SeekImpl() and FindBlockForward() to use the same code flow for both regular and MultiScan operations, eliminating the need for separate MultiScan-specific methods (SeekMultiScan, FindBlockForwardInMultiScan, MultiScanSeekTargetFromBlock, MultiScanUnexpectedSeekTarget, MultiScanLoadDataBlock, MarkPreparedRangeExhausted). Key changes: - New MultiScanIndexIterator class that manages scan range tracking, block handle iteration, forward-only seek enforcement, and wasted block counting - InitDataBlock() loads blocks from ReadSet when MultiScan is active - FindBlockForward() detects scan range boundaries via IsScanRangeExhausted() after index_iter_->Next() - Disabled reseek optimization for MultiScan so MultiScanIndexIterator::Seek() is always called to update scan range tracking state - Removed MultiScanState struct and all MultiScan-specific methods from BlockBasedTableIterator - No changes to CheckDataBlockWithinUpperBound or CheckOutOfBound — they work as-is through iterate_upper_bound - multi_scan_status_ intentionally not checked in Valid() hot path to avoid performance regression; when status is non-OK, block_iter_points_to_real_block_ is already false - Fixed pre-existing bug in ReadSet::SyncRead() that used the base decompressor without compression dictionary, causing ZSTD data corruption when blocks with dictionary compression needed synchronous fallback reads Reviewed By: xingbowang Differential Revision: D93300655 fbshipit-source-id: 231059208e0cc512bc2ec43ff7055fcb2a2dc72d |
||
|
zaidoon
|
16c81a27e9 |
Extend UDI trie index with seqno side-table for same-user-key block boundaries (#14412)
Summary: When the same user key spans adjacent data blocks with different sequence numbers, the trie index cannot distinguish them because it only stores user keys. This adds a side-table that stores per-leaf sequence numbers and overflow block metadata, enabling correct post-seek correction using seqno comparison. Design: - Trie always stores user-key-only separators (unchanged) - Duplicate separators from same-key boundaries are de-duplicated - Side-table stores leaf_seqnos[], leaf_block_counts[], and overflow arrays (offsets, sizes, seqnos) serialized after the trie data - Post-seek correction: after trie Seek lands on a leaf, compare target_seq vs leaf_seqno to decide whether to advance through overflow blocks or to the next trie leaf - Zero overhead when no same-user-key boundaries exist (no side-table serialized, no seqno checks at seek time) Public API changes (user_defined_index.h): - AddIndexEntry: single pure virtual with IndexEntryContext parameter (replaces old 4-arg version). Context carries last_key_seq and first_key_seq for block boundaries. - SeekAndGetResult: single pure virtual with SeekContext parameter (replaces old 2-arg version). Context carries target_seq. - Fix trailing semicolons on NewBuilder/NewReader default overrides. Wrapper layer (user_defined_index_wrapper.h): - Extract sequence numbers from parsed internal keys and pass via context structs to UDI builder/iterator. - Fix CurrentIndexSizeEstimate() to delegate to internal builder (was returning 0). - Fix ApproximateMemoryUsage() to include UDI reader memory. - Fix typos: lof_err_key -> log_err_key, COuld -> Could, "Bad index name" -> "Bad index name: ". Trie builder (trie_index_factory.cc): - Buffer separator entries during building; at Finish(), detect whether any same-user-key boundary was seen (sticky flag, same strategy as ShortenedIndexBuilder::must_use_separator_with_seq_). - When seqno encoding is needed, re-encode all separators with seqno side-table metadata in the trie. - Default null comparator to BytewiseComparator() to prevent crash. Trie iterator (trie_index_factory.cc): - Post-seek correction: compare target_seq vs leaf_seqno to advance through overflow runs. - Overflow run state tracking: overflow_run_index_, overflow_run_size_, overflow_base_idx_ for O(1) access to overflow block handles. - NextAndGetResult advances within overflow runs before moving to next trie leaf. - Return kOutOfBound instead of kUnknown when Seek/Next finds no blocks. LOUDS trie (louds_trie.h, louds_trie.cc): - Seqno side-table: builder AddKeyWithSeqno/AddOverflowBlock methods, BFS reordering of seqno/block_count arrays, serialization/deserialization of per-leaf seqnos, block counts, overflow handles/seqnos, and overflow_base_ prefix sum for O(1) access. - AppendKeySlot() helper with debug bounds assert on all key-append sites. Dead code removal: - LoudsTrieBuilder::NumKeys() (never called externally) - sparse_leaf_count_ (serialized but never read by the reader) - DenseChildNodeNum(pos), DenseLeafIndex(pos), DenseNodeNum(pos) (superseded by FromRank variants that avoid redundant Rank1 calls) Deserialization hardening (all in InitFromData, cold path only): - Move num_keys_ validation before any dependent arithmetic. - Validate dense bitvector sizes match dense_node_count_ (d_labels must be node_count*256, d_has_child must equal d_labels.NumOnes(), d_is_prefix_key must equal node_count). - Validate sparse bitvector sizes match s_labels_size_ (s_has_child and s_louds must have the same number of bits as the label array). - Validate child position table values within s_labels_size_ bounds. - Validate chain suffix offset+length within suffix data blob. - Validate chain end child indices < num_internal or == UINT32_MAX. - EliasFano: add count_ upper-bound check (<=2^30) to prevent count_*low_bits_ integer overflow. - Bitvector: validate select hint values < num_rank_samples_ to prevent OOB in FindNthOneBit/FindNthZeroBit. - EliasFano: custom move ctor/assignment to re-seat low_words_ after owned_low_data_ move (fixes dangling pointer for SSO strings). https://github.com/facebook/rocksdb/issues/14406 Pull Request resolved: https://github.com/facebook/rocksdb/pull/14412 Reviewed By: anand1976 Differential Revision: D95160933 Pulled By: xingbowang fbshipit-source-id: f2c3681c1059c03d540ce1cb9cc14cc79cd9730c |
||
|
Xingbo Wang
|
b48d6f2c12 |
Block TransactionDB when UDI (use_trie_index) is enabled (#14408)
Summary: User-Defined Index (UDI) only supports kTypeValue (Put) entries. TransactionDB is incompatible because transaction ROLLBACK operations write DELETE entries to the WAL to undo uncommitted changes. Evidence from crash DB analysis (T257683723): - All SST files had 0 deletions, 0 merges, 0 range deletions - WAL file 012653.log contained DELETE entries from ROLLBACK: 322982,DELETE(2) ROLLBACK(0x7869643334333837) 322987,DELETE(8) ROLLBACK(0x7869643334333935) 322989,DELETE(8) ROLLBACK(0x7869643334343031) 322993,DELETE(9) ROLLBACK(0x7869643334343035) 322996,DELETE(4) ROLLBACK(0x7869643334333939) Root cause chain: 1. TransactionDB ROLLBACK writes DELETE entries to WAL 2. During recovery/Open(), WAL entries are replayed into memtable 3. During flush, memtable (containing DELETEs) triggers UDI builder 4. UDI builder rejects DELETE: pkey.type != kTypeValue 5. Error: "user_defined_index_factory only supported with Puts" This change adds: 1. Validation in db_stress_tool.cc to reject use_trie_index + use_txn 2. Sanitization in db_crashtest.py to set use_txn=0 when use_trie_index=1 Pull Request resolved: https://github.com/facebook/rocksdb/pull/14408 Test Plan: ./db_stress --use_trie_index=1 --use_txn=1 --delpercent=0 \ --delrangepercent=0 --readpercent=30 --prefixpercent=20 \ --writepercent=40 --iterpercent=10 --customopspercent=0 # Now correctly rejects with clear error message Reviewed By: joshkang97 Differential Revision: D94928704 Pulled By: xingbowang fbshipit-source-id: bdaa1e719f158e4a3fd76c64cf097ac3f41c8512 |
||
|
zaidoon
|
8707abfc11 |
Fix crash in UserDefinedIndexBuilderWrapper with buffered data blocks (#14404)
Summary: When the UDI wrapper's OnKeyAdded() encountered a non-Put key type (e.g. Delete or Merge), it set its internal status_ to non-OK and stopped forwarding OnKeyAdded() to the wrapped internal index builder. However, AddIndexEntry() was always forwarded unconditionally. This asymmetry left the internal ShortenedIndexBuilder's current_block_first_internal_key_ empty, triggering an assertion failure in GetFirstInternalKey() during the buffered-block replay in MaybeEnterUnbuffered(). The crash required three conditions to co-occur: 1. UDI enabled (use_trie_index=1) 2. Compression dictionary enabled (triggering kBuffered mode) 3. Non-Put entries in the data (Delete, Merge, etc.) Fix: move the internal_index_builder_->OnKeyAdded() call before the status_ guard so the internal builder always receives every key, matching the unconditional forwarding in AddIndexEntry(). Pull Request resolved: https://github.com/facebook/rocksdb/pull/14404 Reviewed By: archang19 Differential Revision: D94791493 Pulled By: xingbowang fbshipit-source-id: 882e409f61ae9aca084e9511794ca32ba4ff090f |
||
|
zaidoon
|
ce0fff9f41 |
Add trie-based User Defined Index (UDI) plugin (#14310)
Summary: Implement a Fast Succinct Trie (FST) index based on LOUDS encoding as a User Defined Index plugin for RocksDB's block-based tables. First step toward trie-based indexing per https://github.com/facebook/rocksdb/issues/12396. The trie uses hybrid LOUDS-Dense (upper levels, 256-bit bitmaps) + LOUDS-Sparse (lower levels, label arrays) encoding inspired by the [SuRF paper](https://www.pdl.cmu.edu/PDL-FTP/Storage/surf_sigmod18.pdf) (Zhang et al., SIGMOD 2018). The boundary between dense and sparse levels is automatically chosen to minimize total space. Key Components - **Bitvector** with O(1) rank and O(log n) select using a rank LUT sampled every 256 bits with popcount intrinsics. Uses uint32_t rank LUT entries (halving memory vs uint64_t). Includes word-level `AppendWord()` for efficient dense bitmap construction and `AppendMultiple()` optimized at word granularity for bulk bit fills. - **Streaming trie builder** using flat per-level arrays with deferred internal marking, handle migration for prefix keys, and lazy node creation. Infers trie structure directly from sorted keys via LCP analysis in a single pass (no intermediate tree). - **LoudsTrie** for immutable querying with BFS-ordered handle reordering built into single-pass level-by-level serialization. Move-only semantics with correct pointer re-seating after `std::string` move. - **LoudsTrieIterator** with rank-based traversal, key reconstruction from trie path, and stack-based backtracking for `Next()`. Uses packed 8-byte `LevelPos` (is_dense flag in bit 63) and `autovector<LevelPos, 24>` to avoid heap allocation. Key reconstruction uses a raw char buffer allocated once to `MaxDepth()+1` bytes. - **TrieIndexFactory/Builder/Reader/Iterator** implementing the `UserDefinedIndexFactory` interface. - **Zero-copy block handle loading** using two fixed-width uint64_t arrays (offsets + sizes) with 8-byte alignment, enabling O(1) initialization via direct pointer assignment. Seek Hot Path Optimizations - **Fanout-1 sparse fast path**: Most sparse nodes in tries built from zero-padded numeric keys have exactly one child. Detected via `start_pos + 1 == end_pos` and inlined as a single byte comparison, avoiding the full `SparseSeekLabel` call. - **Linear scan for small sparse nodes**: `SparseSeekLabel` uses sequential scan for nodes with ≤16 labels instead of binary search. Faster for common 10-child digit nodes where branch misprediction cost outweighs linear scan cost. - **Rank reuse**: `DenseLeafIndexFromRankAndHasChildRank` and `SparseLeafIndexFromHasChildRank` overloads accept pre-computed `has_child_rank` from the Seek descent, avoiding redundant `Rank1` calls. General Performance Optimizations - **Select-free sparse traversal**: Precomputed child position lookup tables (`s_child_start_pos_`/`s_child_end_pos_`) eliminate `Select1` calls during Seek. Sparse traversal tracks `(start_pos, end_pos)` directly, using only `Rank1` (O(1)) + array lookup (O(1)) for child descent. - **Cached label_rank pattern**: Eliminates redundant `Rank1` calls in hot paths (Seek, Next, Advance all cache and reuse the label_rank computed for has_child checking). - **Leaf index fast path**: When no prefix keys exist (common case), `SparseLeafIndex` and `DenseLeafIndexFromRank` skip the prefix-key `Rank1` calls entirely, reducing from 3 to 1 `Rank1` call. - **Popcount-based Select64** via 6-step binary search within 64-bit words. - MSVC portability using RocksDB's `BitsSetToOne`/`CountTrailingZeroBits`. Benchmark Results Trie Seek at 32K keys (16-byte keys, 5M lookups, median of 5 runs): | Configuration | ns/op | |---|---:| | Trie (optimized) | **118** | | Binary search (native) | 134 | Trie Seek is **~12% faster** than native binary search index at 32K keys per block. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14310 Reviewed By: anand1976 Differential Revision: D93921511 Pulled By: xingbowang fbshipit-source-id: ba18604bc6bd4f575311a1ae3047a541274869b6 |
||
Hui Xiao
|
372995470a |
Pass statistics and fix null clock in SstFileReader::MultiGet (#14393)
Summary: **Summary:** This is to sync an internal change of passing `Statistics*` to the GetContext constructor and collecting more stats as well as fix a bug this change created. SstFileReader::MultiGet was passing nullptr for both `SystemClock*` and `Statistics*` to the GetContext constructor. After `Statistics*` was passed to the GetContext constructor (the internal change), this caused a segfault when a merge operation was triggered with statistics enabled, because the merge helper's StopWatchNano attempted to dereference the null clock pointer. Fix by passing `r->ioptions.clock` from the reader's options. Additionally, add `assert(clock_)` guards to `StopWatchNano::Start()` and `ElapsedNanos()` to catch null clock bugs in debug builds. Can't do so in release build because it's on hot path. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14393 Test Plan: - `./sst_file_reader_test --gtest_filter='SstFileReaderTableMultiGetTest.Basic'` exercises merge with statistics enabled, previously segfaulted without the fix with the clock, now passes. - `./sst_file_reader_test` - all tests pass. Reviewed By: xingbowang Differential Revision: D94599343 Pulled By: hx235 fbshipit-source-id: 0a748bb00ee27bb202d01d410b52657101c05de0 |
||
|
Josh Kang
|
5db2eb0f3c |
Fix missing corruption check for key overflows (#14384)
Summary: The refactoring in https://github.com/facebook/rocksdb/pull/14287/changes#diff-9f58e06172d3c8b15496fb4e8216a9ceee07ea2648e4c93d6a105d578697aa07L101-L103 unintentionally removed a corruption check for a key existing past its limit, but does account for a value existing past its limit. This fix adds an explicit key check as well Pull Request resolved: https://github.com/facebook/rocksdb/pull/14384 Test Plan: CI Reviewed By: pdillinger Differential Revision: D94275062 Pulled By: joshkang97 fbshipit-source-id: ba793bbb966f0bae33df4c98e498e3d6a2b04087 |
||
|
Josh Kang
|
901c88e37b |
Separate keys and values in data blocks (#14287)
Summary: Introduce new table option with separated key-value storage in data blocks. This PR implements a new SST block format where keys and values are stored in separate sections within data blocks, rather than interleaved. Keys are stored first, followed by all values in a contiguous section. The motivation is better cpu cache hit rate during seeks and potentially better compression. The additional storage cost is a varint per restart point, and 4 bytes additional block footer. For a data block with a restart interval of 16, it is approximately 1 bit of overhead per entry. But compression actually performs better, resulting in ~3% storage savings from benchmark. For now I've opted to not separate kvs in non-data blocks since restart interval for those blocks is typically 1, and values are typically small and probably better inlined. ### New block layout ``` +------------------+ | Keys Section | <- Key entries with delta encoding +------------------+ | Values Section | <- (new) Values stored contiguously +------------------+ | Restart Array | <- Fixed32 offsets to restart points +------------------+ | Values Offset | <- (new) 4 bytes: offset to values section | Footer | <- 4 bytes: packed index_type + num_restarts +------------------+ ``` ### Entry Format **At restart points** ``` +--------------+------------------+----------------+-----------------+-----------+ | shared (v32) | non_shared (v32) | value_sz (v32) | value_off (v32) | key_delta | +--------------+------------------+----------------+-----------------+-----------+ ``` **At non-restart points** ``` +--------------+------------------+----------------+-----------+ | shared (v32) | non_shared (v32) | value_sz (v32) | key_delta | +--------------+------------------+----------------+-----------+ ``` - `value_offset` is only stored at restart points to save space - For non-restart entries, value offset is computed as: `prev_value_offset + prev_value_size` ### Forward Compatibility - We make use of reserved block footer bits to mark if a block has separated kv format. Should an older version read this, it will assume a very large block restart interval and result in a corruption error. ### Key Changes - **BlockBuilder**: Accumulates values in a separate buffer; value offsets are stored only at restart points (other entries derive offset from previous value's position). There is an additional memcpy cost to place the value data after the key data. - **Block iteration**: Iteration now needs to know if we are at a restart point. This will rely on `cur_entry_idx_`, which was previously only used for per-kv checksum purposes. In this new format, we also need to know the block_restart_interval, which was previously also only calculated for per-kv checksums. - **Table properties**: Store `data_block_restart_interval`, `index_block_restart_interval`, and `separate_key_value_in_data_block` in table properties Pull Request resolved: https://github.com/facebook/rocksdb/pull/14287 Test Plan: - Extended block_test, table_test, compaction_test to contain new separated_kv param - Added new parameter to crash test --- ## Benchmark ### Varying Value Size **Write:** `db_bench --num=1000000 --separate_key_value_in_data_block=<bool> --value_size=<X> --benchmarks=fillrandom,compact` **Read:** `db_bench --db=$DB --use_existing_db --benchmarks=readrandom,readseq` | Value Size | FillRandom (ops/s) | | Compact (s) | | ReadRandom (ops/s) | | ReadSeq (ops/s) | | SST Size (MB) | | |----------:|-------------------:|-----:|----------:|-----:|-------------------:|-----:|----------------:|-----:|-------------:|-----:| | | baseline | sep_kv | baseline | sep_kv | baseline | sep_kv | baseline | sep_kv | baseline | sep_kv | | 1 | 253,280 | 264,977 | 0.516 | 0.497 (**-3.7%**) | 596,328 | 586,625 (**-1.6%**) | 5,904,681 | 6,069,581 (**+2.8%**) | 5.1 | 4.2 (**-18.6%**) | | 16 | 235,757 | 242,367 | 0.572 | 0.533 (**-6.8%**) | 570,751 | 572,815 (**+0.4%**) | 5,371,138 | 5,604,908 (**+4.4%**) | 14.7 | 13.4 (**-8.5%**) | | 100 | 264,299 | 265,427 | 0.461 | 0.454 (**-1.5%**) | 323,696 | 332,790 (**+2.8%**) | 4,239,725 | 4,232,416 (**-0.2%**) | 38.8 | 37.6 (**-3.2%**) | | 1,000 | 238,992 | 242,764 | 2.349 | 2.329 (**-0.9%**) | 244,608 | 261,403 (**+6.9%**) | 1,285,394 | 1,265,868 (**-1.5%**) | 342.1 | 342.0 (**-0.0%**) | ### Varying Block Restart Interval **Write:** `db_bench --num=1000000 --separate_key_value_in_data_block=<bool> --block_restart_interval=<X> --benchmarks=fillrandom,compact` **Read:** `db_bench --db=$DB --use_existing_db --benchmarks=readrandom,readseq` | BRI | FillRandom (ops/s) | | Compact (s) | | ReadRandom (ops/s) | | ReadSeq (ops/s) | | SST Size (MB) | | |----:|-------------------:|-----:|----------:|-----:|-------------------:|-----:|----------------:|-----:|-------------:|-----:| | | baseline | sep_kv | baseline | sep_kv | baseline | sep_kv | baseline | sep_kv | baseline | sep_kv | | 1 | 251,654 | 263,707 | 0.453 | 0.485 (**+7.1%**) | 334,653 | 328,708 (**-1.8%**) | 4,194,342 | 3,954,291 (**-5.7%**) | 40.6 | 42.4 (**+4.5%**) | | 4 | 253,797 | 252,394 | 0.476 | 0.476 (**+0.0%**) | 332,719 | 341,676 (**+2.7%**) | 4,135,691 | 4,051,151 (**-2.0%**) | 39.2 | 39.3 (**+0.3%**) | | 8 | 260,143 | 262,273 | 0.496 | 0.460 (**-7.3%**) | 330,859 | 337,567 (**+2.0%**) | 4,144,081 | 4,187,389 (**+1.0%**) | 38.9 | 38.1 (**-2.1%**) | | 16 | 252,875 | 263,176 | 0.464 | 0.455 (**-1.9%**) | 323,783 | 335,418 (**+3.6%**) | 4,127,310 | 4,217,028 (**+2.2%**) | 38.8 | 37.6 (**-3.2%**) | | 32 | 260,224 | 269,422 | 0.464 | 0.451 (**-2.8%**) | 304,001 | 314,989 (**+3.6%**) | 4,310,162 | 4,247,248 (**-1.5%**) | 38.8 | 37.3 (**-3.8%**) | ### Varying Compression **Write:** `db_bench --num=1000000 --separate_key_value_in_data_block=<bool> --compression_type=<X> [--compression_level=<N>] --benchmarks=fillrandom,compact` **Read:** `db_bench --db=$DB --use_existing_db --benchmarks=readrandom,readseq` | Compression | FillRandom (ops/s) | | Compact (s) | | ReadRandom (ops/s) | | ReadSeq (ops/s) | | SST Size (MB) | | |------------|-------------------:|-----:|----------:|-----:|-------------------:|-----:|----------------:|-----:|-------------:|-----:| | | baseline | sep_kv | baseline | sep_kv | baseline | sep_kv | baseline | sep_kv | baseline | sep_kv | | None | 252,494 | 260,552 | 0.413 | 0.419 (**+1.5%**) | 356,290 | 371,535 (**+4.3%**) | 4,479,261 | 4,507,133 (**+0.6%**) | 73.5 | 73.6 (**+0.2%**) | | LZ4 | 246,010 | 256,360 | 0.477 | 0.455 (**-4.6%**) | 342,497 | 345,882 (**+1.0%**) | 4,400,570 | 4,268,102 (**-3.0%**) | 38.3 | 37.6 (**-2.0%**) | | ZSTD (L3) | 254,748 | 258,556 | 1.067 | 1.055 (**-1.1%**) | 176,724 | 177,566 (**+0.5%**) | 2,736,841 | 2,717,739 (**-0.7%**) | 32.9 | 31.3 (**-4.7%**) | | ZSTD (L6) | 256,459 | 259,388 | 1.556 | 1.462 (**-6.0%**) | 177,390 | 176,691 (**-0.4%**) | 2,754,336 | 2,688,682 (**-2.4%**) | 32.8 | 31.1 (**-5.1%**) | ### Varying Block Size **Write:** `db_bench --num=1000000 --separate_key_value_in_data_block=<bool> --block_size=<X> --benchmarks=fillrandom,compact` **Read:** `db_bench --db=$DB --use_existing_db --benchmarks=readrandom,readseq` | Block Size | FillRandom (ops/s) | | Compact (s) | | ReadRandom (ops/s) | | ReadSeq (ops/s) | | SST Size (MB) | | |-----------:|-------------------:|-----:|----------:|-----:|-------------------:|-----:|----------------:|-----:|-------------:|-----:| | | baseline | sep_kv | baseline | sep_kv | baseline | sep_kv | baseline | sep_kv | baseline | sep_kv | | 4 KB | 263,203 | 260,362 | 0.469 | 0.461 (**-1.7%**) | 324,178 | 332,249 (**+2.5%**) | 4,231,537 | 4,217,763 (**-0.3%**) | 38.8 | 37.6 (**-3.1%**) | | 16 KB | 252,742 | 263,161 | 0.426 | 0.428 (**+0.5%**) | 227,805 | 222,873 (**-2.2%**) | 5,146,997 | 5,081,080 (**-1.3%**) | 38.1 | 36.7 (**-3.6%**) | | 64 KB | 257,490 | 260,225 | 0.423 | 0.414 (**-2.1%**) | 86,807 | 91,586 (**+5.5%**) | 5,380,403 | 5,372,372 (**-0.1%**) | 36.3 | 35.0 (**-3.5%**) | ### Varying Key Size **Write:** `db_bench --num=1000000 --separate_key_value_in_data_block=<bool> --min_key_size=10 --max_key_size=100 --benchmarks=fillrandom,compact` **Read:** `db_bench --db=$DB --use_existing_db --benchmarks=readrandom,readseq` | Key Size | FillRandom (ops/s) | | Compact (s) | | ReadRandom (ops/s) | | ReadSeq (ops/s) | | SST Size (MB) | | |---------:|-------------------:|-----:|----------:|-----:|-------------------:|-----:|----------------:|-----:|-------------:|-----:| | | baseline | sep_kv | baseline | sep_kv | baseline | sep_kv | baseline | sep_kv | baseline | sep_kv | | 10–100 | 243,740 | 255,183 | 0.618 | 0.622 (**+0.6%**) | 284,304 | 307,569 (**+8.2%**) | 3,738,921 | 3,686,676 (**-1.4%**) | 41.5 | 41.2 (**-0.8%**) | ### CPU Profile Notes - No compression: DataBlock::SeekForGet uses less cpu (13.2% vs 13.9%) - https://fburl.com/strobelight/6mwwebft with separated KV - https://fburl.com/strobelight/m9m798ka without - ZSTD compression: rocksdb::DecompressSerializedBlock uses more CPU (45.8% vs 44.9%), while DataBlock::SeekForGet uses less cpu (5.09% vs 6.52%) - https://fburl.com/strobelight/3x5nw1k4 with separated KV - https://fburl.com/strobelight/e7809046 without --- Reviewed By: xingbowang, pdillinger Differential Revision: D92103024 Pulled By: joshkang97 fbshipit-source-id: 47cfeb656ff3c20d34975f0b6c4c0462935a83dc |
||
|
Hui Xiao
|
4c89ff1102 |
Remove deprecated SstFileWriter::Add() and skip_filters parameter (#14352)
Summary: **Context/Summary:** Remove `SstFileWriter::Add()` (deprecated in favor of `Put()`) and the `skip_filters` parameter from `SstFileWriter` constructors (deprecated in favor of setting `BlockBasedTableOptions::filter_policy` to `nullptr`). Both APIs have zero active callers. The `skip_filters` field is also removed from `TableBuilderOptions` (write-side only; the read-side `TableReaderOptions::skip_filters` is unchanged). Pull Request resolved: https://github.com/facebook/rocksdb/pull/14352 Test Plan: make check Reviewed By: xingbowang Differential Revision: D93812389 Pulled By: hx235 fbshipit-source-id: 236b36a6e664758ab5ad90e606bc195d0a6de70f |
||
|
Hui Xiao
|
407f02da19 |
Remove deprecated SliceTransform::InRange() virtual method (#14353)
Summary: **Summary/Context:** Remove the `InRange()` virtual method from `SliceTransform` and all its overrides. This method was marked DEPRECATED, never called by RocksDB, and existed only for backward compatibility. Also removes the `in_range` callback parameter from `rocksdb_slicetransform_create()` in the C API, which is a breaking change appropriate for a major version release. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14353 Test Plan: Make check Reviewed By: xingbowang Differential Revision: D93795070 Pulled By: hx235 fbshipit-source-id: 5eba23f1d038b19c494997a55e5d8ca379fbedcb |
||
|
Josh Kang
|
98002215d0 |
Fix interpolation search target key less than shared prefix length. (#14343)
Summary: There was an edge case missed in the implementation of interpolation search for target keys that had a length smaller than the shared prefix. E.g. first_key = "aaaaaa", last_key = "aaaaaz", target_key = "aaz". In the existing setup, we will seek to position 0, but in reality is should be seeked to the end. #### The fix The solution here was to also do a bounds check on the first search iteration. We utilize memcmp on the target key with the shared_prefix to determine if the target key is outside the bounds. An edge case here is if the target key itself a prefix of the shared prefix (e.g. target = "aaaa"), in this case memcmp return return 0, but the target key is actually smaller. ### Minor optimizations - cache left,right values so we don't need to re-compute it when left/right boundaries don't change - In ReadBe64FromKey, utilize memcpy + swap for fast path - since we have already computed a shared_prefix, every other comparison only needs to compare the non-shared suffixes Pull Request resolved: https://github.com/facebook/rocksdb/pull/14343 Test Plan: Added new unit tests to test this case ### Benchmarks No significant regressions due to additional memcmp. #### Configuration - **CPU:** 192 * AMD EPYC-Genoa Processor - **RocksDB Version:** 10.12.0 - **Compression:** Snappy - **Entries:** 1,000,000 - **Value Size:** 100 bytes - **Index Search Type:** interpolation_search - **Index Shortening Mode:** 1 #### Results | Benchmark | Params | ops/s (main) | ops/s (feature) | % change | |-----------|--------|-------------|-----------------|----------| | readrandom | 16B keys, no prefix | 367,264 | 369,163 | +0.52% | | readrandom | 100B keys, prefix_size=50 | 376,066 | 371,193 | -1.29% | Reviewed By: pdillinger Differential Revision: D93535267 Pulled By: joshkang97 fbshipit-source-id: beda182efce1e914ff587e697b927347cfa42656 |
||
|
Peter Dillinger
|
d3817f058d |
Remove deprecated DB::Open raw pointer variants (and more) (#14335)
Summary: and remove deprecated DB::MaxMemCompactionLevel(). In the process of pushing through a relatively clean refactoring of uses of the old functions, some other minor public APIs are also migrated from raw DB pointers to unique_ptr. Claude did pretty much all the work, but requiring dozens of prompts to actually push through relatively clean phase out of raw DB pointers from what needed to be touched, and leaving that code in better shape. (Hundreds of `DB*` still remain all over the place even outside C and Java bindings.) Pull Request resolved: https://github.com/facebook/rocksdb/pull/14335 Test Plan: existing tests; no functional changes intended Reviewed By: xingbowang, mszeszko-meta Differential Revision: D93523820 Pulled By: pdillinger fbshipit-source-id: e4ca22ad81cd2cfe91122d7507d7ca34fe03d043 |
||
|
Peter Dillinger
|
1f9d8ee302 |
Remove obsolete code for block-based format_version < 2 (after #14315) (#14327)
Summary:
After PR https://github.com/facebook/rocksdb/issues/14315 dropped support for block-based table format_version < 2, several code paths became obsolete. This change removes them.
Investigation findings:
1. Table properties are now a hard requirement for block-based SST files:
- format_version >= 2 guarantees a properties block exists
- Removed defensive conditionals like `if (rep_->table_properties)`
- Missing properties block now returns Status::Corruption instead of just logging an error. This is important because some properties affect the semantic interpretation of the file.
2. Index type property (kIndexType) is now required:
- kIndexType was introduced in Feb 2014 (commit
|
||
|
Peter Dillinger
|
641f4703ac |
Refactor data block footer to reserve metadata bits for future features (#14332)
Summary: I'm implementing this intending it to be used for https://github.com/facebook/rocksdb/issues/14287 Refactor the data block footer encoding/decoding to use a struct-based Encode/Decode API (DataBlockFooter), reserving the top 4 bits of the footer for metadata: - Bit 31: Hash index present (kDataBlockBinaryAndHash) - existing use - Bits 28-30: Reserved for future features Comments have some detail for why it is safe to assume no practical existing SST files would use these newly reserved bits. And for forward compatibility, existing versions detect (non-zero) use of these new bits as impossibly large num_restarts and report "bad block contents". Not perfect, but not bad. Key changes: - Replace PackIndexTypeAndNumRestarts/UnPackIndexTypeAndNumRestarts with DataBlockFooter::EncodeTo/DecodeFrom methods - DecodeFrom returns a detailed error when reserved bits are set, enabling graceful failure on newer format versions - Reduce kMaxNumRestarts from 2^31-1 to 2^28-1 (268M), which is adequate for the maximum possible restarts in a 4GiB block - Add GetCorruptionStatus() to Block for detailed error messages (Note that we are sensitive to the size of Block objects, so have to avoid adding unnecessary new members.) - Remove obsolete kMaxBlockSizeSupportedByHashIndex size checks Pull Request resolved: https://github.com/facebook/rocksdb/pull/14332 Test Plan: - Existing unit tests and format compatibility test - Add test for reserved bit detection (ReservedBitInDataBlockFooter) Reviewed By: joshkang97 Differential Revision: D93293152 Pulled By: pdillinger fbshipit-source-id: b65a83e96bb09a98fb9b8b2dd9f754653ca7ed4d |
||
|
Andrew Chang
|
09bda51c50 |
Propagate file_checksum through FileOptions on NewRandomAccessFile (#14321)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14321 Add file_checksum and file_checksum_func_name fields to FileOptions so that downstream FileSystem implementations can access per-file checksum metadata when SST files are opened. The fields are populated from FileMetaData at all call sites where SST files are opened via NewRandomAccessFile: TableCache::GetTableReader, Version::GetTableProperties, and CompactionJob::ReadTablePropertiesDirectly. Also fixes the fallback path in TableCache::GetTableReader to use the local fopts (with temperature and checksum) instead of the original file_options. Added a kNoFileChecksumFuncName which is distinct from kUnknownFileChecksumFuncName: - kUnknownFileChecksumFuncName ("Unknown"): We have FileMetaData for this file, and the metadata says no checksum was computed (no factory was configured when the file was written). This is a property of the file itself. - kNoFileChecksumFuncName ("Unavailable"): We don't even have FileMetaData — we're opening this file in a context where there's no checksum metadata to propagate at all (e.g., SstFileDumper, SstFileReader, checksum generation). It's a property of the call site, not the file. So the assertion file_checksum.empty() is correct for both, but for different reasons — one says "the file has no checksum," the other says "we have no idea about this file's checksum." Reviewed By: pdillinger Differential Revision: D92728944 fbshipit-source-id: 8fd34ea22ca87090b26d0a55c921f354f97f1ffc |
||
|
Maciej Szeszko
|
ebd1000008 |
Fix UB in ReadBe64FromKey shift by 64 (#14340)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14340 `ReadBe64FromKey` pads its result with `val <<= (8 - len) * 8` to right-align partial reads. When the seek target's user key is shorter than shared_prefix_len, len is 0 and this becomes a shift by 64, which is undefined behavior for uint64_t. On x86 this happens to produce 0 (the correct result), but UBSan rightfully flags it. Guard the shift with `len > 0 && len < 8`. Reviewed By: joshkang97 Differential Revision: D93435715 fbshipit-source-id: bab128e9a65ea18d401670268cbac77d45e11340 |
||
|
Josh Kang
|
9f47518676 |
Add interpolation search as an alternative to binary search (#14247)
Summary: Interpolation search is an alternative algorithm to binary search, which performs better on uniformly distributed keys. Instead of binary search always computing the mid point of the left and right boundaries, interpolation search "interpolates" the mid point based on the distance to the target. Fortunately, we can re-use existing block format to support interpolation search. For a given block, we compute the shared_prefix length of the first and last key. Interpolation search is usually done with numerical target values, so for a variable binary length key, we calculate the "value" as the first 8 non-shared bytes. This also means interpolation search would only really be effective for bytewise comparator (guarded via options validations). #### Fallback to binary search - if the the val(left_key) == val(right_key) then we fallback to classic binary search (to avoid divide by 0) - interpolation search is significantly more computationally expensive than binary search, so when the search distance is small, we also fallback to binary search. - if interpolation search does not make significant progress (i.e. reduces search space by more than half each iteration), we can assume data is non-uniform and fallback. Interpolation search also performs best when there is minimal shortening, especially shortening of the last block, as it can heavily skew the distribution of the actual keys. Note that each search algorithm is guaranteed to make progress because at each iteration the search space is guaranteed to be reduce by at least 1. For now this change only applies to index block seeks, as data block seeks and other blocks do not have as many entries and would not require significant number of search rounds, but it could be easily extended to include that support. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14247 Test Plan: Updated unit tests and crash test with new search option ### Benchmark The default benchmark sets up keys in generally uniform distribution, so it was a good way to test performance improvements. Setup: `./db_bench -benchmarks=fillseq,compact -index_shortening_mode=1` #### Before this change ``` ./db_bench -use_existing_db=true -benchmarks=readrandom -seed=1 readrandom : 2.899 micros/op 344973 ops/sec 2.899 seconds 1000000 operations; 38.2 MB/s (1000000 of 1000000 found) ``` #### After this change Notice how key comparison counts are the same between the two. ``` ./db_bench -use_existing_db=true -benchmarks=readrandom -seed=1 -index_search_type=binary_search readrandom : 2.881 micros/op 347128 ops/sec 2.881 seconds 1000000 operations; 38.4 MB/s (1000000 of 1000000 found) ``` ``` ./db_bench -use_existing_db=true -benchmarks=readrandom -seed=1 -index_search_type=interpolation_search readrandom : 2.609 micros/op 383209 ops/sec 2.610 seconds 1000000 operations; 42.4 MB/s (1000000 of 1000000 found) ``` With a non-uniform distribution, `i.e. index_shortening_mode=2` ``` ./db_bench -use_existing_db=true -benchmarks=readrandom -seed=1 -index_search_type=binary_search readrandom : 2.958 micros/op 338075 ops/sec 2.958 seconds 1000000 operations; 37.4 MB/s (1000000 of 1000000 found) ``` ``` ./db_bench -use_existing_db=true -benchmarks=readrandom -seed=1 -index_search_type=interpolation_search readrandom : 5.502 micros/op 181750 ops/sec 5.502 seconds 1000000 operations; 20.1 MB/s (1000000 of 1000000 found) ``` Reviewed By: pdillinger Differential Revision: D91063163 Pulled By: joshkang97 fbshipit-source-id: 151d6aa76f8713740b714de6e406aff40d28ccbc |
||
|
Peter Dillinger
|
871f79d6ef |
Reformat source files (#14331)
Summary: probably something changed, maybe https://github.com/facebook/rocksdb/issues/14311 Full command: ``` git ls-files '*.cc' '*.h' | grep -v '^third-party/' | grep -v 'range_tree' | xargs clang-format -i ``` Pull Request resolved: https://github.com/facebook/rocksdb/pull/14331 Test Plan: CI Reviewed By: mszeszko-meta Differential Revision: D93246992 Pulled By: pdillinger fbshipit-source-id: 6bc5b97978fef8aee52823dadb6daa4bea57343d |
||
|
Peter Dillinger
|
672389fd8c |
Remove obsolete compression code and some .h->.cc movement (#14325)
Summary: In follow-up to https://github.com/facebook/rocksdb/issues/14315 Remove obsolete code replaced by new Compressor/Decompressor interface: * OLD_CompressData and OLD_UncompressData * Individual compression/decompression functions (Snappy_*, Zlib_*, BZip2_*, LZ4_*, LZ4HC_*, XPRESS_*, ZSTD_Compress, ZSTD_Uncompress) * CompressionInfo and UncompressionInfo classes * UncompressionDict class * compression::PutDecompressedSizeInfo and GetDecompressedSizeInfo The only small refactoring in this change that is not pure code removal or movement is in blob_file_builder_test.cc. Move some function implementations etc. from compression.h to compression.cc: * CompressionTypeToString, CompressionTypeFromString, CompressionOptionsToString * ZSTD_TrainDictionary (both overloads), ZSTD_FinalizeDictionary * DecompressorDict::Populate * Most compression library includes Also cleaned up other includes of compression.h, which caused some other files to need new includes. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14325 Test Plan: existing tests Reviewed By: hx235 Differential Revision: D93120580 Pulled By: pdillinger fbshipit-source-id: ab5c50db7379c0387a8c0e379642c9ea2799eae5 |
||
|
Peter Dillinger
|
d8b1893c9d |
DROP support for block-based SST format_version < 2 (#14315)
Summary: ... and remove some old code and tech debt in the process. This is arguably a great milestone and precendent in RocksDB history as for the first time we are explicitly dropping support for the ability to read source-of-truth data in old formats. (We previously dropped support for reading some old bloom filters, but those are performance optimizers not source-of-truth. https://github.com/facebook/rocksdb/issues/10184) However, DBs written with default settings since release 4.6.0, which is very nearly 10 years ago, can still be read. And by using compaction with intermediate versions, there's an upgrade path going back to (AFAIK) early releases of LevelDB (from which RocksDB was forked). Some detail: * The magic number for LevelDB SST files (0xdb4775248b80fb57, most recently called kLegacyBlockBasedTableMagicNumber) now only exists in the code to provide a good error message and to test that good error message. * There is some notable refactoring and renaming around format_version handling. This is a bit of a messy area of code because the footer code being shared between different table formats (block-based, plain, cuckoo) means format_version in the footer is in ways tied to all of them, but in other ways is just tied to block-based table where we have been making updates. Hopefully code comments keep this clear. * Now that there are old format_versions we can't read (and can't write authoritatively in tests), I've needed to split out kMinSupportedFormatVersion into a constant for reads and for writes, currently the same at format_version=2. Comments describe how to update these in the future. * The idea of versioning the compression format is basically going away, though we're keeping BuiltinV2 in places just because it's already there. There's lots of room in the BuiltinV2 schema to expand to new built-in compression types, or new ways of handling existing compression algorithms. CompressionManager with CompatibilityName gives users the power to customize compression without the need for versions tied to format_version. Immediate follow-up: * Clean up compression loose ends like OLD_Compress, OLD_Uncompress Suggested follow-up: * Update plain table builder to migrate to new footer version so that we can drop support for legacy footer. We have to be careful that the (likely untested) forward compatibility path I put in place a while back works (or fix it and wait a while) before dropping support for plain table with legacy footer. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14315 Test Plan: * Some tests updated / added * A couple tests are obsolete: removed * Also updated format compatible test, which now doesn't need to dig as far back into history building RocksDB. Reviewed By: hx235 Differential Revision: D92577766 Pulled By: pdillinger fbshipit-source-id: a23be846189d901ce087af4ca9a99cef18445cb7 |