Un hash rodante (también conocido como hash recursivo o suma de comprobación rodante) es una función hash en la que la entrada se hash en una ventana que se mueve a través de la entrada.
Algunas funciones de hash permiten que un hash rodante se calcule muy rápidamente; el nuevo valor de hash se calcula rápidamente dado solo el valor de hash anterior, el valor anterior eliminado de la ventana y el nuevo valor agregado a la ventana, similar a la forma en que un La función de media móvil se puede calcular mucho más rápidamente que otros filtros de paso bajo.
Una de las aplicaciones principales es el algoritmo de búsqueda de cadenas de Rabin-Karp , que utiliza el hash rodante que se describe a continuación. Otra aplicación popular es el programa rsync , que utiliza una suma de comprobación basada en el adler-32 de Mark Adler como hash móvil. El sistema de archivos de red de ancho de banda bajo (LBFS) utiliza una huella dactilar de Rabin como hash móvil. FastCDC (Fast Content-Defined Chunking) utiliza una huella digital Gear de cálculo eficiente como su hash rodante.
En el mejor de los casos, los valores hash rodantes son independientes por pares [1] o muy universales . No pueden ser independientes en tres sentidos , por ejemplo.
Hash rodante polinomial
El algoritmo de búsqueda de cadenas de Rabin-Karp a menudo se explica mediante una función hash rodante que solo usa multiplicaciones y sumas:
- ,
dónde es una constante, y son los caracteres de entrada (pero esta función no es una huella dactilar de Rabin , ver más abajo).
Para evitar manipular enormes valores, todas las matemáticas se hacen módulo . La elección de y es fundamental para obtener un buen hash; ver generador de congruencia lineal para más discusión.
Eliminar y agregar caracteres simplemente implica sumar o restar el primer o último término. Mover todos los caracteres en una posición a la izquierda requiere multiplicar la suma completa por . Mover todos los caracteres en una posición a la derecha requiere dividir la suma completa por . Tenga en cuenta que en módulo aritmético,se puede elegir para tener un inverso multiplicativo por el cual se puede multiplicar para obtener el resultado de la división sin realizar una división.
Huella dactilar de Rabin
La huella de Rabin es otro hash, que también interpreta la entrada como un polinomio, pero sobre el campo de Galois GF (2) . En lugar de ver la entrada como un polinomio de bytes, se ve como un polinomio de bits y toda la aritmética se realiza en GF (2) (de manera similar a CRC32 ). El hash es el resultado de la división de ese polinomio por un polinomio irreducible sobre GF (2). Es posible actualizar una huella digital de Rabin utilizando solo el byte de entrada y el de salida, convirtiéndola efectivamente en un hash continuo.
Debido a que comparte el mismo autor que el algoritmo de búsqueda de cadenas de Rabin-Karp, que a menudo se explica con otro hash rodante más simple, y debido a que este hash rodante más simple también es un polinomio, ambos hash rodantes a menudo se confunden entre sí. El software de respaldo restic usa una huella digital Rabin para dividir archivos, con un tamaño de blob que varía entre 512 bytes y 8MiB. [2]
Polinomio cíclico
El hash por polinomio cíclico [3] —a veces llamado Buzhash— también es simple, pero tiene la ventaja de evitar multiplicaciones, utilizando cambios de barril en su lugar. Es una forma de hash de tabulación : supone que hay alguna función hash de caracteres a enteros en el intervalo . Esta función hash podría ser simplemente una matriz o una tabla hash que mapee caracteres a números enteros aleatorios. Deja que la funciónser una rotación binaria cíclica (o desplazamiento circular ): gira los bits en 1 a la izquierda, empujando el último bit en la primera posición. P.ej,. Dejarser el exclusivo bit a bit o . Los valores hash se definen como
donde las multiplicaciones por potencias de dos se pueden implementar mediante cambios binarios. El resultado es un número en.
El cálculo de los valores hash de forma continua se realiza de la siguiente manera. Dejarser el valor hash anterior. Girar una vez: . Si es el carácter que se eliminará, gírelo veces: . Entonces simplemente configure
dónde es el nuevo personaje.
El hash por polinomios cíclicos es fuertemente universal o independiente por pares: simplemente mantenga el primero bits. Es decir, toma el resultado y descartar cualquier bits consecutivos. [1] En la práctica, esto se puede lograr mediante una división entera.
Corte basado en contenido usando un hash rodante
Uno de los casos de uso interesantes de la función hash rodante es que puede crear fragmentos dinámicos basados en contenido de una secuencia o archivo. Esto es especialmente útil cuando se requiere enviar solo los fragmentos modificados de un archivo grande a través de una red y una simple adición de un byte al principio del archivo haría que todas las ventanas de tamaño fijo se actualicen, mientras que en realidad, solo la primera "chunk" ha sido modificado.
El enfoque más simple para calcular los fragmentos dinámicos es calcular el hash rodante y si coincide con un patrón (como los N bits inferiores son todos ceros), entonces es un límite de fragmento. Este enfoque asegurará que cualquier cambio en el archivo solo afectará su fragmento actual y posiblemente el siguiente, pero nada más.
Cuando se conocen los límites, los fragmentos deben compararse por sus valores hash para detectar cuál se modificó y debe transferirse a través de la red. [4] El software de respaldo Attic usa un algoritmo Buzhash con un rango de tamaño de fragmentos personalizable para dividir flujos de archivos. [5]
Corte basado en contenido usando suma móvil
Varios programas, incluidos gzip (con la --rsyncable
opción) y rsyncrypto, realizan segmentaciones basadas en el contenido en función de esta suma móvil específica (no ponderada): [6]
dónde
- es la suma de 8196 bytes consecutivos que terminan en byte (requiere 21 bits de almacenamiento),
- es byte del archivo,
- es un "valor hash" que consta de los 12 bits inferiores de .
Cambiar la ventana un byte simplemente implica agregar el nuevo carácter a la suma y restar el carácter más antiguo (que ya no está en la ventana) de la suma.
Para cada dónde , estos programas cortan el archivo entre y . Este enfoque garantizará que cualquier cambio en el archivo solo afectará a su fragmento actual y posiblemente al siguiente, pero a ningún otro fragmento.
Huella digital de engranajes y algoritmo de fragmentación basado en contenido FastCDC
El algoritmo de fragmentación definida por contenido (CDC) necesita calcular el valor hash de un flujo de datos byte por byte y dividir el flujo de datos en fragmentos cuando el valor hash cumple con un valor predefinido. Sin embargo, comparar una cadena byte a byte introducirá una gran sobrecarga de cálculo. FastCDC [7] propone un nuevo y eficiente enfoque de fragmentación definida por contenido. Utiliza un algoritmo de hash Gear de avance rápido, [8] omitiendo la longitud mínima, normalizando la distribución del tamaño del fragmento y, por último, pero no menos importante, rodando dos bytes cada vez para acelerar el algoritmo CDC, que puede lograr un rendimiento 10 veces mayor. que el enfoque CDC basado en Rabin. [9]
El pseudocódigo de la versión básica se proporciona de la siguiente manera:
algoritmo Entrada FastCDC : búfer de datos src , longitud de datos n , salida: punto de corte i MinSize ← 2KB // el tamaño mínimo del fragmento dividido es 2 KB MaxSize ← 64KB // el tamaño máximo del fragmento dividido es 64 KB fp ← 0 i ← MinSize Mask ← 0x0000d93003530000LL // el tamaño del búfer es menor que el tamaño mínimo del fragmento si n ≤ MinSize entonces devuelve n si n ≥ MaxSize entonces n ← MaxSize while i < n do fp ← ( fp << 1) + Gear [ src [ i ]] if ! ( fp & Mask ) luego regresa i regreso yo
Donde Gear array es una matriz hash precalculada. Aquí, FastCDC utiliza el algoritmo de hash de engranajes que puede calcular los resultados de hash rodante rápidamente y mantener la distribución uniforme de los resultados de hash como Rabin. En comparación con el algoritmo hash tradicional de Rabin, alcanza una velocidad mucho más rápida. Los experimentos sugieren que puede generar casi la misma distribución de tamaño de fragmento en un tiempo mucho más corto (aproximadamente 1/10 de fragmentación basada en rabin [9] ) al segmentar el flujo de datos.
Complejidad computacional
Todas las funciones de hash rodante son lineales en el número de caracteres, pero su complejidad con respecto a la longitud de la ventana () varía. El hash rodante de Rabin-Karp requiere la multiplicación de dos-números de bits, la multiplicación de enteros está en. [10] El hash de ngrams mediante polinomios cíclicos se puede realizar en tiempo lineal. [1]
Software
- rollinghashcpp es una implementación de software libre en C ++ de varias funciones hash rodantes
- rollinghashjava es una implementación Java con licencia de Apache de funciones hash rodantes
Ver también
enlaces externos
Notas al pie
- ^ a b c Daniel Lemire, Owen Kaser: El hash recursivo de n -gramas es independiente por pares, en el mejor de los casos, Computer Speech & Language 24 (4), páginas 698–710, 2010. arXiv: 0705.4676 .
- ^ "Referencias - documentación restic 0.9.0" . restic.readthedocs.io . Consultado el 24 de mayo de 2018 .
- ^ Jonathan D. Cohen, Funciones de hash recursivas para n -Grams, ACM Trans. Inf. Syst. 15 (3), 1997.
- ^ Horvath, Adam (24 de octubre de 2012). "Rabin Karp rolling hash - fragmentos de tamaño dinámico basados en contenido hash" .
- ^ "Estructuras de datos y formatos de archivo - Borg - Documentación de Deduplicating Archiver 1.1.5" . borgbackup.readthedocs.io . Consultado el 24 de mayo de 2018 .
- ^ "Algoritmo Rsyncrypto" .
- ^ Xia, Wen; Zhou, Yukun; Jiang, Hong; Feng, Dan; Hua, Yu; Hu, Yuchong; Liu, Qing; Zhang, Yucheng. "FastCDC: un enfoque de fragmentación definido por contenido rápido y eficiente para la deduplicación de datos" . USENIX . Consultado el 24 de julio de 2020 .
- ^ Xia, Wen; Jiang, Hong; Feng, Dan; Tian, Lei; Fu, Min; Zhou, Yukun (2014). "Ddelta: un enfoque de compresión delta rápida inspirado en la deduplicación". Evaluación de desempeño . 79 : 258-272. doi : 10.1016 / j.peva.2014.07.016 . ISSN 0166-5316 .
- ^ a b Xia, Wen; Zou, Xiangyu; Jiang, Hong; Zhou, Yukun; Liu, Chuanyi; Feng, Dan; Hua, Yu; Hu, Yuchong; Zhang, Yucheng (16 de junio de 2020). "El diseño de fragmentación rápida definida por contenido para sistemas de almacenamiento basados en deduplicación de datos" . Transacciones IEEE en sistemas paralelos y distribuidos . 31 (9): 2017-2031. doi : 10.1109 / TPDS.2020.2984632 . S2CID 215817722 . Consultado el 22 de julio de 2020 .
- ^ M. Fürer, Multiplicación de enteros más rápida, en: STOC '07, 2007, págs. 57–66.