Course All lectures for PT purposes - Lecture: Fragmentação: lado reverso

2.1 Como fragmentar e desacelerar N vezes?

Você pode fragmentar e desacelerar exatamente N vezes assim:

Envie solicitações docs00...docs15 sequencialmente , não em paralelo.
Em consultas simples, faça uma seleção não por key , WHERE something=234.

Nesse caso, a parte serializada (serial) leva não 1% e nem 5%, mas cerca de 20% nos bancos de dados modernos. Você também pode obter 50% da parte serializada se acessar o banco de dados usando um protocolo binário extremamente eficiente ou vinculá-lo como uma biblioteca dinâmica a um script Python.

O restante do tempo de processamento de uma solicitação simples será ocupado por operações não paralelizáveis de análise da solicitação, preparação do plano etc. Ou seja, não ler o registro desacelera.

Se dividirmos os dados em 16 tabelas e executarmos sequencialmente, como é comum na linguagem de programação PHP, por exemplo (não é muito bom para iniciar processos assíncronos), obteremos uma desaceleração de 16 vezes. E, talvez, ainda mais, porque também serão adicionadas viagens de ida e volta à rede.

De repente, a escolha da linguagem de programação é importante ao fragmentar.

Lembre-se da escolha da linguagem de programação, porque se você enviar consultas ao banco de dados (ou servidor de pesquisa) sequencialmente, de onde vem a aceleração? Em vez disso, haverá uma desaceleração.

2.2 Sobre a semiautomática

Em alguns lugares, a sofisticação da tecnologia da informação inspira horror ctônico. Por exemplo, o MySQL pronto para uso não tinha a implementação de sharding para certas versões com certeza, no entanto, os tamanhos dos bancos de dados usados na batalha crescem para valores indecentes.

A humanidade sofredora diante de DBAs individuais tem sido atormentada por anos e escreve várias soluções de sharding ruins baseadas em nada. Depois disso, uma solução de sharding mais ou menos decente é escrita chamada ProxySQL (MariaDB/Spider, PG/pg_shard/Citus, ...). Este é um exemplo bem conhecido dessa mesma mancha.

O ProxySQL como um todo é, obviamente, uma solução de classe empresarial completa para software livre, para roteamento e muito mais. Mas uma das tarefas a serem resolvidas é a fragmentação de um banco de dados, que por si só não pode fragmentar de maneira humana. Veja bem, não há opção “shards = 16”, você tem que reescrever cada solicitação no aplicativo, e há muitos deles em lugares, ou colocar alguma camada intermediária entre o aplicativo e o banco de dados que parece: “Hmm ... SELECIONE * DE documentos? Sim, deve ser dividido em 16 pequenos SELECT * FROM server1.document1, SELECT * FROM server2.document2 - para este servidor com tal login / senha, para este com outro. Se alguém não respondeu, então ... ", etc. Exatamente isso pode ser feito por manchas intermediárias. Eles são ligeiramente menores do que para todos os bancos de dados. Para PostgreSQL, tanto quanto eu entendo,

A configuração de cada patch específico é um tópico gigante separado que não caberá em um relatório, portanto, discutiremos apenas os conceitos básicos. Vamos falar melhor um pouco sobre a teoria do buzz.

2.3 Automação absolutamente perfeita?

Toda a teoria de ficar chapado no caso de sharding nesta letra F() , o princípio básico é sempre o mesmo aproximadamente: shard_id = F(object).

Fragmentação - do que se trata? Temos 2 bilhões de registros (ou 64). Queremos quebrá-los em vários pedaços. Surge uma pergunta inesperada - como? Por qual princípio devo espalhar meus 2 bilhões de registros (ou 64) em 16 servidores disponíveis para mim?

O matemático latente em nós deveria sugerir que no final há sempre alguma função mágica que, para cada documento (objeto, linha, etc.), determinará em que peça colocá-lo.

Indo mais fundo na matemática, essa função sempre depende não apenas do objeto em si (a própria linha), mas também de configurações externas, como o número total de shards. Uma função que para cada objeto deve dizer onde colocá-lo, não pode retornar um valor maior que o número de servidores no sistema. E as funções são ligeiramente diferentes:

shard_func = F1(object); 
shard_id = F2(shard_func, ...); 
shard_id = F2(F1(object), current_num_shards, ...).

Mas, além disso, não vamos nos aprofundar nessas selvas de funções individuais, apenas falaremos sobre quais são as funções mágicas F ().

2.4 O que são F()?

Eles podem criar muitos mecanismos de implementação diferentes. Exemplo de resumo:

F = rand() % nums_shards
F = somehash(object.id) % num_shards
F = object.date % num_shards
F = object.user_id % num_shards
...
F = shard_table [ somehash() |… object.date |… ]

Um fato interessante - você pode espalhar naturalmente todos os dados aleatoriamente - lançamos o próximo registro em um servidor arbitrário, em um núcleo arbitrário, em uma tabela arbitrária. Não haverá muita felicidade nisso, mas funcionará.

Existem métodos um pouco mais inteligentes para fragmentar por uma função de hash reproduzível ou mesmo consistente, ou fragmentar por algum atributo. Vamos passar por cada método.

F = rand()

Espalhar-se não é um método muito correto. Um problema: espalhamos nossos 2 bilhões de registros em mil servidores aleatoriamente e não sabemos onde está o registro. Precisamos retirar user_1, mas não sabemos onde ele está. Vamos a mil servidores e classificamos tudo - de alguma forma, isso é ineficiente.

F = alguma coisa()

Vamos espalhar os usuários de maneira adulta: calcule a função hash reproduzível de user_id, pegue o restante da divisão pelo número de servidores e entre em contato imediatamente com o servidor desejado.

Por que estamos fazendo isso? E então, temos um highload e nada mais cabe em um servidor. Se coubesse, a vida seria tão simples.

Ótimo, a situação já melhorou, para conseguir um registro, vamos a um servidor conhecido com antecedência. Mas se temos um range de chaves, então em todo esse range precisamos passar por todos os valores das chaves e, no limite, ir para tantos shards quantas chaves tivermos no range, ou mesmo para cada servidor. A situação melhorou, claro, mas não para todos os pedidos. Algumas consultas foram afetadas.

Fragmentação natural (F = object.date % num_shards)

Às vezes, ou seja, frequentemente, 95% do tráfego e 95% da carga são solicitações que possuem algum tipo de sharding natural. Por exemplo, 95% das consultas de análise social condicional afetam os dados apenas nos últimos 1 dia, 3 dias, 7 dias e os 5% restantes referem-se aos últimos anos. Mas 95% das solicitações são, portanto, naturalmente fragmentadas por data, o interesse dos usuários do sistema está voltado para os últimos dias.

Nesse caso, você pode dividir os dados por data, por exemplo, por um dia, e seguir a resposta à solicitação de relatório de algum dia ou objeto desse dia até esse estilhaço e pronto.

A vida está melhorando - agora não apenas sabemos a localização de um determinado objeto, mas também sabemos sobre o alcance. Se não for solicitado um intervalo de datas, mas um intervalo de outras colunas, é claro que teremos que passar por todos os fragmentos. Mas de acordo com as regras do jogo, temos apenas 5% desses pedidos.

Parece que encontramos uma solução ideal para tudo, mas há dois problemas:

Esta solução é ajustada para um caso específico, quando 95% dos pedidos envolvem apenas a última semana.
Como 95% das solicitações tocam na última semana, todas cairão em um shard que atende nessa última semana. Este fragmento derreterá, enquanto todos os outros ficarão ociosos durante esse período. Ao mesmo tempo, você não pode jogá-los fora, os dados de arquivo também devem ser armazenados.

Não quer dizer que este seja um esquema de fragmentação ruim - cortamos os dados quentes, no entanto, algo precisa ser feito com o fragmento mais quente.

O problema é resolvido por palhaçadas, saltos e cataplasmas, ou seja, um aumento no número de réplicas para o dia atual em chamas, depois uma diminuição gradual no número de réplicas quando esse dia se torna passado e vai para o arquivo. Não existe uma solução ideal chamada “você só precisa espalhar os dados pelo cluster com uma função hash mágica de maneira errada”.

2.5 Preço a pagar

Formalmente, sabemos agora que sabemos "tudo". É verdade que não conhecemos uma dor de cabeça gigante e duas dores de cabeça menores.

1. Dor simples: mal manchada

Este é um exemplo de um livro didático, que quase nunca ocorre em batalha, mas de repente.

Por exemplo com data, só sem data!
Distribuição desigual (perceptível) não intencional .

Escolheram o mecanismo de sharding, e/ou os dados mudaram, e, claro, o PM não transmitiu os requisitos (não temos erros no código, o PM sempre não reporta os requisitos), e a distribuição tornou-se monstruosamente desigual. Ou seja, eles erraram o critério.

Para pegar, você precisa olhar para o tamanho dos cacos. Certamente veremos o problema no momento em que um de nossos fragmentos superaquecer ou se tornar 100 vezes maior que os outros. Você pode corrigi-lo simplesmente substituindo a chave ou a função de fragmentação.

Este é um problema simples, para ser honesto, não acho que pelo menos uma pessoa em cem se depare com isso na vida, mas de repente ajudará pelo menos alguém.

2. Dor "invencível": agregação, união

Como fazer seleções que juntam um bilhão de registros de uma tabela para um bilhão de registros de outra tabela?

Como calcular "rapidamente"... ONDE randcol ENTRE aaa E bbb?
Como fazer de forma "inteligente"... users_32shards JOIN posts_1024 shards?

Resposta curta: de jeito nenhum, sofra!

Se você distribuiu um bilhão de registros para mil servidores na primeira tabela para que eles funcionem mais rápido e fez o mesmo na segunda tabela, naturalmente mil a mil servidores devem se comunicar em pares. Um milhão de conexões não funcionará bem. Se fizermos solicitações ao banco de dados (pesquisa, armazenamento, armazenamento de documentos ou sistema de arquivos distribuído) que não se encaixam bem com o sharding, essas solicitações ficarão extremamente lentas.

Um ponto importante é que algumas solicitações sempre serão manchadas sem sucesso e ficarão lentas . É importante tentar minimizar sua porcentagem. Como consequência, não há necessidade de fazer junções gigantescas com um bilhão por um bilhão de registros. Se for possível replicar uma pequena tabela, relativamente à qual está a juntar-se numa gigantesca tabela partilhada, para todos os nós, deverá fazê-lo. Se as junções forem realmente locais de alguma forma, por exemplo, é possível colocar o usuário e seus posts lado a lado, fragmentá-los da mesma forma e fazer todas as junções dentro da mesma máquina - você precisa fazer exatamente isso .

Este é um curso separado de palestras por três dias, então vamos passar para a última dor infernal e diferentes algoritmos para lidar com ela.

2.6. Dor Complexa/Longa: Resharding

Prepare-se: se você fragmentou seus dados pela primeira vez na vida, em média irá fragmentá-los mais cinco vezes.

Não importa quantos clusters você configure, você ainda precisará reestilhaçar.

Se você for muito inteligente e sortudo, estilhace pelo menos uma vez. Mas uma vez que você tenha certeza, porque no momento em que você pensa que 10 unidades são suficientes para o usuário, alguém naquele momento escreve um pedido de 30 e planeja fazer um pedido de 100 unidades de recursos desconhecidos. Fragmentos nunca são suficientes. Com o primeiro esquema de fragmentação, em qualquer caso, você perderá - você sempre terá que aumentar o número de servidores a serem adicionados ou fazer outra coisa - em geral, de alguma forma, reembalar os dados.

É bom se tivermos bons poderes de dois: havia 16 fragmentos de servidor, agora são 32. É mais divertido se era 17, é 23 - dois números primos. Como os bancos de dados fazem isso, talvez eles tenham algum tipo de mágica por dentro?

A resposta correta é: não, não há mágica por dentro, eles têm o inferno por dentro.

A seguir, consideraremos o que pode ser feito “à mão”, talvez entendamos “como uma máquina automática”.

Na testa #1. realocar tudo

Para todos os objetos, consideramos NewF(object), mude para um novo shard.

A chance de correspondência NewF()=OldF() é baixa.

Vamos cobrir quase tudo.

Oh.

Espero que não exista o inferno de transferir todos os 2 bilhões de registros de fragmentos antigos para novos. A abordagem ingênua é compreensível: havia 17 máquinas, 6 máquinas foram adicionadas ao cluster, 2 bilhões de registros foram classificados, eles foram transferidos de 17 máquinas para 23 máquinas. Uma vez a cada 10 anos, você provavelmente pode fazer isso. Mas no geral é uma má jogada.

Na testa #2. realocar metade

A próxima melhoria ingênua - vamos abandonar um esquema tão estúpido - proibirá 17 carros de reestilhaçar em 23, e sempre iremos reestilhaçar 16 carros em 32 carros! Então, de acordo com a teoria, teremos que deslocar exatamente metade dos dados e, na prática, também podemos fazer isso.

Para todos os objetos, consideramos NewF(object), mude para um novo shard.

Era estritamente 2^N, agora é estritamente 2^(N+1) fragmentos.

A probabilidade de corresponder NewF()=OldF() é 0,5.

Vamos transferir cerca de 50% dos dados.

Ideal, mas só funciona para potências de dois.

Em princípio está tudo bem, exceto a vinculação à potência de dois em termos de número de carros. Essa abordagem ingênua, curiosamente, pode funcionar.

Observe que a divisão adicional do cluster por potências de dois neste caso também é ideal. De qualquer forma, adicionando 16 máquinas a um cluster de 16, somos obrigados a deslocar metade dos dados - exatamente metade e deslocar.

Ok, mas a humanidade realmente não inventou mais nada - a questão surge de uma mente inquisitiva.

Mais divertido #3. Hash consistente

Obviamente, uma imagem com um círculo sobre hash consistente é necessária aqui.

Se você pesquisar "hashing consistente" no Google, um círculo definitivamente sairá, todos os resultados serão preenchidos com círculos.

Ideia: vamos desenhar identificadores de fragmentos (hashes) em um círculo e marcar os identificadores de servidor com hash no topo. Quando você precisa adicionar um servidor, colocamos um novo ponto no círculo, e o que ficou próximo a ele (e apenas o que ficou próximo a ele), realocamos.

Ao adicionar um fragmento: não examinamos tudo, mas apenas 2 "vizinhos", mudamos em média 1/n.

Ao excluir um fragmento: olhamos apenas para o fragmento que está sendo excluído, apenas o deslocamos. Tipo de ideal.

Muito eficaz em termos de minimizar o tráfego ao adicionar um fragmento e absolutamente nojento em termos de balanceamento de dados normal. Porque quando misturamos todos esses objetos que distribuímos para um grande número de máquinas, fazemos isso de maneira relativamente desigual: os pontos ao redor do círculo são espaçados de maneira desigual e a carga de cada nó específico pode ser muito diferente do resto.

Este problema é resolvido pela última linha do nó virtual. Cada nó, cada servidor no círculo é indicado por mais de um ponto. Ao adicionar um servidor, um shard, etc., estamos adicionando alguns pontos. Cada vez que removemos algo, removemos alguns pontos e deslocamos uma pequena parte dos dados.

Estou falando desse espaço com círculos, porque, por exemplo, esse esquema está dentro do Cassandra. Ou seja, quando ela começou a perseguir registros entre nós, saiba que o círculo está olhando para você e provavelmente não aprova.

Porém, em comparação com os primeiros métodos, a vida melhorou - ao adicionar / remover um estilhaço, já examinamos não todos os registros, mas apenas uma parte, e deslocamos apenas uma parte.

Atenção, a pergunta é: pode melhorar ainda mais? E também melhorar a uniformidade do carregamento de estilhaços? Dizem que é possível!

Mais divertido #4. Encontro/HRW

A próxima ideia simples (o material é educacional, então nada complicado): shard_id = arg max hash(object_id, shard_id).

Por que é chamado de hash de Rendezvous, não sei, mas sei por que é chamado de Maior Peso Aleatório. É muito fácil visualizar assim:

Temos, por exemplo, 16 cacos. Para cada objeto (string) que precisa ser colocado em algum lugar, calculamos 16 hashes dependendo do objeto a partir do número do shard. Quem tiver o maior valor de hash vence.

Este é o chamado hash HRW, também conhecido como hash Rendezvous. Burro como um pedaço de pau, o esquema para calcular o número de um estilhaço, em primeiro lugar, é mais fácil de ver do que círculos e dá uma carga uniforme, por outro lado.

O único aspecto negativo é que adicionar um novo fragmento piorou para nós. Existe o risco de ao adicionar um novo shard ainda termos alguns hashes que vão mudar e pode ser necessário revisar tudo. A tecnologia de remoção de fragmentos não mudou muito.

Outro problema é que ele é computacionalmente pesado com um grande número de fragmentos.

Mais divertido #5. Mais técnicas

Curiosamente, a pesquisa não pára e o Google publica alguma nova tecnologia espacial todos os anos:

Ir Hash - Google '2014.
Sonda múltipla—Google '2015.
Maglev-Google '2016.

Se você estiver interessado no assunto, poderá ler muitas dissertações. Apresento esses dados para deixar claro que o problema não foi resolvido, não existe uma super-solução que possa ser implementada em todos os bancos de dados. Até agora, as pessoas defendem dissertações.

conclusões

Existe uma importante técnica básica chamada sharding em homenagem a Gallius Julius Caesar: “Dividir e governar, governar e dividir!”. Se os dados não couberem em um servidor, é necessário dividi-lo em 20 servidores.

Tendo aprendido tudo isso, deve-se ter a impressão de que seria melhor não estilhaçar. Se você decidir que seria melhor não fragmentar, esse é o sentimento certo. Se você pode adicionar memória ao servidor por US $ 100 e não fragmentar nada, faça isso. Ao fragmentar, um sistema distribuído complexo aparecerá com a transferência de dados para frente e para trás, empilhando dados em ninguém sabe onde. Se pode ser evitado, deve ser evitado.

É melhor não fazer na mão, é melhor que a “base” (pesquisa, DFS, ...) possa se fragmentar. De qualquer forma, mais cedo ou mais tarde, o highload virá e de alguma forma os dados terão que ser divididos. Não é fato que, mesmo que a base possa fazer isso sozinha, você não terá problemas. Lembre-se do fundamentalismo algorítmico - você precisa entender como tudo funciona por dentro.

Ao configurar o sharding pela primeira vez, escolha F() com cuidado, pense em solicitações, rede, etc. Mas prepare-se, provavelmente você terá que escolher 2 vezes e pelo menos uma vez terá que refazer tudo.

Como fazer seleções que juntam um bilhão de registros de uma tabela para um bilhão de registros de outra tabela?

Como calcular "rapidamente"... ONDE randcol ENTRE aaa E bbb?
Como fazer de forma "inteligente"... users_32shards JOIN posts_1024 shards?

Resposta curta: de jeito nenhum, sofra!

Este é um curso separado de palestras por três dias, então vamos passar para a última dor infernal e diferentes algoritmos para lidar com ela.

2.6. Dor Complexa/Longa: Resharding

Prepare-se: se você fragmentou seus dados pela primeira vez na vida, em média irá fragmentá-los mais cinco vezes.

Não importa quantos clusters você configure, você ainda precisará reestilhaçar.

A resposta correta é: não, não há mágica por dentro, eles têm o inferno por dentro.

A seguir, consideraremos o que pode ser feito “à mão”, talvez entendamos “como uma máquina automática”.

Na testa #1. realocar tudo

Para todos os objetos, consideramos NewF(object), mude para um novo shard.

A chance de correspondência NewF()=OldF() é baixa.

Vamos cobrir quase tudo.

Oh.

Na testa #2. realocar metade

Para todos os objetos, consideramos NewF(object), mude para um novo shard.

Era estritamente 2^N, agora é estritamente 2^(N+1) fragmentos.

A probabilidade de corresponder NewF()=OldF() é 0,5.

Vamos transferir cerca de 50% dos dados.

Ideal, mas só funciona para potências de dois.

Em princípio está tudo bem, exceto a vinculação à potência de dois em termos de número de carros. Essa abordagem ingênua, curiosamente, pode funcionar.

Ok, mas a humanidade realmente não inventou mais nada - a questão surge de uma mente inquisitiva.

Mais divertido #3. Hash consistente

Obviamente, uma imagem com um círculo sobre hash consistente é necessária aqui.

Se você pesquisar "hashing consistente" no Google, um círculo definitivamente sairá, todos os resultados serão preenchidos com círculos.

Ao adicionar um fragmento: não examinamos tudo, mas apenas 2 "vizinhos", mudamos em média 1/n.

Ao excluir um fragmento: olhamos apenas para o fragmento que está sendo excluído, apenas o deslocamos. Tipo de ideal.

Porém, em comparação com os primeiros métodos, a vida melhorou - ao adicionar / remover um estilhaço, já examinamos não todos os registros, mas apenas uma parte, e deslocamos apenas uma parte.

Atenção, a pergunta é: pode melhorar ainda mais? E também melhorar a uniformidade do carregamento de estilhaços? Dizem que é possível!

Mais divertido #4. Encontro/HRW

A próxima ideia simples (o material é educacional, então nada complicado): shard_id = arg max hash(object_id, shard_id).

Por que é chamado de hash de Rendezvous, não sei, mas sei por que é chamado de Maior Peso Aleatório. É muito fácil visualizar assim:

Outro problema é que ele é computacionalmente pesado com um grande número de fragmentos.

Mais divertido #5. Mais técnicas

Curiosamente, a pesquisa não pára e o Google publica alguma nova tecnologia espacial todos os anos:

Ir Hash - Google '2014.
Sonda múltipla—Google '2015.
Maglev-Google '2016.