Eliminate unnecessary (slow) block cache Ref()ing in MultiGet #9899
Conversation
Summary: When MultiGet() determines that multiple query keys can be served by examining the same data block in block cache (one Lookup()), each PinnableSlice referring to data in that data block needs to hold on to the block in cache so that they can be released at arbitrary times by the API user. Historically this is accomplished with extra calls to Ref() on the Handle from Lookup(), with each PinnableSlice cleanup calling Release() on the Handle, but this creates extra contention on the block cache for the extra Ref()s and Release()es, especially because they hit the same cache shard repeatedly. In the case of merge operands (possibly more cases?), the problem was compounded by doing an extra Ref()+eventual Release() for each merge operand for a key reusing a block (which could be the same key!), rather than one Ref() per key. (Note: the non-shared case with `biter` was already one per key.) This change optimizes MultiGet not to rely on these extra, contentious Ref()+Release() calls by instead, in the shared block case, wrapping the cache Release() cleanup in a refcounted object referenced by the PinnableSlices, such that after the last wrapped reference is released, the cache entry is Release()ed. Relaxed atomic refcounts should be much faster than mutex-guarded Ref() and Release(), and much less prone to a performance cliff when MultiGet() does a lot of block sharing. Note that I did not use std::shared_ptr, because that would require an extra indirection object (shared_ptr itself new/delete) in order to associate a ref increment/decrement with a Cleanable cleanup entry. (If I assumed it was the size of two pointers, I could do some hackery to make it work without the extra indirection, but that's too fragile.) Some details: * Moved existing implementations for cleanable.h from iterator.cc to new cleanable.cc * Improved API comments on Cleanable * Added a public SharedCleanablePtr class to cleanable.h in case others could benefit from the same pattern (potentially many Cleanables and/or smart pointers referencing a shared Cleanable) * Add a typedef for MultiGetContext::Mask * Some variable renaming for clarity Test Plan: existing tests, with ASAN etc. TODO? I'm considering adding some more tests and maybe doing performance test
util/cleanable.cc
Outdated
| return ptr_; // implicit upcast | ||
| } | ||
|
|
||
| void SharedCleanablePtr::RegisterCopyWith(Cleanable *target) { |
There was a problem hiding this comment.
I'll try using this with the GetMergeOperands() PinnableSlices. It'd clean up https://github.com/ajkr/rocksdb/blob/8fc4fb31ad1793ec3ed43209c2ca274bd6fa6ff4/db/db_impl/db_impl.cc#L1993-L2011 (prototype code).
| Cleanable* const value_pinner = biter; | ||
| if (biter->IsValuePinned()) { |
There was a problem hiding this comment.
Should value_pinner be nullptr when !biter->IsValuePinned()?
There was a problem hiding this comment.
Thanks for catching!
|
@pdillinger has imported this pull request. If you are a Meta employee, you can view this diff on Phabricator. |
|
@pdillinger has updated the pull request. You must reimport the pull request before landing. |
|
@pdillinger has imported this pull request. If you are a Meta employee, you can view this diff on Phabricator. |
| assert(biter->HasCleanups()); | ||
| shared_cleanable.Allocate(); | ||
| biter->DelegateCleanupsTo(&*shared_cleanable); | ||
| shared_cleanable.RegisterCopyWith(biter); |
There was a problem hiding this comment.
I was a bit confused about how this PR works until I looked closely at these 2 lines. Essentially, we're swapping the cleanup functions of biter and shared_cleanable (sort of). The cleanup of biter (UnrefWrapper) is then delegated to the value PinnableSlice. The shared_cleanable cleanup function (ForceReleaseCachedEntry) releases the cache handle.
There was a problem hiding this comment.
I'll add to HISTORY.md and some comments here.
|
@pdillinger has updated the pull request. You must reimport the pull request before landing. |
|
@pdillinger has imported this pull request. If you are a Meta employee, you can view this diff on Phabricator. |
|
@pdillinger has updated the pull request. You must reimport the pull request before landing. |
|
@pdillinger has imported this pull request. If you are a Meta employee, you can view this diff on Phabricator. |
|
@pdillinger has updated the pull request. You must reimport the pull request before landing. |
|
@pdillinger has imported this pull request. If you are a Meta employee, you can view this diff on Phabricator. |
Summary: There was a bug in the MultiGet enhancement in facebook#9899 with data block hash index, which was not caught because data block hash index was never added to stress tests. This change fixes both issues. Fixes facebook#10186 I intend to pick this into the 7.4.0 release candidate Test Plan: Failure quickly reproduces in crash test with kDataBlockBinaryAndHash, and does not seem to with the fix. Reproducing the failure with a unit test I believe would be too tricky and fragile to be worthwhile.
Summary: There was a bug in the MultiGet enhancement in #9899 with data block hash index, which was not caught because data block hash index was never added to stress tests. This change fixes both issues. Fixes #10186 I intend to pick this into the 7.4.0 release candidate Pull Request resolved: #10220 Test Plan: Failure quickly reproduces in crash test with kDataBlockBinaryAndHash, and does not seem to with the fix. Reproducing the failure with a unit test I believe would be too tricky and fragile to be worthwhile. Reviewed By: anand1976 Differential Revision: D37315647 Pulled By: pdillinger fbshipit-source-id: 9f648265bba867275edc752f7a56611a59401cba
…#10220) Summary: There was a bug in the MultiGet enhancement in facebook#9899 with data block hash index, which was not caught because data block hash index was never added to stress tests. This change fixes both issues. Fixes facebook#10186 I intend to pick this into the 7.4.0 release candidate Pull Request resolved: facebook#10220 Test Plan: Failure quickly reproduces in crash test with kDataBlockBinaryAndHash, and does not seem to with the fix. Reproducing the failure with a unit test I believe would be too tricky and fragile to be worthwhile. Reviewed By: anand1976 Differential Revision: D37315647 Pulled By: pdillinger fbshipit-source-id: 9f648265bba867275edc752f7a56611a59401cba
Summary: When MultiGet() determines that multiple query keys can be
served by examining the same data block in block cache (one Lookup()),
each PinnableSlice referring to data in that data block needs to hold
on to the block in cache so that they can be released at arbitrary
times by the API user. Historically this is accomplished with extra
calls to Ref() on the Handle from Lookup(), with each PinnableSlice
cleanup calling Release() on the Handle, but this creates extra
contention on the block cache for the extra Ref()s and Release()es,
especially because they hit the same cache shard repeatedly.
In the case of merge operands (possibly more cases?), the problem was
compounded by doing an extra Ref()+eventual Release() for each merge
operand for a key reusing a block (which could be the same key!), rather
than one Ref() per key. (Note: the non-shared case with
biterwasalready one per key.)
This change optimizes MultiGet not to rely on these extra, contentious
Ref()+Release() calls by instead, in the shared block case, wrapping
the cache Release() cleanup in a refcounted object referenced by the
PinnableSlices, such that after the last wrapped reference is released,
the cache entry is Release()ed. Relaxed atomic refcounts should be
much faster than mutex-guarded Ref() and Release(), and much less prone
to a performance cliff when MultiGet() does a lot of block sharing.
Note that I did not use std::shared_ptr, because that would require an
extra indirection object (shared_ptr itself new/delete) in order to
associate a ref increment/decrement with a Cleanable cleanup entry. (If
I assumed it was the size of two pointers, I could do some hackery to
make it work without the extra indirection, but that's too fragile.)
Some details:
entry reuse in MultiGet, but it's likely that in some other cases traces
are missing (XXX comment inserted)
new cleanable.cc
could benefit from the same pattern (potentially many Cleanables and/or
smart pointers referencing a shared Cleanable)
Test Plan:
Added unit tests for SharedCleanablePtr.
Greatly enhanced ability of existing tests to detect cache use-after-free.
bulk (in db_test_util wrapper).
so that entries are immediately erased when unreferenced. (Updated two
tests that depend on caching.) New ASAN testsuite running time seems
OK to me.
If I introduce a bug into my implementation where we skip the shared
cleanups on block reuse, ASAN detects the bug in
db_basic_test *MultiGet*. If I remove either of the above testingenhancements, the bug is not detected.
Consider for follow-up work: manipulate or randomize ordering of
PinnableSlice use and release from MultiGet db_test_util wrapper. But in
typical cases, natural ordering gives pretty good functional coverage.
Performance test:
In the extreme (but possible) case of MultiGetting the same or adjacent keys
in a batch, throughput can improve by an order of magnitude.
./db_bench -benchmarks=multireadrandom -db=/dev/shm/testdb -readonly -num=5 -duration=10 -threads=20 -multiread_batched -batch_size=200Before ops/sec, num=5: 1,384,394
Before ops/sec, num=500: 6,423,720
After ops/sec, num=500: 10,658,794
After ops/sec, num=5: 16,027,257
Also note that previously, with high parallelism, having query keys
concentrated in a single block was worse than spreading them out a bit. Now
concentrated in a single block is faster than spread out, which is hopefully
consistent with natural expectation.
Random query performance: with num=1000000, over 999 x 10s runs running before & after simultaneously (each -threads=12):
Before: multireadrandom [AVG 999 runs] : 1088699 (± 7344) ops/sec; 120.4 (± 0.8 ) MB/sec
After: multireadrandom [AVG 999 runs] : 1090402 (± 7230) ops/sec; 120.6 (± 0.8 ) MB/sec
Possibly better, possibly in the noise.