Cenário
Imagine que temos um tableusuário e um itemusuário. Essas 2 tabelas possuem uma tabela associativa chamada user_itempara definir um many to manyrelacionamento.
Começamos 100
itemregistrosTemos 500 milhões
userde registros.Portanto devemos gerar 50_000_000_000
user_item(50 bilhões)Poderíamos potencialmente ter ainda mais
Não será fácil fragmentar nem particionar porque isso tornará qualquer outra operação mais lenta (caso contrário, precisaremos verificar tudo)
Assuma como padrão de consulta (
INSERT,SELECT,UPDATE) padrões m2m básicos/típicos (que podem ser encontrados em qualquer tutorial ou exemplo
Pergunta
Qual é o melhor design ou solução conhecida para lidar com bilhões de relacionamentos Muitos para Muitos em um banco de dados, independentemente de um esquema?
Esquema
Imagine este esquema simples
CREATE DATABASE IF NOT EXISTS `playground` CHARACTER SET = latin1;
USE playground;
CREATE TABLE IF NOT EXISTS `user`
(
`id` BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
`name` VARCHAR(255) NOT NULL,
PRIMARY KEY (`id`),
INDEX `user__name_fk` (`name`)
) ENGINE = InnoDB
DEFAULT CHARSET = latin1
ROW_FORMAT = DYNAMIC;
CREATE TABLE IF NOT EXISTS `item`
(
`id` BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
`name` VARCHAR(255) NOT NULL,
PRIMARY KEY (`id`),
INDEX `user__name` (`name`)
) ENGINE = InnoDB
DEFAULT CHARSET = latin1
ROW_FORMAT = DYNAMIC;
CREATE TABLE IF NOT EXISTS `user_item`
(
`user_id` BIGINT UNSIGNED NOT NULL,
`item_id` BIGINT UNSIGNED NOT NULL,
PRIMARY KEY (`user_id`, `item_id`),
INDEX `user_item__item` (`item_id`),
FOREIGN KEY `user_id_fk` (`user_id`) REFERENCES `user` (`id`) ON DELETE CASCADE,
FOREIGN KEY `item_id_fk` (`item_id`) REFERENCES `item` (`id`) ON DELETE CASCADE
) ENGINE = InnoDB
DEFAULT CHARSET = latin1
ROW_FORMAT = DYNAMIC;
-- create some default items
INSERT INTO `item` (`name`) VALUES ('item_1'), ('item_2'), ('item_3'), ('item_4'), ('item_5'), ('item_6'), ('item_7'), ('item_8'), ('item_9'), ('item_10');
-- create some users
INSERT INTO `user` (`name`) VALUES ('user_1'), ('user_2'), ('user_3'), ('user_4'), ('user_5'), ('user_6'), ('user_7'), ('user_8'), ('user_9'), ('user_10');
INSERT INTO `user_item` (`user_id`, `item_id`) VALUES (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10);
Mais informações
Não estou perguntando como usar o relacionamento muitos para muitos no MySQL, eu sei disso. Estou perguntando qual é a solução mais conhecida para um problema de escala, ou seja, quando o número de registros relacionados está crescendo exponencialmente em uma escala tão grande.
Além disso, intencionalmente não adicionei nenhum padrão de consulta ( INSERT, SELECT, UPDATE) porque é irrelevante . Suponha o padrão M2M mais típico. Não quero perder o foco na questão real que é sobre escalabilidade e enorme quantidade de dados.
Deve haver algum truque ou alguma solução alternativa conhecida, certo? Também estou considerando um banco de dados NoSQL, então a resposta pode incluir qualquer coisa não relacionada ao MySQL (ou qualquer banco de dados SQL),
Sinto que este deveria ser um problema comum que muitas grandes empresas enfrentarão e, portanto, deveria haver uma solução comum (ou poucas). A causa raiz desse problema é que, embora o MySQL seja ótimo para criar relacionamentos, ele aumentará exponencialmente a tabela associativa m2m .
Os 500 milhões x 100 == 50 bilhões são apenas um exemplo. Mas poderia teoricamente acontecer.
Esclarecimento
- Deixei a consulta de propósito porque você pode assumir a mais fácil.
- Tenho certeza que se eu der alguns exemplos, começarei a aparecer a otimização na consulta específica, essa não é a questão
- Estou fazendo uma pergunta de alto nível e, se não houver uma solução real conhecida, um não explicando o porquê seria suficiente (presumindo que esteja correto)
Aqui está um exemplo de uma consulta simples de muitos para muitos.
SELECT user.*, item.* FROM user
LEFT JOIN user_item ON user.id = user_item.user_id
LEFT JOIN item ON item.id = user_item.item_id
WHERE user.name = 'user_1';
Perguntas semelhantes, mas não iguais
Prefácio
Acho que infelizmente você está entendendo mal:
Espero que esta resposta ajude a esclarecer isso.
Vou começar dizendo que trabalhei com tabelas grandes (cerca de 1 TB de tamanho) que continham dezenas de bilhões de linhas, com consultas que normalmente eram executadas em menos de 1 segundo, em hardware muito modesto (4 CPUs, 16 GB de BATER).
Também salientarei que o tamanho dos dados em repouso não é uma razão para escolher um sistema de banco de dados específico, pois todos eles lidam com a mesma quantidade de dados de forma relativamente igual do ponto de vista do desempenho (independentemente de você estar falando sobre bancos de dados NoSQL ou RDBMS) .
Organização de dados
Uma quantidade X de dados sempre levará Y tempo para ser lida no disco. Por exemplo, em uma tabela de 100 GB, 1 GB de dados sempre levará um tempo consistentemente constante para ser lido no disco, não importa qual sistema de banco de dados está sendo usado para armazenar esses dados. Da mesma forma que uma caminhonete pode transportar 100 tijolos de um lugar para outro, não importa a cor da caminhonete, ainda levará um tempo consistente para transportar os tijolos.
O problema é localizar os tijolos que o cliente deseja transportar da pilha de todos os tijolos (a mesa). Se um cliente deseja 100 tijolos vermelhos , e os tijolos estão todos armazenados em uma grande pilha desorganizada no chão (uma estrutura de dados Heap não indexada), entre 10 cores diferentes, localizar esses 100 tijolos vermelhos levará muito tempo para ser classificado. todos os tijolos para encontrar.
Insira índices
Os índices são um recurso (que quase todos os sistemas de banco de dados oferecem) como forma de organizar os dados em uma estrutura de dados eficiente para pesquisa (geralmente uma árvore B por padrão). Um índice classifica os dados na tabela na ordem das colunas especificadas em sua definição, que então classifica os dados relacionados juntos, tornando a pesquisa muito mais eficiente do que uma tabela heap desorganizada.
Então, se aplicarmos um índice à nossa pilha aleatória de tijolos, digamos por cor, então todos os tijolos vermelhos serão empilhados um ao lado do outro, depois os tijolos azuis todos juntos, depois os tijolos amarelos todos juntos etc. para cavar toda a pilha desorganizada de tijolos , podemos simplesmente caminhar diretamente para a seção vermelha e pegar os primeiros 100 tijolos que pudermos. Obviamente, isso é significativamente mais eficiente do que ter que procurar sem rumo em todos os tijolos.
O mesmo se aplica à forma como os dados são organizados em uma tabela de um banco de dados. Se os índices apropriados forem criados nessa tabela, então esses índices poderão ser procurados diretamente nas linhas que correspondem à consulta que está solicitando essas linhas, em vez de ter que examinar toda a tabela.
Por que as consultas são relevantes
Vou reafirmar o que acabei de dizer acima com alguma ênfase:
E um lembrete sobre como funcionam os índices:
Portanto, para que um índice seja eficaz e útil para uma consulta específica, ele precisa ser definido adequadamente com base nas colunas usadas especificamente nessa consulta.
No meu exemplo anterior sobre tijolos, cor era o campo pesquisado. Se classificássemos os tijolos por cor (definissemos o índice por cor) e o cliente quisesse os tijolos por tamanho, o índice que criamos não nos ajudaria. Isso é semelhante à
WHEREcláusula em uma consulta. Saber quais consultas são executadas com mais frequência e, ainda mais importante, quais predicados (JOINeWHEREcláusulas) essas consultas usam, nos ajuda a definir os índices mais apropriados para atender a essas consultas.Tudo anda de mãos dadas e é quase impossível falar sobre desempenho na prática sem falar sobre as questões que você deseja especificamente ter um bom desempenho.
Outra razão pela qual saber quais consultas serão mais importantes para otimizar é porque isso pode influenciar o design e a arquitetura da sua tabela. E há outras razões também, mas muitas para serem analisadas em profundidade em uma resposta aqui. Então vou me ater ao mais importante (na minha opinião) para esta discussão, que são os índices.
Final
Sim e não. Você está certo sobre a divisão dos dados , mas está errado sobre como pensa que deve fazer isso, com particionamento ou fragmentação. Estas não são as ferramentas certas para esta discussão generalizada sobre ajuste de desempenho e são usadas apenas para propósitos muito específicos. Em vez disso, você deseja Índices novamente, que dividem os dados para você na forma como eles são organizados na estrutura de dados subjacente, novamente, um B-Tree .
As árvores B têm uma
O(log2(n))complexidade de tempo de pesquisa devido à forma como organizam os dados. Isso significa que em uma tabela com 50 bilhões de linhas, também conhecida comon = 50 billion, o tempo de pesquisa élog2(50 billion) = ~36. Em outras palavras, para buscar um índice B-Tree em uma tabela com 50 bilhões de linhas, apenas 36 delas precisam ser rastreadas para localizar os dados solicitados, na pior das hipóteses. Minha calculadora gráfica pode pesquisar 36 linhas de dados em milissegundos.Como você pode ver, gerenciar os dados a serem pesquisados de forma eficiente é um problema resolvido, ao contrário do que você pensava inicialmente.
A melhor solução para o seu problema é aquela que você já projetou.
Isso ocorre porque todos os RDBMS são projetados para lidar exatamente com isso: um monte de tabelas, com relações muitos-para-muitos, e potencialmente bilhões de linhas, onde você SELECT, INSERT ou DELETE linhas.
Qualquer sistema de armazenamento "especial", como NoSQL, armazenamento colunar, particionamento, etc. é útil apenas quando você tem necessidades "especiais" e seus padrões de uso não são mais genéricos.
Mas para todo o processamento normal de dados OLTP e OLAP em um banco de dados, o esquema que você forneceu é típico porque é o melhor para resolver o problema na ausência de características mais específicas de dados ou padrões de uso.
Se precisar acessar algumas linhas por vez, você precisará de índices e terá todos os necessários. Se você precisa acessar uma grande porcentagem de dados, nada é mais eficiente do que uma verificação completa.
Mais otimização só é possível quando seus dados não são mais “genéricos”, mas apresentam algumas particularidades (na composição, ou no padrão de acesso) que podem ser otimizadas com alguns ajustes, mas desde que você não tenha essas particularidades, não há otimizações possíveis e o dimensionamento não é um problema, porque os RDBMS são projetados exatamente para esta tarefa.
É claro que a resposta será mais lenta quando houver bilhões de registros, mas não existe uma maneira geral de armazenar esses bilhões de registros de maneira mais eficiente, se você tiver o padrão de acesso típico.
Como são apenas 100 itens... Se não houver muito mais itens, mude para
SMALL UNSIGNED(máximo de 65K). Isso economizará 30 GB. (Reduzindo uma tabela -> menos E/S e melhor armazenamento em cache -> talvez melhor desempenho de consulta.)Considere ter a
item VARCHAR(..)tag inuser_itemem vez daneeding thetagtable. If the strings are usually "short", the cost of the extra space will be offset by avoiding an extra lookup. [I did this quite successfully withpicture_id`and.]50 bilhões de linhas não são um problema sério se você estiver sempre usando um dos índices.
Considere
INT UNSIGNED-user_ideconomizará 4 bytesBIGINT, mas está limitado a 4 bilhões. VerifiqueSELECT MAX(user_id) FROM userse você [por qualquer motivo] já está chegando à casa dos bilhões."caso contrário, precisamos verificar tudo" - Qual consulta está causando uma grande verificação?
É
ON DELETE CASCADEimportante? [Isso pode não importar.]PARTITIONingé útil para excluir dados antigos, mas não para desempenho de arquivosSELECTs.A fragmentação pode ser útil quando você tem tantos dados que a gravação se torna um problema. No entanto, a configuração e a manutenção são um incômodo.
Ao entrar em tabelas com tamanho de terabytes, você deve calcular quanto tempo levará para preencher a tabela. 50 bilhões de linhas, mesmo em lote, podem levar semanas ou meses. Um controlador RAID de hardware pode ajudar um pouco.
Ok, marcarei minha resposta como aceita, mas se surgir outra resposta mais completa no futuro, posso alterá-la, realmente não me importo, importante é a resposta mais correta/completa para minha pergunta.
Minha pergunta foi muito mal interpretada e seguiu em direções diferentes (exceto Andrea B. uma).
Porém, especialmente graças às 'conversas' nos comentários, alguma parte da resposta surge, então se combinarmos comentários + pedaços de resposta acho que podemos responder corretamente. Não marquei a resposta de Andrea B. porque depois de aprendê-la tenho uma resposta mais completa.
Então, como podemos resolver uma possível tabela, neste caso ManytoMany - Tabela associativa (que por natureza é a mais fácil de crescer em tamanho em comparação com outras).
Podemos assumir que o esquema em si está bem projetado em seu máximo (tipo de dados de coluna, etc.), bem como os padrões de consulta (
SELECT,INSERT...) imagine/suponha que eles já foram otimizados ao máximo e realmente não há melhor maneira de fazer eles. E se alguém que está lendo esta resposta não tem certeza, pode dar uma olhada neste guia de Muitos para Muitos de Rick James , é muito legal, eu acho.Mas no seu caso, imagine que você também sabe que as linhas dessa tabela vão crescer exponencialmente, e mais cedo ou mais tarde ultrapassarão os bilhões, o que você faz?
Em primeiro lugar, parece que não existe uma forma ou 'técnica' aceita que funcione o tempo todo, então todas as soluções abaixo podem ou não funcionar (também conhecidas como soluções alternativas).
Entre todas as 'soluções' parece que elas têm uma coisa em comum, existem basicamente alguma forma de:
Algoritmo de dividir e conquistar
Em outras palavras, você precisa encontrar uma maneira de dividir os dados tanto quanto possível para torná-los mais gerenciáveis. Mas, ao mesmo tempo, não divida muito porque você pode acabar na pior posição, por exemplo, você ainda precisa ser capaz de recuperar
SELECTdados de maneira rápida, então lembre-se de evitar 'escanear' tudo isso 'dividida' 'parte' (aqui ainda estou falando em um nível muito alto e é uma ideia abstrata, não estou falando em nada em específico!)Aqui estão as técnicas
WHEREcláusulaINDEXDividir dados na
WHEREcláusulaEste é o mais óbvio e bastante básico, mas pode não funcionar para todas as consultas ou às vezes você realmente precisa encontrar algo e verificar 'todos os dados'. Obviamente aqui vêm todas as
LIMITboasOFFSETpráticas.Além disso, copiei e colei dos comentários (desculpe, colocaria um link para o comentário, se fosse possível)
Divida os dados no
INDEXRetirado de JD Answer on the Finale (depois de falar sobre tijolos) é realmente muito interessante.
I won't add what he wrote to avoid repetition so you should check out that answer but the technique is true. While I personally know it I think is different if you think it in that way and have that explanation in mind. Really we are just using indexing to split 'data population', Divide-and-conquer.
Split data on usage | the 'Archive' concept
Use Least recently used (LRU) for instance
So this may not work for all cases for sure but, if you can implement a logic where basically, you avoid access all data if you know is 'old' or less used. Here may be different ways to achieve this
DATETIMEcolumn (probably) - (or could be evenidbigger than<VALUE>etc..For the second point, for instance, if you recognize a pattern in the data where, lots of data (maybe even most) is not accessed anymore you could move that (or rename the table) into another one (
user_item_archive) then you create a newuser_itemand work on the fresh one. This is oversimplified and depends on use case but the important is the concept.I'm pretty sure there are articles online about this concept, if someone finds any (or if I will in the future) we could add here.
Sharding
This is the only 'well known' technique but it's a double-edged sword for sure.
This blog on percona is very interesting
Someone mention partition, but I don't recommended because it as IMO little to none use cases and I see it more for when you need to delete data. Accessing data with partition already may lead to a lot of trouble.
Furthermore from this answer by Rick James while the first part tries to optimize the schema example (which is good but it was just an example) The last 2 bits are interestings IMO