La clase BloomFilterPolicy en LevelDB es una implementación de un Filtro de Bloom, una estructura de datos probabilística eficiente en espacio utilizada para determinar si un elemento es miembro de un conjunot.

Ventajas y Desventajas

Comparado con otras estructuras de datos como árboles de búsqueda binaria, Tries, tablas hash o listas simples, los Filtros de Bloom ofrecen una significativa ventaja en cuanto a espacio y tiempo. A diferencia de las estructuras que almacenan los elementos de datos en sí (posiblemente comprimidos), un Filtro de Bloom solo almacena unos pocos valores hash de los elementos y utiliza un array de bits compacto, eliminando la sobrecarga de punteros. El tamaño de memoria requerido es independiente del tamaño de los elementos de datos.

Sin embargo, los Filtros de Bloom son adecuados solo para escenarios donde se necesita verificar la posible pertenencia de un elemento a un conjunto, y tienen una tasa de falsos positivos.

Tasa de Falsos Positivos

La probabilidad de falsos positivos en un Filtro de Bloom depende de:

1. El número de funciones hash, k.
2. La longitud del array de bits subyacente, m.
3. El tamaño del conjunto de datos, n.

La tasa de falsos positivos se minimiza cuando k = ln(2) * (m / n), donde m / n representa los bits por clave (la cantidad promedio de bits asignados a cada clave en el conjunto).

Definición de la Interfaz

La clase BloomFilterPolicy define las siguientes funciones:

• const char* Name() const: Devuelve el nombre de la política de filtrado, utilizado para codificar y decodificar el filtro durante la persistencia y la carga en memoria.
• void CreateFilter(const Slice* keys, int n, std::string* dst) const: Crea una política de filtrado para un conjunto de n claves y serializa la política en el string dst.
• bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const: Verifica si una key podría estar presente en el filtro. Si la clave no está en el conjunto utilizado para crear el filtro, esta función devuelve false.

También existe una función de fábrica:

• const FilterPolicy* NewBloomFilterPolicy(int bits_per_key): Crea una nueva instancia de BloomFilterPolicy con la cantidad especificada de bits por clave.

Miembros Privados

• size_t bits_per_key_: La cantidad promedio de bits asignados por clave.
• size_t k_: El número de funciones hash a utilizar.

Constructor y Destructor

El constructor inicilaiza bits_per_key_ y calcula k_ basándose en la fórmula óptima k = ln(2) * (m / n). Los valores de k_ se ajustan para estar entre 1 y 30 para optimizar el costo de sondeo, lo que puede aumentar ligeramente la tasa de falsos positivos.

 explicit BloomFilterPolicy(int bits_per_key) : bits_per_key_(bits_per_key) {
   // Calculate the optimal number of hash functions (k)
   // We round down and cap k to reduce probing cost, which slightly increases
   // the false positive rate but lowers the filtering cost.
   k_ = static_cast<size_t>(bits_per_key * 0.69); // 0.69 is approximately ln(2)
   if (k_ < 1) k_ = 1;
   if (k_ > 30) k_ = 30;
 }
 

Implementación de Métodos Clave

CreateFilter

Este método genera el array de bits del Filtro de Bloom. Primero, calcula la longitud total de bits necesaria y la ajusta a un mínimo de 64 bits si es necesario para mitigar altas tasas de falsos positivos en conjuntos pequeños. Luego, la longitud se alinea a múltiplos de 8 para usar un array de bytes. El número de funciones hash (k_) se almacena al final del array serializado. Para cada clave, se genera una secuencia de k_ posiciones de bits utilizando una técnica de doble hash para simular múltiples funciones hash independientes. Cada posición de bit calculada se activa en el array.

 void CreateFilter(const Slice* keys, int n, std::string* dst) const override {
   // Compute bloom filter size in bits
   size_t bits = n * bits_per_key_;

   // Enforce a minimum bloom filter length for small n to reduce false positives.
   if (bits < 64) bits = 64;

   // Align to a multiple of 8 bits for byte array storage.
   size_t bytes = (bits + 7) / 8;
   bits = bytes * 8;

   const size_t init_size = dst->size();
   dst->resize(init_size + bytes, 0); // Initialize byte array with zeros
   dst->push_back(static_cast<char>(k_));  // Store the number of hash functions (k)

   char* array = &(*dst)[init_size]; // Pointer to the start of the filter data

   // Process each key to set bits in the filter
   for (int i = 0; i < n; i++) {
     // Use double-hashing to generate a sequence of hash values efficiently.
     // This simulates k independent hash functions using a single initial hash.
     uint32_t h = BloomHash(keys[i]);
     const uint32_t delta = (h >> 17) | (h << 15);  // Create a rotating delta for subsequent hashes

     for (size_t j = 0; j < k_; j++) {
       const uint32_t bitpos = h % bits; // Calculate bit position
       // Set the bit at bitpos
       array[bitpos / 8] |= (1 << (bitpos % 8));
       h += delta; // Move to the next hash value
     }
   }
 }
 

KeyMayMatch

Esta función verifica si una clave dada podría existir dentro del Filtro de Bloom proporcionado. Extrae el número de funciones hash k almacenado al final del filtro. Luego, genera la misma secuencia de posiciones de bits que se usaría en CreateFilter para la clave dada. Para cada posición de bit calculada, comprueba si el bit correspondiente en el array está activado. Si alguno de los bits no está activado, la clave definitivamente no está en el conjunto, y la función devuelve false. Si todos los bits requeridos están activados, la función devuelve true, indicando que la clave podría estar presente (con la posibilidad de un falso positivo).

 bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const override {
   const size_t len = bloom_filter.size();
   // A valid bloom filter must have at least one byte for data and one byte for k.
   if (len < 2) return false;

   const char* array = bloom_filter.data();
   // Calculate total bits, excluding the byte storing k.
   const size_t bits = (len - 1) * 8;

   // Retrieve the number of hash functions (k) used when the filter was created.
   const size_t k = array[len - 1];

   // Handle potential encoding changes or invalid k values.
   if (k > 30) {
     // This range is reserved for future encodings. Assume a match.
     return true;
   }

   // Generate the initial hash and the delta for double-hashing.
   uint32_t h = BloomHash(key);
   const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits

   // Check if all required bits are set for this key.
   for (size_t j = 0; j < k; j++) {
     const uint32_t bitpos = h % bits;
     // If any required bit is not set, the key is definitely not in the set.
     if ((array[bitpos / 8] & (1 << (bitpos % 8))) == 0) {
       return false;
     }
     h += delta; // Move to the next hash value
   }

   // All required bits are set, so the key may match (potential false positive).
   return true;
 }