Bandingkan struktur penyimpanan

Pertanyaan

Untuk beban kerja tertentu, struktur penyimpanan mana yang paling murah di baca, tulis, memori, dan pemulihan?

Setelah baca ini, kamu bisa menghitung perkiraan I/O per operasi untuk B-tree, log append-only, dan Bitcask, lalu memilih berdasarkan pola akses, bukan reputasi.

Prasyarat dan contoh

Kamu sudah baca M09.01 Bangun dictionary berbasis file dan M09.02 Pulihkan sistem setelah crash. Kamu juga paham indeks B-tree dari sisi pemakai (M04).

Dua layanan. Layanan A menyimpan profil pengguna: 100 juta baris, 90% baca, tulis acak. Layanan B menyimpan event sensor: 50.000 tulis per detik, hampir semua baca hanya mengambil key yang baru ditulis. Struktur yang cocok untuk A kemungkinan buruk untuk B, dan sebaliknya.

Mekanisme

1. B-tree berbasis halaman. Data dibagi jadi halaman tetap (umumnya 4-16 KB) yang tersusun sebagai pohon. Update dilakukan di tempat: baca halaman, ubah, tulis balik.

• Fanout: halaman 16 KB dengan entri sekitar 24 byte (key 16 B + penunjuk 8 B) memuat sekitar 600 entri. Dengan fanout 500, tiga tingkat mencakup 125 juta entri dan empat tingkat 62,5 miliar. Jadi 100 juta key butuh sekitar 3-4 tingkat, dan tingkat atas hampir selalu di cache. Baca biasanya 1 I/O disk.
• Tulis: mengubah 100 byte berarti menulis ulang satu halaman 16 KB (write amplification sekitar 160x pada level halaman), ditambah satu record WAL. Halaman yang penuh harus dipecah dan memicu penulisan beberapa halaman.
• Butuh WAL, karena crash di tengah update halaman bisa meninggalkan halaman setengah tertulis (torn page).
• Range scan bagus: key terurut dan berdekatan di halaman.

2. Log append-only dengan indeks. Semua tulis ditambahkan di ujung log. Tulis murah: sekuensial, sekitar ukuran record plus header. Baca butuh cara menemukan record. Tanpa indeks, baca = scan seluruh log. Dengan indeks hash di memori, baca = satu seek. Pembersihan data lama butuh compaction (M09.05).

3. Direktori key bergaya Bitcask. Ini log append-only (M09.01) dengan seluruh keydir di RAM: key -> (file, offset, ukuran).

• Baca: satu lookup memori + satu pread. Latensi stabil, tanpa pohon.
• Tulis: satu append sekuensial, update keydir.
• Memori: 100 juta key x sekitar 70 byte = sekitar 7 GB hanya untuk indeks. Value boleh sebesar apa pun, tapi key harus muat.
• Startup: replay seluruh data, kecuali ada hint file (isi key + offset tanpa value) yang jauh lebih kecil.
• Range scan buruk: hash nggak menyimpan urutan.

4. Tabel ringkas. Kira-kira untuk satu operasi:

| Struktur | Baca titik | Tulis | Range scan | Memori | | --- | --- | --- | --- | --- | | B-tree | 1 I/O (tingkat atas di cache) | 1 halaman + WAL, acak | Baik | Sedang (cache) | | Bitcask | 1 I/O | 1 append | Buruk | Semua key | | LSM (M09.04) | Beberapa, dibantu filter | 1 append + flush | Baik | Filter + indeks |

5. Pilih dari beban kerja. Layanan A: baca dominan, tulis acak, mungkin perlu range scan: B-tree. Layanan B: 50.000 tulis per detik, key sensor 20 juta, nilai kecil: Bitcask kalau key muat di RAM (20 juta x 70 B = 1,4 GB), atau LSM kalau tidak.

Saat rancangan ini gagal

• B-tree dengan tulis acak intens. SSD dengan banyak tulis halaman kecil menghabiskan umur dan throughput. 20.000 update per detik x 16 KB = 320 MB per detik tulis hanya untuk data, belum WAL.
• Bitcask saat key tumbuh. Begitu keydir melewati RAM, OS mulai swap dan latensi baca runtuh. Cek angka ini sebelum memilihnya, bukan setelahnya.
• Log tanpa compaction. Disk penuh oleh versi lama. Pembersihan yang nggak dikendalikan juga bisa menyaingi trafik pengguna.
• Fragmentasi B-tree. Setelah banyak split dan delete, halaman terisi separuh. Ukuran file bisa 1,5-2x data hidup.
• Contoh tandingan: tim memilih Bitcask untuk katalog produk "karena baca satu seek", lalu produk minta pencarian key LIKE 'sepatu-%'. Hash nggak bisa menjawabnya tanpa scan penuh.

Latihan

Tiga beban kerja: (1) 5 juta key sesi pengguna, 80% baca, value 300 B, tanpa scan, RAM 8 GB. (2) 2 miliar key, tulis 20.000/detik, value 200 B, butuh scan prefix, RAM 64 GB. (3) Katalog 10 juta produk, baca dominan, butuh scan terurut per kategori.

Pilih satu struktur untuk tiap beban kerja dan beri satu alasan berangka.

Lihat pembahasan+

1. Bitcask. Keydir 5 juta x 70 B = 350 MB, sangat muat di 8 GB. Baca satu seek, tulis sekuensial, tanpa kebutuhan scan.
2. Bukan Bitcask: 2 miliar x 70 B = 140 GB, melewati RAM 64 GB. Dan B-tree dengan 20.000 tulis acak per detik x 16 KB = 320 MB/s tulis halaman. Pilihan yang masuk akal LSM (M09.04): tulis sekuensial, scan prefix lewat urutan terurut.
3. B-tree. Baca dominan, scan terurut per kategori, 10 juta key hanya 3 tingkat dan sebagian besar di cache. Tulis jarang, jadi biaya write amplification-nya kecil.

Jawaban benar harus menyebut angka yang membatalkan opsi lain, bukan hanya preferensi.

Terkait

• Sebelumnya: M09.02 Pulihkan sistem setelah crash.
• Lanjut ke M09.04 Telusuri proses baca/tulis LSM.
• Pilihan indeks di basis data relasional dibahas di M04. Studi kasus C06 dan lab L09 belum tersedia.

Catatan

• Asumsi: halaman 16 KB, entri 24 byte, overhead memori per key 70 byte. Semua perkiraan kasar, ukur di datamu.
• Yang nggak dibahas: B+tree vs B-tree murni, copy-on-write tree, dan struktur fractal.
• Bitcask dipakai sebagai nama pola dari desain Riak, bukan klaim tentang versi tertentu.
• Terakhir ditinjau: 26 Oktober 2026.