Fundamentos de bancos de dados

• Começando com um armazenamento simples de chave-valor em Bash, mostra passo a passo por que bancos de dados reais precisam tratar durabilidade, atomicidade, isolamento e desempenho como problemas de projeto separados
• fsync/fdatasync, flock e WAL são ferramentas básicas para proteger dados em cenários de falha e concorrência, mas quanto maior o nível de garantia, maior o custo de desempenho
• Motores de armazenamento usam estruturas como B-tree e LSM tree para reduzir I/O de disco e custos de busca, e cada uma delas traz manutenções como vacuum e compaction
• Bancos de dados distribuídos ganham disponibilidade e escalabilidade horizontal, mas em troca assumem a complexidade de sistemas distribuídos, como teorema CAP, partições de rede, ajuste de consistência e resolução de conflitos
• Ao escolher ou implementar um banco de dados, é preciso ajustar à carga de trabalho as garantias ACID, o nível de isolamento, a estrutura de armazenamento, o método de replicação e os requisitos de consistência

---

Os problemas básicos de bancos de dados revelados pelo bashdb

• bashdb é um armazenamento simples de chave-valor feito com duas funções Bash
  • db_set faz append em um arquivo no formato chave,valor
  • db_get lê o último valor combinando grep, sed e tail
• Embora seja simples para fins de aprendizado, essa implementação por si só já expõe os problemas que um banco de dados de produção precisa resolver
  • Durability: se a máquina travar depois de db_set ter sucesso, dados ainda não flushed para o disco podem se perder
  • Atomicity: se houver falha durante a escrita, os dados podem ser gravados só parcialmente e ficar corrompidos
  • Isolation: se leitura e escrita acessarem o mesmo item ao mesmo tempo, a leitura pode ver apenas parte dos dados
  • Performance: db_get faz busca linha por linha no arquivo inteiro, então é O(n)

ACID e tentativas de melhorar o bashdb

• ACID é uma sigla que reúne propriedades que muitos bancos de dados tentam garantir
  • Atomicity: se ocorrer uma falha durante a escrita, a transação inteira é cancelada ou revertida, sem deixar um estado de escrita parcial
  • Consistency: transações inválidas não devem corromper o banco de dados
  • Isolation: não deve haver race conditions em acessos simultâneos aos mesmos dados
  • Durability: escritas bem-sucedidas devem permanecer mesmo após situações como falta de energia
• Nem toda transação de banco de dados precisa necessariamente garantir ACID; em alguns casos de uso, pode-se reduzir as garantias em troca de desempenho

• Durabilidade e fsync

  • A system call write grava buffers em um arquivo, mas isso não significa que eles foram imediatamente persistidos em armazenamento não volátil
  • O kernel pode armazenar os buffers como dirty pages no page cache e só depois fazer o flush para o disco
  • Dispositivos de disco e sistemas RAID também podem ter seu próprio write cache
  • fsync e fdatasync são system calls para fazer flush de dirty pages para armazenamento permanente
  • fdatasync faz flush do raw buffer passado por write
  • fsync faz flush não só dos dados, mas também de metadados do arquivo, como mtime
  • Adicionar sync -d database após db_set pode aumentar a durabilidade com um comportamento próximo de fdatasync, mas normalmente sync é mais lento que a própria escrita, então o desempenho piora
  • O sucesso de fsync() significa que “todas as writes desde o último fsync chegaram ao disco”, e não apenas “as writes desde o último fsync bem-sucedido”
  • O PostgreSQL enfrentou esse problema em 2018 e mudou seu comportamento para entrar em panic em caso de falha de fsync, em vez de simplesmente tentar novamente
  • O caso ficou conhecido como fsyncgate, com link para o artigo sobre falhas de fsync
  • O MongoDB, por padrão, faz sync das escritas a cada 100ms, então não é 100% durável

• Isolamento e flock

  • No bashdb, a forma mais simples de isolamento entre múltiplos processos é aplicar lock no arquivo de armazenamento antes de ler ou escrever
  • O flock no Linux bloqueia arquivos, e com a flag -s é possível usar shared lock para que vários readers leiam ao mesmo tempo
  • O bashdb melhorado usa exclusive lock para escritas e shared lock para leituras
  • A desvantagem é que, a cada escrita, ele bloqueia o banco de dados inteiro
  • Garantir atomicidade de forma simples só com Bash é difícil; há a possibilidade de usar mv -T ou rename, mas isso não foi concluído
  • O bashdb ainda não resolve o problema de consulta O(n)

O papel do motor de armazenamento e seus gargalos

• O motor de armazenamento fornece uma abstração para ler e gravar dados em armazenamento persistente, e seu objetivo principal é alta vazão e baixa latência
• A maior limitação vem das diferenças de velocidade do próprio disco
  • Na tabela de latências de exemplo, uma referência à L1 cache é cerca de 0.5ns, uma leitura aleatória de 4KB em SSD é 150,000ns, e um disk seek é 10,000,000ns
  • Se uma referência à L1 cache fosse equivalente a um batimento cardíaco de cerca de 0,5 segundo, uma leitura sequencial de 1MB em SSD corresponderia a cerca de 12 dias, e uma leitura sequencial de 1MB em disco a cerca de 8 meses
• Por isso, o projeto de motores de armazenamento evoluiu na direção de reduzir ao máximo o I/O de disco e os disk seeks
• Elementos comuns no projeto de um motor de armazenamento incluem
  • a estrutura de dados básica usada para armazenar itens no disco
  • transações ACID
  • cache para reduzir leituras em disco
  • uma camada de API, como SQL, documento ou grafo
• As estruturas de dados de motores de armazenamento podem ser divididas, em linhas gerais, entre estruturas mutáveis e imutáveis
  • Estruturas mutáveis podem sobrescrever depois os dados já gravados no arquivo
  • Estruturas imutáveis apenas relêem dados já gravados no arquivo

B-tree mutável

• Para manter bom desempenho mesmo com o crescimento dos dados, é preciso encontrar itens em tempo no máximo logarítmico, e não com busca linear como no bashdb
• Uma BST permite consultas em O(log n), mas, se os nós estiverem muito distantes uns dos outros no disco, a navegação pode exigir muitos disk seeks
• A B-tree é uma generalização da BST em que um nó pode ter mais de dois filhos, aproveitando spatial locality
  • Normalmente lê-se uma page de 4KB ou 8KB do disco e depois vários nós dentro dela são comparados sequencialmente na memória e no CPU cache
  • Como acessos à memória e ao CPU cache são várias ordens de grandeza mais rápidos que o disco, é importante aproveitar o máximo possível os bytes lidos do disco
• O acesso sequencial à memória pode ser muito poderoso graças a SIMD, instruction pipelining e prefetching
• A B+ tree armazena valores apenas nos leaf nodes e deixa os demais nós guardarem só chaves, permitindo comparar mais chaves em uma única page de disco

• Recuperação de espaço e vacuum

  • A B-tree precisa recuperar espaço vazio gerado por fragmentação de dados para otimizar o uso de espaço
  • Ao atualizar com um valor maior, isso pode sobrescrever dados do próximo nó, então o item é movido para outro lugar e fica um buraco na page original
  • Ao atualizar com um valor menor, fica um buraco no final
  • Exclusões criam buracos no lugar em que o valor apagado estava
  • Esse processo de recuperar espaço e reescrever pages pode ser chamado de vacuum, compaction, page defragmentation ou maintenance
  • Em geral, isso é feito em background para evitar picos de latência nas requisições dos usuários
  • O PostgreSQL permite configurar o auto vacuum daemon
  • A B-tree é comumente usada como estrutura base de índices, como no índice padrão do PostgreSQL, e o DynamoDB já foi chamado em tom de brincadeira de “distributed B-tree”

LSM tree imutável

• A LSM tree é uma estrutura de dados append-only que surgiu da premissa de que o disk seek é caro
• Se os dados forem adicionados apenas ao fim do arquivo, a cabeça do disco precisa se mover menos até a próxima posição de escrita, o que favorece workloads com muitas gravações
• Log Structured Merge tree, ou simplesmente LSM tree, é usada em mecanismos de armazenamento de bancos de dados modernos como RocksDB, Cassandra e ScyllaDB
• O funcionamento básico é o seguinte
  • As gravações são bufferizadas em uma estrutura de dados ordenável na memória
  • Exemplos são AVL tree, Red Black tree e Skip List
  • Ao atingir uma certa capacidade, os dados são descarregados em um arquivo ordenado chamado Sorted String Table, ou SSTable
• A SSTable armazena dados ordenados, o que permite reduzir I/O de disco com binary search e sparse index
• Para garantir durabilidade, as operações escritas em memória também são registradas no Write-Ahead Log, ou WAL
  • Ao iniciar o programa, o WAL é lido para restaurar o estado anterior ao encerramento ou crash
• Exclusões também são adicionadas por append como uma gravação comum, armazenando um tombstone no lugar do valor
  • O tombstone é removido durante o processo de compaction

• Leitura e compaction na LSM tree

  • A leitura em uma LSM tree primeiro busca na estrutura em memória e, se não encontrar, percorre as SSTables em disco da mais recente para a mais antiga
  • Quanto mais gravações houver, maior será o número de SSTables a verificar
  • Mesmo que cada arquivo esteja ordenado, varrer muitos arquivos pequenos pode ser mais lento do que consultar um único arquivo grande
  • A expressão de comparação é log(num_files * table_size) < num_files * log(table_size)
  • Compaction é uma tarefa em background que combina várias SSTables pequenas em uma SSTable grande e remove tombstones
  • O RocksDB implementa Leveled Compaction
  • As SSTables recém-descarregadas ficam no level 0
  • Quando a quantidade configurada de arquivos se acumula em um level, após a compaction o novo arquivo é promovido ao próximo level
  • A remoção de tombstones exige cuidado
  • Pode surgir o problema de data resurrection, em que itens excluídos reaparecem durante a compaction com arquivos mais antigos
  • O RocksDB mantém os tombstones até a compaction que os promove ao último level
  • Um exemplo real em Rust pode ser visto no código de LSM tree do dbeel

• Bloom filter

  • Bloom filter é uma estrutura de dados probabilística de conjunto que permite verificar com eficiência se um item não está em um conjunto
  • O resultado da consulta tem dois casos
    • false: o item definitivamente não está no conjunto
    • true: o item pode estar no conjunto
  • O Bloom filter mapeia os resultados de várias hash functions para posições de bits em um bitmap e os define como 1
  • A complexidade espacial é apresentada como O(log n), em contraste com o O(n) de um set comum
  • É possível ajustar a “probabilidade de ter certeza de que não está presente” alocando mais memória para o bitmap e aumentando o número de hash functions, e há também uma calculadora
  • A LSM tree armazena um Bloom filter para cada SSTable, permitindo pular a busca em SSTables onde foi confirmado que uma key não existe

WAL e garantias de transação

• WAL é uma forma de registrar todas as operações de transação em um arquivo especial para sobreviver a crashes repentinos
• Quando o processo do banco de dados é iniciado, ele lê o arquivo WAL e reconstrói o estado dos dados
  • Transações sem commit log são ignoradas, obtendo assim atomicidade
• Se os dados de uma solicitação de escrita forem registrados e flushados no WAL antes de responder ao usuário, eles certamente poderão ser lidos na inicialização, garantindo durabilidade
• O WAL pode ser visto como uma forma de event sourcing para eventos de transação

Níveis de isolamento e controle de concorrência

• As formas de alcançar isolamento se dividem em três grandes categorias
  • Lock pessimista: bloqueia o acesso a dados que estão sendo escritos no momento
  • Lock otimista: modifica uma cópia dos dados e só faz commit se o original não tiver mudado durante a transação; caso contrário, faz retry
  • MVCC: em vez de sobrescrever os dados, cria uma nova version para que cada usuário veja um snapshot de um ponto específico no tempo
• Nem toda aplicação precisa de isolamento completo, isto é, serializable isolation
• O ANSI/ISO SQL 92 classifica em três tipos os resultados que podem ocorrer quando outra transação altera os mesmos dados durante uma transação
  • Dirty read: lê uma atualização de outra transação que ainda não foi commitada
  • Non-repeatable read: entre duas leituras da mesma row, outra transação faz commit e o valor muda
  • Phantom read: entre duas leituras de um conjunto de rows com a mesma condição, rows são adicionadas ou removidas
• Os níveis de isolamento ANSI/SQL 92, do mais alto para o mais baixo, são os seguintes
  • Serializable: lê apenas dados commitados e evita phantom read, inclusive em escritas de múltiplas rows baseadas em intervalo
  • Repeatable reads: phantom read é permitido
  • Read committed: non-repeatable read é permitido
  • Read uncommitted: dirty read é permitido
• Níveis de isolamento mais altos normalmente vêm com perda de desempenho
• Os níveis de isolamento ANSI/SQL 92 são criticados por não serem completos
  • Muitas implementações de MVCC fornecem snapshot isolation, e não serializable isolation
  • Como algoritmo rápido de MVCC serializable, recomenda-se o HyPer

Por que sistemas distribuídos são necessários e CAP

• Sistemas distribuídos adicionam muita complexidade, então devem ser evitados quando uma solução não distribuída for suficiente
• Há dois motivos comuns para distribuir dados entre várias máquinas
  • Disponibilidade (Availability): mesmo que a máquina do banco de dados sofra crash ou perca a conexão com o usuário, as requisições podem ser enviadas a outra máquina
  • Escalabilidade horizontal (Horizontal Scaling): em vez de vertical scaling para uma única máquina maior, várias máquinas conectadas em rede operam como se fossem uma só
• Sistemas distribuídos introduzem complexidade operacional e o problema de network partition
• O teorema CAP diz que um sistema só pode garantir duas das três propriedades a seguir
  • Consistency: as leituras recebem a escrita mais recente
  • Availability: toda requisição é bem-sucedida independentemente de falhas
  • Partition Tolerance: o sistema continua funcionando mesmo com perda ou atraso de mensagens entre nós
• Um banco de dados em máquina única não tem network partition e é consistente, mas quando a máquina falha, novas requisições falham, violando availability
• Se duas máquinas com CPU, memória e disco separados estiverem conectadas por cabo, em caso de falha surge uma escolha
  • Cancelar as requisições sacrifica availability e preserva consistency
  • Continuar processando requisições apenas na máquina que segue funcionando sacrifica consistency e preserva availability
• Sistemas que sacrificam consistency e se ajustam depois são chamados de eventually consistent
• Como é preciso reunir dados espalhados pelo cluster, network partitions também dificultam JOIN eficiente, e o ecossistema NoSQL recomenda denormalization para aliviar isso

Replicação e o caso do Amazon Dynamo

• O artigo original do Dynamo, da Amazon, é apresentado como um caso em que a disponibilidade era considerada mais importante do que a consistência no carrinho de compras da amazon.com
  • Se o usuário vir dois itens iguais no carrinho, basta remover um deles
  • A avaliação foi de que isso é melhor do que uma situação em que a compra em si se torna impossível
• Para obter disponibilidade, não basta apenas vários nós dividirem os dados; cada item precisa ter pelo menos uma cópia adicional
• Os nós que armazenam cópias de um item são replicas, e o processo de cópia é a replication
• Aumentar o número de replicas eleva a disponibilidade, mas exige mais recursos para armazenar as cópias
• As cópias dos dados também podem não ser armazenadas integralmente, mas divididas com erasure coding e distribuídas entre vários nós; as características de latência relacionadas estão no artigo sobre erasure coding

Consistent Hashing e posicionamento de dados

• Quando há vários nós, é necessário um método de balanceamento de carga ou particionamento de dados para decidir qual nó processará uma requisição de armazenamento
• Um método simples é aplicar hash à primary key e então usar modulo pelo número de nós
  • Quando um nó é adicionado ou removido, len(nodes) muda e a mesma key passa a apontar para outro nó
  • Nesse caso, é preciso migrar quase todos os itens, o que tem alto custo
• Consistent Hashing posiciona os nós em um ring, em vez de um array, para reduzir a quantidade de itens que precisam ser movidos quando nós são adicionados ou removidos
  • É usado em bancos de dados como Dynamo e Cassandra
• No consistent hashing, o hash do nome do nó é posicionado no ring, e o nó encontrado após o hash da key da requisição se torna o proprietário
• A seleção de replicas pode ser feita percorrendo o ring no sentido anti-horário e armazenando cópias nos nós seguintes
  • Se o nó proprietário cair, um nó replica processa a requisição para manter a disponibilidade
  • Esse método é chamado de Leaderless Replication e é usado em bancos de dados no estilo Dynamo, como o Cassandra
• Ao adicionar um nó, o número de keys que precisam ser movidas é, em média, num_keys / num_nodes
• Virtual node significa posicionar o mesmo nó físico várias vezes no ring para reduzir a chance de alguns nós ficarem com muito mais itens do que outros
  • Um exemplo é adicionar um índice como sufixo ao nome do nó, como em "half-0" e "half-1"
• Há outras formas de escolher leader node e replica node, como leader election, mas isso não será tratado aqui

Leaderless Replication e ajuste de consistência

• Uma configuração leaderless obtém alta disponibilidade em troca de sacrificar consistência
• Se o nó proprietário estiver down no momento de uma requisição de write, a escrita vai para as replicas, e depois que o nó proprietário voltar, uma requisição de read pode ler dados antigos
• Se uma determinada requisição precisar de consistência, a requisição de read pode ser enviada em paralelo para várias replicas e para o nó proprietário, e o cliente escolhe os dados mais recentes
• Requisições de write normalmente são enviadas em paralelo para todas as replicas, mas espera-se apenas o acknowledgement de parte dos nós
• Para ajustar a consistência no nível da requisição, verifica-se R + W > N/2 + 1
  • N: número de nós que têm cópias dos dados
  • W: número de nós que precisam dar acknowledgement para o write ter sucesso
  • R: número de nós que precisam responder para o read ter sucesso
• Quando W ou R é N/2 + 1, isso é chamado de quorum, ou maioria de nós

• Resolução de conflitos

  • O processo de escolher o write mais recente é a Conflict Resolution
  • Comparar apenas timestamps não é algo confiável em sistemas distribuídos
  • Cada máquina tem seu próprio hardware clock, e o clock não é perfeitamente preciso, então ocorre drift
  • O NTP recebe a hora de uma fonte mais precisa, mas como a própria requisição passa pela rede, não é possível saber com exatidão o tempo até a resposta
  • O Cassandra usa timestamp, e a documentação relacionada está em Cassandra data versioning
  • O Google Spanner alcançou garantias de consistência baseadas em clock com hardware especial de tempo de alta precisão e uma API que expõe uma faixa de incerteza do timestamp; o artigo relacionado é o Spanner paper
  • Sistemas como o Dynamo reduzem parte dos conflitos com Version Vectors
  • Cada version de um item recebe um par (node, counter) para identificar relações causais entre versions
  • É possível identificar a version que certamente é mais recente e remover alguns valores antigos
  • Como material mais detalhado, há Dotted Version Vectors
  • Também é possível, como no Riak KV, retornar todos os valores em conflito para a aplicação, para que ela resolva com base no conhecimento que tem sobre os dados
  • Em sistemas eventualmente consistentes, várias técnicas para reduzir conflitos normalmente são agrupadas sob o termo Anti Entropy

Técnicas de Anti Entropy

• Read Repair

  • Depois que o cliente escolhe o valor mais recente entre os resultados de read de vários nós, ele o envia novamente aos nós que ainda não o armazenam para fazer o repair

• Hinted Handoff

  • Se uma requisição de write não conseguir chegar ao nó de destino, ela é armazenada como hint em outro nó
  • Quando o nó de destino volta a ficar available, o hint armazenado é entregue
  • Em quorum write, esse método também é chamado de Sloppy Quorum e aumenta ainda mais a disponibilidade de requisições com quorum

• Merkle Trees

  • O read repair corrige apenas os dados consultados, então uma grande quantidade de dados pode permanecer inconsistente por muito tempo
  • Fazer nós se sincronizarem para encontrar toda a diferença é caro, com custo O(n), quando há muitos dados
  • A Merkle tree é uma estrutura hierárquica em que os hashes de faixas de dados ficam nas folhas, e cada pai armazena um hash combinado dos hashes dos filhos
  • Se o hash da raiz for igual, os dados dos dois nós são iguais; se for diferente, compara-se recursivamente os hashes inferiores para encontrar os dados divergentes, tornando a sincronização mais rápida, em O(log n)

• Gossip Dissemination

  • É uma forma simples e confiável de propagar eventos por todo o cluster
  • Um nó envia uma mensagem para uma quantidade configurada de nós aleatórios, ou seja, o fanout, e os nós que a recebem a reenviam para N nós aleatórios
  • Quando um mesmo gossip message é visto o número configurado de vezes, ele deixa de ser broadcast
  • Há um simulator para perceber a convergência dos dados
  • Gossip messages normalmente são transmitidas via UDP

Áreas que podem ser exploradas mais a fundo

• Há muitos outros tópicos em bancos de dados além do que foi tratado aqui
  • uso de O_DIRECT no Linux e implementação de page cache própria
  • failure detection em sistemas distribuídos
  • algoritmos de consensus como Raft
  • distributed transaction
  • leader election
• Ao escolher ou implementar um banco de dados, é preciso analisar junto como storage engine, ACID, níveis de isolamento, replicação distribuída e formas de resolução de conflitos se alinham aos requisitos reais

[GN⁺]

Comentários do Hacker News

• Há um bug no método compact: os tombstones só devem ser ignorados ao compactar o nível final, ou seja, o maior nível, e não removidos entre todos os níveis
  Caso contrário, os tombstones dos níveis superiores desaparecem durante a compactação, fazendo com que entradas que estavam em níveis inferiores voltem a aparecer
  Em bancos de dados baseados em LSM, é uma característica que registros de exclusão/tombstones permaneçam por muito tempo, e alguns bancos de dados, como o RocksDB, incluem otimizações para tentar evitar isso

  • Sim, no texto isso foi omitido de propósito para mantê-lo conciso, e no dbeel isso está sendo tratado
  • Fiquei curioso sobre quais otimizações o RocksDB faz
    Conheço os recursos de exclusão por intervalo, mas não me lembro de ter lido muito sobre exclusão de chave única

• Muita gente aprende bancos de dados estudando SQL, mas eu recomendaria aprender assistindo a aulas assim e entendendo árvores B
  A maior parte dos prós e contras de um SGBD relacional fica clara quando se entende a árvore B e como ela afeta inserção de chaves, consultas e ordenação
  Muita gente tenta acelerar o banco adicionando índices, mas no fim isso é só colocar outra árvore em cima da árvore, o que acaba escondendo o problema fundamental
  Alguns problemas se encaixam bem em árvores B, mas muitos não
  SQL é apenas uma interface de consulta para um sistema remoto de árvore B

  • Isso é reducionista demais
    Árvores B não são a única estratégia de indexação, e também é bem conhecido que índices são um mecanismo para melhorar desempenho de leitura em troca de sacrificar desempenho de escrita
    Em geral, bancos de dados lidam com muito mais leituras do que escritas
    Fico curioso sobre qual é exatamente o problema que “colocar outra árvore em cima da árvore” estaria escondendo, e como isso seria resolvido sem mexer nos índices
    Para tabelas de tamanho razoável, índices são praticamente essenciais
  • Concordo com isso
    É preciso aprender sobre árvores B e índices hash, a camada de E/S, o modelo de processos e coisas do tipo
    Hoje em dia também vale a pena aprender as estratégias gerais dos bancos de dados colunares: materialização tardia de tuplas, execução preguiçosa, varredura linear e busca binária, pipeline de instruções e afins
    Quando se ganha familiaridade com essas coisas, percebe-se que, no mundo real, às vezes um arquivo plano simples ou um banco embarcado como RocksDB já é suficiente, em vez de um SGBD completo
  • Pode ser uma árvore B, uma árvore LSM, uma trie, ou outra estrutura de índice adequada ao caso
    E, claro, também pode haver índices de cobertura
  • Seria bom explicar a parte de “colocar outra árvore em cima da árvore esconde o problema” com um exemplo concreto

• Quero fazer o contraponto ao conselho de “evite sistemas distribuídos se uma solução não distribuída for suficiente”
  Todo sistema de produção minimamente não trivial é um sistema distribuído
  No mínimo, se o banco de dados for um conjunto replicado, ele já é um sistema distribuído, então não aprender sistemas distribuídos é assumir um risco
  Vale a pena ver https://jepsen.io/ e https://raft.github.io/

  • Algumas partes do sistema podem não conseguir evitar chamadas de rede ou aspectos distribuídos
    Isso não significa que seja aceitável introduzir isso em todo lugar, porque isso aumenta muito a complexidade além do necessário
  • Primeiro é preciso definir o que é um “sistema de produção não trivial”
    Dizer isso dessa forma não rebate o conselho de evitar complexidade desnecessária. A questão central não é se algo é distribuído no sentido técnico, mas se isso é realmente necessário
    Aprender sistemas distribuídos e usá-los são coisas diferentes
    O importante é ter a disciplina de, mesmo depois de aprender, aplicá-los só onde fizer sentido
    Hoje em dia, muitas vezes se gasta um enorme esforço para migrar sistemas simples e que funcionam bem para modelos distribuídos mais fortes, como se isso tivesse custo quase zero
    Mas, olhando o problema e a escala que se queria resolver, fica claro que um único Postgres e um monólito já bastariam
    Parece que o conselho do texto original aponta justamente nessa direção
  • Isso pode até ser verdade dentro da bolha do HN, mas do ponto de vista da empresa média não é nem de longe assim
    Ou pelo menos não precisa ser
  • Sistemas distribuídos/redundantes não são backup
    Eu ainda aconselharia escolher a solução simples
    Mesmo em “armazenamentos triviais e simples”, muitos sistemas ainda falham em armazenar, fazer backup e restaurar corretamente o estado persistente
    Tentar restaurar o estado de um armazenamento distribuído numa situação de recuperação de desastre é ainda mais difícil
    Dá para adotar uma solução distribuída depois de primeiro ter uma solução de backup que funcione
  • É difícil chamar failover de réplica de sistema distribuído
    Uma configuração com master e réplicas somente de leitura também não é o que as pessoas normalmente querem dizer com “distribuído”, porque a escrita não é distribuída
    Na prática, distribuído geralmente significa que os dados são shardados, e essa é justamente a parte que se quer evitar a todo custo se não houver necessidade real

• Foi uma leitura divertida por fazer um bom panorama de vários conceitos envolvidos na criação de bancos de dados
  Vai de SIMD, para extrair desempenho de uma única máquina, até algoritmos de consenso
  Já que estamos falando de bancos de dados, confiabilidade e sistemas distribuídos, também vale ler sobre métodos formais que podem ser aplicados a esse tipo de situação e à implementação interna de bancos de dados
  Há um artigo interessante sobre a equipe do S3 modelando com TLA+
  [0] Use of Formal Methods at Amazon Web Services
  https://lamport.azurewebsites.net/tla/formal-methods-amazon....
  [1] How Amazon Web Services uses formal methods
  https://www.amazon.science/publications/how-amazon-web-servi...

• Há consistência de banco de dados e consistência de aplicação
  Por exemplo, é possível alcançar atomicidade, isolamento e durabilidade no nível de uma tabela, mas falhar em escritas que atravessam várias tabelas
  A consistência passa a importar quando se começa a lidar com transações que atualizam várias tabelas ao mesmo tempo
  Todas as tabelas precisam ser atualizadas ao mesmo tempo, ou então nenhuma deve ser atualizada

  • Bom exemplo, vou refletir isso no texto

• Uma arquitetura com “API de documentos como a do MongoDB, replicação leaderless como a do Cassandra e arquitetura de uma thread por núcleo como a do ScyllaDB” é muito legal
  E, além disso, tudo foi feito em Rust

• A etapa de “os livros despertaram minha curiosidade, então eu mesmo criei um pequeno banco de dados” parece ser algo por que muitos desenvolvedores passam pelo menos uma vez
  Eu não tentaria impedir isso. Quando você faz por conta própria, aprende muito sobre o que não funciona
  Se puder dedicar tempo a isso, é uma lição extremamente valiosa
  Ter criado um banco de dados por conta própria foi o que mais aumentou meu respeito pelas soluções existentes
  A parte difícil não é escrever e ler bytes no disco rapidamente
  O realmente difícil é fazer com que funcione de forma estável por anos, dando suporte a casos de uso que você nunca imaginou

  • Às vezes me pergunto quanto da complexidade dos DBMS modernos vem de restrições causadas por casos de uso de domínios de negócio específicos
    Que eficiência seria possível obter se projetássemos um DBMS especializado em domínio partindo do pressuposto de que casos de uso fora do domínio podem ser proibidos e ignorados?
    Por exemplo, hoje usamos bancos de dados de propósito geral até para conjuntos de dados que são essencialmente append-only
    E se houvesse um banco de dados sem qualquer conceito de atualização ou exclusão de linhas existentes, com apenas inserções e exclusão da tabela/conjunto de dados inteiro?
    Um banco desses não precisaria implementar transações MVCC? Cada tabela poderia ser em si o write-ahead log, evitando um write-ahead log separado? Daria para armazenar de forma mais eficiente? A indexação poderia ter atomicidade por chunk em vez de atomicidade no nível da tabela inteira, reduzindo bloqueios?

• A versão de atomicidade em Bash não poderia ser “simplesmente” alcançada copiando o arquivo para um arquivo temporário, modificando-o e depois usando sync; mv; sync?

  • Durante a cópia, também daria para evitar duplicatas com um filtro grep reverso
    Já que estaria copiando mesmo, talvez desse para garantir ordenação também, mas fazer isso só com “bash” e utilitários básicos não parece muito fazer sentido
    Para esse tipo de uso existe o CDB do DJB, isto é, cdbget, cdbmake etc.:
    https://cr.yp.to/cdb.html
  • Sim, vou acrescentar isso depois

• Ótimo texto
  O livro Database Internals parece muito bom; existem mais livros parecidos que mergulhem fundo na implementação interna?

  • Não é um livro, mas recomendo as aulas de banco de dados publicadas pelo grupo do @apavlo na CMU
    https://www.youtube.com/c/cmudatabasegroup
    Há cursos introdutórios e avançados online, além de apresentações e aulas sobre produtos da indústria
    É muito útil
    Como material com uma perspectiva mais teórica de ciência da computação de nível mais alto, e menos focado em implementação física, o livro “Alice”, isto é, “Foundations of Databases”, é excelente
    É muito denso e matemático, mas cobre álgebra relacional e Datalog, além da conversão de Datalog para álgebra relacional
    A edição impressa está difícil de encontrar hoje em dia, e o exemplar usado que comprei chegou com a encadernação destruída e páginas se soltando, mas o livro inteiro está online: http://webdam.inria.fr/Alice/
  • Também há este material conhecido com foco em Postgres: https://www.interdb.jp/pg/
  • Como visão geral em linha parecida, este artigo é bom:
    https://dsf.berkeley.edu/papers/fntdb07-architecture.pdf
  • O livro Database Management Systems, de Raghu Ramakrishnan, também foi muito útil
    Só que o Database Internals é mais moderno

• Gosto que o texto não mistifique “banco de dados” e comece mostrando uma implementação trivial com um one-liner em Bash
  É uma ótima introdução