Filtros de Bloom: resumir el conjunto y aceptar equivocarse

Las dos lecciones anteriores comparten un rasgo que conviene hacer explícito antes de romperlo: ambas son exactas. La resta de vectores devuelve intervalos ciertos y el descenso por el árbol devuelve ramas ciertas, y en ninguno de los dos casos hace falta comprobar nada después. Esta lección explora la tercera familia, que renuncia a esa exactitud de forma deliberada y consciente porque a cambio consigue algo que ninguna de las otras dos ofrece: mensajes cuyo tamaño se mide en bits por elemento en lugar de en bytes, y protocolos que terminan en una o dos idas y vueltas en lugar de en una por nivel del árbol. La renuncia no es gratuita y su contabilidad hay que llevarla con cuidado, porque un falso positivo en una sincronización no significa un dato de más sino un dato de menos, que es el modo de fallo peligroso. Y hay más recorrido del que se suele contar: la familia no se agota en el filtro clásico, sino que incluye variantes capaces de estimar el tamaño de la diferencia antes de decidir nada y variantes invertibles capaces de reconstruirla entera desde un resumen cuyo tamaño depende solo de lo que difiere y no de lo que se guarda, que es exactamente el suelo teórico que la primera lección estableció.

Un resumen que solo se equivoca en un sentido

La construcción es breve. Se reserva un vector de bits de longitud fija, inicialmente a cero, y se eligen varias funciones de hash independientes. Insertar un elemento consiste en calcular sus posiciones con esas funciones y poner a uno los bits correspondientes. Preguntar si un elemento está consiste en mirar esas mismas posiciones: si alguna vale cero, el elemento no está con certeza absoluta; si todas valen uno, el elemento está probablemente, porque esos bits pueden haberlos puesto otros elementos entre todos.

La asimetría es la propiedad definitoria y hay que tenerla presente en todo lo que sigue: no hay falsos negativos, solo falsos positivos. El filtro nunca dirá que no tiene algo que sí tiene, y a veces dirá que tiene algo que no tiene. La tasa de esos errores depende de la relación entre bits reservados y elementos insertados, y con el número óptimo de funciones de hash sale una tabla muy cómoda de recordar, porque no depende en absoluto del tamaño de los elementos.

Bits por elemento y tasa de falsos positivos con k optimo

  4.8 bits ....... 10 %
  9.6 bits ....... 1 %
  14.4 bits ...... 0.1 %
  19.2 bits ...... 0.01 %

  un identificador de 32 bytes son 256 bits: el filtro lo resume en 10 y se equivoca el 1 %

Esa última línea es el argumento comercial entero. Enviar el catálogo de nombres de un millón de elementos cuesta treinta y dos megabytes; enviar un filtro de Bloom que describa el mismo conjunto con un uno por ciento de error cuesta algo más de un megabyte. Y conviene decir sin adornos lo que ese cálculo no arregla: sigue siendo proporcional al número de elementos guardados. El filtro clásico reduce la constante en un factor de veinticinco, no cambia la naturaleza del coste, y por eso la parte verdaderamente interesante de esta familia son las variantes de la segunda mitad de la lección.

// Insercion y consulta con k funciones derivadas de dos hashes
function posiciones(elemento, k, m) {
  const a = hash1(elemento), b = hash2(elemento);
  const salida = [];
  for (let i = 0; i < k; i++) salida.push((a + i * b) % m);
  return salida;
}

function insertar(bits, elemento, k, m) {
  for (const p of posiciones(elemento, k, m)) bits[p] = 1;
}

function quizaContiene(bits, elemento, k, m) {
  return posiciones(elemento, k, m).every((p) => bits[p] === 1);
}

Qué significa un falso positivo cuando se sincronizan datos

El uso en reconciliación es directo. La réplica que quiere ponerse al día construye un filtro con los identificadores de todo lo que tiene y lo envía. La otra recorre sus propios elementos, consulta el filtro y envía aquellos para los que la respuesta sea negativa, porque esa respuesta es certera. El protocolo termina en una ida y vuelta y ha transmitido un filtro pequeño más los datos que faltaban.

Ahora hay que mirar despacio qué ocurre con los falsos positivos, porque la intuición engaña. Un falso positivo significa que el emisor consulta el filtro por un elemento que el receptor no tiene, el filtro responde que sí lo tiene, y en consecuencia ese elemento no se envía. El error no produce tráfico de más sino una omisión: exactamente el modo de fallo que la primera lección señaló como el peligroso, un dato que nunca llega y del que nadie deja constancia. Con un uno por ciento de tasa y una diferencia de mil elementos, se quedan diez por el camino en cada intercambio.

Hay una segunda consecuencia menos evidente y es de privacidad. Mandar un filtro con lo que uno tiene equivale a entregar al otro extremo un oráculo de pertenencia: puede probar cualquier identificador que se le ocurra y averiguar, con la certeza de la asimetría, si no lo tienes, y con alta probabilidad si lo tienes. En un sistema donde los identificadores se derivan de contenido adivinable, esa fuga es real y ha causado problemas documentados en despliegues públicos que usaron filtros para que los clientes ligeros describieran lo que les interesaba. Cuando importe, el filtro hay que engordarlo con elementos falsos, lo cual cuesta ancho de banda y falsos positivos adicionales.

Estimar la diferencia antes de transmitirla

Todas las decisiones de este nivel dependen de una cantidad que ninguna réplica conoce: el tamaño de la diferencia. Elegir el tamaño del filtro, decidir si compensa el descenso por el árbol o si conviene mandarlo todo, dimensionar un mensaje de una sola ronda; todo requiere una estimación previa de cuántos elementos difieren. Y resulta que estimar esa cantidad es mucho más barato que calcularla, lo cual convierte al estimador en una pieza de pleno derecho del protocolo y no en un accesorio.

La técnica más simple es el muestreo por resumen mínimo: cada lado se queda con los cien identificadores cuyo hash es menor y se los envía al otro; la proporción de coincidencias entre esas dos muestras estima la similitud de los conjuntos completos, porque el criterio de selección es el mismo en ambos lados y por tanto las muestras son comparables. Con unos pocos kilobytes se obtiene una estimación con un error de un pequeño porcentaje, suficiente para elegir mecanismo.

La técnica específica de esta familia es el estimador por estratos, que reutiliza la maquinaria de los filtros. Se construyen varios resúmenes en paralelo, cada uno alimentado con una fracción cada vez menor de los elementos, elegida por los bits iniciales de su hash: el primero recibe todos, el segundo la mitad, el tercero la cuarta parte y así sucesivamente. Los estratos densos serán irrecuperables y los ralos decodificarán sin problema; se toma el primero que decodifique, se cuenta lo que contiene y se multiplica por su factor de muestreo. Sale una estimación del tamaño de la diferencia por unos pocos kilobytes fijos, sin depender del tamaño de los conjuntos.

flowchart LR
E[estimador por estratos] --> D[estimacion del tamano de la diferencia]
D --> F[filtro invertible dimensionado a esa cifra]
F --> P[pelado iterativo de celdas puras]
P --> S[diferencia recuperada entera]
P --> X[fallo de decodificacion y reintento mayor]
style D fill:#89b4fa,color:#11111b
style S fill:#a6e3a1,color:#11111b
style X fill:#f38ba8,color:#11111b

Filtros invertibles: recuperar la diferencia, no solo detectarla

La variante que de verdad alcanza el suelo teórico cambia los bits por celdas. Cada celda guarda tres cosas: un contador, la suma exclusiva de los identificadores que cayeron en ella y la suma exclusiva de sus resúmenes de comprobación. Insertar un elemento incrementa el contador y acumula sus dos valores en las celdas que le tocan; borrarlo hace exactamente lo mismo con el contador a la baja, porque la operación exclusiva es su propia inversa. Esa reversibilidad es lo que da nombre a la estructura y lo que permite el truco.

El truco consiste en que dos réplicas pueden restar sus estructuras celda a celda. En el resultado, los elementos comunes se cancelan por completo, porque se insertaron y se restaron con los mismos valores, y solo sobreviven los que están en uno y no en el otro. Lo que queda es un resumen de la diferencia simétrica, y de ahí se extraen los elementos con un pelado iterativo: se busca una celda cuyo contador valga uno o menos uno y cuyo resumen de comprobación cuadre, lo que significa que contiene un solo elemento; se lee, se anota de qué lado estaba y se elimina de las demás celdas donde aparezca, lo que puede dejar puras otras celdas y permitir continuar.

// Restar dos estructuras celda a celda deja solo la diferencia
function restar(mia, suya) {
  return mia.map((c, i) => ({
    cuenta: c.cuenta - suya[i].cuenta,
    clave: c.clave ^ suya[i].clave,
    comprobacion: c.comprobacion ^ suya[i].comprobacion,
  }));
}

// Una celda es pura si contiene un solo elemento y su comprobacion cuadra
function esPura(celda) {
  return Math.abs(celda.cuenta) === 1 && hash(celda.clave) === celda.comprobacion;
}

El resultado es notable y merece enunciarse con precisión: con del orden de una vez y media el tamaño de la diferencia en celdas, el pelado recupera la diferencia completa con probabilidad muy alta, y el mensaje no depende en absoluto del número de elementos guardados. Un millón de elementos por lado con diez de diferencia se reconcilian con un mensaje de unos pocos cientos de bytes y una sola ida y vuelta, más lo que ocupen los diez elementos. Eso es el suelo de la primera lección alcanzado por un camino practicable.