hash consistente

técnica de hash

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 . ${\displaystyle n/m}$ ${\displaystyle n}$ ${\displaystyle m}$

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]

Historia

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]} ${\displaystyle num\_keys/num\_slots}$

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.

tecnica basica

En este caso, el uso de 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 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. ${\displaystyle n}$ ${\displaystyle \beta }$ ${\displaystyle n}$ ${\displaystyle \zeta =\beta \ \%\ n}$ ${\displaystyle {\text{server ID}}}$ ${\displaystyle \zeta }$ ${\displaystyle n}$

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. ${\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 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] ${\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 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 . ${\displaystyle h_{b}(x)}$ ${\displaystyle h_{s}(x)}$ ${\displaystyle {\text{server ID}}}$

Insertar en el clúster ${\displaystyle x}$

Sea el valor hash de un BLOB tal que, dónde y . Para insertar , busque el sucesor de en la BST del 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 clúster ${\displaystyle x}$

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

Insertar un servidor en el cluster

Sea el valor hash del identificador de un servidor tal que, dónde y . Mueva todos los BLOB cuyo valor hash sea menor que , desde el servidor sucesor de . Si es el mayor 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

Encuentre el sucesor de en BST y mueva los BLOB 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 varianza

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]

Extensiones practicas

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]

Comparación con hash de encuentro y otras alternativas

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. ${\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 necesaria ]}

Complejidad

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

Ejemplos

Los ejemplos conocidos de uso constante de hash incluyen:

• Partición de datos automatizada de Couchbase ^[15]
• Servicio de almacenamiento de objetos de OpenStack Swift ^[16]
• Componente de partición del sistema de almacenamiento Dynamo de Amazon ^[17]
• Partición de datos en Apache Cassandra ^[18]
• Partición de datos en ScyllaDB ^[19]
• Partición de datos en Voldemort ^[20]
• Enrutador de hash consistente de Akka ^[21]
• Riak , una base de datos distribuida de valores clave ^[22]
• Gluster , un sistema de archivos de almacenamiento conectado a la red ^[23]
• Red de entrega de contenidos de Akamai ^[24]
• Aplicación de chat de Discord ^[25]
• Equilibrio de carga de solicitudes de gRPC a una caché distribuida 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é distribuido para aliviar los puntos calientes en la World Wide Web. Actas del vigésimo noveno simposio anual de la ACM sobre teoría de la informática . ACM Press Nueva York, NY, Estados Unidos. págs. 654–663. doi :10.1145/258533.258660.
2. Bruce Maggs y Ramesh Sitaraman (2015). "Pepitas algorítmicas en la entrega de contenidos" (PDF) . Revisión de comunicación por computadora ACM SIGCOMM . 45 (3).
3. Diseño de patrones y paradigmas de sistemas distribuidos para servicios escalables y confiables . Medios O'Reilly. 2018.ISBN​ 9781491983607.
4. Roughgarden y Valiant 2021, pag. 2.
5. Roughgarden y Valiant 2021, pag. 7.
6. Roughgarden y Valiant 2021, pag. 8.
7. I. Stoica et al., "Chord: un protocolo de búsqueda entre pares escalable para aplicaciones de Internet", en IEEE/ACM Transactions on Networking, vol. 11, núm. 1, págs. 17–32, febrero de 2003, doi: 10.1109/TNET.2002.808407.
8. Nygren., E.; Sitaraman RK; Sol, J. (2010). "La red Akamai: una plataforma para aplicaciones de Internet de alto rendimiento" (PDF) . Revisión de los sistemas operativos ACM SIGOPS . 44 (3): 2–19. doi :10.1145/1842733.1842736. S2CID  207181702. Archivado (PDF) desde el 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). "Almacenamiento en caché web con hash coherente". Red 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 y Valiant 2021, pag. 6.
11. Moitra 2016, pag. 2.
12. Moitra 2016, pag. 2–3.
13. Moitra 2016, pag. 3.
14. Roughgarden y Valiant 2021, pag. 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). "Construcción de un anillo hash coherente". 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. Lakshmán, Avinash; Malik, Prashant (2010). "Cassandra: un sistema de almacenamiento estructurado descentralizado". Revisión de los sistemas operativos ACM SIGOPS . 44 (2): 35–40. doi :10.1145/1773912.1773922. S2CID  916681.
19. "Comparación de NoSQL: MongoDB frente a 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. "Conceptos Riak". Archivado desde el original el 19 de septiembre de 2015 . Consultado el 6 de diciembre de 2016 .
23. "Algoritmos de GlusterFS: distribución". gluster.org . 2012-03-01 . Consultado el 16 de noviembre de 2019 .
24. Jardín áspero, Tim; Valiente, Gregory (28 de marzo de 2016). "Caja de herramientas algorítmica moderna" (PDF) . stanford.edu . Consultado el 17 de noviembre de 2019 .
25. Vishnevskiy, Stanislav (6 de julio de 2017). "Cómo Discord llevó Elixir a 5.000.000 de usuarios simultáneos" . Consultado el 16 de agosto de 2022 .
26. "Equilibrio de carga de hash coherente para gRPC". 24 de noviembre de 2021 . Consultado el 4 de septiembre de 2023 .
27. Estoica, 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 de igual a igual escalable para aplicaciones de Internet". Transacciones IEEE/ACM en 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 .

Trabajos citados

• Moitra, Ankur (10 de febrero de 2016). "Algoritmos avanzados, 6.854" (PDF) . Instituto de Tecnología de Massachusetts . Archivado (PDF) desde el original el 13 de abril de 2021 . Consultado el 8 de octubre de 2021 .
• Jardín áspero, Tim; Valiant, Gregory (28 de marzo de 2021). "La caja de herramientas algorítmica moderna, introducción al hash consistente" (PDF) . Universidad Stanford . Archivado (PDF) desde el original el 25 de julio de 2021 . Consultado el 7 de octubre de 2021 .

enlaces externos

• Comprender 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 Hash consistente: un algoritmo de hash consistente, rápido y con memoria mínima
• Rendezvous Hashing: una alternativa al Hashing consistente
• Implementaciones en varios idiomas:
  • C
  • C++
  • C#
  • erlang
  • Ir
  • Java
  • PHP
  • Rubí
  • Pitón
  • Pitón (otra vez)
  • perla
  • Perl6