Mengimplementasikan Storage Engine Persisten untuk Database Terdistribusi

Bagian ini membawa Kita membangun komponen utama pertama: lapisan penyimpanan yang sederhana dan persisten (tahan lama).

Mengimplementasikan Storage Engine Persisten untuk Database Terdistribusi.

Secara sederhana, trait di Rust adalah cara untuk mendefinisikan perilaku atau fungsionalitas bersama yang bisa dimiliki oleh berbagai tipe data (struct atau enum). Anggap saja trait sebagai sebuah “kontrak” atau “antarmuka” (interface di bahasa lain) yang menjamin bahwa tipe data apa pun yang mengimplementasikannya akan memiliki metode-metode tertentu.

Mendefinisikan Trait Engine

Sebelum menulis kode penyimpanan spesifik, kita akan mendefinisikan sebuah “kontrak” atau antarmuka. Di Rust, konsep ini diimplementasikan menggunakan trait.

Apa itu Trait? Secara sederhana, trait di Rust adalah cara untuk mendefinisikan fungsionalitas bersama. Anggap saja trait sebagai deskripsi pekerjaan: ia mendefinisikan kemampuan apa yang harus dimiliki oleh sesuatu, tanpa merinci bagaimana cara melakukannya.

Misalnya, trait BisaTerbang mungkin mendefinisikan metode terbang(), dan struct Pesawat maupun Burung bisa mengimplementasikan trait ini dengan cara mereka masing-masing.

Mengikuti desain pluggable dari toydb, kita akan mulai dengan mendefinisikan sebuah trait Engine1 generik. Ini adalah kontrak yang menguraikan operasi inti yang harus disediakan oleh storage engine mana pun. Dengan mendefinisikan antarmuka ini terlebih dahulu, kita dapat menukar implementasi yang berbeda di masa depan (misalnya, dari penyimpanan dalam memori ke penyimpanan berbasis disk) tanpa mengubah sisa kode database.

use anyhow::Result;
use std::ops::RangeBounds;

// Di toydb, trait ini berada di src/storage/engine.rs
pub trait Engine {
    // Menetapkan nilai untuk sebuah kunci.
    fn set(&mut self, key: &[u8], value: Vec<u8>) -> Result<()>;
    // Mendapatkan nilai untuk sebuah kunci.
    fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>>;
    // Menghapus sebuah kunci.
    fn delete(&mut self, key: &[u8]) -> Result<()>;
    // Memindai rentang kunci.
    fn scan(&self, range: impl RangeBounds<Vec<u8>>) -> Result<impl Iterator<Item = Result<(Vec<u8>, Vec<u8>)>>>;
    // Memastikan semua tulisan disimpan secara permanen.
    fn flush(&mut self) -> Result<()>;
}

Catatan: Signature metode di atas disederhanakan untuk kejelasan, tetapi menangkap esensi dari trait Engine di toydb.

Membangun Engine Berstruktur Log

Engine berstruktur log ini diambil dari frase Log-Structured Engine.
Log-Structured: Ini adalah istilah teknis yang merujuk pada arsitektur penyimpanan di mana semua perubahan data (penambahan, pembaruan, penghapusan) ditulis secara berurutan ke akhir sebuah file log (append-only). Ini berbeda dengan sistem yang memodifikasi data di tempatnya (in-place update).

Kita akan mengimplementasikan engine yang terinspirasi dari BitCask, yang sederhana namun kuat. Ini adalah pendekatan yang sama yang diambil oleh toydb dalam file src/storage/bitcask.rs. struct BitCask² kita akan mengimplementasikan trait Engine yang telah kita definisikan.

1. Struktur Data:

   use std::collections::HashMap;
   use std::fs::{File, OpenOptions};
   use std::path::PathBuf;
   
   pub struct BitCask {
       path: PathBuf,
       index: HashMap<Vec<u8>, u64>, // Peta dari kunci ke offset file
       log_file: File,
       current_offset: u64,
   }
   

2. Implementasi Trait:

   impl Engine for BitCask {
       fn set(&mut self, key: &[u8], value: Vec<u8>) -> Result<()> {
           // 1. Buat LogEntry dan serialisasikan.
           // 2. Tambahkan ke akhir log_file.
           // 3. Perbarui index dalam memori dengan offset baru.
           // 4. Perbarui current_offset.
           //... implementasi...
       }
   
       fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>> {
           // 1. Cari kunci di index dalam memori.
           // 2. Jika ditemukan, dapatkan offset.
           // 3. Gunakan File::seek untuk pindah ke offset di log_file.
           // 4. Baca dan deserialisasi LogEntry untuk mendapatkan nilai.
           //... implementasi...
       }
   
       fn delete(&mut self, key: &[u8]) -> Result<()> {
           // Implementasi delete di BitCask biasanya adalah dengan menulis
           // sebuah entri khusus (tombstone) ke log.
           //... implementasi...
       }
   
       fn flush(&mut self) -> Result<()> {
           // Panggil sync_all() untuk memastikan semua tulisan di-buffer
           // oleh sistem operasi telah ditulis ke disk.
           self.log_file.sync_all()?;
           Ok(())
       }
   
       //... implementasi untuk scan...
   }

3. Startup dan Pemulihan:

   • Ketika BitCask dibuat (misalnya, melalui BitCask::new()), ia perlu membangun kembali index dalam memori.

   • Ini dilakukan dengan membaca seluruh log_file dari awal hingga akhir.

   • Untuk setiap LogEntry yang dibaca, perbarui index dengan offset entri tersebut. Jika sebuah kunci muncul beberapa kali, hanya offset terakhir (yang terbaru) yang disimpan. Ini secara alami menangani pembaruan dan penghapusan (jika tombstone digunakan).

Implementasi ini, meskipun sederhana, menangkap esensi dari sistem penyimpanan berstruktur log: penulisan berurutan yang cepat dan indeks dalam memori untuk pembacaan yang cepat.

Melanjutkan pembahasan tentang pluggable storage engine dari toydb, dalam kode sumbernya juga ada contoh implementasi in-memory key value storage engine menggunakan standar pustaka Rust B-tree di src/storage/memory.rs³ meski datanya tidak disimpan (ke penyimpanan persisten).

1. https://github.com/erikgrinaker/toydb/blob/main/src/storage/engine.rs

2. https://github.com/erikgrinaker/toydb/blob/main/src/storage/bitcask.rs

3. https://github.com/erikgrinaker/toydb/blob/main/src/storage/memory.rs