Tair (Redis® OSS-Compatible):TairBloom

Descripción general

En Redis, puede implementar una funcionalidad similar mediante Hash, Set o un conjunto de bits almacenado en un String. Sin embargo, estos métodos consumen gran cantidad de memoria o no pueden escalar dinámicamente sin alterar la tasa de falsos positivos. TairBloom es ideal para casos de uso que requieren comprobaciones eficientes de pertenencia sobre grandes volúmenes de datos y toleran una pequeña tasa de falsos positivos. Puede usar la API de TairBloom directamente, sin necesidad de wrappers personalizados ni implementaciones locales.

Funciones clave

• Bajo consumo de memoria.

• Admite escalado automático.

• Tasa de falsos positivos personalizable que se mantiene estable durante el escalado automático.

Casos de uso

Mejores prácticas

void recommendedSystem(userid) {
    while (true) {
        // Get a candidate article ID.
        docid = getDocByRandom()
        if (bf.exists(userid, docid)) {
            // The article was probably already recommended, so skip it.
            continue;
        } else {
            // The article was definitely not recommended, so send it.
            sendRecommendMsg(docid);
            // Record the recommendation.
            bf.add(userid, docid);
            break;
        }
    }
}

bool crawlerSystem( ) {
    while (true) {
        // Get a URL to crawl.
        url = getURLFromQueue()
        if (bf.exists(url_bloom, url)) {
            // The URL was probably already crawled, so skip it.
            continue;
        } else {
            // Download the URL content.
            doDownload(url)
            // Add the URL to TairBloom.
            bf.add(url_bloom, url);
        }
    }
}

Funcionamiento

TairBloom es una implementación de un Scalable Bloom Filter. Admite escalado automático y mantiene una tasa estable de falsos positivos. Un Scalable Bloom Filter es una versión optimizada del filtro bloom clásico. Las siguientes secciones describen los principios básicos de los filtros bloom y los Scalable Bloom Filters.

• Filtro bloom

  Un filtro bloom es una estructura de datos probabilística eficiente en el uso de espacio, propuesta por Burton Bloom en 1970. Se utiliza para comprobar si un elemento pertenece a un conjunto.

  Un filtro bloom nuevo consiste en un arreglo de bits de m posiciones, todas inicializadas en 0. También emplea k funciones hash distintas que generan una distribución aleatoria uniforme, donde k es una constante menor que m. Al agregar un elemento al filtro bloom, las k funciones hash asignan el elemento a k posiciones del arreglo de bits, y los bits en esas posiciones se establecen en 1. Un mismo bit puede ser compartido por varios elementos. La siguiente figura ilustra cómo se insertan los elementos X1 y X2 en un filtro bloom con k igual a 3.

  

  Para consultar un elemento, se utilizan las mismas k funciones hash para obtener las k posiciones de bits correspondientes. Si todos los bits en esas posiciones son 1, se considera que el elemento está presente en el filtro bloom. Si algún bit es 0, el elemento definitivamente no está presente. La siguiente figura muestra cómo se comprueba la existencia de Y1 y Y2 en el filtro bloom.

  

  Como se observa en la figura, aunque el elemento Y2 nunca se insertó en el filtro bloom, este reporta que Y2 existe. Esto constituye un falso positivo. Con base en ello, se resumen las características de un filtro bloom:

  • Las posiciones de bits pueden ser compartidas por distintos elementos.

  • Pueden ocurrir falsos positivos. Cuantos más elementos haya en el filtro bloom, mayor será la probabilidad de un falso positivo. No obstante, no se producen falsos negativos. Si el filtro indica que un elemento no está presente, definitivamente no lo está.

  • Es posible agregar elementos a un filtro bloom, pero no eliminarlos. Esto se debe a que las posiciones de bits pueden estar compartidas, y borrar un bit correspondiente a un elemento podría afectar a otros.

• Scalable Bloom Filter

  A medida que se agregan más elementos a un filtro bloom, la tasa de falsos positivos aumenta. Para mantener dicha tasa estable, es necesario incrementar el tamaño del filtro bloom. Sin embargo, un filtro bloom estándar no puede redimensionarse. Un Scalable Bloom Filter resuelve este problema mediante la creación de nuevos filtros bloom que se apilan en un único filtro lógico.

  La siguiente figura muestra el modelo básico de un Scalable Bloom Filter (SBF), compuesto por dos capas: BF0 y BF1. Inicialmente, el SBF solo contiene la capa BF0. Suponga que, tras insertar los elementos a, b y c, la capa BF0 ya no puede mantener la tasa de falsos positivos definida por el usuario. En ese momento se crea una nueva capa (BF1). Los elementos subsecuentes d, e y f se insertan en la capa BF1. De igual forma, cuando la capa BF1 deja de cumplir con la tasa de falsos positivos, se crea una nueva capa (BF2), y así sucesivamente. Para obtener más información, consulte Scalable Bloom Filter.

  

  Importante

  Cuando TairBloom escala automáticamente, la nueva capa tiene el doble de capacidad y cuatro veces el consumo de memoria de la capa anterior.

  Cada capa adicional incrementa el tiempo de consulta, ya que una consulta podría necesitar recorrer varias capas de filtros bloom. Un Scalable Bloom Filter siempre inserta datos en la capa más reciente, y las consultas comienzan desde la capa más reciente hasta llegar a la primera capa (BF0). Como consecuencia, las operaciones de escalado automático en TairBloom pueden generar claves grandes y degradar el rendimiento. Esta degradación aumenta conforme crece el número de elementos.

  En la práctica, evite desencadenar el escalado automático de TairBloom y considere esta función como un mecanismo de protección. Reserve suficiente memoria para la instancia a fin de prevenir fallos de escritura tras un evento de escalado automático, los cuales podrían activar un proceso prolongado de desalojo de datos y dejar la instancia sin respuesta. Utilice el comando BF.INFO para comprobar si una clave está a punto de desencadenar un evento de escalado automático. Cuando el número de items en la capa más reciente alcanza su capacity, un evento de escalado automático es inminente.

  Cuando la capacidad real supera la capacidad preestablecida, TairBloom escala automáticamente para garantizar que las operaciones de escritura continúen, lo que previene incidentes en producción. Una vez completada la operación de escalado automático, reconstruya la clave lo antes posible para mejorar el rendimiento y reducir los riesgos asociados al siguiente evento de escalado.

Requisitos previos

Notas de uso

• Los comandos descritos en este tema operan sobre datos de TairBloom en una instancia de Tair.

• Planifique con antelación la capacidad inicial y la tasa de falsos positivos. Si la capacidad esperada de la clave objetivo es mucho mayor que 100, utilice el comando BF.RESERVE para crear la clave de TairBloom. Evite crear la clave con el comando BF.ADD.

  La siguiente lista describe las diferencias entre ejecutar el comando BF.ADD y el comando BF.RESERVE.

  • BF.ADD (o BF.MADD): si la clave objetivo no existe al momento de ejecutar el comando, Tair crea automáticamente una instancia de TairBloom con una capacidad predeterminada de 100 y una tasa de falsos positivos (error_rate) de 0.01. Si la capacidad requerida es mucho mayor que 100, solo podrá agregar más elementos posteriormente mediante la expansión de la capacidad. A medida que aumenta el número de capas internas en TairBloom, las operaciones de consulta deben recorrer múltiples filtros bloom, lo que degrada severamente el rendimiento.

  • BF.RESERVE (o BF.INSERT): al ejecutar este comando, debe establecer la capacity (capacidad inicial). Este comando inicializa la capacidad en la primera capa de la clave TairBloom. Una clave TairBloom con menos capas ofrece consultas más rápidas.

  Nota

  Por ejemplo, para insertar 10,000,000 de elementos con una tasa de falsos positivos de 0.01, crear una clave TairBloom con el comando BF.ADD requiere 176 MB de memoria. En cambio, crear la clave con el comando BF.RESERVE requiere solo 16 MB.

  La siguiente tabla muestra el uso de memoria para claves creadas con diferentes capacidades iniciales y tasas de falsos positivos mediante el comando BF.RESERVE. Los valores son solo de referencia.

  Capacidad	Tasa de falsos positivos: 0.01	Tasa de falsos positivos: 0.001	Tasa de falsos positivos: 0.0001
  100,000	0.12 MB	0.25 MB	0.25 MB
  1,000,000	2 MB	2 MB	4 MB
  10,000,000	16 MB	32 MB	32 MB
  100,000,000	128 MB	256 MB	256 MB
  1,000,000,000	2 GB	2 GB	4 GB

  Al crear una clave con una capacidad muy grande, considere el parámetro error_rate. Una clave con una capacidad muy grande y alta precisión (un valor bajo de error_rate) podría fallar debido a memoria insuficiente en la instancia.

• TairBloom permite insertar nuevos elementos, pero no eliminar los existentes. Por lo tanto, el uso de memoria de una clave TairBloom solo aumenta. Para evitar que una clave TairBloom crezca excesivamente y provoque errores de falta de memoria (OOM), considere las siguientes sugerencias.

  • Divida los datos de negocio: divida y refine sus datos de negocio para evitar almacenar una gran cantidad de información en una sola clave TairBloom. Esto no solo evita que la clave sea demasiado grande y afecte el rendimiento de las consultas, sino que también impide que la mayor parte del tráfico de consultas se dirija a la instancia de Redis donde reside la clave, lo cual podría generar una clave caliente y causar desequilibrio en el acceso.

    Divida sus datos de negocio y distribúyalos entre varias claves TairBloom. Si utiliza una instancia de clúster, puede distribuir las claves TairBloom entre los nodos del clúster para equilibrar la memoria y el tráfico, lo que le permite aprovechar al máximo un clúster distribuido.

  • Reconstrucción periódica: si su negocio lo permite, reconstruya periódicamente la clave TairBloom. Utilice el comando DEL para eliminar la clave TairBloom y luego extraiga los datos de la base de datos del backend para reconstruirla. Esto ayuda a controlar el tamaño de la clave TairBloom.

    También puede crear varias claves TairBloom desde el inicio y rotar entre ellas para controlar el tamaño individual de cada clave. Este enfoque evita reconstrucciones frecuentes, pero consume más memoria.

Referencia de comandos

BF.RESERVE

BF.RESERVE BFKEY 0.01 100

OK

BF.ADD

BF.ADD BFKEY item1

(integer) 1

BF.MADD

BF.MADD BFKEY item1 item2 item3

(integer) 1
    (integer) 1
    (integer) 1

BF.EXISTS

BF.EXISTS BFKEY item1

(integer) 1

BF.MEXISTS

BF.MEXISTS BFKEY item1 item5

(integer) 1
    (integer) 0

BF.INSERT

BF.INSERT bfkey1 CAPACITY 10,000 ERROR 0.001 ITEMS item1 item2 item3

(integer) 1
    (integer) 1
    (integer) 1

BF.INFO

BF.INFO bk1

1) "total_items:6,num_blooms:2"
    2) "bytes:4 bits:32 hashes:7 hashwidth:64 capacity:3 items:3 error_ratio:0.01"
    3) "bytes:16 bits:128 hashes:9 hashwidth:64 capacity:10 items:3 error_ratio:0.0025"

Preguntas frecuentes