Bloom Filter-Based Absence-First Lookup
A Bloom Filter is a probabilistic data structure that approximates membership without storing every element in the set directly, relying instead on a single bit array and multiple hash positions. When the result is "absent" (negative), you can be certain the element is not in the set; when the result is "present" (positive), the element may actually exist, or it may be a false positive. Burton Bloom's 1970 paper introduced this structure, which trades "tolerable errors (false positives)" for significant savings in space and lookup time.
Β· Practice memo Β· 56 min read Β· Hard
What is a Bloom Filter
A Bloom Filter is a probabilistic data structure that approximates membership using only a single bit array and a set of hash positions, without storing every element of a set directly. When the result is "negative" (not found), you can conclude with certainty that the element is not in the set; when the result is "positive" (found), the element may actually exist, or it may be a false positive. Burton Bloom's 1970 paper introduced this structure, which trades "allowable errors (false positives)" for dramatic savings in space and lookup time.1
Why a precheck is necessary
A Bloom Filter's answers are not symmetric: mightContain(key) == false can be trusted to mean the key is absent, but true guarantees nothing about actual existence. So it is not a stand-in for the authoritative store; you use it as a negative precheck that runs ahead of the expensive exact lookup.
On
false, skip the remote lookup.On
true, go to the source store and confirm exactly.
Read a positive as existence and every false positive the Bloom Filter allows turns straight into a business error.
Example: Artifact catalog
This example works with an immutable artifact catalog where each artifact is identified by a SHA-256 digest. Because an artifact digest is already a uniform 32-byte value, two 64-bit hash seeds are read from the leading bytes of the digest. Multiple bit positions are then generated using the formula. Kirsch and Mitzenmacher showed that generating multiple hash positions for a Bloom Filter as linear combinations of two hashes preserves asymptotic false-positive performance.2
The conditions behind "no false negatives"
"A Bloom Filter has no false negatives" is a conditional statement: the mathematical structure only guarantees it inside the conditions, which are these.
the inserted bits were never cleared,
the same key encoding and hash rules are used,
the filter contains every element of the source set,
and the bitset is intact.
Break any one of these and you get false negatives in production. An element that exists in the source today but was missing from the snapshot the lookup used falls out as negative, and processes running different hash protocols do the same thing. The data structure is not defective; the operational environment does not line up, and that is where the false negative comes from.
Trade-offs and Limitations
The trade-offs sit in capacity planning and in what the structure cannot do. Inserting past the expected element count does not break it immediately; bit density rises and the false-positive rate degrades. Correctness does not collapse on the spot, but the Maybe share grows, so skipping exact lookups buys less and less. Deletion, enumeration and exact counts are not jobs a basic Bloom Filter takes on in the first place.
Bloom Filter
= Fixed-size bit array
k deterministic bit positions
Add(x):
Set the bit at each index_i(x) to 1
MightContain(x):
All bits at index_i(x) are 1
β Maybe
Any one of them is 0
β Definitely Not
Design formulas:
m β -n Β· ln(p) / (ln 2)Β²
k β (m / n) Β· ln 2
n = expected number of insertions
m = number of bits
k = number of hash positions
p = target false-positive rate
Estimated false-positive rate:
pΜ = (1 - e^(-kn/m))^k1. Problem Scenario
Say a build system uses a content-addressed artifact store.
Artifact ID:
SHA-256 digest 32 bytes
Authoritative store:
remote object storage
Expensive operation:
HEAD or metadata DB lookup
Catalog snapshot:
list of all artifact digests present in a specific
catalogVersionThe read path looks like this.
1. Artifact digest format validation
2. Bloom Filter lookup
Definitely Not
β Returns absent without any remote I/O
Maybe
β Exact repository lookup
β Returns actual existence resultSuppose the snapshot holds ten million artifacts and most requests ask for digests that do not exist. Then it is reasonable to assume a Bloom Filter can sweep away a large volume of remote HEAD requests. The implementation below, however, is not allowed.
Bloom Filter returns Maybe
β immediately return that the artifact existsMaybe is not exact membership. If the filter was built against catalogVersion=42, a negative result is only valid for that same catalog version.
Filter version:
42
Repository query version:
43
Artifact newly added in Version 43
β Bit not present in Filter 42
β Operational false negativeSo the snapshot carries the following contract with it.
ArtifactIndexSnapshot
- catalogVersion
- expectedItemCount
- insertedItemCount
- targetFalsePositiveRate
- bitCount
- hashCount
- hashProtocolVersion
- bitset2. Core Implementation
C++23
The C++ implementation holds the 32-byte digest as a value type, keeps the filter internals as a uint64_t word array, and exposes no mutation API once it is built.
#include <algorithm>
#include <array>
#include <bit>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <expected>
#include <limits>
#include <span>
#include <utility>
#include <vector>
class ArtifactDigest final
{
public:
static constexpr std::size_t byteCount = 32;
explicit ArtifactDigest(
std::array<std::byte, byteCount> bytes) noexcept
: bytes_(std::move(bytes))
{
}
[[nodiscard]]
std::span<const std::byte, byteCount>
getBytes() const noexcept
{
return bytes_;
}
private:
std::array<std::byte, byteCount> bytes_;
};
struct BloomSpec final
{
std::size_t expectedItemCount;
double targetFalsePositiveRate;
};
enum class BloomError
{
InvalidExpectedItemCount,
InvalidFalsePositiveRate,
CapacityExceeded,
FilterTooLarge,
};
template<typename T>
using BloomResult = std::expected<T, BloomError>;
class ArtifactBloomFilter final
{
public:
[[nodiscard]]
static BloomResult<ArtifactBloomFilter> create(
std::span<const ArtifactDigest> digests,
const BloomSpec& spec)
{
auto layout = createLayout(spec);
if (!layout)
{
return std::unexpected(layout.error());
}
if (digests.size() > spec.expectedItemCount)
{
return std::unexpected(
BloomError::CapacityExceeded);
}
ArtifactBloomFilter filter{
*layout,
digests.size()};
for (const ArtifactDigest& digest : digests)
{
filter.addDigest(digest);
}
return filter;
}
[[nodiscard]]
bool mightContain(
const ArtifactDigest& digest) const noexcept
{
Probe probe = createProbe(digest);
for (std::uint32_t index = 0;
index < hashCount_;
++index)
{
if (!getBit(probe.bitIndex))
{
return false;
}
probe.advance(bitCount_);
}
return true;
}
[[nodiscard]]
std::size_t getBitCount() const noexcept
{
return bitCount_;
}
[[nodiscard]]
std::uint32_t getHashCount() const noexcept
{
return hashCount_;
}
[[nodiscard]]
std::size_t getInsertedItemCount() const noexcept
{
return insertedItemCount_;
}
[[nodiscard]]
double estimateFalsePositiveRate() const noexcept
{
const double m =
static_cast<double>(bitCount_);
const double n =
static_cast<double>(insertedItemCount_);
const double k =
static_cast<double>(hashCount_);
return std::pow(
-std::expm1(-k * n / m),
k);
}
[[nodiscard]]
double getFillRatio() const noexcept
{
std::size_t setBitCount = 0;
for (const std::uint64_t word : words_)
{
setBitCount +=
std::popcount(word);
}
return static_cast<double>(setBitCount)
/ static_cast<double>(bitCount_);
}
[[nodiscard]]
std::vector<std::byte> serializeBits() const
{
std::vector<std::byte> bytes;
bytes.reserve(bitCount_ / 8);
for (const std::uint64_t word : words_)
{
for (std::size_t shift = 0;
shift < 64;
shift += 8)
{
bytes.push_back(
static_cast<std::byte>(
(word >> shift) & 0xFFULL));
}
}
return bytes;
}
private:
static constexpr double ln2 =
0.69314718055994530942;
static constexpr std::size_t minimumBitCount =
64;
static constexpr std::size_t maximumExpectedItemCount =
std::size_t{1} << 30;
static constexpr std::size_t maximumBitCount =
std::size_t{1} << 30;
struct Layout final
{
std::size_t bitCount;
std::uint32_t hashCount;
};
struct Probe final
{
std::size_t bitIndex;
std::size_t step;
void advance(std::size_t bitCount) noexcept
{
bitIndex += step;
if (bitIndex >= bitCount)
{
bitIndex -= bitCount;
}
}
};
std::vector<std::uint64_t> words_;
std::size_t bitCount_;
std::uint32_t hashCount_;
std::size_t insertedItemCount_;
ArtifactBloomFilter(
const Layout& layout,
std::size_t insertedItemCount)
: words_(layout.bitCount / 64, 0),
bitCount_(layout.bitCount),
hashCount_(layout.hashCount),
insertedItemCount_(insertedItemCount)
{
}
void addDigest(
const ArtifactDigest& digest) noexcept
{
Probe probe = createProbe(digest);
for (std::uint32_t index = 0;
index < hashCount_;
++index)
{
setBit(probe.bitIndex);
probe.advance(bitCount_);
}
}
[[nodiscard]]
Probe createProbe(
const ArtifactDigest& digest) const noexcept
{
const auto bytes = digest.getBytes();
const std::uint64_t first =
readU64BigEndian(bytes.first<8>());
const std::uint64_t second =
readU64BigEndian(
bytes.subspan<8, 8>());
return Probe{
.bitIndex =
static_cast<std::size_t>(
first % bitCount_),
.step =
static_cast<std::size_t>(
(second | 1ULL) % bitCount_),
};
}
void setBit(std::size_t bitIndex) noexcept
{
const std::size_t wordIndex =
bitIndex >> 6;
const std::size_t bitOffset =
bitIndex & 63;
words_[wordIndex] |=
std::uint64_t{1} << bitOffset;
}
[[nodiscard]]
bool getBit(std::size_t bitIndex) const noexcept
{
const std::size_t wordIndex =
bitIndex >> 6;
const std::size_t bitOffset =
bitIndex & 63;
return (
words_[wordIndex]
& (std::uint64_t{1} << bitOffset)
) != 0;
}
[[nodiscard]]
static BloomResult<Layout> createLayout(
const BloomSpec& spec)
{
auto idealBitCount =
calculateIdealBitCount(spec);
if (!idealBitCount)
{
return std::unexpected(
idealBitCount.error());
}
Layout bestLayout{};
bool foundLayout = false;
for (std::uint32_t hashCount = 1;
hashCount <= 32;
++hashCount)
{
auto requiredBitCount =
calculateRequiredBitCountForHashCount(
spec.expectedItemCount,
hashCount,
spec.targetFalsePositiveRate);
if (!requiredBitCount)
{
continue;
}
std::size_t candidateBitCount =
alignToWord(
std::max(
minimumBitCount,
*requiredBitCount));
if (candidateBitCount > maximumBitCount)
{
continue;
}
double modeledRate =
calculateModeledFalsePositiveRate(
candidateBitCount,
spec.expectedItemCount,
hashCount);
if (!std::isfinite(modeledRate)
|| modeledRate
> spec.targetFalsePositiveRate)
{
if (candidateBitCount
> maximumBitCount - 64)
{
continue;
}
candidateBitCount += 64;
modeledRate =
calculateModeledFalsePositiveRate(
candidateBitCount,
spec.expectedItemCount,
hashCount);
}
if (std::isfinite(modeledRate)
&& modeledRate
<= spec.targetFalsePositiveRate)
{
const Layout candidateLayout{
.bitCount = candidateBitCount,
.hashCount = hashCount,
};
if (!foundLayout
|| candidateLayout.bitCount
< bestLayout.bitCount
|| (candidateLayout.bitCount
== bestLayout.bitCount
&& candidateLayout.hashCount
< bestLayout.hashCount))
{
bestLayout = candidateLayout;
foundLayout = true;
}
}
}
if (foundLayout)
{
return bestLayout;
}
return std::unexpected(
BloomError::FilterTooLarge);
}
[[nodiscard]]
static BloomResult<std::size_t>
calculateIdealBitCount(
const BloomSpec& spec)
{
if (spec.expectedItemCount == 0
|| spec.expectedItemCount
> maximumExpectedItemCount)
{
return std::unexpected(
BloomError::InvalidExpectedItemCount);
}
if (!std::isfinite(
spec.targetFalsePositiveRate)
|| spec.targetFalsePositiveRate <= 0.0
|| spec.targetFalsePositiveRate >= 1.0)
{
return std::unexpected(
BloomError::InvalidFalsePositiveRate);
}
const double ideal =
-static_cast<double>(
spec.expectedItemCount)
* std::log(
spec.targetFalsePositiveRate)
/ (ln2 * ln2);
if (!std::isfinite(ideal)
|| ideal > static_cast<double>(
maximumBitCount))
{
return std::unexpected(
BloomError::FilterTooLarge);
}
return std::max(
minimumBitCount,
static_cast<std::size_t>(
std::ceil(ideal)));
}
[[nodiscard]]
static BloomResult<std::size_t>
calculateRequiredBitCountForHashCount(
std::size_t itemCount,
std::uint32_t hashCount,
double targetRate)
{
const double n =
static_cast<double>(itemCount);
const double k =
static_cast<double>(hashCount);
const double root =
std::pow(targetRate, 1.0 / k);
const double denominator =
-std::log1p(-root);
const double required =
k * n / denominator;
if (!std::isfinite(required)
|| required > static_cast<double>(
maximumBitCount))
{
return std::unexpected(
BloomError::FilterTooLarge);
}
return std::max(
minimumBitCount,
static_cast<std::size_t>(
std::ceil(required)));
}
[[nodiscard]]
static double calculateModeledFalsePositiveRate(
std::size_t bitCount,
std::size_t itemCount,
std::uint32_t hashCount) noexcept
{
const double m =
static_cast<double>(bitCount);
const double n =
static_cast<double>(itemCount);
const double k =
static_cast<double>(hashCount);
return std::pow(
-std::expm1(-k * n / m),
k);
}
[[nodiscard]]
static std::size_t alignToWord(
std::size_t value) noexcept
{
return (value + 63) & ~std::size_t{63};
}
[[nodiscard]]
static std::uint64_t readU64BigEndian(
std::span<const std::byte, 8> bytes) noexcept
{
std::uint64_t result = 0;
for (const std::byte value : bytes)
{
result =
(result << 8)
| std::to_integer<std::uint8_t>(
value);
}
return result;
}
};Usage:
const BloomSpec spec{
.expectedItemCount = 1'000'000,
.targetFalsePositiveRate = 0.001,
};
const auto filterResult =
ArtifactBloomFilter::create(
artifactDigests,
spec);
if (!filterResult)
{
return filterResult.error();
}
const ArtifactBloomFilter filter =
std::move(*filterResult);
if (!filter.mightContain(requestedDigest))
{
return ArtifactLookup::absent();
}
// Since the result is Maybe, check the exact repository to confirm.
return repository.exists(requestedDigest);Because ArtifactBloomFilter does not retain the digests, the lifetime of the input span need only extend through the construction call. The returned filter directly owns the bitset.
In addition, serializeBits() exports the uint64_t word array as a little-endian byte sequence, producing the same representation as the other three implementations that write byte arrays.
Personal note: this code was written by a Chinese developer, and I no longer remember where I found it or when I saved it.
Python
Python uses a bytearray while building and stores immutable bytes in the finished filter.
from __future__ import annotations
from dataclasses import dataclass
from enum import Enum
from math import ceil, expm1, isfinite, log, log1p
from typing import Generic, Sequence, TypeAlias, TypeVar
TValue = TypeVar("TValue")
_DIGEST_LENGTH = 32
_MINIMUM_BIT_COUNT = 64
_MAXIMUM_EXPECTED_ITEM_COUNT = 1 << 30
_MAXIMUM_BIT_COUNT = 1 << 30
_LN2 = 0.6931471805599453
class BloomError(str, Enum):
INVALID_EXPECTED_ITEM_COUNT = (
"invalid_expected_item_count"
)
INVALID_FALSE_POSITIVE_RATE = (
"invalid_false_positive_rate"
)
CAPACITY_EXCEEDED = "capacity_exceeded"
FILTER_TOO_LARGE = "filter_too_large"
INVALID_DIGEST = "invalid_digest"
@dataclass(frozen=True, slots=True)
class Success(Generic[TValue]):
value: TValue
@dataclass(frozen=True, slots=True)
class Failure:
error: BloomError
Result: TypeAlias = Success[TValue] | Failure
@dataclass(frozen=True, slots=True)
class BloomSpec:
expected_item_count: int
target_false_positive_rate: float
@dataclass(frozen=True, slots=True)
class _Layout:
bit_count: int
hash_count: int
class ArtifactBloomFilter:
def __init__(
self,
bits: bytes,
bit_count: int,
hash_count: int,
inserted_item_count: int,
) -> None:
self._bits = bits
self._bit_count = bit_count
self._hash_count = hash_count
self._inserted_item_count = (
inserted_item_count
)
@classmethod
def create(
cls,
digests: Sequence[bytes],
spec: BloomSpec,
) -> Result[ArtifactBloomFilter]:
layout_result = _create_layout(spec)
if isinstance(layout_result, Failure):
return layout_result
if len(digests) > spec.expected_item_count:
return Failure(
BloomError.CAPACITY_EXCEEDED
)
normalized_digests: list[bytes] = []
for digest in digests:
normalized = _normalize_digest(digest)
if normalized is None:
return Failure(
BloomError.INVALID_DIGEST
)
normalized_digests.append(normalized)
layout = layout_result.value
bits = bytearray(layout.bit_count // 8)
for digest in normalized_digests:
_add_digest(
bits,
layout,
digest,
)
return Success(
cls(
bits=bytes(bits),
bit_count=layout.bit_count,
hash_count=layout.hash_count,
inserted_item_count=len(digests),
)
)
def might_contain(
self,
digest: bytes,
) -> bool:
normalized = _normalize_digest(digest)
if normalized is None:
raise ValueError(
"The artifact digest must be 32 bytes."
)
bit_index, step = _create_probe(
normalized,
self._bit_count,
)
for _ in range(self._hash_count):
if not _get_bit(
self._bits,
bit_index,
):
return False
bit_index = (
bit_index + step
) % self._bit_count
return True
def get_bit_count(self) -> int:
return self._bit_count
def get_hash_count(self) -> int:
return self._hash_count
def get_inserted_item_count(self) -> int:
return self._inserted_item_count
def estimate_false_positive_rate(
self,
) -> float:
m = float(self._bit_count)
n = float(self._inserted_item_count)
k = float(self._hash_count)
return (
-expm1(-k * n / m)
) ** k
def get_fill_ratio(self) -> float:
set_bit_count = sum(
value.bit_count()
for value in self._bits
)
return (
set_bit_count
/ self._bit_count
)
def _create_layout(
spec: BloomSpec,
) -> Result[_Layout]:
validation = _validate_spec(spec)
if validation is not None:
return Failure(validation)
ideal = (
-spec.expected_item_count
* log(spec.target_false_positive_rate)
/ (_LN2 * _LN2)
)
if (
not isfinite(ideal)
or ideal > _MAXIMUM_BIT_COUNT
):
return Failure(
BloomError.FILTER_TOO_LARGE
)
best_layout: _Layout | None = None
for hash_count in range(1, 33):
required_bit_count = (
_calculate_required_bit_count_for_hash_count(
spec.expected_item_count,
hash_count,
spec.target_false_positive_rate,
)
)
if required_bit_count is None:
continue
candidate_bit_count = _align_to_word(
max(
_MINIMUM_BIT_COUNT,
required_bit_count,
)
)
if candidate_bit_count > _MAXIMUM_BIT_COUNT:
continue
modeled_rate = _modeled_false_positive_rate(
candidate_bit_count,
spec.expected_item_count,
hash_count,
)
if (
not isfinite(modeled_rate)
or modeled_rate
> spec.target_false_positive_rate
):
if candidate_bit_count > _MAXIMUM_BIT_COUNT - 64:
continue
candidate_bit_count += 64
modeled_rate = _modeled_false_positive_rate(
candidate_bit_count,
spec.expected_item_count,
hash_count,
)
if (
not isfinite(modeled_rate)
or modeled_rate
> spec.target_false_positive_rate
):
continue
candidate_layout = _Layout(
bit_count=candidate_bit_count,
hash_count=hash_count,
)
if (
best_layout is None
or candidate_layout.bit_count
< best_layout.bit_count
or (
candidate_layout.bit_count
== best_layout.bit_count
and candidate_layout.hash_count
< best_layout.hash_count
)
):
best_layout = candidate_layout
if best_layout is not None:
return Success(best_layout)
return Failure(BloomError.FILTER_TOO_LARGE)
def _validate_spec(
spec: BloomSpec,
) -> BloomError | None:
if (
type(spec.expected_item_count) is not int
or not (
1
<= spec.expected_item_count
<= _MAXIMUM_EXPECTED_ITEM_COUNT
)
):
return BloomError.INVALID_EXPECTED_ITEM_COUNT
rate = spec.target_false_positive_rate
if not _is_real_number(rate):
return BloomError.INVALID_FALSE_POSITIVE_RATE
if rate <= 0.0 or rate >= 1.0:
return BloomError.INVALID_FALSE_POSITIVE_RATE
try:
rate_as_float = float(rate)
except (OverflowError, ValueError):
return BloomError.INVALID_FALSE_POSITIVE_RATE
if not isfinite(rate_as_float):
return BloomError.INVALID_FALSE_POSITIVE_RATE
return None
def _is_real_number(
value: object,
) -> bool:
return (
isinstance(value, (int, float))
and not isinstance(value, bool)
)
def _calculate_required_bit_count_for_hash_count(
item_count: int,
hash_count: int,
target_rate: float,
) -> int | None:
n = float(item_count)
k = float(hash_count)
root = target_rate ** (1.0 / k)
denominator = -log1p(-root)
required = k * n / denominator
if (
not isfinite(required)
or required > _MAXIMUM_BIT_COUNT
):
return None
return max(
_MINIMUM_BIT_COUNT,
ceil(required),
)
def _add_digest(
bits: bytearray,
layout: _Layout,
digest: bytes,
) -> None:
bit_index, step = _create_probe(
digest,
layout.bit_count,
)
for _ in range(layout.hash_count):
_set_bit(bits, bit_index)
bit_index = (
bit_index + step
) % layout.bit_count
def _create_probe(
digest: bytes,
bit_count: int,
) -> tuple[int, int]:
first = int.from_bytes(
digest[0:8],
byteorder="big",
signed=False,
)
second = int.from_bytes(
digest[8:16],
byteorder="big",
signed=False,
)
step = (second | 1) % bit_count
return first % bit_count, step
def _set_bit(
bits: bytearray,
bit_index: int,
) -> None:
byte_index = bit_index >> 3
bit_offset = bit_index & 7
bits[byte_index] |= (
1 << bit_offset
)
def _get_bit(
bits: bytes,
bit_index: int,
) -> bool:
byte_index = bit_index >> 3
bit_offset = bit_index & 7
return (
bits[byte_index]
& (1 << bit_offset)
) != 0
def _align_to_word(
value: int,
) -> int:
return (value + 63) & ~63
def _modeled_false_positive_rate(
bit_count: int,
item_count: int,
hash_count: int,
) -> float:
m = float(bit_count)
n = float(item_count)
k = float(hash_count)
return (-expm1(-k * n / m)) ** k
def _normalize_digest(
digest: object,
) -> bytes | None:
if not isinstance(
digest,
(bytes, bytearray, memoryview),
):
return None
try:
normalized = bytes(digest)
except (TypeError, ValueError):
return None
return (
normalized
if len(normalized) == _DIGEST_LENGTH
else None
)In Python the digest type alone does not tell you enough, because len() on a memoryview is not always a byte count: a view wrapping 32 uint16 elements gives len(view) == 32 while the real byte count is 64.
That is why _normalize_digest() copies to bytes() first and only then checks the length.
This boundary is worth keeping as a regression test.
from array import array
view = memoryview(array("H", [0] * 32))
result = ArtifactBloomFilter.create(
[view],
BloomSpec(
expected_item_count=1,
target_false_positive_rate=0.01,
),
)
assert result == Failure(BloomError.INVALID_DIGEST)
assert ArtifactBloomFilter.create(
[],
BloomSpec(
expected_item_count=10**1000,
target_false_positive_rate=0.01,
),
) == Failure(BloomError.INVALID_EXPECTED_ITEM_COUNT)
assert ArtifactBloomFilter.create(
[],
BloomSpec(
expected_item_count=1,
target_false_positive_rate=10**1000,
),
) == Failure(BloomError.INVALID_FALSE_POSITIVE_RATE)Even when a large Python integer is passed in, the implementation checks the range and boundary without calling float() first, so no OverflowError escapes the API. The same upper limit of elements is used as in the other implementations.
Usage:
spec = BloomSpec(
expected_item_count=1_000_000,
target_false_positive_rate=0.001,
)
filter_result = ArtifactBloomFilter.create(
artifact_digests,
spec,
)
if isinstance(filter_result, Failure):
raise ValueError(filter_result.error)
artifact_filter = filter_result.value
if not artifact_filter.might_contain(
requested_digest
):
return False
return await repository.exists_async(
requested_digest,
catalog_version,
)If a pure-Python query loop is the whole hot path, interpreter overhead can cost more than the bit checks themselves,
so for large batch lookups you have to compare a native extension, NumPy vectorization and a validated Bloom implementation that your store provides.
C#
The C# implementation keeps the finished byte[] private and never hands out a mutable view.
using System;
using System.Buffers.Binary;
using System.Collections.Generic;
using System.Numerics;
public readonly record struct BloomSpec(
int ExpectedItemCount,
double TargetFalsePositiveRate);
public enum BloomError
{
InvalidExpectedItemCount,
InvalidFalsePositiveRate,
CapacityExceeded,
FilterTooLarge,
InvalidDigest,
}
public abstract record BloomResult<T>
{
public abstract bool TryGetValue(
out T value,
out BloomError error);
}
public sealed record BloomSuccess<T>(T Value)
: BloomResult<T>
{
public override bool TryGetValue(
out T value,
out BloomError error)
{
value = this.Value;
error = default;
return true;
}
}
public sealed record BloomFailure<T>(BloomError Error)
: BloomResult<T>
{
public override bool TryGetValue(
out T value,
out BloomError error)
{
value = default!;
error = this.Error;
return false;
}
}
public sealed class ArtifactBloomFilter
{
private const int DigestLength = 32;
private const int MinimumBitCount = 64;
private const int MaximumExpectedItemCount =
1 << 30;
private const int MaximumBitCount = 1 << 30;
private const double Ln2 =
0.6931471805599453;
private readonly byte[] bits;
private readonly int bitCount;
private readonly int hashCount;
private readonly int insertedItemCount;
private ArtifactBloomFilter(
byte[] bits,
int bitCount,
int hashCount,
int insertedItemCount)
{
this.bits = bits;
this.bitCount = bitCount;
this.hashCount = hashCount;
this.insertedItemCount = insertedItemCount;
}
public static BloomResult<ArtifactBloomFilter> Create(
IReadOnlyList<byte[]> digests,
BloomSpec spec)
{
if (digests is null)
{
return Failure(
BloomError.InvalidDigest);
}
if (!CreateLayout(spec).TryGetValue(
out Layout layout,
out BloomError layoutError))
{
return Failure(layoutError);
}
return Build(
digests,
spec,
layout);
}
private static BloomResult<ArtifactBloomFilter> Build(
IReadOnlyList<byte[]> digests,
BloomSpec spec,
Layout layout)
{
if (digests.Count > spec.ExpectedItemCount)
{
return Failure(
BloomError.CapacityExceeded);
}
if (!AllDigestsAreValid(digests))
{
return Failure(
BloomError.InvalidDigest);
}
byte[] bits =
new byte[layout.BitCount / 8];
foreach (byte[] digest in digests)
{
AddDigest(
bits,
layout,
digest);
}
return new BloomSuccess<ArtifactBloomFilter>(
new ArtifactBloomFilter(
bits,
layout.BitCount,
layout.HashCount,
digests.Count));
}
public bool MightContain(
ReadOnlySpan<byte> digest)
{
if (digest.Length != DigestLength)
{
throw new ArgumentException(
"The artifact digest must be 32 bytes.",
nameof(digest));
}
Probe probe =
CreateProbe(
digest,
this.bitCount);
for (
int index = 0;
index < this.hashCount;
index += 1)
{
if (!GetBit(
this.bits,
probe.GetBitIndex()))
{
return false;
}
probe.Advance(this.bitCount);
}
return true;
}
public int GetBitCount()
{
return this.bitCount;
}
public int GetHashCount()
{
return this.hashCount;
}
public int GetInsertedItemCount()
{
return this.insertedItemCount;
}
public double EstimateFalsePositiveRate()
{
double m = this.bitCount;
double n = this.insertedItemCount;
double k = this.hashCount;
return Math.Pow(
-ExponentialMinusOne(-k * n / m),
k);
}
public double GetFillRatio()
{
long setBitCount = 0;
foreach (byte value in this.bits)
{
setBitCount +=
BitOperations.PopCount(
(uint)value);
}
return (double)setBitCount
/ this.bitCount;
}
private static BloomResult<Layout> CreateLayout(
BloomSpec spec)
{
BloomError? error =
ValidateSpec(spec);
if (error is not null)
{
return new BloomFailure<Layout>(
error.Value);
}
double ideal =
-spec.ExpectedItemCount
* Math.Log(
spec.TargetFalsePositiveRate)
/ (Ln2 * Ln2);
if (!double.IsFinite(ideal)
|| ideal > MaximumBitCount)
{
return new BloomFailure<Layout>(
BloomError.FilterTooLarge);
}
Layout? bestLayout = null;
for (int hashCount = 1;
hashCount <= 32;
hashCount += 1)
{
double requiredBitCount =
CalculateRequiredBitCountForHashCount(
spec.ExpectedItemCount,
hashCount,
spec.TargetFalsePositiveRate);
if (!double.IsFinite(requiredBitCount)
|| requiredBitCount
> MaximumBitCount)
{
continue;
}
int candidateBitCount = AlignToWord(
Math.Max(
MinimumBitCount,
checked((int)Math.Ceiling(
requiredBitCount))));
if (candidateBitCount > MaximumBitCount)
{
continue;
}
double modeledRate =
CalculateModeledFalsePositiveRate(
candidateBitCount,
spec.ExpectedItemCount,
hashCount);
if (!double.IsFinite(modeledRate)
|| modeledRate
> spec.TargetFalsePositiveRate)
{
if (candidateBitCount
> MaximumBitCount - 64)
{
continue;
}
candidateBitCount += 64;
modeledRate =
CalculateModeledFalsePositiveRate(
candidateBitCount,
spec.ExpectedItemCount,
hashCount);
}
if (double.IsFinite(modeledRate)
&& modeledRate
<= spec.TargetFalsePositiveRate)
{
Layout candidateLayout = new(
candidateBitCount,
hashCount);
if (bestLayout is null
|| candidateLayout.BitCount
< bestLayout.Value.BitCount
|| (candidateLayout.BitCount
== bestLayout.Value.BitCount
&& candidateLayout.HashCount
< bestLayout.Value.HashCount))
{
bestLayout = candidateLayout;
}
}
}
if (bestLayout is not null)
{
return new BloomSuccess<Layout>(
bestLayout.Value);
}
return new BloomFailure<Layout>(
BloomError.FilterTooLarge);
}
private static BloomError? ValidateSpec(
BloomSpec spec)
{
if (spec.ExpectedItemCount < 1
|| spec.ExpectedItemCount
> MaximumExpectedItemCount)
{
return BloomError.InvalidExpectedItemCount;
}
double rate =
spec.TargetFalsePositiveRate;
if (!double.IsFinite(rate)
|| rate <= 0.0
|| rate >= 1.0)
{
return BloomError.InvalidFalsePositiveRate;
}
return null;
}
private static double
CalculateRequiredBitCountForHashCount(
int itemCount,
int hashCount,
double targetRate)
{
double n = itemCount;
double k = hashCount;
double root =
Math.Pow(targetRate, 1.0 / k);
double denominator =
-LogOneMinus(root);
return k * n / denominator;
}
private static double
CalculateModeledFalsePositiveRate(
int bitCount,
int itemCount,
int hashCount)
{
double m = bitCount;
double n = itemCount;
double k = hashCount;
return Math.Pow(
-ExponentialMinusOne(-k * n / m),
k);
}
private static double LogOneMinus(
double value)
{
if (Math.Abs(value) >= 0.0001)
{
return Math.Log(1.0 - value);
}
double term = value;
double sum = 0.0;
for (int index = 1; index <= 8; index += 1)
{
sum -= term / index;
term *= value;
}
return sum;
}
private static double ExponentialMinusOne(
double value)
{
if (Math.Abs(value) >= 0.0001)
{
return Math.Exp(value) - 1.0;
}
double term = value;
double sum = value;
for (int index = 2; index <= 8; index += 1)
{
term *= value / index;
sum += term;
}
return sum;
}
private static void AddDigest(
byte[] bits,
Layout layout,
ReadOnlySpan<byte> digest)
{
Probe probe =
CreateProbe(
digest,
layout.BitCount);
for (
int index = 0;
index < layout.HashCount;
index += 1)
{
SetBit(
bits,
probe.GetBitIndex());
probe.Advance(
layout.BitCount);
}
}
private static Probe CreateProbe(
ReadOnlySpan<byte> digest,
int bitCount)
{
ulong first =
BinaryPrimitives
.ReadUInt64BigEndian(
digest[..8]);
ulong second =
BinaryPrimitives
.ReadUInt64BigEndian(
digest[8..16]);
return new Probe(
(int)(first % (ulong)bitCount),
(int)((second | 1UL)
% (ulong)bitCount));
}
private static void SetBit(
byte[] bits,
int bitIndex)
{
int byteIndex = bitIndex >> 3;
int bitOffset = bitIndex & 7;
bits[byteIndex] |=
(byte)(1 << bitOffset);
}
private static bool GetBit(
byte[] bits,
int bitIndex)
{
int byteIndex = bitIndex >> 3;
int bitOffset = bitIndex & 7;
return (
bits[byteIndex]
& (1 << bitOffset)
) != 0;
}
private static bool AllDigestsAreValid(
IReadOnlyList<byte[]> digests)
{
foreach (byte[]? digest in digests)
{
if (digest is null
|| digest.Length != DigestLength)
{
return false;
}
}
return true;
}
private static int AlignToWord(int value)
{
return checked(
(value + 63) & ~63);
}
private static BloomFailure<ArtifactBloomFilter>
Failure(BloomError error)
{
return new BloomFailure<ArtifactBloomFilter>(
error);
}
private readonly record struct Layout(
int BitCount,
int HashCount);
private struct Probe
{
private int bitIndex;
private readonly int step;
public Probe(
int bitIndex,
int step)
{
this.bitIndex = bitIndex;
this.step = step;
}
public int GetBitIndex()
{
return this.bitIndex;
}
public void Advance(int bitCount)
{
this.bitIndex += this.step;
if (this.bitIndex >= bitCount)
{
this.bitIndex -= bitCount;
}
}
}
}Usage:
BloomSpec spec = new(
ExpectedItemCount: 1_000_000,
TargetFalsePositiveRate: 0.001);
BloomResult<ArtifactBloomFilter> result =
ArtifactBloomFilter.Create(
artifactDigests,
spec);
if (result is
BloomFailure<ArtifactBloomFilter> failure)
{
return failure.Error;
}
ArtifactBloomFilter filter =
((BloomSuccess<ArtifactBloomFilter>)
result).Value;
if (!filter.MightContain(requestedDigest))
{
return false;
}
return await repository.ExistsAsync(
requestedDigest,
catalogVersion,
cancellationToken);The ReadOnlySpan<byte> is only borrowed for the duration of the query call, so the filter never holds the digest and never puts a span inside an async state machine: membership is computed synchronously, and repository I/O starts after that.
TypeScript
The TypeScript implementation keeps the Uint8Array bitset private and uses bigint for 64-bit seed arithmetic.
export type BloomSpec = Readonly<{
expectedItemCount: number;
targetFalsePositiveRate: number;
}>;
export type BloomError =
| "invalidExpectedItemCount"
| "invalidFalsePositiveRate"
| "capacityExceeded"
| "filterTooLarge"
| "invalidDigest";
export type Result<TValue> =
| Readonly<{
kind: "success";
value: TValue;
}>
| Readonly<{
kind: "failure";
error: BloomError;
}>;
type Layout = Readonly<{
bitCount: number;
hashCount: number;
}>;
const bloomDigestLength = 32;
const minimumBloomBitCount = 64;
const maximumBloomExpectedItemCount =
2 ** 30;
const maximumBloomBitCount =
2 ** 30;
const bloomLn2 =
0.6931471805599453;
export class ArtifactBloomFilter
{
readonly #bits: Uint8Array;
readonly #bitCount: number;
readonly #hashCount: number;
readonly #insertedItemCount: number;
private constructor(
bits: Uint8Array,
layout: Layout,
insertedItemCount: number,
)
{
this.#bits = bits;
this.#bitCount = layout.bitCount;
this.#hashCount = layout.hashCount;
this.#insertedItemCount =
insertedItemCount;
}
public static create(
digests: readonly Uint8Array[],
spec: BloomSpec,
): Result<ArtifactBloomFilter>
{
const layoutResult =
createLayout(spec);
if (layoutResult.kind === "failure") {
return layoutResult;
}
if (digests.length
> spec.expectedItemCount) {
return failure(
"capacityExceeded",
);
}
if (!digests.every(isValidDigest)) {
return failure(
"invalidDigest",
);
}
const layout = layoutResult.value;
const bits =
new Uint8Array(
layout.bitCount / 8,
);
for (const digest of digests) {
addDigest(
bits,
layout,
digest,
);
}
return success(
new ArtifactBloomFilter(
bits,
layout,
digests.length,
),
);
}
public mightContain(
digest: Uint8Array,
): boolean
{
if (!isValidDigest(digest)) {
throw new RangeError(
"The artifact digest must be 32 bytes.",
);
}
const probe =
createProbe(
digest,
this.#bitCount,
);
let bitIndex =
probe.bitIndex;
for (
let index = 0;
index < this.#hashCount;
index += 1
) {
if (!getBit(
this.#bits,
bitIndex,
)) {
return false;
}
bitIndex += probe.step;
if (bitIndex >= this.#bitCount) {
bitIndex -= this.#bitCount;
}
}
return true;
}
public getBitCount(): number
{
return this.#bitCount;
}
public getHashCount(): number
{
return this.#hashCount;
}
public getInsertedItemCount(): number
{
return this.#insertedItemCount;
}
public estimateFalsePositiveRate(): number
{
const m = this.#bitCount;
const n = this.#insertedItemCount;
const k = this.#hashCount;
return (
-Math.expm1(-k * n / m)
) ** k;
}
public getFillRatio(): number
{
let setBitCount = 0;
for (const value of this.#bits) {
setBitCount +=
popCountByte(value);
}
return setBitCount
/ this.#bitCount;
}
public serializeBits(): Uint8Array
{
return this.#bits.slice();
}
}
function createLayout(
spec: BloomSpec,
): Result<Layout>
{
const validation =
validateSpec(spec);
if (validation !== undefined) {
return failure(validation);
}
const ideal =
-spec.expectedItemCount
* Math.log(
spec.targetFalsePositiveRate,
)
/ (bloomLn2 * bloomLn2);
if (!Number.isFinite(ideal)
|| ideal > maximumBloomBitCount) {
return failure(
"filterTooLarge",
);
}
let bestLayout: Layout | undefined;
for (let hashCount = 1;
hashCount <= 32;
hashCount += 1) {
const requiredBitCount =
calculateRequiredBitCountForHashCount(
spec.expectedItemCount,
hashCount,
spec.targetFalsePositiveRate,
);
if (!Number.isFinite(requiredBitCount)
|| requiredBitCount > maximumBloomBitCount) {
continue;
}
let candidateBitCount = alignToWord(
Math.max(
minimumBloomBitCount,
Math.ceil(requiredBitCount),
),
);
if (candidateBitCount > maximumBloomBitCount) {
continue;
}
let modeledRate =
modeledFalsePositiveRate(
candidateBitCount,
spec.expectedItemCount,
hashCount,
);
if (!Number.isFinite(modeledRate)
|| modeledRate
> spec.targetFalsePositiveRate) {
if (candidateBitCount
> maximumBloomBitCount - 64) {
continue;
}
candidateBitCount += 64;
modeledRate =
modeledFalsePositiveRate(
candidateBitCount,
spec.expectedItemCount,
hashCount,
);
}
if (Number.isFinite(modeledRate)
&& modeledRate
<= spec.targetFalsePositiveRate) {
const candidateLayout = {
bitCount: candidateBitCount,
hashCount,
};
if (bestLayout === undefined
|| candidateLayout.bitCount
< bestLayout.bitCount
|| (candidateLayout.bitCount
=== bestLayout.bitCount
&& candidateLayout.hashCount
< bestLayout.hashCount)) {
bestLayout = candidateLayout;
}
}
}
if (bestLayout !== undefined) {
return success(bestLayout);
}
return failure("filterTooLarge");
}
function validateSpec(
spec: BloomSpec,
): BloomError | undefined
{
if (!Number.isSafeInteger(
spec.expectedItemCount)
|| spec.expectedItemCount < 1
|| spec.expectedItemCount
> maximumBloomExpectedItemCount) {
return "invalidExpectedItemCount";
}
const rate =
spec.targetFalsePositiveRate;
if (!Number.isFinite(rate)
|| rate <= 0
|| rate >= 1) {
return "invalidFalsePositiveRate";
}
return undefined;
}
function calculateRequiredBitCountForHashCount(
itemCount: number,
hashCount: number,
targetRate: number,
): number
{
const n = itemCount;
const k = hashCount;
const root =
Math.exp(Math.log(targetRate) / k);
const denominator =
-Math.log1p(-root);
return k * n / denominator;
}
function modeledFalsePositiveRate(
bitCount: number,
itemCount: number,
hashCount: number,
): number
{
const m = bitCount;
const n = itemCount;
const k = hashCount;
return (
-Math.expm1(-k * n / m)
) ** k;
}
function addDigest(
bits: Uint8Array,
layout: Layout,
digest: Uint8Array,
): void
{
const probe =
createProbe(
digest,
layout.bitCount,
);
let bitIndex =
probe.bitIndex;
for (
let index = 0;
index < layout.hashCount;
index += 1
) {
setBit(bits, bitIndex);
bitIndex += probe.step;
if (bitIndex >= layout.bitCount) {
bitIndex -= layout.bitCount;
}
}
}
function createProbe(
digest: Uint8Array,
bitCount: number,
): Readonly<{
bitIndex: number;
step: number;
}>
{
const first =
readU64BigEndian(
digest,
0,
);
const second =
readU64BigEndian(
digest,
8,
);
const modulus =
BigInt(bitCount);
return {
bitIndex:
Number(first % modulus),
step:
Number((second | 1n) % modulus),
};
}
function readU64BigEndian(
bytes: Uint8Array,
offset: number,
): bigint
{
let result = 0n;
for (
let index = 0;
index < 8;
index += 1
) {
result =
(result << 8n)
| BigInt(bytes[offset + index]);
}
return result;
}
function setBit(
bits: Uint8Array,
bitIndex: number,
): void
{
const byteIndex =
bitIndex >> 3;
const bitOffset =
bitIndex & 7;
bits[byteIndex] |=
1 << bitOffset;
}
function getBit(
bits: Uint8Array,
bitIndex: number,
): boolean
{
const byteIndex =
bitIndex >> 3;
const bitOffset =
bitIndex & 7;
return (
bits[byteIndex]
& (1 << bitOffset)
) !== 0;
}
function popCountByte(
value: number,
): number
{
let current = value;
let count = 0;
while (current !== 0) {
current &= current - 1;
count += 1;
}
return count;
}
function alignToWord(
value: number,
): number
{
const remainder =
value % 64;
return remainder === 0
? value
: value + 64 - remainder;
}
function isValidDigest(
digest: Uint8Array,
): boolean
{
return digest instanceof Uint8Array
&& digest.byteLength
=== bloomDigestLength;
}
function success<TValue>(
value: TValue,
): Result<TValue>
{
return {
kind: "success",
value,
};
}
function failure<TValue = never>(
error: BloomError,
): Result<TValue>
{
return {
kind: "failure",
error,
};
}A TypeScript #private field is unreachable outside the class, so constants shared by several free functions have to live at module scope rather than in a class static private field. That is where bloomDigestLength, minimumBloomBitCount, maximumBloomBitCount and bloomLn2 sit.
Call site:
const result =
ArtifactBloomFilter.create(
artifactDigests,
{
expectedItemCount: 1_000_000,
targetFalsePositiveRate: 0.001,
},
);
if (result.kind === "failure") {
throw new Error(result.error);
}
const filter = result.value;
if (!filter.mightContain(
requestedDigest,
)) {
return false;
}
return await repository.existsAsync(
requestedDigest,
catalogVersion,
signal,
);3. Call site
To trust a Bloom Filter's negative, the filter and the exact store have to point at the same catalog snapshot.
export type CatalogVersion = number;
export type ArtifactIndexSnapshot =
Readonly<{
catalogVersion: CatalogVersion;
filter: ArtifactBloomFilter;
}>;
export type ArtifactRepository =
Readonly<{
existsAtVersionAsync: (
digest: Uint8Array,
catalogVersion: CatalogVersion,
signal?: AbortSignal,
) => Promise<boolean>;
}>;
export class ArtifactExistenceService
{
readonly #snapshot: ArtifactIndexSnapshot;
readonly #repository: ArtifactRepository;
public constructor(
snapshot: ArtifactIndexSnapshot,
repository: ArtifactRepository,
)
{
this.#snapshot = snapshot;
this.#repository = repository;
}
public async existsAsync(
digest: Uint8Array,
signal?: AbortSignal,
): Promise<boolean>
{
validateArtifactDigest(digest);
if (!this.#snapshot
.filter
.mightContain(digest)) {
return false;
}
return await this.#repository
.existsAtVersionAsync(
digest,
this.#snapshot.catalogVersion,
signal,
);
}
}
function validateArtifactDigest(
digest: Uint8Array,
): void
{
if (!(digest instanceof Uint8Array)
|| digest.byteLength !== 32) {
throw new RangeError(
"Artifact digests must be 32 bytes.",
);
}
}Separation of responsibilities:
Catalog Loader
= Retrieve exact digest list from DB/object storage
= Acquire catalogVersion
= I/O and cancellation
ArtifactBloomFilter
= digest β Definitely Not | Maybe
= No external I/O
= Does not return exact existence results
ArtifactRepository
= Verify exact existence for Maybe results
= Guarantee catalogVersion consistency
ArtifactExistenceService
= Validate
β Negative precheck
β Only query exact results when needed
Snapshot Publisher
= Complete new filter
β Validate
β Atomically replace with versionSwapping the snapshot never patches the existing filter in place.
Personal note: I do say those classes are needed, but it depends on the project. I only recommend that shape because the original code was written that way. What matters for running a Bloom Filter safely is responsibility and invariants, not that you must create classes named
CatalogLoader,ArtifactRepositoryandSnapshotPublisher.
A Bloom Filter only answers
Definitely Not | Maybe; it never settles existence.On
Maybe, do an exact lookup in the authoritative source.It must be clear which
catalogVersionthe filter represents.Publish a new snapshot only once it is built and validated, and never half-patch a snapshot that queries are using.
Implement within these 4, and treat the rest as implementation choices. I am writing this in line with the 2026 mood, though a more simplified coding style may catch on around 2027 or 2028.
Personal
Reader A
β Continue using Snapshot 42 until done
Builder
β Build Snapshot 43 separately
Validation complete
β Replace `currentSnapshot` reference to 43
Reader B
β Use Snapshot 43With this structure the bitset and the catalog version cannot mix during a query.
Operational boundaries for large snapshots
2Β³β° bit is about 128 MiB, and in C# a byte[] that size lands on the Large Object Heap. So while a new snapshot is being built, peak memory has to cover the previous snapshot and its metadata as well.
In Node.js, the Uint8Array backing store is counted as ArrayBuffer memory separately from the regular V8 heap, so you must monitor both arrayBuffers in memoryUsage() and RSS together.
Personal note: this is a spot where people misunderstand a lot unless they actually measure it, which I confirmed by observation. I watched a process die with OOM while heap memory looked tiny.
If the filter sits near that cap and gets replaced often, consider a Memory-Mapped File or Python's mmap. That only reduces the cost of copying the whole bitset into the managed heap; it is not a universal zero-copy answer that also removes physical memory and page fault costs.
Snapshot propagation and Delta
With many replicas and frequent snapshot updates, downloading the full bitset every time gets expensive on the network. Then you query a Delta Filter holding only the added artifacts alongside the Base Filter, and Base and Delta must use the same key encoding and hash protocol. The version chain also has to state which Base a Delta starts from and up to which catalog version it reaches.
For example, Base 42 can only take a Delta with baseVersion=42, targetVersion=43.
Stack several Deltas and query cost and false positives grow together. A Bloom Filter cannot express deletion directly, so a deleted artifact can keep producing Maybe from an old Base.
So it suits append-heavy catalogs, and once deletions pile up you need periodic Base rebuild or compaction. It is not a default for every system; it is an extension you pull out when rebuilding and propagating a full snapshot blows the operational budget.
4. Implementation order
Where does the exact source set live?
β
Are Bloom positives confirmed with an exact lookup?
β
Which catalog version are negative results valid for?
β
Are the expected element count and target false-positive rate (FPP) specified explicitly?
β
Are the actual `bitCount` and `hashCount` recorded?
β
Do all implementations use the same digest byte order?
β
Is hash position calculation deterministic?
β
Is there no API that clears inserted bits?
β
Is exceeding the expected capacity detected?
β
Is the filter snapshot published atomically after it is complete?
β
Are bit fill ratio and observed FPP monitored?The first thing to check, before hashing, is where Bloom returns positive and where it returns negative.
Do you treat a Bloom positive as ground truth,
or do you use a Bloom negative as an optimization hint?If that meaning is inverted, the system goes wrong no matter how exact the bit operations are.
5. Common misconceptions
A positive result is not proof of existence
mightContain(key) == true
Meaning:
All required bits are 1.
What it does NOT mean:
That the key was actually inserted.A Bloom Filter is a structure that trades false positives for space savings, so you must not use a positive result to finalize business decisions such as payment history, authorization, block status, or duplicate request handling. 1
Safe usage:
Maybe
Additional I/O overhead
False Positive
1 unnecessary exact lookupDangerous usage:
Maybe
Confirmed Present
False Positive
Business Data MisclassificationDo not clear bits in a basic Bloom Filter
Different elements can share the same bit.
Position of A:
[5, 17, 40]
Position of B:
[17, 22, 61]Clearing bit 17 to delete A will cause a false negative when querying B. If deletion is required, choose a different structure such as a Counting Bloom Filter, a Cuckoo Filter, or a generational filter replacement strategy.
"No false negatives" includes snapshot completeness
Even when the filter is mathematically correct, you cannot trust a negative in these situations.
- New elements not reflected in the filter
- Different key canonicalization used
- Digest of some shards missing from the build input
- bitset serialization is corrupted
- Different hash protocol version
- Used with incorrect `catalogVersion`So the operational contract looks more like this.
Successfully inserted into the Filter,
for the same byte key,
there are no false negatives as long as no bits are deleted.Personal note: right now I am using code blocks for emphasis, but this is a point I should think about separately.
Capacity is an error budget, not a memory size
With an expected insert count of n=1,000,000, inserting two million elements raises no array bounds error; instead more bits turn to 1 and the Maybe ratio climbs.
κ³Όν¬ν κ²°κ³Ό:
μ νμ±:
μμ±μ exact lookupμΌλ‘ κ²μ¦νλ©΄ μ μ§
μ±λ₯:
μ격 μ‘°ν μλ΅λ₯ μ ν
μ΅μ’
μν:
κ±°μ λͺ¨λ μ‘°νκ° Maybe
-> filter κ°μΉ μλ©ΈSo I checked whether the creation API explicitly rejects capacity overflow.
Personal note: broken implementations have quite a few more problems than you would think.
The expected FPP formula is an approximation
The pΜ = (1 - e^(-kn/m))^k used by estimateFalsePositiveRate() is an approximation, not an exact value, and
Bose et al. showed that this classical expression gives a value smaller than the actual false-positive rate, and that the error grows larger especially when m is small.3
What the approximation assumes:
k bit positions are independent
m is sufficiently large
What this implementation violates:
double hashing with hβ + iΒ·hβ
does not sample k positions independentlyIn production this number is a capacity-planning metric, not an SLA figure, so real decisions have to rest on the observed false-positive rate. targetFalsePositiveRate is a model target set to design the layout, not an SLA for the FPP observed under a real workload. Design value and operational value split exactly there.
Design input:
targetFalsePositiveRate
β
Model validation:
modeledFalsePositiveRate <= targetFalsePositiveRate
β
Operational judgment:
observedFalsePositiveRatehashCount candidates are evaluated using a closed-form expression
This implementation constrains hashCount to 1 through 32 to bound the query hot path. Instead of rounding the continuous optimum and clamping it at both ends, it evaluates all 32 usable candidates: the required bit count comes out of a formula for each, so no long linear search appears at k=1 or k=32.
For a fixed k, the condition that keeps the model FPP at or below the target p is this.
Solving that for m gives the approximate minimum bit count.
In the actual computation, where the language allows it, use log1p(-root) instead of log(1 - root), and compute the 1 - exp(-x) in the model FPP as -expm1(-x). The point is not to lose significant digits in that subtraction when root or x is small. The C# implementation carries LogOneMinus and ExponentialMinusOne helpers for the same purpose.
The builder computes each k candidate and picks the layout with the fewest bits; on a tie it picks the smaller hash count.
for k = 1..32
β Calculate m_required(k)
β Round up to 64-bit units
β Verify modeled FPP
β Select the smallest bitCountIf rounding after the formula nudges the modeled FPP slightly over the target at a boundary, it adds 64 bits and revalidates. If all 32 candidates exceed the maximum bit count or miss the target, creation fails with FilterTooLarge. expectedItemCount also shares the 2Β³β° cap across all four implementations.
Duplicate insertions also affect capacity accounting
Inserting the same digest repeatedly leaves the bitset as it was. But record the raw input count in insertedItemCount and the FPP gets estimated from more elements than are actually unique. The options are:
- Guarantee uniqueness via DISTINCT in the DB for build inputs
- Deduplicate from a sorted digest stream
- Provide an exact unique count as metadata
- Allow duplicates and use a conservative estimateDo not try to get an exact unique count out of the Bloom Filter itself.
Key encoding is a data structure contract
This implementation takes no arbitrary strings, only 32-byte SHA-256 digests. If you do handle strings directly, you have to fix the following.
- Character encoding: UTF-8
- Unicode normalization: NFC, etc.
- Case rules
- namespace prefix
- Length framing
- protocol versionThese values can look the same in business terms and still differ byte for byte.
"Γ©"
"e" + combining acute accentWithout canonicalization before hashing, they become different elements.
The k positions produced by double hashing do not overlap with each other
With hβ + iΒ·hβ, if step shares a divisor with bitCount the walk can tread the same positions repeatedly, but in this implementation that cannot structurally happen.
step = (seed2 | 1) mod bitCount
β Always odd
bitCount = alignToWord(...)
β Always a multiple of 64
bitCount = 2^a Β· b (a β₯ 6, b is odd)
gcd(step, bitCount) is odd
β A divisor of b
Traversal period = bitCount / gcd
β At least 2^a β₯ 64
hashCount β€ 32 < 64
β All k positions are distinctFor the same reason step never becomes 0, since an odd number is not divisible by the even bitCount. The if (step == 0) step = 1; correction in the original code was an unreachable branch in all four languages; it only leaves the reader with the impression that positions can collide, so dropping it and documenting the invariant is the accurate choice.
The serialization format for the bit array must be specified explicitly
Writing each language's native integer array straight to a file leaves the following unclear.
- word endian
- word width
- bit numbering
- padding
- hash protocol version
- bitCount
- hashCount
- item countA safe header example:
Magic:
"ABF1"
Fields:
formatVersion
hashProtocolVersion
catalogVersion
bitCount
hashCount
expectedItemCount
insertedItemCount
targetFpp
payloadLength
payloadChecksumThe place this actually diverges in this example is C++.
Only C++ packs bits into uint64_t words; the other three use byte arrays. For the common rule byteIndex = index / 8 to produce the same byte stream from a word array, the words have to be serialized little-endian; emit big-endian and the bytes fall out of step with the other three. That is why serializeBits() sits on the C++ side and pins the byte order in code.
Swapping the filter for an empty filter when the checksum fails makes every element negative, which is dangerous.
What I learned from experience: at that point, drop the filter and fall back to an exact lookup.
Lock-free queries on a mutable filter are not automatically safe
A bit set only ever goes 0 β 1, so a single machine word can take an atomic OR. Still, several threads mutating non-atomic bytes or words at once produce data races or lost bit updates, and this implementation took the non-atomic route.
Build:
Single owner
Publish:
Completed immutable filter
Query:
Read-only, shared across multiple threadsFor an online filter that keeps taking inserts, design the per-language atomic word operations and snapshot serialization consistency separately.
A Bloom Filter cannot enumerate its elements
From the bitset alone you cannot recover the following.
- Which artifacts are contained
- Which hash function set a specific bit
- The exact number of unique elements
- Insertion timestamp per elementThe original catalog has to exist separately.
Can an attacker directly choose the digest?
This design rests on SHA-256 artifact digests arriving from a trusted content-hash pipeline. If an external user can choose arbitrary 32-byte values and probe the filter's structure repeatedly, you have to weigh whether they could find inputs aimed at a specific bit pattern. If so, use the following.
- Keyed hash using server secret seed
- Per-tenant namespace
- Request rate limiting
- Filter query results kept privateFor very small sets, a Set is the better choice
A Bloom Filter is worth using when all of the following hold.
- The number of elements is sufficiently large
- Memory for storing exact keys is a burden
- The ratio of negative lookups is high
- The cost of positive exact lookups is high
- A certain false-positive rate is acceptableWith only a few hundred elements a hash set is simpler and exact, and it enumerates and deletes too. The production failure modes:
Returning Maybe as a definitive positive
Clearing bits to 0 when deleting an element
Applying negative results to a repository newer than the filter
Not observing when capacity is exceeded
Using different string encodings across languages
Storing only a raw bitset without a serialization header
Replacing a corrupted filter with an empty filter
Sharing a mutable bitset non-atomically
Mistaking duplicate inputs for unique elements
Finalizing authorization, payment, or security decisions based solely on a Bloom positive
Returning a negative when a digest of incorrect length is queried6. Incorrect Example
export class ArtifactServiceBad
{
readonly #filter: MutableBloomFilter;
readonly #repository: ArtifactRepository;
public constructor(
filter: MutableBloomFilter,
repository: ArtifactRepository,
)
{
this.#filter = filter;
this.#repository = repository;
}
public async existsAsync(
digest: Uint8Array,
): Promise<boolean>
{
// Using Maybe as an exact existence result incorrectly.
return this.#filter.mightContain(
digest,
);
}
public async deleteAsync(
digest: Uint8Array,
): Promise<void>
{
await this.#repository.deleteAsync(
digest,
);
// Clearing a shared bit introduces a false negative for another element.
this.#filter.clearBitsFor(
digest,
);
}
}Problem 1:
Artifact X was never inserted
but all bits for X are
already 1 due to other artifacts
mightContain(X)
β true
Service result:
incorrectly returns "exists"Problem 2:
A and B share bit 17
Delete A
β bit 17 removed
Query B
β bit 17 is 0
β false negativeThe third problem is that there is no snapshot version.
The repository gets updated while the filter is still stale, and the caller cannot tell.
Personal note: a version chain can block that, but in my view the complexity of a snapshot version chain is too high.
A Bloom Filter is essentially a "negative cache" layer in front of the main database. Keeping version vectors or chains to guarantee consistency between the cache layer and the persistence layer usually costs more than it solves. Still, skip the synchronization mechanism entirely and you cannot tune the filter's False Positive ratio, which leaves an untrustworthy cache.
The core problem with the flawed example is, in fact, that it demands explicit deletion via
deleteAsync. A standard Bloom Filter does not support deletion, so putting a data structure that cannot delete elements into a domain where deletions occur inevitably causes problems.I respect what the original C++ author was thinking, but this is my view.
Correct Principles:
Negative:
Exact lookup can be skipped
Maybe:
Exact lookup required
Delete:
Base Bloom Filter is not modified
β Rebuild new snapshot7. Production Scaling
Model-based Correctness and Probabilistic Verification
Bloom Filter tests have to separate exact invariants from probabilistic quality.
Precise Invariants:
All inserted digests
β MightContain == true
Invalid digest length in build input
β InvalidDigest failure
Invalid digest length in lookup input
β Exception
Same input and spec
β Same result
Capacity exceeded
β Explicit failure
Common expected item count upper bound exceeded
β InvalidExpectedItemCount failure
Target FPP not satisfied even at maximum bitCount
β FilterTooLarge failureProbabilistic Quality:
For a sufficient sample of elements that were not inserted
Is the observed FPP within the target range?TypeScript Tests:
import assert from "node:assert/strict";
import {
createHash,
} from "node:crypto";
import test from "node:test";
test(
"No false negatives exist for inserted digests",
() =>
{
const members =
createDigests(
"member",
10_000,
);
const result =
ArtifactBloomFilter.create(
members,
{
expectedItemCount: 10_000,
targetFalsePositiveRate: 0.01,
},
);
if (result.kind === "failure") {
assert.fail(result.error);
}
for (const digest of members) {
assert.equal(
result.value.mightContain(
digest,
),
true,
);
}
});
test(
"The observed false-positive rate falls within the statistically acceptable range",
() =>
{
const itemCount = 20_000;
const probeCount = 200_000;
const targetRate = 0.01;
const result =
ArtifactBloomFilter.create(
createDigests(
"member",
itemCount,
),
{
expectedItemCount: itemCount,
targetFalsePositiveRate:
targetRate,
},
);
if (result.kind === "failure") {
assert.fail(result.error);
}
let falsePositiveCount = 0;
for (
let index = 0;
index < probeCount;
index += 1
) {
const digest =
createDigest(
`non-member:${index}`,
);
if (result.value.mightContain(
digest,
)) {
falsePositiveCount += 1;
}
}
const observedRate =
falsePositiveCount / probeCount;
const modelRate =
result.value
.estimateFalsePositiveRate();
const standardDeviation =
Math.sqrt(
modelRate
* (1 - modelRate)
/ probeCount,
);
const upperBound =
modelRate
+ 5 * standardDeviation;
assert.ok(
observedRate <= upperBound,
`The observed FPP ${observedRate}`
+ `exceeds the allowed upper bound ${upperBound}.`,
);
});
test(
"Digests of incorrect length are rejected at query time",
() =>
{
const result =
ArtifactBloomFilter.create(
createDigests(
"member",
16,
),
{
expectedItemCount: 100,
targetFalsePositiveRate: 0.01,
},
);
if (result.kind === "failure") {
assert.fail(result.error);
}
assert.throws(
() =>
result.value.mightContain(
new Uint8Array(16),
),
RangeError,
);
});
test(
"Exceeding the designed capacity is rejected",
() =>
{
const result =
ArtifactBloomFilter.create(
createDigests(
"member",
101,
),
{
expectedItemCount: 100,
targetFalsePositiveRate: 0.01,
},
);
assert.deepEqual(result, {
kind: "failure",
error: "capacityExceeded",
});
});
test(
"The modeled FPP budget is maintained across all `hashCount` candidates",
() =>
{
const expectedItemCount =
1_000_000;
const targetModeledRate = 1e-20;
const result =
ArtifactBloomFilter.create(
[],
{
expectedItemCount,
targetFalsePositiveRate:
targetModeledRate,
},
);
if (result.kind === "failure") {
assert.fail(result.error);
}
assert.equal(
result.value.getHashCount(),
32,
);
const m = result.value.getBitCount();
const k = result.value.getHashCount();
const modeledRate =
(-Math.expm1(-k * expectedItemCount / m))
** k;
assert.ok(modeledRate <= targetModeledRate);
});
test(
"The lower `hashCount` boundary is also computed via candidate evaluation",
() =>
{
const expectedItemCount =
1_000_000;
const targetModeledRate = 0.95;
const result =
ArtifactBloomFilter.create(
[],
{
expectedItemCount,
targetFalsePositiveRate:
targetModeledRate,
},
);
if (result.kind === "failure") {
assert.fail(result.error);
}
assert.equal(
result.value.getHashCount(),
1,
);
assert.equal(
result.value.getBitCount(),
333_824,
);
const modeledRate =
(-Math.expm1(
-expectedItemCount
/ result.value.getBitCount(),
));
assert.ok(modeledRate <= targetModeledRate);
});
function createDigests(
prefix: string,
count: number,
): readonly Uint8Array[]
{
return Array.from(
{ length: count },
(_, index) =>
createDigest(
`${prefix}:${index}`,
),
);
}
function createDigest(
value: string,
): Uint8Array
{
return createHash("sha256")
.update(value, "utf8")
.digest();
}When inspecting the build result, do not return out of the failure branch: that lets the test pass even when no filter was built.
assert.fail returns never, which both settles the failure and narrows result to the success side for the code that follows. Inputs and the random source are fixed, so this is not a flaky test that moves between runs. Demanding that a finite sample hit the target FPP exactly is statistically unsound, though, and it makes a brittle check that breaks when the implementation shifts even slightly.
State the sample size and the statistical tolerance. Compute the tolerance from the model FPP of the actual layout plus sampling error, not straight from the target FPP. With n = 20,000 and p = 0.01 it evaluates candidates k=1..32 and picks the layout with the smallest bitCount; the test then sets its upper bound from that layout's model FPP and looks in one direction only. A broken filter that always returns negative still passes an upper-bound check on its own, which is what the first test catches.
Operational Metrics
artifact_bloom.bit_count
artifact_bloom.hash_count
artifact_bloom.expected_item_count
artifact_bloom.inserted_item_count
artifact_bloom.fill_ratio
artifact_bloom.estimated_fpp
artifact_bloom.negative.count
artifact_bloom.maybe.count
artifact_bloom.false_positive.count
artifact_bloom.catalog_version
artifact_bloom.snapshot.age_seconds
artifact_bloom.snapshot.load_failure.countReal false positives are measured under a condition like this.
Bloom:
Maybe
Exact Repository:
Absent
1 False PositiveUseful Ratios:
negativeBypassRatio
=
Negative / Total Queries
observedFalsePositiveRate
=
False Positives
/ (Negative Prechecks + False Positives)
falseDiscoveryRatio
=
False Positives
/ Maybe ResultsobservedFalsePositiveRate is the share of absence requests where Bloom wrongly returned positive. falseDiscoveryRatio is the share of queries sent on as Maybe that were absent after all. The first shows Bloom's classification quality, the second the share of Maybe results that wasted an exact lookup, so they must not be merged into one metric. If the bit fill ratio climbs faster than expected, suspect capacity overflow, an unexpected inflow of non-duplicate inputs, or a bad hash distribution.
8. Comparison Notes: C++ / Python / C# / TypeScript
Language | Bit Storage | 64-bit Seed | Key Risks |
|---|---|---|---|
C++ |
|
| view lifetime, serialization endianness |
Python | immutable | arbitrary precision | interpreter loop and object overhead |
C# | private |
| array alias, LOH, snapshot copy |
TypeScript | private |
| bitwise 32-bit conversion, runtime differences |
- Language
C++
- Bit Storage
vector<uint64_t>- 64-bit Seed
uint64_t- Key Risks
view lifetime, serialization endianness
- Language
Python
- Bit Storage
immutable
bytes- 64-bit Seed
arbitrary precision
int- Key Risks
interpreter loop and object overhead
- Language
C#
- Bit Storage
private
byte[]- 64-bit Seed
ulong- Key Risks
array alias, LOH, snapshot copy
- Language
TypeScript
- Bit Storage
private
Uint8Array- 64-bit Seed
bigint- Key Risks
bitwise 32-bit conversion, runtime differences
C++
vector<uint64_t> packs 64 bits into one word, so it is compact and queries allocate nothing. To grow into a mutable concurrent filter, an std::atomic<uint64_t> word array is the candidate, but you must not assume it can be serialized or copied the way a plain vector<uint64_t> can; an immutable snapshot is far simpler. Because no span or string_view lives inside the filter, the lifetime of build inputs is separate from the filter's. The word array is good for performance and a burden for cross-language compatibility: the other three use byte arrays, so C++ alone needs a separate rule for flattening words into bytes.
serializeBits() forces little-endian, turning that rule into code.
Python
bytes suits an immutable snapshot, and a byte-level bitset is far denser than a list holding one Python integer object per element. The cost is that one query runs the Python loop k times, so if you need millions of queries per second, look at a C extension, a Rust/C++ extension, NumPy batch queries, or an external probabilistic index. Python's arbitrary-precision integers remove 64-bit overflow, but at external input boundaries you still apply the same element cap and 32-byte digest normalization as the other implementations, and byte order and modulo rules have to match them too.
C#
byte[] is compact but a reference type: take or return an outside alias and snapshot immutability is gone. This implementation allocates its own array during construction and never exposes it. Large filters land on the Large Object Heap, and frequent snapshot rebuilds nearly double memory while readers still hold the previous filter, so judge deployability by peak memory. ReadOnlySpan<byte> fits query input but cannot cross an async boundary, so finishing membership synchronously and then starting I/O is the natural split.
TypeScript
JavaScript's ordinary bitwise operations convert to signed 32-bit, and reading a 64-bit seed as a number throws away precision, so bigint it is. Bit count is capped at 2Β³β° so bit indices stay plain numbers. That cap is not a TypeScript-only matter: C# indexes arrays with int and alignToWord() adds up to 63, so an upper bound of 2Β³ΒΉ could overflow the signed 32-bit range during alignment, which is why all four implementations use 2Β³β°. Readonly<Uint8Array> does not remove other aliases of the backing storage; add a constructor that takes an external bitset and you have to copy it or transfer ownership explicitly.
Common Contract
What has to match across the four languages is not the class shape.
Digest:
Exactly 32 bytes
Seed 1:
digest[0..8] unsigned big-endian
Seed 2:
digest[8..16] unsigned big-endian
β Set the lowest bit to 1
Initial index:
seed1 mod bitCount
Step:
(seed2 | 1) mod bitCount
Next index:
(index + step) mod bitCount
Hash count candidates:
Evaluate all k = 1..32
bitCount candidate:
Compute m_required(k) = -kn / ln(1 - targetFpp^(1/k))
Then round up to a multiple of 64
Selection rule:
Choose the smallest bitCount
If bitCount is tied, choose the smallest k
Always verify final modeledFpp <= targetFpp
FPP layers:
targetFpp is the builder's design goal
modeledFpp is the approximation verified at build time
observedFpp is the value measured in operation
Expected item count:
Between 1 and 2Β³β°
Bit numbering:
byteIndex = index / 8
bitOffset = index % 8
LSB-first
Serialization of word array implementation:
Expand words into little-endian bytes
bitCount:
Rounded to a multiple of 64 by alignToWord
Upper bound 2Β³β°To serialize a filter across languages or share golden vectors, you have to pin this protocol down in writing.
In particular, a reader must not recompute the layout from targetFpp; it uses the header's bitCount and hashCount as the wire contract. targetFpp is metadata describing what the builder aimed for, not a value that decides the layout of an already published snapshot. Running all four implementations on the same input and comparing the bit arrays byte by byte is how you confirm the contract actually holds. Fix the input at 1,000 SHA-256 digests (member:0 through member:999) with expectedItemCount: 2000 and targetFalsePositiveRate: 0.01.
All four implementations must produce bitCount = 19200, hashCount = 7, set bit count 5858 and fill ratio 0.3051041666666667. The SHA-256 of the 2,400-byte bitset serialized LSB-first is 82a3be1c19b8d8576778c2d536b288f2b26fd50f4b1f42e932f276a15cd78fb6. Only C++ matches when it is flattened little-endian; big-endian diverges. Putting this input rule and checksum in CI is what "pinned down in writing" actually looks like.
9. Further Considerations
When the catalog keeps growing, do you rebuild the fixed filter, or query a base filter and a delta filter together?
Between lowering the target FPP to buy memory and the remote I/O cost that false positives create, which is actually cheaper for you?
During a snapshot swap, can the repository serve exact lookups for the old version while earlier readers still use it?
When the digest is already SHA-256, which threat model fits: using two 64-bit slices, or applying a separate keyed hash?
If deletions are frequent, which is simpler: a counting Bloom Filter, a Cuckoo Filter, or a periodic full rebuild?
When the filter is corrupted or the version does not match, do you fail the service, or disable the Bloom optimization and fall back to exact lookups for every request?
For a length violation on lookup input, exceptions or Result: which makes the call site more honest?
Should the other three languages pay the cost C++ pays, wrapping the digest in a value type so a length violation cannot be represented?
10. Summary
A Bloom negative means absence; a positive only means presence is possible.
Do not stop at a positive: confirm it with an exact lookup in the source store.
Design the bit count and hash count from the expected element count and the target false-positive rate.
Evaluate the required bit count in closed form for each
hashCountcandidate from 1 to 32, pick the smallest layout, then verify the final modeled FPP is at or below target; if even the maximum size misses, fail withFilterTooLarge.Clearing a bit in a basic Bloom Filter causes false negatives through shared bits.
"No false negatives" holds mathematically only when the filter is complete, current, and the hash protocol is the same.
Publish it as an immutable versioned snapshot, and measure fill ratio and observed false-positive rate in production.
targetFppandmodeledFppare design and build values; useobservedFppfor real SLA decisions.In a design that trusts only negatives, a format violation on lookup input must not come back as a negative: creation rejects it with a Result and lookup aborts with an exception.
Python's
memoryviewcan differ in element count and byte count: normalize the digest tobytes, check the length after that, and reject large integer input explicitly at the common boundary.To avoid language-specific
rounddiscrepancies, evaluatehashCountcandidates directly; on the reader side, trust thebitCountandhashCountin the header rather than the target FPP.Getting the bit array's byte representation into the contract is what makes cross-language filter sharing work.
All of the above is long and academic, but there is no need to memorize it. The dumbest thing in the world is reimplementing what others have already built well; this is just my hobby, which is the only reason I am writing these notes.
A Bloom Filter is essentially a negative-cache-only metadata layer sitting in front of the main database. Put differently, it is the checkpoint that decides whether a piece of data is even worth a DB query.
Anyone with no passport at all (data that does not exist) is refused entry, which perfectly blocks the pointless final review (DB I/O).
Holding a passport does not prove it is genuine (False Positive), and the checkpoint cannot be sure. Send only those who pass to the final desk (DB) for verification, and that is good enough in practice.
Do not use a Bloom Filter as an answer table.
If the result is negative, skip the expensive lookup;
if positive, verify against the authoritative store.
The error you accept in exchange for space savings
must cost nothing more than an extra lookup.Footnotes
- Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM 13(7), 1970. The original paper demonstrating how space and lookup time can be reduced at the cost of allowable errors. β©
- Adam Kirsch, Michael Mitzenmacher. Less hashing, same performance: Building a better Bloom filter. Random Structures & Algorithms 33(2), 2008. A paper showing that generating k positions via a linear combination of two hash functions preserves asymptotic false-positive performance. β©
- Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, Michiel Smid, Yihui Tang. On the false-positive rate of Bloom filters. Information Processing Letters, 2008. A paper demonstrating that the classical approximation underestimates the actual false-positive rate. Author preprint β©