Bloom filter

As explained in ScyllaDB in Action

A Bloom filter is a probabilistic membership structure that can report possible membership or definite non-membership with a configurable false-positive rate.

A Bloom filter is a probabilistic membership structure that quickly checks whether a value might appear in a file. A negative result is definite; a positive result may be a false positive. section 8.3.3

ScyllaDB maintains one Bloom filter per SSTable to avoid searching every file during a read. The filter stores hash results in a bit array; unset result bits prove that the key is absent from that SSTable. section 8.3.3 section 8.5

Checking an SSTable for a key

Suppose a key hashes to positions 2, 4, and 6 in a ten-bit filter. Creation sets those bits. A later lookup hashes the partition key again: if any of those bits is unset, the key is not in the SSTable; if all are set, Scylla searches the file because a collision may have produced a false positive. section 8.3.3

Figure 8.13 The Bloom filter allows a query to quickly check whether an SSTable contains a given key.

Use the figure to trace how a Bloom filter narrows an SSTable query before value lookup. section 8.3.3

How ScyllaDB in Action covers it

How deep it goes

Explains bit arrays, multiple hashes, collisions, false positives, and filter sizing, but stops short of implementation configuration.

Examples

Uses a ten-bit filter with hash positions 2, 4, and 6 to demonstrate membership checks and collisions.

What it assumes

Assumes familiarity with SSTables, partition keys, hash functions, and bit arrays.

What you can do after

Evaluate how probabilistic membership checks reduce unnecessary SSTable reads while allowing false positives.

How it connects

Connects Bloom filters to SSTables, partition keys, hash functions, bit arrays, indexes, and compaction.

liveBookmanning.com

Read ScyllaDB in Action on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Advanced Algorithms and Data StructuresA Bloom filter is a space-efficient probabilistic data structure for testing set membership that can report false positives but not false negatives.

Compare how 2 books explain bloom filter →

Related concepts

• false positiveproduces · A false positive is a result that incorrectly indicates a condition or class is present when it is absent.
• hash functionuses · A hash function deterministically maps input data to a value in a bounded output range, commonly for indexing, lookup, comparison, or integrity checking.
• binary vectorhas part · A binary vector is an ordered sequence of elements, each restricted to one of two values, conventionally zero or one.

This explainer was generated by Manning's knowledge graph from the text of ScyllaDB in Action. The section links point to the parts of the book it draws on.