mirror of
https://github.com/facebook/rocksdb.git
synced 2026-10-23 08:09:02 +03:00
main
151 Commits
| Author | SHA1 | Message | Date | |
|---|---|---|---|---|
cm-sally-mate
|
94c7f76da0 |
Keep read-path tombstone conversion from deleting ingested files an older iterator cannot see (#15461)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/15461 **What:** With `min_tombstones_for_range_conversion` set, an iterator whose view predates an ingestion can delete the ingested keys for good. **Why it matters:** Silent, permanent data loss. `Get` returns the ingested key right after ingestion. After one scan from the older iterator, `Get` returns NotFound, also after flush and reopen. Every MyRocks bulk load with the option set takes this path: MyRocks ingests with `allow_global_seqno=false` and `snapshot_consistency=false` (seqno 0). **Root cause:** - The older iterator does not see the ingested file. It sees the deleted keys on both sides of the file as one run, and inserts a range tombstone at its read sequence number. The tombstone covers the ingested keys. - `ingest_seqno_barrier_` (D102044512) refuses a conversion only when the iterator's sequence number is below the ingested seqno. That misses two cases: 1. The file gets no new seqno: no overlap (seqno 0), `ingest_behind`, or `allow_db_generated_files`. Ingestion does not move the barrier at all (`assigned > 0`). 2. `NewIterator()` references the SuperVersion before it reads the sequence number. If an ingestion and a write happen in between, the iterator reads at a sequence number above the ingested file, with a SuperVersion that does not have it. This also loses files ingested with a new seqno. - Ingestions that flush the memtable are safe: the older iterator's memtable becomes immutable. **Fix:** Barrier on the Version, not only on the sequence number. - After `LogAndApply()`, ingestion records the new Version number on the active memtable (`ingest_version_barrier_`), while it still holds the per-CF `ingest_sst_lock`. - `DBIter` passes the number of the Version it reads. `AddLogicallyRedundantRangeTombstone()` refuses the conversion if that number is below the barrier. - Version numbers only go up, and every later Version of the column family has the ingested files. So the check is true exactly when the iterator cannot see an ingestion into this memtable. Iterators created after the ingestion convert as before. - The seqno barrier stays: it still covers old explicit snapshots that read a newer Version. **Related:** D126796014 (`Disable tombstone conversion for kMemtableTier iterators`) fixes a different trigger of the same feature. Reviewed By: joshkang97, archang19 Differential Revision: D126875720 fbshipit-source-id: 5767b866c6174d791f9ddae78311816300ac49f3 |
||
Andrew Chang
|
431ce83b9b |
Disable tombstone conversion for kMemtableTier iterators (#15451)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/15451 Fix a data loss bug in read-path range tombstone conversion. Why the change is required: With `min_tombstones_for_range_conversion` > 0, a DBIter that scans a run of contiguous point tombstones inserts a range tombstone `[first_tombstone_key, next_live_key)` at its read sequence number into the active memtable. This is only logically redundant if the iterator observed every live key inside that range. An iterator created with `ReadOptions::read_tier = kMemtableTier` reads only the mutable and immutable memtables (`DBImpl::NewInternalIterator` adds no SST iterators for that tier), but DBIter still enabled conversion for it: the gates were the active memtable, `table_filter`, prefix mode, and timestamp visibility, not the read tier. Previous behavior: A live key that exists only in SST files and sorts between memtable tombstones is invisible to a memtable-only scan, so the scan treats the tombstones around it as contiguous and inserts a range tombstone covering it. The key is then deleted for all reads at or above the iterator's sequence number, and the deletion persists through flush and compaction. Example with `min_tombstones_for_range_conversion = 2`: `Put(c)`, `Flush()`, `Put(a)`, `Delete(b)`, `Delete(d)`, `Put(e)`; a `kMemtableTier` scan returns `a, e` and inserts `[b, e)`; afterwards `Get(c)` returns NotFound. Both forward and reverse scans trigger it. Affected: column families with `min_tombstones_for_range_conversion` > 0 (EXPERIMENTAL, default 0) that create iterators with `read_tier = kMemtableTier`. Not affected: `kBlockCacheTier` (the scan stops with `Incomplete` before a run can be flushed, already covered by `NoInsertionOnBlockCacheTierIncomplete`), `kPersistedTier` (not supported for iterators), and all other iterators. New behavior: Conversion runs only for iterators with `read_tier = kReadAllTier`, and stays disabled for the iterator lifetime for every other tier. This also turns it off for `kBlockCacheTier` scans that are served fully from cache, which could convert before. The option documentation now lists reads with `read_tier` other than `kReadAllTier` among the configurations where conversion is skipped. Implementation: One more condition, `read_tier == kReadAllTier`, in the DBIter constructor's `min_tombstones_for_range_conversion_` gate, next to the existing `table_filter` and timestamp-visibility checks. Release note added. Safety, compatibility, and limitations: No API, format, or default changes. The change only drops a logically redundant optimization for read tiers that cannot guarantee a complete scan. A new test checks that a range tombstone inserted by a full-tier scan does not change what later `kMemtableTier` and `kBlockCacheTier` reads return. The only difference it found: with a cold block cache, a `kBlockCacheTier` `Get` of a covered key returns NotFound (the full-tier answer) instead of `Incomplete`. Reviewed By: joshkang97, jaykorean Differential Revision: D126796014 fbshipit-source-id: 70f5184dbf5bb9eff765c232ac130ab43379a814 |
||
Josh Kang
|
014e1c43c1 |
Apply readability fixes (isolate decls, braces) (#15394)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/15394 ## Summary RocksDB's `.clang-tidy` enables several readability checks that existing code still violates: `readability-isolate-declaration` (476 findings), `readability-braces-around-statements` (49), `readability-redundant-string-init` (25), `modernize-use-using` (10), `misc-definitions-in-headers` (3) and `readability-duplicate-include` (1). They keep getting flagged whenever nearby lines change. This diff fixes 553 of the 564; upstream has since fixed the other 11. What changed: - Multi-variable declarations such as `std::string a, b;` are split into one declaration per variable. Pointer and reference declarators are kept per variable. - Braces are added around single-statement `if`/`else`/`for`/`while` bodies, and empty spin loops get an empty `{}` body. - `std::string s = ""` / `member("")` initializers are removed. - Remaining `typedef`s in the touched C++ files become `using`. C headers and `extern "C"` code are untouched. - `inline` is added to non-template function definitions in test headers. - A duplicate `#include "util/udt_util.h"` in `db_impl.cc` is removed. These are clang-tidy's own fix-its, applied mechanically and then clang-formatted on the changed lines. Three kinds of broken fix-it output were repaired by hand. Removing a `member("")` initializer left a dangling comma in constructor initializer lists (`ExternalSstFileInfo`, `ColumnFamilyMetaData` and others). The function-type typedefs in `block_test.cc` came out malformed. Empty `while (cond);` spin loops got a `{;` body. Splitting declarations also exposed two vectors in `db_etc2_test.cc` to `performance-inefficient-vector-operation`, so a `reserve()` was added for each. The lint bot reports every finding in a file a diff touches. This diff splits declarations in `options/configurable_test.cc`, so it also fixes that file's 14 older `cert-err58-cpp` and `cppcoreguidelines-avoid-non-const-global-variables` findings, which come from seven mutable file-level maps. Six are now `const` and built where they are used (function-local statics, or locals in their only user). The unused `imm_struct_option_info` is deleted. Compatibility: no behavior change. In public headers, the only edits are removed redundant `""` initializers, split declarations and added braces. Reviewed By: rban1 Differential Revision: D123186310 fbshipit-source-id: f9c8e88b00e997db0196f8725c7c8d880cf798da |
||
Yoshinori Matsunobu
|
77eef9fa2e |
Make RocksDB reverse iteration honor query aborts (#15376)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/15376 RocksDB `DBIter` polled `ROCKSDB_THREAD_YIELD_CHECK_ABORT()` while scanning ordinary forward entries, but reverse `Prev()` / `SeekForPrev()` traversal and `MergeValuesNewToOld()` could scan many internal keys without polling. Long tombstone, version, or merge-operand runs could therefore keep a MyRocks query running after `KILL QUERY` until the scan finished. Poll the existing hook before each potentially expensive internal iterator movement in the forward scan, forward merge-operand scan, and four reverse traversal loops. Mark the abort branch `UNLIKELY`; on abort, invalidate the iterator and return `Status::Aborted("Query abort.")`. MyRocks already defines the hook and maps `Status::Aborted` for a killed THD to `HA_ERR_QUERY_INTERRUPTED`, so no MyRocks change is required. There are no API, ABI, or persisted-format changes. The hook remains Linux-only, and cancellation remains cooperative: this cannot preempt an individual underlying iterator operation that never returns. The change is rebased onto current master, including D124377137's fix for the unrelated `WriteBufferManagerTest.FlushPolicyRetiresAndRestartsHandoffWorkers` failures seen on V1. Reviewed By: pdillinger Differential Revision: D124441004 fbshipit-source-id: 53bf83a00121b42566dbd93de232e973cbe78688 |
||
Jay Huh
|
bcf8711165 |
Add per-column-family ReadOptions to NewIterators (#15230)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/15230 Add a raw C++ `DB::NewIterators()` overload accepting parallel vectors of `ReadOptions` and column family handles. Each iterator receives its own options while all iterators share one consistent sequence snapshot. Require identical snapshot pointers and tailing modes across the options. Implement the overload for primary, secondary, read-only, stackable, and write-prepared DBs. Building on D120048299, both secondary overloads share one helper that captures all SuperVersions and the sequence number under the DB mutex. Preserve read-only `table_filter` support when range-tombstone conversion is configured, and reject that unsafe combination in write-prepared read-write iterators before allocating any iterator. Add validation, per-CF prefix-seek coverage, a secondary catch-up regression test, table-filter contract tests, and a public API release note. Reviewed By: xingbowang Differential Revision: D120296578 fbshipit-source-id: 3775884537ea29a0d32bb3fe10330cf62ac5a406 |
||
Peter Dillinger
|
afc922bf5f |
Make ReadOptions::table_filter a caller-owned pointer for cheaper copies (#15005)
Summary: ReadOptions is copied frequently on read paths, and its only non-trivially-copyable member, table_filter, is a std::function that is almost always empty yet still gets deep-copied on every ReadOptions copy (and can heap-allocate). This changes table_filter to a pointer to a caller-owned std::function instead of storing one by value: when non-nullptr, the caller is responsible for keeping the pointed-to function alive for the duration of the read (like the other pointer fields such as iterate_upper_bound). With this change every ReadOptions member is trivially copyable, so copying ReadOptions no longer touches a std::function at all. That trivial-copyability is locked in with a static_assert in options_test.cc (kept out of the public header). This is inspired by D113109635, which targeted the same ReadOptions-copy hotspot by relocating table_filter to the end of the struct so the trivial members memcpy in one contiguous block. This is intended to be a superior solution: rather than only defragmenting the copy, it removes the std::function copy entirely. This is a breaking API change, tolerated because table_filter is a relatively obscure option. A nullptr, or a pointer to an empty std::function, means no filtering (preserving the previous empty-function behavior). A shared internal helper HasTableFilter(const ReadOptions&) in options_helper.h centralizes the nullptr + empty-function check used on the read paths. The C API and Java bindings now own the std::function and hand ReadOptions a pointer to it; their public signatures are unchanged, and the C API rocksdb_readoptions_t clears the owned function when the callback is null. Making ReadOptions trivially copyable also let -Werror=unused-but-set-variable fire on a pre-existing dead local in db_bench's MultiScan: a ReadOptions that set async_io/readahead_size but was never passed to NewMultiScan (the warning had been suppressed while ReadOptions had a non-trivial member). That local was in fact inert for multiscan -- BlockBasedTableIterator::Prepare overrides ReadOptions::async_io with MultiScanArgs::use_async_io for the coalesced prefetch, so multiscan async I/O is driven by --multiscan_use_async_io, not ReadOptions::async_io. Removed the dead local; MultiScan now uses read_options_ directly, consistent with MultiScanRandom. Pull Request resolved: https://github.com/facebook/rocksdb/pull/15005 Test Plan: Existing table_filter coverage was adapted to the new pointer API and still exercises the behavior end to end: db_iterator_test.TableFilter (callback invoked once per table; returning false hides a table) and its range-conversion rejection case; db_bloom_filter_test SstQueryFilter/FixedWidthSegments range queries; and trie_index_db_test's range-query iterator (which returns iterators outliving the filter, exercising the caller-owned lifetime). db/c_test covers the C API set/clear/has_table_filter path. options_test asserts std::is_trivially_copyable_v<ReadOptions>. Manually verified the db_bench MultiScan async behavior with a ~200MB DB and --use_direct_reads: with ReadOptions::async_io held true, async reads tracked only --multiscan_use_async_io (rocksdb.read.async.micros count 329511 with use_async_io=true vs 0 with false), confirming ReadOptions::async_io does not drive multiscan async and the removed local had no effect. Reviewed By: anand1976 Differential Revision: D113613525 Pulled By: pdillinger fbshipit-source-id: 38d73b607500a5c7ca2b89dd8f4187ef43940aa4 |
||
|
Jay Huh
|
dcb5c2bf53 |
Restore MultiScan prefetch stats dropped in the IODispatcher refactor (#14991)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14991 D91705195 ("Replace Prefetch Logic in BlockBasedTableIterator with IODispatcher") moved MultiScan block prefetching out of BlockBasedTableIterator and into the IODispatcher. The IO-level RecordTick/RecordInHistogram calls lived in the deleted prefetch code, and the IODispatcher was not given equivalent instrumentation, so these tickers were still defined but never populated (they published as absent): - MULTISCAN_BLOCKS_PREFETCHED - MULTISCAN_BLOCKS_FROM_CACHE - MULTISCAN_PREFETCH_BYTES - MULTISCAN_IO_REQUESTS - MULTISCAN_IO_COALESCED_NONADJACENT - MULTISCAN_BLOCKS_PER_PREPARE (histogram) The PREPARE_*, SEEK_ERRORS, and PREFETCH_BLOCKS_WASTED tickers were unaffected (recorded on the prepare/teardown path, which was not replaced). Fix: - ReadSet now exposes generic, caller-agnostic prefetch counters (GetNumBlocksPrefetched, GetNumIORequests, GetPrefetchBytes, GetNumCoalescedNonadjacent), incremented once per block in DispatchPrefetch -- the single choke point for both immediate and memory-deferred dispatch. Counting at dispatch time (not completion) keeps async and deferred prefetches accounted for without double counting the async->sync fallback. - PrepareIORequests now outputs prefetch_bytes (sum of request len) and num_coalesced_nonadjacent (within-threshold gap count) while building coalesced requests, per review feedback to avoid the extra pass over read_reqs/coalesced_block_indices at former line 836. DispatchPrefetch now gets stats directly from PrepareIORequests. - The MULTISCAN_* ticker names stay at the caller: MultiScanIndexIterator's destructor records the aggregate counters at end-of-scan (alongside the existing PREFETCH_BLOCKS_WASTED), so async/deferred reads that complete during iteration are included. MULTISCAN_BLOCKS_PER_PREPARE is recorded in BlockBasedTableIterator::Prepare. This keeps the IODispatcher a generic mechanism rather than leaking a caller's metric names into it. - Also plumb the same metrics into PerfContext for per-operation visibility. Reviewed By: xingbowang Differential Revision: D113356436 fbshipit-source-id: 660e9755d6b1b9aecccd112df94eb6838061b298 |
||
|
Jay Huh
|
eca1a114e0 |
Count unreleased MultiScan prefetch blocks as wasted (#14926)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14926 This fixes a gap in the MultiScan prefetch waste accounting introduced by https://github.com/facebook/rocksdb/pull/14876. That change added reverse MultiScan support and introduced `unreleased_prefetch_blocks_` to track prefetched blocks still owned by the `ReadSet`, because reverse scans can prefetch a suffix of the collected block list and release blocks in non-prefix order. However, those unreleased prefetched blocks were only released during `MultiScanIndexIterator` destruction; they were not included in `MULTISCAN_PREFETCH_BLOCKS_WASTED`. As a result, scans that stopped before consuming all prefetched blocks underreported wasted prefetch blocks. This change counts unreleased prefetched blocks as wasted before destructor cleanup, while avoiding counting the currently positioned block as wasted when it has been reached. Reviewed By: xingbowang Differential Revision: D111531409 fbshipit-source-id: 5e605ce686037256bf6847ab7ca363c3f7701401 |
||
|
Jay Huh
|
e1ea04d9ef |
Add reverse order support to MultiScan (#14876)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14876 Add reverse scan support to `MultiScanArgs`/`MultiScan` so callers can iterate bounded scan ranges in descending order. Plumb reverse scan state through `DBIter`, `BlockBasedTableIterator`, and `MultiScanIndexIterator`, including reverse prefetch windowing and async I/O support. Update `db_bench` `multiscanrandom` to honor `--reverse_iterator` and report rows scanned so reverse MultiScan and iterator baselines can be compared on row throughput. Add `db_stress --multiscan_reverse` coverage so the prepared MultiScan path can be stressed with `SeekForPrev()`/`Prev()` against a control iterator. Also fix the table child iterator path to accept reverse `SeekForPrev()` targets above a file's prepared ranges. `MergingIterator` and `LevelIterator` can legally seek every child to the current range limit; a child file may only have lower prepared ranges, so treating that as invalid caused intermittent `SeekForPrev target is outside prepared ranges` exceptions in the benchmark. Reviewed By: xingbowang Differential Revision: D109357730 fbshipit-source-id: eccece5ca7d8f5d6760d51ebe76801a332a49061 |
||
Steph Pontikes
|
e18d41e08c |
lazily intialize iterators (#14772)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14772 Updated the iterator creation scheme to happen lazily (on request) as oppsed to eagerly. this allows us to prune the iterator tree structure at the time of requesting iterator preparation as opposed to creation, and allows pruning to become an implementation detail. Version now skips non-overlapping SST levels and files before adding children to the iterator tree, returns direct table iterators when a level has a single matching file, and uses pruned LevelIterator instances when multiple files in one non-L0 level match. The overload no longer prepares iterators during creation; callers that need prepared multiscan execution still call Prepare explicitly after construction, and MultiScan does that itself. Benchmark: ran `db_bench` in opt mode for the base revision and this diff, with `fillseq,compact,levelstats,multiscanrandom`, `--num=1000000`, `--reads=10000000`, single thread, fixed seeds, `--multiscan_use_async_io=false`, and `--use_multiscan=true`. Both A and B had exactly one SST file and no memtable/L0 data (`L0: 0 files`, `L1: 1 file, 61 MB`). `multiscanrandom` creates `MultiScanArgs` and calls `NewMultiScan(...)`, which reaches the new `NewIterator(..., scan_opts)` pruning path in this diff. ``` seed base A pruning B delta 424242 21824.333 17693.333 -18.9% 424243 24042.014 19424.056 -19.2% 424244 22424.974 17636.910 -21.4% 424245 22404.213 18612.840 -16.9% ``` Average: base `22673.9 us/op`, pruning `18341.8 us/op`, about `19.1%` faster. Reviewed By: xingbowang Differential Revision: D104904298 fbshipit-source-id: a742106a1d5813fb795a39eeeb35f8cddc02e886 |
||
|
Peter Dillinger
|
8053b9414f |
Change default compression from Snappy to LZ4 (#14818)
Summary: The historical default block compression `kSnappyCompression` dates to when Snappy was the obvious fast/cheap choice. On modern server CPUs LZ4 matches or beats Snappy on compression ratio while decompressing substantially cheaper, so it is a better default. This changes the default `ColumnFamilyOptions::compression` to `kLZ4Compression`, with a runtime fallback of LZ4 -> Snappy -> none depending on what is compiled into the binary (new `GetDefaultCompressionType()` in util/compression.h). Only column families that do not explicitly set `compression` are affected (including compaction output when `CompactionOptions::compression == kDisableCompressionOption`), and only newly written SST files; existing data is read as before. Doc comments, the Java bindings, and the sorted_run_builder example are updated to describe the new default. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14818 Test Plan: Adjusted two unit tests that implicitly depended on the old Snappy default to pin `compression = kSnappyCompression`: db_iterator_test's ReadAhead (readahead byte thresholds assume Snappy-sized files) and compaction_service_test's CustomFileChecksum (LSM shape after auto-compaction determined whether a manual CompactRange had work to do). This change is primarily validated by performance testing. Added a `compressreject` db_bench benchmark (output buffer sized just below the predicted compressed size) to measure the cost of attempting then declining compression, alongside `compress`/`uncompress`. Both db_bench and sst_dump compress/decompress a modest block at a time, as in a real workload. sst_dump on SST files from production workloads (4 files, 16KB blocks, single thread) on recent server-class AMD, Intel, and ARM CPUs, LZ4 vs Snappy: - Compression ratio: comparable; LZ4 is slightly smaller on the more compressible files (up to ~8%) and within ~2% on the rest. - Compression (write) CPU: a wash, within ~2% either direction. - Decompression (read) CPU: the clear win -- Snappy costs ~1.2x-1.5x as much as LZ4, i.e. LZ4 saves ~25-30% read CPU, consistently across AMD, Intel, and ARM. db_bench synthetic workload (100-byte values), at 1 / 12 / 160 threads, LZ4 vs Snappy: - Compression throughput: LZ4 ~10-30% higher. - Decompression throughput: LZ4 much higher, and the advantage grows with core count -- from ~+12% at 12 threads to ~+45-50% at 160 threads, i.e. better multi-core scaling. - Rejection (insufficient ratio) path: comparable; LZ4 ~15-18% faster on compressible-but-rejected blocks and Snappy within ~10% on barely-compressible blocks. No meaningful regression, confirming incompressible data is still efficiently detected and stored raw. Reviewed By: xingbowang Differential Revision: D107536490 Pulled By: pdillinger fbshipit-source-id: f8abaee630d782674778338148e36ed0c84e3661 |
||
Xingbo Wang
|
023fbb074a |
Optimize MultiScan dispatch for sorted blocks (#14783)
Summary: - Propagate validated, sorted MultiScan range state from `DBIter::Prepare()` through `MultiScanArgs`. - Mark block-based table IO jobs as already sorted when the public MultiScan ranges have been validated. - Keep `IODispatcher::SubmitJob()` as the normalization boundary for unsorted callers, while allowing sorted callers to skip the defensive block-handle sort. - Update private dispatcher coalescing helpers to consume sorted block indices and add debug assertions for that precondition. ## Testing CI, new unit test Pull Request resolved: https://github.com/facebook/rocksdb/pull/14783 Reviewed By: anand1976 Differential Revision: D106301516 Pulled By: xingbowang fbshipit-source-id: 99b7ffcaecbf27cb79f15feb4af8680ff1e422d9 |
||
Maciej Szeszko
|
3daabe2db3 |
Fix SeekForPrev key pinning regression in FindValueForCurrentKeyUsingSeek (#14746)
Summary: In PR https://github.com/facebook/rocksdb/issues/13531, we added a `saved_key_.SetUserKey(ikey.user_key)` call in `FindValueForCurrentKeyUsingSeek` to fix unprepared-value reverse iteration. The default `copy`=`true` parameter unconditionally copies the key into the internal buffer, breaking is-key-pinned when `pin_data`=`true`. This path triggers only when a key has more versions than `max_sequential_skip_in_iterations` (default 8 ), making the bug rare and hard to repro deterministically. **Fix:** pass `!pin_thru_lifetime_ || !iter_.iter()->IsKeyPinned()` as the copy parameter, matching every other `SetUserKey` call site in `DBIter`. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14746 Test Plan: New test `SeekForPrevKeyPinnedWithManyVersions`: writes 20 versions of the same key, confirms `FindValueForCurrentKeyUsingSeek` is taken via `NUMBER_OF_RESEEKS_IN_ITERATION`, asserts is-key-pinned == "1" after `SeekForPrev`. Fails without fix, passes with. Reviewed By: xingbowang Differential Revision: D105397906 Pulled By: mszeszko-meta fbshipit-source-id: 5581105e9d929bb4c582c52dd6a7ae3e8dd9da72 |
||
|
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 |
||
|
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
|
8fb8fdd349 |
Use saved_key_ instead of iter_.key() in forward range conversion (#14672)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14672 This fixes the forward path introduced in the original pull request: https://www.internalfb.com/diff/D102409405 That change tried to avoid using user-owned `iterate_upper_bound_` memory by reading `iter_.key()` when the internal iterator was still valid and using it as the exclusive end key for the synthetic range tombstone. That is not safe: after the upper-bound break, `iter_.key()` is only the current merged child position, not a key the bounded scan proved safe to read or use as a range endpoint. Example: run a prefix-bounded scan over prefix `b` with tombstones `ba`, `bb`, `bc`, `iterate_upper_bound = "bd"`, live key `be` in an SST, and later same-prefix key `bz` in the memtable. The SST child can drop out when it notices `be >= bd`, while the memtable child is not upper-bound aware and can still surface `bz`. If cleanup uses `iter_.key() == "bz"`, it inserts `[ba, bz)` and covers the live `be`, even though that key was never safe for the bounded scan to reason about. The fix is to always end the forward range at `saved_key_`, which is the last tombstone user key the iterator actually proved deleted. That is conservative but safe. The regression test builds the mixed SST/memtable example above and asserts that the live `be` remains visible. The diff also re-enables randomized `min_tombstones_for_range_conversion` in `db_crashtest.py` and forces it back to `0` when `use_multiscan == 1`, since multiscan still does not support read-path range conversion. Reviewed By: xingbowang Differential Revision: D102493855 fbshipit-source-id: 45bdb86464268e2c4fa2ea735dbb059a5e054f28 |
||
|
Josh Kang
|
a2abe3cfd6 |
Avoid setting read option upper bound for range tombstone conversion (#14664)
Summary: `DBIter::FindNextUserEntryInternal` previously used `iterate_upper_bound_` (user-controlled memory) as the exclusive end-key when flushing an accumulated tombstone run. That pointer is dangerous as it points to user memory space, which can be modified at any moment. This PR removes that dependency: the end-key is always derived from RocksDB-owned data — either the live `iter_` key that broke the run, or `saved_key_` when `iter_` is exhausted. The tradeoff here is that there is potentially 1 less tombstone to get covered in this path, which is reasonable. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14664 Test Plan: Updated unit tests, CI passes Reviewed By: xingbowang Differential Revision: D102409405 Pulled By: joshkang97 fbshipit-source-id: b2beed73e5fe5b955b2d782fc467eda637c4fcf2 |
||
|
Josh Kang
|
03e5a0b9a8 |
Fix range tombstone conversion + ingest sst and re-enable crash tests (#14654)
Summary:
Fixes a correctness bug in read-path range-tombstone synthesis when it races with `IngestExternalFile`. The synthesis path could insert a tombstone into the active memtable at a snapshot's sequence number, while ingestion installed an L0 SST at `LastSequence + 1` — a higher seqno than the synthesized tombstone. This breaks the main assumption of range tombstone reads that all lower levels have lower seqno.
The fix introduces a per-CF `port::RWMutex` (`ColumnFamilyData::ingest_sst_lock_`) plus a per-memtable `ingest_seqno_barrier_`. Ingestion takes the read lock and range tombstone synthesis **tries** to take a write lock.
If iterator lock is successful, then we have a new updated barrier seqno that we can validate the iterator seqno against. An added benefit is we no longer need to gate against empty memtable. This was originally added as an easy fix to prevent memtables from being inserted into while ingestion was happening.
## The bug, by example
`ReadPathRangeTombstoneTest.NewerPointInOlderFileStillVisible` (`db/db_iterator_test.cc:6929`):
1. L0 file `b@1, c@2, d@3`, then L0 file `Delete(b)4, Delete(c)5`.
2. Active memtable: `Put(z)6`. Snapshot taken at seq 6.
3. `IngestExternalFile({c → "vc_live"})` → installed at L0 with seq 7.
4. Iterator at snap 6 walks the deletion run and synthesizes `[b, d) @ seq 6` into the active memtable via `MemTable::AddLogicallyRedundantRangeTombstone`.
5. `Get("c")` at the latest snapshot: memtable returns covering tombstone (seq 6), `Version::Get` short-circuits, **never reads `c@7`** — returns `NotFound` instead of `"vc_live"`.
The invariant `Version::Get` relies on (memtable seqs ≥ any L0 seq for the same key) is broken because synthesis writes at the *snapshot's* seq while ingestion writes at `LastSequence + 1`.
Pull Request resolved: https://github.com/facebook/rocksdb/pull/14654
Test Plan:
- Updated regression test
- Re-enable crashtests and manually run
| Flavor | Jobs |
|---|---:|
| `fbcode_blackbox_crash_test` | 200 |
| `fbcode_whitebox_crash_test` | 30 |
| `fbcode_asan_blackbox_crash_test` | 30 |
| `fbcode_tsan_blackbox_crash_test` | 30 |
| `fbcode_crash_test_with_atomic_flush` | 30 |
| `fbcode_crash_test_with_wc_txn` | 30 |
| `fbcode_crash_test_with_ts` | 30 |
| **Total** | **380** |
Reviewed By: xingbowang
Differential Revision: D102044512
Pulled By: joshkang97
fbshipit-source-id: 0c69187595edc5a5fa80be24bffdba710a92e56e
|
||
|
Josh Kang
|
790294f3ad |
Disallow table_filters entirely when range tombstone conversion is enabled (#14618)
Summary: The prior fix (https://github.com/facebook/rocksdb/issues/14586) disabled read-path range tombstone synthesis at the `DBIter` level when `table_filter` was set. However, synthesized tombstones persist in the memtable beyond the lifetime of the iterator that created them. A prior unfiltered iterator can synthesize a range tombstone that then silently affects a subsequent filtered iterator's results — the filtered scan sees the tombstone but not the SSTs it was derived from, allowing hidden SST state to corrupt the filtered view. See failed crash test in T264151327. This PR takes the stronger approach of rejecting iterator creation outright (`InvalidArgument`) when `ReadOptions::table_filter` is used on a column family with `min_tombstones_for_range_conversion > 0`. This eliminates the entire class of interaction bugs between the two features rather than trying to suppress conversion in individual code paths. ## Example - `min_tombstones_for_range_conversion = 2` - L1 SST_keep: `Put(a), Put(b), Put(c)` (`c` is the live boundary) - L0 SST_dels: `Delete(a), Delete(b)` (2 contiguous tombstones, newer) ### Step 1 — Iterator A (no filter) A walks `Del(a) Del(b)` (2 contig) then `c` (live). Synthesizes range tombstone `[a, c)` into the active memtable. ### Step 2 — Iterator B (`table_filter` skips SST_dels) B's filter excludes SST_dels, so `a, b` from SST_keep should appear live. But the memtable now holds range tombstone `[a, c)` from step 1, which applies to B regardless of `table_filter`. B sees only `c` — **a, b are silently hidden**. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14618 Test Plan: - `TableFilterNotAllowed` test validates the rejection path end-to-end: unfiltered scan synthesizes the tombstone, filtered iterator is rejected with `InvalidArgument`, and the full-DB view remains correct via `VerifyIteration`. - Crash test sanitization ensures `db_stress` won't hit the incompatible configuration. - Run crash test sanitization unit test: `python3 tools/db_crashtest_test.py` - Run iterator tests: `make db_iterator_test && ./db_iterator_test --gtest_filter="*TableFilterNotAllowed*"` Reviewed By: xingbowang Differential Revision: D100873156 Pulled By: joshkang97 fbshipit-source-id: dd0d123d94b1bfda2a4a5040681fcc7cf14f760e |
||
|
Josh Kang
|
9886d52fc4 |
Disable range tomb conversion when using legacy prefix iterator (#14625)
Summary:
There is an assumption in the code that within a given prefix all keys can be seen after a seek to that prefix. The problem occurs when there is a Next() followed by a Prev() back into the same prefix. The merging iterator actually uses SeekForPrev during Prev for non-child iterators, and as a result changes the prefix being used. Now that we are back to our original prefix, the view is incomplete.
The fix is to simply disable range tombstone conversion in this legacy prefix mode.
### Example
Use a 1-byte prefix extractor, so the prefix is just the first character.
Think of the merged iterator as combining two children:
- Child A: `b8`
- Child B: `b7, c1`
Global sorted order is:
```text
b7, b8, c1
```
So:
- predecessor of `c1` should be `b8`
- predecessor of `b8` should be `b7`
## Sequence
Start in legacy prefix mode:
- `total_order_seek = false`
- `prefix_same_as_start = false`
Now do:
1. `Seek("b8")`
2. `Next()`
3. `Prev()`
## What should happen
```text
Seek("b8") -> b8
Next() -> c1
Prev() -> b8
```
Because in the global order, `b8` is immediately before `c1`.
## What the buggy iterator did
```text
Seek("b8") -> b8
Next() -> c1
Prev() -> b7
```
So it skipped `b8`.
## Why it happens
When `Prev()` switches direction, the merging iterator tells all non-current
children to `SeekForPrev(current_key)`.
At that moment:
- current key is `c1`
- so the other children get `SeekForPrev("c1")`
But in legacy prefix mode, those child seeks are allowed to use prefix
filtering. So a child that only contains `b*` keys can effectively say:
```text
"I was asked for prefix c; I do not have prefix c."
```
That child drops out instead of returning its real global predecessor `b8`.
Then the current child simply moves back from `c1` to `b7`, and the merged
result becomes `b7`.
Pull Request resolved: https://github.com/facebook/rocksdb/pull/14625
Test Plan: Update unit tests to disable feature.
Reviewed By: xingbowang
Differential Revision: D101259748
Pulled By: joshkang97
fbshipit-source-id: 23e19c470f931406f96a34a7baebca89e91c7e39
|
||
|
Xingbo Wang
|
c47e35395b |
db: disable read-path tombstone conversion for partial UDT reads (#14595)
Summary: T263957043 reproduces in whitebox crash testing when DBIter converts a run of point deletes into a range tombstone while reading with an older user-defined timestamp. The scan can observe an older delete for the boundary keys but miss newer live versions of the same keys and interior keys, so the synthesized tombstone is based on partial visibility and later hides valid max-timestamp reads. ## Problem Read-path range tombstone conversion (`min_tombstones_for_range_conversion`) assumes the scan observes all interior live keys between the start and end of a contiguous delete run. With user-defined timestamps, a read at an older timestamp can see deletes but miss newer Puts for the same keys. The synthesized range tombstone then incorrectly covers those newer versions, causing data loss on subsequent max-timestamp reads. ## Fix Gate read-path range conversion on full timestamp visibility. The optimization is now only enabled when: 1. There is no `table_filter` (existing guard — SSTs hidden by filter can break the contiguity assumption) 2. There is no `iter_start_ts` (time-travel scans see a subset of versions) 3. Either no read timestamp is set, or the read timestamp is the max timestamp (all `0xff` bytes) This is done via a new helper `HasFullTimestampVisibility()` checked at `DBIter` construction time. ## Test Changes - Updated all existing UDT test variants in `ReadPathRangeTombstoneTest` to read at max timestamp so the optimization remains covered where it is valid. - Added `UDTOlderTimestampDisablesInsertion`: a regression test that writes at ts=1, deletes at ts=2, writes again at ts=3, then reads at ts=2. Verifies no range tombstone is synthesized and a subsequent max-timestamp read still sees all live values. ## Validation - `make -j192 db_iterator_test` - `./db_iterator_test --gtest_filter='*ReadPathRangeTombstoneTest*'` - `./db_iterator_test --gtest_filter='*UDTOlderTimestampDisablesInsertion*' --gtest_repeat=5` - Reran the original whitebox crash-test seed from T263957043 against the patched tree; crash-recovery verification passed Pull Request resolved: https://github.com/facebook/rocksdb/pull/14595 Reviewed By: joshkang97 Differential Revision: D100235999 Pulled By: xingbowang fbshipit-source-id: 7a287f3c7fdc47428fda0ab89eedd5d43f663985 |
||
|
Xingbo Wang
|
4d8a0acd76 |
Disable read-path range tombstone synthesis when ReadOptions.table_filter is set (#14586)
Summary: **Root cause:** DBIter's read-path range tombstone conversion assumes the iterator can observe *every* interior live key between point tombstones. When `ReadOptions.table_filter` is active, whole SSTs can be hidden from the scan. DBIter may then mistake non-contiguous deletes for a contiguous run and synthesize a range tombstone that covers real, still-live keys — silently corrupting the read path. This is not UDT-specific; UDT just changes the failure surface. The stress test failures that triggered investigation were from `db_stress_tool/no_batched_ops_stress.cc` applying an SQFC-backed `table_filter` for range queries even when `total_order_seek` is forced. ## Fix `db/db_iter.cc`: When initializing `min_tombstones_for_range_conversion_`, set it to 0 (disabling range conversion) whenever `read_options.table_filter` is non-null. This is the conservative and correct behavior — filtered scans don't provide the full key visibility the optimization requires. ## Test `db/db_iterator_test.cc` — new test `ReadPathRangeTombstoneTest.TableFilterHiddenInteriorKey`: - Constructs five flushed SSTs so that the live interior key `"b"` lives in a 2-entry SST that the `table_filter` hides. - Keeps the active memtable non-empty (key `"zz"`) so range conversion has a valid insertion point — without this the test is a false negative. - Asserts `inserted_ranges_.size() == 0` (no synthesis occurred). - Verifies `"b"` is still readable via a normal `Get`. - Runs both with and without UDT (user-defined timestamps) via `SCOPED_TRACE`. On unpatched HEAD this test fails with `inserted_ranges_.size() == 1`; with the fix it passes. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14586 Reviewed By: joshkang97 Differential Revision: D100023487 Pulled By: xingbowang fbshipit-source-id: 5ef885c89a6cfd7a97b814e38bdcc48d3a1ab349 |
||
|
Josh Kang
|
156328107d |
Fix range deletion crash test errors (#14573)
Summary: Fix two bugs in read-path range tombstone conversion (`min_tombstones_for_range_conversion`): 1. **SeekToLast stale saved_key_**: `SeekToLast()` did not clear `saved_key_` before calling `PrevInternal()`. A stale key from a prior `Seek()` would be swapped into `range_tomb_end_key_`, corrupting the tombstone tracking bounds and triggering an assertion failure when `range_tomb_first_key_ > end_key`. 2. **Tombstone inserted at wrong sequence**: The current behavior uses the "max" seqno of the tombstones as the insertion seqno. This is not correct because it does not take into account the seqno range deletions seen throughout the iteration. Unfortunately, range deletions are not visible to the db_iter as the are filtered at the merging iterator level. A future refactor may try to expose this, but currently the simplest solution is to just use the iterator seqno. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14573 Test Plan: Unit tests for both bugs that fail without the fix. Reviewed By: xingbowang Differential Revision: D99569668 Pulled By: joshkang97 fbshipit-source-id: bb1b154beccced7438831cd5cf2780ad1e11a4cc |
||
|
Josh Kang
|
3f51c0a185 |
Convert sequential single deletes into range tombstones (#14448)
Summary:
Add a read-path optimization that converts contiguous point tombstones into range tombstones during forward/reverse iteration. When a configurable threshold of consecutive point deletions (kTypeDeletion, kTypeDeletionWithTimestamp, kTypeSingleDeletion — with no live keys between them) is detected, a range tombstone covering `[first_tombstone_key, next_live_key)` is inserted into the active mutable memtable. This benefits future iterators by enabling efficient skipping via range tombstone fragmentation.
If there is a memtable switch during the read iteration, then the range deletion entry is discarded.
The inserted range tombstones are logically redundant (they don't delete anything that isn't already deleted by point tombstones), skip WAL (they're a derived optimization regenerated by future reads on crash), and use the max tombstone sequence number so they don't interfere with newer writes.
## Key changes
- **New option `min_tombstones_for_range_conversion`** (`AdvancedColumnFamilyOptions`): Threshold of contiguous point tombstones before converting to a range tombstone. Default 0 (disabled). Dynamically changeable via `SetOptions()`.
- **`DBIter` tracking logic** (`db/db_iter.cc`): Tracks contiguous tombstones during `FindNextUserEntryInternal()` (forward) and `PrevInternal()` (reverse). When a live key terminates a run that meets the threshold, `MaybeInsertRangeTombstone()` inserts `[first_tombstone, live_key)` into the active memtable.
- **`FindValueForCurrentKey` `found_visible` output** (`db/db_iter.cc`): Distinguishes "key deleted at this snapshot" from "no visible entries" so reverse tracking doesn't treat post-snapshot keys as tombstones.
- **`IterKey::Swap()`** (`db/dbformat.h`): Efficiently tracks reverse tombstone run end keys without extra allocations.
- **`MemTable::AddLogicallyRedundantRangeTombstone()`** (`db/memtable.cc`): Concurrent-safe range tombstone insertion into the active memtable. Range tombstone skiplist always uses concurrent inserts.
- **`ConstructFragmentedRangeTombstones` race fix** (`db/db_impl/db_impl_write.cc`): Moved after `MarkImmutable()` to prevent lost entries.
- **`MarkImmutable` ordering fix** (`db/memtable_list.cc`): Called before `current_->Add()` to close a race window.
- **Prefix filter awareness** (`db/db_iter.cc`): Tombstone tracking scoped to the seek prefix when prefix filtering is active. See dedicated section below.
- **Transaction awareness** (`db/db_iter.cc`): Tombstones with `seq > snapshot` excluded from tracking. `min_uncommitted` guard uses `insert_seq` (which may be bumped to `earliest_seq`) instead of `range_tomb_max_seq_`. See dedicated section below.
- **Duplicate range check**: Skips insertion if the memtable already covers `[start, end)`.
- **New statistics**: `READ_PATH_RANGE_TOMBSTONES_INSERTED` and `READ_PATH_RANGE_TOMBSTONES_DISCARDED`.
- **Memtable MultiGet batch lookup** (`memtable/inlineskiplist.h`, `db/memtable.cc`): `InlineSkipList::MultiGet()` with cached search path ("finger") for sorted key lookups.
- **New option `memtable_batch_lookup_optimization`** (`AdvancedColumnFamilyOptions`): Enables batch lookup for memtable MultiGet. Default false. Immutable.
## Deciding Range Tombstone Seqno
- The range tombstone is inserted with `insert_seq = max(range_tomb_max_seq_, earliest_seq)` where `range_tomb_max_seq_` is the maximum sequence number across all point tombstones in the contiguous run, and `earliest_seq` is the memtable's earliest sequence number. This preserves the memtable's `earliest_seqno_` invariant.
- If the iterator's snapshot sequence (`sequence_`) predates the memtable's `earliest_seq`, insertion is skipped entirely to avoid unintentionally covering entries between `sequence_` and `earliest_seq`.
## ConstructFragmentedRangeTombstones Race Fix
- `MarkImmutable()` and `ConstructFragmentedRangeTombstones()` are now called before `mutex_.Lock()` in `SwitchMemtable`, keeping this work outside the DB mutex. `MarkImmutable()` blocks concurrent `AddLogicallyRedundantRangeTombstone()` calls via `immutable_mutex_`, ensuring no range tombstones are inserted after the fragmented list is built. `MarkImmutable()` is idempotent, so `MemTableList::Add()` calling it again inside the mutex is harmless.
## Prefix Filter Safety
- When prefix filtering is active, the BBTI bloom filter may reject SST files outside the seek prefix, but the memtable (no bloom filter) returns keys across prefix boundaries. Tombstone tracking is scoped to the seek prefix so that converted range tombstones cannot cover live keys hidden in filtered files.
- `total_order_seek=true` disables prefix filtering — all files are visible, so tombstones safely span prefix boundaries.
- **Behavior change**: Seeking to an out-of-domain key with `total_order_seek=false` now treats it as total-order (prefix_ not set). When `prefix_same_as_start=true`, iterating past an out-of-domain key cleanly invalidates the iterator instead of calling `Transform()` on it (which was UB in release builds with `FixedPrefixTransform`). This is a requirement because an incorrect iterator scan could lead to a range tombstone covering a live key.
## Transaction Support
- Tombstones written by the transaction's own uncommitted writes (sequence > snapshot) are now excluded from contiguous tombstone tracking entirely at the tracking site in `FindNextUserEntryInternal()` and `PrevInternal()`. Previously, tracking relied on a `min_uncommitted` check at insertion time, but this was insufficient — a transaction's own Delete with `seq > snapshot` could extend a run of committed tombstones, and the resulting range tombstone would cover data visible to other snapshots.
- The fix skips any tombstone with `ikey_.sequence > sequence_` during tracking. If a transaction-owned tombstone appears mid-run, it flushes the accumulated committed run first, then resets tracking. This ensures only tombstones visible to the current snapshot are ever converted.
- Both WritePrepared and WriteUnprepared transactions are supported with dedicated test coverage:
- **WritePrepared**: When tombstones are committed before `Prepare()`, their seqnos are below `min_uncommitted` and insertion proceeds safely. When `Prepare()` happens first, tombstone seqnos exceed `min_uncommitted` and insertion is blocked.
- **WriteUnprepared**: Multiple unprepared batches with different seqno ranges are handled correctly. Own transaction Deletes that extend a committed tombstone run block insertion of the entire run. After rollback, data correctness is verified.
## UDT support
- When user-defined timestamps (UDT) are enabled, keys include an 8-byte timestamp suffix. The comparator, Put/Delete APIs, and ReadOptions all require timestamps.
- Forward exhaustion with UDT: `iterate_upper_bound_` is a plain user key without a timestamp suffix. It is padded with min timestamp via `AppendKeyWithMinTimestamp()` so it sorts after all entries with this user key, preserving the exclusive bound semantics.
- Reverse exhaustion with UDT: The end key comes from either the previous live key (which already has a proper timestamp suffix) or the seek target set by `SetSavedKeyToSeekForPrevTarget()` (which appends a timestamp via `SetInternalKey(..., timestamp_ub_)` and `UpdateInternalKey(..., ts)`). In both cases, the end key is already properly timestamped, so no additional padding is needed unlike forward exhaustion.
- Contiguous tombstone detection works correctly with UDT because the underlying `kTypeDeletionWithTimestamp` entries are tracked the same way as `kTypeDeletion`.
## Concurrent Iterators
- Should concurrent iterators happen to read the range at the same time, both will produce the same range and seqno entry. Only one will be accepted by the skip list and the others will be rejected. Future iterators will read the range and not even attempt to insert the range.
- There is nothing preventing similar ranges from being inserted however. Two iterators can produce overlapping ranges, but this protection would be complicated to implement and there is no evidence that it is a likely scenario yet.
Pull Request resolved: https://github.com/facebook/rocksdb/pull/14448
Test Plan:
- **Unit tests** (`db/db_iterator_test.cc`): `ReadPathRangeTombstoneTest` parameterized by forward/reverse with cases for basic insertion, non-contiguous (below threshold), memtable switch, exhausted iterator with/without bounds, direction change, mixed Delete/SingleDelete, single-delete-only runs, snapshot predating memtable, block cache tier incomplete, skip when covered by existing range, UDT basic scan, UDT exhaustion, prefix filter cross-prefix scan (`PrefixFilterCrossPrefixScanCoversLiveKey` with default/total_order_seek/prefix_same_as_start variants), stale ikey from forward-then-reverse scan (`StaleIkeyFromForwardThenReverse`), and reseek stale ikey (`ReseekStaleIkey`).
- **Concurrency test** (`db/db_test2.cc`): `DBTestConcurrentRangeTombstoneConversions` parameterized by `(allow_concurrent_memtable_write, min_tombstones_for_range_conversion)` with mixed writers, deleters, range deleters, and concurrent forward/reverse readers.
- **Transaction tests** (`utilities/transactions/write_prepared_transaction_test.cc`, `write_unprepared_transaction_test.cc`): Tests for WritePrepared (insertion allowed when tombstones committed before prepare, blocked when after; seqno bump shadowing prepared writes `RangeTombstoneSeqnoBumpShadowsPreparedWrite`) and WriteUnprepared (multiple batches, extended visibility with CalcMaxVisibleSeq, own deletions with rollback).
- **IterKey::Swap tests** (`db/dbformat_test.cc`): `IterKeySwapTest` parameterized over `(key_len, copy, use_secondary)` × 2 covering all inline/heap/pinned/secondary combinations.
- **InlineSkipList MultiGet tests** (`memtable/inlineskiplist_test.cc`): Basic, exact matches, empty, single key, randomized validation against `std::set::lower_bound`, duplicate keys with callback walk, and concurrent MultiGet with read-after-write consistency.
- **Memtable MultiGet tests** (`db/db_basic_test.cc`): Batch lookup, overwrite, flush, merge, disabled by default, paranoid checks, and snapshot tests.
- **Stress test coverage**: `min_tombstones_for_range_conversion` and `memtable_batch_lookup_optimization` options added to `db_crashtest.py` and `db_stress` flags.
- `make check` passes all tests.
### Benchmark results
Tombstones scattered randomly in clusters via `seek_nexts_to_delete` for realistic workloads.
**DB Setup A (scattered deletes, 100 per seek)**:
```
# Step 1: Create and compact
./db_bench --benchmarks=fillseq,compact --seed=1 --compression_type=none --num=1000000 --db=<DB>
# Step 2: Scatter tombstones (5000 seeks × 100 deletes ≈ 500k tombstones)
./db_bench --benchmarks=seekrandom,flush --seed=1 --compression_type=none --num=2000 \
--seek_nexts=0 --seek_nexts_to_delete=100 --use_existing_db=1 --threads=1 --db=<DB>
```
**DB Setup A2 (scattered deletes, 8 per seek)**:
```
# Step 1: Create and compact
./db_bench --benchmarks=fillseq,compact --seed=1 --compression_type=none --num=1000000 --db=<DB>
# Step 2: Scatter tombstones (5000 seeks × 8 deletes ≈ 40k tombstones)
./db_bench --benchmarks=seekrandom,flush --seed=1 --compression_type=none --num=2000 \
--seek_nexts=0 --seek_nexts_to_delete=8 --use_existing_db=1 --threads=1 --db=<DB>
```
**DB Setup B (no deletes)**:
```
./db_bench --benchmarks=fillseq,compact --seed=1 --compression_type=none --num=1000000 \
[--key_size=100] --db=<DB>
```
**Read workload** (same for all):
```
./db_bench --benchmarks=seekrandom --seek_nexts=100 --threads=8 \
--reverse_iterator={true,false} --seed=1 --use_existing_db=1 \
--compression_type=none --num=1000000 --duration=10 \
--disable_auto_compactions \
[--key_size=100] [--min_tombstones_for_range_conversion=X] --db=<DB_COPY>
```
Each workload averaged over 3 runs.
**Table 1: seekrandom forward, scattered deletes (2000 seeks × 100 deletes/seek)**
| Variant | avg ops/s | % vs main |
|---------|-----------|-----------|
| main | 2,895 | - |
| threshold=0 | 2,869 | -0.9% |
| threshold=8 | 287,334 | +9,824% |
**Table 2: seekrandom reverse, scattered deletes (2000 seeks × 100 deletes/seek)**
| Variant | avg ops/s | % vs main |
|---------|-----------|-----------|
| main | 544 | - |
| threshold=0 | 548 | +0.7% |
| threshold=8 | 206,491 | +37,860% |
**Table 3: seekrandom forward, scattered deletes (2000 seeks × 8 deletes/seek)**
| Variant | avg ops/s | % vs main |
|---------|-----------|-----------|
| main | 194,049 | - |
| threshold=0 | 195,703 | +0.9% |
| threshold=8 | 310,740 | +60.1% |
**Table 4: seekrandom reverse, scattered deletes (2000 seeks × 8 deletes/seek)**
| Variant | avg ops/s | % vs main |
|---------|-----------|-----------|
| main | 63,854 | - |
| threshold=0 | 69,266 | +8.5% |
| threshold=8 | 218,101 | +241.6% |
**Table 5: seekrandom forward, no deletes (regression check)**
| Variant | key=16B avg ops/s | % vs main | key=100B avg ops/s | % vs main |
|---------|-------------------|-----------|---------------------|-----------|
| main | 330,901 | - | 236,048 | - |
| threshold=0 | 328,398 | -0.8% | 238,055 | +0.9% |
| threshold=8 | 332,539 | +0.5% | 233,776 | -1.0% |
**Table 6: seekrandom reverse, no deletes (regression check)**
| Variant | key=16B avg ops/s | % vs main | key=100B avg ops/s | % vs main |
|---------|-------------------|-----------|---------------------|-----------|
| main | 261,445 | - | 192,177 | - |
| threshold=0 | 265,020 | +1.4% | 191,616 | -0.3% |
| threshold=8 | 250,881 | -4.0% | 189,239 | -1.5% |
Reviewed By: xingbowang
Differential Revision: D96203950
Pulled By: joshkang97
fbshipit-source-id: 06ba66ebde3c355f04671d1e681f1b1586e8751d
|
||
|
Andrew Chang
|
453ebd6f37 |
Fix MultiScan not respecting SupportedOps for async IO (#14510)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14510 When a filesystem does not return kAsyncIO in SupportedOps(), MultiScan still sends ReadAsync/Poll/AbortIO requests. Regular iterators check via CheckFSFeatureSupport in ArenaWrappedDBIter::Init and ForwardIterator, but MultiScan blindly trusted the caller-provided MultiScanArgs::use_async_io flag. Fix: In the MultiScan constructor, after scan_opts_ is initialized, check CheckFSFeatureSupport and disable use_async_io if the FS doesn't support it. Also pass the (potentially modified) scan_opts_ to Prepare() instead of the original scan_opts parameter. Reviewed By: mszeszko-meta Differential Revision: D97995735 fbshipit-source-id: 331639d950fd3cb9f491feed996d5820294beb4e |
||
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 |
||
|
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 |
||
Ryan Hancock
|
feffb67303 |
Replace Prefetch Logic in BlockBasedTableIterator with IODispatcher. (#14255)
Summary: This diff introduces the IODispatcher into the BlockBasedTableIterator. This replaces much of the prefetch logic with the logic found in IODispatcher. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14255 Test Plan: I ran the following benchmark, %change is within noise tolerance. There shouldn't be any large performance improvement with this change, more so there should also not be any performance degradation. MultiScan Benchmark: Current Branch vs Main Configuration: - Threads: 4 - Ranges per scan: 10 - Stride: 5000 - Seek nexts: 100 - Cache: Cold (dropped before each run) - Runs: 3 Results: │ Mode │ Main (ops/sec) │ Current (ops/sec) │ Change │ │ Sync │ 8,901 │ 9,032 │ +1.5% │ │ Async │ 11,297 │ 11,947 │ +5.8% │ I further run db_stress test ``` make -j32 -f crash_test.mk J=32 blackbox_crash_test ``` Against my local machine for 60 minutes, on local flash, with async-io for multiscans always on. Reviewed By: anand1976 Differential Revision: D91705195 Pulled By: krhancoc fbshipit-source-id: acf2f944e8b715e99384c8cee79f8d241eadf5b8 |
||
Anand Ananthabhotla
|
b89d290c20 |
Add MultiScan statistics (#14248)
Summary: Pull Request resolved: https://github.com/facebook/rocksdb/pull/14248 ### Overview This diff introduces the addition of multi-scan statistics to RocksDB, enhancing the database's ability to monitor and analyze performance during multi-scan operations. ### Key Changes #### Implemented Multi-Scan Statistics The following statistics were implemented to provide deeper insights into multi-scan operations: - **MULTISCAN_PREPARE_MICROS**: Measures the time (in microseconds) spent preparing for multi-scan operations. - **MULTISCAN_BLOCKS_PER_PREPARE**: Tracks the number of blocks processed per multi-scan prepare operation. - **Wasted Prefetch Blocks Count**: Counts the number of prefetched blocks that were not used (i.e., wasted) if the iterator is abandoned before accessing them. - **MULTISCAN_TOTAL_BLOCKS_SCANNED**: Tracks the total number of blocks scanned during all multi-scan operations. - **MULTISCAN_TOTAL_KEYS_SCANNED**: Measures the total number of keys scanned across all multi-scan operations. - **MULTISCAN_TOTAL_MICROS**: Captures the total time (in microseconds) spent in multi-scan operations. - **MULTISCAN_PREFETCHED_BLOCKS**: Counts the number of blocks that were prefetched during multi-scan operations. - **MULTISCAN_USED_PREFETCH_BLOCKS**: Tracks the number of prefetched blocks that were actually used during multi-scan operations. ### Impact This diff provides more fine-grained statistics for multi-scan operations, allowing developers and users to better understand and optimize the performance of their RocksDB instances. Reviewed By: krhancoc Differential Revision: D91053297 fbshipit-source-id: 7158741b9f026c0b5ce8ba1264dbd137e7fe985d |
||
|
Ryan Hancock
|
b9951ded37 |
Introducing Prepare all iterators for LevelIterator (#14100)
Summary:
This diff introduces the async prepare of all iterators within a MultiScan. The current state has each iterator be prepared as its needed, and with this diff, we prepare all iterators during the prepare phase of the Level Iterator, this will allow more time for each IO to be dispatched and serviced, increasing the odds that a block is ready as the scan seeks to it.
Benchmark is prefilled using
```
KEYSIZE=64
VALUESIZE=512
NUMKEYS=5000000
SCAN_SIZE=100
DISTANCE=25000
NUM_SCANS=15
THREADS=1
./db_bench --db=$DB \
--benchmarks="fillseq" \
--write_buffer_size=5242880 \
--max_write_buffer_number=4 \
--target_file_size_base=5242880 \
--disable_wal=1 --key_size=$KEYSIZE \
--value_size=$VALUESIZE --num=$NUMKEYS --threads=32
}
```
And benchmark ran is
```
run() {
echo 1 | sudo tee /proc/sys/vm/drop_caches
./db_bench --db=$DB --use_existing_db=1 \
--benchmarks=multiscan \
--disable_auto_compactions=1 --seek_nexts=$SCAN_SIZE \
--multiscan-use-async-io=1 \
--multiscan-size=$NUM_SCANS --multiscan-stride=$DISTANCE \
--key_size=$KEYSIZE --value_size=$VALUESIZE \
--num=$NUMKEYS --threads=$THREADS --duration=60 --statistics
}
```
The benchmark uses large stride sides to ensure that two scans would touch separate files. We reduce the size of the block cache to increase likelyhood of reads (and simulate larger data sets)
**Branch:**
```
Integrated BlobDB: blob cache disabled
RocksDB: version 10.8.0
Date: Tue Nov 11 13:26:29 2025
CPU: 166 * AMD EPYC-Milan Processor
CPUCache: 512 KB
Keys: 64 bytes each (+ 0 bytes user-defined timestamp)
Values: 512 bytes each (256 bytes after compression)
Entries: 5000000
Prefix: 0 bytes
Keys per prefix: 0
RawSize: 2746.6 MB (estimated)
FileSize: 1525.9 MB (estimated)
Write rate: 0 bytes/second
Read rate: 0 ops/second
Compression: Snappy
Compression sampling rate: 0
Memtablerep: SkipListFactory
Perf Level: 1
------------------------------------------------
multiscan_stride = 25000
multiscan_size = 15
seek_nexts = 100
DB path: [/data/rocksdb/mydb]
multiscan : 837.941 micros/op 1193 ops/sec 60.001 seconds 71605 operations; (multscans:71605)
```
**Baseline:**
```
Set seed to 1762898809121995 because --seed was 0
Initializing RocksDB Options from the specified file
Initializing RocksDB Options from command-line flags
Integrated BlobDB: blob cache disabled
RocksDB: version 10.9.0
Date: Tue Nov 11 14:06:49 2025
CPU: 166 * AMD EPYC-Milan Processor
CPUCache: 512 KB
Keys: 64 bytes each (+ 0 bytes user-defined timestamp)
Values: 512 bytes each (256 bytes after compression)
Entries: 5000000
Prefix: 0 bytes
Keys per prefix: 0
RawSize: 2746.6 MB (estimated)
FileSize: 1525.9 MB (estimated)
Write rate: 0 bytes/second
Read rate: 0 ops/second
Compression: Snappy
Compression sampling rate: 0
Memtablerep: SkipListFactory
Perf Level: 1
------------------------------------------------
multiscan_stride = 25000
multiscan_size = 15
seek_nexts = 100
DB path: [/data/rocksdb/mydb]
multiscan : 1129.916 micros/op 885 ops/sec 60.001 seconds 53102 operations; (multscans:53102)
```
Repeated for confirmation.
This introduces a ~20% improvement in latency and op/s.
Note: Benchmarks are single threaded as, when increasing thread count, we start seeing large amounts of overhead being induced by block cache contention, finally resulting in both baseline and branch becoming equal.
Further on network attached storage with high latency, the level iterator, preparing all iterators so a 20% improvement even at high thread counts.
Pull Request resolved: https://github.com/facebook/rocksdb/pull/14100
Reviewed By: anand1976
Differential Revision: D86913584
Pulled By: krhancoc
fbshipit-source-id: da9d0c890e25e392a33389ce6b80f9bfb84d3f85
|
||
Changyu Bi
|
ea75cdc493 |
Fix a bug in MultiScan that moves iterator backward (#14106)
Summary:
MultiScanUnexpectedSeekTarget() currently uses user key comparison to decide on the next data block for multiscan. This can cause a multiscan to move backward in the following scenario:
data block 1: ..., k@7, k@6
data block 2: k@5, ...
DB iter scan through k@7, k@6 and k@5 and decides to seek to k@0 due to option [`max_sequential_skip_in_iterations`](
|
||
|
Changyu Bi
|
144e9f1e42 |
Fix compaction picking with L0 standalone range deletion file (#14061)
Summary: When a standalone range deletion file is ingested in L0, currently it is compacted with any overlapping L0 files. This is not desirable when we ingest new data on top of the range deletion file. This PR fixes the compaction picking logic to only consider L0 files older than the standalone range deletion file. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14061 Test Plan: added a new unit test and updated an existing one. Reviewed By: xingbowang Differential Revision: D84930780 Pulled By: cbi42 fbshipit-source-id: 65f4403ccb40ba964b9e65b09e2f7f7efebe81df |
||
anand76
|
112ff5bb70 |
Allow empty MultiScan result in BlockBasedTableIterator Prepare (#14046)
Summary: Currently in BlockBasedTableIterator's Prepare(), the index lookup for a MultiScan range is expected to return atleast 1 data block (unless UDI is in use). This is because there's an implicit assumption that only ranges intersecting with the keys in the file will be prepared. This assumption, however, doesn't hold if there are range deletions and the smallest and/or largest keys in the file extend beyond the keys in the file. The LevelIterator prunes the MultiScan ranges based on the smallest/largest key, so its possible for a range to only overlap the range deletion portion of the file and not overlap any of the data blocks. Furthermore, the BlockBasedTableIterator is now much more forgiving of Seek to targets outside of prepared ranges after https://github.com/facebook/rocksdb/issues/14040 . Keeping the above in mind, this PR removes the check in BlockBasedTableIterator for non-empty index result. It adds assertions in LevelIterator to verify that ranges are being properly pruned. Another side effect is we can no longer rely solely on a scan range having 0 data blocks (i.e cur_scan_start_idx >= cur_scan_end_idx) to decide if the iterator is out of bound. We can only do so for all but the last range prepared range. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14046 Test Plan: 1. Add unit test in db_iterator_test 2. Run crash test Reviewed By: xingbowang Differential Revision: D84623871 Pulled By: anand1976 fbshipit-source-id: 2418e629f92b1c46c555ddea3761140f700819e4 |
||
Xingbo Wang
|
1585f2240c |
Move the MultiScan seek key check to upper layer (#14040)
Summary: The current seek key validation is too strict. This change relaxes it at block iterator level, and add additional check at DB iterator level. The new contract is that when MultiScan is used, after prepared is called, each following seek must seek the start key of the prepared scan range in order. Otherwise, the iterator is set with error status. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14040 Test Plan: Unit test Reviewed By: anand1976 Differential Revision: D84292297 Pulled By: xingbowang fbshipit-source-id: 7b31f727e67e7c0bfc53c2f9a6552e0c3d324869 |
||
|
anand76
|
035242415f |
Fix incorrect MultiScan handling of range limit between files (#14011)
Summary: This PR fixes a bug in how MultiScan handled a scan range limit falling in the key range between files. The bug was in LevelIterator, where Prepare() relied on FindFile to determine the lower bound file for the range limit. FindFile returns the smallest file index with `range.limit < file.largest_key`. However, that doesn't guarantee that the range overlaps the file, as the `range.limit` could be smaller than `file.smallest_key`. This also fixes a bug in BlockBasedTableIterator of Valid() returning true even if status() returned error. This was exposed by the previous bug. Pull Request resolved: https://github.com/facebook/rocksdb/pull/14011 Test Plan: Add unit tests in db_iterator_test and table_test Reviewed By: cbi42 Differential Revision: D83496439 Pulled By: anand1976 fbshipit-source-id: a9d2d138d69d0c816d9f4160a984b273d00d683f |
||
|
Changyu Bi
|
862438a7a1 |
Fix handling of out-of-range scan option (#13995)
Summary: currently BlockBasedTableIterator::Prepare() fails the iterator with non-ok status if an out-of-range scan option is detected. This is due to the interaction between LevelIterator and BlockBasedTableIterator, see added comment above BlockBasedTableIterator::Prepare(). This can fail stress test for L0 files since it doesn't use LevelIterator and scan options are not pruned. This PR fixes this by adding an internal option to MultiScanArgs that enables this check. Pull Request resolved: https://github.com/facebook/rocksdb/pull/13995 Test Plan: - new unit test - stress test that fails before this pr: `python3 -u ./tools/db_crashtest.py whitebox --iterpercent=60 --prefix_size=-1 --prefixpercent=0 --readpercent=0 --test_batches_snapshots=0 --use_multiscan=1 --read_fault_one_in=0 --kill_random_test=88888 --interval=60 --multiscan_use_async_io=0 --mmap_read=0 --level0_file_num_compaction_trigger=20` Reviewed By: anand1976 Differential Revision: D83166088 Pulled By: cbi42 fbshipit-source-id: 241a7d43c8c00d9a98eea0cabb03d2174d51aae5 |
||
|
anand76
|
afbbc90b06 |
Fail multi scan upon Prepare failure or bad scan options (#13974)
Summary: Return a failure status for multi scan if Prepare fails, or if the scan options are unsupported, instead of falling back on a regular scan. This PR also fixes a bug in LevelIterator that caused max_prefetch_size to be ignored. Pull Request resolved: https://github.com/facebook/rocksdb/pull/13974 Test Plan: Add new test in db_iterator_test and table_test Reviewed By: xingbowang Differential Revision: D82843944 Pulled By: anand1976 fbshipit-source-id: f12756c40ebd38d8d4e4425e97438b6e766a4663 |
||
|
anand76
|
a5d4db64e2 |
Fix multiscan crash when fill_cache=false (#13889)
Summary: When fill_cache is ReadOptions is false, multi scan Prepare crashes with the following assertion failure. In this case, CreateAndPibBlockInCache needs to directly create a block with full ownership. https://github.com/facebook/rocksdb/issues/9 0x00007f2fc003bc93 in __GI___assert_fail (assertion=0x7f2fc2147361 "pinned_data_blocks_guard[block_idx].GetValue()", file=0x7f2fc2146e08 "table/block_based/block_based_table_iterator.cc", line=1178, function=0x7f2fc2147262 "virtual void rocksdb::BlockBasedTableIterator::Prepare(const rocksdb::MultiScanArgs *)") at assert.c:101 101 in assert.c https://github.com/facebook/rocksdb/issues/10 0x00007f2fc1d73088 in rocksdb::BlockBasedTableIterator::Prepare(rocksdb::MultiScanArgs const*) () from /data/users/anand76/rocksdb_anand76/librocksdb.so.10.6 Pull Request resolved: https://github.com/facebook/rocksdb/pull/13889 Test Plan: Parameterize the DBMultiScanIteratorTest tests with fill_cache Reviewed By: cbi42 Differential Revision: D80552069 Pulled By: anand1976 fbshipit-source-id: 1a0b64af1e14c63d826add1f994a832ebff12757 |
||
|
Ryan Hancock
|
0b44282a9d |
Introduction of MultiScanOptions (#13837)
Summary: To better support future options, and changes, we need to convert the std::vector<ScanOptions> to something more malleable. This diff introduces the MultiScanOptions structure and pipes it through the various points in the code in the Prepare path. Pull Request resolved: https://github.com/facebook/rocksdb/pull/13837 Test Plan: Ensure all associated tests pass ``` make check all ``` Reviewed By: cbi42 Differential Revision: D79655229 Pulled By: krhancoc fbshipit-source-id: 3a90fb7420e9655021de85ed0158b866f8bfba05 |
||
|
Changyu Bi
|
ccd850fa56 |
Bug fix in MultiScan and stress test (#13822)
Summary: Fix a bug in MultiScan where BlockBasedTableIterator should not return out-of-bound when the all blocks of the last scan are exhausted. This prevented LevelIterator from entering the next file so iterator is returning less keys than expected. Also fixed stress testing to specify iterate_upper_bound correctly. Pull Request resolved: https://github.com/facebook/rocksdb/pull/13822 Test Plan: - the following fails quickly before this PR and finishes after this PR ```python3 tools/db_crashtest.py whitebox --iterpercent=60 --prefix_size=-1 --prefixpercent=0 --readpercent=0 --test_batches_snapshots=0 --use_multiscan=1 --seed=1 --fill_cache=1 --read_fault_one_in=0 --column_families=1 --allow_unprepared_value=0 --kill_random_test=88888``` - new unit test that fails before this PR Reviewed By: krhancoc Differential Revision: D79308957 Pulled By: cbi42 fbshipit-source-id: c9eafd1c8750b959b0185d7c63199b503493cbd2 |
||
|
anand76
|
8b84390517 |
Add upper bound support for forward scans in MultiScan (#13723)
Summary: Respect the scan upper bound/limit, if specified, in `MultiScan`. This applies to block based table and other native RocksDB SSTs. In order to properly support it, the `MultiScan` object caches the `ReadOptions` passed by the user and sets the `iterate_upper_bound` as appropriate. We optimize for the case of either all scans specifying the upper bound, or none of them. In case of mixed scans, we reallocate the DB iterator anytime `ReadOptions` has to be updated. Tests: New unit tests in `db_iterator_test` Pull Request resolved: https://github.com/facebook/rocksdb/pull/13723 Reviewed By: cbi42 Differential Revision: D77385049 Pulled By: anand1976 fbshipit-source-id: 9c02d125770cbedbe6e8c10767ba537e7f7540e1 |
||
|
Changyu Bi
|
5bc8abc0ec |
New CF option to trigger flush based on average cost of scanning memtable (#13593)
Summary: This PR introduces a new CF option, `memtable_avg_op_scan_flush_trigger`, to support triggering a memtable flush when an iterator skips too many invisible keys from the active memtable. This is a follow up to https://github.com/facebook/rocksdb/pull/13523#discussion_r2038261975, which introduced the option `memtable_op_scan_flush_trigger` for a single expensive iterator step. This PR focus on an expensive stretch of iterator steps, between Seeks and until iterator destruction. To avoid triggering a memtable flush for a stretch that is too small, this option only takes effect when the total number of entries skipped from the active memtable in a stretch of iterator steps exceeds `memtable_op_scan_flush_trigger`. Pull Request resolved: https://github.com/facebook/rocksdb/pull/13593 Test Plan: * New unit tests covering the new option * Add the option to the crash test. Reviewed By: hx235 Differential Revision: D74434263 Pulled By: cbi42 fbshipit-source-id: 64f1101efb79c7498e2038eff630713ead8f6f41 |
||
|
Changyu Bi
|
56359da691 |
Trigger memtable flush based on number of hidden entries scanned (#13523)
Summary: Introduce a mutable CF option `memtable_op_scan_flush_trigger`. When a DB iterator scans this number of hidden entries (tombstones, overwritten puts) from the active memtable in a Seek() or Next() operation, it marks the memtable to be eligible for flush. Subsequent write operations will schedule the marked memtable for flush. The main change is small and is in db_iter.cc. Some refactoring is done to consolidate and simplify creation of `ArenaWrappedDBIter` and `DBIter`. Pull Request resolved: https://github.com/facebook/rocksdb/pull/13523 Test Plan: - new unit tests added. - added `memtable_op_scan_flush_trigger` in crash test - benchmark: The following benchmark was done with a previous version of the PR where the option was `memtable_tombstone_scan_limit` and it concerns tombstone only. The results should still be applicable for the case when there's no overwritten puts. Tests that when memtable has many tombstones, the option helps to improve scan performance: ``` TEST_TMPDIR=/dev/shm ./db_bench --benchmarks=seekrandomwhilewriting --expand_range_tombstones=true --writes_per_range_tombstone=1 --max_num_range_tombstones=10000000 --perf_level=2 --range_tombstone_width=100 --memtable_tombstone_scan_limit= memtable_tombstone_scan_limit = 10000 seekrandomwhilewriting : 18.527 micros/op 53973 ops/sec 18.527 seconds 1000000 operations; (7348 of 1000000 found) next_on_memtable_count = 122305248 grep "flush_started" /dev/shm/dbbench/LOG | wc 8 200 2417 memtable_tombstone_scan_limit=200 seekrandomwhilewriting : 4.918 micros/op 203315 ops/sec 4.918 seconds 1000000 operations; (4510 of 1000000 found) next_on_memtable_count = 1853167 grep "flush_started" /dev/shm/dbbench/LOG | wc 184 4600 54121 When memtable_tombstone_scan_limit=200, more flush is trigged to drop tombstones sooner and improve scan performance. ``` Tests that the new option does not introduce noticeable regression: ``` TEST_TMPDIR=/dev/shm ./db_bench --benchmarks=seekrandomwhilewriting[-X5] --expand_range_tombstones=true --writes_per_range_tombstone=1 --max_num_range_tombstones=10000000 --perf_level=2 --range_tombstone_width=100 --seed=123 Main: seekrandomwhilewriting [AVG 5 runs] : 46049 (± 4512) ops/sec PR: seekrandomwhilewriting [AVG 5 runs] : 46100 (± 4470) ops/sec The results are noisy with this PR performing better and worse in different runs, with no noticeable regression. ``` Reviewed By: pdillinger Differential Revision: D72596434 Pulled By: cbi42 fbshipit-source-id: 2d51a0221dc20dac844aeba2ad3999d075a4cf91 |
||
|
Maciej Szeszko
|
8234d67e5a |
Auto refresh iterator with snapshot (#13354)
Summary: # Problem Once opened, iterator will preserve its' respective RocksDB snapshot for read consistency. Unless explicitly `Refresh'ed`, the iterator will hold on to the `Init`-time assigned `SuperVersion` throughout its lifetime. As time goes by, this might result in artificially long holdup of the obsolete memtables (_potentially_ referenced by that superversion alone) consequently limiting the supply of the reclaimable memory on the DB instance. This behavior proved to be especially problematic in case of _logical_ backups (outside of RocksDB `BackupEngine`). # Solution Building on top of the `Refresh(const Snapshot* snapshot)` API introduced in https://github.com/facebook/rocksdb/pull/10594, we're adding a new `ReadOptions` opt-in knob that (when enabled) will instruct the iterator to automatically refresh itself to the latest superversion - all that while retaining the originally assigned, explicit snapshot (supplied in `read_options.snapshot` at the time of iterator creation) for consistency. To ensure minimal performance overhead we're leveraging relaxed atomic for superversion freshness lookups. Pull Request resolved: https://github.com/facebook/rocksdb/pull/13354 Test Plan: **Correctness:** New test to demonstrate the auto refresh behavior in contrast to legacy iterator: `./db_iterator_test --gtest_filter=*AutoRefreshIterator*`. **Stress testing:** We're adding command line parameter controlling the feature and hooking it up to as many iterator use cases in `db_stress` as we reasonably can with random feature on/off configuration in db_crashtest.py. # Benchmarking The goal of this benchmark is to validate that throughput did not regress substantially. Benchmark was run on optimized build, 3-5 times for each respective category or till convergence. In addition, we configured aggressive threshold of 1 second for new `Superversion` creation. Experiments have been run 'in parallel' (at the same time) on separate db instances within a single host to evenly spread the potential adverse impact of noisy neighbor activities. Host specs [1]. **TLDR;** Baseline & new solution are practically indistinguishable from performance standpoint. Difference (positive or negative) in throughput relative to the baseline, if any, is no more than 1-2%. **Snapshot initialization approach:** This feature is only effective on iterators with well-defined `snapshot` passed via `ReadOptions` config. We modified the existing `db_bench` program to reflect that constraint. However, it quickly turned out that the actual `Snapshot*` initialization is quite expensive. Especially in case of 'tiny scans' (100 rows) contributing as much as 25-35 microseconds, which is ~20-30% of the average per/op latency unintentionally masking _potentially_ adverse performance impact of this change. As a result, we ended up creating a single, explicit 'global' `Snapshot*` for all the future scans _before_ running multiple experiments en masse. This is also a valuable data point for us to keep in mind in case of any future discussions about taking implicit snapshots - now we know what the lower bound cost could be. ## "DB in memory" benchmark **DB Setup** 1. Allow a single memtable to grow large enough (~572MB) to fit in all the rows. Upon shutdown all the rows will be flushed to the WAL file (inspected `000004.log` file is 541MB in size). ``` ./db_bench -db=/tmp/testdb_in_mem -benchmarks="fillseq" -key_size=32 -value_size=512 -num=1000000 -write_buffer_size=600000000 max_write_buffer_number=2 -compression_type=none ``` 2. As a part of recovery in subsequent DB open, WAL will be processed to one or more SST files during the recovery. We're selecting a large block cache (`cache_size` parameter in `db_bench` script) suitable for holding the entire DB to test the “hot path” CPU overhead. ``` ./db_bench -use_existing_db=true -db=/tmp/testdb_in_mem -statistics=false -cache_index_and_filter_blocks=true -benchmarks=seekrandom -preserve_internal_time_seconds=1 max_write_buffer_number=2 -explicit_snapshot=1 -use_direct_reads=1 -async_io=1 -num=? -seek_nexts=? -cache_size=? -write_buffer_size=? -auto_refresh_iterator_with_snapshot={0|1} ``` | seek_nexts=100; num=2,000,000 | seek_nexts = 20,000; num=50000 | seek_nexts = 400,000; num=2000 -- | -- | -- | -- baseline | 36362 (± 300) ops/sec, 928.8 (± 23) MB/s, 99.11% block cache hit | 52.5 (± 0.5) ops/sec, 1402.05 (± 11.85) MB/s, 99.99% block cache hit | 156.2 (± 6.3) ms / op, 1330.45 (± 54) MB/s, 99.95% block cache hit auto refresh | 35775.5 (± 537) ops/sec, 926.65 (± 13.75) MB/s, 99.11% block cache hit | 53.5 (± 0.5) ops/sec, 1367.9 (± 9.5) MB/s, 99.99% block cache hit | 162 (± 4.14) ms / op, 1281.35 (± 32.75) MB/s, 99.95% block cache hit _-cache_size=5000000000 -write_buffer_size=3200000000 -max_write_buffer_number=2_ | seek_nexts=3,500,000; num=100 -- | -- baseline | 1447.5 (± 34.5) ms / op, 1255.1 (± 30) MB/s, 98.98% block cache hit auto refresh | 1473.5 (± 26.5) ms / op, 1232.6 (± 22.2) MB/s, 98.98% block cache hit _-cache_size=17680000000 -write_buffer_size=14500000000 -max_write_buffer_number=2_ | seek_nexts=17,500,000; num=10 -- | -- baseline | 9.11 (± 0.185) s/op, 997 (± 20) MB/s auto refresh | 9.22 (± 0.1) s/op, 984 (± 11.4) MB/s [1] ### Specs | Property | Value -- | -- RocksDB | version 10.0.0 Date | Mon Feb 3 23:21:03 2025 CPU | 32 * Intel Xeon Processor (Skylake) CPUCache | 16384 KB Keys | 16 bytes each (+ 0 bytes user-defined timestamp) Values | 100 bytes each (50 bytes after compression) Prefix | 0 bytes RawSize | 5.5 MB (estimated) FileSize | 3.1 MB (estimated) Compression | Snappy Compression sampling rate | 0 Memtablerep | SkipListFactory Perf Level | 1 Reviewed By: pdillinger Differential Revision: D69122091 Pulled By: mszeszko-meta fbshipit-source-id: 147ef7c4fe9507b6fb77f6de03415bf3bec337a8 |
||
Andrew Kryczka
|
4eaf628120 |
Add Iterator property "rocksdb.iterator.is-value-pinned" (#12659)
Summary: `ReadOptions::pin_data` already has the effect of pinning the `Slice` returned by `Iterator::value()` when the value is stored inline (e.g., `kTypeValue`). This PR adds a bit of visibility into that via a new `Iterator` property, "rocksdb.iterator.is-value-pinned", as well as some documentation and tests. See also: https://github.com/facebook/rocksdb/issues/12658 Pull Request resolved: https://github.com/facebook/rocksdb/pull/12659 Reviewed By: cbi42 Differential Revision: D57391200 Pulled By: ajkr fbshipit-source-id: 0caa8db27ca1aba86ee2addc3dfd6f0e003d32e2 |
||
|
Jay Huh
|
f16ba42116 |
Fix IteratorsConsistentView tests (#12582)
Summary: Fixing the failure in IteratorsConsistentViewExplicitSnapshot as shown in https://github.com/facebook/rocksdb/actions/runs/8825927545/job/24230854140?pr=12581 The failure was due to the timing of the `flush()` for the later Column Family in the loop. If the flush for the later CFs installs the new super version before getting the SV for the iterator, assertion succeeds, but if the order flips, SV will be obsolete and assertion can fail. This PR simplifies the test in a way that we do only one `flush()` so that `SYNC_POINT` can guarantee the order of operations. For ImplicitSnapshot test, it now just triggers flush for the second CF after obtaining SV for the first CF. For the ExplicitSnapshot test, it now triggers atomic flush() for all CFs after obtaining SV for the first CF. Pull Request resolved: https://github.com/facebook/rocksdb/pull/12582 Test Plan: ``` ./db_iterator_test --gtest_filter="*IteratorsConsistentView*" ./multi_cf_iterator_test -- --gtest_filter="*ConsistentView* ``` Reviewed By: ajkr, jowlyzhang Differential Revision: D56557234 Pulled By: jaykorean fbshipit-source-id: 7aa2f6d0e12a915b6e16cd240389bcfb5b4a5b62 |
||
|
Jay Huh
|
1fca175eec |
MultiCFSnapshot for NewIterators() API (#12573)
Summary: As mentioned in https://github.com/facebook/rocksdb/issues/12561 and https://github.com/facebook/rocksdb/issues/12566 , `NewIterators()` API has not been providing consistent view of the db across multiple column families. This PR addresses it by utilizing `MultiCFSnapshot()` function which has been used for `MultiGet()` APIs. To be able to obtain the thread-local super version with ref, `sv_exclusive_access` parameter has been added to `MultiCFSnapshot()` so that we could call `GetReferencedSuperVersion()` or `GetAndRefSuperVersion()` depending on the param and support `Refresh()` API for MultiCfIterators Pull Request resolved: https://github.com/facebook/rocksdb/pull/12573 Test Plan: **Unit Tests Added** ``` ./db_iterator_test --gtest_filter="*IteratorsConsistentView*" ``` ``` ./multi_cf_iterator_test -- --gtest_filter="*ConsistentView*" ``` **Performance Check** Setup ``` make -j64 release TEST_TMPDIR=/dev/shm/db_bench ./db_bench -benchmarks="filluniquerandom" -key_size=32 -value_size=512 -num=10000000 -compression_type=none ``` Run ``` TEST_TMPDIR=/dev/shm/db_bench ./db_bench -use_existing_db=1 -benchmarks="multireadrandom" -cache_size=10485760000 ``` Before the change ``` DB path: [/dev/shm/db_bench/dbbench] multireadrandom : 6.374 micros/op 156892 ops/sec 6.374 seconds 1000000 operations; (0 of 1000000 found) ``` After the change ``` DB path: [/dev/shm/db_bench/dbbench] multireadrandom : 6.265 micros/op 159627 ops/sec 6.265 seconds 1000000 operations; (0 of 1000000 found) ``` Reviewed By: jowlyzhang Differential Revision: D56444066 Pulled By: jaykorean fbshipit-source-id: 327ce73c072da30c221e18d4f3389f49115b8f99 |
||
Yu Zhang
|
f2546b6623 |
Support returning write unix time in iterator property (#12428)
Summary: This PR adds support to return data's approximate unix write time in the iterator property API. The general implementation is: 1) If the entry comes from a SST file, the sequence number to time mapping recorded in that file's table properties will be used to deduce the entry's write time from its sequence number. If no such recording is available, `std::numeric_limits<uint64_t>::max()` is returned to indicate the write time is unknown except if the entry's sequence number is zero, in which case, 0 is returned. This also means that even if `preclude_last_level_data_seconds` and `preserve_internal_time_seconds` can be toggled off between DB reopens, as long as the SST file's table property has the mapping available, the entry's write time can be deduced and returned. 2) If the entry comes from memtable, we will use the DB's sequence number to write time mapping to do similar things. A copy of the DB's seqno to write time mapping is kept in SuperVersion to allow iterators to have lock free access. This also means a new `SuperVersion` is installed each time DB's seqno to time mapping updates, which is originally proposed by Peter in https://github.com/facebook/rocksdb/issues/11928 . Similarly, if the feature is not enabled, `std::numeric_limits<uint64_t>::max()` is returned to indicate the write time is unknown. Needed follow up: 1) The write time for `kTypeValuePreferredSeqno` should be special cased, where it's already specified by the user, so we can directly return it. 2) Flush job can be updated to use DB's seqno to time mapping copy in the SuperVersion. 3) Handle the case when `TimedPut` is called with a write time that is `std::numeric_limits<uint64_t>::max()`. We can make it a regular `Put`. Pull Request resolved: https://github.com/facebook/rocksdb/pull/12428 Test Plan: Added unit test Reviewed By: pdillinger Differential Revision: D54967067 Pulled By: jowlyzhang fbshipit-source-id: c795b1b7ec142e09e53f2ed3461cf719833cb37a |
||
|
Jay Huh
|
c00c16855d |
Access DBImpl* and CFD* by CFHImpl* in Iterators (#12395)
Summary: In the current implementation of iterators, `DBImpl*` and `ColumnFamilyData*` are held in `DBIter` and `ArenaWrappedDBIter` for two purposes: tracing and Refresh() API. With the introduction of a new iterator called MultiCfIterator in PR https://github.com/facebook/rocksdb/issues/12153 , which is a cross-column-family iterator that maintains multiple DBIters as child iterators from a consistent database state, we need to make some changes to the existing implementation. The new iterator will still be exposed through the generic Iterator interface with an additional capability to return AttributeGroups (via `attribute_groups()`) which is a list of wide columns grouped by column family. For more information about AttributeGroup, please refer to previous PRs: https://github.com/facebook/rocksdb/issues/11925 #11943, and https://github.com/facebook/rocksdb/issues/11977. To be able to return AttributeGroup in the default single CF iterator created, access to `ColumnFamilyHandle*` within `DBIter` is necessary. However, this is not currently available in `DBIter`. Since `DBImpl*` and `ColumnFamilyData*` can be easily accessed via `ColumnFamilyHandleImpl*`, we have decided to replace the pointers to `ColumnFamilyData` and `DBImpl` in `DBIter` with a pointer to `ColumnFamilyHandleImpl`. Pull Request resolved: https://github.com/facebook/rocksdb/pull/12395 Test Plan: # Summary In the current implementation of iterators, `DBImpl*` and `ColumnFamilyData*` are held in `DBIter` and `ArenaWrappedDBIter` for two purposes: tracing and Refresh() API. With the introduction of a new iterator called MultiCfIterator in PR #12153 , which is a cross-column-family iterator that maintains multiple DBIters as child iterators from a consistent database state, we need to make some changes to the existing implementation. The new iterator will still be exposed through the generic Iterator interface with an additional capability to return AttributeGroups (via `attribute_groups()`) which is a list of wide columns grouped by column family. For more information about AttributeGroup, please refer to previous PRs: #11925 #11943, and #11977. To be able to return AttributeGroup in the default single CF iterator created, access to `ColumnFamilyHandle*` within `DBIter` is necessary. However, this is not currently available in `DBIter`. Since `DBImpl*` and `ColumnFamilyData*` can be easily accessed via `ColumnFamilyHandleImpl*`, we have decided to replace the pointers to `ColumnFamilyData` and `DBImpl` in `DBIter` with a pointer to `ColumnFamilyHandleImpl`. # Test Plan There should be no behavior changes. Existing tests and CI for the correctness tests. **Test for Perf Regression** Build ``` $> make -j64 release ``` Setup ``` $> TEST_TMPDIR=/dev/shm/db_bench ./db_bench -benchmarks="filluniquerandom" -key_size=32 -value_size=512 -num=1000000 -compression_type=none ``` Run ``` TEST_TMPDIR=/dev/shm/db_bench ./db_bench -use_existing_db=1 -benchmarks="newiterator,seekrandom" -cache_size=10485760000 ``` Before the change ``` DB path: [/dev/shm/db_bench/dbbench] newiterator : 0.552 micros/op 1810157 ops/sec 0.552 seconds 1000000 operations; DB path: [/dev/shm/db_bench/dbbench] seekrandom : 4.502 micros/op 222143 ops/sec 4.502 seconds 1000000 operations; (0 of 1000000 found) ``` After the change ``` DB path: [/dev/shm/db_bench/dbbench] newiterator : 0.520 micros/op 1924401 ops/sec 0.520 seconds 1000000 operations; DB path: [/dev/shm/db_bench/dbbench] seekrandom : 4.532 micros/op 220657 ops/sec 4.532 seconds 1000000 operations; (0 of 1000000 found) ``` Reviewed By: pdillinger Differential Revision: D54332713 Pulled By: jaykorean fbshipit-source-id: b28d897ad519e58b1ca82eb068a6319544a4fae5 |
||
|
Peter Dillinger
|
54cb9c77d9 |
Prefer static_cast in place of most reinterpret_cast (#12308)
Summary: The following are risks associated with pointer-to-pointer reinterpret_cast: * Can produce the "wrong result" (crash or memory corruption). IIRC, in theory this can happen for any up-cast or down-cast for a non-standard-layout type, though in practice would only happen for multiple inheritance cases (where the base class pointer might be "inside" the derived object). We don't use multiple inheritance a lot, but we do. * Can mask useful compiler errors upon code change, including converting between unrelated pointer types that you are expecting to be related, and converting between pointer and scalar types unintentionally. I can only think of some obscure cases where static_cast could be troublesome when it compiles as a replacement: * Going through `void*` could plausibly cause unnecessary or broken pointer arithmetic. Suppose we have `struct Derived: public Base1, public Base2`. If we have `Derived*` -> `void*` -> `Base2*` -> `Derived*` through reinterpret casts, this could plausibly work (though technical UB) assuming the `Base2*` is not dereferenced. Changing to static cast could introduce breaking pointer arithmetic. * Unnecessary (but safe) pointer arithmetic could arise in a case like `Derived*` -> `Base2*` -> `Derived*` where before the Base2 pointer might not have been dereferenced. This could potentially affect performance. With some light scripting, I tried replacing pointer-to-pointer reinterpret_casts with static_cast and kept the cases that still compile. Most occurrences of reinterpret_cast have successfully been changed (except for java/ and third-party/). 294 changed, 257 remain. A couple of related interventions included here: * Previously Cache::Handle was not actually derived from in the implementations and just used as a `void*` stand-in with reinterpret_cast. Now there is a relationship to allow static_cast. In theory, this could introduce pointer arithmetic (as described above) but is unlikely without multiple inheritance AND non-empty Cache::Handle. * Remove some unnecessary casts to void* as this is allowed to be implicit (for better or worse). Most of the remaining reinterpret_casts are for converting to/from raw bytes of objects. We could consider better idioms for these patterns in follow-up work. I wish there were a way to implement a template variant of static_cast that would only compile if no pointer arithmetic is generated, but best I can tell, this is not possible. AFAIK the best you could do is a dynamic check that the void* conversion after the static cast is unchanged. Pull Request resolved: https://github.com/facebook/rocksdb/pull/12308 Test Plan: existing tests, CI Reviewed By: ltamasi Differential Revision: D53204947 Pulled By: pdillinger fbshipit-source-id: 9de23e618263b0d5b9820f4e15966876888a16e2 |