Membangun Database Sendiri

• Menjelaskan prinsip dasar dan proses implementasi database key-value
• Dimulai dari penyimpanan dan pencarian persisten melalui sistem berkas
• Muncul masalah ketidakefisienan saat operasi tambah, ubah, dan hapus data
• Berkembang secara bertahap menjadi struktur yang lebih efisien seperti append-only file, index, pengurutan, segmen kompaksi (compaction), dan lain-lain
• Berkaitan dengan struktur modern seperti LSM Tree yang dipakai di sistem skala besar

---

Pengantar: Memulai Database Sendiri

Jika kita menganggap tidak ada konsep database, maka kita mengeksplorasi langkah demi langkah bagaimana membangun database sendiri. Meninjau proses implementasi bentuk database key-value yang paling sederhana

Ide Dasar: Penyimpanan yang Persisten Menggunakan File

• Tujuan database adalah menyimpan data secara persisten dan kemudian mencari secara efisien di kemudian hari
• Cara paling umum adalah menuliskan setiap pasangan key-value ke file dengan memakai file system
• Saat menyimpan data, misalnya, isi file ditambahkan dengan format seperti $ db set 1 "Lorem ipsum"
• Untuk mencari data, gunakan cara memeriksa secara berurutan semua pasangan key-value di file untuk menemukan key yang diinginkan
• Saat perubahan dilakukan, nilai key tersebut diganti langsung di file, dan saat penghapusan dilakukan, record itu dihapus dari file

Permasalahan: Modifikasi In-Place yang Tidak Efisien

• Modifikasi dan penghapusan langsung di file sangat tidak efisien
• Karena file hanyalah aliran byte, bila data di tengah diubah, semua data setelahnya harus dipindahkan
• Misalnya, saat mengganti suatu record dengan nilai baru yang panjangnya berbeda, beban pemindahan seluruh isi setelahnya muncul
• Semakin banyak data, semakin besar dampaknya terhadap kecepatan dan efisiensi

Peningkatan 1: Struktur Append-Only File

• Terapkan metode menyimpan semua perubahan dengan tetap membiarkan data lama ada, yaitu hanya menambahkan catatan baru di akhir file saat melakukan perubahan atau penghapusan
• Setiap kali data berubah, tambahkan record baru dan ubah algoritma agar mencari key versi terbaru
• Penghapusan ditandai dengan nilai khusus "tombstone" (seperti null)
• Kelebihan: pencatatan dapat dilakukan secara efisien tanpa memindahkan data yang sudah ada
• Kekurangan: file makin membesar karena data duplikat dan penanda penghapusan
• Kecepatan pencarian tetap lambat karena tetap membutuhkan pemindaian menyeluruh

Peningkatan 2: Pengaturan Ukuran File dan Compaction

• Untuk mengatasi masalah file yang terus membesar, saat file melebihi ukuran tertentu, pindah ke file baru (segment) dan hapus data yang tidak perlu (duplikat/terhapus) dari file lama agar ukurannya berkurang (compaction)
• Saat compaction, pertahankan hanya data yang benar-benar dibutuhkan dan hapus catatan lama atau penanda penghapusan yang sudah tidak relevan
• Struktur berkembang menjadi beberapa file segment yang dapat digabung (merge) bila diperlukan

Peningkatan 3: Pencarian Cepat Melalui Index

• Buat in-memory hash table index yang menyimpan offset posisi file untuk setiap key agar pencarian menjadi lebih cepat
• Saat query, indeks diperiksa lebih dulu lalu langsung membaca lokasi file yang sesuai
• trade-off: pencarian cepat, tetapi karena indeks ada di memori, jika jumlah key sangat banyak akan terkena batas memori
• Karena pengelolaan indeks, kinerja tulis sedikit menurun

Peningkatan 4: Sorted String Tables dan Sparse Index

• Jika data selalu disimpan dalam urutan key, query rentang (range query) bisa menjadi sangat efisien
• Dengan keadaan terurut, indeks tidak perlu menyimpan semua key, cukup menyimpan sebagian key (sparse index)
• Densitas indeks dapat diatur untuk menyeimbangkan konsumsi memori dan efisiensi pencarian

Cara Implementasi: Kombinasi In-Memory dan On-Disk untuk Ketahanan Persitenan

• Data baru pertama-tama ditulis ke daftar in-memory yang terurut, dan juga dicatat ke file append-only sebagai bentuk backup
• Ketika daftar in-memory membesar, data tersebut disimpan ke file di disk (SST) dalam keadaan terurut, sambil memperbarui indeks
• Saat membaca, sistem memeriksa memori terlebih dahulu, jika tidak ada maka mencari di disk menggunakan indeks
• File di disk dikelola sebagai immutable, sehingga modifikasi/penghapusan tetap ditangani dengan menambahkan data baru
• Data yang berlebihan, duplikat, atau terhapus dibersihkan secara berkala lewat compaction agar ukuran file terjaga

Kemunculan LSM Tree (Log-Structured Merge Tree)

• Struktur yang berkembang ini saat ini banyak digunakan dengan nama LSM Tree
• Kombinasi memtable in-memory dan file on-disk sorted string table (SST) ini cepat dan cocok untuk skala besar
• LevelDB, Amazon DynamoDB, dan sistem key-value skala besar lain menjadikan ini sebagai struktur data inti
• Meski ada kekurangan dan perbedaan dari struktur lain (misalnya DB relasional berbasis B-Tree), performanya terbukti handal untuk beban trafik tinggi dan skalabilitas besar

Kesimpulan

• Dimulai dari file-based sederhana lalu berkembang melalui append-only, index, pengurutan, segment-compaction, dan kombinasi in-memory-on-disk menjadi desain database yang lebih baik
• Memungkinkan mempelajari cara kerja dan pertimbangan struktural database melalui proses implementasi langsung
• Struktur LSM Tree berperan sebagai komponen standar pada sistem data berskala besar modern
• Masih ada ruang untuk mengeksplorasi pendekatan lain, termasuk struktur B-Tree pada basis data relasional di masa depan

[GN⁺]

Komentar Hacker News

• Saya sangat menyukai desain dan contohnya; komposisinya mudah dibaca dan sangat mengesankan. Praktik semacam ini juga pengalaman yang sangat menyenangkan. Memulai dari kondisi kosong membuat Anda benar-benar bisa menguji seberapa banyak yang Anda kuasai.
  • Saya sendiri dulu sempat bersikap terburu-buru: "Jangan bikin database sendiri, jangan pakai database KV, pakai saja SQL". Tapi pemikiran itu pun baru muncul setelah saya mencoba merancang DB secara langsung atau menghindari SQL demi hanya memakai database KV, lalu akhirnya malah merekayasa ulang SQL dengan cara yang kurang rapi. Jelas nilai belajar dari pengalaman langsung itu nyata.
  • Satu hal yang agak kurang adalah contoh yang menggunakan lorem ipsum, jadi jadi mudah dibaca sekilas tanpa fokus. Contoh data yang nyata pasti lebih menarik. Selain itu, tulisannya memang keren.
• Klaim bahwa "LSM tree adalah struktur data yang secara dasar dipakai di DynamoDB dan berkinerja sangat baik bahkan di skala besar... mampu menangani 80 juta request per detik" agak menyesatkan. LSM digunakan pada storage engine tingkat node, dan tidak menjelaskan bagaimana sistem terdistribusi secara keseluruhan diskalakan sampai 80 juta rps. Setahu saya, paper Dynamo aslinya memang memakai BerkeleyDB (b-tree atau LSM), lalu pada paper 2012 beralih penuh ke mesin berbasis LSM.
• Saya mengklik beberapa artikel dari daftar dan terkesan dengan desain serta animasinya yang benar-benar cantik—sangat mengagumkan.
• Bagian pertama contoh di "Sorting in Practice" terlihat rusak. Penjelasan tertulis bahwa data disortir di memori lalu ditulis ke disk dalam keadaan terurut, tapi contoh aslinya justru membuat urutannya hilang saat menulis ke disk. Begitu juga contoh flush (yang kedua) di bagian recap, sementara teksnya menyatakan file ditulis dalam kondisi terurut.
• Menarik sekali. Akhir-akhir ini saya sedang memodelkan aktivitas developer sebagai sistem key-value time-series—setiap developer sebagai key, commit sebagai value. Saya mengalami masalah serupa: log tumbuh cepat, indeks jadi berat, dan query rentang menjadi lambat. Saya penasaran bagaimana menentukan data mana yang dibuang saat segment compaction; rasanya sulit menyeimbangkan kebaruan dan periode retensi.
• Saya sudah menghabiskan 4 minggu terakhir fokus menulis triple store sendiri. Sayang, beberapa insight yang bisa membuat saya lebih cepat paham akan lebih berguna jika artikel ini keluar sedikit lebih awal.
• Kalau penulis membaca ini, saya penasaran apakah Anda bisa menambahkan RSS feed di situsnya. Ingin banget menambahkannya ke Feedly supaya lebih mudah dibaca.
• Kalau Anda ingin membuat database sendiri, saya sangat merekomendasikan buku online gratis ini.
  • Saya ingat ada artikel yang menjelaskan konsep dasar database lewat contoh bash (mis. "Membuat DB dengan Bash") yang dulu diperkenalkan di sini, tapi sekarang saya tidak bisa menemukannya. Jika ada yang tahu tautannya, tolong bagikan.
• Situsnya sekarang sudah terlalu ramai hingga tidak bisa diakses.
  • Berarti butuh database yang lebih cepat.
• Saya sangat suka pendekatan yang menjelaskan dari "First Principles" seperti ini. Jika diikuti, di setiap tahap Anda bisa melihat masalah apa yang muncul, dan saat memecahkannya muncul masalah tambahan apa. Jadi jelas banget prosesnya sampai akhirnya sampai pada solusi yang terasa sangat memuaskan.