Algoritmo
El hashing consistente reparte claves entre servidores para que añadir o quitar un nodo solo mueva las claves necesarias; se usa en cachés y almacenes.
El hashing consistente es una forma de repartir claves entre muchos servidores, propuesta por Karger y colaboradores en 1997 para cachés web distribuidas. Trata el espacio de hash como un anillo, coloca servidores y claves sobre él y asigna cada clave al primer servidor que se encuentra en el sentido de las agujas del reloj. Dar a cada servidor varios puntos en el anillo, llamados nodos virtuales, equilibra la carga.
Con hash(key) % N, cambiar el número de servidores reubica casi todas las claves: la tasa de aciertos de la caché se desploma y hay que mover enormes volúmenes de datos. El hashing consistente mueve de media solo 1/(N+1) de las claves al añadir un servidor, y solo hacia el nuevo, así que el clúster puede crecer y encogerse en funcionamiento. Ketama en los clientes de Memcached, el artículo de Dynamo de Amazon, Cassandra y las opciones de hash consistente de Nginx y HAProxy se basan en esta idea.
Empieza calculando cuántas claves mueve el sharding mod-N y luego implementa un anillo de hash con un arreglo ordenado y búsqueda binaria. Después mide cómo se reduce la dispersión de la carga al añadir nodos virtuales y compara la selección de réplicas, el hashing de rendezvous y el jump consistent hash. Con esa base podrás explicar los compromisos con claridad en entrevistas de diseño de sistemas.
Añadir o quitar un nodo mueve en promedio cerca de 1/(N+1) de las claves, y los nodos existentes nunca intercambian claves entre sí.
El espacio de hash es un círculo y una clave pertenece al primer nodo en sentido horario. La consulta es una búsqueda binaria sobre posiciones ordenadas.
Varios puntos por nodo reducen el desequilibrio de carga, y su número expresa diferencias de capacidad entre servidores.
Las réplicas van a los siguientes R nodos distintos en sentido horario; el hashing de rendezvous y el jump hash logran el mismo objetivo de otra forma.
Los primeros 8 bytes de un resumen MD5 sirven como posición en el anillo, y cada nodo recibe 100 nodos virtuales insertados en una lista ordenada con bisect.insort. get usa bisect_left para hallar el primer punto en la posición de la clave o después y vuelve al principio al pasar del final. Añadir el nodo D mueve solo alrededor de una cuarta parte de las claves, y al quitarlo cada clave regresa a su nodo original.
consistent_hashing.py
import bisect
import hashlib
def h(key: str) -> int:
return int.from_bytes(hashlib.md5(key.encode()).digest()[:8], "big")
class HashRing:
def __init__(self, nodes=(), vnodes=100):
self.vnodes = vnodes
self.points = [] # sorted hash positions on the ring
self.owner = {} # position -> physical node
for node in nodes:
self.add(node)
def add(self, node):
for i in range(self.vnodes):
p = h(f"{node}#{i}")
bisect.insort(self.points, p)
self.owner[p] = node
def remove(self, node):
for i in range(self.vnodes):
p = h(f"{node}#{i}")
self.points.pop(bisect.bisect_left(self.points, p))
del self.owner[p]
def get(self, key):
if not self.points:
raise LookupError("ring is empty")
i = bisect.bisect_left(self.points, h(key)) % len(self.points)
return self.owner[self.points[i]]
ring = HashRing(["A", "B", "C"])
keys = [f"user:{n}" for n in range(10_000)]
before = {k: ring.get(k) for k in keys}
ring.add("D")
moved = sum(before[k] != ring.get(k) for k in keys)
print(f"moved {moved / len(keys):.1%} of keys") # about 25%
ring.remove("D")
print(all(ring.get(k) == before[k] for k in keys)) # True
python consistent_hashing.pySeis capítulos que te llevan desde la instalación hasta las ideas clave de Hashing consistente.
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Hashing consistente.
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.