Benchmark with key prefix distribution is incorrectly sampled
- Dominant language
- C++
- Stars
- 32.1k
- Forks
- 6.9k
- Avg merge
- 32m
- Merged PRs (30d)
- 1
Description
In the benchmark from the FAST 2020 paper that uses a two-term exponential distribution, the sampling from that distribution is quite flawed, resulting in as much as a 2x error in the frequency of writes generated to each key range, particularly in the tail.
The current sampling algorithm tries to map the bucket frequencies onto an integer scale between [0, amplify] where amplify is 1/least_frequent_weight. This mapping is only accurate if all of the frequencies are integer multiples of the least frequent weight, which is not the case -- particularly in the tail, most of the bucket frequencies will be only slightly larger than the least frequent bucket, and since a floor is used in the integer mapping, they'll end up getting rounded down to having the same frequency as the least frequent bucket. This means that some buckets will have as much as 2x relative error - for example, a bucket might have 1.99x the frequency of the least frequent one, yet still be assigned an integer weight equal to the least frequent one.
This mapping onto integers seems unnecessary and flawed vs just mapping onto doubles between 0 and 1 and generating a uniform distribution in that range.
I don't know to what extent this invalidates the main results of the paper, but figured I would report it since it seems like a pretty error in the experimental setup.
Contributor guide
Assessment
This issue has not been assessed yet.