Nos últimos anos, com o advento de conceitos como computação em nuvem e grandes dados, os sistemas distribuídos ganharam popularidade e relevância.
Um tal tipo de sistema, caches distribuídos que alimentam muitos sites dinâmicos de alto tráfego e aplicativos web, normalmente consistem de um caso particular de hashing distribuído. Estes tiram vantagem de um algoritmo conhecido como hashing consistente.
O que é um hashing consistente? Qual é a motivação por trás disso, e porque você deve se importar?
Neste artigo, vou primeiro rever o conceito geral de hashing e seu propósito, seguido por uma descrição do hashing distribuído e os problemas que ele implica. Por sua vez, isso nos levará ao nosso assunto do título.
O que é hashing?
O que é o “hashing”? Merriam-Webster define o substantivo hash como “carne picada misturada com batatas e dourada”, e o verbo como “cortar (como carne e batatas) em pedaços pequenos”. Então, detalhes culinários à parte, hash significa aproximadamente “cortar e misturar” – e é precisamente de onde vem o termo técnico.
Uma função de hash é uma função que mapeia um pedaço de dado descrevendo tipicamente algum tipo de objeto, muitas vezes de tamanho arbitrário – para outro pedaço de dado, tipicamente um inteiro, conhecido como código de hash, ou simplesmente hash.
Por exemplo, alguma função hash projetada para hash strings, com um intervalo de saída de 0 .. 100, pode mapear a string Hello para, digamos, o número 57, Hasta la vista, baby para o número 33, e qualquer outra string possível para algum número dentro desse intervalo. Como há muito mais entradas possíveis do que saídas, qualquer dado número terá muitas cordas diferentes mapeadas para ele, um fenômeno conhecido como colisão. Boas funções de hash devem de alguma forma “cortar e misturar” (daí o termo) os dados de entrada de tal forma que as saídas para diferentes valores de entrada sejam espalhadas o mais uniformemente possível pela faixa de saída.
Funções de hash têm muitos usos e para cada uma, diferentes propriedades podem ser desejadas. Há um tipo de função de hash conhecida como funções de hash criptográficas, que devem atender a um conjunto restritivo de propriedades e são utilizadas para fins de segurança – incluindo aplicações como proteção por senha, verificação de integridade e impressão digital de mensagens e detecção de corrupção de dados, entre outras, mas estas estão fora do escopo deste artigo.
As funções de hash não criptográficas também têm vários usos, sendo o mais comum o seu uso em tabelas de hash, que é o que nos preocupa e que vamos explorar com mais detalhes.
Introdução de tabelas de hash (Hash Maps)
Imagine que precisávamos manter uma lista de todos os membros de algum clube enquanto podíamos procurar por qualquer membro específico. Poderíamos tratar disso mantendo a lista em um array (ou lista ligada) e, para realizar uma pesquisa, iterar os elementos até encontrarmos o desejado (podemos estar pesquisando com base no nome deles, por exemplo). No pior caso, isso significaria verificar todos os membros (se o que estamos procurando é o último, ou não está presente), ou metade deles, em média. Em termos da teoria da complexidade, a pesquisa teria então complexidade O(n), e seria razoavelmente rápida para uma lista pequena, mas seria cada vez mais lenta na proporção direta do número de membros.
Como isso poderia ser melhorado? Vamos supor que todos esses sócios do clube tinham um sócio ID, que por acaso era um número seqüencial refletindo a ordem na qual eles se juntaram ao clube.
Partindo do princípio de que a busca por ID era aceitável, poderíamos colocar todos os sócios em um array, com seus índices correspondentes aos seus IDs (por exemplo, um sócio com ID=10 estaria no índice 10 no array). Isto nos permitiria acessar cada membro diretamente, sem nenhuma busca. Isso seria muito eficiente, na verdade, tão eficiente quanto possível, correspondendo à menor complexidade possível, O(1), também conhecido como tempo constante.
Mas, reconhecidamente, o nosso sócio do clube ID cenário é de certa forma elaborado. E se IDs fossem números grandes, não seqüenciais ou aleatórios? Ou, se a busca por ID não fosse aceitável, e precisássemos procurar pelo nome (ou algum outro campo) em vez disso? Seria certamente útil manter nosso acesso direto rápido (ou algo próximo) e ao mesmo tempo ser capaz de lidar com conjuntos de dados arbitrários e critérios de busca menos restritivos.
Aqui onde as funções de hash vêm em socorro. Uma função de hash adequada pode ser usada para mapear um dado arbitrário para um número inteiro, que desempenhará um papel similar ao de um membro do nosso clube ID, embora com algumas diferenças importantes.
Primeiro, uma boa função de hash geralmente tem uma ampla faixa de saída (tipicamente, toda a faixa de um número inteiro de 32 ou 64 bits), então construir uma matriz para todos os índices possíveis seria ou impraticável ou simplesmente impossível, e um colossal desperdício de memória. Para superar isso, nós podemos ter um array de tamanho razoável (digamos, apenas o dobro do número de elementos que esperamos armazenar) e realizar uma operação modulada no hash para obter o índice do array. Então, o índice seria index = hash(object) mod N, onde N é o tamanho do array.
Segundo, os hashes de objeto não serão únicos (a menos que estejamos trabalhando com um conjunto de dados fixo e uma função de hash perfeita construída sob medida, mas não discutiremos isso aqui). Haverá colisões (aumentadas ainda mais pela operação do módulo), e portanto um simples acesso direto ao índice não funcionará. Há várias maneiras de lidar com isso, mas uma típica é anexar uma lista, comumente conhecida como balde, a cada índice de array para manter todos os objetos compartilhando um dado índice.
Então, temos um array de tamanho N, com cada entrada apontando para um balde de objeto. Para adicionar um novo objeto, precisamos calcular o seu hash modulo N, e verificar o balde no índice resultante, adicionando o objeto se ele ainda não estiver lá. Para procurar um objeto, fazemos o mesmo, basta olhar para o balde para verificar se o objeto está lá. Tal estrutura é chamada de tabela de hash, e embora as buscas dentro dos baldes sejam lineares, uma tabela de hash de tamanho adequado deve ter um número razoavelmente pequeno de objetos por balde, resultando em um acesso de tempo quase constante (uma complexidade média de O(N/k), onde k é o número de baldes).
Com objetos complexos, a função de hash normalmente não é aplicada ao objeto inteiro, mas sim a uma chave. No nosso exemplo de membro do clube, cada objeto pode conter vários campos (como nome, idade, endereço, e-mail, telefone), mas poderíamos escolher, digamos, o e-mail para agir como a chave para que a função de hash fosse aplicada apenas ao e-mail. Na verdade, a chave não precisa ser parte do objeto; é comum armazenar pares chave/valor, onde a chave é geralmente uma string relativamente curta, e o valor pode ser uma peça arbitrária de dados. Nesses casos, a tabela de hash ou mapa de hash é usada como um dicionário, e é assim que algumas linguagens de alto nível implementam objetos ou arrays associativos.
Scaling Out: Distributed Hashing
Agora que discutimos hashing, estamos prontos para analisar o hashing distribuído.
Em algumas situações, pode ser necessário ou desejável dividir uma tabela de hash em várias partes, hospedadas por servidores diferentes. Uma das principais motivações para isso é contornar as limitações de memória do uso de um único computador, permitindo a construção de tabelas de hash arbitrariamente grandes (com servidores suficientes).
Em tal cenário, os objetos (e suas chaves) são distribuídos entre vários servidores, daí o nome.
Um caso típico de uso para isso é a implementação de caches in-memory, como Memcached.
Estas configurações consistem em um pool de servidores de cache que hospedam muitos pares de chaves/valor e são usados para fornecer acesso rápido aos dados originalmente armazenados (ou computados) em outro lugar. Por exemplo, para reduzir a carga em um servidor de banco de dados e ao mesmo tempo melhorar o desempenho, uma aplicação pode ser projetada para primeiro buscar dados dos servidores de cache, e somente se ela não estiver presente – uma situação conhecida como cache miss-resortar para o banco de dados, executando a consulta relevante e cacheando os resultados com uma chave apropriada, para que ela possa ser encontrada da próxima vez que for necessária.
Agora, como ocorre a distribuição? Que critérios são usados para determinar quais chaves hospedar em quais servidores?
A maneira mais simples é pegar o módulo hash do número de servidores. Ou seja, server = hash(key) mod N, onde N é o tamanho do pool. Para armazenar ou recuperar uma chave, o cliente primeiro calcula o hash, aplica uma operação modulo N, e usa o índice resultante para contatar o servidor apropriado (provavelmente usando uma tabela de busca de endereços IP). Note que a função hash usada para distribuição de chaves deve ser a mesma em todos os clientes, mas não precisa ser a mesma usada internamente pelos servidores de cache.
Vejamos um exemplo. Digamos que temos três servidores, A, B e C, e temos algumas chaves de string com seus hashes:
| KEY | HASH | HASH mod 3 |
|---|---|---|
| “john” | 1633428562 | 2 |
| “factura” | 7594634739 | 0 |
| “cana” | 5000799124 | 1 |
| “steve” | 9787173343 | 0 |
| “kate” | 3421657995 | 2 |
Um cliente quer recuperar o valor da chave john. O seu hash modulo 3 é 2, por isso deve contactar o servidor C. A chave não é encontrada lá, então o cliente vai buscar os dados da fonte e adiciona-os. O pool fica assim:
| A | B | C |
|---|---|---|
| “john” |
Próximo outro cliente (ou o mesmo) quer recuperar o valor da chave bill. O seu hash modulo 3 é 0, por isso deve contactar o servidor A. A chave não é encontrada lá, então o cliente vai buscar os dados da fonte e adiciona-os. O pool tem este aspecto agora:
| A | B | C |
|---|---|---|
| “bill” | “john” |
Após as chaves restantes serem adicionadas, o pool tem este aspecto:
| A | B | C |
|---|---|---|
| “bill” | “jane” | “john” |
| “steve” | “kate” |
O Problema de Reabastecimento
Este esquema de distribuição é simples, intuitivo, e funciona bem. Ou seja, até o número de servidores mudar. O que acontece se um dos servidores falhar ou ficar indisponível? As chaves precisam ser redistribuídas para contabilizar o servidor que falta, é claro. O mesmo se aplica se um ou mais servidores novos forem adicionados ao pool; as chaves precisam ser redistribuídas para incluir os novos servidores. Isto é verdade para qualquer esquema de distribuição, mas o problema com a nossa simples distribuição modulada é que quando o número de servidores muda, a maioria hashes modulo N mudará, por isso a maioria das chaves terá de ser movida para um servidor diferente. Portanto, mesmo que um único servidor seja removido ou adicionado, todas as chaves provavelmente precisarão ser mudadas de novo para um servidor diferente.
Do nosso exemplo anterior, se removêssemos o servidor C, teríamos que refazer ohash de todas as chaves usando hash modulo 2 ao invés de hash modulo 3, e as novas localizações para as chaves se tornariam:
| KEY | HASH | HASH mod 2 | ||
|---|---|---|---|---|
| “john” | 1633428562 | 0 | ||
| “factura” | 7594634739 | 1 | ||
| “cana” | 5000799124 | 0 | ||
| “steve” | 9787173343 | 1 | ||
| “kate” | 3421657995 | 1 |
| A | B |
|---|---|
| “john” | “bill” |
| “jane” | “steve” |
| “kate” |
Nota que todos os locais-chave mudaram, não só os do servidor C.
No caso típico de uso mencionado anteriormente (cache), isto significaria que, de repente, as chaves não serão encontradas porque ainda não estarão presentes em sua nova localização.
Então, a maioria das consultas resultará em falhas, e os dados originais provavelmente precisarão ser recuperados novamente da fonte a ser refazida, colocando assim uma carga pesada no(s) servidor(es) de origem (tipicamente uma base de dados). Isto pode muito bem degradar o desempenho severamente e possivelmente travar os servidores de origem.
A Solução: Hashing Consistente
Então, como este problema pode ser resolvido? Precisamos de um esquema de distribuição que não dependa diretamente do número de servidores, para que, ao adicionar ou remover servidores, o número de chaves que precisam ser realocadas seja minimizado. Um desses esquemas – um esquema inteligente, mas surpreendentemente simples – é chamado de hashing consistente, e foi descrito pela primeira vez por Karger et al. no MIT em um artigo acadêmico de 1997 (de acordo com a Wikipedia).
Consistent Hashing é um esquema de hashing distribuído que opera independentemente do número de servidores ou objetos em uma tabela de hash distribuído, atribuindo-lhes uma posição em um círculo abstrato, ou anel de hash. Isto permite que servidores e objetos sejam escalados sem afetar o sistema em geral.
Imagine que nós mapeamos o intervalo de saída do hash para a borda de um círculo. Isso significa que o valor mínimo possível de hash, zero, corresponderia a um ângulo de zero, o valor máximo possível (algum inteiro grande que chamaremos INT_MAX) corresponderia a um ângulo de 2𝝅 radians (ou 360 graus), e todos os outros valores de hash caberiam linearmente em algum lugar no meio. Então, poderíamos pegar uma chave, calcular seu hash, e descobrir onde ele se encontra na borda do círculo. Assumindo um INT_MAX de 1010 (por exemplo), as chaves do nosso exemplo anterior seriam parecidas com isto:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| “john” | 1633428562 | 58.8 |
| “factura” | 7594634739 | 273.4 |
| “jane” | 5000799124 | 180 |
| “steve” | 9787173343 | 352.3 |
| “kate” | 3421657995 | 123.2 |
Agora imagine que também colocamos os servidores na borda do círculo, atribuindo-lhes também ângulos pseudo-aleatórios. Isto deve ser feito de forma repetitiva (ou pelo menos de forma que todos os clientes concordem com os ângulos dos servidores). Uma maneira conveniente de fazer isso é hashing o nome do servidor (ou endereço IP, ou algum ID) – como nós faríamos com qualquer outra chave – para chegar ao seu ângulo.
No nosso exemplo, as coisas podem se parecer com isto:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| “john” | 1633428562 | 58.8 |
| “factura” | 7594634739 | 273.4 |
| “jane” | 5000799124 | 180 |
| “steve” | 9787173343 | 352.3 |
| “kate” | 3421657995 | 123.2 |
| “A” | 5572014558 | 200.6 |
| “B” | 8077113362 | 290.8 |
| “C” | 2269549488 | 81.7 |
Desde que tenhamos as chaves tanto para os objectos como para os servidores no mesmo círculo, podemos definir uma regra simples para associar o primeiro ao segundo: Cada chave de objeto pertencerá ao servidor cuja chave estiver mais próxima, no sentido anti-horário (ou no sentido horário, dependendo das convenções utilizadas). Em outras palavras, para descobrir qual servidor pedir uma determinada chave, precisamos localizar a chave no círculo e mover no sentido do ângulo ascendente até encontrarmos um servidor.
No nosso exemplo:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| “john” | 1633428562 | 58.7 |
| “C” | 2269549488 | 81.7 |
| “kate” | 3421657995 | 123.1 |
| “jane” | 5000799124 | 180 |
| “A” | 5572014557 | 200.5 |
| “factura” | 7594634739 | 273.4 |
| “B” | 8077113361 | 290.7 |
| “steve” | 787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| “john” | 1632929716 | 58.7 | “C” | C |
| “kate” | 3421831276 | 123.1 | “A” | A |
| “jane” | 5000648311 | 180 | “A” | A |
| “conta” | 7594873884 | 273.4 | “B” | B |
| “steve” | 9786437450 | 352.3 | “C” | C |
De uma perspectiva de programação, o que faríamos é manter uma lista ordenada de valores do servidor (que poderiam ser ângulos ou números em qualquer intervalo real), e caminhar nesta lista (ou usar uma busca binária) para encontrar o primeiro servidor com um valor maior ou igual ao da chave desejada. Se nenhum valor desse tipo for encontrado, precisamos nos enrolar, pegando o primeiro da lista.
Para garantir que as chaves dos objetos sejam distribuídas uniformemente entre os servidores, precisamos aplicar um truque simples: atribuir não uma, mas muitas etiquetas (ângulos) para cada servidor. Assim, em vez de termos etiquetas A, B e C, poderíamos ter, digamos, A0 .. A9, B0 .. B9 e C0 .. C9, todas intercaladas ao longo do círculo. O fator pelo qual aumentar o número de etiquetas (chaves do servidor), conhecido como peso, depende da situação (e pode até ser diferente para cada servidor) para ajustar a probabilidade de as chaves acabarem em cada uma delas. Por exemplo, se o servidor B fosse duas vezes mais potente que o resto, poderia ser-lhe atribuído o dobro de etiquetas, e como resultado, acabaria por conter o dobro de objectos (em média).
Para o nosso exemplo vamos assumir que os três servidores têm um peso igual a 10 (isto funciona bem para três servidores, para 10 a 50 servidores, um peso na faixa de 100 a 500 funcionaria melhor, e pools maiores podem precisar de pesos ainda maiores):
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| “C6” | 408965526 | 14.7 |
| “A1” | 473914830 | 17 |
| “A2” | 548798874 | 19.7 |
| “A3” | 1466730567 | 52.8 |
| “C4” | 1493080938 | 53.7 |
| “john” | 1633428562 | 58.7 |
| “B2” | 1808009038 | 65 |
| “C0” | 1982701318 | 71.3 |
| “B3” | 2058758486 | 74.1 |
| “A7” | 2162578920 | 77.8 |
| “B4” | 2660265921 | 95.7 |
| “C9” | 3359725419 | 120.9 |
| “kate” | 3421657995 | 123.1 |
| “A5” | 3434972143 | 123.6 |
| “C1” | 3672205973 | 132.1 |
| “C8” | 3750588567 | 135 |
| “B0” | 4049028775 | 145.7 |
| “B8” | 4755525684 | 171.1 |
| “A9” | 4769549830 | 171.7 |
| “jane” | 5000799124 | 180 |
| “C7” | 5014097839 | 1808>180.5 |
| “B1” | 5444659173 | 196 |
| “A6” | 6210502707 | 223.5 |
| “A0” | 6511384141 | 234.4 |
| “B9” | 7292819872 | 262.5 |
| “C3” | 7330467663 | 263.8 |
| “C5” | 7502566333 | 270 |
| “factura” | 7594634739 | 273.4 |
| “A4” | 8047401090 | 289.7 |
| “C2” | 8605012288 | 309.7 |
| “A8” | 8997397092 | 323.9 |
| “B7” | 9038880553 | 325.3 |
| “B5” | 9368225254 | 337.2 |
| “B6” | 9379713761 | 337.6 |
| “steve” | 9787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| “john” | 1632929716 | 58.7 | “B2” | B |
| “kate” | 3421831276 | 123.1 | “A5” | A |
| “jane” | 5000648311 | 180 | “C7” | C |
| “conta” | 7594873884 | 273.4 | “A4” | A |
| “steve” | 9786437450 | 352.3 | “C6” | C |
Então, qual é o benefício de toda esta abordagem de círculo? Imagine que o servidor C é removido. Para explicar isto, devemos remover as etiquetas C0 .. C9 do círculo. Isto resulta em que as chaves de objetos anteriormente adjacentes às etiquetas deletadas agora são aleatoriamente etiquetadas Ax e Bx, reatribuindo-as aos servidores A e B.
Mas o que acontece com as outras chaves de objetos, as que originalmente pertenciam em A e B? Nada! Essa é a beleza disso: A ausência de Cx etiquetas não afecta essas chaves de forma alguma. Então, remover um servidor resulta na atribuição aleatória das suas chaves-objecto ao resto dos servidores, deixando todas as outras chaves intocadas:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| “A1” | 473914830 | 17 |
| “A2” | 548798874 | 19.7 |
| “A3” | 1466730567 | 52.8 |
| “john” | 1633428562 | 58.7 |
| “B2” | 1808009038 | 65 |
| “B3” | 2058758486 | 74.1 |
| “A7” | 2162578920 | 77.8 |
| “B4” | 2660265921 | 95.7 |
| “kate” | 3421657995 | 123.1 |
| “A5” | 3434972143 | 123.6 |
| “B0” | 4049028775 | 145.7 |
| “B8” | 4755525684 | 171.1 |
| “A9” | 4769549830 | 171.7 |
| “jane” | 5000799124 | 180 |
| “B1” | 5444659173 | 196 |
| “A6” | 6210502707 | 223.5 |
| “A0” | 6511384141 | 234.4 |
| “B9” | 7292819872 | 262.5 |
| “b9” | 7594634739 | 273.4 |
| “A4” | 8047401090 | 289.7 |
| “A8” | 8997397092 | 323.9 |
| “B7” | 9038880553 | 325.3 |
| “B5” | 9368225254 | 337.2 |
| “B6” | 9379713761 | 337.6 |
| “steve” | 9787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| “john” | 1632929716 | 58.7 | “B2” | B |
| “kate” | 3421831276 | 123.1 | “A5” | A |
| “jane” | 5000648311 | 180 | “B1” | B |
| “factura” | 7594873884 | 273.4 | “A4” | A |
| “steve” | 9786437450 | 352.3 | “A1” | A |
Algo semelhante acontece se, em vez de removermos um servidor, adicionarmos um. Se quiséssemos adicionar servidor D ao nosso exemplo (digamos, como um substituto para C), teríamos de adicionar etiquetas D0 .. D9. O resultado seria que aproximadamente um terço das chaves existentes (todas pertencentes a A ou B) seriam reatribuídas a D, e, novamente, o resto permaneceria o mesmo:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| “D2” | 439890723 | 15.8 |
| “A1” | 473914830 | 17 |
| “A2” | 548798874 | 19.7 |
| “D8” | 796709216 | 28.6 |
| “D1” | 1008580939 | 36.3 |
| “A3” | 1466730567 | 52,8 |
| “D5” | 1587548309 | 57.1 |
| “john” | 1633428562 | 58.7 |
| “B2” | 1808009038 | 65 |
| “B3” | 2058758486 | 74.1 |
| “A7” | 2162578920 | 77.8 |
| “B4” | 2660265921 | 95.7 |
| “D4” | 2909395217 | 104.7 |
| “kate” | 3421657995 | 123.1 |
| “A5” | 3434972143 | 123.6 |
| “D7” | 3567129743 | 128.4 |
| “B0” | 4049028775 | 145.7 |
| “B8” | 4755525684 | 171.1 |
| “A9” | 4769549830 | 171.7 |
| “jane” | 5000799124 | 180 |
| “B1” | 5444659173 | 196 |
| “D6” | 5703092354 | 205.3 |
| “A6” | 6210502707 | 223.5 |
| “A0” | 6511384141 | 234.4 |
| “B9” | 7292819872 | 262.5 |
| “b9” | 7594634739 | 273.4 |
| “A4” | 8047401090 | 289.7 |
| “D0” | 8272587142 | 297.8 |
| “A8” | 8997397092 | 323.9 |
| “B7” | 9038880553 | 325.3 |
| “D3” | 9048608874 | 325.7 |
| “D9” | 9314459653 | 335.3 |
| “B5” | 9368225254 | 337.2 |
| “B6” | 9379713761 | 337.6 |
| “steve” | 9787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| “john” | 1632929716 | 58.7 | “B2” | B |
| “kate” | 3421831276 | 123.1 | “A5” | A |
| “jane” | 5000648311 | 180 | “B1” | B |
| “factura” | 7594873884 | 273.4 | “A4” | A |
| “steve” | 9786437450 | 352.3 | “D2” | D |
É esta a consistência do hashing que resolve o problema do rehashing.
Em geral, apenas k/N chaves precisam ser remapeadas quando k é o número de chaves e N é o número de servidores (mais especificamente, o máximo do número inicial e final de servidores).
Observamos que ao usar o cache distribuído para otimizar o desempenho, pode acontecer que o número de servidores de cache mude (as razões para isso podem ser uma falha do servidor, ou a necessidade de adicionar ou remover um servidor para aumentar ou diminuir a capacidade geral). Utilizando hashing consistente para distribuir chaves entre os servidores, podemos ter certeza de que, se isso acontecer, o número de chaves a serem reajustadas – e portanto, o impacto nos servidores de origem – será minimizado, evitando possíveis paradas ou problemas de desempenho.
Existem clientes para vários sistemas, tais como Memcached e Redis, que incluem suporte para hashing consistente fora da caixa.
Alternativamente, você mesmo pode implementar o algoritmo, na sua linguagem de escolha, e isso deve ser relativamente fácil uma vez que o conceito seja compreendido.
Se a ciência dos dados lhe interessa, Toptal tem alguns dos melhores artigos sobre o assunto no blog