Vinicius Quinafelex Alves

No banco de dados, quando uma tabela cresce a ponto de chegar a gigabytes de dados ou bilhões de registros, gerenciar a disponibilidade e sobrecarga de uma única instância de banco de dados fica bastante desafiador. Nestes cenários, é recomendado particionar a tabela para facilitar a gestão e processamento dos dados.

Uma das formas mais drásticas de particionamento é a fragmentação do banco de dados, ou sharding, que divide os registros e processamento em instâncias de banco de dados diferentes. Isso permite que sejam usados vários servidores físicos diferentes, aumentando o potencial de armazenamento e processamento.

Aplicar sharding em um banco de dados é desafiador e gera dificuldades que costumam ser triviais em bancos de instâncias únicas, como agregação e filtro de dados, seleção e gestão de instâncias, detecção de gargalos, etc.

Este artigo introduz o conceito de distribuição de registros de banco de dados em shards usando consistent hashing.

Hashing

Hashing envolve usar um algoritmo que converte dados em uma representação numérica. Para sharding de registros, calculamos um hash baseado no ID do registro.

Para sharding, bons algoritmos de hash distribuem os valores igualitariamente, são de rápida execução, e permitem que pequenas alterações no dado de entrada gerem grandes mudanças no dado de saída. É aceitável que diferentes inputs gerem o mesmo valor de hash, mas por flexibilidade é melhor que o hash tenha um grande volume de valores possíveis.

Por simplicidade, a demonstração abaixo gera valores de 0 a 999, mas em cenário de real seria mais recomendado valores de 0 a 2^32.

Dynamic sharding

Cada shard do banco de dados será responsável por uma faixa de valores de hash. Como o objetivo é distribuir o processamento de forma balanceada, inicialmente é recomendado dividir os dados proporcionalmente.

Dessa forma, podemos determinar em qual instância cada um dos registros devem ser armazenados

Adicionando uma instância

Quando uma das instâncias estiver ficando muito grande, ou se tornar um hotspot com muitas requisições, podemos dividir a faixa de hash e transferir os dados apenas dessa instância, enquanto todas as outras instâncias continuam funcionando normalmente. Por exemplo, se quisermos dividir a instância A no meio:

Removendo uma instância

De forma semelhante, se duas instâncias estiverem com pouco uso, é simples juntar os dados em uma única instância. Por exemplo, se instâncias C e D estiverem com pouco uso, podemos elejer a instância C para absorver os dados da instância D.

Virtual nodes

É esperado que diferentes shards tenham diferentes níveis de uso, mesmo que o hash esteja dividindo os dados igualmente. Por exemplo, alguns registros podem ter mais acesso que outros, ou os dados de entrada da função de hash estejam emulando algum enviesamento na função.

Para ajudar a rebalancear o processamento das instâncias sem alterar a quantidade, podemos atribuir diferentes faixas para uma mesma instância. Neste caso, é mais apropriado dizer que as faixas estão associadas à nodos virtuais do que instâncias de banco de dados.

Porque é preferível usar consistent hashing ao invés de linear hashing

Linear hashing é uma estratégia para distribuir registros em uma quantidade fixa de repositórios. Já que cada repositório possui um único valor de representação, é uma estratégia bastante intuitiva e rápida.

A forma mais comum de implementar linear hashing é usando a operação de módulo (mod) nos valores de saída do hash, utilizando a quantidade de instâncias de banco de dados como divisor. Isso funciona para distribuir is registros igualmente nas instâncias de banco de dados.

Porém, incluir ou remover instâncias irá mudar o divisor do módulo, então agora cada ID de registro pode gerar um valor de mod diferente do valor original.

Para garantir que os registros continuem salvos nas instâncias corretas de banco de dados, considerando o novo valor, é necessário recalcular o valor de mod de todos os IDs dentro do banco de dados. Se o novo valor for diferente do anterior, será necessário migrar o dados para a instância correta.

Considerando um banco com os registros proporcionalmente distribuídos, alterar o divisor fará com que pelo menos 50% dos registros de todo o banco de dados precise mudar para outra instância de banco de dados, afetando todas as instâncias, independente de qual a alteração na quantidade de instâncias. Nos piores casos, a quantidade de movimentações pode chegar a quase 100% dos registros.

Como demonstrado em um cenário com três instâncias de banco de dados:

Em um cenário do mundo real, se a instância A está sobrecarregada, adicionar uma nova instância precisaria movimentar registros de todo o banco de dados, e não apenas da instância A. Além de não ser um processo otimizado, torna muito mais difícil de administrar a disponibilidade do banco de dados para os sistemas.

Estimar o resultado da distribuição também é difícil. Existe a possibilidade de depois dos dados terem sido redistribuidos, alguma instância acabe com um grande volume de registros acessados com alta frequência, potencialmente ficando mais sobrecarregado do que a instância anterior.

Dynamic table mitiga a maioria dos problemas

Usar uma tabela dinâmica permite especificar quais faixas de hash devem ser reorganizadas. Assim é mais fácil controlar quantos registros precisarão ser analisados e movimentados, quantas instâncias de banco de dados serão impactados.

Na situação em que uma instância esteja sobrecarregada, mesmo se não escolhermos uma faixa que iria distribuir devidamente o nível de processamento, não haverá o risco de aumentar a sobrecarga da instância.