Optimize dict no_value also for even addresses#13683
Merged
Merged
Conversation
tezc
reviewed
Dec 19, 2024
tezc
reviewed
Dec 19, 2024
tezc
reviewed
Dec 19, 2024
3eba2c5 to
9192840
Compare
tezc
approved these changes
Dec 19, 2024
moticless
added a commit
that referenced
this pull request
May 12, 2025
The idea of packing the key (`sds`), value (`robj`) and optionally TTL into a single struct in memory was mentioned a few times in the past by the community in various flavors. This approach improves memory efficiency, reduces pointer dereferences for faster lookups, and simplifies expiration management by keeping all relevant data in one place. This change goes along with setting keyspace's dict to no_value=1, and saving considerable amount of memory. Two more motivations that well aligned with this unification are: - Prepare the groundwork for replacing EXPIRE scan based implementation and evaluate instead new `ebuckets` data structure that was introduced as part of [Hash Field Expiration feature](https://redis.io/blog/hash-field-expiration-architecture-and-benchmarks/). Using this data structure requires embedding the ExpireMeta structure within each object. - Consider replacing dict with a more space efficient open addressing approach hash table that might rely on keeping a single pointer to object. Before this PR, I POC'ed on a variant of open addressing hash-table and was surprised to find that dict with no_value actually could provide a good balance between performance, memory efficiency, and simplicity. This realization prompted the separation of the unification step from the evaluation of a new hash table to avoid introducing too many changes at once and to evaluate its impact independently before considering replacement of existing hash-table. On an earlier [commit](#13683) I extended dict no_value optimization (which saves keeping dictEntry where possible) to be relevant also for objects with even addresses in memory. Combining it with this unification saves a considerable amount of memory for keyspace. # kvobj This PR adopts Valkey’s [packing](valkey-io/valkey@3eb8314) layout and logic for key, value, and TTL. However, unlike Valkey implementation, which retained a common `robj` throughout the project, this PR distinguishes between the general-purpose, overused `robj`, and the new `kvobj`, which embeds both the key and value and used by the keyspace. Conceptually, `robj` serves as a base class, while `kvobj` acts as a derived class. Two new flags introduced into redis object, `iskvobj` and `expirable`: ``` struct redisObject { unsigned type:4; unsigned encoding:4; unsigned lru:LRU_BITS; unsigned iskvobj : 1; /* new flag */ unsigned expirable : 1; /* new flag */ unsigned refcount : 30; /* modified: 32bits->30bits */ void *ptr; }; typedef struct redisObject robj; typedef struct redisObject kvobj; ``` When the `iskvobj` flag is set, the object includes also the key and it is appended to the end of the object. If the `expirable` flag is set, an additional 8 bytes are added to the object. If the object is of type string, and the string is rather short, then it will be embedded as well. As a result, all keys in the keyspace are promoted to be of type `kvobj`. This term attempts to align with the existing Redis object, robj, and the kvstore data structure. # EXPIRE Implementation As `kvobj` embeds expiration time as well, looking up expiration times is now an O(1) operation. And the hash-table of EXPIRE is set now to be `no_value` mode, directly referencing `kvobj` entries, and in turn, saves memory. Next, I plan to evaluate replacing the EXPIRE implementation with the [ebuckets](https://github.com/redis/redis/blob/unstable/src/ebuckets.h) data structure, which would eliminate keyspace scans for expired keys. This requires embedding `ExpireMeta` within each `kvobj` of each key with expiration. In such implementation, the `expirable` flag will be shifted to indicate whether `ExpireMeta` is attached. # Implementation notes ## Manipulating keyspace (find, modify, insert) Initially, unifying the key and value into a single object and storing it in dict with `no_value` optimization seemed like a quick win. However, it (quickly) became clear that this change required deeper modifications to how keys are manipulated. The challenge was handling cases where a dictEntry is opt-out due to no_value optimization. In such cases, many of the APIs that return the dictEntry from a lookup become insufficient, as it just might be the key itself. To address this issue, a new-old approach of returning a "link" to the looked-up key's `dictEntry` instead of the `dictEntry` itself. The term `link` was already somewhat available in dict API, and is well aligned with the new dictEntLink declaration: ``` typedef dictEntry **dictEntLink; ``` This PR introduces two new function APIs to dict to leverage returned link from the search: ``` dictEntLink dictFindLink(dict *d, const void *key, dictEntLink *bucket); void dictSetKeyAtLink(dict *d, void *key, dictEntLink *link, int newItem); ``` After calling `link = dictFindLink(...)`, any necessary updates must be performed immediately after by calling `dictSetKeyAtLink()` without any intervening operations on given dict. Otherwise, `dictEntLink` may become invalid. Example: ``` /* replace existing key */ link = dictFindLink(d, key, &bucket, 0); // ... Do something, but don't modify the dict ... // assert(link != NULL); dictSetKeyAtLink(d, kv, &link, 0); /* Add new value (If no space for the new key, dict will be expanded and bucket will be looked up again.) */ link = dictFindLink(d, key, &bucket); // ... Do something, but don't modify the dict ... // assert(link == NULL); dictSetKeyAtLink(d, kv, &bucket, 1); ``` ## dict.h - The dict API has became cluttered with many unused functions. I have removed these from dict.h. - Additionally, APIs specifically related to hash maps (no_value=0), primarily those handling key-value access, have been gathered and isolated. - Removed entirely internal functions ending with “*ByHash()” that were originally added for optimization and not required any more. - Few other legacy dict functions were adapted at API level to work with the term dictEntLink as well. - Simplified and generalized an optimization that related to comparison of length of keys of type strings. ## Hash Field Expiration Until now each hash object with expiration on fields needed to maintain a reference to its key-name (of the hash object), such that in case it will be active-expired, then it will be possible to resolve the key-name for the notification sake. Now there is no need anymore. --------- Co-authored-by: debing.sun <debing.sun@redis.com>
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This pull request enhances the
no_valueflag option in the dict implementation,which is used to store keys without associated values. Previously, when a key
had an odd memory address and was the only item in a table entry, it could be
directly stored as a pointer without requiring an intermediate
dictEntry. Withthis update, the optimization has been extended to also handle keys with even
memory addresses in the same manner.