Introdução

A maioria de nós trata o banco de dados como a única parte da stack que nunca abre. Você escreve um INSERT, ele volta rápido, e quando para de voltar rápido você cria um índice e torce. Funciona até uma migration travar uma tabela por vinte minutos, ou uma query que usava índice ontem fazer sequential scan hoje, e ninguém no time conseguir explicar por quê.

Esta série abre a caixa. Cada artigo pega uma camada de um engine de banco (páginas, B-trees, LSM trees, write-ahead log, MVCC, índices, planner, replicação) e mostra como ela funciona de verdade, usando PostgreSQL e SQLite como código real para ler. A série Data Structures with Golang montou árvores e hash tables em memória; aqui a gente vê o que muda quando essas estruturas precisam viver no disco e sobreviver a uma queda de energia.

As duas metades de um banco

Tirando o protocolo de rede e os arquivos de configuração, um banco relacional é mais ou menos dois programas colados.

A camada de query recebe texto e transforma em trabalho: faz o parse do SQL, confere contra o catálogo, escolhe um plano e executa esse plano como uma árvore de operadores (scan, filtro, join, sort).

O storage engine cuida dos bytes: como as linhas ficam organizadas em páginas de tamanho fixo, quais páginas ficam em cache na memória, como os índices acham as linhas, como uma alteração vira durável antes do commit retornar, e como duas transações evitam ver o trabalho pela metade uma da outra.

A maior parte da série fica do lado do storage, porque é de lá que vem o comportamento que surpreende. Um planner escolhendo um plano ruim normalmente está reagindo a algo real sobre páginas e estatísticas. Um UPDATE lento no PostgreSQL faz sentido quando você sabe que ele escreve uma versão nova inteira da linha em vez de alterar a antiga no lugar.

Roadmap da série

Cada camada se apoia na anterior. MVCC não faz muito sentido antes de você saber como é uma página e um registro de WAL, então a ordem importa.

Os exemplos de código são em Go, igual à série de estruturas de dados. São pequenos e servem para mostrar uma ideia, não para competir com um engine de verdade.

Um store append-only e onde ele quebra

O jeito mais rápido de entender por que os engines são construídos do jeito que são é construir a coisa mais burra que funciona e ver ela quebrar. Aqui vai um key-value store que faz append de toda escrita num arquivo e mantém um hash map da chave para o offset em bytes do registro mais recente:

package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strings"
)

type DB struct {
	f     *os.File
	index map[string]int64 // key -> offset of the latest record
}

func Open(path string) (*DB, error) {
	f, err := os.OpenFile(path, os.O_RDWR|os.O_CREATE|os.O_APPEND, 0o644)
	if err != nil {
		return nil, err
	}
	db := &DB{f: f, index: map[string]int64{}}
	return db, db.rebuild()
}

// rebuild scans the whole file to recover the index after a restart.
func (db *DB) rebuild() error {
	r := bufio.NewReader(io.NewSectionReader(db.f, 0, 1<<62))
	var off int64
	for {
		line, err := r.ReadString('\n')
		if err == io.EOF {
			return nil // a partial last line is silently ignored
		}
		if err != nil {
			return err
		}
		key, _, _ := strings.Cut(line, ",")
		db.index[key] = off
		off += int64(len(line))
	}
}

func (db *DB) Set(key, value string) error {
	off, err := db.f.Seek(0, io.SeekEnd)
	if err != nil {
		return err
	}
	if _, err := fmt.Fprintf(db.f, "%s,%s\n", key, value); err != nil {
		return err
	}
	db.index[key] = off
	return nil
}

func (db *DB) Get(key string) (string, bool, error) {
	off, ok := db.index[key]
	if !ok {
		return "", false, nil
	}
	r := bufio.NewReader(io.NewSectionReader(db.f, off, 1<<62))
	line, err := r.ReadString('\n')
	if err != nil {
		return "", false, err
	}
	_, value, _ := strings.Cut(strings.TrimSuffix(line, "\n"), ",")
	return value, true, nil
}

func main() {
	db, err := Open("toy.db")
	if err != nil {
		panic(err)
	}
	db.Set("user:1", "ana")
	db.Set("user:1", "ana maria")

	v, _, _ := db.Get("user:1")
	fmt.Println(v) // ana maria
}

Escrever é um append sequencial, que é mais ou menos a coisa mais barata que dá para pedir a um disco. Ler é um lookup no hash mais uma leitura posicionada. Isso é bem parecido com o Bitcask, o storage engine do Riak, e para alguns workloads é bom de verdade.

Agora tenta usar para qualquer coisa real.

Roda Set("user:1", ...) um milhão de vezes e o arquivo tem um milhão de registros, dos quais um está vivo. Você precisa de algo que reescreva o arquivo sem os registros mortos enquanto as escritas continuam chegando. Isso é compaction, e fazer isso bem com arquivos ordenados é a ideia inteira por trás das LSM Trees.

Pede todas as chaves entre user:100 e user:200. Hash map não tem ordem, então você varre tudo. O índice também precisa caber na RAM, e é reconstruído lendo o arquivo inteiro a cada restart. Uma estrutura ordenada que mora no disco e carrega uma página por vez é o assunto de B-Trees e Pages & Storage Layout.

Puxa o cabo de energia logo depois do Set retornar. O Fprintf retornou quando os bytes chegaram no page cache do sistema operacional, não no disco. A escrita pode ter sumido, ou metade dela pode estar lá, e o rebuild vai pular a linha rasgada sem falar nada. Aí o próximo append gruda nela: depois de um crash no meio da escrita de user:2, o arquivo termina em user:2,toruser:1,ana e o store agora acredita que existe uma chave user:2. Fazer "o commit retornou" significar "está no disco", sem chamar fsync a cada linha, é o trabalho do Write-Ahead Log.

Roda duas goroutines transferindo dinheiro entre account:a e account:b. Nada impede um leitor de ver o débito sem o crédito, e o próprio map nem é seguro para escrita concorrente. Transactions & MVCC mostra como os engines deixam leitores e escritores andarem sem bloquear um ao outro e sem ver uma alteração pela metade.

Depois vêm as perguntas que só existem quando há uma linguagem de query: achar usuários por email quando a chave é um ID (Indexes), decidir entre um índice e um scan completo (Query Planning), e manter uma segunda máquina sincronizada (Replication).

Cada artigo da série resolve um dos buracos acima, e cada solução cobra em outro lugar. B-trees deixam leitura barata e escrita espalhada; LSM trees fazem o contrário. MVCC tira o bloqueio entre leitor e escritor e deixa lixo que alguém precisa limpar com vacuum. A maior parte da série é sobre esses trade-offs.

Como acompanhar

Você precisa de dois engines instalados, os dois de graça:

• PostgreSQL 18, mais fácil via Docker: docker run --rm -e POSTGRES_PASSWORD=pg -p 5432:5432 postgres:18
• SQLite 3, que provavelmente já está na sua máquina como sqlite3

Os dois formam uma boa dupla. PostgreSQL é um engine cliente-servidor com WAL separado, buffer pool e tabelas heap. SQLite é uma única biblioteca C com um único arquivo de banco, então o layout inteiro do arquivo cabe na sua cabeça.

Alguns comandos que vamos usar bastante:

-- PostgreSQL
SHOW block_size;                         -- 8192: the page size
SELECT pg_relation_filepath('users');    -- where the table lives on disk
EXPLAIN (ANALYZE, BUFFERS)
  SELECT * FROM users WHERE id = 42;     -- the plan, plus pages read/hit
CREATE EXTENSION pageinspect;            -- read raw page contents

-- SQLite
PRAGMA page_size;                        -- 4096 by default
EXPLAIN QUERY PLAN
  SELECT * FROM users WHERE id = 42;

EXPLAIN (ANALYZE, BUFFERS) é o que vale a pena se acostumar. Ele mostra quantas páginas uma query tocou e se elas vieram do buffer pool (shared hit) ou precisaram ser lidas (read). Esse número liga quase todo artigo seguinte a algo que você consegue medir.

Quando formos ler código-fonte, esses são bons pontos de partida:

• PostgreSQL: src/include/storage/bufpage.h (layout da página), src/backend/access/nbtree/README (notas de design da B-tree), src/backend/access/transam/README (transações e WAL)
• SQLite: src/btree.c, src/pager.c e src/wal.c, mais o documento do formato de arquivo
• LevelDB: doc/impl.md, uma descrição curta e legível de uma LSM tree

Os READMEs do PostgreSQL valem ouro. São documentos de design longos, em texto puro, escritos por quem escreveu o código, e explicam o raciocínio por trás do código melhor que a maioria dos livros.

O que você já deveria saber

• SQL suficiente para escrever joins e saber o que é uma primary key
• Go suficiente para ler os exemplos
• Árvores e hash tables no nível da Parte 2 e da Parte 3 de Data Structures with Golang

O artigo de B-trees em especial assume que você já viu uma árvore binária de busca e uma árvore balanceada. Ele gasta o tempo explicando por que disco quer uma árvore larga e rasa em vez de alta e fina.

Conclusão

Um banco é uma camada de query em cima de um storage engine, e quase todo comportamento que você nota em produção, seja um update lento, uma tabela inchada ou um plano que virou, vem de um trade-off que uma dessas camadas fez. O store de brinquedo acima tem todos os buracos que um engine de verdade fecha.

O próximo é Pages & Storage Layout: por que tudo é lido em páginas de 8 KB, como uma linha é colocada dentro de uma, e o que o buffer pool faz com elas.