Mesin Penyimpanan Data untuk Database Terdistribusi
Bagian ini menyelami lapisan terbawah dari database: storage engine (mesin penyimpanan data), setelah sebelumnya mengetahui alur sebuah kueri. Kita akan menjelajahi pertukaran teoretis antara desain engine yang berbeda dan kemudian menganalisis implementasi praktis dalam toydb.
Peran Storage Engine
Tanggung jawab utama dari storage engine adalah untuk menyimpan dan mengambil pasangan key-value di disk secara andal. Ini adalah fondasi fisik tempat semua data berada.
Kisah Dua Arsitektur: B-Trees vs. LSM-Trees
Dua arsitektur dominan untuk storage engine berbasis disk adalah B-Trees dan Log-Structured Merge-Trees (LSM-Trees). Memahami pertukaran di antara keduanya sangat penting untuk desain database.
B-Trees: Struktur data ini dioptimalkan untuk operasi baca. Data diatur dalam halaman (pages) berukuran tetap, dan pencarian kunci menelusuri pohon secara logaritmik. Namun, operasi tulis, pembaruan, dan penghapusan memerlukan I/O acak (random I/O) karena halaman harus dimodifikasi di tempatnya (in-place). Hal ini dapat menjadi bottleneck pada beban kerja yang padat tulis. B-Trees adalah struktur data pengindeksan yang paling banyak digunakan di hampir semua database relasional tradisional seperti MySQL dan PostgreSQL.
LSM-Trees: Sebaliknya, LSM-Trees dioptimalkan untuk operasi tulis. Alih-alih memodifikasi data di tempat, semua operasi tulis (termasuk pembaruan dan penghapusan) adalah operasi penambahan (append) berurutan. Data baru pertama kali ditulis ke struktur dalam memori yang disebut
memtable(dan secara bersamaan ke write-ahead log atau WAL untuk durabilitas). Ketikamemtablepenuh, ia diurutkan dan ditulis ke disk sebagai file immutable yang disebut Sorted String Table (SSTable). Operasi baca mungkin perlu memeriksamemtabledan beberapa SSTable di disk, yang dapat meningkatkan amplifikasi baca (read amplification). Untuk menjaga agar jumlah file tetap terkendali dan meningkatkan efisiensi baca, proses latar belakang yang disebut compaction secara berkala menggabungkan SSTable-SSTable yang lebih kecil menjadi yang lebih besar. Arsitektur ini banyak digunakan oleh database NoSQL seperti Cassandra, LevelDB, dan RocksDB.
Pilihan antara B-Tree dan LSM-Tree melibatkan pertukaran fundamental antara performa baca dan tulis, serta amplifikasi tulis dan ruang.
Write Path & Read Path: Kedua istilah ini adalah terminologi standar dalam internal database untuk menggambarkan urutan operasi yang dilakukan sistem penyimpanan (storage engine) untuk menulis (menyimpan/memperbarui) data dan membaca (mengambil) data.
Write Amplification adalah fenomena di mana jumlah data yang secara fisik ditulis ke media penyimpanan (seperti SSD) lebih besar daripada jumlah data logis yang sebenarnya ingin ditulis oleh aplikasi atau database. Ini diukur sebagai rasio antara data yang ditulis ke perangkat penyimpanan dan data yang ditulis ke database.
Read Amplification mengacu pada jumlah operasi baca disk yang diperlukan untuk satu kueri atau permintaan baca data.Cold Cache (Cache Dingin) adalah keadaan awal dari sebuah cache. Cache tersebut “dingin” karena belum memiliki data yang berguna di dalamnya. Ketika sebuah permintaan data datang, sistem akan memeriksa cache terlebih dahulu. Karena data tersebut tidak ada di sana (cache miss), sistem harus melakukan operasi I/O yang lambat untuk mengambilnya dari penyimpanan utama (seperti SSD atau hard disk).
Warm Cache (Cache Hangat) adalah keadaan transisi di mana cache telah “dihangatkan” oleh permintaan-permintaan sebelumnya. Cache ini tidak lagi kosong, tetapi juga belum terisi secara optimal dengan semua data yang paling sering diakses.
Hot Cache (Cache Panas) adalah keadaan ideal untuk kinerja tinggi. Cache “panas” karena berisi data yang paling sering dan paling baru diakses oleh aplikasi (hot data). Ketika permintaan data datang, kemungkinan besar data tersebut sudah ada di cache (cache hit), sehingga permintaan dapat dilayani dengan kecepatan memori, tanpa perlu mengakses disk sama sekali.Ideal workload (beban kerja ideal): Read-intensive (padat baca) dan Write-intensive (padat tulis).
B-Tree
Write Path: I/O acak, pembaruan in-place pada halaman.
Read Path: Pencarian pohon logaritmik yang efisien, biasanya satu I/O disk (jika warm cache).
Write Amplification: Lebih rendah pada beberapa beban kerja, terutama dengan cache besar.
Read Amplification: Rendah:
\(O(\log_B N)\)Penggunaan Ruang: Kurang efisien; halaman bisa terfragmentasi dan hanya terisi sebagian.
Beban Kerja Ideal: Padat baca, beban kerja transaksional (OLTP).
LSM-Tree
Write Path: Tulis berurutan ke
memtable/WAL, kemudian flush ke SSTable immutable.Read Path: Perlu memeriksa
memtabledan beberapa level SSTable di disk, berpotensi lebih lambat.Write Amplification: Lebih tinggi karena proses compaction yang menulis ulang data berulang kali.
Read Amplification: Lebih tinggi, karena perlu membaca dari beberapa file untuk satu kunci.
Penggunaan Ruang: Lebih efisien karena compaction dan kompresi blok yang rapat.
Beban Kerja Ideal: Padat tulis, throughput tinggi, seperti data timeseries (deret waktu) atau log.
Analisis Lapisan Penyimpanan toydb
toydb menampilkan abstraksi storage engine yang pluggable, yang merupakan praktik desain yang baik untuk fleksibilitas. Implementasi utamanya adalah
BitCask, sebuah model penyimpanan yang terinspirasi dari makalah oleh Riak1.
BitCask adalah hash table berstruktur log yang sederhana. Cara kerjanya adalah sebagai berikut:
Operasi Tulis: Setiap operasi tulis menambahkan entri baru ke akhir file data aktif. Ini adalah operasi I/O berurutan murni, yang sangat cepat pada disk magnetik maupun SSD.
Struktur Indeks: Sebuah hash map dalam memori, yang disebut
keydir, menyimpan pemetaan dari setiap kunci ke lokasi (file ID, offset, ukuran) entri nilai terbarunya di file data.Operasi Baca: Untuk membaca sebuah kunci, sistem hanya perlu melakukan satu pencarian di
keydirdalam memori untuk mendapatkan lokasinya, dan kemudian satu kali I/O disk untuk membaca nilai dari file data.
Pilihan toydb untuk menggunakan BitCask (atau mesin berstruktur log serupa) 2 daripada B-Tree atau LSM-Tree penuh adalah keputusan pedagogis yang disengaja.
Ini memberikan manfaat performa dari penulisan berurutan, sebuah konsep kunci dalam penyimpanan modern, tanpa kompleksitas yang sangat besar dalam mengimplementasikan strategi compaction (untuk LSM-Trees) atau algoritma pohon seimbang (untuk B-Trees). Kompleksitas tersebut akan mengaburkan tujuan pembelajaran utama yang terkait dengan sifat terdistribusi dari sistem.
BitCask mengajarkan konsep yang relevan (penulisan append-only) sambil meminimalkan overhead implementasi, memungkinkan pengembang untuk fokus pada komponen sistem terdistribusi yang lebih baru dan menantang seperti Raft dan MVCC.
Sheehy, J., & Smith, D. (2010). Bitcask: A Log-Structured Hash Table for Fast Key/Value Data. Riak. Diakses pada 3 Oktober 2025, dari https://riak.com/assets/bitcask-intro.pdf