Deduplicating Barcode Scans with Bloom Filters

A pure-Python Bloom filter for high-throughput barcode-scan deduplication: false-positive math, bounded memory, and a mandatory exact fall-through

At a busy dispensing counter the scan stream can burst to thousands of events a second, and the deduplication layer must answer “have I seen this key before?” for every one of them without letting memory grow without bound. Holding every seen key in a set is correct but linear in memory: a week of high-volume dispensing is millions of keys, and the working set outgrows a single worker. A Bloom filter answers the membership question in constant memory regardless of how many keys have passed through — which makes it the ideal pre-filter in front of an authoritative exact store. The trade is that it can occasionally say “possibly seen” for a key it has never observed. In a controlled-substance system that asymmetry is not a footnote; it is the whole safety argument, because a filter that could be trusted to drop a scan would occasionally drop a real dispense. This recipe builds the filter and, just as importantly, wires it so a “possibly seen” answer can never by itself suppress a controlled event. It implements the probabilistic pre-filter described in the parent reference, Real-Time Barcode-Scan Deduplication.

The design goal is precise: use the filter to make the common case — a brand-new key — cheap, by skipping the network round-trip to the exact store whenever the filter says “definitely never seen.” Only the rarer “possibly seen” answer pays for an exact lookup, and only the exact store may ever declare a duplicate.

A Bloom filter setting and testing k bits for one scan key A scan key is fed through three independent hash functions, each reduced modulo the bit-array length m to an index. On add, those three bits are set in a fixed-size bit vector. On test, all three bits are read: if every bit is set the key is possibly seen and must fall through to an exact check, while if any bit is clear the key is definitely new and can be fast-pathed. The bit vector stays a constant size no matter how many keys are inserted. Scan key sha256 digest h1 mod m h2 mod m h3 mod m bit vector (size m, constant) all k bits set ⇒ possibly seen → exact check any bit clear ⇒ definitely new → fast-path

Problem framing

The deduplication gate needs to know, for each incoming scan key, whether it is worth paying for an authoritative exact lookup. The overwhelming majority of keys in a healthy stream are genuinely new, and for those a network round-trip to the shared exact store is wasted work. A Bloom filter turns that majority into a local, constant-time, constant-memory “definitely never seen” answer. The one thing it must never do is the inverse: it must never let its “possibly seen” answer be the reason a Schedule II dispense is dropped, because that answer is sometimes wrong in the direction that loses a real event.

Two properties of the filter make this safe when respected:

  • No false negatives. If a key was ever added, the filter always reports “possibly seen.” A genuine duplicate can never slip past the pre-filter and skip the exact check.
  • Bounded false positives. A key that was never added can be reported “possibly seen” with a probability set by the filter’s sizing. This costs an unnecessary exact lookup — never a dropped scan — provided the fall-through rule is honored.

Prerequisites & environment

  • Python 3.11+ — the implementation uses dataclass(frozen=True) and modern typing.
  • Standard library only. Bits are stored in a bytearray and manipulated with pure-Python bit operations; there is no bitarray or third-party dependency. Hashing uses hashlib; add pytest only for the test block.
  • The false-positive-rate identities. For a bit array of m bits, k hash functions, and n inserted keys, the false-positive probability is p ≈ (1 - e^(-kn/m))^k. The optimal hash count is k = (m/n) · ln 2, and to hit a target p for an expected n you size m = -n · ln p / (ln 2)^2. These are the only formulas you need to pick parameters deliberately rather than by feel.
  • Regulatory context. The exactly-once accounting standard of 21 CFR § 1304.21 and the perpetual-inventory standard of 21 CFR § 1304.11 are why a bloom-only “seen” must never drop a controlled-substance scan. The filter is an optimization around the exact guarantee, never a replacement for it.

Implementation: a rotating pure-Python Bloom filter

The filter derives k indices from a single SHA-256 digest using double hashing (the Kirsch–Mitzenmacher technique): two independent 64-bit values pulled from the digest generate all k indices as (h1 + i·h2) mod m, which is statistically indistinguishable from k independent hashes without paying for k separate digests. A rotating wrapper holds two generations so the structure can shed old keys and never saturate — when the active generation reaches its design capacity it is retired behind a fresh one, and queries consult both.

python
from __future__ import annotations

import hashlib
import json
import logging
import math
from dataclasses import dataclass

logger = logging.getLogger("pharmacy.scan.bloom")


def optimal_params(expected_n: int, target_fp: float) -> tuple[int, int]:
    """Return (m_bits, k_hashes) that meet target_fp for expected_n keys.
    m = -n ln p / (ln 2)^2 ;  k = (m/n) ln 2."""
    if expected_n <= 0 or not (0.0 < target_fp < 1.0):
        raise ValueError("expected_n must be > 0 and 0 < target_fp < 1")
    m = math.ceil(-expected_n * math.log(target_fp) / (math.log(2) ** 2))
    k = max(1, round((m / expected_n) * math.log(2)))
    return m, k


class BloomFilter:
    """Fixed-size Bloom filter over a bytearray. No false negatives; the
    false-positive rate is bounded by (m, k) and the number of inserts."""

    def __init__(self, m_bits: int, k_hashes: int) -> None:
        self.m = m_bits
        self.k = k_hashes
        self._bits = bytearray((m_bits + 7) // 8)
        self._count = 0

    def _indices(self, key: str) -> list[int]:
        digest = hashlib.sha256(key.encode("utf-8")).digest()
        h1 = int.from_bytes(digest[:8], "big")
        h2 = int.from_bytes(digest[8:16], "big") | 1   # odd => good stride
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, key: str) -> None:
        for idx in self._indices(key):
            self._bits[idx >> 3] |= (1 << (idx & 7))
        self._count += 1

    def __contains__(self, key: str) -> bool:
        return all(
            self._bits[idx >> 3] & (1 << (idx & 7))
            for idx in self._indices(key)
        )

    @property
    def fill_ratio(self) -> float:
        set_bits = sum(bin(b).count("1") for b in self._bits)
        return set_bits / self.m

    @property
    def count(self) -> int:
        return self._count


@dataclass
class RotatingBloom:
    """Two-generation Bloom filter. When the active generation reaches its
    design capacity it is retired behind a fresh one, bounding saturation and
    letting keys age out with the deduplication window."""

    expected_n: int
    target_fp: float

    def __post_init__(self) -> None:
        self._m, self._k = optimal_params(self.expected_n, self.target_fp)
        self._active = BloomFilter(self._m, self._k)
        self._retiring: BloomFilter | None = None

    def probably_seen(self, key: str) -> bool:
        if key in self._active:
            return True
        return self._retiring is not None and key in self._retiring

    def add(self, key: str) -> None:
        if self._active.count >= self.expected_n:
            self._retiring = self._active            # keep one generation of history
            self._active = BloomFilter(self._m, self._k)
        self._active.add(key)

    def observe(self, key: str) -> bool:
        """Pre-filter verdict for the dedup gate. Returns True for
        'possibly seen' (caller MUST fall through to the exact store) and
        False for 'definitely new' (caller may fast-path)."""
        verdict = self.probably_seen(key)
        logger.info(json.dumps({
            "event": "bloom_prefilter",
            "verdict": "probably_seen" if verdict else "definitely_new",
            "fp_budget": self.target_fp,
            "fill_ratio": round(self._active.fill_ratio, 4),
        }, sort_keys=True))
        if not verdict:
            self.add(key)          # record the new key for next time
        return verdict

The observe method is the single call the deduplication gate makes. Its contract is deliberately narrow: True means “possibly seen — you must consult the exact store,” and False means “definitely new — you may skip the exact store and commit.” It never returns a verdict that suppresses on its own authority. Adding the key on a definitely_new verdict is what makes the next retransmission of the same key report probably_seen and route to the exact check where it will be caught.

Verification & testing

Two properties must hold: the filter never produces a false negative (a real duplicate can never escape the pre-filter), and its false-positive rate stays within the configured budget across a realistic load. The block below proves both empirically.

python
import pytest


def test_no_false_negatives():
    # Every key that was added MUST report probably_seen. This is the safety
    # property that guarantees no genuine duplicate skips the exact check.
    bf = RotatingBloom(expected_n=10_000, target_fp=0.01)
    keys = [f"scan-key-{i}" for i in range(10_000)]
    for key in keys:
        bf.add(key)
    assert all(bf.probably_seen(k) for k in keys)


def test_false_positive_rate_within_budget():
    # Query keys that were never inserted; the observed FP rate must stay
    # near the configured target (with generous slack for sampling noise).
    n, target = 20_000, 0.01
    bf = RotatingBloom(expected_n=n, target_fp=target)
    for i in range(n):
        bf.add(f"present-{i}")
    trials = 50_000
    fp = sum(bf.probably_seen(f"absent-{j}") for j in range(trials))
    observed = fp / trials
    assert observed <= target * 2.0, f"FP rate {observed:.4f} exceeds budget"


def test_optimal_params_hit_target():
    m, k = optimal_params(expected_n=10_000, target_fp=0.001)
    assert k >= 1 and m > 0
    # Analytic FP at capacity must not exceed the target we asked for.
    analytic = (1 - math.exp(-k * 10_000 / m)) ** k
    assert analytic <= 0.001 * 1.2

Capturing the emitted pre-filter line confirms the audit trail carries only the verdict and sizing telemetry — never the raw scan payload or any operator identity:

text
INFO pharmacy.scan.bloom {"event": "bloom_prefilter", "fill_ratio": 0.4213, \
     "fp_budget": 0.01, "verdict": "definitely_new"}

The key never appears in clear text in the filter’s logs: the gate hashes it to a SHA-256 digest before the filter ever sees it, so the pre-filter telemetry stays inside the HIPAA audit-control boundary of 45 CFR § 164.312(b).

Gotchas & compliance pitfalls

  • Never drop a controlled-substance scan on a bloom-only hit. This is the cardinal rule. A “possibly seen” verdict is sometimes wrong, so treating it as a duplicate would occasionally suppress a real dispense — an under-count that surfaces as a reportable Schedule II shortage. Always fall through to the exact store, which is the only authority allowed to suppress. The atomic exact claim that backs the fall-through is built in Idempotent Scan Ingestion with Redis SETNX.
  • Filter saturation degrades the rate, silently. Insert far more than expected_n keys and the fill ratio climbs, driving the false-positive rate well above the budget until nearly everything reads “possibly seen.” That is safe — it only costs extra exact lookups — but it erodes the fast path. The rotating wrapper bounds it by retiring a generation at capacity; monitor fill_ratio and alarm before it approaches the design point.
  • A standard filter cannot delete a key. Clearing one key’s bits would clear bits shared with other keys and create false negatives. Never unset bits in place. When keys must age out with the deduplication window, rotate a whole generation (as here) or use a counting Bloom filter that tracks per-bit counters — but never mutate a shared bit to remove a single member.
  • Hash quality matters. Deriving all k indices from a single well-distributed digest via double hashing is sound; deriving them from a weak or truncated hash clusters the set bits and inflates the real false-positive rate above the analytic one. Keep the full SHA-256 digest as the source of both h1 and h2.
  • Sizing to the wrong n. The false-positive math holds only near the design capacity. Size m and k from the peak number of distinct keys you expect within one filter generation, not the average, or the live rate will exceed the budget under load.

Frequently Asked Questions

If the filter can be wrong, why use it at all?

Because it is only ever wrong in the safe direction when wired correctly. A false “possibly seen” costs one extra exact lookup; it never drops a scan. In exchange, every genuinely new key — the common case — is resolved locally in constant time and memory, skipping the network round-trip to the exact store. The filter buys throughput and bounded memory without touching the correctness guarantee, which stays entirely with the exact store.

Counting Bloom filter or rotating generations for aging keys out?

Both work; they trade memory for granularity. A counting Bloom filter stores a small counter per bucket instead of a single bit, which lets you delete individual keys at several times the memory cost. Rotating two standard generations, as shown here, ages keys out in coarse blocks at minimal memory. For scan deduplication, where keys naturally expire with the time window, rotation is simpler and cheaper — you never need to delete one specific key, only to forget everything older than the window.

How do I choose the target false-positive rate?

Trade throughput against exact-store load. A smaller target p means a larger bit array and more hashes, so more memory and slightly more CPU per query, but fewer unnecessary exact lookups. A rate around one percent is a common starting point: it keeps the filter compact while sending only one in a hundred genuinely-new keys on an unnecessary round-trip. Because a false positive never costs correctness, you can tune p purely on the throughput-versus-memory curve.

Does the Bloom filter ever touch protected health information?

No. The deduplication gate hashes the composite scan key to a SHA-256 digest before the filter sees it, and the filter stores only bits and logs only its verdict plus sizing telemetry. No NDC-plus-operator correlation, no patient identifier, and no raw payload ever enters the filter or its audit line, keeping it inside the 45 CFR § 164.312(b) audit-control boundary.

Related topics

Idempotent Scan Ingestion with Redis SETNX