En informática , el hash consistente [1] [2] es un tipo especial de técnica de hash tal que cuando se cambia el tamaño de una tabla hash , solo es necesario reasignar las claves en promedio, donde es el número de claves y el número de ranuras. Por el contrario, en la mayoría de las tablas hash tradicionales, un cambio en el número de ranuras de la matriz hace que casi todas las claves se reasignen porque la asignación entre las claves y las ranuras está definida por una operación modular .
El hash consistente distribuye uniformemente las claves de caché entre los fragmentos , incluso si algunos de los fragmentos fallan o dejan de estar disponibles. [3]
El término "hashing consistente" fue introducido por David Karger et al. en el MIT para su uso en almacenamiento en caché distribuido , particularmente para la web . [4] Este artículo académico de 1997 en el Simposio sobre Teoría de la Computación introdujo el término "hashing consistente" como una forma de distribuir solicitudes entre una población cambiante de servidores web. [5] Cada ranura está representada por un servidor en un sistema o clúster distribuido. La adición de un servidor y la eliminación de un servidor (durante la escalabilidad o una interrupción) solo requiere que los elementos se vuelvan a barajar cuando cambia el número de ranuras (es decir, servidores). Los autores mencionan el hash lineal y su capacidad para manejar la adición y eliminación secuencial de servidores, mientras que el hash consistente permite agregar y eliminar servidores en un orden arbitrario. [1] Posteriormente, el documento fue reutilizado para abordar el desafío técnico de realizar un seguimiento de un archivo en redes peer-to-peer, como una tabla hash distribuida . [6] [7]
Teradata utilizó esta técnica en su base de datos distribuida, lanzada en 1986, aunque no utilizaron este término. Teradata todavía utiliza el concepto de tabla hash para cumplir exactamente este propósito. Akamai Technologies fue fundada en 1998 por los científicos Daniel Lewin y F. Thomson Leighton (coautores del artículo que acuñó "hashing consistente"). En la red de entrega de contenido de Akamai, [8] se utiliza hash consistente para equilibrar la carga dentro de un grupo de servidores, mientras que se utiliza un algoritmo de matrimonio estable para equilibrar la carga entre los grupos. [2]
También se ha utilizado hash consistente para reducir el impacto de fallas parciales del sistema en grandes aplicaciones web para proporcionar un almacenamiento en caché sólido sin incurrir en las consecuencias de una falla en todo el sistema. [9] El hash consistente también es la piedra angular de las tablas hash distribuidas (DHT), que emplean valores hash para dividir un espacio de claves en un conjunto distribuido de nodos y luego construyen una red superpuesta de nodos conectados que proporciona una recuperación eficiente de nodos por clave.
El hash de encuentro , diseñado en 1996, es una técnica más simple y general [ cita requerida ] . Logra los objetivos de un hash consistente utilizando el algoritmo de peso aleatorio más alto (HRW) muy diferente.
En el problema de equilibrio de carga , por ejemplo, cuando se debe asignar un BLOB a uno de los servidores de un cluster , se podría usar una función hash estándar de tal manera que calculemos el valor hash para ese BLOB, asumiendo el valor resultante. del hash es , realizamos una operación modular con la cantidad de servidores ( en este caso) para determinar el servidor en el que podemos colocar el BLOB: ; por lo tanto, el BLOB se colocará en el servidor sucesor en este caso. Sin embargo, cuando se agrega o elimina un servidor durante una interrupción o escalamiento (cuando cambia), todos los BLOB en cada servidor deben reasignarse y moverse debido al refrito , pero esta operación es costosa.
El hash coherente se diseñó para evitar el problema de tener que reasignar cada BLOB cuando se agrega o elimina un servidor en todo el clúster. La idea central es utilizar una función hash que asigne tanto el BLOB como los servidores a un círculo unitario, generalmente radianes. Por ejemplo (donde está el hash de un BLOB o el identificador del servidor, como la dirección IP o UUID ). Luego, cada BLOB se asigna al siguiente servidor que aparece en el círculo en el sentido de las agujas del reloj. Por lo general, el algoritmo de búsqueda binaria o la búsqueda lineal se utilizan para encontrar un "lugar" o servidor para colocar ese BLOB en particular o complejidades respectivamente; y en cada iteración, que ocurre en el sentido de las agujas del reloj, se realiza una operación (donde está el valor del servidor dentro del cluster) para encontrar el servidor donde colocar el BLOB. Esto proporciona una distribución uniforme de BLOB a los servidores. Pero, lo que es más importante, si un servidor falla y se elimina del círculo, solo los BLOB que se asignaron al servidor fallido deben reasignarse al siguiente servidor en el sentido de las agujas del reloj. Del mismo modo, si se agrega un nuevo servidor, se agrega al círculo unitario y solo es necesario reasignar los BLOB asignados a ese servidor.
Es importante destacar que cuando se agrega o elimina un servidor, la gran mayoría de los BLOB mantienen sus asignaciones de servidor anteriores y la adición de un servidor solo provoca que una fracción de los BLOB se reubiquen. Aunque el proceso de mover BLOB entre servidores de caché en el clúster depende del contexto, comúnmente, el servidor de caché recién agregado identifica a su "sucesor" y mueve todos los BLOB, cuyo mapeo pertenece a este servidor (es decir, cuyo valor hash es menor que ese del nuevo servidor), desde el mismo. Sin embargo, en el caso de los cachés de páginas web , en la mayoría de las implementaciones no es necesario mover ni copiar, suponiendo que el BLOB almacenado en caché sea lo suficientemente pequeño. Cuando una solicitud llega a un servidor de caché recién agregado, se produce una pérdida de caché y se realiza una solicitud al servidor web real y el BLOB se almacena en caché localmente para futuras solicitudes. Los BLOB redundantes en los servidores de caché utilizados anteriormente se eliminarían según las políticas de desalojo de caché . [10]
Sean y las funciones hash utilizadas para el BLOB y el identificador único del servidor, respectivamente. En la práctica, se utiliza un árbol de búsqueda binaria (BST) para mantener dinámicamente dentro de un clúster o hashring, y para encontrar el sucesor o mínimo dentro del BST, se utiliza el recorrido del árbol .
Para evitar la asimetría de múltiples nodos dentro del radianes, que ocurre debido a la falta de distribución uniforme de los servidores dentro del clúster, se utilizan múltiples etiquetas. Esas etiquetas duplicadas se denominan "nodos virtuales", es decir, etiquetas múltiples que apuntan a una única etiqueta o servidor "real" dentro del clúster. La cantidad de nodos virtuales o etiquetas duplicadas utilizadas para un servidor particular dentro de un clúster se denomina "peso" de ese servidor en particular. [14]
Se necesitan varias extensiones de la técnica básica para utilizar eficazmente el hash consistente para el equilibrio de carga en la práctica. En el esquema básico anterior, si un servidor falla, todos sus BLOB se reasignan al siguiente servidor en el sentido de las agujas del reloj, lo que potencialmente duplica la carga de ese servidor. Puede que esto no sea deseable. Para garantizar una redistribución más uniforme de los BLOB en caso de falla del servidor, cada servidor se puede dividir en varias ubicaciones en el círculo unitario. Cuando un servidor falla, los BLOB asignados a cada una de sus réplicas en el círculo unitario se reasignarán a un servidor diferente en el sentido de las agujas del reloj, redistribuyendo así los BLOB de manera más uniforme. Otra extensión se refiere a una situación en la que un único BLOB se "calienta" y se accede a él un gran número de veces y tendrá que alojarse en varios servidores. En esta situación, el BLOB se puede asignar a varios servidores contiguos atravesando el círculo unitario en el sentido de las agujas del reloj. Una consideración práctica más compleja surge cuando dos BLOB se agrupan cerca uno del otro en el círculo unitario y ambos se "calientan" al mismo tiempo. En este caso, ambos BLOB utilizarán el mismo conjunto de servidores contiguos en el círculo unitario. Esta situación se puede mejorar si cada BLOB elige una función hash diferente para asignar servidores al círculo unitario. [2]
El hash de encuentro , diseñado en 1996, es una técnica más simple y general, y permite un acuerdo completamente distribuido sobre un conjunto de opciones dentro de un posible conjunto de opciones. De hecho, se puede demostrar que el hash consistente es un caso especial de hash de encuentro. Debido a su simplicidad y generalidad, el hash de encuentro ahora se utiliza en lugar del hash consistente en muchas aplicaciones.
Si los valores clave siempre aumentan de forma monótona , un enfoque alternativo que utilice una tabla hash con claves monótonas puede ser más adecuado que el hash consistente. [ cita necesaria ]
Hay un costo promedio para la redistribución de claves y la complejidad para un hash consistente proviene del hecho de que se requiere una búsqueda binaria entre los ángulos de los nodos para encontrar el siguiente nodo en el anillo. [ cita necesaria ]
Los ejemplos conocidos de uso constante de hash incluyen:
El hash consistente es una técnica que evita estos problemas y la usamos para calcular la ubicación de cada clave en el clúster.