-
Notifications
You must be signed in to change notification settings - Fork 24.4k
Reduce dbBuckets operation time complexity from O(N) to O(1) #12697
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Conversation
Co-authored-by: Roshan Khatri <rvkhatri@amazon.com>
|
For slot not owned by the node, the above solution wouldn't account any buckets for it. However, for slots active on a node and later migrated I believe we don't reduce the size to 0 bucket. So, additional 4 bucket for such slot would be accounted which I believe is the true state of the node. @oranagra let me know what you think about it. |
|
If the memory for the dict is still allocated, then that ok. If we released it, we should update the counter |
|
@oranagra I think we need to improve the logic introduced in #11695 to not add to the list when However, when |
|
Ok. Let's merge this one and handle that issue separately. |
Introduced in #12697 , should reset bucket_count when empty db, or the overhead memory usage of db can be miscalculated.
The change in dbSwapDatabases seems harmless. Because in non-clustered mode, dbBuckets calculations are strictly accurate and in cluster mode, we only have one DB. Modify it for uniformity (just like resize_cursor). The change in swapMainDbWithTempDb is needed in case we swap with the temp db, otherwise the overhead memory usage of db can be miscalculated. Introduced in redis#12697.
…tion In the old dictRehashingInfo implementation, for the initialization scenario, it mistakenly directly set to_size to DICTHT_SIZE(DICT_HT_INITIAL_EXP), which is 4 in our code by default. In scenarios where dictExpand directly passes the target size as initialization, the code will calculate bucket_count incorrectly. For example, in DEBUG POPULATE or RDB load scenarios, it will cause the final bucket_count to be initialized to 65536 (16384 * 4), see: ``` before: DB 0: 10000000 keys (0 volatile) in 65536 slots HT. it should be: DB 0: 10000000 keys (0 volatile) in 16777216 slots HT. ``` In PR, new ht will also be initialized before calling rehashingStarted in _dictExpand, so that the calls in dictRehashingInfo can be unified. This PR also cleans up dictRehashingStarted* and dictRehashingCompleted*, eliminating some duplicate code. Bug was introduced in redis#12697.
…on (#12846) In the old dictRehashingInfo implementation, for the initialization scenario, it mistakenly directly set to_size to DICTHT_SIZE(DICT_HT_INITIAL_EXP), which is 4 in our code by default. In scenarios where dictExpand directly passes the target size as initialization, the code will calculate bucket_count incorrectly. For example, in DEBUG POPULATE or RDB load scenarios, it will cause the final bucket_count to be initialized to 65536 (16384 * 4), see: ``` before: DB 0: 10000000 keys (0 volatile) in 65536 slots HT. it should be: DB 0: 10000000 keys (0 volatile) in 16777216 slots HT. ``` In PR, new ht will also be initialized before calling rehashingStarted in _dictExpand, so that the calls in dictRehashingInfo can be unified. Bug was introduced in #12697.
…2763) The change in dbSwapDatabases seems harmless. Because in non-clustered mode, dbBuckets calculations are strictly accurate and in cluster mode, we only have one DB. Modify it for uniformity (just like resize_cursor). The change in swapMainDbWithTempDb is needed in case we swap with the temp db, otherwise the overhead memory usage of db can be miscalculated. In addition we will swap all fields (including rehashing list), just for completeness (and reduce the chance of surprises in the future). Introduced in #12697.
As part of #11695 independent dictionaries were introduced per slot. Time complexity to discover total no. of buckets across all dictionaries increased to O(N) with straightforward implementation of iterating over all dictionaries and adding
dictBucketsof each.To optimize the time complexity, we could maintain a global counter at db level to keep track of the count of buckets and update it on the start and end of rehashing.