`CompactRange()` always compacts to bottommost level for leveled compaction by cbi42 · Pull Request #11468 · facebook/rocksdb

cbi42 · 2023-05-22T16:49:08Z

Summary: currently for leveled compaction, the max output level of a call to CompactRange() is pre-computed before compacting each level. This max output level is the max level whose key range overlaps with the manual compaction key range. However, during manual compaction, files in the max output level may be compacted down further by some background compaction. When this background compaction is a trivial move, there is a race condition and the manual compaction may not be able to compact all keys in the specified key range. This PR updates CompactRange() to always compact to the bottommost level to make this race condition more unlikely (it can still happen, see more in comment here: https://github.com/cbi42/rocksdb/blob/796f58f42ad1bdbf49e5fcf480763f11583b790e/db/db_impl/db_impl_compaction_flush.cc#L1180C29-L1184).

This PR also changes the behavior of CompactRange() when bottommost_level_compaction=kIfHaveCompactionFilter (the default option). The old behavior is that, if a compaction filter is provided, CompactRange() always does an intra-level compaction at the final output level for all files in the manual compaction key range. The only exception when first_overlapped_level = 0 and max_overlapped_level = 0. It’s awkward to maintain the same behavior after this PR since we do not compute max_overlapped_level anymore. So the new behavior is similar to kForceOptimized: always does intra-level compaction at the bottommost level, but not including new files generated during this manual compaction.

Several unit tests are updated to work with this new manual compaction behavior.

Test plan: Add new unit tests DBCompactionTest.ManualCompactionCompactAllKeysInRange*

facebook-github-bot · 2023-05-22T18:46:10Z

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

cbi42 · 2023-05-22T20:39:34Z

db/db_test2.cc

    ASSERT_EQ(fm + 3, TestGetTickerCount(options, BLOCK_CACHE_FILTER_MISS));
    ASSERT_EQ(fh, TestGetTickerCount(options, BLOCK_CACHE_FILTER_HIT));
    ASSERT_EQ(im + 3, TestGetTickerCount(options, BLOCK_CACHE_INDEX_MISS));
-    ASSERT_EQ(ih + 3, TestGetTickerCount(options, BLOCK_CACHE_INDEX_HIT));


Since we no longer read more levels to compute max_overlapped_level. Same for the changes below.

cbi42 · 2023-05-22T20:40:19Z

db/manual_compaction_test.cc

-    // 1 is first compacted to L1 and then further compacted into [2, 4, 8],
-    // so finally the logged level for 1 is L1.
-    ASSERT_EQ(1, filter->KeyLevel("1"));
+    // 1 is first compacted from L0 to L1, and then L1 intra level compaction


New behavior for kIfHaveCompactionFilter.

cbi42 · 2023-05-22T20:41:18Z

db/db_bloom_filter_test.cc

  compact_options.target_level = 7;
  ASSERT_OK(db_->CompactRange(compact_options, handles_[1], nullptr, nullptr));

-  ASSERT_EQ(trivial_move, 1);


Multiple trivial moves to compact to the bottommost level.

ajkr · 2023-05-25T20:39:23Z

a manual compaction may not be able to compact all keys in the specified key range

In what cases does it matter? In case keys moved beyond max_overlapped_level due to automatic non-trivial compaction, those keys were compacted after the manual compaction began. This seems good enough for all settings except BottommostLevelCompaction::kForce (non-default). Perhaps the bigger problem is automatic trivial-move compaction moves keys beyond max_overlapped_level?

Another question: do you think kForce has a valid use case?

ajkr

LGTM, thanks!

ajkr · 2023-05-26T03:20:07Z

db/db_compaction_test.cc

Nice test cases

cbi42 · 2023-05-30T21:08:12Z

a manual compaction may not be able to compact all keys in the specified key range

In what cases does it matter? In case keys moved beyond max_overlapped_level due to automatic non-trivial compaction, those keys were compacted after the manual compaction began. This seems good enough for all settings except BottommostLevelCompaction::kForce (non-default). Perhaps the bigger problem is automatic trivial-move compaction moves keys beyond max_overlapped_level?

Another question: do you think kForce has a valid use case?

Perhaps the bigger problem is automatic trivial-move compaction moves keys beyond max_overlapped_level?

Yes, it is a problem only when files are trivially moved beyond max_overlapped_level. Updated PR summary for this.

Another question: do you think kForce has a valid use case?

Not sure if any user has this need, manual compaction with kForce can probably produce larger files and less number of files in the last level.

facebook-github-bot · 2023-05-30T21:28:59Z

@cbi42 has updated the pull request. You must reimport the pull request before landing.

facebook-github-bot · 2023-05-30T21:29:35Z

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

facebook-github-bot · 2023-05-31T18:22:45Z

@cbi42 has updated the pull request. You must reimport the pull request before landing.

facebook-github-bot · 2023-05-31T21:09:47Z

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

…ommost level. Fix new unit tests. Need to fix existing unit tests that this change breaks.

kForceOptimized. Fix failed existing unit tests.

facebook-github-bot · 2023-06-01T19:45:48Z

@cbi42 has updated the pull request. You must reimport the pull request before landing.

cbi42 · 2023-06-01T19:46:34Z

db/db_impl/db_impl_compaction_flush.cc

            // or kIfHaveCompactionFilter with compaction filter set.
            s = RunManualCompaction(
                cfd, final_output_level, final_output_level, options, begin,
-                end, exclusive, !trim_ts.empty() /* disallow_trivial_move */,


Intra-level compaction does not allow trivial move anyway.

facebook-github-bot · 2023-06-01T19:47:05Z

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

facebook-github-bot · 2023-06-01T22:29:19Z

@cbi42 merged this pull request in e95cc12.

…action (facebook#11468) Summary: currently for leveled compaction, the max output level of a call to `CompactRange()` is pre-computed before compacting each level. This max output level is the max level whose key range overlaps with the manual compaction key range. However, during manual compaction, files in the max output level may be compacted down further by some background compaction. When this background compaction is a trivial move, there is a race condition and the manual compaction may not be able to compact all keys in the specified key range. This PR updates `CompactRange()` to always compact to the bottommost level to make this race condition more unlikely (it can still happen, see more in comment here: https://github.com/cbi42/rocksdb/blob/796f58f42ad1bdbf49e5fcf480763f11583b790e/db/db_impl/db_impl_compaction_flush.cc#L1180C29-L1184). This PR also changes the behavior of CompactRange() when `bottommost_level_compaction=kIfHaveCompactionFilter` (the default option). The old behavior is that, if a compaction filter is provided, CompactRange() always does an intra-level compaction at the final output level for all files in the manual compaction key range. The only exception when `first_overlapped_level = 0` and `max_overlapped_level = 0`. It’s awkward to maintain the same behavior after this PR since we do not compute max_overlapped_level anymore. So the new behavior is similar to kForceOptimized: always does intra-level compaction at the bottommost level, but not including new files generated during this manual compaction. Several unit tests are updated to work with this new manual compaction behavior. Pull Request resolved: facebook#11468 Test Plan: Add new unit tests `DBCompactionTest.ManualCompactionCompactAllKeysInRange*` Reviewed By: ajkr Differential Revision: D46079619 Pulled By: cbi42 fbshipit-source-id: 19d844ba4ec8dc1a0b8af5d2f36ff15820c6e76f Signed-off-by: tabokie <xy.tao@outlook.com>

* Always allow L0->L1 trivial move during manual compaction (facebook#11375) Summary: during manual compaction (CompactRange()), L0->L1 trivial move is disabled when only L0 overlaps with compacting key range (introduced in facebook#7368 to enforce kForce* contract). This can cause large memory usage due to compaction readahead when number of L0 files is large. This PR allows L0->L1 trivial move in this case, and will do a L1 -> L1 intra-level compaction when needed (`bottommost_level_compaction` is kForce*). In brief, consider a DB with only L0 file, and user calls CompactRange(kForce, nullptr, nullptr), - before this PR, RocksDB does a L0 -> L1 compaction (disallow trivial move), - after this PR, RocksDB does a L0 -> L1 compaction (allow trivial move), and a L1 -> L1 compaction. Users can use kForceOptimized to avoid this extra L1->L1 compaction overhead when L0s are overlapping and cannot be trivial moved. This PR also fixed a bug (see previous discussion in facebook#11041) where `final_output_level` of a manual compaction can be miscalculated when `level_compaction_dynamic_level_bytes=true`. This bug could cause incorrect level being moved when CompactRangeOptions::change_level is specified. Pull Request resolved: facebook#11375 Test Plan: - Added new unit tests to test that L0 -> L1 compaction allows trivial move and L1 -> L1 compaction is done when needed. Reviewed By: ajkr Differential Revision: D44943518 Pulled By: cbi42 fbshipit-source-id: e9fb770d17b163c18a623e1d1bd6b81159192708 Signed-off-by: tabokie <xy.tao@outlook.com> * `CompactRange()` always compacts to bottommost level for leveled compaction (facebook#11468) Summary: currently for leveled compaction, the max output level of a call to `CompactRange()` is pre-computed before compacting each level. This max output level is the max level whose key range overlaps with the manual compaction key range. However, during manual compaction, files in the max output level may be compacted down further by some background compaction. When this background compaction is a trivial move, there is a race condition and the manual compaction may not be able to compact all keys in the specified key range. This PR updates `CompactRange()` to always compact to the bottommost level to make this race condition more unlikely (it can still happen, see more in comment here: https://github.com/cbi42/rocksdb/blob/796f58f42ad1bdbf49e5fcf480763f11583b790e/db/db_impl/db_impl_compaction_flush.cc#L1180C29-L1184). This PR also changes the behavior of CompactRange() when `bottommost_level_compaction=kIfHaveCompactionFilter` (the default option). The old behavior is that, if a compaction filter is provided, CompactRange() always does an intra-level compaction at the final output level for all files in the manual compaction key range. The only exception when `first_overlapped_level = 0` and `max_overlapped_level = 0`. It’s awkward to maintain the same behavior after this PR since we do not compute max_overlapped_level anymore. So the new behavior is similar to kForceOptimized: always does intra-level compaction at the bottommost level, but not including new files generated during this manual compaction. Several unit tests are updated to work with this new manual compaction behavior. Pull Request resolved: facebook#11468 Test Plan: Add new unit tests `DBCompactionTest.ManualCompactionCompactAllKeysInRange*` Reviewed By: ajkr Differential Revision: D46079619 Pulled By: cbi42 fbshipit-source-id: 19d844ba4ec8dc1a0b8af5d2f36ff15820c6e76f Signed-off-by: tabokie <xy.tao@outlook.com> * add check in range interface Signed-off-by: tabokie <xy.tao@outlook.com> --------- Signed-off-by: tabokie <xy.tao@outlook.com> Co-authored-by: Changyu Bi <changyubi@meta.com>

facebook-github-bot added the CLA Signed label May 22, 2023

cbi42 commented May 22, 2023

View reviewed changes

cbi42 requested review from ajkr and hx235 May 22, 2023 20:41

ajkr approved these changes May 26, 2023

View reviewed changes

db/db_compaction_test.cc

Copy link
Copy Markdown

Contributor

ajkr May 26, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nice test cases

cbi42 force-pushed the manual-compact-always-to-bottom branch from c3b5792 to 2bffb41 Compare May 30, 2023 21:28

cbi42 force-pushed the manual-compact-always-to-bottom branch from 2bffb41 to 8708150 Compare May 31, 2023 18:22

cbi42 added 7 commits June 1, 2023 12:28

Add unit tests.

971fb1e

Manual compaction with level compaction always try to compact to bott…

64aa144

…ommost level. Fix new unit tests. Need to fix existing unit tests that this change breaks.

Make kIfHaveCompactionFilter behave like

136c83e

kForceOptimized. Fix failed existing unit tests.

Fix unit tests.

026a21a

Update comments.

de567b6

Add change log compact_range_to_bottom.md.

707d267

Update change log and minor code change.

1952285

cbi42 force-pushed the manual-compact-always-to-bottom branch from 8708150 to 1952285 Compare June 1, 2023 19:45

cbi42 commented Jun 1, 2023

View reviewed changes

facebook-github-bot closed this in e95cc12 Jun 1, 2023

facebook-github-bot added the Merged label Jun 1, 2023

tabokie mentioned this pull request Aug 14, 2023

cherry-pick compaction enhancements tikv/rocksdb#345

Closed

niklasf mentioned this pull request Sep 3, 2023

Update RocksDB to 8.5.3 rust-rocksdb/rust-rocksdb#815

Merged

speedbmike mentioned this pull request Oct 10, 2023

Add speedb as an alternative to rocksdb apache/kvrocks#1792

Merged

ajkr mentioned this pull request Nov 26, 2023

[BUG] CompactRange does not apply to all the records in range. #7983

Closed

igorcanadi mentioned this pull request Jan 17, 2024

[SYS-6913] Upgrade RocksDB-Cloud to 8.9.1 rockset/rocksdb-cloud#315

Closed

979357361 mentioned this pull request Apr 6, 2025

[BUG] compact_range miss keys in [begin, end), causing compactor_filter fail to remove outdated keys #13526

Open

Conversation

cbi42 commented May 22, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

facebook-github-bot commented May 22, 2023

Uh oh!

cbi42 May 22, 2023

Choose a reason for hiding this comment

Uh oh!

cbi42 May 22, 2023

Choose a reason for hiding this comment

Uh oh!

cbi42 May 22, 2023

Choose a reason for hiding this comment

Uh oh!

ajkr commented May 25, 2023

Uh oh!

ajkr left a comment

Choose a reason for hiding this comment

Uh oh!

ajkr May 26, 2023

Choose a reason for hiding this comment

Uh oh!

cbi42 commented May 30, 2023

Uh oh!

facebook-github-bot commented May 30, 2023

Uh oh!

facebook-github-bot commented May 30, 2023

Uh oh!

facebook-github-bot commented May 31, 2023

Uh oh!

facebook-github-bot commented May 31, 2023

Uh oh!

facebook-github-bot commented Jun 1, 2023

Uh oh!

cbi42 Jun 1, 2023

Choose a reason for hiding this comment

Uh oh!

facebook-github-bot commented Jun 1, 2023

Uh oh!

facebook-github-bot commented Jun 1, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

cbi42 commented May 22, 2023 •

edited

Loading