Algoritmo
O hashing consistente distribui chaves entre servidores para que adicionar ou remover um nó mova só as chaves necessárias; é usado em caches e bancos de dados.
Hashing consistente é uma forma de distribuir chaves entre muitos servidores, proposta por Karger e colegas em 1997 para caches web distribuídos. O espaço de hash é tratado como um anel: servidores e chaves são colocados nele, e cada chave pertence ao primeiro servidor encontrado no sentido horário. Dar a cada servidor vários pontos no anel, chamados nós virtuais, equilibra a carga.
Com hash(key) % N, mudar o número de servidores realoca quase todas as chaves: a taxa de acerto do cache despenca e é preciso mover grandes volumes de dados. O hashing consistente move em média só 1/(N+1) das chaves quando um servidor entra, e apenas para o novo servidor, então o cluster pode crescer e encolher em produção. O ketama dos clientes Memcached, o artigo do Dynamo da Amazon, o Cassandra e as opções de hash consistente do Nginx e do HAProxy se baseiam nessa ideia.
Comece calculando quantas chaves o sharding mod-N move e depois implemente um anel de hash com um array ordenado e busca binária. Em seguida, meça como a variação de carga diminui com mais nós virtuais e compare a escolha de réplicas, o rendezvous hashing e o jump consistent hash. Com essa base você consegue explicar as escolhas com clareza em entrevistas de system design.
Adicionar ou remover um nó move em média cerca de 1/(N+1) das chaves, e os nós existentes nunca trocam chaves entre si.
O espaço de hash é um círculo e uma chave pertence ao primeiro nó no sentido horário. A consulta é uma busca binária sobre posições ordenadas.
Vários pontos por nó reduzem o desequilíbrio de carga, e a quantidade de pontos expressa diferenças de capacidade entre servidores.
As réplicas vão para os próximos R nós distintos no sentido horário; o rendezvous hashing e o jump hash chegam ao mesmo objetivo de outro jeito.
Os primeiros 8 bytes de um digest MD5 servem como posição no anel, e cada nó recebe 100 nós virtuais inseridos em uma lista ordenada com bisect.insort. get usa bisect_left para achar o primeiro ponto na posição da chave ou depois dela e volta ao início ao passar do fim. Adicionar o nó D move só cerca de um quarto das chaves, e removê-lo devolve cada chave ao nó 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 levam você da instalação aos conceitos essenciais de Hashing consistente.
Tire dúvidas, compartilhe experiências e troque opiniões sobre Hashing consistente.
Ainda não há discussões. Comece a primeira.
0 comentários
Fazer login · Faça login para deixar um comentário.