Hashing consistente

En ciencias de la computación , el hash consistente ^{[ 1 ] [ 2 ]} es un tipo especial de técnica de hash tal que cuando se redimensiona una tabla hash , solo${\displaystyle n/m}$Las teclas deben reasignarse en promedio donde${\displaystyle n}$es el número de llaves y${\displaystyle m}$es el número de ranuras. 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 ]} En contraste, 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 se define mediante una operación modular .

Las redes de distribución de contenido utilizan el hash consistente porque resulta útil para distribuir las solicitudes de contenido desde una población rotativa de servidores web. Tim Berners-Lee atribuye a los algoritmos de hash consistente, y a Daniel Lewin como su inventor, la solución al problema del slashdotting que afectó a la World Wide Web en la década de 1990. ^{[ 4 ]}

El término "hashing consistente" fue introducido por David Karger et al. en el MIT para su uso en el almacenamiento en caché distribuido , particularmente para la web . ^{[ 5 ]} 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 las solicitudes entre una población cambiante de servidores web. ^{[ 6 ]} Cada ranura está representada por un servidor en un sistema distribuido o clúster. La adición de un servidor y la eliminación de un servidor (durante la escalabilidad o la interrupción) requiere solo${\displaystyle num_keys/num_slots}$elementos que se reorganizan 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 ]} El artículo fue posteriormente 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 . ^{[ 7 ] [ 8 ]}

Teradata utilizó esta técnica en su base de datos distribuida , lanzada en 1986, aunque no empleó este término. Teradata sigue utilizando el concepto de tabla hash para cumplir precisamente con 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ñó el término "hashing consistente"). En la red de entrega de contenido de Akamai, ^{[ 9 ]} el hash consistente se utiliza para equilibrar la carga dentro de un clúster de servidores, mientras que un algoritmo de matrimonio estable se utiliza para equilibrar la carga entre clústeres. ^{[ 2 ]}

El hash consistente también se ha utilizado para reducir el impacto de fallas parciales del sistema en grandes aplicaciones web para proporcionar un almacenamiento en caché robusto sin incurrir en las consecuencias de una falla en todo el sistema. ^{[ 10 ]} El hash consistente también es la piedra angular de las tablas hash distribuidas (DHT), que emplean valores hash para particionar 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 . Logra los objetivos de un hash consistente utilizando el algoritmo de peso aleatorio más alto (HRW), que es muy diferente.

En el problema del equilibrio de carga , por ejemplo, cuando un BLOB tiene que ser asignado a uno de${\displaystyle n}$servidores en un clúster , se podría usar una función hash estándar de tal manera que calculemos el valor hash para ese BLOB, suponiendo que el valor resultante del hash sea${\displaystyle \beta }$, realizamos una operación modular con el número de servidores (${\displaystyle n}$en este caso) para determinar el servidor en el que podemos colocar el BLOB:${\displaystyle \zeta =\beta \ \%\ n}$; por lo tanto, el BLOB se colocará en el servidor cuyo${\displaystyle {\text{ID del servidor}}}$es sucesor de${\displaystyle \zeta }$en este caso. Sin embargo, cuando se agrega o se elimina un servidor durante una interrupción o escalado (cuando${\displaystyle n}$cambios), todos los BLOB en cada servidor deben reasignarse y moverse debido al rehashing , pero esta operación es costosa.

El hash consistente 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 mapee tanto el BLOB como los servidores a un círculo unitario, generalmente${\displaystyle 2\pi }$radianes. Por ejemplo,${\displaystyle \zeta =\Phi \ \%\ 360}$(dónde${\displaystyle \Phi }$es el hash de un BLOB o identificador del servidor, como la dirección IP o el UUID ). Cada BLOB se asigna al siguiente servidor que aparece en el círculo en sentido horario. Por lo general, se utiliza un algoritmo de búsqueda binaria o una búsqueda lineal para encontrar un "lugar" o servidor donde colocar ese BLOB en particular.${\displaystyle O(\log N)}$o${\displaystyle O(N)}$complejidades respectivamente; y en cada iteración, que ocurre en sentido horario, una operación${\displaystyle \zeta \ \leq \ \Psi }$(dónde${\displaystyle \Psi }$(es el valor del servidor dentro del clúster) se realiza para encontrar el servidor donde colocar el BLOB. Esto proporciona una distribución uniforme de los BLOB entre los servidores. Pero, más importante aún, si un servidor falla y se elimina del círculo, solo los BLOB que estaban asignados a ese servidor deben reasignarse al siguiente servidor en sentido horario. Del mismo modo, si se agrega un nuevo servidor, se agrega al círculo unitario y solo los BLOB asignados a ese servidor deben reasignarse.

Es importante destacar que, cuando se agrega o se elimina un servidor, la gran mayoría de los BLOB mantienen sus asignaciones de servidor anteriores, y la adición de${\displaystyle n^{th}}$El servidor solo causa${\displaystyle 1/n}$fracción de los BLOBs a reubicar. Aunque el proceso de mover BLOBs entre servidores de caché en el clúster depende del contexto, comúnmente, el servidor de caché recién agregado identifica a su "predecesor" y mueve todos los BLOBs cuyo mapeo pertenece a este servidor (es decir, cuyo valor hash es menor que el del nuevo servidor) desde él. Sin embargo, en el caso de las cachés de páginas web , en la mayoría de las implementaciones no hay participación de movimiento o copia, suponiendo que el BLOB en caché sea lo suficientemente pequeño. Cuando una solicitud llega a un servidor de caché recién agregado, se produce un fallo de caché y se realiza una solicitud al servidor web real y el BLOB se almacena en caché localmente para futuras solicitudes. Los BLOBs redundantes en los servidores de caché utilizados anteriormente se eliminarían según las políticas de desalojo de caché . ^{[ 11 ]}

Se necesitan varias extensiones a la técnica básica para utilizar eficazmente el hash consistente en el balanceo 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 sentido horario, lo que podría duplicar la carga de ese servidor. Esto puede no ser deseable. Para garantizar una redistribución más uniforme de los BLOB en caso de fallo del servidor, cada servidor puede ser hasheado en múltiples 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 sentido horario, redistribuyendo así los BLOB de manera más uniforme. Otra extensión se refiere a una situación en la que un solo BLOB se vuelve "caliente" y se accede a él muchas veces, por lo que tendrá que alojarse en varios servidores. En esta situación, el BLOB puede asignarse a varios servidores contiguos recorriendo el círculo unitario en sentido horario. Una consideración práctica más compleja surge cuando dos BLOBs se procesan mediante hash cerca uno del otro en el círculo unitario y ambos se "calientan" al mismo tiempo. En este caso, ambos BLOBs utilizarán el mismo conjunto de servidores contiguos en el círculo unitario. Esta situación puede mitigarse si cada BLOB elige una función hash diferente para asignar los servidores al círculo unitario. ^{[ 2 ]}

El hash Rendezvous , diseñado en 1996, es una técnica más simple y general, y permite un acuerdo totalmente distribuido sobre un conjunto de${\displaystyle k}$opciones de un conjunto posible de${\displaystyle n}$opciones. De hecho, se puede demostrar que el hashing consistente es un caso especial del hashing por encuentro. Debido a su simplicidad y generalidad, el hashing por encuentro se utiliza actualmente en lugar del hashing consistente en muchas aplicaciones.

Si los valores de las claves 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.

El${\displaystyle O(K/N)}$es un costo promedio para la redistribución de claves y el${\displaystyle O(\log N)}$La complejidad del 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.

Entre los ejemplos conocidos de uso de funciones hash consistentes se incluyen:

• Particionamiento automatizado de datos de Couchbase ^{[ 16 ]}
• Servicio de almacenamiento de objetos Swift de OpenStack ^{[ 17 ]}
• Componente de particionamiento del sistema de almacenamiento Dynamo de Amazon ^{[ 18 ]}
• Particionamiento de datos en Apache Cassandra ^{[ 19 ]}
• Particionamiento de datos en ScyllaDB ^{[ 20 ]}
• Particionamiento de datos en Voldemort ^{[ 21 ]}
• Enrutador de hash consistente de Akka ^{[ 22 ]}
• Riak , una base de datos distribuida de clave-valor ^{[ 23 ]}
• Gluster , un sistema de archivos de almacenamiento conectado a la red ^{[ 24 ]}
• Red de distribución de contenido de Akamai ^{[ 25 ]}
• Aplicación de chat Discord ^{[ 26 ]}
• Balanceo de carga de solicitudes gRPC a una caché distribuida en SpiceDB ^{[ 27 ]}
• Algoritmo de acordes ^{[ 28 ]}
• Sistema de almacenamiento de objetos MinIO ^{[ 29 ]}

• Comprender el hash consistente
• Hashing consistente realizado por Michael Nielsen el 3 de junio de 2009.
• Hashing consistente, Danny Lewin y la creación de Akamai
• Hash consistente con salto: un algoritmo de hash consistente, rápido y con mínimo consumo de memoria.
• Hashing de encuentro: una alternativa al hash consistente
• Implementaciones en varios idiomas:
  • do
  • C++
  • DO#
  • Erlang
  • Ir
  • Java
  • PHP
  • Rubí
  • Pitón
  • Python (de nuevo)
  • Perl
  • Perl6