Cleanup key tracking documentation and table management by madolson · Pull Request #8039 · redis/redis

madolson · 2020-11-10T19:36:35Z

This change updates how we manage CSC tracking tables to improve memory efficiency and reduce unnecessary messages to clients.

The main change is we now always clear out the tracking table when flushdb is called instead instead of just for flushall. The original motivation here was back when there was a 16 million slot table, it was expensive to clean up so we didn't want to free it. However, there needed to be some way to reclaim the memory used by the table, so flushall was for that purpose. Now that it's less expensive to clear the table, we should always do it, since we are already notifying all the clients to free out their local caches.

The secondary change here is that we also free client tracking tables asynchronously when requested. The tracking table can get very large, and could block the main thread for several seconds otherwise.

oranagra · 2020-11-10T19:59:10Z

@madolson LGTM, but i don't trust myself in this area of the code base.
are you sure the TrackingTable is no longer needed when just one db was flushed (and others are kept)?
i suppose that's right since we sent a NULL invalidation message to all clients, but maybe it has other purposes (i just don't know that area and too busy to dig in now).

i find the desire to not pay the price of flushing the whole 16m slots back then on flushdb, and yet agreeing to pay it for flushall, odd.
i could understand that if you had to scan the data structure on flushdb you want to avoid it, but on flushall you can just release it without scanning.
can you clear that for me?

madolson · 2020-11-10T21:55:01Z

AFAIK there is no other logic there, @soloestoy was the original contributor of this so maybe he has a better idea.

The old implementation was a 16 million item array of radix trees that pointed to clients. You couldn't simply just free the array, you needed to loop through it looking for radix trees, and free all those too. So even if there was just one key being tracked by one client, you had to pay a huge cost to do flushall.

A side node, we probably should free the radix tree async when flushall async is used, and I intend to do some testing on that to see if it's really that important.

madolson · 2020-11-10T22:21:01Z

I guess another issue is someone might have been ignoring the flush message, and relying on the invalidations to eventually get sent.

hwware · 2020-11-11T02:53:08Z

Hello @madolson @oranagra , I used to do some benchmark testing on this part and hopefully I can provide some hint to the optimization of this tracking cleanup performance issue.
What I did is doing this steps:

start redis server with empty db
using ./redis-benchmark -t get -r 100000000 -n 10000000000000000 --enable-tracking to populate the tracking table
stop the benchmark and verify the tracking table being populated through info command.(through tracking_total_keys and tracking_total_items)
doing flushall
i noticed signficant delay in the 4th step if the tracking table is big. in my Mac for 1 million tracking keys I see 1.5s delay when i doing flushall eventhough the keyspace is empty, but if we start the same step with non --enable-tracking flag when we start the benchmarking program, the call replied immediatey and it is hardly notice any latencies..

Therefore, as @madolson mentioned, we may need to think of the way to free tracking table async when the tracking table grows big. I was thinking about the implementation also, maybe we should provide a hardcoded value for now, if the size of tracking table grows bigger than that, we can unlink the table and freeing it in the background thread. but we need to provide the bio interface for freeing the radix tree.. Or we encourge user limiting the tracking-table-max-keys configuration? How do you think on this? Or am I missing something here? Thanks!

hwware · 2020-11-11T03:01:03Z

Also I guess cleaning up tracking table and sending invalidation can be used when the configured max memory was reached?

madolson · 2020-11-11T19:44:30Z

Isn't it kind of weird that we are tracking key misses? I didn't realize we were doing that.

madolson · 2020-11-24T05:33:51Z

@hwware I updated the code to also free the tracking table async. I also did some refactoring of bio, since it might be my least favorite code in all of Redis.

@soloestoy Would still love your input about changing the behavior of flushdb also freeing the table.

src/bio.h

soloestoy · 2020-12-07T03:26:10Z

Hi @madolson I reread the history of tracking on flushdb and flushall, I'm sure free the TrackingTable when flushdb called is right and safe, and we do need an async way to free it.

About the bio refactoring, I think it's better to split this PR into two different PRs: one is the async freeing TrackingTable(with the lazyfree refactoring), the other one is the whole bio refactoring, it more clear I think.

madolson · 2020-12-07T21:16:07Z

@soloestoy Thanks! I was originally going to split it, but I also thought it's easier to review the BIO refactor when it's motivated by a new callback. The total change is pretty small, so I think it's probably easier to keep them together? If you strongly disagree, I'll split them.

madolson · 2020-12-10T01:40:19Z

@redis/core-team Going to take that roughly as the code is okay, but it's still a major decision.

oranagra · 2020-12-10T08:46:53Z

@madolson what changed since my last review of the code? just a rebase?
I see that back then the only thing bothered me is that i didn't understand the reasons why the old version flushed TrackingTable only when all databases are emptied and not just one.
I don't know that code well enough, so all i can say is that given that you and Zhao think that's a safe change, i'm ok with it (aka LGTM!)

madolson · 2020-12-10T15:54:31Z

@oranagra The table is flushed async now, the behavior altering change is the same as before.

yossigo

@madolson LGTM, with one minor comment.

yossigo · 2020-12-13T16:09:04Z

src/bio.c


+struct lazy_free_job {
+    lazy_free_fn *fn; /* Function that will free the provided arguments */
+    void *args[1]; /* List of arguments to be passed to the free function */


Consider args[0] to make it more clear that it's dynamically allocated and it will also make the sizeof calculation more correct when allocating.

It would be cleaner, but it throws a warning:
"warning: zero size arrays are an extension [-Wzero-length-array]". I suppose it's more portable this way. I think it's okay because we need at least one argument.

i you can use an empty array then, like we use here:

typedef struct clientReplyBlock { size_t size, used; char buf[]; } clientReplyBlock;

that seems the portable way to do it (C99).

Apparently that can't exist in nested structures? I moved it out of the struct, so now we'll use a couple extra bytes but it's cleaner.

For current bio use, it's ok, but i think it should be more generic, what should we do if we we add a new bio job, such as dump and restore keys.

Cleanup key tracking documentation, always cleanup the tracking table, and free the tracking table in an async manner when applicable.

madolson requested a review from soloestoy November 10, 2020 19:36

madolson linked an issue Nov 10, 2020 that may be closed by this pull request

[QUESTION]Question regarding Client Side Caching #7681

Closed

madolson force-pushed the unstable-csc-cleanup branch from 22c6d73 to fd1bc78 Compare November 24, 2020 04:43

JimB123 reviewed Nov 24, 2020

View reviewed changes

src/bio.h Outdated Show resolved Hide resolved

Cleanup key tracking documentation and table management

cd2019f

madolson force-pushed the unstable-csc-cleanup branch from d964531 to cd2019f Compare December 7, 2020 20:56

madolson added 2 commits December 7, 2020 13:02

Handled upstream merge so the delta is smaller

a1b4425

Alignment

2a588c6

madolson added the state:major-decision Requires core team consensus label Dec 10, 2020

yossigo added the approval-needed Waiting for core team approval to be merged label Dec 10, 2020

yossigo reviewed Dec 13, 2020

View reviewed changes

yossigo mentioned this pull request Dec 13, 2020

client side caching: free space tracking table when calling flushdb #7341

Closed

Cleanup free_arg size

3e3ef83

yossigo approved these changes Dec 15, 2020

View reviewed changes

madolson added release-notes indication that this issue needs to be mentioned in the release notes and removed state:major-decision Requires core team consensus labels Dec 23, 2020

madolson merged commit 59ff42c into redis:unstable Dec 24, 2020

oranagra mentioned this pull request Jan 10, 2021

Redis 6.2 rc2 #8305

Merged

Conversation

madolson commented Nov 10, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

oranagra commented Nov 10, 2020

Uh oh!

madolson commented Nov 10, 2020

Uh oh!

madolson commented Nov 10, 2020

Uh oh!

hwware commented Nov 11, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

hwware commented Nov 11, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

madolson commented Nov 11, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

madolson commented Nov 24, 2020

Uh oh!

Uh oh!

soloestoy commented Dec 7, 2020

Uh oh!

madolson commented Dec 7, 2020

Uh oh!

madolson commented Dec 10, 2020

Uh oh!

oranagra commented Dec 10, 2020

Uh oh!

madolson commented Dec 10, 2020

Uh oh!

yossigo left a comment

Choose a reason for hiding this comment

Uh oh!

yossigo Dec 13, 2020

Choose a reason for hiding this comment

Uh oh!

madolson Dec 14, 2020

Choose a reason for hiding this comment

Uh oh!

oranagra Dec 14, 2020

Choose a reason for hiding this comment

Uh oh!

madolson Dec 15, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ShooterIT Dec 21, 2020

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

madolson commented Nov 10, 2020 •

edited

Loading

hwware commented Nov 11, 2020 •

edited

Loading

hwware commented Nov 11, 2020 •

edited

Loading

madolson commented Nov 11, 2020 •

edited

Loading

madolson Dec 15, 2020 •

edited

Loading