Filtros de Bloom

Lo que cubre este capítulo

El último bloque del curso se va hacia estructuras que hacen un trato que las anteriores rechazaban: renuncia a la exactitud o a una garantía de peor caso, y a cambio te llevas una ganancia enorme en espacio o en simplicidad. El filtro de Bloom es el ejemplo más puro. Responde "¿ya vi este elemento?" usando una fracción mínima de la memoria que necesitaría un set real, a cambio de aceptar una tasa pequeña y ajustable de falsos positivos — de vez en cuando dice "probablemente sí" para algo que nunca vio. Y lo importante: nunca produce un falso negativo; si dice "no", el elemento definitivamente no está. Esa asimetría es justo lo que quiere una clase enorme de sistemas — un pre-filtro rápido y diminuto que rechaza de forma confiable el caso común (nunca visto) y solo rara vez dispara una verificación cara e innecesaria. En este capítulo construimos uno a partir de un array de bits y unas cuantas funciones hash, vemos cómo los elementos encienden bits y cómo una consulta produce un falso positivo, y medimos la recompensa: representar un millón de elementos con 1% de error en 1.2 megabytes donde un set real necesita 122 — cien veces menos.

Un poco de historia

Burton Howard Bloom presentó el filtro en un paper de 1970 con un título maravillosamente práctico: "Space/Time Trade-offs in Hash Coding with Allowable Errors". Su ejemplo motivador era un programa de separación silábica: la mayoría de las palabras siguen reglas simples de separación, y solo un diccionario pequeño de excepciones necesita la búsqueda cara, así que un filtro compacto que dijera de forma confiable "esta palabra no es una excepción" (rechazando el caso común) ahorraba casi todos los accesos a disco. Ese es el arquetipo de todo uso de filtros de Bloom desde entonces — una compuerta barata en memoria frente a una operación cara. La estructura se quedó como herramienta de especialistas durante décadas, y luego se volvió omnipresente con el auge de los sistemas distribuidos a gran escala en los 2000: Bigtable de Google y sus descendientes (Cassandra, HBase, LevelDB, RocksDB) usan filtros de Bloom para evitar lecturas a disco de llaves que no existen, ahorrando cantidades enormes de operaciones de I/O. El trade-off espacio/tiempo que Bloom planteó en 1970 — acepta un poco de error para ahorrar mucha memoria — resultó ser una de las ideas más trascendentes de la ingeniería de sistemas, y lanzó toda una familia de estructuras de datos probabilísticas (counting Bloom filters, cuckoo filters, HyperLogLog, count-min sketch) construidas sobre el mismo trato.

La intuición

Empieza con un array de m bits, todos en cero, y elige k funciones hash que mapeen cada elemento a una posición de bit. Para agregar un elemento, lo hasheas de k formas y enciendes esos k bits en 1. Para consultarlo, lo hasheas de las mismas k formas y miras esos k bits: si todos son 1, reportas "probablemente presente"; si alguno es 0, reportas "definitivamente ausente". La garantía de ausencia es hermética y vale la pena detenerse en ella: agregar un elemento solo enciende bits, nunca los apaga, así que si un bit sigue en 0, ningún elemento que lo hubiera encendido fue agregado jamás — un solo 0 es prueba de ausencia. Por eso nunca hay falsos negativos, nunca.

Los falsos positivos vienen del otro lado de la moneda. Los k bits de una consulta podrían estar todos en 1 no porque ese elemento se haya agregado, sino porque otros elementos entre todos encendieron esos bits. La animación lo muestra: después de agregar cat, dog y fox, la palabra hycr — que nunca se agregó — hashea a tres posiciones que otros elementos ya habían encendido, así que el filtro dice "probablemente presente". Eso es un falso positivo, y su probabilidad es ajustable: más bits (m más grande) significa menos colisiones y menos falsos positivos; más elementos (n más grande) significa más bits encendidos y más falsos positivos. Lo notable es de qué no depende el espacio: de los elementos mismos. Ya sea que guardes palabras de 8 caracteres o documentos de 8 kilobytes, cada uno cuesta el mismo puñado de bits, porque solo se registran sus posiciones hash, nunca el elemento. Un set real tiene que guardar cada elemento completo; un filtro de Bloom no guarda ninguno, solo la sombra que proyectan sobre el array de bits. De ahí sale la ganancia de memoria de cien a uno — y también la razón por la que nunca puedes recuperar los elementos ni borrar uno (apagar un bit podría apagar un bit que otro elemento necesita).

Complejidad: cómo escala

Agregar y consultar son ambas O(k) — un puñado de cálculos de hash y accesos a bits, sin importar cuántos elementos estén guardados. El espacio es la parte llamativa: para una tasa de falsos positivos objetivo p, el filtro óptimo usa m = −n·ln(p)/(ln2)² bits para n elementos, que son aproximadamente 1.44·log₂(1/p) bits por elemento — más o menos 9.6 bits por elemento para una tasa de 1%, o 14.4 para 0.1%, sin importar el tamaño del elemento. El face-off compara eso contra un set real que guarda los mismos elementos:

Ambos crecen linealmente con la cantidad de elementos, pero la línea del filtro de Bloom queda muy por debajo de la del set, y lo que importa es la brecha. Con un millón de llaves de 16 caracteres y 1% de falsos positivos, el filtro de Bloom usó cerca de 1.2 megabytes (9.6 bits por elemento) mientras que un set real de Python necesitó unos 122 megabytes — cien veces más. Y esa brecha se ensancha conforme crece el tamaño del elemento: los 9.6 bits por elemento del filtro son fijos, así que guardar llaves más largas o documentos completos infla el set mientras el filtro se queda plano. Este es el trade-off espacio/tiempo que Bloom nombró: no estás ahorrando tiempo (la búsqueda de un set ya es O(1)), estás ahorrando memoria, por un orden de magnitud o más, a cambio de una salpicada controlada de falsos positivos. Para un filtro que vive en RAM cuidando una base de datos en disco, caber en una centésima parte de la memoria es la diferencia entre viable y no viable.

En qué es bueno y en qué no

Los filtros de Bloom son la herramienta correcta como pre-filtro barato frente a una operación cara, cuando la respuesta común es "no está presente" y un falso positivo raro solo cuesta una verificación innecesaria (nunca un resultado incorrecto, si la verificación cara es la autoridad final). Los usos canónicos: bases de datos y motores de almacenamiento (Bigtable, Cassandra, HBase, LevelDB, RocksDB) revisando si una llave podría estar en una tabla en disco antes de leerla, saltándose el I/O de disco para llaves que definitivamente no están; CDNs y caches evitando búsquedas de objetos no cacheados; navegadores web revisando URLs contra listas de sitios maliciosos (Google Safe Browsing); correctores ortográficos y filtros de palabras; sistemas distribuidos reduciendo llamadas de red (¿este nodo posiblemente tiene el dato?); y deduplicación (¿ya vi esto?). Donde sea que la memoria esté apretada y una tasa pequeña de falsos positivos sea aceptable porque solo dispara un fallback, el ahorro de espacio de un orden de magnitud del filtro de Bloom es decisivo.

Donde es la herramienta equivocada es cuando necesitas exactitud (cero tolerancia a falsos positivos), cuando necesitas borrar elementos (un filtro de Bloom estándar no puede — apagar un bit podría romper otros elementos; un counting Bloom filter, que reemplaza los bits con contadores pequeños, soporta borrado a cambio de más espacio), cuando necesitas enumerar o recuperar los elementos guardados (imposible — solo quedan las sombras de bits), o cuando necesitas guardar valores asociados (es un set, no un map). Tampoco se puede redimensionar fácilmente una vez construido (las posiciones hash asumen una m fija), y su tasa de falsos positivos se degrada si agregas más elementos de los que dimensionaste. Y para conteos chicos de elementos un set real es más simple y el ahorro de memoria es irrelevante. El filtro de Bloom es un especialista: membresía aproximada, sin borrado, sin enumeración, a cambio de un espacio fijo diminuto.

Los datos, o las entradas

El face-off compara la memoria de un filtro de Bloom dimensionado de forma óptima (1% de falsos positivos) contra un set real de Python con llaves de 16 caracteres, conforme la cantidad de elementos crece hasta un millón. La correctitud se verifica en serio: a lo largo de muchos filtros aleatorios, todo elemento agregado debe dar presente (un falso negativo sería imposible y sería un bug), y la tasa de falsos positivos medida — sobre decenas de miles de consultas de elementos nunca agregados — debe mantenerse cerca de la teórica (1 − e^(−kn/m))^k. La animación construye un filtro chiquito de 24 bits y 3 hashes, agrega cat, dog y fox (viendo cómo se encienden los bits), y luego consulta un miembro (todos los bits encendidos → probablemente presente), un no-miembro real (un bit en 0 → definitivamente ausente), y una palabra que es un falso positivo (todos los bits encendidos por coincidencia).

Constrúyelo, una función a la vez

El filtro de Bloom — un array de bits, k hashes por doble hashing, agregar y consultar:

class BloomFilter:
    """A Bloom filter with m bits and k hash functions. The k hashes are derived from two base hashes
    by DOUBLE HASHING (h_i = h1 + i·h2), which behaves like k independent hashes without computing k
    of them."""

    def __init__(self, m_bits, k):
        self.m = m_bits
        self.k = k
        self.bits = bytearray((m_bits + 7) // 8)   # m bits, packed 8 per byte

    def _positions(self, item):
        data = repr(item).encode()
        h1 = int.from_bytes(hashlib.sha256(data).digest()[:8], "big")
        h2 = int.from_bytes(hashlib.md5(data).digest()[:8], "big") | 1   # odd, so it's coprime-ish with m
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, item):
        """Set the k bits this item hashes to. Adding only ever turns bits ON — which is exactly why
        a Bloom filter can never produce a false negative."""
        for pos in self._positions(item):
            self.bits[pos >> 3] |= 1 << (pos & 7)

    def __contains__(self, item):
        """Probably-present if ALL k bits are set; definitely-absent if ANY is 0."""
        return all(self.bits[pos >> 3] & (1 << (pos & 7)) for pos in self._positions(item))

    def fill_ratio(self):
        """Fraction of bits currently set — used to sanity-check against the theoretical prediction."""
        return sum(bin(byte).count("1") for byte in self.bits) / self.m

Dimensionarlo — los bits y la cantidad de hashes óptimos para una tasa de error objetivo, y la fórmula de falsos positivos:

def optimal_params(n, target_fpr):
    """Given the expected number of items n and a target false-positive rate, the size m and hash
    count k that minimize memory. m = -n·ln(p) / (ln2)^2 bits, and the optimal k = (m/n)·ln2 — which
    works out to roughly 1.44·log2(1/p) bits per item, independent of the items' own size. Returns
    (m_bits, k)."""
    m = max(1, math.ceil(-n * math.log(target_fpr) / (math.log(2) ** 2)))
    k = max(1, round((m / n) * math.log(2)))
    return m, k


def theoretical_fpr(m, k, n):
    """The predicted false-positive rate after inserting n items into m bits with k hashes:
    (1 - e^(-k·n/m))^k. This is the formula a Bloom filter is designed around."""
    return (1 - math.exp(-k * n / m)) ** k

Míralo funcionar

Aquí hay un filtro de Bloom de 24 bits con 3 funciones hash. Empieza todo en ceros. Agregar cat enciende sus tres posiciones hash en 1 (azul); dog y fox encienden tres más cada uno — los bits solo se prenden, nunca se apagan. Ahora las consultas. Preguntar por cat revisa sus tres posiciones: todas están en 1 (verde), así que el filtro reporta "probablemente presente" — correctamente. Preguntar por un no-miembro real encuentra al menos una posición todavía en 0 (rojo), lo cual prueba que nunca se agregó — la garantía de cero falsos negativos, a la vista. Y luego el caso interesante: una palabra que nunca se agregó, pero cuyas tres posiciones hash resultan ser bits que cat, dog o fox ya habían encendido. El filtro las revisa, encuentra las tres en 1, y reporta "probablemente presente" — un falso positivo. Nada está mal; esos bits sí están encendidos, solo que por otros elementos. Ese es el error por el que el filtro cambia la exactitud, y su tasa es exactamente lo que controla la fórmula de dimensionamiento:

El código completo

La pestaña "desde cero" es el filtro de Bloom más la matemática del dimensionamiento óptimo; la pestaña de librería es un set real — la referencia exacta que el filtro aproxima y la línea base de memoria a la que le gana — con una nota sobre la librería de producción rbloom. Cambia entre ellas: el set es exacto y guarda cada elemento; el filtro de Bloom es aproximado y no guarda ninguno, y ese es todo el trato.

"""Bloom filter — a probabilistic set that answers "have I seen this?" using a tiny fraction of the
memory a real set needs, at the cost of occasional false positives (but NEVER false negatives). It's
the first of the tier's structures that trade exactness for a dramatic resource win, and the trade is
often worth it: a Bloom filter can represent millions of items in a few megabits and reject
never-seen items instantly, which is why it guards databases, caches, and browsers against expensive
lookups.

The structure is startlingly simple: a bit array of m bits, all zero, and k independent hash
functions. To ADD an item, hash it k ways and set those k bits to 1. To QUERY an item, hash it the
same k ways and check whether ALL k bits are 1. If any is 0, the item was definitely never added (no
false negatives — adding only ever sets bits). If all k are 1, the item is PROBABLY present, but
might be a false positive: those bits could have been set by other items. There's no way to remove an
item (clearing a bit might unset a bit another item needs) and no way to list what's stored. In
exchange, the space is a handful of bits per item regardless of how large the items themselves are.
"""
import hashlib
import math


# region: bloom
class BloomFilter:
    """A Bloom filter with m bits and k hash functions. The k hashes are derived from two base hashes
    by DOUBLE HASHING (h_i = h1 + i·h2), which behaves like k independent hashes without computing k
    of them."""

    def __init__(self, m_bits, k):
        self.m = m_bits
        self.k = k
        self.bits = bytearray((m_bits + 7) // 8)   # m bits, packed 8 per byte

    def _positions(self, item):
        data = repr(item).encode()
        h1 = int.from_bytes(hashlib.sha256(data).digest()[:8], "big")
        h2 = int.from_bytes(hashlib.md5(data).digest()[:8], "big") | 1   # odd, so it's coprime-ish with m
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, item):
        """Set the k bits this item hashes to. Adding only ever turns bits ON — which is exactly why
        a Bloom filter can never produce a false negative."""
        for pos in self._positions(item):
            self.bits[pos >> 3] |= 1 << (pos & 7)

    def __contains__(self, item):
        """Probably-present if ALL k bits are set; definitely-absent if ANY is 0."""
        return all(self.bits[pos >> 3] & (1 << (pos & 7)) for pos in self._positions(item))

    def fill_ratio(self):
        """Fraction of bits currently set — used to sanity-check against the theoretical prediction."""
        return sum(bin(byte).count("1") for byte in self.bits) / self.m
# endregion


# region: params
def optimal_params(n, target_fpr):
    """Given the expected number of items n and a target false-positive rate, the size m and hash
    count k that minimize memory. m = -n·ln(p) / (ln2)^2 bits, and the optimal k = (m/n)·ln2 — which
    works out to roughly 1.44·log2(1/p) bits per item, independent of the items' own size. Returns
    (m_bits, k)."""
    m = max(1, math.ceil(-n * math.log(target_fpr) / (math.log(2) ** 2)))
    k = max(1, round((m / n) * math.log(2)))
    return m, k


def theoretical_fpr(m, k, n):
    """The predicted false-positive rate after inserting n items into m bits with k hashes:
    (1 - e^(-k·n/m))^k. This is the formula a Bloom filter is designed around."""
    return (1 - math.exp(-k * n / m)) ** k
# endregion

"""The contrast and the reference. A Bloom filter approximates a set, so the natural comparison is a
REAL set — exact membership, no false positives, but storing every element in full. Python's built-in
`set` is that reference: it's the correctness oracle (a Bloom filter must never report absent for
something a set contains) and the memory baseline the Bloom filter beats by orders of magnitude.

In production you'd use a maintained implementation like `rbloom` (a fast Rust-backed Bloom filter):

    from rbloom import Bloom
    bf = Bloom(1_000_000, 0.01)   # expected items, target false-positive rate
    bf.add("key"); "key" in bf

`exact_set_bytes` estimates the memory a real set would need, for the memory face-off.
"""
import sys


# region: exact_set
def exact_set_bytes(items):
    """A rough measure of the memory a real Python set of these items uses: the set's own overhead
    plus each element's object size. This is what a Bloom filter replaces with a fixed, tiny bit
    array — and it grows with both the number of items AND the size of each item, where the Bloom
    filter is independent of item size."""
    s = set(items)
    total = sys.getsizeof(s)
    for item in s:
        total += sys.getsizeof(item)
    return total
# endregion

Desde cero vs librería

El filtro de Bloom replantea lo que puede ser una estructura de datos. Cada estructura antes de este bloque era exacta — guardaba tus datos y respondía preguntas sobre ellos correctamente. El filtro de Bloom no guarda ningún dato, solo una sombra de bits con pérdida, y responde una pregunta un poco más débil (quizá-presente) usando una fracción del espacio. Es un trato profundo y útil, y es la idea fundacional de las estructuras de datos probabilísticas: HyperLogLog cuenta elementos distintos en kilobytes sin importar el conteo, count-min sketch estima frecuencias en espacio fijo, y los filtros cuckoo y quotient refinan el trade-off de Bloom. La lección es que la exactitud es un recurso que puedes gastar — cuando un error pequeño y controlado es aceptable, cambiarlo te compra espacio (o tiempo) que no puedes conseguir de ninguna otra forma. El ahorro de memoria de cien a uno del face-off es lo que vale ese trato en la práctica, y escala todavía más con el tamaño del elemento porque el costo del filtro es independiente de él. En producción usarías rbloom o el filtro integrado de tu base de datos; construir uno tú mismo es lo que vuelve concreto el "sin falsos negativos, falsos positivos ajustables, espacio independiente del tamaño del elemento" en lugar de una lista de propiedades.

Dónde te lo vas a encontrar

Los filtros de Bloom corren en la infraestructura debajo de casi todo sistema grande. Motores de almacenamiento y bases de datos — Cassandra, HBase, Bigtable, LevelDB, RocksDB, extensiones de PostgreSQL — los usan para saltarse lecturas a disco de llaves ausentes, una de las optimizaciones de I/O de mayor impacto en sistemas de datos. Los navegadores web los usan (Google Safe Browsing) para revisar URLs contra listas enormes de malware/phishing de forma local. Las CDNs y los caches los usan para evitar búsquedas de contenido no cacheado. Los sistemas distribuidos los usan para reducir viajes de red ("¿esta réplica podría tener la llave?"). Los clientes de criptomonedas (Bitcoin SPV) los usaron para pedir transacciones relevantes sin descargar todo. Los correctores ortográficos, las blocklists de contraseñas débiles, la deduplicación de clics en anuncios y los sistemas de recomendación ("¿este usuario ya vio este ítem?") todos los usan. Y la familia más amplia — HyperLogLog para cardinalidad, count-min sketch para frecuencias — mueve analítica a gran escala (Redis, Presto y los sistemas de streaming los traen incluidos). Donde sea que una prueba de membresía aproximada y diminuta pueda controlar el acceso a una operación cara, seguramente hay un filtro de Bloom haciéndolo.

Lo que te llevas

Un filtro de Bloom es un array de bits más k funciones hash que guarda membresía aproximada de conjunto en unos cuantos bits por elemento — independiente del tamaño del elemento — encendiendo k bits al agregar y revisándolos al consultar. Un bit en 0 prueba ausencia (sin falsos negativos, nunca); k bits todos en 1 significan probablemente-presente pero puede ser un falso positivo, a una tasa que ajustas con la fórmula de dimensionamiento (~1.44·log₂(1/p) bits por elemento). Cambia exactitud, borrado y enumeración por un ahorro de espacio de un orden de magnitud — cien veces menos con 1% de error para un millón de llaves — y por eso cuida bases de datos, caches y navegadores como pre-filtro barato. Es el ejemplo fundacional de cambiar exactitud por recursos, el tema de las estructuras de datos probabilísticas.

El siguiente capítulo mantiene el tema de los trade-offs ingeniosos pero regresa a estructuras exactas, cambiando determinismo por simplicidad. Las skip lists consiguen la búsqueda, inserción y borrado en O(log n) de un árbol balanceado usando nada más listas ligadas y volados — la aleatorización reemplaza las rotaciones intrincadas de los árboles AVL y rojo-negro con una estructura mucho más fácil de construir y de razonar, y que se usa en bases de datos reales (los sorted sets de Redis, LevelDB) precisamente por esa simplicidad.