Introdução

2 anos atrás eu tinha feito um conteúdo aqui no TabNews sobre um banco de dados que tinha feito em Rust: Como criei o meu próprio banco de dados, o Rustbase.
Rust, a linguagem dos sonhos. De uns tempos pra cá muita coisa mudou. O banco de dados era muito instável. Não tinha durabilidade dos dados; os indices eram todos carregados na memória RAM, ou seja, se o tamanho do indice for maior que que sua RAM, já era, crash na hora; e não tinha controle de concorrência (eu fiz wrap em tudo com o Mutex).

Eu acho que estava no vale da curva de aprendizado, achava que aquilo era o mais correto, mas por algum motivo não me dei ao luxo de parar a estudar, e percebi que TUDO estava errado. Simplemente me afundei no assunto, li papers, vi videos no YT, vi source codes de vários bancos de dados (PostgreSQL, MySQL, WiredTiger ou o MongoDB...). Eu estudei bastante sobre o assunto e não sei nem metade de como funciona o Postgres por baixo dos panos.

O que aconteceu com o Rustbase?

O repositório do Rustbase pode parecer parado, mas estou trabalhando no DustData, no core do negócio. Implementei várias coisas lá: Slotted pages, BTree (incompleta) e Transactions (ainda estou aprendendo como funciona). Cada módulo de um banco de dados é bem denso, por isso demora pra implementar cada um.

Já que banco de dados é um assunto de gosto bastante, gostaria de compartilhar como um banco de dados funciona conforme eu aprendo sobre o assunto aqui, todas as informações mastigadinhas e claro, mostrar como eu fiz na prática.

Aproveitando o gancho, vou explicar pra vocês a parte mais importante de um banco de dados:

Slotted pages

Slotted pages é o átomo de um banco de dados, TUDO é feito em páginas. Vou mostrar o layout primeiramente pra ficar mais fácil de visualizar:

Slotted page layout
             CELL_POINTER_SIZE
                    |                           +-> header.lower
 PAGE_HEADER_SIZE   |                           |
 |--------|------------------|                  V                    
 +--------+-------------------+-----------------+-----------------+ -+
 | header |  cell pointer 01  | cell pointer 02 | --->            |  |
 +--------+-------------------+-----------------+                 |  |
 |                        (Free space)                            |  +- PAGE_SIZE (4096 bytes)
 |          +-----------------+-----------------+-----------------+  |
 |     <--- | cell data 02    | cell data 01    |  special space  |  |
 +----------+-----------------+-----------------+-----------------+ -+
            ^
            |
            +-> header.upper

Isso é uma página, pode parecer um monstro mas é mais simples que imagina. Imagine que uma página basicamente é um array, só que no disco. Cada página normalmente tem 4096 bytes fixo. Os primeiros bytes é para o header. O header contém algumas infomações sobre a página, tipo o lower e o upper, checksum, etc. O cell pointer é uma série de bytes (no caso do DustData tem 6 bytes de tamanho fixo) que diz a localização do dado, ou seja, o cell pointer a ponta a localização do cell data. O free space é um espaço vazio, no caso do DustData são bytes nulos (0x00). O cell data é o dado em si, com alguns metadados para ver se, por exemplo, o dados foi excluido. O special space é um espaço reservado.

Se vermos o binário de uma página vamo ser isso:

(Esse primeiros binários DUSTDATA PAGE são os magic bytes, apenas pra identificar se realmente é uma página. Nesse caso, não há o special space)

Você pode ver como implementei as páginas aqui: Especificações dos bytes e Implementação da página.

Mas porque as página precisam ter um tamanho fixo? E por que tem que ser 4096 bytes?

Bem, um banco de dados não só são apenas uma página, mas sim centenas, talvez centenas de milhares ou talvez milhões dependendo do tamanho da sua tabela. Fazer sequencial scan em cada página pra ver em qual endereço do arquivo ela acaba é inviável. Então fazer ela ser um tamanho fixo basta usar matemática pra saber o endereço das páginas. Por exemplo: Quero pegar a página 5. Se não fosse tamanho fixo eu teria que ir byte a byte pra ver se a página chegou ao fim, pra depois ir pra proxima página até chegar na quinta. Se fosse fixa basta fazer:

P = i * Pt

aonde P é o endereço da página, i é o indice (nesse caso é 5) e Pt é o tamanho constante da página:

P = 5 * 4096
P = 20480

Pronto! 20480 é o endereço da página 5. Fazendo isso mata outra charada: por que tem que ser 4096 bytes? O seu disco não é como a sua memória RAM, você não consegue ler apenas 1 byte no seu disco (tem como mas o seu SO camufla isso), o seu disco é lido em blocos, e você pode tirar vantagem disso lendo em blocos também, assim você não perde tempo e bytes atoa.

Ok, mas e se meu dado for maior que 4096 bytes?

Agora ta ficando mais interessante: Há algo chamado overflow e pager que cuida justamente disso. Basicamente ele cria uma outra página só pra adicionar os dados que você quer. Simples!

Beleza, mas porque diabos eu usaria slotted pages?

No PostgreSQL por exemplo, indices e tabelas são feitas em páginas, justamente porque é confiável, além de tirar aproveito do comportamento de um array, você pode por exemplo usar Binary Search em uma página, aumentando drasticamente a performance do seu DB.

Conclusão

Em resumo slotted pages é isso, se tiver alguma dúvida não hesite em perguntar!

Obrigado por ler até aqui, com certeza vou publicar mais sobre o meu banco de dados.

Links

GitHub do DustData
GitHub do Rustbase

Referências

Bufpages PostgreSQL
Slotted Pages - A disk based page layout