Optimize resizing hash table to resize not only non-empty dicts. #12819

CharlesChen888 · 2023-11-29T09:03:17Z

The function tryResizeHashTables only attempts to shrink the dicts that has keys (change from #11695), this was a serious problem until the change in #12850 since it meant if all keys are deleted, we won't shrink the dick.
But still, both dictShrink and dictExpand may be blocked by a fork child process, therefore, the cron job needs to perform both dictShrink and dictExpand, for not just non-empty dicts, but all dicts in DBs.

What this PR does:

Try to resize all dicts in DBs (not just non-empty ones, as it was since Shrink dict when deleting dictEntry #12850)
handle both shrink and expand (not just shrink, as it was since forever)
Refactor some APIs about dict resizing (get rid of htNeedsShrink htNeedsShrink dictShrinkToFit, and expose dictShrinkIfNeeded dictExpandIfNeeded which already contains all the code of those functions we get rid of, to make APIs more neat)
In the Don't rehash if redis has child process test, now that cron would do resizing, we no longer need to write to DB after the child process got killed, and can wait for the cron to expand the hash table.

soloestoy · 2023-11-29T09:59:43Z

it's better to add a test case, such as using memory stats to check overhead.hashtable.main to determine if resize is done correctly.

src/server.c

tests/unit/other.tcl

oranagra · 2023-12-06T09:04:46Z

@CharlesChen888 please avoid force-pushes.
if you must rebase (you don't usually need to), please just merge the upstream into your branch instead.
since we're gonna squash merge this, it doesn't matter, and it makes it easier to review incremental changes.

soloestoy · 2023-12-12T05:52:41Z

Another tip: Currently, the function tryResizeHashTables only attempts to shrink, but in theory, dictExpand triggered by dictAdd can also be blocked by a child process. Therefore, the cron job also needs to consider performing dictExpand. Fortunately, the current name of this cron job is tryResizeHashTables, so it would make sense to add an expansion check in the resize function.

oranagra · 2023-12-12T07:38:59Z

good point. let's do it.
we'll be able to remove one line from the Don't rehash if redis has child process test.
so we just need to add another condition to htNeedsResize, right?
do you think we should do it in #12850 (which use the same conditions for server cron resize triggers and dict internal resize triggers), here? or another followup PR?

soloestoy · 2023-12-12T07:43:36Z

I think #12850 should focus on the dictionary itself. The changes to htNeedsResize and tryResizeHashTables would be more appropriate in this PR.

oranagra · 2023-12-12T09:02:32Z

@CharlesChen888 to test our last change, please remove the excessive line in the Don't rehash if redis has child process test.
i.e. the one that writes to the db after killing the child process.
you would probably need to replace the assertion at the end of the test with a wait_for_condition.

please also list this change and the reason behind it in the top comment, and make sure other details from this PR are described there.

thank you!

CharlesChen888 · 2023-12-18T02:23:33Z

Sorry about the force push again... I was trying my git plugin and it didn't work properly as I thought.

oranagra · 2024-01-02T16:36:12Z

we discussed this PR in the core-team meeting, and we had the following conclusions:

we believe that after Shrink dict when deleting dictEntry #12850 is merged, the cron-triggered shrinking isn't needed as much, and we can:
1. remove the fast scan and keep only the slow scan
2. let it scan all the dicts, without skipping the empty ones.
3. we should let the cron mechanism handle expansion too (not just shrinking), both are needed in case a resize was skipped due to dict_can_resize.
if for some reason we realize the above solution isn't good, we can maybe change the top level dicts (soon to be Refactor the per-slot dict-array db.c into a new kvstore data structure #12822) to completely delete the dict (either dictEmpty or dictRelease) when the dict becomes empty. then we don't need the slow scan. [we'll need some benchmarks to check the impact of that on a dict that has one key that's constantly removed and re-added]

When we insert entries into dict, it may autonomously expand if needed. However, when we delete entries from dict, it doesn't shrink to the proper size. If there are few entries in a very large dict, it may cause huge waste of memory and inefficiency when iterating. The main keyspace dicts (keys and expires), are shrinked by cron (`tryResizeHashTables` calls `htNeedsResize` and `dictResize`), And some data structures such as zset and hash also do that (call `htNeedsResize`) right after a loop of calls to `dictDelete`, But many other dicts are completely missing that call (they can only expand). In this PR, we provide the ability to automatically shrink the dict when deleting. The conditions triggering the shrinking is the same as `htNeedsResize` used to have. i.e. we expand when we're over 100% utilization, and shrink when we're below 10% utilization. Additionally: * Add `dictPauseAutoResize` so that flows that do mass deletions, will only trigger shrinkage at the end. * Rename `dictResize` to `dictShrinkToFit` (same logic as it used to have, but better name describing it) * Rename `_dictExpand` to `_dictResize` (same logic as it used to have, but better name describing it) related to discussion #12819 (comment) --------- Co-authored-by: Oran Agra <oran@redislabs.com> Co-authored-by: zhaozhao.zz <zhaozhao.zz@alibaba-inc.com>

oranagra · 2024-01-15T06:22:21Z

@CharlesChen888 now that #12850 was merged, can you look into the approach from the previous comment?

oranagra

@soloestoy please take another look

src/dict.c

oranagra · 2024-01-29T06:33:44Z

@CharlesChen888 i've edited the top comment, please take a look.
also if you can mention something more about the refactoring in bullet 4 please do.
and please mark the resolved comments as such.
thanks.

CharlesChen888 · 2024-01-29T12:45:11Z

@oranagra Thanks for editing the top comment. I am OK with it. I also mentioned the specific APIs that I changed. Some comments are added according to @soloestoy 's advise.

tests consistently fail on timeout (sleep that's too short). it now takes more time because in #12819 we iterate on all dicts, not just non-empty ones. it passed the PR's CI because it skips the `slow` tag, which might have been misplaced, but now it is probably required. with the fix, the tests take quite a lot of time: ``` [ok]: Redis can trigger resizing (1860 ms) [ok]: Redis can rewind and trigger smaller slot resizing (744 ms) ``` before #12819: ``` [ok]: Redis can trigger resizing (309 ms) [ok]: Redis can rewind and trigger smaller slot resizing (295 ms) ``` failure: https://github.com/redis/redis/actions/runs/7704158180/job/20995931735 ``` *** [err]: expire scan should skip dictionaries with lot's of empty buckets in tests/unit/expire.tcl scan didn't handle slot skipping logic. *** [err]: Redis can trigger resizing in tests/unit/other.tcl Expected '[Dictionary HT] Hash table 0 stats (main hash table): table size: 128 number of elements: 5 [Expires HT] Hash table 0 stats (main hash table): No stats available for empty dictionaries ' to match '*table size: 8*' (context: type eval line 29 cmd {assert_match "*table size: 8*" [r debug HTSTATS 0]} proc ::test) *** [err]: Redis can rewind and trigger smaller slot resizing in tests/unit/other.tcl Expected '[Dictionary HT] Hash table 0 stats (main hash table): table size: 256 number of elements: 10 [Expires HT] Hash table 0 stats (main hash table): No stats available for empty dictionaries ' to match '*table size: 16*' (context: type eval line 27 cmd {assert_match "*table size: 16*" [r debug HTSTATS 0]} proc ::test) ```

Ci report this failure: ``` *** [err]: Don't rehash if used memory exceeds maxmemory after rehash in tests/unit/maxmemory.tcl Expected '4098' to equal or match '4002' WARNING: the new maxmemory value set via CONFIG SET (1176088) is smaller than the current memory usage (1231083) ``` It can be seen from the log that used_memory changed before we set maxmemory. The reason is that in redis#12819, in cron, in addition to trying to shrink, we will also tyring to expand. The dict was expanded by cron before we set maxmemory, causing the test to fail. The fix is to disable resize before reaching 1:1 raido, and wait until maxmemory is set before enabling resize.

Ci report this failure: ``` *** [err]: Don't rehash if used memory exceeds maxmemory after rehash in tests/unit/maxmemory.tcl Expected '4098' to equal or match '4002' WARNING: the new maxmemory value set via CONFIG SET (1176088) is smaller than the current memory usage (1231083) ``` It can be seen from the log that used_memory changed before we set maxmemory. The reason is that in #12819, in cron, in addition to trying to shrink, we will also tyring to expand. The dict was expanded by cron before we set maxmemory, causing the test to fail. Before setting maxmemory, we only add 4095 keys to avoid triggering resize.

guybe7 · 2024-02-01T07:57:07Z

hi @CharlesChen888 a few comments:

i see you changed a after 200 ;# waiting for serverCron to wait_for_condition which is very good, but why only in that test? there are a few other tests in the same file to also sleep 200ms for the same purpose
why did you add a new test instead of adjusting Redis can trigger resizing to run on an empty db? i'm asking because it seems pretty fragile to check the actual overhead rather than the amount of buckets

CharlesChen888 · 2024-02-01T09:36:54Z

@guybe7

I simply did not check carefully through the whole file ...
Because on a newly started DB everything is clean, which makes such "fragile" thing checking overhead easier. And there is no metric showing bucket count directly.

oranagra · 2024-02-01T10:10:30Z

note that other than the difference of deleting all keys instead of most keys, and the difference in measuring memory instead of bucket count, these two tests also differ in the fact one of them runs in cluster mode and the other without.
i'm not sure if the right approach would be to convert the test added here to look at the bucket count, or add a loop that will run the tests above it twice (completely emptying vs emptying most keys).
i.e. maybe we also want to keep one that runs without cluster mode?

oranagra · 2024-02-05T14:57:46Z

@CharlesChen888 can you try doing what i suggested above?

CharlesChen888 · 2024-02-06T07:13:01Z

@oranagra just to make sure, you are suggesting adding tests, so we can test that the new code work for both empty and non-empty dicts?

oranagra · 2024-02-06T10:18:02Z

@CharlesChen888 IIRC i'm suggesting to delete the new test you added and instead run the other test twice (once when it removes most of the keys in the dict and once when it removes all of them)
does that make sense?

you can also take this opportunity to mirror the after 200 improvement to other tests that may be susceptible to the same issue.

The reason is the same as redis#13016. The reason is that in redis#12819, in cron, in addition to trying to shrink, we will also tyring to expand. The dict was expanded by cron before we trigger the bgsave since we do have the enough keys (4096) to hit the radio. Before the bgsave, we only add 4095 keys to avoid this issue. Also removing local-process, don't remember we are using it.

The reason is the same as #13016. The reason is that in #12819, in cron, in addition to trying to shrink, we will also tyring to expand. The dict was expanded by cron before we trigger the bgsave since we do have the enough keys (4096) to hit the radio. Before the bgsave, we only add 4095 keys to avoid this issue.

When we insert entries into dict, it may autonomously expand if needed. However, when we delete entries from dict, it doesn't shrink to the proper size. If there are few entries in a very large dict, it may cause huge waste of memory and inefficiency when iterating. The main keyspace dicts (keys and expires), are shrinked by cron (`tryResizeHashTables` calls `htNeedsResize` and `dictResize`), And some data structures such as zset and hash also do that (call `htNeedsResize`) right after a loop of calls to `dictDelete`, But many other dicts are completely missing that call (they can only expand). In this PR, we provide the ability to automatically shrink the dict when deleting. The conditions triggering the shrinking is the same as `htNeedsResize` used to have. i.e. we expand when we're over 100% utilization, and shrink when we're below 10% utilization. Additionally: * Add `dictPauseAutoResize` so that flows that do mass deletions, will only trigger shrinkage at the end. * Rename `dictResize` to `dictShrinkToFit` (same logic as it used to have, but better name describing it) * Rename `_dictExpand` to `_dictResize` (same logic as it used to have, but better name describing it) related to discussion redis#12819 (comment) --------- Co-authored-by: Oran Agra <oran@redislabs.com> Co-authored-by: zhaozhao.zz <zhaozhao.zz@alibaba-inc.com>

…is#12819) The function `tryResizeHashTables` only attempts to shrink the dicts that has keys (change from redis#11695), this was a serious problem until the change in redis#12850 since it meant if all keys are deleted, we won't shrink the dick. But still, both dictShrink and dictExpand may be blocked by a fork child process, therefore, the cron job needs to perform both dictShrink and dictExpand, for not just non-empty dicts, but all dicts in DBs. What this PR does: 1. Try to resize all dicts in DBs (not just non-empty ones, as it was since redis#12850) 2. handle both shrink and expand (not just shrink, as it was since forever) 3. Refactor some APIs about dict resizing (get rid of `htNeedsShrink` `htNeedsShrink` `dictShrinkToFit`, and expose `dictShrinkIfNeeded` `dictExpandIfNeeded` which already contains all the code of those functions we get rid of, to make APIs more neat) 4. In the `Don't rehash if redis has child process` test, now that cron would do resizing, we no longer need to write to DB after the child process got killed, and can wait for the cron to expand the hash table.

…redis#13009) tests consistently fail on timeout (sleep that's too short). it now takes more time because in redis#12819 we iterate on all dicts, not just non-empty ones. it passed the PR's CI because it skips the `slow` tag, which might have been misplaced, but now it is probably required. with the fix, the tests take quite a lot of time: ``` [ok]: Redis can trigger resizing (1860 ms) [ok]: Redis can rewind and trigger smaller slot resizing (744 ms) ``` before redis#12819: ``` [ok]: Redis can trigger resizing (309 ms) [ok]: Redis can rewind and trigger smaller slot resizing (295 ms) ``` failure: https://github.com/redis/redis/actions/runs/7704158180/job/20995931735 ``` *** [err]: expire scan should skip dictionaries with lot's of empty buckets in tests/unit/expire.tcl scan didn't handle slot skipping logic. *** [err]: Redis can trigger resizing in tests/unit/other.tcl Expected '[Dictionary HT] Hash table 0 stats (main hash table): table size: 128 number of elements: 5 [Expires HT] Hash table 0 stats (main hash table): No stats available for empty dictionaries ' to match '*table size: 8*' (context: type eval line 29 cmd {assert_match "*table size: 8*" [r debug HTSTATS 0]} proc ::test) *** [err]: Redis can rewind and trigger smaller slot resizing in tests/unit/other.tcl Expected '[Dictionary HT] Hash table 0 stats (main hash table): table size: 256 number of elements: 10 [Expires HT] Hash table 0 stats (main hash table): No stats available for empty dictionaries ' to match '*table size: 16*' (context: type eval line 27 cmd {assert_match "*table size: 16*" [r debug HTSTATS 0]} proc ::test) ```

Ci report this failure: ``` *** [err]: Don't rehash if used memory exceeds maxmemory after rehash in tests/unit/maxmemory.tcl Expected '4098' to equal or match '4002' WARNING: the new maxmemory value set via CONFIG SET (1176088) is smaller than the current memory usage (1231083) ``` It can be seen from the log that used_memory changed before we set maxmemory. The reason is that in redis#12819, in cron, in addition to trying to shrink, we will also tyring to expand. The dict was expanded by cron before we set maxmemory, causing the test to fail. Before setting maxmemory, we only add 4095 keys to avoid triggering resize.

The reason is the same as redis#13016. The reason is that in redis#12819, in cron, in addition to trying to shrink, we will also tyring to expand. The dict was expanded by cron before we trigger the bgsave since we do have the enough keys (4096) to hit the radio. Before the bgsave, we only add 4095 keys to avoid this issue.

When we insert entries into dict, it may autonomously expand if needed. However, when we delete entries from dict, it doesn't shrink to the proper size. If there are few entries in a very large dict, it may cause huge waste of memory and inefficiency when iterating. The main keyspace dicts (keys and expires), are shrinked by cron (`tryResizeHashTables` calls `htNeedsResize` and `dictResize`), And some data structures such as zset and hash also do that (call `htNeedsResize`) right after a loop of calls to `dictDelete`, But many other dicts are completely missing that call (they can only expand). In this PR, we provide the ability to automatically shrink the dict when deleting. The conditions triggering the shrinking is the same as `htNeedsResize` used to have. i.e. we expand when we're over 100% utilization, and shrink when we're below 10% utilization. Additionally: * Add `dictPauseAutoResize` so that flows that do mass deletions, will only trigger shrinkage at the end. * Rename `dictResize` to `dictShrinkToFit` (same logic as it used to have, but better name describing it) * Rename `_dictExpand` to `_dictResize` (same logic as it used to have, but better name describing it) related to discussion redis#12819 (comment) --------- Co-authored-by: Oran Agra <oran@redislabs.com> Co-authored-by: zhaozhao.zz <zhaozhao.zz@alibaba-inc.com>

…is#12819) The function `tryResizeHashTables` only attempts to shrink the dicts that has keys (change from redis#11695), this was a serious problem until the change in redis#12850 since it meant if all keys are deleted, we won't shrink the dick. But still, both dictShrink and dictExpand may be blocked by a fork child process, therefore, the cron job needs to perform both dictShrink and dictExpand, for not just non-empty dicts, but all dicts in DBs. What this PR does: 1. Try to resize all dicts in DBs (not just non-empty ones, as it was since redis#12850) 2. handle both shrink and expand (not just shrink, as it was since forever) 3. Refactor some APIs about dict resizing (get rid of `htNeedsShrink` `htNeedsShrink` `dictShrinkToFit`, and expose `dictShrinkIfNeeded` `dictExpandIfNeeded` which already contains all the code of those functions we get rid of, to make APIs more neat) 4. In the `Don't rehash if redis has child process` test, now that cron would do resizing, we no longer need to write to DB after the child process got killed, and can wait for the cron to expand the hash table.

…redis#13009) tests consistently fail on timeout (sleep that's too short). it now takes more time because in redis#12819 we iterate on all dicts, not just non-empty ones. it passed the PR's CI because it skips the `slow` tag, which might have been misplaced, but now it is probably required. with the fix, the tests take quite a lot of time: ``` [ok]: Redis can trigger resizing (1860 ms) [ok]: Redis can rewind and trigger smaller slot resizing (744 ms) ``` before redis#12819: ``` [ok]: Redis can trigger resizing (309 ms) [ok]: Redis can rewind and trigger smaller slot resizing (295 ms) ``` failure: https://github.com/redis/redis/actions/runs/7704158180/job/20995931735 ``` *** [err]: expire scan should skip dictionaries with lot's of empty buckets in tests/unit/expire.tcl scan didn't handle slot skipping logic. *** [err]: Redis can trigger resizing in tests/unit/other.tcl Expected '[Dictionary HT] Hash table 0 stats (main hash table): table size: 128 number of elements: 5 [Expires HT] Hash table 0 stats (main hash table): No stats available for empty dictionaries ' to match '*table size: 8*' (context: type eval line 29 cmd {assert_match "*table size: 8*" [r debug HTSTATS 0]} proc ::test) *** [err]: Redis can rewind and trigger smaller slot resizing in tests/unit/other.tcl Expected '[Dictionary HT] Hash table 0 stats (main hash table): table size: 256 number of elements: 10 [Expires HT] Hash table 0 stats (main hash table): No stats available for empty dictionaries ' to match '*table size: 16*' (context: type eval line 27 cmd {assert_match "*table size: 16*" [r debug HTSTATS 0]} proc ::test) ```

Ci report this failure: ``` *** [err]: Don't rehash if used memory exceeds maxmemory after rehash in tests/unit/maxmemory.tcl Expected '4098' to equal or match '4002' WARNING: the new maxmemory value set via CONFIG SET (1176088) is smaller than the current memory usage (1231083) ``` It can be seen from the log that used_memory changed before we set maxmemory. The reason is that in redis#12819, in cron, in addition to trying to shrink, we will also tyring to expand. The dict was expanded by cron before we set maxmemory, causing the test to fail. Before setting maxmemory, we only add 4095 keys to avoid triggering resize.

The reason is the same as redis#13016. The reason is that in redis#12819, in cron, in addition to trying to shrink, we will also tyring to expand. The dict was expanded by cron before we trigger the bgsave since we do have the enough keys (4096) to hit the radio. Before the bgsave, we only add 4095 keys to avoid this issue.

CharlesChen888 changed the title ~~Optimize resize hash tabled to resize not only non-empty dicts.~~ Optimize resizing hash table to resize not only non-empty dicts. Nov 29, 2023

soloestoy requested review from hpatro, oranagra and soloestoy November 29, 2023 09:57

oranagra reviewed Nov 29, 2023

View reviewed changes

src/server.c Outdated Show resolved Hide resolved

src/server.c Outdated Show resolved Hide resolved

hpatro reviewed Nov 29, 2023

View reviewed changes

src/server.c Outdated Show resolved Hide resolved

src/server.c Outdated Show resolved Hide resolved

hpatro reviewed Dec 1, 2023

View reviewed changes

tests/unit/other.tcl Outdated Show resolved Hide resolved

tests/unit/other.tcl Outdated Show resolved Hide resolved

CharlesChen888 added 5 commits December 6, 2023 10:08

Optimize resize hash enabling to resize empty dicts.

530e354

Typo and rename.

bb39f2e

Add test for resizing empty dicts.

c9486f4

Simplify the test.

e23c3c1

Add external skip tag.

0ad566d

CharlesChen888 force-pushed the optimize-resize-empty-slot-dict branch from 54cd573 to 0ad566d Compare December 6, 2023 02:08

Remove duplicate definition during rebase.

008777e

lyq2333 mentioned this pull request Dec 8, 2023

Optimize dictExpand of empty dict #12847

Merged

oranagra mentioned this pull request Dec 10, 2023

Shrink dict when deleting dictEntry #12850

Merged

Add expand condition to htNeedsResize.

9e50d91

Rewrite rehash test.

cc6a77e

CharlesChen888 force-pushed the optimize-resize-empty-slot-dict branch from 997ddd1 to cc6a77e Compare December 18, 2023 02:06

Merge branch 'unstable' into optimize-resize-empty-slot-dict

5512d56

oranagra approved these changes Jan 25, 2024

View reviewed changes

soloestoy approved these changes Jan 29, 2024

View reviewed changes

src/dict.c Show resolved Hide resolved

Add comments about dictShrinkIfNeeded and dictExpandIfNeeded.

246b466

oranagra merged commit af7ceeb into redis:unstable Jan 29, 2024

oranagra mentioned this pull request Jan 30, 2024

fix dict rehash tests introduced by #12802 broken by #12819 #13009

Merged

enjoy-binbin mentioned this pull request Jan 31, 2024

Fix dict resize allow test #13016

Merged

enjoy-binbin mentioned this pull request Feb 7, 2024

Fix dict don't rehash when there is child test #13035

Merged

Optimize resizing hash table to resize not only non-empty dicts. #12819

Optimize resizing hash table to resize not only non-empty dicts. #12819

Uh oh!

Conversation

CharlesChen888 commented Nov 29, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

soloestoy commented Nov 29, 2023

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

oranagra commented Dec 6, 2023

Uh oh!

soloestoy commented Dec 12, 2023

Uh oh!

oranagra commented Dec 12, 2023

Uh oh!

soloestoy commented Dec 12, 2023

Uh oh!

oranagra commented Dec 12, 2023

Uh oh!

CharlesChen888 commented Dec 18, 2023

Uh oh!

oranagra commented Jan 2, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

oranagra commented Jan 15, 2024

Uh oh!

oranagra left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

oranagra commented Jan 29, 2024

Uh oh!

CharlesChen888 commented Jan 29, 2024

Uh oh!

guybe7 commented Feb 1, 2024

Uh oh!

CharlesChen888 commented Feb 1, 2024

Uh oh!

oranagra commented Feb 1, 2024

Uh oh!

oranagra commented Feb 5, 2024

Uh oh!

CharlesChen888 commented Feb 6, 2024

Uh oh!

oranagra commented Feb 6, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

CharlesChen888 commented Nov 29, 2023 •

edited

Loading

oranagra commented Jan 2, 2024 •

edited

Loading