Introdução
“Você tem que correr o mais rápido que puder apenas para permanecer no lugar,
e para chegar a algum lugar, você tem que correr pelo menos duas vezes mais rápido!”
(c) Alice no País das Maravilhas
Há algum tempo fui convidado para dar uma palestra analistas nossa empresa no tema desenho de modelos de dados, porque parados em projetos por muito tempo (às vezes por vários anos) perdemos de vista o que está acontecendo ao nosso redor no mundo das tecnologias de TI. Em nossa empresa (acontece) muitos projetos não utilizam bancos de dados NoSQL (pelo menos por enquanto), então em minha palestra prestei atenção a eles separadamente usando o exemplo do HBase e tentei orientar a apresentação do material para aqueles que nunca os usaram funcionaram. Em particular, ilustrei alguns dos recursos do design de modelo de dados usando um exemplo que li há vários anos . Ao analisar exemplos, comparei várias opções para resolver o mesmo problema, a fim de melhor transmitir as ideias principais ao público.
Recentemente, “sem nada para fazer”, perguntei-me (o longo fim de semana de maio em quarentena é especialmente propício para isso): até que ponto os cálculos teóricos corresponderão à prática? Na verdade, foi assim que nasceu a ideia deste artigo. Um desenvolvedor que trabalha com NoSQL há vários dias pode não aprender nada de novo com ele (e, portanto, pode pular imediatamente metade do artigo). Mas pelo analistasPara aqueles que ainda não trabalharam de perto com NoSQL, acho que será útil para obter uma compreensão básica dos recursos de design de modelos de dados para HBase.
Análise de exemplo
Na minha opinião, antes de começar a usar bancos de dados NoSQL, você precisa pensar com cuidado e pesar os prós e os contras. Freqüentemente, o problema provavelmente pode ser resolvido usando SGBDs relacionais tradicionais. Portanto, é melhor não usar NoSQL sem motivos significativos. Mesmo assim, se você decidiu usar um banco de dados NoSQL, deve levar em consideração que as abordagens de design aqui são um pouco diferentes. Especialmente alguns deles podem ser incomuns para aqueles que anteriormente lidaram apenas com SGBDs relacionais (de acordo com minhas observações). Assim, no mundo “relacional”, normalmente começamos modelando o domínio do problema, e só então, se necessário, desnormalizamos o modelo. No NoSQL nós deve levar imediatamente em conta os cenários esperados para trabalhar com dados e inicialmente desnormalizar os dados. Além disso, há uma série de outras diferenças, que serão discutidas a seguir.
Consideremos o seguinte problema “sintético”, com o qual continuaremos trabalhando:
É necessário projetar uma estrutura de armazenamento para a lista de amigos de usuários de alguma rede social abstrata. Para simplificar, vamos supor que todas as nossas conexões são direcionadas (como no Instagram, não no Linkedin). A estrutura deve permitir que você efetivamente:
- Responda à pergunta se o usuário A lê o usuário B (padrão de leitura)
- Permitir adicionar/remover conexões em caso de assinatura/cancelamento de assinatura do usuário A do usuário B (modelo de alteração de dados)
Claro, existem muitas opções para resolver o problema. Em um banco de dados relacional regular, provavelmente faríamos simplesmente uma tabela de relacionamentos (possivelmente tipificada se, por exemplo, precisarmos armazenar um grupo de usuários: família, trabalho, etc., que inclua este “amigo”), e otimizar a velocidade de acesso adicionaria índices/particionamento. Muito provavelmente a mesa final seria mais ou menos assim:
user_id
ID_amigo
Vasya
Petya
Vasya
Оля
doravante, para maior clareza e melhor compreensão, indicarei nomes em vez de IDs
No caso do HBase, sabemos que:
- é possível uma pesquisa eficiente que não resulta em uma varredura completa da tabela exclusivamente por chave
- na verdade, é por isso que escrever consultas SQL familiares a muitos desses bancos de dados é uma má ideia; tecnicamente, é claro, você pode enviar uma consulta SQL com Joins e outras lógicas para o HBase a partir do mesmo Impala, mas quão eficaz será...
Portanto, somos forçados a usar o ID do usuário como chave. E meu primeiro pensamento sobre o tema “onde e como armazenar IDs de amigos?” talvez uma ideia armazená-los em colunas. Esta opção mais óbvia e “ingênua” será mais ou menos assim (vamos chamá-la Opção 1 (padrão)para referência adicional):
RowKey
Alto-falantes
Vasya
1: Petia
2: Olia
3: Dasha
Petya
1: Masha
2: Vasya
Aqui, cada linha corresponde a um usuário da rede. As colunas têm nomes: 1, 2, ... - de acordo com o número de amigos, e os IDs dos amigos são armazenados nas colunas. É importante observar que cada linha terá um número diferente de colunas. No exemplo da figura acima, uma linha possui três colunas (1, 2 e 3), e a segunda possui apenas duas (1 e 2) - aqui nós mesmos usamos duas propriedades HBase que os bancos de dados relacionais não possuem:
- a capacidade de alterar dinamicamente a composição das colunas (adicionar um amigo -> adicionar uma coluna, remover um amigo -> excluir uma coluna)
- linhas diferentes podem ter composições de colunas diferentes
Vamos verificar nossa estrutura quanto ao cumprimento dos requisitos da tarefa:
- Lendo dados: para saber se Vasya é assinante de Olya, precisaremos subtrair toda a linha pela chave RowKey = “Vasya” e classifique os valores das colunas até “encontrarmos” Olya neles. Ou itere pelos valores de todas as colunas, “não atenda” Olya e retorne a resposta False;
- Editando dados: adicionando um amigo: para uma tarefa semelhante, também precisamos subtrair toda a linha usando a chave RowKey = “Vasya” para contar o número total de seus amigos. Precisamos desse número total de amigos para determinar o número da coluna na qual precisamos anotar o ID do novo amigo.
- Alterando dados: excluindo um amigo:
- Precisa subtrair toda a linha pela chave RowKey = “Vasya” e classifique as colunas para encontrar aquela em que está registrado o amigo a ser excluído;
- A seguir, após excluir um amigo, precisamos “deslocar” todos os dados em uma coluna para não obter “lacunas” na sua numeração.
Vamos agora avaliar o quão produtivos serão esses algoritmos, que precisaremos implementar no lado da “aplicação condicional”, usando . Vamos denotar o tamanho da nossa rede social hipotética como n. Então o número máximo de amigos que um usuário pode ter é (n-1). Podemos ainda negligenciar este (-1) para os nossos propósitos, uma vez que no âmbito da utilização de símbolos O não é importante.
- Lendo dados: é necessário subtrair toda a linha e iterar por todas as suas colunas no limite. Isso significa que a estimativa superior de custos será de aproximadamente O(n)
- Editando dados: adicionando um amigo: para determinar o número de amigos, você precisa percorrer todas as colunas da linha e, em seguida, inserir uma nova coluna => O(n)
- Alterando dados: excluindo um amigo:
- Semelhante à adição - você precisa passar por todas as colunas no limite => O(n)
- Após remover as colunas, precisamos “movê-las”. Se você implementar isso “de frente”, no limite precisará de até (n-1) operações. Mas aqui e mais adiante na parte prática usaremos uma abordagem diferente, que implementará um “pseudo-shift” para um número fixo de operações - ou seja, será gasto tempo constante nisso, independentemente de n. Este tempo constante (O(2) para ser exato) pode ser desprezado em comparação com O(n). A abordagem é ilustrada na figura abaixo: simplesmente copiamos os dados da “última” coluna para aquela da qual queremos excluir os dados e, em seguida, excluímos a última coluna:
No total, em todos os cenários recebemos uma complexidade computacional assintótica de O(n).
Você provavelmente já percebeu que quase sempre temos que ler a linha inteira do banco de dados e, em dois dos três casos, apenas percorrer todas as colunas e calcular o número total de amigos. Portanto, como tentativa de otimização, você pode adicionar uma coluna “count”, que armazena o número total de amigos de cada usuário da rede. Neste caso, não podemos ler a linha inteira para calcular o número total de amigos, mas ler apenas uma coluna de “contagem”. O principal é não esquecer de atualizar a “contagem” ao manipular os dados. Que. nós melhoramos Opção 2 (contagem):
RowKey
Alto-falantes
Vasya
1: Petia
2: Olia
3: Dasha
contagem: 3
Petya
1: Masha
2: Vasya
contagem: 2
Comparado com a primeira opção:
- Lendo dados: para obter uma resposta à pergunta “Vasya lê Olya?” nada mudou => O (n)
- Editando dados: adicionando um amigo: Simplificamos a inserção de um novo amigo, pois agora não precisamos ler a linha inteira e iterar sobre suas colunas, mas só podemos obter o valor da coluna “contagem”, etc. determine imediatamente o número da coluna para inserir um novo amigo. Isso leva a uma redução na complexidade computacional para O (1)
- Alterando dados: excluindo um amigo: Ao excluir um amigo, também podemos usar esta coluna para reduzir o número de operações de E/S ao “deslocar” os dados uma célula para a esquerda. Mas a necessidade de iterar pelas colunas para encontrar aquela que precisa ser excluída ainda permanece, então => O(n)
- Por outro lado, agora, ao atualizar os dados, precisamos atualizar a coluna “contagem” todas as vezes, mas isso leva um tempo constante, que pode ser negligenciado no âmbito dos símbolos O.
Em geral, a opção 2 parece um pouco mais óptima, mas é mais como “evolução em vez de revolução”. Para fazer uma “revolução” precisaremos Opção 3 (coluna).
Vamos virar tudo “de cabeça para baixo”: vamos atribuir nome da coluna ID do usuário! O que vai estar escrito na coluna em si não é mais importante para nós, que seja o número 1 (em geral, coisas úteis podem ser armazenadas ali, por exemplo, o grupo “família/amigos/etc.”). Essa abordagem pode surpreender o “leigo” despreparado que não tem experiência anterior trabalhando com bancos de dados NoSQL, mas é justamente essa abordagem que permite utilizar o potencial do HBase nesta tarefa de forma muito mais eficaz:
RowKey
Alto-falantes
Vasya
Petia: 1
Olia: 1
Dasha: 1
Petya
Masha: 1
Vasya: 1
Aqui obtemos várias vantagens ao mesmo tempo. Para entendê-los, vamos analisar a nova estrutura e estimar a complexidade computacional:
- Lendo dados: para responder à questão de saber se Vasya é assinante de Olya, basta ler uma coluna “Olya”: se estiver lá, então a resposta é Verdadeiro, se não – Falso => O(1)
- Editando dados: adicionando um amigo: Adicionando um amigo: basta adicionar uma nova coluna “ID do amigo” => O(1)
- Alterando dados: excluindo um amigo: basta remover a coluna Friend ID => O(1)
Como você pode ver, uma vantagem significativa desse modelo de armazenamento é que em todos os cenários que necessitamos, operamos com apenas uma coluna, evitando a leitura de toda a linha do banco de dados e, além disso, enumerando todas as colunas desta linha. Poderíamos parar por aí, mas...
Você pode ficar confuso e avançar um pouco mais no caminho de otimizar o desempenho e reduzir as operações de E/S ao acessar o banco de dados. E se armazenássemos as informações completas do relacionamento diretamente na própria chave de linha? Ou seja, faça a chave composta como userID.friendID? Neste caso, nem precisamos ler as colunas da linha (Opção 4 (linha)):
RowKey
Alto-falantes
Vasya. Petya
Petia: 1
Vasya.Olya
Olia: 1
Vasya.Dasha
Dasha: 1
Petya.Masha
Masha: 1
Petya. Vasya
Vasya: 1
Obviamente, a avaliação de todos os cenários de manipulação de dados em tal estrutura, como na versão anterior, será O(1). A diferença com a opção 3 estará apenas na eficiência das operações de I/O no banco de dados.
Bem, o último “arco”. É fácil perceber que na opção 4, a chave da linha terá comprimento variável, o que possivelmente pode afetar o desempenho (aqui lembramos que o HBase armazena dados como um conjunto de bytes e as linhas nas tabelas são classificadas por chave). Além disso, temos um separador que pode precisar ser tratado em alguns cenários. Para eliminar essa influência, você pode usar hashes de userID e friendID, e como ambos os hashes terão comprimento constante, você pode simplesmente concatená-los, sem separador. Então os dados da tabela ficarão assim (Opção 5 (hash)):
RowKey
Alto-falantes
dc084ef00e94aef49be885f9b01f51c01918fa783851db0dc1f72f83d33a5994
Petia: 1
dc084ef00e94aef49be885f9b01f51c0f06b7714b5ba522c3cf51328b66fe28a
Olia: 1
dc084ef00e94aef49be885f9b01f51c00d2c2e5d69df6b238754f650d56c896a
Dasha: 1
1918fa783851db0dc1f72f83d33a59949ee3309645bd2c0775899fca14f311e1
Masha: 1
1918fa783851db0dc1f72f83d33a5994dc084ef00e94aef49be885f9b01f51c0
Vasya: 1
Obviamente, a complexidade algorítmica de trabalhar com tal estrutura nos cenários que estamos considerando será a mesma da opção 4 - ou seja, O(1).
No total, vamos resumir todas as nossas estimativas de complexidade computacional em uma tabela:
Adicionando um amigo
Verificando um amigo
Removendo um amigo
Opção 1 (padrão)
O (n)
O (n)
O (n)
Opção 2 (contagem)
O (1)
O (n)
O (n)
Opção 3 (coluna)
O (1)
O (1)
O (1)
Opção 4 (linha)
O (1)
O (1)
O (1)
Opção 5 (hash)
O (1)
O (1)
O (1)
Como você pode ver, as opções 3 a 5 parecem ser as mais preferíveis e, teoricamente, garantem a execução de todos os cenários de manipulação de dados necessários em tempo constante. Nas condições da nossa tarefa, não há exigência explícita de obter uma lista de todos os amigos do usuário, mas em atividades reais de projeto, seria bom para nós, como bons analistas, “antecipar” que tal tarefa poderia surgir e “Espalhe um canudo.” Portanto, minhas simpatias estão do lado da opção 3. Mas é bem provável que em um projeto real esse pedido já pudesse ter sido resolvido por outros meios, portanto, sem uma visão geral de todo o problema, é melhor não fazer conclusões finais.
Preparação do experimento
Gostaria de testar na prática os argumentos teóricos acima - esse foi o objetivo da ideia que surgiu no fim de semana prolongado. Para isso, é necessário avaliar a velocidade de operação da nossa “aplicação condicional” em todos os cenários descritos de utilização do banco de dados, bem como o aumento deste tempo com o aumento do tamanho da rede social (n). O parâmetro alvo que nos interessa e que mediremos durante o experimento é o tempo gasto pela “aplicação condicional” para realizar uma “operação comercial”. Por “transação comercial” entendemos um dos seguintes:
- Adicionando um novo amigo
- Verificando se o usuário A é amigo do usuário B
- Removendo um amigo
Assim, tendo em conta os requisitos delineados na declaração inicial, o cenário de verificação surge da seguinte forma:
- Gravação de dados. Gere aleatoriamente uma rede inicial de tamanho n. Para nos aproximarmos do “mundo real”, o número de amigos que cada usuário possui também é uma variável aleatória. Meça o tempo durante o qual nossa “aplicação condicional” grava todos os dados gerados no HBase. Em seguida, divida o tempo resultante pelo número total de amigos adicionados - é assim que obtemos o tempo médio para uma “operação comercial”
- Lendo dados. Para cada usuário, crie uma lista de “personalidades” para as quais você precisa obter uma resposta se o usuário está inscrito nelas ou não. O comprimento da lista = aproximadamente o número de amigos do usuário, sendo que para metade dos amigos verificados a resposta deve ser “Sim”, e para a outra metade – “Não”. A verificação é realizada de forma que as respostas “Sim” e “Não” se alternem (ou seja, a cada segundo caso teremos que percorrer todas as colunas da linha para as opções 1 e 2). O tempo total de triagem é então dividido pelo número de amigos testados para obter o tempo médio de triagem por sujeito.
- Exclusão de dados. Remova todos os amigos do usuário. Além disso, a ordem de exclusão é aleatória (ou seja, “embaralhamos” a lista original usada para registrar os dados). O tempo total de verificação é então dividido pelo número de amigos removidos para obter o tempo médio por verificação.
Os cenários precisam ser executados para cada uma das 5 opções de modelo de dados e para diferentes tamanhos de rede social para ver como o tempo muda à medida que cresce. Dentro de um n, as conexões na rede e a lista de usuários a verificar devem, obviamente, ser as mesmas para todas as 5 opções.
Para um melhor entendimento, segue abaixo um exemplo de dados gerados para n= 5. O “gerador” escrito produz três dicionários de ID como saída:
- o primeiro é para inserção
- o segundo é para verificar
- terceiro – para exclusão
{0: [1], 1: [4, 5, 3, 2, 1], 2: [1, 2], 3: [2, 4, 1, 5, 3], 4: [2, 1]} # всего 15 друзей
{0: [1, 10800], 1: [5, 10800, 2, 10801, 4, 10802], 2: [1, 10800], 3: [3, 10800, 1, 10801, 5, 10802], 4: [2, 10800]} # всего 18 проверяемых субъектов
{0: [1], 1: [1, 3, 2, 5, 4], 2: [1, 2], 3: [4, 1, 2, 3, 5], 4: [1, 2]} # всего 15 друзей
Como você pode ver, todos os IDs maiores que 10 no dicionário para verificação são justamente aqueles que certamente darão a resposta Falso. A inserção, verificação e exclusão de “amigos” são feitas exatamente na sequência especificada no dicionário.
O experimento foi realizado em um laptop rodando Windows 10, onde o HBase estava rodando em um contêiner Docker e o Python com Jupyter Notebook rodando no outro. O Docker recebeu 2 núcleos de CPU e 2 GB de RAM. Toda a lógica, como a emulação da “aplicação condicional” e o “piping” para geração de dados de teste e medição de tempo, foi escrita em Python. A biblioteca foi usada para trabalhar com HBase , para calcular hashes (MD5) para a opção 5 - hashlib
Levando em consideração o poder computacional de um laptop específico, um lançamento para n = 10, 30,… foi selecionado experimentalmente. 170 – quando o tempo total de operação do ciclo completo de testes (todos os cenários para todas as opções para todos n) era ainda mais ou menos razoável e cabia durante uma festa de chá (em média 15 minutos).
Aqui é necessário observar que neste experimento não estamos avaliando principalmente números absolutos de desempenho. Mesmo uma comparação relativa entre duas opções diferentes pode não ser totalmente correta. Agora estamos interessados na natureza da mudança no tempo dependendo de n, pois levando em consideração a configuração acima da “bancada de teste”, é muito difícil obter estimativas de tempo “limpas” da influência de fatores aleatórios e outros ( e tal tarefa não foi definida).
Resultado da experiência
O primeiro teste é como muda o tempo gasto no preenchimento da lista de amigos. O resultado está no gráfico abaixo.
As opções 3 a 5, como esperado, mostram um tempo de “transação comercial” quase constante, que não depende do crescimento do tamanho da rede e de uma diferença indistinguível no desempenho.
A opção 2 também mostra desempenho constante, mas um pouco pior, quase exatamente 2 vezes em relação às opções 3-5. E isso é uma boa notícia, pois se correlaciona com a teoria - nesta versão o número de operações de E/S de/para o HBase é exatamente 2 vezes maior. Isto pode servir como evidência indireta de que nossa bancada de testes, em princípio, oferece boa precisão.
A opção 1 também, como esperado, acaba sendo a mais lenta e demonstra um aumento linear no tempo gasto na adição de um ao outro ao tamanho da rede.
Vejamos agora os resultados do segundo teste.
As opções 3 a 5 comportam-se novamente como esperado - tempo constante, independente do tamanho da rede. As opções 1 e 2 demonstram um aumento linear no tempo à medida que o tamanho da rede aumenta e um desempenho semelhante. Além disso, a opção 2 acaba sendo um pouco mais lenta - aparentemente devido à necessidade de revisar e processar a coluna adicional de “contagem”, que se torna mais perceptível à medida que n cresce. Mas ainda me absterei de tirar quaisquer conclusões, uma vez que a precisão desta comparação é relativamente baixa. Além disso, essas proporções (cuja opção, 1 ou 2, é mais rápida) mudaram de corrida para corrida (mantendo a natureza da dependência e “indo pescoço a pescoço”).
Bem, o último gráfico é o resultado de testes de remoção.
Novamente, não há surpresas aqui. As opções 3 a 5 realizam a remoção em tempo constante.
Além disso, curiosamente, as opções 4 e 5, ao contrário dos cenários anteriores, apresentam um desempenho visivelmente ligeiramente pior do que a opção 3. Aparentemente, a operação de eliminação de linhas é mais cara do que a operação de eliminação de colunas, o que geralmente é lógico.
As opções 1 e 2, como esperado, demonstram um aumento linear no tempo. Ao mesmo tempo, a opção 2 é consistentemente mais lenta que a opção 1 – devido à operação de E/S adicional para “manter” a coluna de contagem.
Conclusões gerais do experimento:
- As opções 3 a 5 demonstram maior eficiência, pois aproveitam o HBase; Além disso, seu desempenho difere entre si por uma constante e não depende do tamanho da rede.
- A diferença entre as opções 4 e 5 não foi registrada. Mas isto não significa que a opção 5 não deva ser utilizada. É provável que o cenário experimental utilizado, tendo em conta as características de desempenho da bancada de testes, não tenha permitido a sua detecção.
- A natureza do aumento do tempo necessário para a realização de “operações comerciais” com dados confirmou geralmente os cálculos teóricos obtidos anteriormente para todas as opções.
Epílogo
As experiências grosseiras realizadas não devem ser tomadas como verdade absoluta. Existem muitos fatores que não foram levados em consideração e distorceram os resultados (essas flutuações são especialmente visíveis nos gráficos com um tamanho de rede pequeno). Por exemplo, a velocidade de economia usada pelo happybase, o volume e o método de implementação da lógica que escrevi em Python (não posso afirmar que o código foi escrito de maneira ideal e usou efetivamente os recursos de todos os componentes), talvez os recursos de cache HBase, atividade em segundo plano do Windows 10 no meu laptop, etc. Em geral, podemos assumir que todos os cálculos teóricos demonstraram experimentalmente a sua validade. Bem, ou pelo menos não foi possível refutá-los com tal “ataque frontal”.
Concluindo, recomendações para todos que estão apenas começando a projetar modelos de dados em HBase: abstraiam da experiência anterior trabalhando com bancos de dados relacionais e lembrem-se dos “mandamentos”:
- Ao projetar, partimos da tarefa e dos padrões de manipulação de dados, e não do modelo de domínio
- Acesso eficiente (sem varredura completa da tabela) – somente por chave
- Desnormalização
- Linhas diferentes podem conter colunas diferentes
- Composição dinâmica de alto-falantes
Fonte: habr.com