Skip to content

Conversation

@guybe7
Copy link
Collaborator

@guybe7 guybe7 commented Nov 30, 2023

Description

Gather most of the scattered redisDb-related code from the per-slot dict PR (#11695) and turn it to a new data structure, kvstore. i.e. it's a class that represents an array of dictionaries.

Motivation

The main motivation is code cleanliness, the idea of using an array of dictionaries is very well-suited to becoming a self-contained data structure.
This allowed cleaning some ugly code, among others: loops that run twice on the main dict and expires dict, and duplicate code for allocating and releasing this data structure.

Notes

  1. This PR reverts the part of Unified db rehash method for both standalone and cluster #12848 where the rehashing list is global (handling rehashing dicts is under the responsibility of kvstore, and should not be managed by the server)
  2. This PR also replaces the type of server.pubsubshard_channels from dict** to kvstore (original PR: Replace slots_to_channels radix tree with slot specific dictionaries for shard channels. #12804). After that was done, server.pubsub_channels was also chosen to be a kvstore (with only one dict, which seems odd) just to make the code cleaner by making it the same type as server.pubsubshard_channels, see pubsubtype.serverPubSubChannels
  3. the keys and expires kvstores are currenlty configured to allocate the individual dicts only when the first key is added (unlike before, in which they allocated them in advance), but they won't release them when the last key is deleted.

Worth mentioning that due to the recent change the reply of DEBUG HTSTATS changed, in case no keys were ever added to the db.

before:

127.0.0.1:6379> DEBUG htstats 9
[Dictionary HT]
Hash table 0 stats (main hash table):
No stats available for empty dictionaries
[Expires HT]
Hash table 0 stats (main hash table):
No stats available for empty dictionaries

after:

127.0.0.1:6379> DEBUG htstats 9
[Dictionary HT]
[Expires HT]

@guybe7 guybe7 changed the title dictarray Introducing dictarray Dec 6, 2023
@guybe7 guybe7 marked this pull request as ready for review December 6, 2023 05:35
@guybe7 guybe7 requested a review from oranagra December 6, 2023 05:47
@guybe7
Copy link
Collaborator Author

guybe7 commented Dec 6, 2023

@vitarb can you please share your thoughts?

Copy link
Member

@oranagra oranagra left a comment

Choose a reason for hiding this comment

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

i only lightly skimmed though it.
mainly at the code that uses the array (code that remained in db.c, and other c files).
i think the idea to move this to a generic data structure is good.
i'd like to hear @madolson and @hpatro opinions before going into deep review.

@madolson
Copy link
Contributor

madolson commented Dec 7, 2023

I guess I'm still not convinced that we need a separate entity that differentiates the DB from the Dict Array, to me they still seem one and the same. There is a lot of logic being silo'd out into the Dictarray that is still pretty heavily coupled to Redis, cursors and per-slot information for sampling.

@guybe7
Copy link
Collaborator Author

guybe7 commented Dec 19, 2023

Note that the merge commit Merge remote-tracking branch 'origin/unstable' into dictarray inserts the logical change of moving the resharding list from the server struct into dictarray
i.e. in some way handling portion of #12848 in the reverse way.

1. revert recent dict changes (dictTypeExt)
2. wrap more of dict's API in dictarray
3. remove daCumulativeKeyCountAdd from API
4. add dbFind
@guybe7
Copy link
Collaborator Author

guybe7 commented Feb 1, 2024

@oranagra worth mentioning that due to the recent change the reply of DEBUG HTSTATS changed, in case of no keys were ever added to the db.

before:

127.0.0.1:6379> DEBUG htstats 9
[Dictionary HT]
Hash table 0 stats (main hash table):
No stats available for empty dictionaries
[Expires HT]
Hash table 0 stats (main hash table):
No stats available for empty dictionaries

after:

127.0.0.1:6379> DEBUG htstats 9
[Dictionary HT]
[Expires HT]

@oranagra
Copy link
Member

oranagra commented Feb 1, 2024

ok, i don't mind. but please mention it in the top comment.

Comment on lines +2653 to +2654
server.db[j].keys = kvstoreCreate(&dbDictType, slot_count_bits, KVSTORE_ALLOCATE_DICTS_ON_DEMAND);
server.db[j].expires = kvstoreCreate(&dbExpiresDictType, slot_count_bits, KVSTORE_ALLOCATE_DICTS_ON_DEMAND);
Copy link
Member

Choose a reason for hiding this comment

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

@madolson please comment if you think we should drop this flag.
it means that a cluster node will only allocate a dict when the slot is assigned to it and populated, but on the other hand, when the slot is unassigned, the dict will remain allocated.
till now all 16k dicts were always allocated.
i'm worried that someone will find it odd.

p.s. maybe we can add a kvstore interface to explicitly release a specific empty dict, and call it when a slot is unassigned?

Copy link
Member

Choose a reason for hiding this comment

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

@zuiderkwast maybe you wanna look into that?

Copy link
Contributor

Choose a reason for hiding this comment

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

It's not that annoying. It's a bit weird that for static configurations there won't be the extra overhead, but there will be if you scale out and add move slots to other nodes. I don't think it's likely a big issue, and now that there is an interface we can improve it later.

Copy link
Member

Choose a reason for hiding this comment

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

i'm bothered by two things:

  1. after resharding there's wasted memory which we can reclaim.
  2. the memory usage depends on the history and not just current state.

isn't it really simple to solve? some 10 trivial lines of code?

Copy link
Contributor

Choose a reason for hiding this comment

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

i see madolson also reacted with a thumbs up emoji. i try to add it in #13072

@oranagra
Copy link
Member

oranagra commented Feb 5, 2024

i'd like to merge the PR as is, and maybe address the last remaining comment later.
any objections?

@oranagra oranagra changed the title Introducing kvstore Refactor the per-slot dict-array db.c into a new kvstore data structure Feb 5, 2024
@oranagra oranagra merged commit 8cd62f8 into redis:unstable Feb 5, 2024
enjoy-binbin added a commit to enjoy-binbin/redis that referenced this pull request Feb 6, 2024
When the dict is NULL, we also need to push resize_cursor, otherwise it
will keep doing useless continue here, and there is no way to resize the
other dict behind it.

Introduced in redis#12822.
oranagra added a commit that referenced this pull request Feb 6, 2024
…#13031)

When the dict is NULL, we also need to push resize_cursor, otherwise it
will keep doing useless continue here, and there is no way to resize the
other dict behind it.

Introduced in #12822.

---------

Co-authored-by: Oran Agra <oran@redislabs.com>
enjoy-binbin added a commit to enjoy-binbin/redis that referenced this pull request Feb 6, 2024
After redis#12822, when pubsubshard_channels became empty, kvstoreDictDelete
will delete the dict (which is the only one currently deleting dicts that
become empty) and in the next loop, we will make an invalid call to dictNext.

After the dict becomes empty, we break out of the loop without calling dictNext.
oranagra pushed a commit that referenced this pull request Feb 6, 2024
…3033)

After #12822, when pubsubshard_channels became empty, kvstoreDictDelete
will delete the dict (which is the only one currently deleting dicts
that
become empty) and in the next loop, we will make an invalid call to
dictNext.

After the dict becomes empty, we break out of the loop without calling
dictNext.
roggervalf pushed a commit to roggervalf/redis that referenced this pull request Feb 11, 2024
…re (redis#12822)

# Description
Gather most of the scattered `redisDb`-related code from the per-slot
dict PR (redis#11695) and turn it to a new data structure, `kvstore`. i.e.
it's a class that represents an array of dictionaries.

# Motivation
The main motivation is code cleanliness, the idea of using an array of
dictionaries is very well-suited to becoming a self-contained data
structure.
This allowed cleaning some ugly code, among others: loops that run twice
on the main dict and expires dict, and duplicate code for allocating and
releasing this data structure.

# Notes
1. This PR reverts the part of redis#12848
where the `rehashing` list is global (handling rehashing `dict`s is
under the responsibility of `kvstore`, and should not be managed by the
server)
2. This PR also replaces the type of `server.pubsubshard_channels` from
`dict**` to `kvstore` (original PR:
redis#12804). After that was done,
server.pubsub_channels was also chosen to be a `kvstore` (with only one
`dict`, which seems odd) just to make the code cleaner by making it the
same type as `server.pubsubshard_channels`, see
`pubsubtype.serverPubSubChannels`
3. the keys and expires kvstores are currenlty configured to allocate
the individual dicts only when the first key is added (unlike before, in
which they allocated them in advance), but they won't release them when
the last key is deleted.

Worth mentioning that due to the recent change the reply of DEBUG
HTSTATS changed, in case no keys were ever added to the db.

before:
```
127.0.0.1:6379> DEBUG htstats 9
[Dictionary HT]
Hash table 0 stats (main hash table):
No stats available for empty dictionaries
[Expires HT]
Hash table 0 stats (main hash table):
No stats available for empty dictionaries
```

after:
```
127.0.0.1:6379> DEBUG htstats 9
[Dictionary HT]
[Expires HT]
```
roggervalf pushed a commit to roggervalf/redis that referenced this pull request Feb 11, 2024
…redis#13031)

When the dict is NULL, we also need to push resize_cursor, otherwise it
will keep doing useless continue here, and there is no way to resize the
other dict behind it.

Introduced in redis#12822.

---------

Co-authored-by: Oran Agra <oran@redislabs.com>
roggervalf pushed a commit to roggervalf/redis that referenced this pull request Feb 11, 2024
…dis#13033)

After redis#12822, when pubsubshard_channels became empty, kvstoreDictDelete
will delete the dict (which is the only one currently deleting dicts
that
become empty) and in the next loop, we will make an invalid call to
dictNext.

After the dict becomes empty, we break out of the loop without calling
dictNext.
oranagra added a commit that referenced this pull request Mar 13, 2024
…13072)

Currently (following #11695, and #12822), keys kvstore and expires
kvstore both flag with ON_DEMAND, it means that a cluster node will
only allocate a dict when the slot is assigned to it and populated,
but on the other hand, when the slot is unassigned, the dict will
remain allocated.

We considered releasing the dict when the slot is unassigned, but it
causes complications on replicas. On the other hand, from benchmarks
we conducted, it looks like the performance impact of releasing the
dict when it becomes empty and re-allocate it when a key is added
again, isn't huge.

This PR add KVSTORE_FREE_EMPTY_DICTS to cluster mode keys / expires
kvstore.

The impact is about about 2% performance drop, for this hopefully
uncommon scenario.

---------

Co-authored-by: Oran Agra <oran@redislabs.com>
funny-dog pushed a commit to funny-dog/redis that referenced this pull request Sep 17, 2025
…re (redis#12822)

# Description
Gather most of the scattered `redisDb`-related code from the per-slot
dict PR (redis#11695) and turn it to a new data structure, `kvstore`. i.e.
it's a class that represents an array of dictionaries.

# Motivation
The main motivation is code cleanliness, the idea of using an array of
dictionaries is very well-suited to becoming a self-contained data
structure.
This allowed cleaning some ugly code, among others: loops that run twice
on the main dict and expires dict, and duplicate code for allocating and
releasing this data structure.

# Notes
1. This PR reverts the part of redis#12848
where the `rehashing` list is global (handling rehashing `dict`s is
under the responsibility of `kvstore`, and should not be managed by the
server)
2. This PR also replaces the type of `server.pubsubshard_channels` from
`dict**` to `kvstore` (original PR:
redis#12804). After that was done,
server.pubsub_channels was also chosen to be a `kvstore` (with only one
`dict`, which seems odd) just to make the code cleaner by making it the
same type as `server.pubsubshard_channels`, see
`pubsubtype.serverPubSubChannels`
3. the keys and expires kvstores are currenlty configured to allocate
the individual dicts only when the first key is added (unlike before, in
which they allocated them in advance), but they won't release them when
the last key is deleted.

Worth mentioning that due to the recent change the reply of DEBUG
HTSTATS changed, in case no keys were ever added to the db.

before:
```
127.0.0.1:6379> DEBUG htstats 9
[Dictionary HT]
Hash table 0 stats (main hash table):
No stats available for empty dictionaries
[Expires HT]
Hash table 0 stats (main hash table):
No stats available for empty dictionaries
```

after:
```
127.0.0.1:6379> DEBUG htstats 9
[Dictionary HT]
[Expires HT]
```
funny-dog pushed a commit to funny-dog/redis that referenced this pull request Sep 17, 2025
…redis#13031)

When the dict is NULL, we also need to push resize_cursor, otherwise it
will keep doing useless continue here, and there is no way to resize the
other dict behind it.

Introduced in redis#12822.

---------

Co-authored-by: Oran Agra <oran@redislabs.com>
funny-dog pushed a commit to funny-dog/redis that referenced this pull request Sep 17, 2025
…dis#13033)

After redis#12822, when pubsubshard_channels became empty, kvstoreDictDelete
will delete the dict (which is the only one currently deleting dicts
that
become empty) and in the next loop, we will make an invalid call to
dictNext.

After the dict becomes empty, we break out of the loop without calling
dictNext.
funny-dog pushed a commit to funny-dog/redis that referenced this pull request Sep 17, 2025
…edis#13072)

Currently (following redis#11695, and redis#12822), keys kvstore and expires
kvstore both flag with ON_DEMAND, it means that a cluster node will
only allocate a dict when the slot is assigned to it and populated,
but on the other hand, when the slot is unassigned, the dict will
remain allocated.

We considered releasing the dict when the slot is unassigned, but it
causes complications on replicas. On the other hand, from benchmarks
we conducted, it looks like the performance impact of releasing the
dict when it becomes empty and re-allocate it when a key is added
again, isn't huge.

This PR add KVSTORE_FREE_EMPTY_DICTS to cluster mode keys / expires
kvstore.

The impact is about about 2% performance drop, for this hopefully
uncommon scenario.

---------

Co-authored-by: Oran Agra <oran@redislabs.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

Status: Done

Development

Successfully merging this pull request may close these issues.

7 participants