Blocked Bloom filters: localize probes and watch skew

Last updated: 5 Oct 20269 min read

tutorial

A blocked Bloom filter first maps an incident ID to one block, then sets several positions within that block. Lookup reads the same block and checks the positions. This arrangement keeps a key's probes together rather than scattering them across the whole filter. It is a layout tradeoff, not a proof that every implementation wins on a real CPU. The Python program stores each block as an integer bit mask. Blocks receiving more keys fill sooner and can produce more false positives than quieter blocks, even when overall occupancy looks moderate. The hash convention must stay fixed across writes and queries. As in a standard Bloom filter, positives need verification, and clearing a selected bit to delete one key would risk hiding another.

Operational case

A dispatcher has sixteen independent bit blocks, each with sixty-four positions. Pump-47, valve-19, and sensor-61 are inserted. A pump query hashes to one block and tests four local bit positions. If many incident IDs land in that same block, its bit mask can saturate while another block stays sparse. A global percentage of set bits would conceal that hot block. Record per-block occupancy before trusting a chosen block count. The output prints membership for a known insertion and the number of blocks; it does not claim a measured cache miss rate or a universal false-positive probability.

Working Python program

import hashlib


class BlockedIncidentFilter:
    def __init__(self, block_count=16, bits_per_block=64, hash_count=4):
        if block_count < 1 or bits_per_block < 1 or hash_count < 1:
            raise ValueError("block, bit, and hash counts must be positive")
        self.blocks = [0] * block_count
        self.bits_per_block = bits_per_block
        self.hash_count = hash_count

    def _location(self, incident_id):
        encoded = incident_id.encode("utf-8")
        block_digest = hashlib.blake2b(encoded, digest_size=8).digest()
        block_number = int.from_bytes(block_digest, "big") % len(self.blocks)
        bit_numbers = []
        for hash_number in range(self.hash_count):
            digest = hashlib.blake2b(
                encoded + hash_number.to_bytes(4, "big"), digest_size=8
            ).digest()
            bit_numbers.append(int.from_bytes(digest, "big") % self.bits_per_block)
        return block_number, bit_numbers

    def add(self, incident_id):
        block_number, bit_numbers = self._location(incident_id)
        for bit_number in bit_numbers:
            self.blocks[block_number] |= 1 << bit_number

    def might_contain(self, incident_id):
        block_number, bit_numbers = self._location(incident_id)
        return all(self.blocks[block_number] & (1 << bit_number)
                   for bit_number in bit_numbers)


filter_index = BlockedIncidentFilter()
for incident_id in ("pump-47", "valve-19", "sensor-61"):
    filter_index.add(incident_id)
print("pump=", filter_index.might_contain("pump-47"),
      "blocks=", len(filter_index.blocks), sep="")

Output

pump=Trueblocks=16

Time, space, and tradeoff

With H in-block hash probes, insertion and lookup use O(H) bit operations and hash work proportional to the encoded key length. The conceptual bit storage is O(BW) for B blocks of W bits; Python integer and list overhead make process memory larger. All probes concern one block, but this code uses separate hash calls and does not simulate hardware cache lines. Choosing a small W or concentrating keys in one block can raise false positives. There is no deletion, count estimate, or strict capacity; after enough insertions a saturated block always answers positive for its mapped keys.

Common Mistakes

Do not infer uniform per-block load from total filter occupancy.
Do not claim Python integer blocks are physical cache-line measurements.
Do not clear a shared bit to remove one incident.
Do not treat a positive answer as proof of an existing incident.

Connected lessons

Compare its mutation contract with Counting Bloom filters: delete only a known insertion, Scalable Bloom filters: grow without discarding old members, Cuckoo filters: relocate compact fingerprints safely, then run the membership audit and contract quiz.

data structures

range-query-structures