Hash consistente é uma técnica de hashing que funciona muito bem quando operada em um ambiente dinâmico onde o sistema distribuído aumenta e diminui com freqüência. O conceito central de Hashing Consistente foi introduzido no papel Hashing Consistente e RandomTrees: Protocolos de Caching Distribuído para Alívio de Hot Spots na World Wide Web, mas ganhou popularidade após o famoso papel que introduziu o DynamoDB – Dynamo: Loja de Valor-Chave de Alta Disponibilidade da Amazon. Desde então, o hashing consistente ganhou tração e encontrou uma tonelada de casos de uso na concepção e dimensionamento de sistemas distribuídos de forma eficiente. Os dois exemplos famosos que utilizam exaustivamente esta técnica são Bit Torrent, para as suas redes peer-to-peer e Akamai, para os seus caches web. Neste artigo mergulhamos profundamente na necessidade do Hashing Consistente, os internos do mesmo, e mais importante, ao longo do caminho implementá-lo usando arrays e Binary Search.

Antes de saltarmos para o núcleo da técnica de Hashing Consistente, primeiro esclarecemos algumas coisas, uma das quais são as Funções de Hash. Funções Hash são quaisquer funções que mapeiam valor de um domínio de tamanho arbitrário para outro domínio de tamanho fixo, normalmente chamado de Espaço Hash. Por exemplo, mapeando URLs para inteiros de 32 bits ou conteúdo HTML de páginas web para uma string de 256 bytes. Os valores gerados como uma saída dessas funções de hash são tipicamente usados como chaves para permitir uma pesquisa eficiente da entidade original.

Um exemplo de uma função de hash simples é uma função que mapeia um número inteiro de 32 bits em um espaço de hash inteiro de 8 bits. A função poderia ser implementada usando o operador aritmético modulo e podemos conseguir isso tomando um modulo 256 que produz números no intervalo tomando 8-bits para sua representação. Uma função hash, que mapeia chaves para esse domínio inteiro, muitas vezes aplica o modulo N de forma a restringir os valores, ou o espaço hash, a um intervalo .

Uma boa função de hash tem as seguintes propriedades

• A função é computacionalmente eficiente e os valores gerados são fáceis para pesquisas
• A função, para a maioria dos casos de uso geral, comporta-se como um gerador pseudo-aleatória que espalha os dados uniformemente sem qualquer correlação perceptível

Agora que vimos o que é uma função de hash, damos uma olhada em como poderíamos usá-los e construímos um sistema distribuído um pouco escalável.

Construindo um sistema de armazenamento distribuído

Dizemos que estamos construindo um sistema de armazenamento distribuído no qual os usuários podem carregar arquivos e acessá-los sob demanda. O serviço expõe as seguintes APIs aos usuários

upload para carregar o arquivo fetch para buscar o arquivo e retornar seu conteúdo

Nos bastidores o sistema tem nós de armazenamento nos quais os arquivos são armazenados e acessados. Estes nós expõem as funções put_file e fetch_file que coloca e obtém o conteúdo do arquivo de/para o disco e envia a resposta para o servidor da API principal que por sua vez a envia de volta ao usuário.

Para sustentar a carga inicial, o sistema tem 5 nós de Stogare que armazenam os arquivos carregados de forma distribuída. Ter vários nós garante que o sistema, como um todo, não seja sobrecarregado, e o armazenamento é distribuído quase que uniformemente.

Quando o usuário invoca a função upload com o caminho do arquivo, o sistema primeiro precisa identificar o nó de armazenamento que será responsável por manter o arquivo e nós fazemos isso aplicando uma função hash no caminho e, por sua vez, obtendo o índice do nó de armazenamento. Uma vez obtido o nó de armazenamento, lemos o conteúdo do arquivo e colocamos esse arquivo no nó invocando a função put_file do nó.

# storage_nodes holding instances of actual storage node objectsstorage_nodes = def hash_fn(key): """The function sums the bytes present in the `key` and then take a mod with 5. This hash function thus generates output in the range . """ return sum(bytearray(key.encode('utf-8'))) % 5def upload(path): # we use the hash function to get the index of the storage node # that would hold the file index = hash_fn(path) # we get the StorageNode instance node = storage_nodes # we put the file on the node and return return node.put_file(path)def fetch(path): # we use the hash function to get the index of the storage node # that would hold the file index = hash_fn(path) # we get the StorageNode instance node = storage_nodes # we fetch the file from the node and return return node.fetch_file(path)

A função hash utilizada aqui simplesmente soma os bytes e pega o módulo por 5 (já que existem 5 nós de armazenamento no sistema) e assim gera a saída no espaço hash . Este valor de saída agora representa o índice do motor de armazenamento que será responsável por guardar o ficheiro.

Dizer que temos 5 ficheiros ‘f1.txt’, ‘f2.txt’, ‘f3.txt’, ‘f4.txt’, ‘f5′.txt’ se aplicarmos a função hash a estes descobrimos que eles são armazenados nos nós de armazenamento E, A, B, C e D respectivamente.

As coisas se tornam interessantes quando o sistema ganha alguma tração e ele precisa ser escalado para 7 nós, o que significa que agora a função hash deve fazer mod 7 ao invés de um mod 5. Alterar a função hash implica em alterar o mapeamento e associação de arquivos com nós de armazenamento. Primeiro precisamos administrar as novas associações e ver quais arquivos precisam ser movidos de um nó para outro.

Com a nova função hash os mesmos 5 arquivos ‘f1.txt’, ‘f2.txt’, ‘f3.txt’, ‘f4.txt’, ‘f5.txt’ serão agora associados aos nós de armazenamento D, E, F, G, A. Aqui vemos que mudar a função hash requer que movamos cada um dos 5 arquivos para um nó diferente.

Se tivermos que mudar a função hash toda vez que aumentarmos ou diminuirmos a escala e se isso requerer que não movamos todos os dados, mas até mesmo metade deles, o processo se torna super caro e, a longo prazo, inviável. Portanto, precisamos de uma maneira de minimizar o movimento de dados necessário durante escalas ou reduções de escala, e é aqui que o Hashing Consistente se encaixa e minimiza a transferência de dados necessária.

Hashing Consistente

O principal ponto de dor do sistema acima é que ele é propenso a eventos como escalas e reduções de escala, pois ele requer muitas alterações nas associações. Estas associações são puramente guiadas pela Função Hash subjacente e portanto se pudéssemos de alguma forma tornar esta função de hash independente do número de nós de armazenamento no sistema, resolvemos esta falha.

O Hashing consistente resolve esta situação mantendo o Espaço Hash enorme e constante, algures na ordem de e o nó de armazenamento e os objectos tanto mapeados para um dos slots neste enorme Espaço Hash. Ao contrário do sistema tradicional onde o arquivo foi associado ao nó de armazenamento no índice onde foi associado ao hash, neste sistema as chances de uma colisão entre um arquivo e um nó de armazenamento são infinitamente pequenas e por isso precisamos de uma maneira diferente de definir esta associação.

Em vez de usar uma abordagem baseada em colisão definimos a associação como – o arquivo será associado ao nó de armazenamento que está presente à direita imediata da sua localização do hash. Definir associação desta forma nos ajuda

• manter a função hash independente do número de nós de armazenamento
• manter associações relativas e não conduzidas por colisões absolutas

Hashing Consistente em média requer apenas k/n unidades de dados a serem migrados durante a escala para cima e para baixo; onde k é o número total de chaves e n é o número de nós no sistema.

Uma maneira muito ingênua de implementar isto é alocando um array de tamanho igual ao Espaço Hash e colocando os arquivos e o nó de armazenamento literalmente no array no local do hashed. A fim de obter associação, iteramos a partir da localização do hash do item para a direita e encontramos o primeiro Nó de Armazenamento. Se chegarmos ao fim do array e não encontrarmos nenhum Nó de Armazenamento, fazemos um círculo de volta ao índice 0 e continuamos a busca. A abordagem é muito fácil de implementar mas sofre das seguintes limitações

• requer uma grande quantidade de memória para manter um array tão grande
• a associação por iteração sempre à direita é O(hash_space)

Uma maneira melhor de implementar isto é usando dois arrays: um para manter os Nodos de Armazenamento, chamado nodes e outro para manter as posições dos Nodos de Armazenamento no espaço do hash, chamado keys. Há uma correspondência um-para-um entre as duas arrays – o Nó de Armazenamento nodes está presente na posição keys no espaço de hash. Ambas as arrays são mantidas ordenadas de acordo com a matriz keys.

Função hash em Hashing Consistente

Definimos total_slots como o tamanho de todo esse espaço hash, tipicamente da ordem 2^256 e a função hash poderia ser implementada tomando SHA-256 seguido por um mod total_slots. Como o total_slots é enorme e uma constante, a seguinte implementação da função hash é independente do número real de Nós de Armazenamento presentes no sistema e, portanto, não é afetada por eventos como aumentos e diminuições de escala.

def hash_fn(key: str, total_slots: int) -> int: """hash_fn creates an integer equivalent of a SHA256 hash and takes a modulo with the total number of slots in hash space. """ hsh = hashlib.sha256() # converting data into bytes and passing it to hash function hsh.update(bytes(key.encode('utf-8'))) # converting the HEX digest into equivalent integer value return int(hsh.hexdigest(), 16) % total_slots

Adicionando um novo nó no sistema

Quando há necessidade de aumentar a escala e adicionar um novo nó no sistema, no nosso caso um novo nó de armazenamento, we

• find the position of the node where it resides in the Hash Space
• populate the new node with data it is supost to serve
• add the node in the Hash Space

Quando um novo nó é adicionado no sistema ele afeta apenas os arquivos que hash no local à esquerda e associado com o nó à direita, da posição em que o novo nó irá se encaixar. Todos os outros arquivos e associações permanecem inalterados, minimizando assim a quantidade de dados a serem migrados e o mapeamento necessário para serem alterados.

Da ilustração acima, vemos quando um novo nó K é adicionado entre os nós B e E, alteramos as associações dos arquivos presentes no segmento B-K e as atribuímos ao nó K. Os dados pertencentes ao segmento B-K podiam ser encontrados no nó E ao qual estavam anteriormente associados. Assim os únicos arquivos afetados e que precisam de migração estão no segmento B-K; e sua associação muda do nó E para o nó K.

Para implementar isto em um nível baixo usando nodes e keys array, primeiro obtemos a posição do novo nó no Espaço Hash usando a função hash. Nós então encontramos o índice da menor chave maior que a posição na ordenação keys array usando a busca binária. Este índice será onde a chave e o novo nó de armazenamento serão colocados em keys e nodes array respectivamente.

def add_node(self, node: StorageNode) -> int: """add_node function adds a new node in the system and returns the key from the hash space where it was placed """ # handling error when hash space is full. if len(self._keys) == self.total_slots: raise Exception("hash space is full") key = hash_fn(node.host, self.total_slots) # find the index where the key should be inserted in the keys array # this will be the index where the Storage Node will be added in the # nodes array. index = bisect(self._keys, key) # if we have already seen the key i.e. node already is present # for the same key, we raise Collision Exception if index > 0 and self._keys == key: raise Exception("collision occurred") # Perform data migration # insert the node_id and the key at the same `index` location. # this insertion will keep nodes and keys sorted w.r.t keys. self.nodes.insert(index, node) self._keys.insert(index, key) return key

Removendo um novo nó do sistema

Quando houver a necessidade de reduzir a escala e remover um nó existente do sistema, we

• find the position of the node to be removed from the Hash Space
• populate the node to the right with data that was associated with the node to be removed

remove the node from the Hash Space

Quando um nó é removido do sistema ele afeta apenas os arquivos associados com o próprio nó. Todos os outros arquivos e associações permanecem inalterados, minimizando assim a quantidade de dados a serem migrados e mapeados a serem alterados.

Da ilustração acima, vemos que quando o nó K é removido do sistema, mudamos as associações de arquivos associados ao nó K para o nó que se encontra à sua direita imediata i.e. nó E. Assim os únicos arquivos afetados e que precisam de migração são os associados ao nó K.

Para implementar isto em um nível baixo usando nodes e keys array, obtemos o índice onde o nó K se encontra no array keys usando a busca binária. Uma vez que temos o índice, removemos a chave do array keys e o Nó de Armazenamento do array nodes presente naquele índice.

def remove_node(self, node: StorageNode) -> int: """remove_node removes the node and returns the key from the hash space on which the node was placed. """ # handling error when space is empty if len(self._keys) == 0: raise Exception("hash space is empty") key = hash_fn(node.host, self.total_slots) # we find the index where the key would reside in the keys index = bisect_left(self._keys, key) # if key does not exist in the array we raise Exception if index >= len(self._keys) or self._keys != key: raise Exception("node does not exist") # Perform data migration # now that all sanity checks are done we popping the # keys and nodes at the index and thus removing the presence of the node. self._keys.pop(index) self.nodes.pop(index) return key

Associando um item a um nó

Agora vimos como o hashing consistente ajuda a manter a migração de dados, durante scale-ups e scale-downs, a um mínimo; é hora de vermos como encontrar eficientemente o “nó à direita” para um dado item. A operação para encontrar a associação tem que ser super rápida e eficiente pois é algo que será invocado para cada leitura e escrita que acontecer no sistema.

Para implementar isto em baixo nível, nós novamente tiramos vantagem da pesquisa binária e executamos esta operação em O(log(n)). Nós primeiro passamos o item para a função hash e buscamos a posição onde o item é hashed no espaço hash. Esta posição é então pesquisada binario no array keys para obter o índice da primeira chave que é maior que a posição (obtida da função hash). se não houver chaves maiores que a posição, no array keys, fazemos um círculo para trás e retornamos o índice 0. O índice assim obtido será o índice do nó de armazenamento no array nodes associado ao item.

def assign(self, item: str) -> str: """Given an item, the function returns the node it is associated with. """ key = hash_fn(item, self.total_slots) # we find the first node to the right of this key # if bisect_right returns index which is out of bounds then # we circle back to the first in the array in a circular fashion. index = bisect_right(self._keys, key) % len(self._keys) # return the node present at the index return self.nodes

O código fonte com a implementação de Hashing Consistente em Python pode ser encontrado em github.com/arpitbbhayani/consistent-hashing.

Conclusão

Hashing Consistente é um dos algoritmos mais importantes para nos ajudar a escalar horizontalmente e gerenciar qualquer sistema distribuído. O algoritmo não só funciona em sistemas fragmentados mas também encontra sua aplicação no balanceamento de carga, particionamento de dados, gerenciamento de sessões sticky baseadas em servidores, algoritmos de roteamento e muito mais. Muitas bases de dados devem sua escala, performance e habilidade de lidar com a carga úmida ao Hashing Consistente.

• Funções de Hash – Wikipedia

Hashing Consistente – Wikipedia Hashing Consistente – Stanford Hashing Consistente e Árvores Aleatórias Dynamo: Amazon’s Highly Available Key-value Store

Outros artigos que você pode gostar:

• Python Caches Integers

Fractional Cascading – Speeding up Binary Searches

• Copy-on-Write Semantics

What makes MySQL LRU cache scan resistant

• Building Finite State Machines with Python Coroutines

Este artigo foi originalmente publicado no meu blog – Consistent Hashing.

Se você gostou do que leu, assine a minha newsletter e receba o post diretamente na sua caixa de entrada e me dê um grito @arpit_bhayani.