Dasar-Dasar Database

 (tontinton.com)
5 poin oleh GN⁺ 2023-12-16 | 1 komentar | Bagikan ke WhatsApp
  • Berangkat dari penyimpanan key-value Bash sederhana, artikel ini menunjukkan secara bertahap mengapa database nyata harus menangani durability, atomicity, isolation, dan performa sebagai masalah desain tersendiri
  • fsync/fdatasync, flock, dan WAL adalah alat dasar untuk melindungi data dalam situasi kegagalan dan konkurensi, tetapi semakin tinggi tingkat jaminannya, semakin besar biaya performanya
  • Storage engine menggunakan struktur seperti B-tree dan LSM tree untuk mengurangi I/O disk dan biaya pencarian, dan masing-masing disertai pemeliharaan seperti vacuum dan compaction
  • Database terdistribusi memperoleh ketersediaan dan penskalaan horizontal, tetapi harus menanggung kompleksitas sistem terdistribusi seperti teorema CAP, network partition, penyesuaian konsistensi, dan penyelesaian konflik
  • Saat memilih atau mengimplementasikan database, jaminan ACID, tingkat isolation, struktur penyimpanan, metode replikasi, dan kebutuhan konsistensi harus disesuaikan dengan workload

Masalah dasar database yang terungkap lewat bashdb

  • bashdb adalah penyimpanan key-value sederhana yang dibuat dari dua fungsi Bash
    • db_set melakukan append ke file dalam format key,value
    • db_get membaca nilai terakhir dengan menggabungkan grep, sed, dan tail
  • Meski sederhana untuk pembelajaran, implementasi ini saja sudah memperlihatkan masalah yang harus diselesaikan database produksi
    • Durability: jika mesin crash setelah db_set berhasil, data yang belum di-flush ke disk bisa hilang
    • Atomicity: jika crash terjadi saat penulisan, hanya sebagian data yang bisa tercatat sehingga data rusak
    • Isolation: jika pembacaan dan penulisan mengakses item yang sama secara bersamaan, pihak pembaca bisa melihat hanya sebagian data
    • Performance: db_get menelusuri seluruh file baris demi baris, sehingga kompleksitasnya O(n)

ACID dan upaya memperbaiki bashdb

  • ACID adalah akronim untuk sekumpulan sifat yang ingin dijamin oleh banyak database
    • Atomicity: jika terjadi kegagalan saat penulisan, seluruh transaksi dibatalkan atau di-rollback sehingga tidak menyisakan kondisi penulisan parsial
    • Consistency: transaksi ilegal tidak boleh merusak database
    • Isolation: tidak boleh ada race condition pada akses bersamaan ke data yang sama
    • Durability: penulisan yang berhasil harus tetap bertahan bahkan setelah situasi seperti kegagalan daya
  • Tidak semua transaksi database harus selalu menjamin ACID; pada sebagian kasus penggunaan, jaminan dapat diturunkan demi performa

  • Durability dan fsync

    • System call write menulis buffer ke file, tetapi bukan berarti data langsung tercatat ke penyimpanan non-volatil
    • Kernel dapat menyimpan buffer sebagai dirty page di page cache lalu mem-flush-nya ke disk nanti
    • Perangkat disk atau sistem RAID juga dapat memiliki write cache terpisah
    • fsync dan fdatasync adalah system call untuk mem-flush dirty page ke penyimpanan permanen
    • fdatasync mem-flush raw buffer yang dikirim lewat write
    • fsync mem-flush bukan hanya data, tetapi juga metadata file seperti mtime
    • Menambahkan sync -d database setelah db_set dapat meningkatkan durability dengan perilaku yang mendekati fdatasync, tetapi biasanya sync lebih lambat daripada write itu sendiri sehingga performa memburuk
    • Keberhasilan fsync() berarti “semua write sejak fsync terakhir telah mencapai disk”, bukan hanya “write setelah fsync terakhir yang berhasil”
    • PostgreSQL mengalami masalah ini pada 2018, lalu mengubah perilakunya menjadi panic saat fsync gagal, alih-alih mencoba ulang
    • Peristiwa ini dikenal sebagai fsyncgate, dan materi terkaitnya menaut ke makalah fsync failures
    • Secara default, penulisan MongoDB di-sync setiap 100ms, sehingga tidak 100% durable

  • Isolation dan flock

    • Metode isolation multiproses paling sederhana di bashdb adalah memasang lock sebelum membaca atau menulis file penyimpanan
    • flock di Linux mengunci file, dan dengan flag -s, beberapa reader dapat membaca bersamaan melalui shared lock
    • bashdb yang diperbaiki menggunakan exclusive lock untuk penulisan dan shared lock untuk pembacaan
    • Kekurangannya adalah setiap penulisan mengunci seluruh database
    • Sulit menjamin atomicity secara sederhana hanya dengan Bash; ada kemungkinan menggunakan mv -T atau rename, tetapi tidak diselesaikan
    • bashdb tetap tidak menyelesaikan masalah lookup O(n)

Peran dan bottleneck storage engine

  • Storage engine menyediakan abstraksi untuk membaca dan menulis data ke penyimpanan persisten, dengan tujuan utama throughput tinggi dan latensi rendah
  • Kendala terbesar berasal dari perbedaan kecepatan disk itu sendiri
    • Dalam contoh tabel latensi, referensi L1 cache disajikan sekitar 0.5ns, 4KB random read dari SSD 150,000ns, dan disk seek 10,000,000ns
    • Jika referensi L1 cache dianggap setara detak jantung sekitar 0,5 detik, maka pembacaan sekuensial 1MB dari SSD setara sekitar 12 hari, dan pembacaan sekuensial 1MB dari disk setara sekitar 8 bulan
  • Karena itu, desain storage engine berkembang ke arah meminimalkan I/O disk dan disk seek sebanyak mungkin
  • Elemen desain storage engine yang umum adalah sebagai berikut
    • Struktur data dasar untuk menyimpan item di disk
    • Transaksi ACID
    • Cache untuk mengurangi pembacaan disk
    • Lapisan API seperti SQL, document, dan graph
  • Struktur data storage engine secara garis besar dapat dibagi menjadi struktur yang dapat diubah dan struktur immutable
    • Struktur yang dapat diubah dapat menimpa data yang sudah ditulis ke file di kemudian hari
    • Struktur immutable hanya membaca kembali data yang sudah ditulis ke file

B-tree yang dapat diubah

  • Agar tetap memiliki performa baik meski data bertambah, item harus bisa ditemukan dalam waktu paling banyak logaritmik, bukan pencarian linear seperti bashdb
  • BST memungkinkan lookup O(log n), tetapi jika node saling berjauhan di disk, proses pencarian dapat memicu banyak disk seek
  • B-tree adalah generalisasi BST di mana satu node dapat memiliki lebih dari dua child, dan memanfaatkan spatial locality
    • Setelah biasanya membaca page 4KB atau 8KB dari disk, banyak node di dalamnya dibandingkan secara berurutan di memori dan CPU cache
    • Karena akses memori dan CPU cache beberapa orde magnitudo lebih cepat daripada disk, penting untuk memanfaatkan sebanyak mungkin byte yang sudah dibaca dari disk
  • Akses memori sekuensial bisa sangat kuat berkat SIMD, instruction pipelining, dan prefetching
  • B+ tree hanya menyimpan nilai pada leaf node dan node lainnya hanya menyimpan key, sehingga lebih banyak key dapat dibandingkan dalam satu page disk

  • Reklamasi ruang dan vacuum

    • B-tree perlu mereklamasi ruang kosong akibat fragmentasi data untuk mengoptimalkan ruang
    • Jika diperbarui dengan nilai besar, data node berikutnya bisa tertimpa, sehingga item dipindahkan ke lokasi lain dan page asal menyisakan lubang
    • Jika diperbarui dengan nilai kecil, lubang tersisa di bagian akhir
    • Penghapusan membuat lubang di tempat nilai yang dihapus sebelumnya berada
    • Proses reklamasi ruang dan penulisan ulang page seperti ini dapat disebut vacuum, compaction, page defragmentation, maintenance, dan sebagainya
    • Biasanya dilakukan di latar belakang untuk menghindari spike latensi pada permintaan pengguna
    • PostgreSQL dapat mengonfigurasi auto vacuum daemon
    • B-tree umum digunakan sebagai struktur data dasar index, seperti index default PostgreSQL, dan DynamoDB pernah dijuluki secara bercanda sebagai “distributed B-tree”

LSM tree yang immutable

  • LSM tree adalah struktur data append-only yang berangkat dari fakta bahwa disk seek itu mahal
  • Jika data hanya ditambahkan di akhir file, head disk tidak perlu banyak berpindah ke lokasi penulisan berikutnya, sehingga menguntungkan untuk workload dengan banyak penulisan
  • Log Structured Merge tree, disingkat LSM tree, digunakan pada storage engine database modern seperti RocksDB, Cassandra, dan ScyllaDB
  • Operasi dasarnya adalah sebagai berikut
    • Men-buffer penulisan ke struktur data di memori yang dapat diurutkan
    • Contohnya adalah AVL tree, Red Black tree, dan Skip List
    • Saat mencapai kapasitas tertentu, data di-flush menjadi file terurut bernama Sorted String Table, atau SSTable
  • SSTable menyimpan data terurut sehingga dapat mengurangi I/O disk dengan binary search dan sparse index
  • Untuk durabilitas, operasi yang ditulis ke memori dicatat ke Write-Ahead Log, atau WAL
    • Saat program dimulai, WAL dibaca untuk memulihkan kondisi sebelum berhenti atau crash
  • Penghapusan juga di-append seperti penulisan biasa, dan tombstone disimpan sebagai pengganti nilai
    • Tombstone dihapus dalam proses compaction

  • Pembacaan dan compaction pada LSM tree

    • Pembacaan pada LSM tree pertama-tama mencari di struktur data memori; jika tidak ada, ia menelusuri SSTable di disk dari file terbaru ke file terlama
    • Semakin banyak penulisan, semakin banyak jumlah SSTable yang harus diperiksa
    • Meskipun setiap file terurut, menelusuri banyak file kecil bisa lebih lambat daripada melihat satu file besar
    • Ekspresi perbandingannya adalah log(num_files * table_size) < num_files * log(table_size)
    • Compaction adalah pekerjaan latar belakang yang menggabungkan beberapa SSTable kecil menjadi satu SSTable besar dan menghapus tombstone
    • RocksDB mengimplementasikan Leveled Compaction
    • SSTable yang baru di-flush ditempatkan di level 0
    • Jika sejumlah file yang dikonfigurasi menumpuk pada satu level, setelah compaction file baru dipromosikan ke level berikutnya
    • Penghapusan tombstone harus dilakukan dengan hati-hati
    • Dapat muncul masalah data resurrection, yaitu item yang sudah dihapus hidup kembali saat compaction dengan file yang lebih lama
    • RocksDB mempertahankan tombstone hingga sebelum compaction yang mempromosikannya ke level terakhir
    • Contoh nyata dalam Rust ditautkan ke kode LSM tree dbeel

  • Bloom filter

    • Bloom filter adalah struktur data himpunan probabilistik untuk memeriksa secara efisien bahwa suatu item tidak ada dalam sebuah set
    • Hasil lookup ada dua
      • false: item dipastikan tidak ada dalam set
      • true: item mungkin ada dalam set
    • Bloom filter memetakan hasil dari beberapa hash function ke posisi bit pada bitmap dan menyetelnya menjadi 1
    • Kompleksitas ruang disajikan sebagai O(log n), berbeda dari O(n) pada set biasa
    • Dengan mengalokasikan lebih banyak memori bitmap dan menambah jumlah hash function, probabilitas untuk “yakin bahwa item tidak ada” dapat disesuaikan; tersedia juga kalkulator
    • LSM tree menyimpan Bloom filter untuk setiap SSTable, sehingga dapat melewati pencarian pada SSTable yang dipastikan tidak memiliki key tertentu

WAL dan jaminan transaksi

  • WAL adalah metode mencatat semua operasi transaksi ke file khusus agar dapat bertahan dari crash mendadak
  • Saat proses database dimulai, file WAL dibaca dan status data direkonstruksi
    • Transaksi tanpa commit log dilewati, sehingga atomicity diperoleh
  • Jika data permintaan penulisan dicatat dan di-flush ke WAL sebelum merespons pengguna, data tersebut pasti dapat dibaca saat startup, sehingga durabilitas diperoleh
  • WAL dapat dilihat sebagai salah satu bentuk event sourcing untuk event transaksi

Level isolasi dan kontrol konkurensi

  • Cara mencapai isolasi secara garis besar terbagi menjadi tiga
    • Lock pesimistis: mencegah akses ke data yang sedang ditulis
    • Lock optimistis: memodifikasi salinan data, lalu commit hanya jika data asli tidak berubah selama transaksi; jika berubah, retry
    • MVCC: tidak menimpa data, melainkan membuat version baru, sehingga setiap pengguna melihat snapshot pada titik waktu tertentu
  • Tidak semua aplikasi membutuhkan isolasi penuh, yaitu serializable isolation
  • ANSI/ISO SQL 92 mengklasifikasikan hasil yang dapat terjadi ketika transaksi lain mengubah data yang sama selama sebuah transaksi menjadi tiga jenis
    • Dirty read: membaca update dari transaksi lain yang belum commit
    • Non-repeatable read: di antara dua pembacaan row yang sama, transaksi lain melakukan commit sehingga nilainya berubah
    • Phantom read: di antara dua pembacaan kumpulan row dengan kondisi yang sama, ada row yang ditambahkan atau dihapus
  • Level isolasi ANSI/SQL 92, dari yang tertinggi, adalah sebagai berikut
    • Serializable: hanya membaca data yang sudah commit dan menghindari phantom read, termasuk penulisan multi-row berbasis rentang
    • Repeatable reads: phantom read diperbolehkan
    • Read committed: non-repeatable read diperbolehkan
    • Read uncommitted: dirty read diperbolehkan
  • Level isolasi yang lebih tinggi biasanya disertai pengorbanan performa
  • Level isolasi ANSI/SQL 92 dikritik karena tidak lengkap
    • Banyak implementasi MVCC menyediakan snapshot isolation, bukan serializable isolation
    • HyPer direkomendasikan sebagai algoritme MVCC serializable yang cepat

Mengapa sistem terdistribusi diperlukan dan CAP

  • Sistem terdistribusi menambahkan banyak kompleksitas, sehingga sebaiknya dihindari ketika solusi non-terdistribusi sudah memadai
  • Ada dua alasan umum mengapa data perlu didistribusikan ke beberapa mesin
    • Ketersediaan (Availability): meskipun mesin database crash atau koneksi dengan pengguna terputus, permintaan dapat dikirim ke mesin lain
    • Skalabilitas horizontal (Horizontal Scaling): alih-alih melakukan vertical scaling dengan mesin tunggal yang lebih besar, beberapa mesin yang terhubung melalui jaringan dibuat bertindak seperti satu kesatuan
  • Sistem terdistribusi memperkenalkan kompleksitas operasional dan masalah network partition
  • Teorema CAP mengatakan bahwa sistem hanya dapat menjamin dua dari tiga hal berikut
    • Consistency: pembacaan menerima penulisan terbaru
    • Availability: semua permintaan berhasil terlepas dari adanya kegagalan
    • Partition Tolerance: sistem terus beroperasi meskipun ada kehilangan atau keterlambatan pesan antar-node
  • Database pada satu mesin tidak memiliki network partition dan konsisten, tetapi saat mesin gagal, permintaan baru gagal sehingga melanggar availability
  • Jika dua mesin memiliki CPU, memori, dan disk yang terpisah serta terhubung dengan kabel, pilihan akan bercabang dalam situasi kegagalan
    • Jika permintaan dibatalkan, availability dikorbankan dan consistency dipertahankan
    • Jika permintaan terus diproses hanya pada mesin yang masih beroperasi, consistency dikorbankan dan availability dipertahankan
  • Sistem yang mengorbankan consistency lalu menyelaraskannya kemudian disebut eventually consistent
  • Network partition juga membuat JOIN yang efisien menjadi sulit karena harus mengumpulkan data yang tersebar di cluster, dan kubu NoSQL merekomendasikan denormalization untuk menguranginya

Replikasi dan Contoh Amazon Dynamo

  • Paper Dynamo asli dari Amazon diperkenalkan sebagai contoh bahwa di keranjang belanja amazon.com, availability dianggap lebih penting daripada consistency
    • Jika pengguna melihat dua item yang sama di keranjang belanja, mereka cukup menghapus salah satunya
    • Ini dinilai lebih baik daripada situasi ketika pembelian sama sekali tidak bisa dilakukan
  • Untuk memperoleh availability, tidak cukup hanya dengan beberapa node membagi data; setiap item juga harus memiliki setidaknya satu salinan
  • Node yang menyimpan salinan item disebut replica, dan proses penyalinannya disebut replication
  • Meningkatkan jumlah replica akan menaikkan availability, tetapi membutuhkan lebih banyak sumber daya untuk menyimpan salinan
  • Salinan data tidak harus disimpan secara utuh; data juga dapat dipecah dengan erasure coding dan disebar ke beberapa node, dengan karakteristik latensi terkait dijelaskan di artikel erasure coding

Consistent Hashing dan Penempatan Data

  • Saat ada beberapa node, diperlukan metode load balancing atau partisi data untuk menentukan node mana yang menangani permintaan penyimpanan
  • Metode sederhana adalah melakukan hash pada primary key lalu mengambil modulo dengan jumlah node
    • Jika node ditambahkan atau dihapus, len(nodes) berubah sehingga key yang sama menunjuk ke node yang berbeda
    • Dalam kasus ini, hampir semua item harus dimigrasikan, sehingga biayanya besar
  • Consistent Hashing menempatkan node pada ring, bukan array, sehingga mengurangi jumlah item yang harus dipindahkan saat node ditambahkan atau dihapus
    • Digunakan dalam database seperti Dynamo dan Cassandra
  • Dalam consistent hashing, hash dari nama node ditempatkan pada ring, dan node yang ditemui setelah hash dari key permintaan menjadi pemiliknya
  • Pemilihan replica dapat dilakukan dengan mengitari ring berlawanan arah jarum jam dan menyimpan salinan pada node berikutnya
    • Jika node pemilik mati, node replica menangani permintaan untuk mempertahankan availability
    • Cara ini disebut Leaderless Replication dan digunakan dalam database bergaya Dynamo seperti Cassandra
  • Jumlah key yang harus dipindahkan saat node ditambahkan rata-rata adalah num_keys / num_nodes
  • Virtual node menempatkan satu node fisik beberapa kali pada ring untuk mengurangi kemungkinan sebagian node memiliki terlalu banyak item
    • Contohnya adalah menambahkan index sebagai suffix pada nama node, seperti "half-0", "half-1"
  • Ada metode lain untuk memilih leader node dan replica node, yaitu leader election, tetapi tidak dibahas di sini

Leaderless Replication dan Penyesuaian Konsistensi

  • Konfigurasi leaderless mengorbankan consistency sebagai imbalan untuk mendapatkan availability yang tinggi
  • Jika node pemilik sedang down saat permintaan write, data ditulis ke replica, dan setelah node pemilik kembali aktif, permintaan read dapat membaca data lama
  • Jika consistency diperlukan pada permintaan tertentu, permintaan read dikirim secara paralel ke beberapa replica dan node pemilik, lalu klien memilih data yang paling baru
  • Permintaan write biasanya dikirim secara paralel ke semua replica, tetapi hanya menunggu acknowledgement dari sebagian node
  • Untuk menyesuaikan consistency pada tingkat permintaan, periksa R + W > N/2 + 1
    • N: jumlah node yang memiliki salinan data
    • W: jumlah node yang harus memberikan acknowledgement agar write berhasil
    • R: jumlah node yang harus merespons agar read berhasil
  • Permintaan ke mayoritas node, dengan W atau R sebesar N/2 + 1, disebut quorum

  • Resolusi Konflik

    • Proses memilih write terbaru disebut Conflict Resolution
    • Sekadar membandingkan timestamp sulit dipercaya dalam sistem terdistribusi
    • Setiap mesin memiliki hardware clock sendiri, dan clock tidak sepenuhnya akurat sehingga terjadi drift
    • NTP mengambil waktu dari sumber waktu yang lebih akurat, tetapi karena permintaan itu sendiri melewati jaringan, waktu yang dibutuhkan hingga respons tidak dapat diketahui dengan tepat
    • Cassandra menggunakan timestamp, dan dokumentasi terkait ditautkan sebagai Cassandra data versioning
    • Google Spanner mencapai jaminan consistency berbasis clock dengan hardware waktu khusus berpresisi tinggi dan API yang mengekspos rentang ketidakpastian timestamp; paper terkait adalah Spanner paper
    • Sistem seperti Dynamo mengurangi sebagian konflik dengan Version Vectors
    • Setiap versi item diberi pasangan (node, counter) untuk menemukan hubungan kausal antarversi
    • Versi yang jelas lebih baru dapat ditemukan sehingga sebagian nilai lama dapat dihapus
    • Referensi lebih lanjut ditautkan ke Dotted Version Vectors
    • Seperti Riak KV, nilai-nilai yang konflik juga dapat dikembalikan semuanya ke aplikasi, lalu aplikasi menyelesaikannya berdasarkan pengetahuan tentang data
    • Berbagai teknik untuk mengurangi konflik dalam sistem eventually consistent biasanya dikelompokkan di bawah istilah Anti Entropy

Teknik Anti Entropy

  • Read Repair

    • Setelah klien memilih nilai terbaru dari hasil read beberapa node, nilai tersebut dikirim kembali ke node-node yang belum menyimpannya untuk melakukan repair

  • Hinted Handoff

    • Jika permintaan write tidak dapat mencapai node tujuan, data disimpan sebagai hint di node lain
    • Saat node tujuan kembali available, hint yang tersimpan diteruskan kepadanya
    • Dalam quorum write, cara ini juga disebut Sloppy Quorum dan meningkatkan availability permintaan quorum

  • Merkle Trees

    • Karena read repair hanya memperbaiki data yang dibaca, banyak data dapat tetap tidak konsisten dalam waktu lama
    • Menemukan seluruh perbedaan dengan menyinkronkan antar-node mahal saat datanya banyak, yaitu O(n)
    • Merkle tree adalah struktur hierarkis yang menyimpan hash rentang data pada leaf, sementara parent menyimpan hash hasil kombinasi hash anak-anaknya
    • Jika hash root sama, data di kedua node sama; jika berbeda, hash di bawahnya dibandingkan secara rekursif untuk menemukan data yang tidak cocok, sehingga sinkronisasi dapat dibuat cepat menjadi O(log n)

  • Gossip Dissemination

    • Ini adalah cara sederhana dan andal untuk menyebarkan event ke seluruh klaster
    • Node mengirim pesan ke sejumlah node acak yang telah ditetapkan, yaitu fanout, lalu node penerima mengirimkannya lagi ke N node acak
    • Jika pesan gossip yang sama sudah terlihat sebanyak jumlah yang ditetapkan, pesan tersebut tidak lagi di-broadcast
    • Tersedia simulator untuk merasakan konvergensi data
    • Pesan gossip biasanya dikirim melalui UDP

Area yang Dapat Dibahas Lebih Mendalam

  • Selain hal-hal yang dibahas di sini, database memiliki banyak topik lain
    • Penggunaan O_DIRECT di Linux dan implementasi page cache sendiri
    • Failure detection dalam sistem terdistribusi
    • Algoritme consensus seperti Raft
    • Distributed transaction
    • Leader election
  • Saat memilih atau mengimplementasikan database, perlu dilihat bersama bagaimana storage engine, ACID, isolation level, replikasi terdistribusi, dan metode resolusi konflik sesuai dengan kebutuhan nyata

Bacaan terkait

1 komentar

 
GN⁺ 2023-12-16
Opini Hacker News

  • Ada bug pada metode compact: tombstone seharusnya hanya dilewati saat melakukan kompaksi level terakhir, yaitu level terbesar, dan tidak boleh dihapus di antara semua level.
    Jika tidak, tombstone di level atas akan hilang selama proses kompaksi, sehingga entri yang ada di level bawah muncul kembali.
    Dalam database berbasis LSM, salah satu karakteristiknya adalah record penghapusan/tombstone bertahan lama, dan beberapa database seperti RocksDB memasukkan optimasi untuk menghindari hal ini.

    • Benar, di artikel sengaja dihilangkan demi keringkasan, dan di dbeel sudah ditangani.
    • Penasaran optimasi seperti apa yang dilakukan RocksDB.
      Saya tahu fitur untuk range deletion, tetapi tidak terlalu ingat pernah membaca soal penghapusan single-key.

  • Banyak orang mempelajari database sambil belajar SQL, tetapi saya menyarankan belajar dengan mengikuti kelas seperti ini dan memahami B-tree.
    Kelebihan dan kekurangan RDBMS sebagian besar dapat dipahami jika kita mengetahui B-tree dan dampaknya terhadap penyisipan key, lookup, dan pengurutan.
    Banyak orang mencoba mempercepat database dengan menambahkan indeks, tetapi pada akhirnya itu hanya menumpuk pohon lain di atas pohon, sehingga menutupi masalah mendasar.
    Sebagian masalah cocok dengan B-tree, tetapi banyak juga yang tidak.
    SQL hanyalah antarmuka kueri untuk sistem B-tree jarak jauh.

    • Itu terlalu reduksionis.
      B-tree juga bukan satu-satunya strategi pengindeksan, dan sudah diketahui umum bahwa indeks adalah mekanisme untuk meningkatkan performa baca dengan mengorbankan performa tulis.
      Sebab, secara umum database menangani jauh lebih banyak pembacaan daripada penulisan.
      Saya penasaran masalah apa tepatnya yang ditutupi oleh “menumpuk pohon lain di atas pohon”, dan bagaimana Anda akan menyelesaikannya tanpa menyentuh indeks.
      Untuk tabel berukuran cukup, indeks pada praktiknya wajib.
    • Saya setuju dengan ini.
      Kita perlu mempelajari hal-hal seperti B-tree dan hash index, lapisan I/O, dan model proses.
      Saat ini strategi umum database berorientasi kolom juga layak dipelajari: late tuple materialization, lazy execution, linear scan dan binary search, instruction pipelining, dan semacamnya.
      Setelah terbiasa dengan hal-hal ini, di lapangan kita akan menyadari bahwa terkadang yang cukup bukan DBMS, melainkan file datar sederhana atau database embedded seperti RocksDB.
    • Bisa saja B-tree, LSM-tree, trie, atau struktur indeks lain yang sesuai dengan situasinya.
      Tentu saja, bisa juga ada covering index.
    • Akan bagus jika bagian “menutupi masalah karena menumpuk pohon lain di atas pohon” dijelaskan dengan contoh konkret.

  • Untuk saran “hindari sistem terdistribusi jika solusi non-terdistribusi sudah cukup”, saya ingin mengatakan sebaliknya.
    Semua sistem operasional yang tidak sepele adalah sistem terdistribusi.
    Setidaknya jika database Anda berupa replica set, itu sudah merupakan sistem terdistribusi, jadi tidak mempelajari sistem terdistribusi berarti mengambil risiko.
    https://jepsen.io/ dan https://raft.github.io/ layak dilihat.

    • Sebagian dari sistem mungkin tidak bisa menghindari panggilan jaringan atau aspek terdistribusi.
      Namun itu tidak berarti hal tersebut boleh diterapkan di mana-mana; jika dilakukan, kompleksitas akan meningkat jauh melebihi kebutuhan.
    • Kita harus mendefinisikan dulu “sistem operasional yang tidak sepele”.
      Jika hanya dikatakan seperti itu, ini tidak membantah saran untuk menghindari kompleksitas yang tidak perlu. Intinya bukan apakah secara teknis terdistribusi, melainkan apakah benar-benar diperlukan.
      Mempelajari sistem terdistribusi berbeda dengan menggunakannya.
      Yang penting adalah apakah setelah mempelajarinya kita masih punya disiplin untuk menerapkannya hanya di tempat yang tepat.
      Saat ini sering ada banyak upaya untuk memindahkan sistem sederhana yang berjalan baik ke model terdistribusi yang lebih kuat, seolah-olah biayanya hampir nol.
      Namun jika melihat masalah dan skala yang ingin diselesaikan, jelas ada banyak kasus di mana satu instance Postgres dan monolith sudah cukup.
      Sepertinya saran di artikel aslinya bermakna seperti itu.
    • Di dalam gelembung HN mungkin benar, tetapi dari sudut pandang bisnis rata-rata sama sekali tidak demikian.
      Setidaknya, tidak harus begitu.
    • Sistem terdistribusi/redundan bukanlah backup.
      Saya tetap akan menyarankan memilih solusi yang sederhana.
      Banyak sistem bahkan gagal menyimpan, mencadangkan, dan memulihkan state persisten dengan benar pada “penyimpanan yang sepele dan sederhana”.
      Mencoba memulihkan state penyimpanan terdistribusi dalam situasi pemulihan bencana lebih sulit lagi.
      Miliki dulu solusi backup yang berfungsi, baru setelah itu mengadopsi solusi terdistribusi juga tidak masalah.
    • Failover replika sulit disebut sebagai sistem terdistribusi.
      Konfigurasi master dengan replika read-only juga berbeda dari “terdistribusi” yang biasanya orang maksud, karena penulisannya tidak terdistribusi.
      Dalam praktik, terdistribusi biasanya berarti data di-sharding, dan itu adalah bagian yang benar-benar ingin dihindari jika tidak benar-benar diperlukan.

  • Saya membacanya dengan senang karena artikel ini meninjau dengan baik berbagai konsep yang terkait saat membuat database.
    Cakupannya mulai dari SIMD untuk memeras performa dari satu mesin hingga algoritma konsensus.
    Karena sedang membahas database, reliabilitas, dan sistem terdistribusi, ada baiknya juga membaca tentang metode formal yang dapat diterapkan pada situasi seperti ini dan implementasi internal database.
    Ada makalah menarik dari tim S3 yang memodelkannya dengan TLA+.
    [0] Use of Formal Methods at Amazon Web Services
    https://lamport.azurewebsites.net/tla/formal-methods-amazon....
    [1] How Amazon Web Services uses formal methods
    https://www.amazon.science/publications/how-amazon-web-servi...

  • Ada konsistensi database dan konsistensi aplikasi dalam konsistensi.
    Misalnya, pada level satu tabel kita bisa mencapai atomicity, isolation, dan durability, tetapi bisa gagal pada penulisan yang melibatkan beberapa tabel.
    Konsistensi menjadi penting saat mulai menangani transaksi yang memperbarui beberapa tabel sekaligus.
    Semua tabel harus diperbarui secara bersamaan, atau tidak ada yang diperbarui sama sekali.

    • Contoh yang bagus, akan saya refleksikan di artikel.

  • Desain yang “memiliki API dokumen seperti MongoDB, leaderless replication seperti Cassandra, dan arsitektur thread-per-core seperti ScyllaDB” sangat keren.
    Ditambah lagi semuanya ditulis dalam Rust.

  • Tahap “buku-buku itu memicu rasa ingin tahu, lalu saya membuat database kecil sendiri” tampaknya pernah dilalui banyak developer setidaknya sekali
    Saya tidak akan berusaha mencegahnya. Dengan mencobanya sendiri, kita benar-benar belajar banyak tentang apa yang tidak berjalan
    Kalau bisa meluangkan waktu, itu pelajaran yang sangat berharga
    Pengalaman membuat database sendiri adalah hal yang paling menumbuhkan rasa hormat saya terhadap solusi-solusi yang sudah ada
    Menulis dan membaca byte ke/dari disk dengan cepat bukan bagian yang sulit
    Yang benar-benar sulit adalah membuatnya bekerja secara stabil selama bertahun-tahun sambil mendukung use case yang bahkan tidak pernah kita bayangkan

    • Saya sering bertanya-tanya seberapa besar kompleksitas DBMS modern berasal dari batasan yang muncul karena use case domain bisnis tertentu
      Efisiensi seperti apa yang bisa didapat jika kita merancang DBMS khusus domain dengan asumsi bahwa use case di luar domain boleh dilarang dan diabaikan?
      Misalnya, saat ini kita memakai database serbaguna bahkan untuk dataset yang pada dasarnya append-only
      Bagaimana kalau database sama sekali tidak punya konsep pembaruan atau penghapusan baris yang sudah ada, dan hanya memiliki insert serta penghapusan seluruh tabel/dataset?
      Apakah database seperti itu tidak perlu mengimplementasikan transaksi MVCC? Karena setiap tabel itu sendiri adalah write-ahead log, bisakah kita menghindari write-ahead log terpisah? Bisakah disimpan dengan lebih efisien? Bisakah indexing dibuat atomik per chunk, bukan atomik untuk seluruh tabel, sehingga mengurangi locking?

  • Bukankah atomicity versi Bash bisa dicapai “secara sederhana” dengan menyalin file ke file sementara, memodifikasinya, lalu memakai sync; mv; sync?

    • Saat menyalin, kita juga bisa menghindari duplikasi dengan filter grep terbalik
      Sekalian menyalin, mungkin sorting juga bisa dijamin, tetapi melakukannya hanya dengan “bash” dan utilitas dasar rasanya tidak terlalu masuk akal
      Untuk keperluan seperti itu ada CDB dari DJB, yaitu cdbget, cdbmake, dan lain-lain:
      https://cr.yp.to/cdb.html
    • Benar, akan saya tambahkan nanti

  • Tulisan yang bagus
    Buku Database Internals tampak bagus; apakah ada buku serupa lain yang membahas implementasi internal secara mendalam?

    • Bukan buku, tetapi saya merekomendasikan kuliah database dari grup @apavlo di CMU
      https://www.youtube.com/c/cmudatabasegroup
      Kelas pengantar dan lanjutan keduanya tersedia online, dan ada juga presentasi serta kuliah tentang produk industri
      Sangat berguna
      Untuk materi dari sudut pandang ilmu komputer teoretis yang lebih tinggi dan kurang berfokus pada implementasi fisik, buku “Alice”, yaitu “Foundations of Databases”, sangat bagus
      Sangat padat dan matematis, tetapi membahas aljabar relasional dan Datalog, serta cara mengubah Datalog menjadi aljabar relasional
      Buku cetaknya sekarang sulit didapat, dan buku bekas yang saya beli datang dengan jilid rusak dan halaman-halaman terlepas, tetapi seluruh bukunya tersedia online: http://webdam.inria.fr/Alice/
    • Ada juga materi terkenal yang berfokus pada Postgres: https://www.interdb.jp/pg/
    • Untuk gambaran umum dengan gaya serupa, paper ini bagus:
      https://dsf.berkeley.edu/papers/fntdb07-architecture.pdf
    • Buku Database Management Systems karya Raghu Ramakrishnan juga sangat berguna
      Namun Database Internals lebih modern

  • Saya suka tulisan ini karena tidak memistifikasi “database”, melainkan memulai dengan menunjukkan implementasi sepele berupa satu baris Bash
    Pembuka yang bagus