Bloom Filters

[ltbringer]

SSTables may grow as large as 100GBs. This will require a tradeoff between search using disk-seek vs loading the sstable in memory. Even after using multiple threads, it is difficult to offer high throughput when the key doesn't exist.

A Bloom Filter is a probabilistic data structure that could take a key and say one of:

1. Maybe the key exists.
2. The key surely doesn't exist.

In other words, there is a chance of false positives but no chance of false negatives. Here, the rate of false positives is controlled by:

$p = (1 - e^{-kn/m})^k$
Where¹,

• $p$ is the false positive rate
• $k$ is the number of hash functions used
• $n$ is the number of keys in the filter
• $m$ is the size of the bit vector.

Footnotes

1. https://en.wikipedia.org/wiki/Bloom_filter ↩