Use a moving average of cache size estimates #151
Merged
Conversation
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
a511c95 to
ca7381f
Compare
With small caches, the outlier query is very effective at reducing the error bars on the cache size estimate. As the cache grows though, it becomes a small % of the total cache size. Since the entry sizes can have a long tail, the small number of large entries in the sample query can have a big effect on the overall estimate. To counteract this, we'll use a moving average of the last N estimates. The estimates will be stored directly in the cache so can be shared amongst all processes. We'll calculate N such that we'll try to have sampled at least 0.05% of all records in the cache, with a maximum of 50 estimates. Testing shows this should roughly keep us within a +/-5% error margin. There's a race condition on writing the moving average back, but that should be rare and not important. If the cache is small enough so that the queries sample all the data, we'll just write the exact value back to the cache and ignore previous estimates.
ca7381f to
4e18cce
Compare
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.
With small caches, the outlier query is very effective at reducing the
error bars on the cache size estimate. As the cache grows though, it
becomes a small % of the total cache size.
Since the entry sizes can have a long tail, the small number of large
entries in the sample query can have a big effect on the overall
estimate.
To counteract this, we'll use a moving average of the last N estimates.
The estimates will be stored directly in the cache so can be shared
amongst all processes.
We'll calculate N such that we'll try to have sampled at least 0.05% of
all records in the cache, with a maximum of 50 estimates. Testing shows
this should roughly keep us within a +/-5% error margin.
There's a race condition on writing the moving average back, but that
should be rare and not important.
If the cache is small enough so that the queries sample all the data,
we'll just write the exact value back to the cache and ignore previous
estimates.