Designing Data-Intensive Applications: Capítulo 3 — Armazenamento e Recuperação

Existem diferentes tipos de bancos de dados, e cada um tem mecanismos diferentes para armazenar e recuperar informações. Vamos descobrir os trade-offs de cada uma.

Como bancos de dados lidam com armazenamento e recuperação de dados?

Quando estamos fazendo qualquer aplicação séria, quase sempre usamos algum banco de dados. Alguns exemplos comuns são:

• PostgreSQL

• MySQL

• SQLite

• MongoDB

• DynamoDB

Esses bancos de dados geralmente são ideais para processar transações. Geralmente usados em sistemas usados pelos usuários, o que quer dizer que são otimizados para um alto volume de tráfego. São conhecidos como OLTP: online transaction processing.

Porém, existe também um outro tipo de banco de dados, menos conhecido. Eles são usados para análise de dados. O que quer dizer menor volume de requisições, mas com um aumento no número de informações requisitada (query). São conhecidos como OLAP: online analytics processing.

Bem vindos ao Capítulo 3 do Designing Data-Intensive Applications: Armazenamento e Recuperação. Vamos descobrir sobre como bancos de dados armazenam dados em memória e no disco para otimizar para diferentes casos de uso.

Enquanto OLTP lida com muitas operações simples e rápidas, OLAP processa poucas queries complexas que analisam grandes volumes de dados.

✨ O que esperar do artigo

• As estruturas de dados que armazenam os dados dos bancos de dados

• As diferenças entre bancos de dados otimizados para transações ou analytics

• Como escolher a engine apropriada para a tua aplicação

As Estruturas por Trás dos Bancos de Dados

Todo banco de dados precisa fazer duas coisas fundamentais: guardar dados quando você pede e devolvê-los depois. Parece simples, mas a maneira como isso é feito afeta drasticamente a performance.

Vamos começar com o exemplo mais simples possível - um banco de dados feito em bash:

db_set () {
    echo "$1,$2" >> database
}

db_get () {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

Este exemplo mostra um banco de dados key-value onde cada linha tem uma chave e um valor separados por vírgula. O interessante é que mesmo sendo extremamente simples, ele já demonstra um conceito fundamental: o log.

O log é apenas um arquivo onde novos dados são sempre adicionados ao final. Esta abordagem tem algumas vantagens importantes:

• Escrever sequencialmente no disco é muito rápido

• O formato é resistente a crashes (dados parcialmente escritos ficam no final)

• Concorrência é mais simples (apenas um escritor)

Porém, a busca é terrível - precisamos ler o arquivo inteiro para encontrar uma chave. Para resolver isso, precisamos de um índice.

Indexação e Estruturas de Dados

Um índice é uma estrutura de dados adicional que nos ajuda a encontrar dados mais rapidamente.

Hash Indexes

A forma mais simples de índice é um hash map em memória. O Bitcask (engine padrão do Riak) usa essa abordagem:

• Mantém um mapa em memória de todas as chaves

• Cada chave aponta para a posição do valor no disco

• Muito eficiente para leitura (apenas um acesso ao disco)

• Limitado pela memória RAM disponível

Esta abordagem é ideal quando:

• Cada chave cabe na memória

• Cada chave tem muitas atualizações

• Leituras são mais comuns que escritas

O hash index foi um dos primeiros a ser criados. Porém, as principais estratégias usadas hoje em dia são as LSM-Trees e B-Trees.

Em um Hash Index, o principal limitador é a RAM necessária para armazenar as chaves, que direcionam para os buckets. Os buckets, então, apontam diretamente para o disco, de modo que apenas uma leitura é necessária. Fonte: Database Indexes: Hash and B-Tree Indexing

Log-Structured (LSM-Trees)

Bancos como Cassandra, RocksDB e LevelDB usam uma abordagem chamada LSM-tree (Log-Structured Merge Tree). A ideia é:

1. Manter um índice em memória para escritas recentes

2. Periodicamente despejar esse índice para o disco em arquivos ordenados

3. Mesclar esses arquivos em background para manter a performance

Esta abordagem é ótima para escritas frequentes, pois transforma escritas aleatórias em sequenciais.

LSM-trees otimizam escritas mantendo dados recentes em memória (Memtable) e periodicamente mesclando arquivos ordenados em disco (SSTables), reduzindo escritas aleatórias.

Page-Oriented (B-Trees)

O B-tree é o representante mais famoso desta família, usado em praticamente todos os bancos relacionais. Ele:

1. Divide os dados em páginas de tamanho fixo (geralmente 4KB)

2. Mantém essas páginas em uma estrutura de árvore balanceada

3. Atualiza as páginas diretamente no disco quando necessário

Esta abordagem é mais eficiente para leituras aleatórias, pois precisa ler menos dados do disco. Além disso, é mais escalável que os índices hash, por precisar de menos memória para localizar os dados.

B-tree com fator de ramificação 3: a raiz e nós internos contêm valores divisores que guiam a busca, enquanto as folhas armazenam os dados reais. Por exemplo, para encontrar 275, seguimos 200 < 275 < 500 na raiz, depois 275 < 300 no nó interno.

Comparando B-Trees e LSM-Trees

A escolha entre essas abordagens depende do seu caso de uso:

Para OLTP (processamento de transações):

• Se suas escritas são frequentes: considere LSM-trees

• Se suas leituras são críticas: B-trees podem ser melhores

• Se tudo precisa caber em memória: estruturas em memória como Redis

Para OLAP (análise de dados):

• Armazenamento colunar geralmente é melhor

• Compressão é mais importante que velocidade de escrita

• Considere data warehouses especializados

A chave é entender seus padrões de acesso: quanto você lê vs escreve, quão aleatório é o acesso, quanto pode ficar em memória.

Bancos In-Memory

Com memória RAM cada vez mais barata, alguns bancos optam por manter todos os dados em memória:

Vantagens:

• Performance extremamente alta

• Mais simples de implementar

• Bom para dados que precisam de acesso muito rápido

Desvantagens:

• Custo por GB maior que disco

• Limitado ao tamanho da RAM

• Precisa estratégia para persistência

Exemplos incluem:

• Redis: para caching, estruturas de dados como filas de prioridades, messageria

• Memcached: para caching simples

• VoltDB: para OLTP de alta performance

Outras Estruturas de Indexação

Além de B-trees e LSM-trees, existem outras estruturas especializadas:

Full-Text Search

Quando precisamos pesquisar texto completo, como em um mecanismo de busca, usamos índices especializados:

• Índices Invertidos: Mapeiam palavras para documentos

• Tries: Árvores otimizadas para busca de strings

• Fuzzy Search: Permite encontrar palavras similares

O Elasticsearch e Lucene, por exemplo, usam uma combinação de LSM-trees com índices invertidos para permitir buscas eficientes em texto.

Índices Espaciais

Para dados geográficos (como encontrar restaurantes próximos), usamos:

• R-trees

• Geohash

• Quadtrees

Índices Multi-dimensionais

Quando precisamos buscar por múltiplas dimensões simultaneamente (como cor, tamanho e preço de produtos), podemos usar:

• Space-filling curves

• K-d trees

• R-trees multi-dimensionais

Processamento de Transações ou Analytics

Quando uma empresa cresce, geralmente separa seus sistemas em duas partes:

1. Sistemas OLTP para operações do dia a dia

2. Data warehouses para análise de dados

Por que essa separação? Principalmente porque analistas fazendo queries complexas podem afetar a performance do sistema principal.

Data Warehouses

Um data warehouse é um banco separado que contém cópias dos dados de vários sistemas OLTP. Os dados passam por um processo chamado ETL (Extract, Transform, Load):

1. Extract: Extrai dados dos sistemas fonte

2. Transform: Limpa e padroniza os dados

3. Load: Carrega no warehouse em um formato otimizado para análise

O processo ETL reduz e otimiza dados: extraindo das fontes OLTP, transformando para análise, e carregando no data warehouse. Note como o volume de dados diminui de 100GB para 25GB após processamento.

Ferramentas populares incluem:

• Amazon Redshift

• Google BigQuery

• Snowflake

• Apache Hive

• PostHog Data Warehouse

Os dados em um data warehouse geralmente são organizados de forma dimensional, com:

• Tabelas de fatos: eventos ou transações (ex: vendas)

• Tabelas de dimensões: dados de referência (ex: produtos, clientes)

• Métricas agregadas: cálculos comuns pré-computados

Essa organização permite queries analíticas complexas sem impactar os sistemas OLTP.

Armazenamento Colunar

Data warehouses geralmente usam um formato diferente de armazenamento: em vez de guardar dados por linha (como OLTP), guardam por coluna.

Por exemplo, uma tabela de vendas tradicional vs colunar:

# Formato tradicional (por linha)
row1: {date: 2024-01-01, product_id: 123, quantity: 1, price: 10}
row2: {date: 2024-01-01, product_id: 456, quantity: 2, price: 20}

# Formato colunar
dates:     [2024-01-01, 2024-01-01]
products:  [123, 456]
quantities:[1, 2]
prices:    [10, 20]

Por que isso é melhor para análise?

• Só precisa ler as colunas necessárias para a query

• Dados similares ficam juntos, permitindo melhor compressão

• Mais fácil de computar agregações (somas, médias, etc)

Como é a visualização de um banco de dados baseado em colunas vs baseado em linhas. Ainda sim, interagimos com o banco de dados do mesmo jeito: tabelas e dados nas tabelas. A diferença é como o dado é guardado. Fonte: In-depth: ClickHouse vs PostgreSQL

Otimizações Avançadas

Tanto LSM-trees quanto armazenamento colunar têm complexidades que precisam ser gerenciadas:

Write Amplification: Uma escrita pode causar múltiplas escritas no disco

• Em LSM-trees: devido à compactação

• Em B-trees: devido à divisão de páginas

• Em colunar: ao atualizar uma linha, precisa atualizar várias colunas

Compactação: Process de mesclar e limpar dados

• Remove registros obsoletos

• Reorganiza dados para melhor eficiência

• Acontece em background para não afetar performance

Bloom Filters: Estrutura probabilística que ajuda a evitar leituras desnecessárias

• Diz se uma chave definitivamente não existe

• Ou se talvez exista

• Muito usado em LSM-trees para evitar procurar em vários arquivos

📚 Referências e leituras adicionais

1. Designing Data-Intensive Applications - O livro que inspirou este artigo

2. The Log-Structured Merge-Tree - O artigo original sobre LSM-trees

3. In-depth: ClickHouse vs PostgreSQL - Artigo do PostHog sobre as diferenças entre o PostgreSQL (OLTP) vs ClickHouse (OLAP)

🌟 Resumo

• Bancos de dados são fundamentalmente logs com índices

• LSM-trees são ótimas para escritas frequentes, B-trees para leituras aleatórias

• OLTP vs OLAP exigem otimizações diferentes

• Data warehouses usam armazenamento colunar para análises eficientes

• A escolha da engine deve ser baseada nos seus padrões de acesso

---

Muito obrigado por ser um assinante ou leitor, e ter chegado até o final!

Se você quiser fazer mais algo pra me ajudar, compartilhe esse artigo com outras pessoas e clique no botão de ❤️ curtir.

Quer fazer parte da comunidade? Entre em nosso servidor no Discord! 💬