Un filtro de cociente es una estructura de datos probabilística de uso eficiente del espacio que se utiliza para probar si un elemento es miembro de un conjunto (un filtro de consulta de miembros aproximado , AMQ). Una consulta provocará una respuesta que especifique que el elemento definitivamente no está en el conjunto o que el elemento probablemente esté en el conjunto. El primer resultado es definitivo; es decir , la prueba no genera falsos negativos . Pero con el último resultado hay alguna probabilidad, ε, de que la prueba devuelva "el elemento está en el conjunto" cuando en realidad el elemento no está presente en el conjunto ( es decir , un falso positivo). Existe una compensación entre ε, la tasa de falsos positivos y el tamaño de almacenamiento; aumentar el tamaño de almacenamiento del filtro reduce ε. Otras operaciones de AMQ incluyen "insertar" y "opcionalmente eliminar". Cuantos más elementos se agreguen al conjunto, mayor será la probabilidad de falsos positivos.
Una aplicación típica para filtros de cociente y otros filtros AMQ es servir como proxy para las claves en una base de datos en disco. A medida que se agregan o eliminan claves de la base de datos, el filtro se actualiza para reflejar esto. Cualquier búsqueda consultará primero el filtro de cociente rápido, luego buscará en la base de datos (presumiblemente mucho más lenta) solo si el filtro de cociente informó la presencia de la clave. Si el filtro devuelve ausencia, se sabe que la clave no está en la base de datos sin que se hayan realizado accesos al disco.
Un filtro de cociente tiene las operaciones AMQ habituales de inserción y consulta. Además, también se puede fusionar y redimensionar sin tener que volver a aplicar el hash a las claves originales (evitando así la necesidad de acceder a esas claves desde el almacenamiento secundario). Esta propiedad beneficia a ciertos tipos de árboles de combinación estructurados por registros .
Historia
La tabla hash compacta subyacente a un filtro de cociente fue descrita por Cleary en 1984. [1] La primera referencia conocida al uso de la estructura como un filtro AMQ es por Pagh et. Alabama. en 2005. [2] En 2009, Dillinger y Manolios optimizaron los metadatos de la estructura, agregaron alojamiento en el lugar de más elementos y aplicaron la estructura a la verificación del modelo de estado explícito . [3] En 2011, Bender et al. escribió el nombre "filtro de cociente", describió varias variantes con diferentes compensaciones de codificación de metadatos, mostró cómo fusionar y cambiar el tamaño de los filtros de cociente, presentó una versión optimizada para escritura del filtro de cociente para su uso en disco y aplicó la estructura al almacenamiento de la base de datos problemas. [4] [5] En 2017, Pandey et al. describió una versión que usa instrucciones de manipulación de bits de hardware para mejorar el rendimiento, admite actualizaciones simultáneas y agrega soporte para asociar un contador de tamaño variable a cada elemento. [6]
Descripción del algoritmo
El filtro de cociente se basa en una especie de tabla hash en la que las entradas contienen solo una parte de la clave más algunos bits de metadatos adicionales. Estos bits se utilizan para tratar el caso en el que distintas claves hacen hash en la misma entrada de la tabla. Por el contrario, otros tipos de tablas hash que se ocupan de tales colisiones mediante la vinculación a áreas de desbordamiento no son compactas porque la sobrecarga debida a la vinculación puede exceder el almacenamiento utilizado para almacenar la clave. [1] En un filtro de cociente, una función hash genera una huella digital de p bits. Los r bits menos significativos se denominan resto, mientras que los q = p - r bits más significativos se denominan cociente, de ahí el nombre cociente (acuñado por Knuth . [7] ) La tabla hash tiene 2 q ranuras.
Por alguna clave d que hashes a la huella digital d H , deja que su cociente de ser d Q y el resto sea d R . QF intentará almacenar el resto en la ranura d Q , que se conoce como ranura canónica . Sin embargo, es posible que la ranura canónica ya esté ocupada porque varias teclas pueden generar la misma huella digital (una colisión fuerte) o porque incluso cuando las huellas digitales de las teclas son distintas, pueden tener el mismo cociente (una colisión suave) . Si el espacio canónico está ocupado, el resto se almacena en algún espacio a la derecha.
Como se describe a continuación, el algoritmo de inserción asegura que todas las huellas dactilares que tengan el mismo cociente se almacenen en ranuras contiguas. Tal conjunto de huellas dactilares se define como una carrera . [4] Tenga en cuenta que la primera huella digital de una ejecución podría no ocupar su espacio canónico si la ejecución ha sido forzada a la derecha por alguna ejecución hacia la izquierda.
Sin embargo, una ejecución cuya primera huella digital ocupa su ranura canónica indica el inicio de un clúster . [4] La ejecución inicial y todas las ejecuciones posteriores comprenden el clúster, que termina en una ranura desocupada o en el inicio de otro clúster.
Los tres bits adicionales se utilizan para reconstruir la huella digital de una ranura. Tienen la siguiente función:
- esta ocupado
- se establece cuando una ranura es la ranura canónica para alguna clave almacenada (en algún lugar) en el filtro (pero no necesariamente en esta ranura).
- is_continuation
- se establece cuando una ranura está ocupada pero no por el primer resto de una ejecución.
- is_shifted
- se establece cuando el resto de una ranura no está en su ranura canónica.
Las diversas combinaciones tienen el siguiente significado:
significado | |||
---|---|---|---|
0 | 0 | 0 | Ranura vacía |
0 | 0 | 1 | La ranura contiene el inicio de la ejecución que se ha cambiado de su ranura canónica. |
0 | 1 | 0 | no utilizado. |
0 | 1 | 1 | La ranura mantiene la continuación de la ejecución que se ha cambiado de su ranura canónica. |
1 | 0 | 0 | La ranura contiene el inicio de la ejecución que se encuentra en su ranura canónica. Este es también el comienzo del clúster. |
1 | 0 | 1 | La ranura contiene el inicio de la ejecución que se ha cambiado de su ranura canónica. También existe la carrera para la que esta es la ranura canónica, pero se desplaza a la derecha. |
1 | 1 | 0 | no utilizado. |
1 | 1 | 1 | La ranura mantiene la continuación de la ejecución que se ha cambiado de su ranura canónica. También existe la carrera para la que esta es la ranura canónica, pero se desplaza a la derecha. |
Buscar
Podemos probar si un filtro de cociente contiene alguna clave, d, de la siguiente manera. [4]
Aplicamos hash a la clave para producir su huella digital, d H , que luego dividimos en sus q bits de orden superior, d Q , que comprenden su cociente, y sus r bits de orden inferior, d R , que comprenden el resto. La ranura d Q es la ranura canónica de la llave. Esa ranura está vacía si sus tres bits de metadatos son falsos. En ese caso, el filtro no contiene la clave.
Si la ranura canónica está ocupada, debemos ubicar la ejecución del cociente. El conjunto de ranuras que contienen restos pertenecientes al mismo cociente se almacenan de forma contigua y estos comprenden la ejecución del cociente. La primera ranura de la carrera podría ser la ranura canónica, pero también es posible que toda la carrera haya sido desplazada hacia la derecha por la invasión desde la izquierda de otra carrera.
Para ubicar la ejecución del cociente, primero debemos ubicar el inicio del clúster. El clúster consta de un conjunto contiguo de ejecuciones. Comenzando con la ranura canónica del cociente, podemos escanear a la izquierda para ubicar el inicio del clúster, luego escanear a la derecha para ubicar la ejecución del cociente.
Escaneamos a la izquierda en busca de una ranura con is_shifted es falso. Esto indica el inicio del clúster. Luego, escaneamos a la derecha manteniendo un recuento continuo del número de ejecuciones que debemos omitir. Cada espacio a la izquierda del espacio canónico que tiene is_occupied establecido indica que se omitirá otra ejecución, por lo que incrementamos la cuenta corriente. Cada ranura que tiene is_continuation clear indica el comienzo de otra ejecución, por lo tanto, el final de la ejecución anterior, por lo que disminuimos el recuento continuo . Cuando la cuenta corriente llega a cero, estamos escaneando la ejecución del cociente. Podemos comparar el resto en cada ranura en la carrera con D R . Si se encuentra, informamos que la clave está (probablemente) en el filtro; de lo contrario, informamos que la clave definitivamente no está en el filtro.
Ejemplo de búsqueda
Tomemos, por ejemplo, la búsqueda del elemento e . Vea el estado 3 en la figura. Calcularíamos hash (e) , lo dividiríamos en su resto, e R y su cociente e Q , que es 4. Al escanear a la izquierda de la ranura 4 encontramos tres ranuras is_occupied , en los índices 4, 2 y 1, indicando e Q 's ejecutar es la tercera ejecución en el clúster. El escaneo se detiene en la ranura 1, que detectamos como el inicio del clúster porque no está vacío ni desplazado. Ahora debemos escanear directamente a la tercera ejecución. El inicio de una ejecución se indica si is_continuation es falso. La primera ejecución se encuentra en el índice 1, la segunda en el 4 y la tercera en el 5. Comparamos el resto retenido en cada espacio en la ejecución que comienza en el índice 5. Solo hay un espacio en esa ejecución pero, en nuestro ejemplo, su resto es igual a e R , lo que indica que e es de hecho un miembro del filtro, con probabilidad 1 - ε.
Inserción
La inserción sigue una ruta similar a la de búsqueda hasta que determinamos que la clave definitivamente no está en el filtro. [4] En ese punto, insertamos el resto en una ranura en la ejecución actual, una ranura elegida para mantener la ejecución en orden ordenado. Desplazamos hacia adelante los restos en cualquier ranura del clúster en o después de la ranura elegida y actualizamos los bits de la ranura.
- Cambiar el resto de una ranura no afecta el bit is_occupied de la ranura porque pertenece a la ranura, no al resto contenido en la ranura.
- Si insertamos un resto al comienzo de una ejecución existente, el resto anterior se desplaza y se convierte en una ranura de continuación, por lo que establecemos su bit is_continuation .
- Establecemos el bit is_shifted de cualquier resto que cambiemos.
Ejemplo de inserción
La figura muestra un filtro de cociente que pasa por una serie de estados a medida que se agregan elementos. En el estado 1 se han añadido tres elementos. El espacio que ocupa cada uno forma un tramo de un espacio que también es un grupo distinto.
En el estado 2 elementos c de y d se han añadido. El elemento c tiene un cociente de 1, lo mismo que b . Suponemos que b R
En el estado 3 elemento de una ha sido añadido. Su cociente es 1. Suponemos que a R R, por lo que los restos de las ranuras 1 a 4 deben desplazarse. La ranura 2 recibe b R y se marca como una continuación y se cambia . La ranura 5 recibe e R y se marca como desplazada . Las corridas para los cocientes 1, 2 y 4 ahora comprenden un grupo, y la presencia de esas tres corridas en el grupo se indica al tener las ranuras 1, 2 y 4 marcadas como ocupadas .
Costo de operación
Longitud del racimo
Bender [4] sostiene que los clústeres son pequeños. Esto es importante porque las búsquedas y las inserciones requieren ubicar el inicio y la longitud de un clúster completo. Si la función hash genera huellas dactilares distribuidas uniformemente, entonces la longitud de la mayoría de las ejecuciones es O (1) y es muy probable que todas las ejecuciones tengan una longitud O (log m ) donde m es el número de ranuras en la tabla. [4]
Probabilidad de falsos positivos
Bender [4] calcula la probabilidad de un falso positivo (es decir, cuando el hash de dos claves da como resultado la misma huella dactilar) en términos del tamaño restante de la tabla hash y el factor de carga. Recuerde que una huella dactilar de p bit se divide en un cociente de q bit, que determina el tamaño de la tabla de m = 2 q ranuras y un resto de bit r . El factor de cargaes la proporción de ranuras ocupadas n respecto al total de ranuras m :. Entonces, para una buena función hash, es aproximadamente la probabilidad de una colisión fuerte.
Espacio / rendimiento
La versión de Pandey del filtro de cociente requiere menos espacio que un filtro Bloom comparable cuando la tasa de falsos positivos objetivo es menor que 1/64. [6]
Solicitud
Los filtros de cociente son AMQ y, como tales, brindan muchos de los mismos beneficios que los filtros Bloom . Una base de datos grande, como Webtable [8], puede estar compuesta por subtablas más pequeñas, cada una de las cuales tiene un filtro asociado. Cada consulta se distribuye simultáneamente a todas las subtablas. Si una subtabla no contiene el elemento solicitado, su filtro puede completar rápidamente la solicitud sin incurrir en E / S.
Los filtros de cociente ofrecen dos beneficios en algunas aplicaciones.
- Se pueden combinar dos filtros de cociente de manera eficiente sin afectar sus tasas de falsos positivos. Esto no es posible con los filtros Bloom.
- Algunos duplicados se pueden tolerar de manera eficiente y se pueden eliminar.
El espacio utilizado por los filtros de cociente es comparable al de los filtros Bloom. Sin embargo, los filtros de cociente se pueden fusionar de manera eficiente en la memoria sin tener que volver a insertar las claves originales.
Esto es particularmente importante en algunos sistemas de almacenamiento estructurados por registros que utilizan el árbol de fusión estructurado por registros o el árbol LSM. [9] El árbol LSM es en realidad una colección de árboles, pero que se trata como un único almacén de valores-clave. Una variación del árbol LSM es el árbol de combinación de matrices ordenadas o SAMT. [10] En esta variación, los árboles componentes de un SAMT se denominan árboles Wanna-B . Cada árbol Wanna- B tiene un filtro de cociente asociado. Una consulta en el SAMT se dirige únicamente a determinados árboles Wanna- B, como lo demuestran sus filtros de cociente.
El sistema de almacenamiento en su funcionamiento normal compacta los árboles Wanna- B de SAMT, fusionando los árboles Wanna- B más pequeños en otros más grandes y fusionando sus filtros de cociente. Una propiedad esencial de los filtros de cociente es que se pueden fusionar de manera eficiente sin tener que volver a insertar las claves originales. Dado que para conjuntos de datos grandes, los árboles Wanna- B pueden no estar en la memoria, acceder a ellos para recuperar las claves originales implicaría muchas E / S.
Por construcción, los valores en un filtro de cociente se almacenan en orden. Cada ejecución está asociada con un valor de cociente específico, que proporciona la porción más significativa de la huella dactilar, las ejecuciones se almacenan en orden y cada ranura en la ejecución proporciona la porción menos significativa de la huella dactilar.
Entonces, trabajando de izquierda a derecha, se pueden reconstruir todas las huellas digitales y la lista resultante de números enteros estará ordenada. Combinar dos filtros de cociente es entonces una simple cuestión de convertir cada filtro de cociente en una lista de este tipo, fusionar las dos listas y usarlo para completar un nuevo filtro de cociente más grande. Del mismo modo, podemos reducir a la mitad o duplicar el tamaño de un filtro de cociente sin repetir las claves, ya que las huellas digitales se pueden volver a calcular utilizando solo los cocientes y los residuos. [4]
Ver también
Notas
- ↑ a b Cleary, John G. (septiembre de 1984). "Tablas hash compactas mediante sondeo lineal bidireccional" . Transacciones IEEE en computadoras . 33 (9): 828–834. doi : 10.1109 / TC.1984.1676499 . S2CID 195908955 .
- ^ Pagh, Anna; Pagh, Rasmus ; Rao, S. Srinivasa (2005). "Un reemplazo óptimo del filtro Bloom" (PDF) . Actas del Decimosexto Simposio Anual ACM-SIAM sobre Algoritmos Discretos . págs. 823–829.
- ^ Dillinger, Peter C .; Manolios, Panagiotis (2009). "Almacenamiento estatal rápido y de uso general" . 16º Taller Internacional SPIN sobre Software de Verificación de Modelos . Springer, Lecture Notes in Computer Science 5578.
- ^ a b c d e f g h yo Bender, Michael A .; Farach-Colton, Martin ; Johnson, Rob; Kuszmaul, Bradley C .; Medjedovic, Dzejla; Montes, Pablo; Shetty, Pradeep; Spillane, Richard P .; Zadok, Erez (junio de 2011). "Don't thrash: cómo almacenar en caché su hash en flash" (PDF) . Actas de la 3ra conferencia de USENIX sobre temas candentes en almacenamiento y sistemas de archivos (HotStorage'11) . Consultado el 21 de julio de 2012 .
- ^ Bender, Michael A .; Farach-Colton, Martin ; Johnson, Rob; Kraner, Russell; Kuszmaul, Bradley C .; Medjedovic, Dzejla; Montes, Pablo; Shetty, Pradeep; Spillane, Richard P .; Zadok, Erez (27 a 31 de agosto de 2012). "Don't thrash: cómo almacenar en caché su hash en flash" (PDF) . Actas de la Dotación VLDB . 5 (11): 1627–1637. arXiv : 1208.0290 . Código bibliográfico : 2012arXiv1208.0290B . doi : 10.14778 / 2350229.2350275 . S2CID 47180056 .
- ^ a b Pandey, Prashant; Bender, Michael A .; Johnson, Rob; Patro, Rob (mayo de 2017). "Un filtro de conteo de uso general: hacer que cada bit cuente" . Actas de la Conferencia Internacional ACM 2017 sobre Gestión de Datos (SIGMOD '17) . Consultado el 2 de diciembre de 2020 .
- ^ Knuth, Donald (1973). El arte de la programación informática: búsqueda y clasificación, volumen 3 . Sección 6.4, ejercicio 13: Addison Wesley.Mantenimiento de CS1: ubicación ( enlace )
- ^ Chang, Fay; et al. (2006). "Bigtable: un sistema de almacenamiento distribuido para datos estructurados" (PDF) . OSDI '06: Actas del 7mo Simposio de USENIX sobre Diseño e Implementación de Sistemas Operativos : 15 . Consultado el 21 de julio de 2012 .
- ^ O'Neil, Patrick; et al. (1996). "El árbol de fusión estructurado por registros (árbol LSM)" . Acta Informatica . 33 (4): 351–385. doi : 10.1007 / s002360050048 . S2CID 12627452 .
- ^ Spillane, Richard (mayo de 2012). "Gestión de transacciones de aplicaciones y sistemas eficiente, escalable y versátil para capas de almacenamiento directo" (PDF) . Consultado el 21 de julio de 2012 . Cite journal requiere
|journal=
( ayuda )
enlaces externos
- Medios relacionados con el filtro de cociente en Wikimedia Commons