Separate internal and user key comparators in `BlockIter` by ajkr · Pull Request #6944 · facebook/rocksdb

ajkr · 2020-06-05T21:00:06Z

Replace BlockIter::comparator_ and IndexBlockIter::user_comparator_wrapper_ with a concrete UserComparatorWrapper and InternalKeyComparator. The motivation for this change was the inconvenience of not knowing the concrete type of BlockIter::comparator_, which prevented calling specialized internal key comparison functions to optimize comparison of keys with global seqno applied.

Test Plan:

benchmark setup -- single file DBs, in-memory, no compression. "normal_db"
created by regular flush; "ingestion_db" created by ingesting a file. Both
DBs have same contents.

$ TEST_TMPDIR=/dev/shm/normal_db/ ./db_bench -benchmarks=fillrandom,compact -write_buffer_size=10485760000 -disable_auto_compactions=true -compression_type=none -num=1000000
$ ./ldb write_extern_sst ./tmp.sst --db=/dev/shm/ingestion_db/dbbench/ --compression_type=no --hex --create_if_missing < <(./sst_dump --command=scan --output_hex --file=/dev/shm/normal_db/dbbench/000007.sst | awk 'began {print "0x" substr($1, 2, length($1) - 2), "==>", "0x" $5} ; /^Sst file format: block-based/ {began=1}')
$ ./ldb ingest_extern_sst ./tmp.sst --db=/dev/shm/ingestion_db/dbbench/

benchmark run command:

$ TEST_TMPDIR=/dev/shm/$DB/ ./db_bench -benchmarks=seekrandom -seek_nexts=$SEEK_NEXT -use_existing_db=true -cache_index_and_filter_blocks=false -num=1000000 -cache_size=0 -threads=1 -reads=200000000 -mmap_read=1 -verify_checksum=false

results: perf increased significantly for ingestion_db (enough to cover the losses in #6843) and changed negligibly for normal_db:

SEEK_NEXT	DB	code	ops/sec	% change
0	normal_db	master	378879
0	normal_db	PR6944	376974	-0.5
0	ingestion_db	master	357010
0	ingestion_db	PR6944	394068	10.4
10	normal_db	master	235596
10	normal_db	PR6944	237640	0.9
10	ingestion_db	master	216041
10	ingestion_db	PR6944	234371	8.5

facebook-github-bot

@ajkr has imported this pull request. If you are a Facebook employee, you can view this diff on Phabricator.

facebook-github-bot · 2020-06-27T00:52:22Z

@ajkr has updated the pull request. Re-import the pull request

facebook-github-bot · 2020-06-30T02:53:01Z

@ajkr has updated the pull request. Re-import the pull request

facebook-github-bot · 2020-06-30T07:19:01Z

@ajkr has updated the pull request. Re-import the pull request

facebook-github-bot

@ajkr has imported this pull request. If you are a Facebook employee, you can view this diff on Phabricator.

pdillinger

More review to come

util/user_comparator_wrapper.h

table/block_based/block_test.cc

facebook-github-bot · 2020-07-01T23:15:50Z

@ajkr has updated the pull request. Re-import the pull request

facebook-github-bot · 2020-07-02T00:22:29Z

@ajkr has updated the pull request. Re-import the pull request

pdillinger

LGTM! :)

I would request before landing: 'make check' under valgrind, and preemptively run stress test for a little while.

pdillinger · 2020-07-02T22:23:39Z

Perf note in HISTORY.md also might be warranted. Up to you.

facebook-github-bot · 2020-07-07T19:58:42Z

@ajkr has updated the pull request. Re-import the pull request

facebook-github-bot

@ajkr has imported this pull request. If you are a Facebook employee, you can view this diff on Phabricator.

ajkr · 2020-07-07T20:51:33Z

LGTM! :)

Thanks for the review!

I would request before landing: 'make check' under valgrind, and preemptively run stress test for a little while.

Done, ran:

$ make -j48 valgrind_test
$ python tools/db_crashtest.py blackbox --simple -write_buffer_size=1048576 -target_file_size_base=1048576 -max_bytes_for_level_base=4194304 -value_size_mult=33 -max_key=1000000 --duration=1200 --interval=20

Perf note in HISTORY.md also might be warranted. Up to you.

Done.

The test failure (e.g., ./librocksdb_stress_debug.so: undefined reference to alternative_rocksdb_ns::test::SetupSyncPointsToMockDirectIO()'`) looks unrelated.

facebook-github-bot · 2020-07-08T00:48:31Z

@ajkr merged this pull request in dd29ad4.

PR facebook#6944 transitioned `BlockIter` from using `Comparator*` to using concrete `UserComparatorWrapper` and `InternalKeyComparator`. However, adding them as instance variables to `BlockIter` was not optimal. Bloating `BlockIter` caused the `ArenaWrappedDBIter`'s arena allocator to do more heap allocations which harmed performance of `DB::NewIterator()`. This PR pushes down the concrete comparator objects to the point of usage, which forces them to be on the stack. As a result, the `BlockIter` is back to its original size prior to facebook#6944 (actually a bit smaller since there were two `Comparator*` before). Test Plan: verified our internal `DB::NewIterator()`-heavy regression test no longer reports regression.

Summary: PR #6944 transitioned `BlockIter` from using `Comparator*` to using concrete `UserComparatorWrapper` and `InternalKeyComparator`. However, adding them as instance variables to `BlockIter` was not optimal. Bloating `BlockIter` caused the `ArenaWrappedDBIter`'s arena allocator to do more heap allocations (in certain cases) which harmed performance of `DB::NewIterator()`. This PR pushes down the concrete comparator objects to the point of usage, which forces them to be on the stack. As a result, the `BlockIter` is back to its original size prior to #6944 (actually a bit smaller since there were two `Comparator*` before). Pull Request resolved: #7149 Test Plan: verified our internal `DB::NewIterator()`-heavy regression test no longer reports regression. Reviewed By: riversand963 Differential Revision: D22623189 Pulled By: ajkr fbshipit-source-id: f6d69accfe5de51e0bd9874a480b32b29909bab6

Summary: PR facebook#6944 transitioned `BlockIter` from using `Comparator*` to using concrete `UserComparatorWrapper` and `InternalKeyComparator`. However, adding them as instance variables to `BlockIter` was not optimal. Bloating `BlockIter` caused the `ArenaWrappedDBIter`'s arena allocator to do more heap allocations (in certain cases) which harmed performance of `DB::NewIterator()`. This PR pushes down the concrete comparator objects to the point of usage, which forces them to be on the stack. As a result, the `BlockIter` is back to its original size prior to facebook#6944 (actually a bit smaller since there were two `Comparator*` before). Pull Request resolved: facebook#7149 Test Plan: verified our internal `DB::NewIterator()`-heavy regression test no longer reports regression. Reviewed By: riversand963 Differential Revision: D22623189 Pulled By: ajkr fbshipit-source-id: f6d69accfe5de51e0bd9874a480b32b29909bab6

facebook-github-bot added the CLA Signed label Jun 5, 2020

ajkr force-pushed the refactor-block-iter-internal-vs-user-key branch 3 times, most recently from fd10a11 to 2212f0b Compare June 7, 2020 23:55

facebook-github-bot reviewed Jun 7, 2020

View reviewed changes

ajkr force-pushed the refactor-block-iter-internal-vs-user-key branch from 2212f0b to d3cdfd2 Compare June 27, 2020 00:52

ajkr force-pushed the refactor-block-iter-internal-vs-user-key branch from d3cdfd2 to 4a01817 Compare June 30, 2020 02:52

facebook-github-bot reviewed Jun 30, 2020

View reviewed changes

pdillinger assigned pdillinger and unassigned pdillinger Jun 30, 2020

pdillinger self-requested a review June 30, 2020 19:18

pdillinger reviewed Jul 1, 2020

View reviewed changes

util/user_comparator_wrapper.h Outdated Show resolved Hide resolved

table/block_based/block_test.cc Outdated Show resolved Hide resolved

ajkr force-pushed the refactor-block-iter-internal-vs-user-key branch from 1667475 to c87dd92 Compare July 1, 2020 23:15

pdillinger approved these changes Jul 2, 2020

View reviewed changes

ajkr added 10 commits July 7, 2020 11:38

explicitly choose comparator in BlockIter and DataBlockIter

79aaa86

migrate to CompareCurrentKey()

9a2dccb

replace GlobalSeqnoAppliedKey with UpdateKey at end of each operation

410d82f

Add InternalKey::Compare that does global seqno override

815bc27

minor fixups/cleanups

0fe9432

use IsUserKey() consistently to determine block contents

abef19b

make format

6bc6ccb

move UpdateKey to public APIs only

3b6d15a

avoid InternalKeyComparator name allocation/copy

f882e49

satisfy clang

a6806f1

ajkr added 3 commits July 7, 2020 11:38

address comments so far

b3f8846

more comments

5204048

update HISTORY.md

bdf25f3

ajkr force-pushed the refactor-block-iter-internal-vs-user-key branch from 76b413c to bdf25f3 Compare July 7, 2020 19:58

facebook-github-bot reviewed Jul 7, 2020

View reviewed changes

facebook-github-bot closed this in dd29ad4 Jul 8, 2020

facebook-github-bot added the Merged label Jul 8, 2020

ajkr mentioned this pull request Jul 20, 2020

minimize BlockIter comparator scope #7149

Closed

andrew-kryczka mentioned this pull request Oct 27, 2025

eliminate per-iterator heap allocation by constructing InternalKeyComparator in-place #14044

Closed

Conversation

ajkr commented Jun 5, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

facebook-github-bot left a comment

Choose a reason for hiding this comment

Uh oh!

facebook-github-bot commented Jun 27, 2020

Uh oh!

facebook-github-bot commented Jun 30, 2020

Uh oh!

facebook-github-bot commented Jun 30, 2020

Uh oh!

facebook-github-bot left a comment

Choose a reason for hiding this comment

Uh oh!

pdillinger left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

facebook-github-bot commented Jul 1, 2020

Uh oh!

facebook-github-bot commented Jul 2, 2020

Uh oh!

pdillinger left a comment

Choose a reason for hiding this comment

Uh oh!

pdillinger commented Jul 2, 2020

Uh oh!

facebook-github-bot commented Jul 7, 2020

Uh oh!

facebook-github-bot left a comment

Choose a reason for hiding this comment

Uh oh!

ajkr commented Jul 7, 2020

Uh oh!

facebook-github-bot commented Jul 8, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

ajkr commented Jun 5, 2020 •

edited

Loading