database/rocksdb
1
0
Fork 0
mirror of https://github.com/facebook/rocksdb.git synced 2026-10-23 08:09:02 +03:00
Code Activity
14,217 Commits 290 Branches 299 Tags
main
Commit Graph

12 Commits

Author SHA1 Message Date
Josh Kang
4b983da055 Spell out special member functions (rule of five) (#15387) 
Summary:
Pull Request resolved: https://github.com/facebook/rocksdb/pull/15387

## Summary

RocksDB's `.clang-tidy` enables `cppcoreguidelines-special-member-functions`,
`cppcoreguidelines-virtual-class-destructor` and the noexcept-move checks,
and clang warns `-Wdeprecated-copy-with-user-provided-dtor`. A full scan
reports 476 findings. In most of them, a class declares a destructor (or
copy operations) but leaves the rest of copy/move implicit. That has two
costs. Readers can't tell whether a class may be copied or moved. And
resource-owning classes keep an implicit copy that would double-free if
anyone ever used it. This diff resolves 453 of the 476.

Approach, picked per class from least to most invasive:
1. An empty user-provided destructor becomes `= default`. This covers most
   interface classes, such as `virtual ~X() {}` -> `= default`. If the
   class is still copied, that would only rename the deprecated-copy
   warning, so the destructor is removed instead when nothing needs it
   (`Customizable`, `TableFactory` and `InternalKeyComparator` inherit a
   virtual one; `IteratorWrapperBase` isn't polymorphic), and
   `MemTableRep::KeyComparator` gets defaulted copy and move.
2. Classes whose copy is already deleted get explicitly deleted move
   operations too. Move was already unavailable, so this only documents
   it.
3. Resource-owning classes that are never copied get deleted copy and move
   operations. Examples: the C API wrapper structs, which run a
   `destructor_` callback (edited in `tools/c_api_gen/c_base.cc` and
   regenerated into `db/c.cc`); `ShardedCache`, which frees its shards;
   iterator wrappers; and RAII handles.
4. Value types that are copied or moved get the missing operations as
   `= default`, which keeps their current behavior.
5. Exception specifications of existing functions are unchanged, except
   for `WriteBatch`'s move assignment (below): no other `noexcept` is
   added or removed. Only the move operations this diff
   newly declares (`Comparator`, `FileSampledStats` and the thread-local
   `Entry`) are `noexcept`; they copy only scalars or atomics.

`WriteBatch`'s copy and move assignment destroyed `*this` and
placement-new'ed a new `WriteBatch` over it. That is undefined behavior
when `*this` is a subclass, and if the copy constructor threw, `*this`
was left destroyed and was later destroyed again. Move assignment now
assigns member-wise and ends in the same state as the move constructor,
which leaves `has_key_with_ts_`, the timestamp-size tracking and the
other fields it doesn't copy at their defaults. `rep_` is swapped through
a temporary, because a plain string move-assignment can keep the old
buffer (e.g. a large batch reset with `batch = WriteBatch()` would keep
its memory). Nothing in it can throw, so it is now `noexcept`. Copy
assignment copies into a temporary and moves it in, so a throwing copy
leaves `*this` unchanged.

Bugs this exposed and fixed:
- `RestoreAfterCopyOrCreateWorkItem` (backup engine): the hand-written
  move constructor and assignment moved only some fields, so `from_file`
  and `to_file` were empty after `push_back(std::move(...))`. A restore
  that hit a checksum mismatch then reported "While restoring  -> : ..."
  without file names. It now uses the compiler-generated moves, which
  are still `noexcept`.
- `ExternalSstFileIngestionJob` lived in a `std::vector`, and its
  destructor frees raw-owned pointers, so the implicit copy used on
  vector reallocation would double-free. Its file batches also point into
  its own inline file storage, so neither a copy nor a move is safe after
  `Prepare()`. Copy and move are now deleted, and `DBImpl` holds jobs
  through `std::unique_ptr`.

Compatibility: no public class loses an operation users can call. Public
interfaces mostly only get `virtual ~X() = default;`.
`WriteBatch`'s move assignment becomes `noexcept`, which is not part of
the mangled name, so the ABI doesn't change.
`SubcompactionJobInfo` and `CompactionJobInfo` intentionally stay C++20
aggregates, so users' aggregate and designated initializers keep
compiling. `Configurable`, `CompareInterface`, `WriteBatchBase`,
`ObjectLibrary::Entry` and `MemTableRep::KeyComparator` declare defaulted
copy and move, and `Customizable` no longer declares a destructor. As a
result, `Configurable` and `Customizable` subclasses that declare no
destructor or copy operations of their own now move their
registered-options list instead of copying it. In-tree, these are the
mutable-options adapters, the table factories, the memory allocators and
test classes; all are held through smart pointers or used in place, and
`Clone()` copies, so none is moved by value.

Not changed (23): `IODebugContext` (custom deep copy plus a
`std::shared_mutex`), `DBWithColumnFamilies` in db_bench (stored in a
`std::vector` with non-movable members), `Snapshot`'s protected virtual
destructor (intended), `ManagedSnapshot`, the `SubcompactionJobInfo` and
`CompactionJobInfo` aggregates, and the 16 noexcept-move-constructor and
noexcept-swap findings on existing functions, including `autovector`'s
move assignment (adding `noexcept` would change their exception
specifications). Copying `ManagedSnapshot` already double-releases the
snapshot. Fixing that needs a real move implementation and is a behavior
change, so it is left for a separate diff.

Reviewed By: rban1

Differential Revision: D123186309

fbshipit-source-id: 6f8e57e233e12199a007407130bb9a1f6d52e8d1
 2026-10-12 16:00:09 -07:00
Xingbo Wang
4c2a977aa5 Track newer snapshot versions in RocksDB metadata reads (#15086) 
Summary:
Pull Request resolved: https://github.com/facebook/rocksdb/pull/15086

Why: An application built on top of RocksDB could use cache population reads through explicit snapshots and needs to know when the returned value has already been superseded, without a second point read.

Previous behavior: Get and MultiGet returned the snapshot-visible value and optional timestamp but could not report a newer point update or covering range deletion.

New behavior: experimental C++, C, and Java metadata-read APIs report newer committed puts, deletes, merges, and covering range tombstones; ordinary primary-DB writes completed before the read are guaranteed to be reported, racing writes remain best-effort, and true has no false positives.

Implementation: metadata reads widen lookup behind read-callback hooks while keeping metadata-only state off passive common object layouts; per-key state stays in KeyContext/GetContext, ordinary MultiGet row-cache replay semantics are preserved, BlobDB/TTL use shared output helpers, dead single-CF plumbing and an invalid cross-key stress assertion are removed, and the range-tombstone ordering invariant is documented without changing behavior.

Safety and unsupported cases: tracking is opt-in and requires an explicit snapshot; persisted-tier reads, custom transactional visibility callbacks, secondary DBs, and unsupported subclasses return NotSupported, while read-only/compacted DBs return false because their in-process views are static.

Tests and limitations: 1,265 Buck tests plus focused metadata, 100x coerced-context-switch row-cache, write-committed/write-prepared crash tests, builds, and lint passed. Current-parent release db_bench found no material passive regression: readrandom +0.65%, MultiGet batch 4 -1.40%, and batch 32 +0.48%.

Reviewed By: pdillinger

Differential Revision: D104182397

fbshipit-source-id: 36f7be1cd50fe2383689adaae31a6bb7d7e462dc
 2026-09-11 04:44:59 -07:00
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
 2026-04-03 22:47:51 -07:00
Peter Dillinger
bda8d93ba9 Fix and detect headers with missing dependencies (#8893) 
Summary:
It's always annoying to find a header does not include its own
dependencies and only works when included after other includes. This
change adds `make check-headers` which validates that each header can
be included at the top of a file. Some headers are excluded e.g. because
of platform or external dependencies.

rocksdb_namespace.h had to be re-worked slightly to enable checking for
failure to include it. (ROCKSDB_NAMESPACE is a valid namespace name.)

Fixes mostly involve adding and cleaning up #includes, but for
FileTraceWriter, a constructor was out-of-lined to make a forward
declaration sufficient.

This check is not currently run with `make check` but is added to
CircleCI build-linux-unity since that one is already relatively fast.

Pull Request resolved: https://github.com/facebook/rocksdb/pull/8893

Test Plan: existing tests and resolving issues detected by new check

Reviewed By: mrambacher

Differential Revision: D30823300

Pulled By: pdillinger

fbshipit-source-id: 9fff223944994c83c105e2e6496d24845dc8e572
 2021-09-10 10:00:26 -07:00
Yanqin Jin
d758273ceb Get() with timestamp should respect snapshot (#7227) 
Summary:
If user-defined timestamp is enabled, current implementation can expose
newer data to queries even if an older sequence number is specified via
read_options.snapshot. This PR makes Get() respect sequence-number-based
snapshot.

Solution is simple. Besides using <ukey, ts, seq> to search the index for the key,
we also verify that the candidate result's seq is smaller than or equal to seq. This
requires passing a seq via `GetContext`, which results in the majority of code
change caused by this PR.

Also added a few unit tests to demonstrate standard visibility during point lookup
and range scan when timestamp and snapshot are both present.

Test plan (devserver):
```
make check
$./db_bench --benchmarks=fillseq,readrandom -cache_size=$[64*1024*1024]
```
Result
this PR: readrandom   :       4.827 micros/op 207180 ops/sec;   22.9 MB/s (1000000 of 1000000 found)
master:  readrandom   :       4.936 micros/op 202610 ops/sec;   22.4 MB/s (1000000 of 1000000 found)

Pull Request resolved: https://github.com/facebook/rocksdb/pull/7227

Reviewed By: ltamasi

Differential Revision: D23015242

Pulled By: riversand963

fbshipit-source-id: ea7b85a728654553ba357d2e6a207b5e40f7376a
 2020-08-14 19:20:58 -07:00
sdong
fdf882ded2 Replace namespace name "rocksdb" with ROCKSDB_NAMESPACE (#6433) 
Summary:
When dynamically linking two binaries together, different builds of RocksDB from two sources might cause errors. To provide a tool for user to solve the problem, the RocksDB namespace is changed to a flag which can be overridden in build time.
Pull Request resolved: https://github.com/facebook/rocksdb/pull/6433

Test Plan: Build release, all and jtest. Try to build with ROCKSDB_NAMESPACE with another flag.

Differential Revision: D19977691

fbshipit-source-id: aa7f2d0972e1c31d75339ac48478f34f6cfcfb3e
 2020-02-20 12:09:57 -08:00
Manuel Ung
eae832740b WriteUnPrepared: improve read your own write functionality (#5573) 
Summary:
There are a number of fixes in this PR (with most bugs found via the added stress tests):
1. Re-enable reseek optimization. This was initially disabled to avoid infinite loops in https://github.com/facebook/rocksdb/pull/3955 but this can be resolved by remembering not to reseek after a reseek has already been done. This problem only affects forward iteration in `DBIter::FindNextUserEntryInternal`, as we already disable reseeking in `DBIter::FindValueForCurrentKeyUsingSeek`.
2. Verify that ReadOption.snapshot can be safely used for iterator creation. Some snapshots would not give correct results because snaphsot validation would not be enforced, breaking some assumptions in Prev() iteration.
3. In the non-snapshot Get() case, reads done at `LastPublishedSequence` may not be enough, because unprepared sequence numbers are not published. Use `std::max(published_seq, max_visible_seq)` to do lookups instead.
4. Add stress test to test reading own writes.
5. Minor bug in the allow_concurrent_memtable_write case where we forgot to pass in batch_per_txn_.
6. Minor performance optimization in `CalcMaxUnpreparedSequenceNumber` by assigning by reference instead of value.
7. Add some more comments everywhere.
Pull Request resolved: https://github.com/facebook/rocksdb/pull/5573

Differential Revision: D16276089

Pulled By: lth

fbshipit-source-id: 18029c944eb427a90a87dee76ac1b23f37ec1ccb
 2019-07-23 08:08:19 -07:00
Maysam Yabandeh
fe642cbee6 WritePrepared: fix race condition in reading batch with duplicate keys (#5147) 
Summary:
When ReadOption doesn't specify a snapshot, WritePrepared::Get used kMaxSequenceNumber to avoid the cost of creating a new snapshot object (that requires sync over db_mutex). This creates a race condition if it is reading from the writes of a transaction that had duplicate keys: each instance of duplicate key is inserted with a different sequence number and depending on the ordering the ::Get might skip the newer one and read the older one that is obsolete.
The patch fixes that by using last published seq as the snapshot sequence number. It also adds a check after the read is done to ensure that the max_evicted_seq has not advanced the aforementioned seq, which is a very unlikely event. If it did, then the read is not valid since the seq is not backed by an actually snapshot to let IsInSnapshot handle that properly when an overlapping commit is evicted from commit cache.
A unit  test is added to reproduce the race condition with duplicate keys.
Pull Request resolved: https://github.com/facebook/rocksdb/pull/5147

Differential Revision: D14758815

Pulled By: maysamyabandeh

fbshipit-source-id: a56915657132cf6ba5e3f5ea1b5d78c803407719
 2019-04-12 14:40:41 -07:00
Maysam Yabandeh
14b3f683a1 WriteUnPrepared: less virtual in iterator callback (#5049) 
Summary:
WriteUnPrepared adds a virtual function, MaxUnpreparedSequenceNumber, to ReadCallback, which returns 0 unless WriteUnPrepared is enabled and the transaction has uncommitted data written to the DB. Together with snapshot sequence number, this determines the last sequence that is visible to reads.
The patch clarifies the guarantees of the GetIterator API in WriteUnPrepared transactions and make use of that to statically initialize the read callback and thus avoid the virtual call.
Furthermore it increases the minimum value for min_uncommitted from 0 to 1 as seq 0 is used only for last level keys that are committed in all snapshots.

The following benchmark shows +0.26% higher throughput in seekrandom benchmark.

Benchmark:
./db_bench --benchmarks=fillrandom --use_existing_db=0 --num=1000000 --db=/dev/shm/dbbench

./db_bench --benchmarks=seekrandom[X10] --use_existing_db=1 --db=/dev/shm/dbbench --num=1000000 --duration=60 --seek_nexts=100
seekrandom [AVG    10 runs] : 20355 ops/sec;  225.2 MB/sec
seekrandom [MEDIAN 10 runs] : 20425 ops/sec;  225.9 MB/sec

./db_bench_lessvirtual3 --benchmarks=seekrandom[X10] --use_existing_db=1 --db=/dev/shm/dbbench --num=1000000 --duration=60 --seek_nexts=100
seekrandom [AVG    10 runs] : 20409 ops/sec;  225.8 MB/sec
seekrandom [MEDIAN 10 runs] : 20487 ops/sec;  226.6 MB/sec
Pull Request resolved: https://github.com/facebook/rocksdb/pull/5049

Differential Revision: D14366459

Pulled By: maysamyabandeh

fbshipit-source-id: ebaff8908332a5ae9af7defeadabcb624be660ef
 2019-04-02 14:47:16 -07:00
Maysam Yabandeh
a661c0d208 WritePrepared: optimize read path by avoiding virtual (#5018) 
Summary:
The read path includes a callback function, ReadCallback, which would eventually calls IsInSnapshot to figure if a particular seq is in the reading snapshot or not. This callback is virtual, which adds the cost of multiple virtual function call to each read. The first few checks in IsInSnapshot, however, are quite trivial and take care of majority of the cases. The patch moves those to a non-virtual function in the the parent class, ReadCallback, to lower the virtual callback cost.
Pull Request resolved: https://github.com/facebook/rocksdb/pull/5018

Differential Revision: D14226562

Pulled By: maysamyabandeh

fbshipit-source-id: 6feed5b34f3b082e52092c5ef143e29b49c46b44
 2019-02-26 16:56:19 -08:00
Manuel Ung
a16e00b7b9 WriteUnPrepared Txn: Disable seek to snapshot optimization (#3955) 
Summary:
This is implemented by extending ReadCallback with another function `MaxUnpreparedSequenceNumber` which returns the largest visible sequence number for the current transaction, if there is uncommitted data written to DB. Otherwise, it returns zero, indicating no uncommitted data.

There are the places where reads had to be modified.
- Get and Seek/Next was just updated to seek to max(snapshot_seq, MaxUnpreparedSequenceNumber()) instead, and iterate until a key was visible.
- Prev did not need need updates since it did not use the Seek to sequence number optimization. Assuming that locks were held when writing unprepared keys, and ValidateSnapshot runs, there should only be committed keys and unprepared keys of the current transaction, all of which are visible. Prev will simply iterate to get the last visible key.
- Reseeking to skip keys optimization was also disabled for write unprepared, since it's possible to hit the max_skip condition even while reseeking. There needs to be some way to resolve infinite looping in this case.
Closes https://github.com/facebook/rocksdb/pull/3955

Differential Revision: D8286688

Pulled By: lth

fbshipit-source-id: 25e42f47fdeb5f7accea0f4fd350ef35198caafe
 2018-06-27 12:23:07 -07:00
Maysam Yabandeh
f46464d383 write-prepared txn: call IsInSnapshot 
Summary:
This patch instruments the read path to verify each read value against an optional ReadCallback class. If the value is rejected, the reader moves on to the next value. The WritePreparedTxn makes use of this feature to skip sequence numbers that are not in the read snapshot.
Closes https://github.com/facebook/rocksdb/pull/2850

Differential Revision: D5787375

Pulled By: maysamyabandeh

fbshipit-source-id: 49d808b3062ab35e7ae98ad388f659757794184c
 2017-09-11 09:14:48 -07:00