En informática , el hash coherente [1] [2] es un tipo especial de hash de modo que cuando se cambia el tamaño de una tabla hash , solo las claves deben reasignarse en promedio donde es el número de llaves 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 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 .
Historia
El término "hash consistente" fue introducido por David Karger et al. en el MIT para su uso en almacenamiento en caché distribuido. Este artículo académico de 1997 introdujo el término "hash consistente" como una forma de distribuir solicitudes entre una población cambiante de servidores web. Luego, cada ranura está representada por un servidor en un sistema distribuido. La adición de un servidor y la eliminación del servidor (digamos, debido a una falla) solo requiereelementos que se volverán a barajar cuando cambie 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]
Teradata usó esta técnica en su base de datos distribuida, lanzada en 1986, aunque no usaron 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ña "hash consistente"). En la red de entrega de contenido de Akamai, [3] se usa hash consistente para equilibrar la carga dentro de un clúster de servidores , mientras que se usa un algoritmo de unión estable para equilibrar la carga entre clústeres. [2]
También se ha utilizado hash consistente para reducir el impacto de fallas parciales del sistema en aplicaciones web grandes para proporcionar un almacenamiento en caché sólido sin incurrir en las consecuencias de una falla en todo el sistema. [4] El hash consistente es también 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 construir una red superpuesta de nodos conectados que brindan una recuperación eficiente de los nodos por clave. El hash de encuentro , diseñado en 1996, es una técnica más simple y general [ cita requerida ] . Alcanza los objetivos de hash consistente utilizando el algoritmo de peso aleatorio más alto (HRW) muy diferente.
Técnica básica
Considere el problema del equilibrio de carga en el que un conjunto de objetos (por ejemplo, páginas web o segmentos de video) deben asignarse a un conjunto deservidores. Una forma de distribuir objetos uniformemente a lo largo del servidores es utilizar una función hash estándar y colocar el objeto en servidor con id , Sin embargo, si se agrega o quita un servidor (es decir, cambios), la asignación de servidor de casi todos los objetos del sistema puede cambiar. Esto es problemático ya que los servidores a menudo se activan o desactivan y cada evento de este tipo requeriría reasignar y mover casi todos los objetos a nuevos servidores.
El hash consistente se diseñó para evitar el problema de tener que cambiar la asignación de servidor de cada objeto cuando se agrega o quita un servidor. La idea principal es utilizar una función hash para asignar aleatoriamente tanto los objetos como los servidores a un círculo unitario, por ejemplo, en un ángulo degrados con respecto al eje horizontal. Luego, cada objeto se asigna al siguiente servidor que aparece en el círculo en el orden de las agujas del reloj. Esto proporciona una distribución uniforme de los objetos a los servidores. Pero, lo que es más importante, si un servidor falla y se elimina del círculo, solo los objetos que se asignaron al servidor fallido deben reasignarse al siguiente servidor en el orden de las agujas del reloj. Del mismo modo, si se agrega un nuevo servidor, se agrega al círculo de la unidad, y solo los objetos asignados a ese servidor deben reasignarse. Es importante destacar que cuando se agrega o elimina un servidor, la gran mayoría de los objetos mantienen sus asignaciones de servidor anteriores.
Extensiones prácticas
Se necesitan varias extensiones de la técnica básica para utilizar de forma eficaz el hash coherente para el equilibrio de carga en la práctica. [2] En el esquema básico anterior, si un servidor falla, todos sus objetos se reasignan al siguiente servidor en el orden de las agujas del reloj, duplicando potencialmente la carga de ese servidor. Esto puede no ser deseable. Para garantizar una redistribución más uniforme de los objetos en caso de fallo del servidor, cada servidor se puede aplicar a varias ubicaciones en el círculo unitario. [2] Cuando un servidor falla, los objetos asignados a cada una de sus réplicas en el círculo unitario serán reasignados a un servidor diferente en el orden de las agujas del reloj, redistribuyendo así los objetos de manera más uniforme. Otra extensión se refiere a una situación en la que un solo objeto se pone "caliente" y se accede a él una gran cantidad de veces y tendrá que estar alojado en varios servidores. En esta situación, el objeto puede asignarse a múltiples servidores contiguos atravesando el círculo unitario en el sentido de las agujas del reloj. [2] Una consideración práctica más compleja surge cuando dos objetos que tienen un hash cerca del otro en el círculo unitario y ambos se "calientan" al mismo tiempo. En este caso, ambos objetos utilizarán el mismo conjunto de servidores contiguos en el círculo unitario. Esta situación puede mejorarse eligiendo cada objeto una función hash diferente para mapear servidores al círculo unitario. [2]
Comparación con Rendezvous Hashing 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 en un conjunto de opciones 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, Rendezvous Hashing ahora se usa en lugar de 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. [ cita requerida ]
Complejidad
Tabla hash clásica | Hash consistente | |
---|---|---|
agregar un nodo | ||
eliminar un nodo | ||
agregar una clave | ||
quitar una llave |
La es un costo promedio para la redistribución de claves y el 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. [ cita requerida ]
Ejemplos de
Entre los ejemplos conocidos de uso de hash consistente se incluyen:
- Partición de datos automatizada de Couchbase [5]
- Servicio de almacenamiento de objetos de OpenStack Swift [6]
- Componente de partición del sistema de almacenamiento de Amazon Dynamo [7]
- Particionamiento de datos en Apache Cassandra [8]
- Partición de datos en Voldemort [9]
- Enrutador hash consistente de Akka [10]
- Riak , una base de datos distribuida de valores clave [11]
- Gluster , un sistema de archivos de almacenamiento conectado a la red [12]
- Red de distribución de contenido de Akamai [13]
- Aplicación de chat Discord [14]
- Balanceador de carga de red Maglev [15]
- Partición de datos en Azure Cosmos DB
Referencias
- ↑ a b Karger, D .; Lehman, E .; Leighton, T .; Panigrahy, R .; Levine, M .; Lewin, D. (1997). Hash constante y árboles aleatorios: protocolos de almacenamiento en caché distribuidos para aliviar los puntos calientes en la World Wide Web . Actas del Vigésimo noveno Simposio Anual ACM sobre Teoría de la Computación . ACM Press Nueva York, NY, EE. UU. págs. 654–663. doi : 10.1145 / 258533.258660 .
- ^ a b c d e f g Bruce Maggs y Ramesh Sitaraman (2015). "Pepitas algorítmicas en la entrega de contenido" (PDF) . Revisión de comunicación informática ACM SIGCOMM . 45 (3).
- ^ Nygren., E .; Sitaraman RK; Sol, J. (2010). "La red Akamai: una plataforma para aplicaciones de Internet de alto rendimiento" (PDF) . Revisión de sistemas operativos ACM SIGOPS . 44 (3): 2–19. doi : 10.1145 / 1842733.1842736 . S2CID 207181702 . Archivado (PDF) desde el original el 13 de septiembre de 2012 . Consultado el 19 de noviembre de 2012 .
- ^ Karger, D .; Sherman, A .; Berkheimer, A .; Bogstad, B .; Dhanidina, R .; Iwamoto, K .; Kim, B .; Matkins, L .; Yerushalmi, Y. (1999). "Web Caching con hash consistente" . Redes informáticas . 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 .
- ^ "¿Qué es exactamente Membase?" . Consultado el 29 de octubre de 2020 .
- ^ Holt, Greg (febrero de 2011). "Construyendo un anillo de hash consistente" . openstack.org . Consultado el 17 de noviembre de 2019 .
- ^ DeCandia, G .; Hastorun, D .; Jampani, M .; Kakulapati, G .; Lakshman, A .; Pilchin, A .; Sivasubramanian, S .; Vosshall, P .; Vogels, Werner (2007). "Dynamo: Tienda de valor-clave de alta disponibilidad de Amazon" (PDF) . Actas del 21º Simposio de ACM sobre principios de sistemas operativos . 41 (6): 205–220. doi : 10.1145 / 1323293.1294281 . Consultado el 7 de junio de 2018 .
- ^ Lakshman, Avinash; Malik, Prashant (2010). "Cassandra: un sistema de almacenamiento estructurado descentralizado". Revisión de sistemas operativos ACM SIGOPS . 44 (2): 35–40. doi : 10.1145 / 1773912.1773922 .
- ^ "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.
- ^ "Enrutamiento Akka" . akka.io . Consultado el 16 de noviembre de 2019 .
- ^ "Conceptos de Riak" . Archivado desde el original el 19 de septiembre de 2015 . Consultado el 6 de diciembre de 2016 .
- ^ "Algoritmos GlusterFS: Distribución" . gluster.org . 2012-03-01 . Consultado el 16 de noviembre de 2019 .
- ^ Roughgarden, Tim; Valiente, Gregory (28 de marzo de 2016). "Caja de herramientas algorítmica moderna" (PDF) . stanford.edu . Consultado el 17 de noviembre de 2019 .
- ^ Vishnevskiy, Stanislav (6 de julio de 2017). "Cómo Discord escaló Elixir a 5.000.000 de usuarios simultáneos" . Consultado el 17 de noviembre de 2019 .
- ^ Eisenbud, Daniel E .; Yi, Cheng; Contavalli, Carlo; Smith, Cody; Kononov, Roman; Mann-Hielscher, Eric; Cilingiroglu, Ardas; Cheyney, Bin; Shang, Wentao; Hosein, Jinnah Dylan. "Maglev: un equilibrador de carga de red de software rápido y confiable" (PDF) . Consultado el 17 de noviembre de 2019 .
enlaces externos
- Comprender el hash consistente
- Hash consistente por Michael Nielsen el 3 de junio de 2009
- Hashing consistente, Danny Lewin y la creación de Akamai
- Saltar hash consistente: un algoritmo hash consistente, de memoria mínima y rápido
- Rendezvous Hashing: una alternativa al hash consistente
- Implementaciones en varios idiomas:
- C
- C ++
- C#
- Erlang
- Ir
- Java
- PHP
- Rubí
- Pitón
- Python (de nuevo)
- Perl
- Perl6