Criando seu próprio banco de dados

• Explica os princípios fundamentais e o processo de implementação de um banco de dados chave-valor.
• Começa com armazenamento persistente e busca por meio de um sistema de arquivos.
• Na inserção, atualização e remoção de dados surgem problemas de ineficiência.
• Evolui gradualmente para uma estrutura mais eficiente com arquivo Append-Only, índice, ordenação e compactação de segmentos.
• Está ligado a estruturas modernas como a árvore LSM e é usada em sistemas reais de grande escala.

---

Introdução: o início de criar um banco de dados

Se partirmos do pressuposto de que não existe o conceito de banco de dados, exploramos passo a passo como criar um banco de dados próprio. Nesta etapa, observamos o processo de implementação do tipo mais simples de banco de dados chave-valor.

Ideia básica: armazenamento persistente com arquivos

• O objetivo do banco de dados é armazenar dados de forma persistente e pesquisar de modo eficiente depois.
• O método mais comum é registrar cada par chave-valor em um arquivo usando o sistema de arquivos.
• Ao armazenar dados, por exemplo, adiciona-se conteúdo ao arquivo no formato $ db set 1 "Lorem ipsum".
• Para buscar dados, percorremos todos os pares chave-valor do arquivo sequencialmente até encontrar a key desejada.
• Na atualização, substitui-se o valor da key diretamente no arquivo; na remoção, elimina-se o registro do arquivo.

Problema: atualização in-place ineficiente

• Alterar ou remover dados diretamente no arquivo é muito ineficiente.
• Como o arquivo é apenas um fluxo de bytes, mudar dados no meio dele exige mover todos os bytes que vêm depois.
• Por exemplo, ao substituir um registro por um novo valor com tamanho diferente, é necessário deslocar todo o conteúdo posterior.
• Quanto maior o volume de dados, maior o impacto em desempenho e eficiência.

Melhoria 1: estrutura de arquivo Append-Only

• Ao atualizar e remover, os dados existentes permanecem como estão, e passa-se a adicionar apenas novos registros no fim do arquivo.
• Sempre que os dados mudam, adiciona-se um novo registro e o algoritmo passa a procurar o último valor da key.
• A remoção é marcada com um valor especial de "tombstone" (como null).
• Vantagem: permite gravação eficiente sem mover dados antigos.
• Desvantagem: o arquivo cresce com o tempo por causa de duplicatas e marcas de remoção.
• A busca ainda é lenta, pois continua exigindo varredura completa.

Melhoria 2: controle de tamanho do arquivo e compactação (compaction)

• Para evitar que o arquivo cresça indefinidamente, quando ele atinge determinado tamanho, cria-se um novo arquivo (segmento) e remove-se do arquivo anterior dados desnecessários (duplicados/removidos), reduzindo seu tamanho (compaction).
• Na compaction, mantém-se apenas os dados realmente necessários e removem-se registros antigos ou apenas marcadores de exclusão.
• A estrutura evolui para gerenciar vários arquivos de segmento, passando a mesclá-los (merge) conforme necessário.

Melhoria 3: busca rápida com índice (Index)

• Cria-se um índice em memória (hash table) com a posição (offset) de cada key no arquivo, permitindo busca rápida.
• Ao buscar, consulta-se o índice primeiro e lê-se diretamente a posição correspondente no arquivo.
• trade-off: a busca fica mais rápida, mas por estar em memória, um grande número de keys pode esbarrar no limite de memória.
• Por causa do gerenciamento do índice, o desempenho de gravação é reduzido em certa medida.

Melhoria 4: Sorted String Tables ordenadas e Sparse Index

• Ao manter os dados sempre ordenados pela key, é possível obter alta eficiência em consultas de intervalo (range query).
• Com essa ordenação, o índice pode ser armazenado para apenas algumas keys (índice esparso), e não para todas.
• Ajustando a densidade do índice, é possível controlar o trade-off entre uso de memória e eficiência de busca.

Implementação: combinação memória + disco e persistência

• Novos dados são primeiro gravados em uma lista em memória ordenada e, adicionalmente, registrados em um arquivo append-only para função de backup.
• Quando a lista em memória cresce, ela é gravada em arquivo on-disk (SST) de forma ordenada, atualizando o índice.
• Na consulta, verifica-se primeiro a memória; se não encontrar, busca-se no disco com o índice.
• Arquivos on-disk são mantidos como imutáveis, e atualizações/remover também são tratadas com novos registros.
• Dados duplicados ou removidos são compactados periodicamente (compaction) para controlar o tamanho do arquivo.

Surgimento da árvore LSM (Log-Structured Merge Tree)

• A estrutura evoluída acima é usada amplamente com o nome de árvore LSM.
• É uma combinação de memtable e sorted string table (SST) on-disk, adequada para alto desempenho em ambientes de grande escala.
• É usada como estrutura de dados principal em sistemas de banco de dados chave-valor em grande escala, como LevelDB e Amazon DynamoDB.
• Embora haja desvantagens e diferenças em relação a outras estruturas (como bancos relacionais baseados em B-Tree), ela comprova forte desempenho em alta carga e escalabilidade.

Conclusão

• Partindo de uma base simples em arquivos, a estrutura evolui para uma melhor arquitetura ao combinar append-only, índice, ordenação, compaction de segmentos e integração memória-disco.
• É possível aprender, por meio da implementação direta, sobre o funcionamento interno e as decisões estruturais de um banco de dados.
• A estrutura de árvore LSM desempenha um papel padrão em sistemas modernos de dados em larga escala.
• Ainda há espaço para investigar outras abordagens, como a estrutura B-Tree de bancos relacionais.

[GN⁺]

Comentário do Hacker News

• O design e os exemplos deste texto me agradaram muito; a estrutura de leitura ficou muito clara. Esse tipo de exercício também foi uma experiência bastante divertida. Começar de um estado de vazio permite uma validação real de quanto você realmente sabe.
  • Eu também, no passado, tinha uma postura apressada do tipo “não faça seu próprio banco de dados, não use banco de dados KV, use só SQL”. Mas esse pensamento surgiu depois que eu tentei projetar um banco de dados diretamente, ou evitar SQL para usar apenas KV, e acabei reinventando SQL de forma precária. Aprender passando pela experiência prática tem um valor claro.
  • O único ponto negativo foi usar lorem ipsum como exemplo; por isso acabei passando rápido sem focar. Um exemplo com dados reais chamaria muito mais atenção. Fora isso, é realmente um ótimo texto.
• Quando se diz que “a árvore LSM, usada normalmente em serviços como o DynamoDB, apresenta excelente desempenho até em larga escala… com até 80 milhões de requisições por segundo”, há um pequeno risco de interpretação errada. O LSM é usado no motor de armazenamento por nó, mas não é explicado como todo o sistema distribuído escala para 80 milhões de RPS. Pelo que me lembro, o paper original do Dynamo usava BerkeleyDB (b-tree ou LSM), e em 2012 houve uma transição completa para um motor baseado em LSM.
• Li alguns artigos da lista e achei o design e as animações realmente bonitos.
• O primeiro exemplo em “Sorting in Practice” parece quebrado. No texto de explicação, ele diz que após ordenar na memória, os dados devem ser gravados no disco já ordenados, mas no exemplo real, a ordenação se perde ao escrever no disco. O exemplo de flush da parte de recap (o segundo) também é assim, embora o texto diga que o arquivo é gravado em ordem.
• Achei o artigo interessante. Recentemente, estou modelando atividade de desenvolvedores como um sistema chave-valor de séries temporais, com desenvolvedor como chave e commit como valor. Encontro um problema semelhante: o log cresce rapidamente, o índice pesa cada vez mais, e consultas por intervalo ficam lentas. Fiquei curioso sobre como decidir quais dados descartar durante a compactação de segmentos; manter o equilíbrio entre novidade e retenção parece difícil.
• Nas últimas 4 semanas, eu fiquei mergulhado em escrever um triple store do zero. Se esse texto tivesse saído um pouco antes, teria entendido certos insights mais cedo. Uma pena.
• Se o autor ler isso, fiquei curioso se seria possível adicionar RSS no site; quero acompanhar via Feedly.
• Se você quiser criar seu próprio banco de dados, recomendo este livro online gratuito
  • Eu lembro de um artigo de antes em que alguém explicou os conceitos básicos de banco de dados com exemplo em bash (ex.: “Criando DB com bash”), mas não consigo achar agora. Se alguém souber esse link, compartilharia?
• O tráfego já está alto demais para o site ficar inacessível.
  • Vai precisar de um banco de dados mais rápido.
• Gosto muito dessa abordagem de explicar desde os primeiros princípios. Seguindo o texto, fica fácil entender em cada etapa qual problema surge e quais problemas adicionais aparecem ao resolvê-lo; isso permite chegar a uma solução realmente satisfatória.