Construindo um banco de dados inspirado no SQLite em Rust - Parte 1

Introdução

Sempre me intrigou o funcionamento interno dos bancos de dados. Como desenvolvedor, uso SQLite, MySQL e PostgreSQL diariamente, mas sempre tive aquela coceira de curiosidade: “Como isso realmente funciona por dentro?”. Depois de anos tratando bancos de dados como caixas pretas, decidi que era hora de abrir uma e ver suas engrenagens.

Foi com esse espírito de exploração que iniciei o projeto FerrousDB (sim, o nome é um trocadilho com “ferrugem” em inglês - não me julguem!). A ideia era não apenas replicar o SQLite, mas realmente entender cada decisão de design, cada estrutura de dados, cada algoritmo.

“O que não posso criar, não entendo.” – Richard Feynman

Objetivos do Projeto

Este projeto nasceu da minha curiosidade pessoal. Queria respostas para perguntas que me perseguiam há anos:

• Como os dados realmente transitam entre memória e disco?
• Por que aquela limitação de uma única chave primária por tabela?
• O que acontece nos bastidores quando faço um rollback?
• Como os índices conseguem ser tão rápidos?
• O que torna um full table scan tão custoso?

Passos Iniciais

Quando comecei este projeto, percebi que precisava dividir o elefante em pedaços menores. Aqui está como estruturei os primeiros passos:

1. Configuração do Ambiente: Criação do projeto Rust e estrutura básica.
2. Implementação de um REPL (Read-Eval-Print Loop): Uma interface de linha de comando simples para interagir com o banco.
3. Parsing de Comandos SQL e Metacomandos: Diferenciar e interpretar comandos para futura execução.

1. Configuração do Ambiente

Criamos um novo projeto Rust utilizando o cargo:

cargo new ferrous_db --bin
cd ferrous_db

Estrutura inicial básica do banco de dados:

#[derive(Serialize, Deserialize, Clone, PartialEq)]
/// Represents the FerrousDB database.
pub struct FerrousDB {
    pub tables: HashMap<String, Table>,
    pub indexs: HashMap<String, BPTree>,
    is_loaded: bool,
}

impl FerrousDB {
    pub fn create_table(
        &mut self,
        name: &str,
        columns: Vec<ColumnSchema>,
    ) -> Result<(), FerrousDBError> {
        if self.tables.contains_key(name) {
            return Err(FerrousDBError::TableExists(name.to_string()));
        }

        let table = Table {
            name: name.to_string(),
            schema: columns,
            rows: Vec::new(),
        };
        self.tables.insert(name.to_string(), table);
        self.save_to_file("data.ferrous")
            .expect("Falha ao salvar no arquivo");
        Ok(())
    }

    ///...
}

• Utilizamos a crate serde para serialização e desserialização de dados.
• Utilizamos a estrutura Table para representar uma tabela no banco de dados (para ver a implementação completa, consulte o código em src/core/table.rs)
• Utilizamos a estrutura BPTree para representar um índice B+ (para ver a implementação completa, consulte o código em src/core/bptree.rs).
  • Índices são estruturas de dados que melhoram a velocidade das operações de recuperação de dados em uma tabela. O B+ Tree é uma das estruturas mais comuns utilizadas para esse fim, devido à sua eficiência em operações de busca, inserção e remoção.

2. Implementação do REPL

Para interagir com o banco de dados, implementamos um REPL simples.

/// src/bin/repl.rs
use std::io::{self, Write};

use ferrous_db::FerrousDB;

/// Starts a Read-Eval-Print Loop (REPL) for interacting with FerrousDB.
pub fn repl() {
    let mut db = FerrousDB::new();
    loop {
        print!("sql> ");
        io::stdout().flush().unwrap();

        let mut input = String::new();
        io::stdin().read_line(&mut input).unwrap();
        let input = input.trim();

        if input.eq_ignore_ascii_case("exit") {
            break;
        }

        match db.execute_sql(input) {
            Ok(result) => {
                println!("{}", result);
            }
            Err(err) => {
                println!("Error parsing SQL: {:?}", err);
            }
        }
    }
}

fn main() {
    repl();
}

3. Parsing de Comandos SQL e Metacomandos

Utilizamos a crate sqlparser para interpretar os comandos SQL.

use sqlparser::ast::{Statement, Expr, Offset};
use sqlparser::dialect::GenericDialect;
use sqlparser::parser::Parser;
use crate::core::error_handling::FerrousDBError;
use crate::core::parser::command::SQLCommand;

pub fn parse_sql(sql: &str) -> Result<SQLCommand, FerrousDBError> {
    let dialect = GenericDialect {};
    let ast = Parser::parse_sql(&dialect, sql).map_err(|e| FerrousDBError::ParseError(e.to_string()))?;

    if ast.len() != 1 {
        return Err(FerrousDBError::ParseError("Apenas uma instrução SQL é suportada".to_string()));
    }

    match &ast[0] {
        Statement::CreateTable(create_table) => {
            // veja o código completo no github
        }
        Statement::Insert(insert) => {
            // veja o código completo no github
        }
        Statement::Query(query) => {
            // veja o código completo no github
        }
        _ => Err(FerrousDBError::ParseError(
            "Unsupported SQL command".to_string(),
        )),
    }
}

Estrutura do Projeto

O código está organizado da seguinte forma:

• src/core/db.rs: Implementa as operações principais do banco de dados, como criação de tabelas e inserção de dados.
• src/core/parser/: Contém os módulos para parsing de comandos.
• src/core/table.rs: Define a estrutura da tabela e operações relacionadas.
• src/core/row.rs: Representa uma linha no banco de dados.
• src/core/bptree.rs: Implementação inicial de uma árvore B+ para índices.

Referências

• What would SQLite look like if written in Rust? por João Henrique Machado Silva.
• Building a Database From Scratch in Rust por Paolo Rechia.
• Database of databases: Explore diferentes bancos de dados e seus recursos.
• Introduction to SQLite: Uma introdução ao SQLite.

Esses artigos fornecem insights valiosos sobre a construção de bancos de dados e são ótimas leituras complementares.

O Caminho à Frente

Nos próximos artigos, abordaremos:

• Implementação Completa do Parser SQL: Suporte a mais comandos e cláusulas.
• Gerenciamento de Armazenamento: Persistência em disco e serialização de dados.
• Implementação de Índices com Árvore B+: Melhorar a performance nas consultas.
• Transações e Controle de Concorrência: Garantir a integridade dos dados.
• Otimizador de Consultas: Estratégias para otimizar a execução de queries.

Conclusão

Este projeto é uma excelente oportunidade para mergulhar nos detalhes de como um banco de dados funciona. Utilizando Rust, ganhamos não apenas performance, mas também segurança ao lidar com memória e threads. Acompanhe os próximos artigos para continuar explorando o desenvolvimento do FerrousDB!

---

Você pode encontrar o código completo no nosso repositório do GitHub. Pull requests são bem-vindos!