Revision 7e62c5d67a6afccbcc92c38b58c8af93af7814d8 authored by Aaron Gao on 10 May 2017, 08:32:52 UTC, committed by Aaron Gao on 10 May 2017, 21:06:54 UTC
Summary: Consider BlockReadAmpBitmap with bytes_per_bit = 32. Suppose bytes [a, b) were used, while bytes [a-32, a) and [b+1, b+33) weren't used; more formally, the union of ranges passed to BlockReadAmpBitmap::Mark() contains [a, b) and doesn't intersect with [a-32, a) and [b+1, b+33). Then bits [floor(a/32), ceil(b/32)] will be set, and so the number of useful bytes will be estimated as (ceil(b/32) - floor(a/32)) * 32, which is on average equal to b-a+31. An extreme example: if we use 1 byte from each block, it'll be counted as 32 bytes from each block. It's easy to remove this bias by slightly changing the semantics of the bitmap. Currently each bit represents a byte range [i*32, (i+1)*32). This diff makes each bit represent a single byte: i*32 + X, where X is a random number in [0, 31] generated when bitmap is created. So, e.g., if you read a single byte at random, with probability 31/32 it won't be counted at all, and with probability 1/32 it will be counted as 32 bytes; so, on average it's counted as 1 byte. *But there is one exception: the last bit will always set with the old way.* (*) - assuming read_amp_bytes_per_bit = 32. Closes https://github.com/facebook/rocksdb/pull/2259 Differential Revision: D5035652 Pulled By: lightmark fbshipit-source-id: bd98b1b9b49fbe61f9e3781d07f624e3cbd92356
1 parent 2014cdf
File | Mode | Size |
---|---|---|
arcanist_util | ||
buckifier | ||
build_tools | ||
cache | ||
cmake | ||
coverage | ||
db | ||
docs | ||
env | ||
examples | ||
hdfs | ||
include | ||
java | ||
memtable | ||
monitoring | ||
options | ||
port | ||
table | ||
third-party | ||
tools | ||
util | ||
utilities | ||
.clang-format | -rw-r--r-- | 138 bytes |
.deprecated_arcconfig | -rw-r--r-- | 566 bytes |
.gitignore | -rw-r--r-- | 708 bytes |
.travis.yml | -rw-r--r-- | 2.3 KB |
AUTHORS | -rw-r--r-- | 247 bytes |
CMakeLists.txt | -rw-r--r-- | 26.5 KB |
CONTRIBUTING.md | -rw-r--r-- | 733 bytes |
DEFAULT_OPTIONS_HISTORY.md | -rw-r--r-- | 1.4 KB |
DUMP_FORMAT.md | -rw-r--r-- | 763 bytes |
HISTORY.md | -rw-r--r-- | 42.6 KB |
INSTALL.md | -rw-r--r-- | 4.7 KB |
LANGUAGE-BINDINGS.md | -rw-r--r-- | 712 bytes |
LICENSE | -rw-r--r-- | 1.6 KB |
Makefile | -rw-r--r-- | 53.2 KB |
PATENTS | -rw-r--r-- | 1.9 KB |
README.md | -rw-r--r-- | 1.4 KB |
ROCKSDB_LITE.md | -rw-r--r-- | 1.0 KB |
TARGETS | -rw-r--r-- | 18.1 KB |
USERS.md | -rw-r--r-- | 4.9 KB |
Vagrantfile | -rw-r--r-- | 877 bytes |
WINDOWS_PORT.md | -rw-r--r-- | 12.5 KB |
appveyor.yml | -rw-r--r-- | 416 bytes |
src.mk | -rw-r--r-- | 24.1 KB |
thirdparty.inc | -rw-r--r-- | 7.8 KB |
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...