facebook / facebook/rocksdb

Benchmark with key prefix distribution is incorrectly sampled

Open
#8,355 2 comments 0 reactions 1 assignee Assigned to @zhichao-cao View on GitHub
question
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.