Hashing consistente

Técnica de hash

En informática , el hash consistente ^{[1] [2]} es un tipo especial de técnica de hash en el que, cuando se redimensiona una tabla hash , solo es necesario reasignar las claves en promedio, donde es el número de claves y es 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 se reasignen casi todas las claves porque la asignación entre las claves y las ranuras está definida por una operación modular . ${\displaystyle n/m}$ ${\displaystyle n}$ ${\displaystyle m}$

El hash consistente distribuye uniformemente las claves de caché entre los fragmentos , incluso si algunos de ellos fallan o no están disponibles. ^[3]

Historia

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 . ^[4] Este artículo académico de 1997 en Symposium on Theory of Computing 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 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 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] 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 . ^{[6] [7]} ${\displaystyle num\_keys/num\_slots}$

Teradata utilizó esta técnica en su base de datos distribuida ^{[ cita requerida ]} , 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ñó el término "hashing consistente"). En la red de distribución de contenido de Akamai, ^[8] 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 fallos parciales del sistema en aplicaciones web de gran tamaño para proporcionar un almacenamiento en caché robusto sin incurrir en las consecuencias de un fallo 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 particionar un espacio de claves en un conjunto distribuido de nodos y luego construyen una red superpuesta de nodos conectados que proporcionan una recuperación eficiente de nodos por clave.

El algoritmo Rendezvous Hashing , diseñado en 1996, es una técnica más simple y más general ^{[ cita requerida ]} . Logra los objetivos de un algoritmo hash consistente utilizando el algoritmo de peso aleatorio más alto (HRW, por sus siglas en inglés), que es muy diferente.

Técnica básica

En este caso, el uso de un hash consistente daría como resultado que el "BLOB" se almacene en el servidor 139. Un BLOB se asigna al siguiente servidor que aparece en el círculo en el sentido de las agujas del reloj hasta que llega a un servidor que es ${\displaystyle \zeta \leq {\text{server ID}}}$

En el problema del balanceo de carga , por ejemplo, cuando un BLOB tiene que ser asignado 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, suponiendo que 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 cuyo sucesor de 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 rehashing , pero esta operación es costosa. ${\displaystyle n}$ ${\displaystyle \beta }$ ${\displaystyle n}$ ${\displaystyle \zeta =\beta \ \%\ n}$ ${\displaystyle {\text{server ID}}}$ ${\displaystyle \zeta }$ ${\displaystyle n}$

El hash consistente fue diseñado 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 usar una función hash que asigna tanto el BLOB como los servidores a un círculo unitario, generalmente radianes. Por ejemplo, (donde es el hash de un BLOB o identificador de servidor, como 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, se utiliza un algoritmo de búsqueda binaria o una búsqueda lineal para encontrar un "punto" o servidor en el que 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 es el valor del servidor dentro del clúster) para encontrar el servidor en el que colocar el BLOB. Esto proporciona una distribución uniforme de los 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. ${\displaystyle 2\pi }$ ${\displaystyle \zeta =\Phi \ \%\ 360}$ ${\displaystyle \Phi }$ ${\displaystyle O(\log N)}$ ${\displaystyle O(N)}$ ${\displaystyle \zeta \ \leq \ \Psi }$ ${\displaystyle \Psi }$

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 hace que una fracción de los BLOB se reubique. Aunque el proceso de mover BLOB entre servidores de caché en el clúster depende del contexto, comúnmente, el servidor de caché recientemente agregado identifica a su "sucesor" y mueve todos los BLOB, cuya asignación pertenece a este servidor (es decir, cuyo valor hash es menor que el del nuevo servidor), desde él. Sin embargo, en el caso de los 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 almacenado en caché sea lo suficientemente pequeño. Cuando una solicitud llega a un servidor de caché recientemente agregado, ocurre una falla 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] ${\displaystyle n^{th}}$ ${\displaystyle 1/n}$

Implementación

Sean y las funciones hash utilizadas para el BLOB y el identificador único del servidor respectivamente. En la práctica, se utiliza un árbol binario de búsqueda (BST) para mantener dinámicamente el dentro de un clúster o hashring, y para encontrar el sucesor o mínimo dentro del BST, se utiliza el recorrido del árbol . ${\displaystyle h_{b}(x)}$ ${\displaystyle h_{s}(x)}$ ${\displaystyle {\text{server ID}}}$

Insertar en el cluster ${\displaystyle x}$

Sea el valor hash de un BLOB tal que, donde y . Para insertar , busque el sucesor de en la BST de s. Si es mayor que todos los s, el BLOB se coloca en el servidor con el valor más pequeño. ${\displaystyle \beta }$ ${\displaystyle h_{b}(x)=\beta \ \%\ 360}$ ${\displaystyle x\in \mathrm {BLOB} }$ ${\displaystyle h_{b}(x)=\zeta }$ ${\displaystyle x}$ ${\displaystyle \zeta }$ ${\displaystyle {\text{server ID}}}$ ${\displaystyle \zeta }$ ${\displaystyle {\text{server ID}}}$ ${\displaystyle {\text{server ID}}}$

Eliminar del cluster ${\displaystyle x}$

Busque el sucesor de en la BST, elimine el BLOB del . Si no tiene sucesor, elimine el BLOB del . más pequeño de los . ^[11] ${\displaystyle \zeta }$ ${\displaystyle {\text{server ID}}}$ ${\displaystyle \zeta }$ ${\displaystyle {\text{server ID}}}$

Insertar un servidor en un clúster

Sea el valor hash del identificador de un servidor tal que, donde y . Mueva todos los BLOB cuyo valor hash sea menor que , del servidor cuyo es sucesor de . Si es el más grande de todos los s, mueva los BLOB relevantes del más pequeño de los s a . ^[12] ${\displaystyle \Phi }$ ${\displaystyle h_{s}(x)=\Phi \ \%\ 360}$ ${\displaystyle x\in \{{\text{IP address, UUID}}\}}$ ${\displaystyle h_{s}(x)=\theta }$ ${\displaystyle \theta }$ ${\displaystyle {\text{server ID}}}$ ${\displaystyle \theta }$ ${\displaystyle \theta }$ ${\displaystyle {\text{server ID}}}$ ${\displaystyle {\text{server ID}}}$ ${\displaystyle \theta }$

Eliminar un servidor del clúster

Busque el sucesor de en el BST, mueva los BLOB desde a su servidor sucesor. Si no tiene un sucesor, mueva los BLOB al más pequeño de los s. ^[13] ${\displaystyle \theta }$ ${\displaystyle \theta }$ ${\displaystyle \theta }$ ${\displaystyle {\text{server ID}}}$

Reducción de la varianza

Para evitar la asimetría de múltiples nodos dentro del radián, que ocurre debido a la falta de una distribución uniforme de los servidores dentro del clúster, se utilizan múltiples etiquetas. Esas etiquetas duplicadas se denominan "nodos virtuales", es decir, múltiples etiquetas 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 en particular dentro de un clúster se denomina "peso" de ese servidor en particular. ^[14]

Extensiones prácticas

Se necesitan varias extensiones de la técnica básica para usar de manera efectiva el hash consistente para equilibrar la carga en la práctica. En el esquema básico anterior, si falla un servidor, 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. Esto puede no ser deseable. Para garantizar una redistribución más uniforme de los BLOB en caso de falla del servidor, cada servidor puede ser asignado a múltiples ubicaciones en el círculo unitario. Cuando falla un servidor, 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 solo BLOB se "calienta" y se accede a él una gran cantidad de veces y tendrá que alojarse en múltiples servidores. En esta situación, el BLOB puede asignarse a múltiples servidores contiguos recorriendo 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 procesan en hash cerca uno del otro en el círculo unitario y ambos se "activan" 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]

Comparación con el hash de rendezvous y otras alternativas

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

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 requerida ]}

Complejidad

Existe 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 requerida ]} ${\displaystyle O(K/N)}$ ${\displaystyle O(\log N)}$

Ejemplos

Algunos ejemplos conocidos de uso consistente de hash incluyen:

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

Referencias

1. Karger, D.; Lehman, E.; Leighton, T .; Panigrahy, R.; Levine, M.; Lewin, D. (1997). Hashing consistente y árboles aleatorios: protocolos de almacenamiento en caché distribuidos para aliviar puntos calientes en la World Wide Web. Actas del vigésimo noveno simposio anual de la ACM sobre teoría de la computación . ACM Press Nueva York, NY, EE. UU., págs. 654–663. doi :10.1145/258533.258660.
2. Bruce Maggs y Ramesh Sitaraman (2015). "Pepitas algorítmicas en la distribución de contenido" (PDF) . ACM SIGCOMM Computer Communication Review . 45 (3).
3. Diseño de patrones y paradigmas de sistemas distribuidos para servicios escalables y confiables . O'Reilly Media. 2018. ISBN 9781491983607.
4. Roughgarden & Valiant 2021, pág. 2.
5. Roughgarden & Valiant 2021, pág. 7.
6. Roughgarden & Valiant 2021, pág. 8.
7. I. Stoica et al., "Chord: un protocolo de búsqueda escalable peer-to-peer para aplicaciones de Internet", en IEEE/ACM Transactions on Networking, vol. 11, núm. 1, pp. 17–32, febrero de 2003, doi: 10.1109/TNET.2002.808407.
8. Nygren., E.; Sitaraman RK; Sun, J. (2010). "La red Akamai: una plataforma para aplicaciones de Internet de alto rendimiento" (PDF) . ACM SIGOPS Operating Systems Review . 44 (3): 2–19. doi :10.1145/1842733.1842736. S2CID  207181702. Archivado (PDF) del original el 30 de noviembre de 2022 . Consultado el 29 de agosto de 2023 .
9. Karger, D.; Sherman, A.; Berkheimer, A.; Bogstad, B.; Dhanidina, R.; Iwamoto, K.; Kim, B.; Matkins, L.; Yerushalmi, Y. (1999). "Web Caching with Consistent Hashing". Redes de computadoras . 31 (11): 1203–1213. doi :10.1016/S1389-1286(99)00055-9. Archivado desde el original el 21 de julio de 2008 . Consultado el 5 de febrero de 2008 .
10. Roughgarden & Valiant 2021, pág. 6.
11. Moitra 2016, pág. 2.
12. Moitra 2016, págs. 2–3.
13. Moitra 2016, pág. 3.
14. Roughgarden & Valiant 2021, págs. 6–7.
15. "¿Qué es exactamente Membase?". 16 de diciembre de 2014. Consultado el 29 de octubre de 2020 .
16. Holt, Greg (febrero de 2011). "Building a Consistent Hashing Ring" (Construcción de un anillo de hash consistente). openstack.org . Consultado el 17 de noviembre de 2019 .
17. DeCandia, G.; Hastorún, D.; Jampani, M.; Kakulapati, G.; Lakshman, A.; Pilchín, A.; Sivasubramanian, S.; Vosshall, P.; Vogels, Werner (2007). "Dínamo" (PDF) . Revisión de los sistemas operativos ACM Sigops . 41 (6): 205–220. doi : 10.1145/1323293.1294281 . Consultado el 7 de junio de 2018 .
18. Lakshman, Avinash; Malik, Prashant (2010). "Cassandra: un sistema de almacenamiento estructurado descentralizado". ACM SIGOPS Operating Systems Review . 44 (2): 35–40. doi :10.1145/1773912.1773922. S2CID  916681.
19. "Comparación de NoSQL: MongoDB vs ScyllaDB". benchant.com . Consultado el 21 de marzo de 2024 .
20. "Diseño - Voldemort". www.project-voldemort.com/ . Archivado desde el original el 9 de febrero de 2015 . Consultado el 9 de febrero de 2015 . 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.
21. "Enrutamiento de Akka". akka.io. Consultado el 16 de noviembre de 2019 .
22. "Riak Concepts". Archivado desde el original el 19 de septiembre de 2015. Consultado el 6 de diciembre de 2016 .
23. "Algoritmos GlusterFS: distribución". gluster.org . 2012-03-01 . Consultado el 2019-11-16 .
24. Roughgarden, Tim; Valiant, Gregory (28 de marzo de 2016). "Modern Algorithmic Toolbox" (PDF) . stanford.edu . Consultado el 17 de noviembre de 2019 .
25. Vishnevskiy, Stanislav (6 de julio de 2017). "Cómo Discord logró que Elixir alcanzara los 5 000 000 de usuarios simultáneos" . Consultado el 16 de agosto de 2022 .
26. "Equilibrio de carga de hash consistente para gRPC". 24 de noviembre de 2021. Consultado el 4 de septiembre de 2023 .
27. Stoica, I. ; Morris, R.; Liben-Nowell, D.; Karger, D.; Kaashoek, MF; Dabek, F.; Balakrishnan, H. (25 de febrero de 2003). "Chord: un protocolo de búsqueda escalable entre pares para aplicaciones de Internet". Transacciones IEEE/ACM sobre redes . 11 (1): 17–32. doi :10.1109/TNET.2002.808407. S2CID  221276912.
28. "Análisis profundo de versiones, metadatos y almacenamiento de MinIO" . Consultado el 24 de octubre de 2023 .

Obras citadas

• Moitra, Ankur (10 de febrero de 2016). «Algoritmos avanzados, 6.854» (PDF) . Instituto Tecnológico de Massachusetts . Archivado (PDF) del original el 13 de abril de 2021. Consultado el 8 de octubre de 2021 .
• Roughgarden, Tim; Valiant, Gregory (28 de marzo de 2021). "The Modern Algorithmic Toolbox, Introduction to Consistent Hashing" (PDF) . Universidad de Stanford . Archivado (PDF) del original el 25 de julio de 2021 . Consultado el 7 de octubre de 2021 .

Enlaces externos

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