¿Qué es un filtro de Bloom y qué problemas reales de backend resuelve?

#Qué es realmente un filtro de Bloom

Un filtro de Bloom es una estructura de datos probabilística diseñada para responder una pregunta de la forma más barata posible: "¿es posible que ya haya visto esto?" Sacrifica precisión perfecta a cambio de búsquedas O(1) y un consumo de memoria que se mantiene plano sin importar cuántos elementos insertes: un hash set con mil millones de cadenas cuesta gigabytes; un filtro de Bloom calibrado para esos mismos mil millones de elementos con una tasa de falsos positivos del 1% cuesta un par de bytes por elemento, y ese multiplicador no crece con la longitud de la cadena.

Estructuralmente no es más que un arreglo de bits de tamaño m, inicializado en ceros, más k funciones hash independientes. Insertar un elemento significa aplicarle k hashes y poner esos k bits en 1. Comprobar la pertenencia significa aplicar los mismos k hashes al elemento y preguntar si todos esos bits ya están en 1.

Esa asimetría es todo el diseño:

• Si cualquiera de los k bits es 0, el elemento definitivamente no está en el conjunto. Nunca hay falsos negativos: esa es la garantía que hace seguro usar un filtro de Bloom como comprobación rápida delante de algo autoritativo.
• Si todos los k bits son 1, el elemento probablemente está en el conjunto — "probablemente" porque otras inserciones podrían haber activado esos mismos bits por pura coincidencia. Ese es el falso positivo, y es el precio que se paga por la compresión.

La tasa de falsos positivos se puede ajustar intercambiando espacio: más bits por elemento y más funciones hash bajan la tasa de error a costa de memoria. Las dos fórmulas clásicas que un entrevistador espera que al menos menciones son el tamaño óptimo del arreglo m = -(n · ln p) / (ln 2)² para n elementos esperados y una tasa objetivo de falsos positivos p, y el número óptimo de funciones hash k = (m/n) · ln 2. En la práctica casi nunca se derivan a mano — las bibliotecas las calculan a partir de n y p —, pero saber que existen, y que insertar más elementos de los que se dimensionó degrada la tasa de falsos positivos, es justo la señal que el entrevistador busca.

Hay otra propiedad tan importante como el falso positivo: un filtro de Bloom estándar no puede borrar elementos. Poner un bit en 0 para "eliminar" un elemento podría apagar un bit del que depende otro elemento distinto, convirtiendo silenciosamente un verdadero positivo en un falso negativo, lo cual rompe la única garantía que la estructura existe para dar. Si necesitas borrado, la alternativa es un filtro de Bloom con contadores (cada posición es un contador pequeño en vez de un solo bit, que se incrementa al insertar y se decrementa al borrar) o una estructura más moderna como el filtro Cuckoo, que soporta borrado de forma nativa y suele ser más eficiente en espacio para la misma tasa de falsos positivos.

#Filtro de Bloom vs. las alternativas

#Los problemas de backend que realmente resuelve

El patrón que aparece una y otra vez en sistemas reales es: poner un filtro de Bloom delante de una consulta costosa y autoritativa, para que absorba el tráfico que de otro modo golpearía esa consulta sin necesidad.

• Caché negativa delante de una base de datos. Si la mayoría de las búsquedas son por claves que no existen — comprobar disponibilidad de nombre de usuario, revisar una clave de caché antes de caer al origen lento, verificar si una URL es maliciosa —, un filtro de Bloom responde "definitivamente no existe" sin un acceso a disco ni una ida y vuelta de red, y solo reenvía los casos "quizás existe" al almacén real.
• Evitar la penetración de caché. Una avalancha de peticiones por claves que nunca se cachearon (o que directamente no existen) puede saltarse la capa de caché por completo y golpear la base de datos — un vector de caída clásico. Un filtro de Bloom con las "claves que se sabe que existen" delante de la caché absorbe esa avalancha.
• Motores de almacenamiento LSM-tree (Cassandra, HBase, RocksDB, LevelDB) mantienen un filtro de Bloom por cada SSTable en disco. Antes de hacer una lectura de disco para comprobar si una clave vive en un archivo determinado, el motor consulta primero el filtro de Bloom de ese archivo — con docenas de SSTables, esto convierte una tormenta de accesos a disco O(número de archivos) en un puñado de comprobaciones de bits en memoria.
• Crawlers distribuidos y pipelines de deduplicación usan un filtro de Bloom para decidir "¿ya encolé/procesé esta URL (o este evento, o este id de usuario)?" sin mantener en memoria cada clave vista alguna vez — el diseño de crawler más adelante en este módulo se apoya exactamente en esto.
• Listas de seguridad de CDN y navegadores (el ejemplo clásico es comprobar "URL maliciosa conocida") usan filtros de Bloom para que el caso común — la URL está bien — nunca necesite una llamada de red a un servicio de threat intelligence.

#Implementación

A continuación, un filtro de Bloom real — dimensionado con las fórmulas estándar, usando dos funciones hash independientes combinadas mediante double hashing para simular k funciones hash de forma barata — usado para proteger una comprobación de disponibilidad de nombre de usuario delante de una base de datos.

Ajustar líneas largas
import hashlib
import math


class BloomFilter:
    def __init__(self, expected_items: int, false_positive_rate: float = 0.01):
        self.size = self._optimal_size(expected_items, false_positive_rate)
        self.hash_count = self._optimal_hash_count(self.size, expected_items)
        self.bit_array = bytearray(math.ceil(self.size / 8))

    @staticmethod
    def _optimal_size(n: int, p: float) -> int:
        # m = -(n * ln p) / (ln 2)^2
        return max(1, math.ceil(-(n * math.log(p)) / (math.log(2) ** 2)))

    @staticmethod
    def _optimal_hash_count(m: int, n: int) -> int:
        # k = (m / n) * ln 2
        return max(1, round((m / n) * math.log(2)))

    def _bit_positions(self, item: str):
        h1 = int(hashlib.sha256(item.encode()).hexdigest(), 16)
        h2 = int(hashlib.md5(item.encode()).hexdigest(), 16)
        for i in range(self.hash_count):
            yield (h1 + i * h2) % self.size

    def add(self, item: str) -> None:
        for bit in self._bit_positions(item):
            self.bit_array[bit // 8] |= (1 << (bit % 8))

    def might_contain(self, item: str) -> bool:
        return all(
            self.bit_array[bit // 8] & (1 << (bit % 8))
            for bit in self._bit_positions(item)
        )


class UsernameRegistry:
    """Protege una búsqueda de nombre de usuario lenta y autoritativa con un filtro de Bloom."""

    def __init__(self, existing_usernames: list[str]):
        self.bloom = BloomFilter(expected_items=len(existing_usernames), false_positive_rate=0.001)
        for name in existing_usernames:
            self.bloom.add(name)

    def is_taken(self, username: str) -> bool:
        if not self.bloom.might_contain(username):
            # Certeza total: este nombre de usuario nunca fue insertado. No hace falta ir a la BD.
            return False
        # El filtro dice "quizás" — se confirma contra la fuente de verdad real.
        return self._check_database(username)

    def _check_database(self, username: str) -> bool:
        # SELECT 1 FROM users WHERE username = %s (o un GET a Redis, etc.)
        raise NotImplementedError

Con un millón de nombres de usuario existentes y una tasa de falsos positivos del 0.1%, este filtro cuesta aproximadamente 1.8 MB de memoria y resuelve la abrumadora mayoría de las comprobaciones "¿está tomado?" — absolutamente todas las de un nombre de usuario genuinamente disponible — sin tocar jamás la base de datos.

🧠 Check your understanding
0/3 · 0/3 answered
1. Un filtro de Bloom indica que una clave está presente. ¿Qué se puede concluir?
La clave nunca fue insertadaLa clave fue eliminadaLa clave está presente con la probabilidad de error configurada como falso positivoLa clave definitivamente está presente
2. ¿Por qué un filtro de Bloom estándar no soporta borrado?
Requeriría rehashear todas las inserciones futurasApagar un bit podría desactivar un bit del que depende otro elemento insertado, generando un falso negativoLos arreglos de bits son inmutables en la mayoría de los lenguajesSí soporta borrado, solo requiere un lock
3. ¿Dónde se usa un filtro de Bloom por SSTable en un motor de almacenamiento real?
Para comprimir el SSTable en discoPara reemplazar por completo el índice de clave primariaPara decidir si vale la pena hacer una lectura de disco de un archivo dado antes de hacerlaPara cifrar las claves en reposo