Fundamentos de bancos de dados

Noções básicas do bashdb

• bashdb, o programa de banco de dados mais simples possível, é composto por duas funções bash.
• A função db_set acrescenta dados a um arquivo, e a função db_get busca os dados.
• Os problemas do bashdb incluem durabilidade, atomicidade, isolamento e desempenho.

Tornando o bashdb ACID

• ACID representa as propriedades de transações de banco de dados: atomicidade, consistência, isolamento e durabilidade.
• Para melhorar a durabilidade do bashdb, adiciona-se o comando sync ao db_set.
• Para isolamento, adiciona-se bloqueio de arquivo usando o programa flock.

Durabilidade

• fsync e fdatasync são chamadas de sistema que fazem flush do buffer de escrita para o disco.
• O comando sync faz flush de todas as páginas “sujas” para o disco, e a flag -d chama fdatasync.

Isolamento

• Usa-se flock para fornecer isolamento entre múltiplos processos no bashdb.
• flock é um programa Linux para bloqueio de arquivos, e a flag -s permite leituras simultâneas.

Más notícias

• Não foi encontrada uma forma simples de garantir atomicidade com bashdb.
• Para melhorar o desempenho, é necessário aprimorar o algoritmo O(n).

Mecanismo de armazenamento

• O objetivo de um mecanismo de armazenamento é fornecer uma abstração para ler e escrever dados em armazenamento persistente.
• O projeto de um mecanismo de armazenamento busca minimizar I/O de disco e buscas no disco.

B-tree mutável

• A B-tree é uma variação da BST com localidade espacial, minimizando I/O de disco e buscas.
• A B-tree é uma BST generalizada em que os nós podem ter mais filhos.

LSM tree imutável

• A LSM tree é uma estrutura de dados imutável escrita sequencialmente, vantajosa para workloads intensivos em escrita.
• A LSM tree armazena dados em buffer na memória e, ao atingir certa capacidade, faz flush para uma SSTable ordenada.

Filtro de Bloom

• O filtro de Bloom é uma estrutura de dados probabilística que permite verificar com eficiência se um item não existe em um conjunto.
• O filtro de Bloom funciona usando funções hash e tem complexidade espacial O(log n).

Write Ahead Log

• WAL é um arquivo especial que registra todas as operações de transação e reconstrói o estado quando o processo do banco de dados é iniciado.

Isolamento

• Para alcançar isolamento, pode-se usar bloqueio pessimista, bloqueio otimista ou MVCC.
• O padrão ANSI/ISO SQL 92 define vários níveis de isolamento de leitura.

Sistemas distribuídos

• Sistemas distribuídos adicionam complexidade e podem distribuir dados entre várias máquinas para disponibilidade e escalabilidade horizontal.
• De acordo com o teorema CAP, um sistema só pode garantir duas entre consistência, disponibilidade e tolerância a partições.

Hashing consistente

• Hashing consistente é um método de particionamento de dados que reduz a quantidade de itens migrados quando nós são adicionados ou removidos.

Opinião do GN⁺:

• Entender os problemas fundamentais dos bancos de dados e as propriedades ACID é essencial para a engenharia de bancos de dados.
• O exemplo do bashdb ajuda a compreender problemas que surgem em sistemas reais de banco de dados.
• O projeto de mecanismos de armazenamento e sistemas distribuídos é um fator importante que determina o desempenho e a confiabilidade de um banco de dados.

[GN⁺]

Comentários do Hacker News

• Resumo do primeiro comentário:

  • Uma das características de bancos de dados baseados em LSM é que registros excluídos ou tombstones permanecem por muito tempo.
  • Tombstones devem ser ignorados apenas no nível final, e não em todos os níveis.
  • Caso contrário, um tombstone de um nível superior pode ser removido e um item de um nível inferior pode reaparecer.
  • Bancos de dados como RocksDB tentam resolver esse problema com otimizações.

• Resumo do segundo comentário:

  • Evitar aprender sobre sistemas distribuídos pode ser arriscado.
  • Na prática, todo sistema de produção não trivial é um sistema distribuído.
  • Se o banco de dados é um conjunto de réplicas, então ele é um sistema distribuído.
  • Se quiser aprender sobre sistemas distribuídos, vale conferir jepsen.io e raft.github.io.

• Resumo do terceiro comentário:

  • Existem consistência do banco de dados e consistência da aplicação.
  • É possível atingir ACID (atomicidade, consistência, isolamento e durabilidade) em uma tabela, mas falhar em escritas que envolvem várias tabelas.
  • Ao lidar com transações que atualizam várias tabelas ao mesmo tempo, todas elas devem ser atualizadas simultaneamente ou nenhuma deve ser atualizada.

• Resumo do quarto comentário:

  • O texto oferece uma excelente visão geral de vários conceitos envolvidos na construção de bancos de dados.
  • Ele cobre desde extrair desempenho de uma única máquina com SIMD até algoritmos de consenso.
  • Há menção a métodos formais aplicados à confiabilidade de bancos de dados e a sistemas distribuídos.
  • Existe um artigo interessante sobre como a equipe do Amazon S3 faz modelagem usando TLA+.

• Resumo do quinto comentário:

  • Muitas pessoas aprendem SQL para estudar bancos de dados, mas entender B-trees ajuda a compreender melhor os pontos fortes e fracos de um RDBMS.
  • As pessoas tentam acelerar o banco de dados adicionando índices, mas isso na prática apenas mascara o problema.
  • Alguns problemas se encaixam bem em B-trees, mas muitos não.
  • SQL é apenas uma interface de consulta para um sistema remoto de B-trees.

• Resumo do sexto comentário:

  • Muitos desenvolvedores passam, em algum momento, pela fase de tentar criar seu próprio pequeno banco de dados.
  • Esse processo pode ensinar muito sobre o que não funciona.
  • Criar seu próprio banco de dados ajuda a aumentar o respeito pelas soluções existentes.
  • Transferir dados do disco de forma rápida e confiável é uma tarefa difícil.

• Resumo do sétimo comentário:

  • Em uma versão em Bash, a atomicidade pode ser obtida copiando o arquivo para um arquivo temporário, depois modificando-o e usando sync; mv; sync.

• Resumo do oitavo comentário:

  • É um design muito interessante, com API de documentos semelhante ao MongoDB, replicação sem líder semelhante ao Cassandra e arquitetura de um core por thread semelhante ao ScyllaDB.
  • Tudo isso foi implementado em Rust.

• Resumo do nono comentário:

  • O livro 'Database Internals' é surpreendentemente excelente e oferece uma exploração profunda da parte interna dos bancos de dados.
  • A pessoa pergunta se existem outros livros parecidos.

• Resumo do décimo comentário:

  • O livro 'Database Design and Implementation' também é uma leitura excelente, com muitos exemplos escritos em Java.
  • Para pesquisa de fato, a recomendação é o trabalho de Andy (Pavlo), Viktor Leis, Thorsten Grust e Thomas Neumann.