Hispanopedia Wiki
Articulo de referencia

Hashing de encuentro

Hashing de encuentro con n=12, k=4. Los clientes C 1 y C 4 eligen independientemente el mismo subconjunto aleatorio de cuatro sitios {S 2 , S 5 , S 6 , S 10 } de entre las doce ...

Hispanopedia WikiContenido en espanolLectura gratuita
Hashing de encuentro con n=12, k=4. Los clientes C 1 y C 4 eligen independientemente el mismo subconjunto aleatorio de cuatro sitios {S 2 , S 5 , S 6 , S 10 } de entre las doce opciones S 1 , S 2 , ..., S 12 , para colocar réplicas o partes del objeto O.

El hash de encuentro o de peso aleatorio más alto (HRW) [ 1 ] [ 2 ] es un algoritmo que permite a los clientes lograr un acuerdo distribuido sobre un conjunto dek{\displaystyle k}opciones de un conjunto posible denorte{\displaystyle n}opciones. Una aplicación típica se da cuando los clientes necesitan ponerse de acuerdo sobre a qué sitios (o proxies) se asignan los objetos.

El hash consistente aborda el caso especial k=1{\displaystyle k=1}utilizando un método diferente. El hash Rendezvous es mucho más simple y general que el hash consistente (ver más abajo).

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 está prefiriendo al hash consistente en aplicaciones del mundo real. [ 3 ] [ 4 ] [ 5 ] El hash de encuentro se utilizó muy pronto en muchas aplicaciones, incluyendo el almacenamiento en caché móvil, [ 6 ] el diseño de enrutadores, [ 7 ] el establecimiento seguro de claves , [ 8 ] y el sharding y las bases de datos distribuidas . [ 9 ] Otros ejemplos de sistemas del mundo real que utilizan el hash de encuentro incluyen el balanceador de carga de GitHub, [ 10 ] la base de datos distribuida Apache Ignite , [ 11 ] el almacén de archivos Tahoe-LAFS, [ 12 ] el servicio de distribución de archivos grandes CoBlitz, [ 13 ] Apache Druid, [ 14 ] el Cloud Object Store de IBM, [ 15 ] el sistema de gestión de datos Arvados, [ 16 ] Apache Kafka, [ 17 ] y la plataforma pub/sub Twitter EventBus. [ 18 ]

Una de las primeras aplicaciones del hash de encuentro fue permitir que los clientes de multidifusión en Internet (en contextos como MBONE ) identificaran puntos de encuentro de multidifusión de forma distribuida. [ 19 ] [ 20 ] Fue utilizado en 1998 por el Protocolo de enrutamiento de matriz de caché (CARP) de Microsoft para la coordinación y el enrutamiento de caché distribuidos. [ 21 ] [ 22 ] Algunos protocolos de enrutamiento de multidifusión independientes del protocolo utilizan el hash de encuentro para elegir un punto de encuentro. [ 1 ]

Definición del problema y enfoque

Algoritmo

El hash de encuentro resuelve una versión general del problema de la tabla hash distribuida : se nos da un conjunto denorte{\displaystyle n}sitios (servidores o proxies, por ejemplo). ¿Cómo puede cualquier conjunto de clientes, dado un objeto?O{\displaystyle O}, acordar un subconjunto k de sitios para asignar aO{\displaystyle O}La versión estándar del problema utiliza k = 1. Cada cliente debe realizar su selección de forma independiente, pero todos deben terminar eligiendo el mismo subconjunto de sitios. Esto no es trivial si añadimos una restricción de mínima interrupción y exigimos que, cuando un sitio falle o se elimine, solo los objetos que se corresponden con ese sitio deban reasignarse a otros sitios.

La idea básica es darle a cada sitioSj{\displaystyle S_{j}}una puntuación (un peso ) para cada objetoOi{\displaystyle O_{i}}y asignar el objeto al sitio con la puntuación más alta. Todos los clientes primero acuerdan una función hash.h(⋅){\displaystyle h(\cdot )}. Para objetoOi{\displaystyle O_{i}}, el sitioSj{\displaystyle S_{j}}se define para tener pesowi,j=h(Oi,Sj){\displaystyle w_{i,j}=h(O_{i},S_{j})}Cada cliente calcula estos pesos de forma independiente.wi,1,wi,2…wi,norte{\displaystyle w_{i,1},w_{i,2}\dots w_{i,n}}y selecciona los k sitios que producen los k valores hash más grandes. De este modo, los clientes han logrado una distribuciónk{\displaystyle k}-acuerdo.

Si un sitioS{\displaystyle S}se agrega o se elimina, solo los objetos que se asignan aS{\displaystyle S}se reasignan a diferentes sitios, cumpliendo con la restricción de mínima interrupción mencionada anteriormente. La asignación HRW puede ser calculada independientemente por cualquier cliente, ya que depende únicamente de los identificadores del conjunto de sitios.S1,S2…Snorte{\displaystyle S_{1},S_{2}\dots S_{n}}y el objeto que se está asignando.

HRW se adapta fácilmente a diferentes capacidades entre sitios. Si el sitioSk{\displaystyle S_{k}}tiene el doble de capacidad que los otros sitios, simplemente representamosSk{\displaystyle S_{k}}dos veces en la lista, por ejemplo, comoSk,1,Sk,2{\displaystyle S_{k,1},S_{k,2}}. Claramente, ahora se asignará el doble de objetos aSk{\displaystyle S_{k}}en cuanto a los otros sitios.

Propiedades

Consideremos la versión simple del problema, con k = 1, donde todos los clientes deben acordar un único sitio para un objeto O. Si abordamos el problema de forma ingenua, podría parecer suficiente tratar los n sitios como cubetas en una tabla hash y asignar el nombre del objeto O a esta tabla mediante la función hash. Desafortunadamente, si alguno de los sitios falla o es inaccesible, el tamaño de la tabla hash cambia, lo que obliga a reasignar todos los objetos. Esta interrupción masiva hace que este método de hash directo sea inviable.

Sin embargo, bajo el hash de encuentro, los clientes manejan las fallas de los sitios seleccionando el sitio que produce el siguiente peso más alto. El reasignamiento solo es necesario para los objetos actualmente asignados al sitio fallido, y la interrupción es mínima. [ 1 ] [ 2 ]

El hash de encuentro tiene las siguientes propiedades:

  1. Baja sobrecarga: La función hash utilizada es eficiente, por lo que la sobrecarga en los clientes es muy baja.
  2. Balanceo de carga : Dado que la función hash es aleatoria, cada uno de los n sitios tiene la misma probabilidad de recibir el objeto O. Las cargas son uniformes en todos los sitios.
    1. Capacidad del sitio: Los sitios con diferentes capacidades pueden representarse en la lista de sitios con una multiplicidad proporcional a su capacidad. Un sitio con el doble de capacidad que los demás sitios se representará dos veces en la lista, mientras que todos los demás se representarán una sola vez.
  3. Alta tasa de aciertos : Dado que todos los clientes coinciden en colocar un objeto O en el mismo sitio SO , cada recuperación o colocación de O en SO produce la máxima utilidad en términos de tasa de aciertos. El objeto O siempre se encontrará a menos que sea desalojado por algún algoritmo de reemplazo en SO .
  4. Interrupción mínima: Cuando un sitio falla, solo es necesario reasignar los objetos asignados a ese sitio. La interrupción se reduce al mínimo posible. [ 1 ] [ 2 ]
  5. Acuerdo k distribuido : Los clientes pueden llegar a un acuerdo distribuido sobre k sitios simplemente seleccionando los k sitios principales en el ordenamiento. [ 8 ]

Tiempo de ejecución O (log n ) mediante hash de encuentro jerárquico basado en esqueletos

La versión estándar de Rendezvous Hashing descrita anteriormente funciona bastante bien para n moderado, pero cuandonorte{\displaystyle n}es extremadamente grande, el uso jerárquico de Rendezvous Hashing lograO(registro⁡norte){\displaystyle O(\log n)}tiempo de ejecución. [ 23 ] [ 24 ] [ 25 ] Este enfoque crea una estructura jerárquica virtual (llamada "esqueleto") y lograO(registro⁡norte){\displaystyle O(\log n)}tiempo de ejecución aplicando HRW en cada nivel mientras se desciende por la jerarquía. La idea es elegir primero alguna constantemetro{\displaystyle m}y organizar elnorte{\displaystyle n}sitios endo=⌈norte/metro⌉{\displaystyle c=\lceil n/m\rceil }gruposdo1={S1,S2…Smetro},do2={Smetro+1,Smetro+2…S2metro}…{\displaystyle C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots }A continuación, construya una jerarquía virtual eligiendo una constante.F{\displaystyle f}y imaginando estosdo{\displaystyle c}racimos colocados en las hojas de un árbolT{\displaystyle T}de nodos virtuales, cada uno con ramificaciónF{\displaystyle f}.

Se utiliza un esqueleto para lograr un tiempo de ejecución log(n) . Los nodos reales aparecen como cuadrados en el nivel de las hojas. Los nodos virtuales del esqueleto aparecen como círculos punteados. Los clústeres del nivel de las hojas tienen un tamaño m = 4, y el esqueleto tiene un factor de ramificación f = 3.

En el diagrama adjunto, el tamaño del clúster esmetro=4{\displaystyle m=4}y el abanico del esqueleto esF=3{\displaystyle f=3}. Suponiendo 108 sitios (nodos reales) para mayor comodidad, obtenemos una jerarquía virtual de tres niveles. Dado queF=3{\displaystyle f=3}Cada nodo virtual tiene una numeración natural en octal. Por lo tanto, los 27 nodos virtuales del nivel más bajo se numerarían000,001,002,...,221,222{\displaystyle 000,001,002,...,221,222}en octal (por supuesto, podemos variar el factor de ramificación en cada nivel; en ese caso, cada nodo se identificará con el número de base mixta correspondiente).

La forma más sencilla de comprender la jerarquía virtual es comenzar desde la cima y descender por ella. Aplicamos sucesivamente el algoritmo Rendezvous Hashing al conjunto de nodos virtuales en cada nivel de la jerarquía y descendemos por la rama definida por el nodo virtual ganador. De hecho, podemos comenzar en cualquier nivel de la jerarquía virtual. Comenzar en niveles inferiores requiere más operaciones hash, pero puede mejorar la distribución de la carga en caso de fallos.

Por ejemplo, en lugar de aplicar HRW a los 108 nodos reales del diagrama, podemos aplicar primero 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 necesitamos27+4=31{\displaystyle 27+4=31}hashes, en lugar de 108. Si aplicamos este método comenzando un nivel más arriba en la jerarquía, necesitaríamos9+3+4=16{\displaystyle 9+3+4=16}hashes para llegar al sitio ganador. La figura muestra cómo, si procedemos comenzando desde la raíz del esqueleto, podemos elegir sucesivamente los nodos virtuales.(2)3{\displaystyle (2)_{3}},(20)3{\displaystyle (20)_{3}}, y(200)3{\displaystyle (200)_{3}}y finalmente terminamos con el sitio 74.

La jerarquía virtual no necesita almacenarse, sino que puede crearse bajo demanda, ya que los nombres de los nodos virtuales son simplemente prefijos de la base.F{\displaystyle f}(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, trabajaríamos con las cadenas0,1,2{\displaystyle 0,1,2}(en el nivel 1),20,21,22{\displaystyle 20,21,22}(en el nivel 2), y200,201,202{\displaystyle 200,201,202}(en el nivel 3). Claramente,T{\displaystyle T}tiene alturah=O(registro⁡do)=O(registro⁡norte){\displaystyle h=O(\log c)=O(\log n)}, desdemetro{\displaystyle m}yF{\displaystyle f}son ambas constantes. El trabajo realizado en cada nivel esO(1){\displaystyle O(1)}, desdeF{\displaystyle f}es una constante.

El valor demetro{\displaystyle m}se puede elegir en función de factores como la tasa de fallos prevista y el grado de equilibrio de carga deseado. Un valor más alto demetro{\displaystyle m}Esto conlleva una menor asimetría de carga en caso de fallo, a costa de una mayor sobrecarga de búsqueda.

La elecciónmetro=norte{\displaystyle m=n}es equivalente al hash de encuentro no jerárquico. En la práctica, la función hashh(⋅){\displaystyle h(\cdot )}es muy barato, así quemetro=norte{\displaystyle m=n}puede funcionar bastante bien a menos quenorte{\displaystyle n}es muy alto.

Para cualquier objeto dado, está claro que cada grupo de nivel de hoja, y por lo tanto cada uno de losnorte{\displaystyle n}los sitios se eligen con igual probabilidad.

Replicación, fallos de sitio y adición de sitios

Se puede mejorar la resiliencia ante fallos replicando cada objeto O en los r < m sitios de mayor rango para O, eligiendo r en función del nivel de resiliencia deseado. La estrategia más sencilla consiste en replicar únicamente dentro del clúster de nivel hoja.

Si el sitio de nivel hoja seleccionado para O no está disponible, seleccionamos el siguiente sitio con mayor rango dentro del mismo clúster de nivel hoja. Si O se ha replicado dentro del clúster de nivel hoja, seguramente lo encontraremos en el siguiente sitio disponible en el orden de clasificación de los r sitios. Todos los objetos que contenía el servidor fallido aparecen en algún otro sitio de su clúster. (Otra opción es ascender uno o más niveles en el esqueleto y seleccionar un nodo alternativo entre los nodos virtuales hermanos de ese nivel. Luego descendemos por la jerarquía hasta los nodos reales, como se indicó anteriormente).

Cuando se agrega un sitio al sistema, este puede convertirse en el sitio de destino para algunos objetos ya asignados a otros sitios. Los objetos asignados a otros clústeres nunca se asignarán a este nuevo sitio, por lo que solo debemos considerar los objetos que se encuentran en otros sitios de su clúster. Si los sitios son cachés, intentar acceder a un objeto asignado al nuevo sitio resultará en un fallo de caché; el objeto correspondiente se recuperará y se almacenará en caché, y la operación volverá a la normalidad.

Si los sitios son servidores, algunos objetos deben reasignarse a este sitio recién agregado. Como antes, los objetos asignados a otros clústeres nunca se asignarán a este nuevo sitio, por lo que solo debemos considerar los objetos que contienen los sitios de su clúster. Es decir, solo necesitamos reasignar los objetos presentes actualmente en los m sitios de este clúster local, en lugar de todos los objetos del sistema. Los nuevos objetos que se asignen a este sitio se le asignarán automáticamente.

Comparación con el hash consistente

Debido a su simplicidad, menor sobrecarga y generalidad (funciona para cualquier k < n ), el hash de encuentro se está prefiriendo cada vez más al hash consistente. Ejemplos recientes de su uso incluyen el balanceador de carga de GitHub, [ 10 ] la base de datos distribuida Apache Ignite, [ 11 ] y la plataforma pub/sub de Twitter EventBus. [ 18 ]

El hash consistente funciona asignando cada sitio de forma uniforme y aleatoria a múltiples puntos en un círculo unitario llamados tokens. Los objetos también se asignan al círculo unitario y se colocan en el sitio que posee el token que se encuentra primero, siguiendo el sentido horario desde la ubicación del objeto. Cuando se elimina un sitio, cada uno de sus objetos se transfiere al sitio que posee el siguiente token encontrado, siguiendo el sentido horario. Si cada sitio se asigna a un gran número de tokens (entre 100 y 200, por ejemplo), esto reasignará los objetos de forma relativamente uniforme entre los sitios restantes.

Si los tokens de un sitio se colocan en el círculo unitario mediante el hash de 200 variantes del ID del sitio, por ejemplo, la asignación de cualquier objeto requiere almacenar o recalcular 200 valores hash para cada sitio. Sin embargo, los tokens asociados a un sitio determinado pueden precalcularse y almacenarse en una lista ordenada, lo que requiere solo una única aplicación de la función hash al objeto y una búsqueda binaria para calcular la asignación. Aun con muchos tokens por sitio, la versión básica del hash consistente puede no distribuir los objetos de manera uniforme entre los sitios, ya que cuando se elimina un sitio, cada objeto asignado a él se distribuye solo entre tantos otros sitios como tokens tenga el sitio (por ejemplo, entre 100 y 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, además de ofrecer otros beneficios. [ 26 ]

Ventajas del hash Rendezvous sobre el hash consistente

El hash de encuentro (HRW) es mucho más simple conceptualmente y en la práctica. También distribuye los objetos uniformemente en todos los sitios, dada una función hash uniforme. A diferencia del hash consistente, HRW no requiere precomputación ni almacenamiento de tokens. Consideremos k = 1. Un objetoOi{\displaystyle O_{i}}se coloca en uno denorte{\displaystyle n}sitiosS1,S2…Snorte{\displaystyle S_{1},S_{2}\dots S_{n}}mediante el cálculo de lanorte{\displaystyle n}valores hashh(Oi,Sj){\displaystyle h(O_{i},S_{j})}y eligiendo el sitioSk{\displaystyle S_{k}}que produce el valor hash más alto. Si un nuevo sitioSnorte+1{\displaystyle S_{n+1}}Se agregan nuevas colocaciones de objetos o solicitudes que se calcularánnorte+1{\displaystyle n+1}valores hash, y elige el mayor de ellos. Si un objeto ya está en el sistema enSk{\displaystyle S_{k}}Mapas a este nuevo sitioSnorte+1{\displaystyle S_{n+1}}, se recuperará de nuevo y se almacenará en caché enSnorte+1{\displaystyle S_{n+1}}. Todos los clientes lo obtendrán de ahora en adelante desde este sitio, y la copia antigua almacenada en caché enSk{\displaystyle S_{k}}En última instancia, será reemplazado por el algoritmo de gestión de caché local. SiSk{\displaystyle S_{k}}Si se desconecta, sus objetos se reasignarán uniformemente a los restantes.norte−1{\displaystyle n-1}sitios.

Las variantes del algoritmo HRW, como el uso de un esqueleto (ver más abajo), pueden reducir elO(norte){\displaystyle O(n)}tiempo para la ubicación del objetoO(registro⁡norte){\displaystyle O(\log n)}, a costa de una menor uniformidad global en la colocación. Cuandonorte{\displaystyle n}no es demasiado grande, sin embargo, elO(norte){\displaystyle O(n)}Es poco probable que el costo de implementación de HRW básico sea un problema. HRW evita por completo la sobrecarga y la complejidad asociadas con el manejo correcto de múltiples tokens para cada sitio y los metadatos asociados.

El hash de encuentro también tiene la gran ventaja de que proporciona soluciones sencillas a otros problemas importantes, como la distribución.k{\displaystyle k}-acuerdo.

El hash consistente es un caso especial del hash Rendezvous.

El hashing de encuentro es más simple y general que el hashing consistente. Se puede demostrar que el hashing consistente es un caso especial de HRW mediante la elección adecuada de una función hash de dos lugares. A partir del identificador del sitioS{\displaystyle S}La versión más simple del hash consistente calcula una lista de posiciones de tokens, por ejemplo,ts=hdo(S){\displaystyle t_{s}=h_{c}(S)}dóndehdo{\displaystyle h_{c}}asigna valores hash a ubicaciones en el círculo unitario. Defina la función hash de dos lugares.h(S,O){\displaystyle h(S,O)}ser1minS(hdo(O)−ts){\displaystyle {\frac {1}{\min _{S}(h_{c}(O)-t_{s})}}}dóndehdo(O)−ts{\displaystyle h_{c}(O)-t_{s}}denota la distancia a lo largo del círculo unitario desdehdo(O){\displaystyle h_{c}(O)}ats{\displaystyle t_{s}}(desdehdo(O)−ts{\displaystyle h_{c}(O)-t_{s}}tiene algún valor mínimo distinto de cero, no hay problema en traducir este valor a un entero único en algún rango acotado). Esto duplicará exactamente la asignación producida por el hash consistente.

Sin embargo, no es posible reducir HRW a un hash consistente (suponiendo que el número de tokens por sitio sea 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 las claves. Sin embargo, este comportamiento resulta indeseable cuando los nodos tienen capacidades diferentes para procesar o almacenar las 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 lo tuviera en cuenta, de modo que este nodo más potente recibiera el doble de claves que cada uno de los otros.

Un mecanismo sencillo para abordar este caso consiste en asignar dos ubicaciones virtuales a este nodo, de modo que si alguna de las ubicaciones virtuales del nodo más grande tiene el hash más alto, ese nodo recibe la clave. Sin embargo, 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, requeriría añadir muchos nodos virtuales en proporciones diferentes, 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 Protocolo de Enrutamiento de Matriz de Caché (CARP) es un borrador de la IETF de 1998 que describe un método para calcular factores de carga que se pueden multiplicar por la puntuación hash de cada nodo para obtener un nivel arbitrario de precisión para ponderar los nodos de manera diferente. [ 21 ] Sin embargo, una desventaja de este enfoque es que cuando se cambia el peso de cualquier nodo, o cuando se agrega o elimina cualquier nodo, todos los factores de carga deben recalcularse y escalarse de forma relativa. Cuando los factores de carga cambian en relación unos con otros, se produce un movimiento de claves entre nodos cuyo peso no cambió, pero cuyo factor de carga sí cambió en relación con otros nodos del sistema. Esto resulta en un movimiento excesivo de claves. [ 27 ]

Replicación controlada

La replicación controlada bajo hash escalable o CRUSH [ 28 ] es una extensión de RUSH [ 29 ] que mejora el hash de encuentro mediante la construcción de un árbol donde se utiliza una función pseudoaleatoria (hash) para recorrer el árbol y encontrar qué nodo es el responsable de una clave dada. Permite una estabilidad perfecta al añadir nodos; sin embargo, no es perfectamente estable al eliminar o reasignar pesos a los nodos, ya que el movimiento excesivo de claves es proporcional a la altura del árbol.

El algoritmo CRUSH es utilizado por el sistema de almacenamiento de datos Ceph para asignar objetos de datos a los nodos responsables de almacenarlos. [ 30 ]

Otras variantes

En 2005, Christian Schindelhauer y Gunnar Schomaker describieron un método logarítmico para reponderar las puntuaciones 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. [ 31 ] Esto permitió los beneficios duales de una precisión perfecta al ponderar los nodos, junto con una estabilidad perfecta, ya que solo era necesario 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 . [ 27 ]

Sistemas que utilizan el hash de encuentro

El hash de encuentro se utiliza ampliamente en sistemas del mundo real. Una lista parcial incluye la base de datos en memoria de Oracle, [ 9 ] el balanceador de carga de GitHub, [ 10 ] la base de datos distribuida Apache Ignite, [ 11 ] el almacén de archivos Tahoe-LAFS, [ 12 ] el servicio de distribución de archivos grandes CoBlitz, [ 13 ] Apache Druid, [ 14 ] el almacén de objetos en la nube de IBM, [ 15 ] el sistema de gestión de datos Arvados, [ 16 ] Apache Kafka, [ 17 ] y la plataforma pub/sub de Twitter EventBus. [ 18 ]

Implementación

La implementación es sencilla una vez que se tiene una función hash.h(⋅){\displaystyle h(\cdot )}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 losnorte{\displaystyle n}sitios, y luego elige el más grande. Este algoritmo se ejecuta enO(norte){\displaystyle O(n)}tiempo. Si la función hash es eficiente, elO(norte){\displaystyle O(n)}El tiempo de ejecución no es un problema a menos quenorte{\displaystyle n}es muy grande. Se aplica una transformación logarítmica a la puntuación uniforme (intervalo unitario); al multiplicarla por los pesos de los nodos, la probabilidad de que un nodo gane es proporcional a su peso en relación con el peso total de todos los nodos. Cabe destacar que la magnitud de las puntuaciones varía considerablemente, pero las probabilidades permanecen constantes.

Hash de encuentro ponderado

Código Python que implementa un hash de encuentro ponderado: [ 27 ]

import mmh3 import math from dataclasses import dataclassdef hash_to_unit_interval ( s : str ) -> float : """Aplica un hash a una cadena en el intervalo unitario (0, 1]""" return ( mmh3 . hash128 ( s ) + 1 ) / 2 ** 128@dataclass class Node : """Clase que representa un nodo al que se le asignan claves como parte de un hash de encuentro ponderado.""" nombre : str peso : floatdef compute_weighted_score ( self , key : str ) - > float : score : float = hash_to_unit_interval ( f " { self.name } : { key } " ) log_score : float = 1.0 / -math.log ( score ) return self.weight * log_score​​​​​​def determine_responsible_node ( nodes : list [ Node ], key : str ) -> Node : """Determina qué nodo de un conjunto de nodos de diferentes pesos es responsable de la clave proporcionada.""" return max ( nodes , key = lambda node : node . compute_weighted_score ( key ), default = None )

Ejemplos de resultados de WRH:

import wrh from collections import Counter from wrh import Nodenodo1 : Nodo = Nodo ( "nodo1" , 100 ) nodo2 : Nodo = Nodo ( " nodo2" , 200 ) nodo3 : Nodo = Nodo ( "nodo3" , 300 ) print ( str ( wrh.determine_responsible_node ([ nodo1 , nodo2 , nodo3 ], "foo" ) )) # imprime: "Nodo(nombre='nodo1', peso=100)" print ( str ( wrh.determine_responsible_node ([ nodo1 , nodo2 , nodo3 ], "bar" ) ) ) # imprime: "Nodo(nombre='nodo2', peso=300)" print ( str ( wrh.determine_responsible_node ( [ nodo1 , nodo2 , nodo3 ] , "hola" ))) # imprime: "Nodo(nombre='node2', peso=300)" nodos : lista [ Nodo ] = [ nodo1 , nodo2 , nodo3 ] nodos_responsables : lista [ Nodo ] = [ wrh.determinar_nodo_responsable ( nodos , f " clave : { clave } " ) . nombre para clave en rango ( 45_000 )] imprimir ( Contador ( nodos_responsables )) # imprime: Contador({'node3': 22487, 'node2': 15020, 'node1': 7493})

Referencias

  1. 1 2 3 4 5 6 Thaler, David; Chinya Ravishankar. "Un esquema de mapeo basado en nombres para Rendezvous" (PDF) . Informe técnico de la Universidad de Michigan CSE-TR-316-96 . Recuperado el 15 de septiembre de 2013 .
  2. 1 2 3 4 Thaler, David; Chinya Ravishankar (febrero de 1998). "Uso de esquemas de mapeo basados ​​en nombres para aumentar las tasas de aciertos". IEEE/ACM Transactions on Networking . 6 (1): 1– 14. CiteSeerX 10.1.1.416.8943 . doi : 10.1109/90.663936 . S2CID 936134 .  
  3. ↑ "Explicación del hash de encuentro - Randorithms" . randorithms.com . Consultado el 29 de marzo de 2021 .
  4. ↑ "Rendezvous hashing: mi método de distribución "consistente" de referencia - Paul Khuong: algo de Lisp" . pvk.ca. Consultado el 29 de marzo de 2021 .
  5. ^ Aniruddha (8 de enero de 2020). "Encuentro Hashing" . Medio . Consultado el 29 de marzo de 2021 .
  6. ↑ Mayank, Anup; Ravishankar, Chinya (2006). "Soporte para comunicaciones de dispositivos móviles en presencia de servidores de difusión" (PDF) . International Journal of Sensor Networks . 2 (1/2): 9–16 . doi : 10.1504/IJSNET.2007.012977 .
  7. ↑ Guo, Danhua; Bhuyan, Laxmi; Liu, Bin (octubre de 2012). "Un diseño eficiente de filtro L7 paralelizado para servidores multinúcleo". IEEE/ACM Transactions on Networking . 20 (5): 1426– 1439. doi : 10.1109/TNET.2011.2177858 . S2CID 1982193 . 
  8. 1 2 Wang, Peng; Ravishankar, Chinya (2015). "Ataques de suplantación y robo de claves en redes de sensores"" (PDF) . Revista Internacional de Redes de Sensores .
  9. 1 2 Mukherjee, Niloy; et al. (agosto de 2015). "Arquitectura distribuida de Oracle Database In-memory". Actas de la Fundación VLDB . 8 (12): 1630– 1641. doi : 10.14778/2824032.2824061 . 
  10. 1 2 3 GitHub Engineering (22 de septiembre de 2016). "Presentación del balanceador de carga de GitHub" . Blog de GitHub . Consultado el 1 de febrero de 2022 .
  11. 1 2 3 "Apache Ignite" , Wikipedia , 18 de agosto de 2022 , consultado el 9 de diciembre de 2022
  12. ^ " Tahoe -LAFS" . tahoe-lafs.org . Consultado el 2 de enero de 2023 .
  13. 1 2 Park, KyoungSoo; Pai, Vivek S. (2006). "Escala y rendimiento en el servicio de distribución de archivos grandes CoBlitz". Usenix Nsdi .
  14. 1 2 "Proceso de enrutamiento · Apache Druid" . druid.apache.org . Consultado el 2 de enero de 2023 .
  15. 1 2 "IBM Cloud Object Storage System, Versión 3.14.11, Guía de expansión del grupo de almacenamiento" (PDF) . IBM Cloud Object Storage System™ Versión . Consultado el 2 de enero de 2023 .
  16. 1 2 "Arvados | Conservar clientes" . doc.arvados.org . Consultado el 2 de enero de 2023 .
  17. 1 2 "Escalado horizontal de consumidores de Kafka con hash de encuentro" . Tinybird.co . Recuperado el 15 de febrero de 2023 .
  18. ^ Aniruddha ( 8 de enero de 2020). "Encuentro Hashing" . i0excepción . Consultado el 9 de diciembre de 2022 .
  19. ↑ Blazevic, Ljubica (21 de junio de 2000). "Distributed Core Multicast (DCM): un protocolo de enrutamiento para muchos grupos pequeños con aplicación a la telefonía IP móvil" . Borrador de la IETF . IETF . Recuperado el 17 de septiembre de 2013 .
  20. ↑ Fenner, B. (agosto de 2006). "Protocolo independiente de multidifusión - modo disperso (PIM-SM): especificación del protocolo (revisada)" . IETF RFC . IETF . Consultado el 17 de septiembre de 2013 .
  21. 1 2 Valloppillil, Vinod; Kenneth Ross (27 de febrero de 1998). "Protocolo de enrutamiento de matriz de caché v1.0" . Borrador de Internet . Recuperado el 15 de septiembre de 2013 .
  22. ↑ "Protocolo de enrutamiento de matriz de caché y Microsoft Proxy Server 2.0" (PDF) . Microsoft. Archivado del original (PDF) el 18 de septiembre de 2014. Recuperado el 15 de septiembre de 2013 .
  23. ↑ 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. Archivado del original (PDF) el 16 de noviembre de 2020. Recuperado el 15 de noviembre de 2015 .
  24. ↑ Wang, Wei; Chinya Ravishankar (enero de 2009). "Jerarquías virtuales basadas en hash para un servicio de localización escalable en redes móviles ad hoc". Mobile Networks and Applications . 14 (5): 625– 637. doi : 10.1007/s11036-008-0144-3 . S2CID 2802543 . 
  25. ^ Mayank, Anup; Phatak, Trivikram; Ravishankar, Chinya (2006), Coordinación descentralizada basada en hash de cachés multimedia distribuidas (PDF) , Proc. Quinta Conferencia Internacional IEEE sobre Redes (ICN'06), Mauricio: IEEE
  26. ^ DeCandia, G.; Hastorún, D.; Jampani, M.; Kakulapati, G.; Lakshman, A.; Pilchín, A.; Sivasubramanian, S.; Vosshall, P.; Vogels, W. (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 .
  27. 1 2 3 Jason Resch. "Nuevos algoritmos de hash para el almacenamiento de datos" (PDF) .
  28. ↑ Sage A. Weil; et al. "CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data" (PDF) . Archivado del original (PDF) el 20 de febrero de 2019. 
  29. ↑ RJ Honicky, Ethan L. Miller. "Replicación bajo hash escalable: una familia de algoritmos para la distribución descentralizada y escalable de datos" (PDF) . Archivado del original (PDF) el 26 de febrero de 2017. Consultado el 25 de febrero de 2017 .
  30. ↑ Ceph. "Mapas de aplastamiento" .
  31. ↑ Christian Schindelhauer, Gunnar Schomaker (2005). "Tablas hash distribuidas ponderadas": 218. CiteSeerX 10.1.1.414.9353 . {{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
  • Hashing de encuentro: una alternativa al hash consistente