Resumo comentado: Designing Data-Intensive Applications — Parte 2
Olá!
Vamos continuar explorando o livro mencionado no artigo anterior?
No capítulo 3, ocorre um detalhamento sobre o conceitos fundamentais relacionados a armazenamento (Storage) e Recuperação de dados (Retrieval). Vamos começar tentando construir um banco de dados partindo de alguns blocos fundamentais.
O exemplo de mecanismo mais simples que é dado para suportar essa funcionalidade é um armazenamento usando um arquivo, no qual os dados são inseridos no final do mesmo e consequentemente lidos por algum tipo de varredura, usando Bash. O que acarreta em performance adequada na escrita (O(1)) e uma não tão boa assim na leitura (O(N)).
Aqui temos um dos dilemas mais comuns da computação: a eterna luta entre características conflitantes entre si que invariavelmente nos obriga a tomar alguma decisão difícil na arquitetura desses sistemas, os famosos trade-offs.
Para melhorar a performance de leitura nesse nosso mecanismo rudimentar de armazenamento, podemos usar um índice. Que é uma estrutura de dados adicional que é aplicada em cima dos dados para que consigamos efetuar buscas de uma forma mais efetiva. Para esse cenário, é possível implementar esse mecanismo usando a memória da máquina que tá rodando nosso banco. O índice é composto de uma chave, que aponta para um valor determinado no conjunto de dados. O intuito de usar uma chave é que para computadores, é mais fácil de percorrer chaves ao invés de todos os dados. Ou seja, é o uso de uma técnica de indireção.
Aqui vale uma imagem para ilustrar melhor o caminho da informação ao utilizar índices:
Visando melhorar o mecanismo rudimentar de armazenamento de dados em um arquivo, o livro sugere usar Hash Indexes para termos esse mapeamento de chaves e valores de forma otimizada na memória do computador. Com isso conseguimos fazer buscas mais rápidas recorrendo a essa estrutura de dados.
Porém, ainda há alguns problemas não resolvidos no nosso semi banco de dados com esses mecanismos, a saber: como deletar registros de forma eficiente? Será que usar arquivos para armazenar os registros é uma boa idéia? Esse mecanismo é tolerante a falhas? O que acontece caso o mecanismo pare de funcionar durante a escrita de algum registro? Há suporte para múltiplos usuários tentando efetuar operações ao mesmo tempo (concorrência)? Como suportar atualizações (updates) ao invés de inserções no fim do arquivo (appends) no momento de atualizar os dados?
Uma estrutura de dados recomendada como evolução do nosso mecanismo é o uso de Sorted String Tables (SSTables), que se baseia no no mesmo uso de chave/valores, porém, ordenados por chave. Ou seja, antes de ir no disco de fato buscar dados, há uma camada de memória antes (ou seja, mais uma camada de indireção) que precisa ser consultada. Essa estrutura contém um dicionário com uma outra chave como índice (nesse caso, pode ser uma string qualquer) + o offset do valor desejado. O intuito de usar offset é porque é mais fácil utilizar dessa técnica de endereçamento para percorrer arquivos. É possível encontrar nas bibliotecas padrão da maioria das linguagens mecanismos que trabalham dessa forma para manipulação de arquivos.
Com SSTables, não precisamos manter todo o índice na memória, apenas a estrutura inicial que mapeia para as localidades das chaves desejadas correspondentes, o que traz uma outra vantagem: a possibilidade de compactação desses blocos de forma sucessiva. Aqui o mecanismo é simples: agrupe pela chave em arquivos separados para tal e de tempos em tempos, usando algum processo em segundo plano.
Além disso, é possível usar uma MemTable como mais um mecanismo adicional de facilitação para a gestão dos registros. Utilizando algoritmos que ordenam os dados internamente, como Árvores Rubro-Negras (Red-Black Trees) ou Árvores AVL (AVL Tree), é possível inserir os dados sem ordem definidas e lê-los ordenados.
Para ficar menos abstrato, o fluxo completo de uma SSTable é o seguinte:
Resumindo os passos:
Ao receber uma solicitação de escrita, adicione esses dados na MemTable, que irá ordena-la internamente para você.
Quando a MemTable ficar grande demais, escreva no disco o segmento mais recente (como já há ordenação prévia, isso é fácil de saber qual é). É possível limpar a MemTable nesse processo também.
Em caso de leitura, leia da MemTable primeiro. Caso o dado não esteja na memória, faça uma varredura nos segmentos escritos em disco e retorne.
De tempos em tempos, compacte os dados escritos em disco e faça o expurgo dos dados antigos ou obsoletos.
Esse mecanismo de compactação de arquivos utilizando segmentos em arquivos é usado em bancos de dados como LevelDB e RocksDB e é chamado de Log Structured Merge-Tree (LSM-Trees).
A biblioteca Lucene (base de sistemas como o ElasticSearch e do Apache Solr), que suportam Busca de Texto Completo (Full-Text Search), possui funcionalidades similares a esse mecanismo de compactação de motores LSM em seu core.
Apesar de parecer um mecanismo bastante robusto, LSM perde em popularidade para o mecanismo Árvore B (B-Tree). Que corrobora para uma coisa que eu sempre falo: todos os problemas da computação foram resolvidos na década de 70 (ou até antes). Portanto, sem nenhuma supresa, esse mecanismo é dessa época (e usado até hoje, para variar).
Ao invés de escrever os segmentos de forma sequencial e em blocos variáveis de tamanho como o LSM, esse mecanismo armazena os dados em blocos (ou páginas) de tamanho fixo, como 4KB (dado a sinergia que esse tamanho possui com o hardware). Para quem não sabia, um disco geralmente é gerenciado dessa forma. Mais detalhes sobre armazenamento aqui.
Vamos ilustrar o funcionamento desse mecanismo com a seguinte imagem:
Aqui o mecanismo é simples: ocorre uma busca a partir da página/nó inicial, que contém referências para outras páginas filhas, usando um valor limite de referências que cada nó pode ter de referências filhas. Esse limite é chamado de fator de ramificação (Branching Factor). Cada nó/página contém dados ordenados em um determinado intervalo para otimizar a busca.
Em caso de leitura ou atualizações, basta seguir as referências entre as páginas para tudo ser mantido em uma ordem coerente (estruturas de árvore tem como característica o balanceamento na inserção, naturalmente). Com essa estrutura, é possível obter O(log n) na leitura de forma consistente, além de um grande potencial de armazenamento usando poucos recursos. Um exemplo mencionado no livro é que com páginas de 4KB e fatores de ramificação de 500 registros, é possível armazenar com somente 4 níveis na estrutura da árvore até 256 TB de dados.
Porém, há algumas limitações em termos de confiabilidade em se tratando do uso de B-Trees. Uma delas é que, como usamos referências na árvore para ter o controle de onde estão os dados, o que acontece caso o banco de dados sofra alguma pane? Muito provavelmente irá ocorrer algum tipo de falha de integridade.
A solução para tal é (advinhe!): mais uma camada de indireção, chamada de WAL (Write-Ahead Log) ou redo-log. Que nada mais que um arquivo em que as alterações são escritas de forma contínua para que, em caso de algum crash no mecanismo principal, as alterações possam ser lidas desse local e refeitas na B-Tree.
Com isso, temos um mecanismo minimamente funcional e tolerante a falhas!
O livro diz que LSM-Trees são mais rápidas para escritas e B-Trees se saem melhor para leitura de dados. Porém, vou citar literalmente um trecho do livro que achei curioso:
However, benchmarks are often inconclusive and sensitive to details of the workload. You need to test systems with your particular workload in order to make a valid comparison.
Ou seja, como tudo em computação, depende e talvez seja necessário analisar caso-a-caso.
Agora eu paro por aqui dado que esse artigo tá muito grande.
Até a próxima!
Você gostou do conteúdo e gostaria de fazer mentoria comigo? Clique aqui e descubra como.
