El hash de Rendezvous o de mayor peso aleatorio (HRW) [1] [2] es un algoritmo que permite a los clientes lograr un acuerdo distribuido en un conjunto de opciones de un posible conjunto de opciones. Una aplicación típica es cuando los clientes necesitan acordar a qué sitios (o proxies) se asignan los objetos.
El hash de encuentro es mucho más simple y más general que el hash consistente , que se convierte en un caso especial (para) de hash de encuentro.
Historia
El hash de encuentro fue inventado por David Thaler y Chinya Ravishankar en la Universidad de Michigan en 1996. [1] El hash consistente apareció un año después en la literatura.
Dada su simplicidad y generalidad, el hash de encuentro se prefiere ahora al hash consistente en aplicaciones del mundo real. [3] [4] [5] El hash Rendezvous se utilizó muy temprano en muchas aplicaciones, incluido el almacenamiento en caché móvil, [6] el diseño de enrutadores, [7] el establecimiento de claves seguras , [8] y la fragmentación y las bases de datos distribuidas . [9]
Una de las primeras aplicaciones del hash de encuentro fue permitir a los clientes de multidifusión en Internet (en contextos como MBONE ) identificar los puntos de encuentro de multidifusión de forma distribuida. [10] [11] Fue utilizado en 1998 por el Cache Array Routing Protocol (CARP) de Microsoft para la coordinación y el enrutamiento de la caché distribuida. [12] [13] Algunos protocolos de enrutamiento de multidifusión independientes del protocolo utilizan el hash de encuentro para elegir un punto de encuentro. [1]
Descripción general
Algoritmo
El hash de Rendezvous resuelve el problema de la tabla hash distribuida : ¿Cómo puede un conjunto de clientes, dado un objeto, acuerde dónde en un conjunto de sitios (servidores, digamos) para colocar ? Cada cliente debe seleccionar un sitio de forma independiente, pero todos los clientes deben terminar eligiendo el mismo sitio. Esto no es trivial si agregamos una restricción de interrupción mínima y requerimos que solo los objetos mapeados a un sitio eliminado puedan reasignarse a otros sitios.
La idea básica es darle a cada sitio una puntuación (un peso ) para cada objetoy asigne el objeto al sitio con la puntuación más alta. Todos los clientes acuerdan primero una función hash. Por objeto, el sitio se define para tener peso . HRW asigna al sitio cuyo peso es el más grande. Desde se acuerda, cada cliente puede calcular independientemente los pesos y elige el más grande. Si el gol se distribuye-acuerdo, los clientes pueden elegir independientemente los sitios con el valores hash más grandes.
Si un sitio se agrega o quita, solo los objetos mapeados a se reasignan a diferentes sitios, satisfaciendo la restricción de interrupción mínima anterior. La asignación de HRW puede ser calculada de forma independiente por cualquier cliente, ya que depende solo de los identificadores para el conjunto de sitios. y el objeto que se asigna.
HRW se adapta fácilmente a diferentes capacidades entre sitios. Si el sitio tiene el doble de capacidad que los otros sitios, simplemente representamos dos veces en la lista, digamos, como . Claramente, ahora se asignarán el doble de objetos a en cuanto a los otros sitios.
Propiedades
Primero puede parecer suficiente tratar los n sitios como depósitos en una tabla hash y aplicar un hash al nombre del objeto O en esta tabla. Sin embargo, si alguno de los sitios falla o es inaccesible, el tamaño de la tabla hash cambia, lo que requiere que todos los objetos se reasignen. Esta disrupción masiva hace que este hash directo sea inviable. Sin embargo, bajo el hash de encuentro, los clientes manejan las fallas del sitio eligiendo el sitio que produce el siguiente peso más grande. La reasignación solo es necesaria para los objetos actualmente asignados al sitio fallido, y la interrupción es mínima. [1] [2]
El hash de Rendezvous tiene las siguientes propiedades:
- Baja sobrecarga: la función hash utilizada es eficiente, por lo que la sobrecarga en los clientes es muy baja.
- Equilibrio de carga : Dado que la función hash se asignaron al azar, cada una de las n sitios es la misma probabilidad de recibir el objeto O . Las cargas son uniformes en todos los sitios.
- Capacidad del sitio: los sitios con diferentes capacidades se pueden representar en la lista de sitios con multiplicidad en proporción a la capacidad. Un sitio con el doble de capacidad que los otros sitios se representará dos veces en la lista, mientras que todos los demás sitios se representarán una vez.
- Alta tasa de aciertos : dado que todos los clientes están de acuerdo en colocar un objeto O en el mismo sitio S O , cada búsqueda o colocación de O en S O produce la máxima utilidad en términos de tasa de aciertos. El objeto O siempre se encontrará a menos que es desalojado por algún algoritmo de sustitución en S O .
- Interrupción mínima: cuando un sitio falla, solo los objetos asignados a ese sitio deben reasignarse. La disrupción está en el nivel mínimo posible, como se demuestra en. [1] [2]
- Distribuido k -acuerdo: Los clientes pueden llegar a un acuerdo distribuidos en k sitios, basta con seleccionar los mejores k sitios en el pedido. [8]
Comparación con hash consistente
El hash consistente funciona mapeando sitios de manera uniforme y aleatoria a puntos en un círculo unitario llamados tokens. Los objetos también se asignan al círculo unitario y se colocan en el sitio cuya ficha es la primera que se encuentra viajando en el sentido de las agujas del reloj desde la ubicación del objeto. Cuando se elimina un sitio, los objetos que posee se transfieren al sitio que posee el siguiente token que se encuentra moviéndose en el sentido de las agujas del reloj. Siempre que cada sitio se asigne a un gran número (100-200, digamos) de tokens, esto reasignará objetos de una manera relativamente uniforme entre los sitios restantes.
Si los sitios se asignan a puntos en el círculo de forma aleatoria mediante el hash de 200 variantes de la ID del sitio, por ejemplo, la asignación de cualquier objeto requiere almacenar o recalcular 200 valores de hash para cada sitio. Sin embargo, los tokens asociados con un sitio determinado pueden calcularse previamente y almacenarse en una lista ordenada, lo que requiere solo una aplicación única de la función hash al objeto y una búsqueda binaria para calcular la asignación. Sin embargo, incluso con muchos tokens por sitio, la versión básica de hash consistente puede no equilibrar los objetos de manera uniforme entre los sitios, ya que cuando se elimina un sitio, cada objeto asignado se distribuye solo en tantos otros sitios como tokens tenga el sitio (digamos 100 –200).
Las variantes de hash consistente (como Dynamo de Amazon ) que utilizan una lógica más compleja para distribuir tokens en el círculo unitario ofrecen un mejor equilibrio de carga que el hash consistente básico, reducen la sobrecarga de agregar nuevos sitios y reducen la sobrecarga de metadatos y ofrecen otros beneficios. [14]
Por el contrario, el hash de encuentro (HRW) es mucho más sencillo desde el punto de vista conceptual y práctico. También distribuye objetos de manera uniforme en todos los sitios, dada una función hash uniforme. A diferencia del hash consistente, HRW no requiere precomputación ni almacenamiento de tokens. Un objeto se coloca en uno de sitios calculando el valores hash y eligiendo el sitio que produce el valor hash más alto. Si un sitio nuevo se agrega, las nuevas ubicaciones de objetos o solicitudes computarán valores hash y elija el más grande de ellos. Si un objeto ya está en el sistema en mapas a este nuevo sitio , se buscará de nuevo y se almacenará en caché en . Todos los clientes lo obtendrán en adelante de este sitio, y la copia antigua en caché enfinalmente será reemplazado por el algoritmo de administración de caché local. Si se desconecta, sus objetos se reasignarán uniformemente al resto sitios.
Las variantes del algoritmo HRW, como el uso de un esqueleto (ver más abajo), pueden reducir la tiempo para que la ubicación del objeto , a costa de una menor uniformidad global de ubicación. Cuándo no es demasiado grande, sin embargo, el No es probable que el costo de colocación de HRW básico sea un problema. HRW evita por completo toda la sobrecarga y la complejidad asociadas con el manejo correcto de múltiples tokens para cada sitio y metadatos asociados.
El hash de Rendezvous también tiene la gran ventaja de que proporciona soluciones sencillas a otros problemas importantes, como la distribución -convenio.
El hash consistente es un caso especial de hash Rendezvous
El hash de encuentro es más simple y más general que el hash consistente. Se puede demostrar que el hash consistente es un caso especial de HRW mediante la elección adecuada de una función hash de dos lugares. Desde el identificador del sitio la versión más simple de hash consistente calcula una lista de posiciones de token, por ejemplo, dónde asigna valores hash a ubicaciones en el círculo unitario. Definir la función hash de dos lugares ser - estar dónde denota la distancia a lo largo del círculo unitario desde a (desde tiene un valor mínimo distinto de cero, no hay problema para traducir este valor a un número entero único en algún rango acotado). Esto duplicará exactamente la asignación producida por hash consistente.
Sin embargo, no es posible reducir HRW a un hash consistente (asumiendo que el número de tokens por sitio está limitado), ya que HRW potencialmente reasigna los objetos de un sitio eliminado a un número ilimitado de otros sitios.
Variaciones ponderadas
En la implementación estándar del hash de encuentro, cada nodo recibe una proporción estáticamente igual de claves. Sin embargo, este comportamiento no es deseable cuando los nodos tienen diferentes capacidades para procesar o mantener sus claves asignadas. Por ejemplo, si uno de los nodos tuviera el doble de capacidad de almacenamiento que los demás, sería beneficioso que el algoritmo pudiera tener esto en cuenta, de modo que este nodo más potente reciba el doble de claves que cada uno de los demás.
Un mecanismo sencillo para manejar este caso es asignar dos ubicaciones virtuales a este nodo, de modo que si alguna de las ubicaciones virtuales de ese nodo más grande tiene el hash más alto, ese nodo recibe la clave. Pero esta estrategia no funciona cuando los pesos relativos no son múltiplos enteros. Por ejemplo, si un nodo tuviera un 42% más de capacidad de almacenamiento, sería necesario agregar muchos nodos virtuales en diferentes proporciones, lo que reduciría considerablemente el rendimiento. Se han propuesto varias modificaciones al hash de encuentro para superar esta limitación.
Protocolo de enrutamiento de matriz de caché
El Cache Array Routing Protocol (CARP) es un borrador de IETF de 1998 que describe un método para calcular los factores de carga que se pueden multiplicar por la puntuación de hash de cada nodo para producir un nivel arbitrario de precisión para ponderar los nodos de manera diferente. [12] Sin embargo, una desventaja de este enfoque es que cuando se cambia el peso de cualquier nodo, o cuando se agrega o quita cualquier nodo, todos los factores de carga deben volverse a calcular y escalar relativamente. Cuando los factores de carga cambian entre sí, desencadena el movimiento de claves entre nodos cuyo peso no se modificó, pero cuyo factor de carga sí cambió en relación con otros nodos del sistema. Esto da como resultado un movimiento excesivo de teclas. [15]
Replicación controlada
La replicación controlada bajo hash escalable o CRUSH [16] es una extensión de RUSH [17] que mejora el hash de encuentro mediante la construcción de un árbol en el que se utiliza una función pseudoaleatoria (hash) para navegar por el árbol y encontrar qué nodo es el responsable en última instancia. para una clave determinada. Permite una estabilidad perfecta para agregar nudos, sin embargo, no es perfectamente estable al quitar o volver a ponderar los nudos, siendo el exceso de movimiento de las teclas proporcional a la altura del árbol.
El sistema de almacenamiento de datos ceph utiliza el algoritmo CRUSH para asignar objetos de datos a los nodos responsables de almacenarlos. [18]
Variante basada en esqueleto
Cuándo es extremadamente grande, una variante basada en esqueleto puede mejorar el tiempo de ejecución. [19] [20] [21] Este enfoque crea una estructura jerárquica virtual (llamada "esqueleto") y logratiempo de ejecución aplicando HRW en cada nivel mientras desciende la jerarquía. La idea es elegir primero alguna constante y organizar el sitios en racimos A continuación, cree una jerarquía virtual eligiendo una constante e imaginando estos racimos colocados en las hojas de un árbol de nodos virtuales, cada uno con fanout .
En el diagrama adjunto, el tamaño del clúster es , y el fanout esqueleto es . Suponiendo 108 sitios (nodos reales) por conveniencia, obtenemos una jerarquía virtual de tres niveles. Desde, cada nodo virtual tiene una numeración natural en octal. Por lo tanto, los 27 nodos virtuales en el nivel más bajo estarían numerados en octal (podemos, por supuesto, variar el abanico en cada nivel; en ese caso, cada nodo se identificará con el número de base mixta correspondiente).
En lugar de aplicar HRW a los 108 nodos reales, primero podemos aplicar HRW a los 27 nodos virtuales de nivel más bajo, seleccionando uno. Luego aplicamos HRW a los cuatro nodos reales de su clúster y elegimos el sitio ganador. Solo necesitamos hashes, en lugar de 108. Si aplicamos este método comenzando un nivel más alto en la jerarquía, necesitaríamos hashes para llegar al sitio ganador. La figura muestra cómo, si procedemos a partir de la raíz del esqueleto, podemos elegir sucesivamente los nodos virtuales, , y , y finalmente terminar con el sitio 74.
Podemos comenzar en cualquier nivel de la jerarquía virtual, no solo en la raíz. Comenzar más abajo en la jerarquía requiere más hashes, pero puede mejorar la distribución de la carga en caso de fallas. Además, no es necesario almacenar la jerarquía virtual, pero se puede crear a pedido, ya que los nombres de los nodos virtuales son simplemente prefijos de base-(o representaciones de base mixta). Podemos crear fácilmente cadenas ordenadas adecuadamente a partir de los dígitos, según sea necesario. En el ejemplo, estaríamos trabajando con las cadenas (en el nivel 1), (en el nivel 2), y (en el nivel 3). Claramente, tiene altura , desde y son ambas constantes. El trabajo realizado en cada nivel es, desde es una constante.
Para cualquier objeto dado, está claro que el método elige cada grupo y, por lo tanto, cada uno de los sitios, con igual probabilidad. Si el sitio finalmente seleccionado no está disponible, podemos seleccionar un sitio diferente dentro del mismo clúster, de la manera habitual. Alternativamente, podríamos subir uno o más niveles en el esqueleto y seleccionar una alternativa entre los nodos virtuales hermanos en ese nivel, y una vez más descender la jerarquía a los nodos reales, como se indicó anteriormente.
El valor de se puede elegir en función de factores como la tasa de falla anticipada y el grado de equilibrio de carga deseado. Un valor más alto de conduce a un menor sesgo de carga en caso de falla a costa de una mayor sobrecarga de búsqueda.
La elección es equivalente al hash de encuentro no jerárquico. En la práctica, la función hash es muy barato, entonces puede funcionar bastante bien a menos que es muy alto.
Otras variantes
En 2005, Christian Schindelhauer y Gunnar Schomaker describieron un método logarítmico para volver a ponderar los puntajes hash de una manera que no requiere un escalado relativo de los factores de carga cuando cambia el peso de un nodo o cuando se agregan o eliminan nodos. [22] Esto permitió los beneficios duales de una precisión perfecta al ponderar nodos, junto con una estabilidad perfecta, ya que solo se necesitaba reasignar un número mínimo de claves a los nuevos nodos.
Se utiliza una estrategia de hash similar basada en logaritmos para asignar datos a los nodos de almacenamiento en el sistema de almacenamiento de datos de Cleversafe , ahora IBM Cloud Object Storage . [15]
Implementación
La implementación es sencilla una vez que una función hash se elige (el trabajo original sobre el método HRW hace una recomendación de función hash). [1] [2] Cada cliente solo necesita calcular un valor hash para cada uno de lossitios y luego elija el más grande. Este algoritmo se ejecuta enhora. Si la función hash es eficiente, la el tiempo de ejecución no es un problema a menos que es muy grande.
Hash de encuentro ponderado
Código Python que implementa un hash de encuentro ponderado: [15]
#! / usr / bin / env python3 import mmh3 import mathdef int_to_float ( value : int ) -> float : "" "Convierte un entero uniformemente aleatorio [[computación de 64 bits | 64 bits]] en un número de punto flotante uniformemente aleatorio en el intervalo . "" " cincuenta_tres_ones = 0xFFFFFFFFFFFFFFFF >> ( 64 - 53 ) cincuenta_tres_ceros = float ( 1 << 53 ) return ( valor & cincuenta_tres_res ) / cincuenta_tres_zerosclass Node : "" "Clase que representa un nodo al que se le asignan claves como parte de un hash de encuentro ponderado." "" def __init__ ( self , name : str , seed , weight ) -> None : self . nombre , yo . semilla , yo . peso = nombre , semilla , peso def __str__ ( self ): return "[" + self . nombre + "(" + str ( auto . semilla ) + "" + str ( auto . de peso ) + ")]" def compute_weighted_score ( self , key ): hash_1 , hash_2 = mmh3 . hash64 ( str ( clave ), 0xFFFFFFFF y self . seed ) hash_f = int_to_float ( hash_2 ) score = 1.0 / - math . log ( hash_f ) return self . peso * puntajedef determine_responsible_node ( nodos , clave ): "" "Determina qué nodo, de un conjunto de nodos de varios pesos, es responsable de la clave proporcionada." "" puntaje_más alto , campeón = - 1 , Ninguno para el nodo en los nodos : puntaje = nodo . compute_weighted_score ( clave ) si el puntaje > puntaje_más alto : campeón , puntaje_más alto = nodo , devuelve el puntaje campeón
Ejemplos de salidas de WRH:
[GCC 4.2.1 Compatible con Apple LLVM 6.0 (clang-600.0.39)] en darwin Escriba "ayuda", "derechos de autor", "créditos" o "licencia" para obtener más información. >>> importar wrh >>> nodo1 = wrh . Node ( "node1" , 123 , 100 ) >>> node2 = wrh . Nodo ( "nodo2" , 567 , 200 ) >>> nodo3 = wrh . Node ( "node3" , 789 , 300 ) >>> str ( wrh . Determine_responsible_node ([ node1 , node2 , node3 ], 'foo' )) '[node3 (789, 300)]' >>> str ( wrh . Determine_responsible_node ([ node1 , node2 , node3 ], 'bar' )) '[node3 (789, 300)]' >>> str ( wrh . determine_responsible_node ([ node1 , node2 , node3 ], 'hola' )) '[node2 ( 567, 200)] '
Referencias
- ^ a b c d e f Thaler, David; Chinya Ravishankar. "Un esquema de mapeo basado en el nombre para el encuentro" (PDF) . Informe técnico de la Universidad de Michigan CSE-TR-316-96 . Consultado el 15 de septiembre de 2013 .
- ^ a b c d Thaler, David; Chinya Ravishankar (febrero de 1998). "Uso de esquemas de asignación basados en nombres para aumentar las tasas de acierto". Transacciones IEEE / ACM sobre redes . 6 (1): 1-14. CiteSeerX 10.1.1.416.8943 . doi : 10.1109 / 90.663936 .
- ^ "Explicación del hash de encuentro - Randoritmos" . randorithms.com . Consultado el 29 de marzo de 2021 .
- ^ "Hash de encuentro: mi método de distribución" consistente "de línea de base - Paul Khuong: algunos Lisp" . pvk.ca . Consultado el 29 de marzo de 2021 .
- ^ Aniruddha (8 de enero de 2020). "Rendezvous Hashing" . Medio . Consultado el 29 de marzo de 2021 .
- ^ Mayank, Anup; Ravishankar, Chinya (2006). "Apoyo a las comunicaciones de dispositivos móviles en presencia de servidores de difusión" (PDF) . Revista internacional de redes de sensores . 2 (1/2): 9–16. doi : 10.1504 / IJSNET.2007.012977 .
- ^ Guo, Danhua; Bhuyan, Laxmi; Liu, Bin (octubre de 2012). "Un eficiente diseño de filtro L7 paralelizado para servidores multinúcleo". Transacciones IEEE / ACM sobre redes . 20 (5): 1426–1439. doi : 10.1109 / TNET.2011.2177858 .
- ^ a b Wang, Peng; Ravishankar, Chinya (2015). "Clave endosar y clave ataques Robo en Redes de Sensores ' " (PDF) . Revista internacional de redes de sensores .
- ^ Mukherjee, Niloy; et al. (Agosto de 2015). "Arquitectura distribuida de Oracle Database In-memory". Actas de la Dotación VLDB . 8 (12): 1630–1641. doi : 10.14778 / 2824032.2824061 .
- ^ Blazevic, Ljubica. "Distributed Core Multicast (DCM): un protocolo de enrutamiento para muchos grupos pequeños con aplicación a la telefonía IP móvil" . Borrador del IETF . IETF . Consultado el 17 de septiembre de 2013 .
- ^ Fenner, B. "Protocolo de multidifusión independiente - Modo disperso (PIM-SM): Especificación de protocolo (revisada)" . IETF RFC . IETF . Consultado el 17 de septiembre de 2013 .
- ^ a b Valloppillil, Vinod; Kenneth Ross. "Protocolo de enrutamiento de matriz de caché v1.0" . Borrador de Internet . Consultado el 15 de septiembre de 2013 .
- ^ "Protocolo de enrutamiento de matriz de caché y Microsoft Proxy Server 2.0" (PDF) . Microsoft. Archivado desde el original (PDF) el 18 de septiembre de 2014 . Consultado el 15 de septiembre de 2013 .
- ^ DeCandia, G .; Hastorun, D .; Jampani, M .; Kakulapati, G .; Lakshman, A .; Pilchin, A .; Sivasubramanian, S .; Vosshall, P .; Vogels, W. (2007). "Dynamo: Tienda de valor-clave de alta disponibilidad de Amazon" (PDF) . Actas del 21º Simposio de ACM sobre principios de sistemas operativos . doi : 10.1145 / 1323293.1294281 . Consultado el 7 de junio de 2018 .
- ^ a b c Jason Resch. "Nuevos algoritmos hash para almacenamiento de datos" (PDF) .
- ^ Sage A. Weil; et al. "CRUSH: Colocación controlada, escalable y descentralizada de datos replicados" (PDF) . Archivado desde el original (PDF) el 20 de febrero de 2019.
- ^ RJ Honicky, Ethan L. Miller. "Replicación bajo hash escalable: una familia de algoritmos para distribución de datos descentralizada escalable" (PDF) .
- ^ Ceph. "Crush Maps" .
- ^ Yao, Zizhen; Ravishankar, Chinya; Tripathi, Satish (13 de mayo de 2001). Jerarquías virtuales basadas en hash para el almacenamiento en caché en redes híbridas de entrega de contenido (PDF) . Riverside, CA: Departamento de CSE, Universidad de California, Riverside . Consultado el 15 de noviembre de 2015 .
- ^ Wang, Wei; Chinya Ravishankar (enero de 2009). "Jerarquías virtuales basadas en hash para servicio de ubicación escalable en redes móviles ad-hoc". Aplicaciones y redes móviles . 14 (5): 625–637. doi : 10.1007 / s11036-008-0144-3 .
- ^ Mayank, Anup; Phatak, Trivikram; Ravishankar, Chinya (2006), Coordinación descentralizada basada en hash de cachés multimedia distribuidos (PDF) , Proc. 5a Conferencia Internacional sobre Redes de IEEE (ICN'06), Mauricio: IEEE
- ^ Christian Schindelhauer, Gunnar Schomaker (2005). "Tablas hash distribuidas ponderadas": 218. CiteSeerX 10.1.1.414.9353 . Cite journal requiere
|journal=
( ayuda )
enlaces externos
- Rendezvous Hashing: una alternativa al hash consistente