Dasar-Dasar Database

Dasar-Dasar bashdb

• bashdb, program database paling sederhana, terdiri dari dua fungsi bash.
• Fungsi db_set menambahkan data ke file, dan fungsi db_get mencari data.
• Masalah pada bashdb mencakup durabilitas, atomisitas, isolasi, dan performa.

Meningkatkan bashdb menjadi ACID

• ACID adalah sifat transaksi database yang berarti atomisitas, konsistensi, isolasi, dan durabilitas.
• Untuk meningkatkan durabilitas bashdb, perintah sync ditambahkan ke db_set.
• Untuk isolasi, penguncian file ditambahkan menggunakan program flock.

Durabilitas

• fsync dan fdatasync adalah system call yang mem-flush buffer tulis ke disk.
• Perintah sync mem-flush semua halaman 'dirty' ke disk, dan flag -d memanggil fdatasync.

Isolasi

• flock digunakan untuk menyediakan isolasi multi-proses pada bashdb.
• flock adalah program Linux untuk penguncian file, dan flag -s digunakan untuk mengizinkan pembacaan simultan.

Kabar buruk

• Tidak ditemukan cara sederhana untuk menjamin atomisitas dengan bashdb.
• Untuk meningkatkan performa, algoritma O(n) perlu diperbaiki.

Storage engine

• Tujuan storage engine adalah menyediakan abstraksi untuk membaca dan menulis data ke penyimpanan persisten.
• Desain storage engine bertujuan meminimalkan disk I/O dan disk seek.

B-tree yang dapat diubah

• B-tree adalah varian BST dengan locality spasial yang meminimalkan disk I/O dan seek.
• B-tree adalah BST yang digeneralisasi agar node dapat memiliki lebih banyak child.

LSM tree immutable

• LSM tree adalah struktur data immutable yang ditulis secara sekuensial dan menguntungkan untuk workload yang berfokus pada penulisan.
• LSM tree mem-buffer data di memori, lalu saat mencapai kapasitas tertentu, data di-flush menjadi SSTable terurut.

Bloom filter

• Bloom filter adalah struktur data probabilistik yang dapat memeriksa secara efisien apakah suatu item tidak ada di dalam himpunan.
• Bloom filter bekerja menggunakan fungsi hash, dan memiliki kompleksitas ruang O(log n).

Write Ahead Log

• WAL adalah file khusus yang mencatat semua operasi transaksi dan merekonstruksi status saat proses database dimulai.

Isolasi

• Untuk mencapai isolasi, dapat digunakan pessimistic locking, optimistic locking, atau MVCC.
• ANSI/ISO standard SQL 92 mendefinisikan berbagai tingkat isolasi pembacaan.

Sistem terdistribusi

• Sistem terdistribusi menambah kompleksitas, dan data dapat didistribusikan ke beberapa mesin demi ketersediaan dan scale-out horizontal.
• Menurut teori CAP, sistem hanya dapat menjamin dua dari tiga hal: konsistensi, ketersediaan, dan toleransi partisi.

Consistent hashing

• Consistent hashing adalah metode partisi data yang mengurangi jumlah item yang harus dimigrasikan saat node ditambahkan atau dihapus.

Pendapat GN⁺:

• Memahami masalah dasar database dan sifat ACID adalah inti dari rekayasa database.
• Contoh bashdb membantu memahami masalah yang muncul pada sistem database nyata.
• Desain storage engine dan sistem terdistribusi adalah faktor penting yang menentukan performa dan keandalan database.

[GN⁺]

Komentar Hacker News

• Ringkasan komentar pertama:

  • Salah satu karakteristik database berbasis LSM adalah record yang dihapus atau tombstone dapat tetap tersisa dalam waktu lama.
  • Tombstone hanya boleh dilewati pada level terakhir, dan tidak boleh dilewati di semua level.
  • Jika tidak, tombstone di level atas bisa terhapus sehingga entri di level bawah muncul kembali.
  • Database seperti RocksDB berupaya menyelesaikan masalah ini dengan optimisasi.

• Ringkasan komentar kedua:

  • Menghindari mempelajari sistem terdistribusi bisa berbahaya.
  • Pada praktiknya, semua sistem produksi yang nontrivial adalah sistem terdistribusi.
  • Jika database merupakan himpunan replikasi, maka itu adalah sistem terdistribusi.
  • Jika ingin mempelajari sistem terdistribusi, lihat jepsen.io dan raft.github.io.

• Ringkasan komentar ketiga:

  • Ada konsistensi database dan konsistensi aplikasi.
  • ACID (atomicity, consistency, isolation, durability) bisa dicapai pada satu tabel, tetapi dapat gagal pada penulisan yang melibatkan banyak tabel.
  • Saat menangani transaksi yang memperbarui banyak tabel sekaligus, semua tabel harus diperbarui bersamaan atau sama sekali tidak diperbarui.

• Ringkasan komentar keempat:

  • Ini adalah tulisan yang memberikan gambaran sangat baik tentang berbagai konsep yang terlibat dalam membangun database.
  • Mencakup dari peningkatan performa pada satu mesin dengan SIMD hingga algoritme konsensus.
  • Ada penyebutan tentang metode formal yang diterapkan pada keandalan database dan sistem terdistribusi.
  • Ada makalah menarik tentang bagaimana tim Amazon S3 melakukan pemodelan dengan TLA+.

• Ringkasan komentar kelima:

  • Banyak orang mempelajari database dengan belajar SQL, tetapi dengan memahami B-tree, kita bisa lebih memahami kekuatan dan kelemahan RDBMS.
  • Orang mencoba mempercepat database dengan menambahkan indeks, tetapi sebenarnya itu hanya menutupi masalah.
  • Beberapa masalah cocok untuk B-tree, tetapi banyak yang tidak.
  • SQL hanyalah antarmuka kueri untuk sistem B-tree jarak jauh.

• Ringkasan komentar keenam:

  • Banyak pengembang pada suatu titik akan melewati fase membuat database kecil mereka sendiri.
  • Melalui proses ini, mereka dapat belajar banyak tentang apa yang tidak bekerja.
  • Membuat database sendiri membantu meningkatkan penghargaan terhadap solusi yang sudah ada.
  • Mengirimkan data dari disk dengan cepat dan andal adalah pekerjaan yang sulit.

• Ringkasan komentar ketujuh:

  • Dalam versi Bash, atomicity dapat dicapai dengan menyalin file ke file sementara, lalu memodifikasinya dan menggunakan sync; mv; sync.

• Ringkasan komentar kedelapan:

  • Ini adalah desain yang sangat keren, dengan API dokumen yang mirip MongoDB, replikasi tanpa leader yang mirip Cassandra, dan arsitektur satu core per thread yang mirip ScyllaDB.
  • Semua itu diimplementasikan dalam Rust.

• Ringkasan komentar kesembilan:

  • Buku 'Database Internals' luar biasa bagus dan memberikan pembahasan mendalam tentang internals.
  • Penulis bertanya apakah ada buku lain yang serupa.

• Ringkasan komentar kesepuluh:

  • Buku 'Database Design and Implementation' juga sangat bagus untuk dibaca, dengan banyak contoh yang ditulis dalam Java.
  • Untuk riset yang lebih nyata, disarankan karya Andy (Pavlo), Viktor Leis, Thorsten Grust, Thomas Neumann, dan lainnya.