Skip to content

Conversation

@oranagra
Copy link
Member

There's a rare case which leads to stagnation in the defragger, causing
it to keep scanning the keyspace and do nothing (not moving any
allocation), this happens when all the allocator slabs of a certain bin
have the same % utilization, but the slab from which new allocations are
made have a lower utilization.

this commit fixes it by removing the current slab from the overall
average utilization of the bin, and also eliminate any precision loss in
the utilization calculation and move the decision about the defrag to
reside inside jemalloc.

and also add a test that consistently reproduce this issue.

oranagra added 2 commits May 20, 2020 14:09
also support:
  debug mallctl-str thread.tcache.flush VOID
There's a rare case which leads to stagnation in the defragger, causing
it to keep scanning the keyspace and do nothing (not moving any
allocation), this happens when all the allocator slabs of a certain bin
have the same % utilization, but the slab from which new allocations are
made have a lower utilization.

this commit fixes it by removing the current slab from the overall
average utilization of the bin, and also eliminate any precision loss in
the utilization calculation and move the decision about the defrag to
reside inside jemalloc.

and also add a test that consistently reproduce this issue.
@antirez antirez merged commit af34245 into redis:unstable May 20, 2020
@antirez
Copy link
Contributor

antirez commented May 20, 2020

Thank you @oranagra

@oranagra oranagra deleted the defrag_edge_case branch May 20, 2020 13:32
JackieXie168 pushed a commit to JackieXie168/redis that referenced this pull request Jun 18, 2020
fix a rare active defrag edge case bug leading to stagnation
@oranagra
Copy link
Member Author

Yes, I'm aware of that... Apparently I wasn't able to solve the problem.
I'm currently out of ideas.. Maybe we should disable the test at some point..

oranagra added a commit that referenced this pull request Nov 21, 2021
Background:
Following the upgrade to jemalloc 5.2, there was a test that used to be flaky and
started failing consistently (on 32bit), so we disabled it ​(see #9645).

This is a test that i introduced in #7289 when i attempted to solve a rare stagnation
problem, and it later turned out i failed to solve it, ans what's more i added a test that
caused it to be not so rare, and as i mentioned, now in jemalloc 5.2 it became consistent on 32bit.

Stagnation can happen when all the slabs of the bin are equally utilized, so the decision
to move an allocation from a relatively empty slab to a relatively full one, will never
happen, and in that test all the slabs are at 50% utilization, so the defragger could just
keep scanning the keyspace and not move anything.

What this PR changes:
* First, finally in jemalloc 5.2 we have the count of non-full slabs, so when we compare
  the utilization of the current slab, we can compare it to the average utilization of the non-full
  slabs in our bin, instead of the total average of our bin. this takes the full slabs out of the game,
  since they're not candidates for migration (neither source nor target).
* Secondly, We add some 12% (100/8) to the decision to defrag an allocation, this is the part
  that aims to avoid stagnation, and it's especially important since the above mentioned change
  can get us closer to stagnation.
* Thirdly, since jemalloc 5.2 adds sharded bins, we take into account all shards (something
  that's missing from the original PR that merged it), this isn't expected to make any difference
  since anyway there should be just one shard.

How this was benchmarked.
What i did was run the memefficiency test unit with `--verbose` and compare the defragger hits
and misses the tests reported.
At first, when i took into consideration only the non-full slabs, it got a lot worse (i got into
stagnation, or just got a lot of misses and a lot of hits), but when i added the 10% i got back
to results that were slightly better than the ones of the jemalloc 5.1 branch. i.e. full defragmentation
was achieved with fewer hits (relocations), and fewer misses (keyspace scans).
hwware pushed a commit to hwware/redis that referenced this pull request Dec 20, 2021
Background:
Following the upgrade to jemalloc 5.2, there was a test that used to be flaky and
started failing consistently (on 32bit), so we disabled it ​(see redis#9645).

This is a test that i introduced in redis#7289 when i attempted to solve a rare stagnation
problem, and it later turned out i failed to solve it, ans what's more i added a test that
caused it to be not so rare, and as i mentioned, now in jemalloc 5.2 it became consistent on 32bit.

Stagnation can happen when all the slabs of the bin are equally utilized, so the decision
to move an allocation from a relatively empty slab to a relatively full one, will never
happen, and in that test all the slabs are at 50% utilization, so the defragger could just
keep scanning the keyspace and not move anything.

What this PR changes:
* First, finally in jemalloc 5.2 we have the count of non-full slabs, so when we compare
  the utilization of the current slab, we can compare it to the average utilization of the non-full
  slabs in our bin, instead of the total average of our bin. this takes the full slabs out of the game,
  since they're not candidates for migration (neither source nor target).
* Secondly, We add some 12% (100/8) to the decision to defrag an allocation, this is the part
  that aims to avoid stagnation, and it's especially important since the above mentioned change
  can get us closer to stagnation.
* Thirdly, since jemalloc 5.2 adds sharded bins, we take into account all shards (something
  that's missing from the original PR that merged it), this isn't expected to make any difference
  since anyway there should be just one shard.

How this was benchmarked.
What i did was run the memefficiency test unit with `--verbose` and compare the defragger hits
and misses the tests reported.
At first, when i took into consideration only the non-full slabs, it got a lot worse (i got into
stagnation, or just got a lot of misses and a lot of hits), but when i added the 10% i got back
to results that were slightly better than the ones of the jemalloc 5.1 branch. i.e. full defragmentation
was achieved with fewer hits (relocations), and fewer misses (keyspace scans).
@yoav-steinberg yoav-steinberg mentioned this pull request Apr 21, 2022
1 task
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants