Fragmentação

1.1 O que é fragmentação?

Se você pesquisar persistentemente no Google, descobrirá que há uma borda bastante borrada entre o chamado particionamento e o chamado sharding. Cada um chama do que quiser, do que quiser. Algumas pessoas distinguem entre particionamento horizontal e sharding. Outros dizem que o sharding é um certo tipo de particionamento horizontal.

Não encontrei um único padrão terminológico que fosse aprovado pelos pais fundadores e certificado pela ISO. A convicção interna pessoal é mais ou menos assim: particionar em média é “cortar a base em pedaços” de maneira arbitrária.

• Particionamento vertical - por coluna. Por exemplo, existe uma tabela gigante com alguns bilhões de registros em 60 colunas. Em vez de manter uma dessas tabelas gigantes, mantemos pelo menos 60 tabelas gigantes de 2 bilhões de registros cada - e isso não é uma base de coluna, mas particionamento vertical (como exemplo de terminologia).
• Particionamento horizontal - cortamos linha por linha, talvez dentro do servidor.

O momento estranho aqui é a sutil diferença entre particionamento horizontal e sharding. Posso ser cortado em pedaços, mas não posso dizer com certeza o que é. Há uma sensação de que sharding e particionamento horizontal são quase a mesma coisa.

Sharding é, em geral, quando uma tabela grande em termos de bancos de dados ou pró-coleção de documentos, objetos, se você não tiver um banco de dados, mas um armazenamento de documentos, é cortada exatamente por objetos. Ou seja, de 2 bilhões de objetos, peças são selecionadas não importando o tamanho. Os próprios objetos dentro de cada objeto não são cortados em pedaços, não os colocamos em colunas separadas, ou seja, os colocamos em lotes em lugares diferentes.

Existem diferenças terminológicas sutis. Por exemplo, relativamente falando, os desenvolvedores do Postgres podem dizer que o particionamento horizontal é quando todas as tabelas nas quais a tabela principal é dividida estão no mesmo esquema e, quando em máquinas diferentes, isso já é sharding.

Em um sentido geral, sem estar vinculado à terminologia de um banco de dados específico e de um sistema de gerenciamento de dados específico, há uma sensação de que sharding é apenas fatiar linha por linha / documento por documento e assim por diante - isso é tudo.

Eu enfatizo o típico. No sentido de que estamos fazendo tudo isso não apenas para cortar 2 bilhões de documentos em 20 tabelas, cada uma das quais seria mais gerenciável, mas para distribuí-lo em muitos núcleos, muitos discos ou muitos servidores físicos ou virtuais diferentes .

1.2 Divida o indivisível

Entende-se que fazemos isso para que cada fragmento - cada pedaço de dado - seja replicado muitas vezes. Mas realmente, não.

INSERT INTO docs00 
SELECT * FROM documents WHERE (id%16)=0 
... 
 
INSERT INTO docs15 
SELECT * FROM documents WHERE (id%16)=15 

Na verdade, se você fizer tal fatiamento de dados, e de uma tabela SQL gigante no MySQL em seu valente laptop, você gerará 16 pequenas tabelas, sem ir além de um único laptop, nem um único esquema, nem um único banco de dados, etc. . e assim por diante. - é isso, você já tem sharding.

Isso resulta no seguinte:

• A largura de banda aumenta.
• A latência não muda, ou seja, cada um, por assim dizer, trabalhador ou consumidor neste caso, ganha o seu. Diferentes solicitações são atendidas aproximadamente ao mesmo tempo.
• Ou ambos, e outro, e também alta disponibilidade (replicação).

Por que largura de banda? Às vezes, podemos ter volumes de dados que não cabem - não está claro onde, mas eles não cabem - em 1 {kernel | disco | servidor | ...}. Simplesmente não há recursos suficientes, só isso. Para trabalhar com esse grande conjunto de dados, você precisa cortá-lo.

Por que latência? Em um núcleo, a varredura de uma tabela de 2 bilhões de linhas é 20 vezes mais lenta do que a varredura de 20 tabelas em 20 núcleos, em paralelo. Os dados são processados ​​muito lentamente em um único recurso.

Por que alta disponibilidade? Ou cortamos os dados para fazer as duas coisas ao mesmo tempo e várias cópias de cada fragmento ao mesmo tempo - a replicação garante alta disponibilidade.

1.3 Um exemplo simples "como fazer à mão"

A fragmentação condicional pode ser cortada usando a tabela de teste test.documents para 32 documentos e gerando 16 tabelas de teste dessa tabela, aproximadamente 2 documentos cada test.docs00, 01, 02, ..., 15.

INSERT INTO docs00 
SELECT * FROM documents WHERE (id%16)=0 
... 
 
INSERT INTO docs15 
SELECT * FROM documents WHERE (id%16)=15 

Por que sobre? Porque a priori não sabemos como os id são distribuídos, se de 1 a 32 inclusive, então serão exatamente 2 documentos cada, caso contrário não.

Nós fazemos isso aqui porque. Depois de termos feito 16 mesas, podemos "pegar" 16 do que precisamos. Independentemente do que atingirmos, podemos paralelizar esses recursos. Por exemplo, se não houver espaço em disco suficiente, faria sentido decompor essas tabelas em discos separados.

Tudo isso, infelizmente, não é gratuito. Suspeito que no caso do padrão SQL canônico (não releio o padrão SQL há muito tempo, talvez não seja atualizado há muito tempo), não existe uma sintaxe padronizada oficial para dizer a qualquer servidor SQL : "Caro servidor SQL, faça-me 32 fragmentos e divida-os em 4 discos. Mas em implementações individuais, muitas vezes há uma sintaxe específica para fazer basicamente a mesma coisa. PostgreSQL tem mecanismos de particionamento, MySQL tem MariaDB, Oracle provavelmente fez tudo isso há muito tempo.

No entanto, se fizermos isso manualmente, sem suporte de banco de dados e dentro da estrutura do padrão, pagaremos condicionalmente com a complexidade do acesso aos dados . Onde havia um simples SELECT * FROM documentos WHERE id=123, agora 16 x SELECT * FROM docsXX. E é bom se tentássemos obter o registro por chave. Muito mais interessante se estivéssemos tentando obter uma série inicial de registros. Agora (se nós, enfatizo, somos, por assim dizer, tolos e permanecemos dentro da estrutura do padrão), os resultados desses 16 SELECT * FROM terão que ser combinados no aplicativo.

Que mudança de desempenho você pode esperar?

• Intuitivamente - linear.
• Teoricamente - sublinear, porque a lei Amdahl.
• Praticamente, talvez quase linearmente, talvez não.

Na verdade, a resposta correta é desconhecida. Com uma aplicação inteligente da técnica de sharding, você pode obter uma degradação superlinear significativa no desempenho de seu aplicativo, e até mesmo o DBA entrará em execução com um pôquer em brasa.

Vamos ver como isso pode ser alcançado. É claro que apenas definir a configuração PostgreSQL shards=16 e depois decolar sozinho não é interessante. Vamos pensar em como podemos ter certeza de diminuir a fragmentação em 16 vezes por 32 - isso é interessante do ponto de vista de como não fazer isso.

Nossas tentativas de acelerar ou desacelerar sempre vão esbarrar nos clássicos - a boa e velha lei de Amdahl, que diz que não existe paralelização perfeita de nenhuma solicitação, sempre existe alguma parte consistente.

1.4 lei Amdahl

Há sempre uma parte serializada.

Sempre há uma parte da execução da consulta que é paralelizada e sempre há uma parte que não é paralelizada. Mesmo que lhe pareça uma consulta perfeitamente paralela, pelo menos a coleção da linha de resultado que você vai enviar ao cliente a partir das linhas recebidas de cada shard está sempre lá, e é sempre sequencial.

Há sempre alguma parte consistente. Pode ser minúsculo, completamente invisível no contexto geral, pode ser gigantesco e, portanto, afetar fortemente a paralelização, mas sempre existe.

Além disso, sua influência está mudando e pode crescer significativamente, por exemplo, se cortarmos nossa tabela - vamos aumentar as apostas - de 64 registros para 16 tabelas de 4 registros, essa parte mudará. Claro, a julgar por quantidades tão gigantescas de dados, estamos trabalhando em um telefone celular e um processador 86 de 2 MHz, e não temos arquivos suficientes que possam ser mantidos abertos ao mesmo tempo. Aparentemente, com essas entradas, abrimos um arquivo por vez.

• Era Total = Serial + Paralelo . Onde, por exemplo, paralelo é todo o trabalho dentro do BD, e serial é enviar o resultado para o cliente.
• Tornou-se Total2 = Serial + Paralelo/N + Xserial . Por exemplo, quando o ORDER BY, Xserial>0.

Com este simples exemplo, estou tentando mostrar que algum Xserial aparece. Além do fato de sempre haver uma parte serializada e do fato de estarmos tentando trabalhar com dados em paralelo, há uma parte adicional para fornecer esse fatiamento de dados. Grosso modo, podemos precisar de:

• encontre essas 16 tabelas no dicionário interno do banco de dados;
• Abrir arquivos;
• alocar memória;
• desalocar memória;
• mesclar resultados;
• sincronizar entre os núcleos.

Alguns efeitos fora de sincronia ainda aparecem. Eles podem ser insignificantes e ocupar um bilionésimo do tempo total, mas são sempre diferentes de zero e estão sempre presentes. Com a ajuda deles, podemos perder drasticamente o desempenho após o sharding.

Esta é uma imagem padrão sobre a lei de Amdahl. O importante aqui é que as linhas, que idealmente devem ser retas e crescer linearmente, correm para uma assíntota. Mas como o gráfico da Internet é ilegível, fiz, na minha opinião, tabelas mais visuais com números.

Digamos que temos alguma parte serializada do processamento da solicitação que leva apenas 5%: serial = 0.05 = 1/20 .

Intuitivamente, parece que com uma parte serializada que leva apenas 1/20 do processamento da solicitação, se paralelizarmos o processamento da solicitação para 20 núcleos, ela se tornará cerca de 20, no pior dos casos 18, vezes mais rápido.

Na verdade, a matemática é uma coisa sem coração :

parede = 0,05 + 0,95/num_cores, aceleração = 1 / (0,05 + 0,95/num_cores)

Acontece que se você calcular bem, com uma parte serializada de 5%, o ganho de velocidade será de 10 vezes (10,3), ou seja, 51% em relação ao ideal teórico.

Tendo usado 20 núcleos (20 discos, se preferir) para a tarefa em que um costumava trabalhar, nunca obteremos teoricamente uma aceleração de mais de 20 vezes, mas na prática - muito menos. Além disso, com o aumento do número de paralelos, a ineficiência aumenta muito.

Quando resta apenas 1% do trabalho serializado e 99% é paralelizado, os valores de aceleração melhoram um pouco:

Para uma consulta perfeitamente termonuclear, que naturalmente leva horas para ser concluída, e o trabalho preparatório e a montagem do resultado levam pouquíssimo tempo (serial = 0,001), já veremos uma boa eficiência:

Observe que nunca veremos 100% . Em casos especialmente bons, você pode ver, por exemplo, 99,999%, mas não exatamente 100%.