Telusuri proses baca/tulis LSM

Pertanyaan

Apa yang terjadi pada satu put dan satu get di mesin LSM, dan di mana tiap langkah bisa lambat atau gagal?

Setelah baca ini, kamu bisa menelusuri jalur tulis dan baca, menghitung jumlah file yang diperiksa, dan memperkirakan efek Bloom filter.

Prasyarat dan contoh

Kamu sudah baca M09.02 Pulihkan sistem setelah crash dan M09.03 Bandingkan struktur penyimpanan. WAL dan perbandingan dengan B-tree dianggap sudah kamu pahami.

Layanan menerima 30.000 tulis per detik, value 200 B, dengan 2 miliar key. Bitcask nggak muat di RAM (M09.03), B-tree membuat tulis acak. LSM (log-structured merge-tree) menyerap tulis di memori dan menuliskannya ke disk sebagai file terurut yang nggak pernah diubah.

Mekanisme

Jalur tulis.

1. Tambahkan record ke WAL dan fsync sesuai kontrak (M09.02). Ini yang membuat tulis tahan crash.
2. Masukkan ke memtable, struktur terurut di memori (skip list atau pohon), misalnya 64 MB.
3. Balas klien.
4. Saat memtable penuh, bekukan jadi immutable memtable, buat memtable baru, dan flush yang beku ke disk sebagai SSTable. Setelah flush selesai dan tahan, WAL segmen itu boleh dibuang.

Pada 30.000 x 200 B = 6 MB per detik, memtable 64 MB penuh sekitar tiap 10 detik. Tiap flush menghasilkan satu file 64 MB (sebelum kompresi). Semua penulisan ke disk sekuensial.

SSTable. File terurut berdasarkan key, tersusun dari blok (misalnya 4 KB) yang berisi banyak record, plus:

• Indeks sparse: satu entri per blok, key pertama blok -> offset. File 64 MB berisi 16.384 blok 4 KB, jadi indeksnya hanya 16.384 entri (sekitar 500 KB). Cari key dengan binary search di indeks, lalu baca satu blok.
• Bloom filter: struktur probabilistik yang menjawab "key ini pasti tidak ada" atau "mungkin ada". Dengan 10 bit per key, false positive sekitar 1%. Tidak pernah false negative.
• Footer berisi posisi indeks dan filter, serta versi format.

Jalur baca. Periksa dari yang terbaru ke terlama:

1. Memtable.
2. Immutable memtable (kalau ada).
3. SSTable, dari yang terbaru. Untuk tiap file: tanya Bloom filter. Kalau "pasti tidak ada", lewati. Kalau "mungkin", cari di indeks sparse, baca satu blok, cek key.

Hasil pertama yang ditemukan menang, karena yang lebih baru menutupi yang lama. Delete ditulis sebagai tombstone dan juga menutupi (M09.05).

Efek Bloom filter. Misal ada 8 SSTable yang tumpang tindih dan key yang dicari nggak ada. Tanpa filter: 8 pembacaan blok. Dengan filter 1% false positive: rata-rata 8 x 0,01 = 0,08 pembacaan. Untuk key yang ada di file tertua, filter tetap mencegah pembacaan di 7 file lain (ditambah sekitar 0,07 kesalahan). Filter menukar memori (10 bit per key, jadi 2 miliar key = sekitar 2,5 GB) dengan I/O.

Mengapa file terurut penting. Karena SSTable terurut, menggabungkan dua file cukup dengan merge sekuensial, dan scan rentang cuma membaca blok berurutan. Memtable yang terurut itulah yang menghasilkan file terurut tanpa tulis acak.

Saat rancangan ini gagal

• Flush lebih lambat dari tulis masuk. Memtable beku menumpuk. Mesin harus memperlambat atau menolak tulis (write stall) sebelum RAM habis.
• Terlalu banyak SSTable. Tanpa compaction, 200 file tumpang tindih berarti baca menyentuh banyak filter dan, pada false positive, banyak blok. Latensi p99 naik jauh lebih dulu dibanding p50.
• Filter tidak membantu scan rentang. Bloom filter menjawab keanggotaan satu key, bukan "ada key dalam rentang ini?". Scan tetap menyentuh semua file yang tumpang tindih (kecuali ada filter prefix).
• Bloom filter di luar RAM. Kalau filter nggak muat dan harus dibaca dari disk, kamu menambah I/O alih-alih menghemat.
• Contoh tandingan: tim memasang filter dan mengira baca key yang ada jadi O(1) I/O. Key yang ada di level terdalam tetap harus melewati semua file di atasnya, dan tiap false positive menambah satu blok.

Latihan

Ada memtable dan 6 SSTable yang tumpang tindih. Tiap filter 10 bit per key (false positive 1%). Satu get untuk key yang nggak ada, lalu get untuk key yang ada hanya di SSTable tertua. Blok 4 KB dibaca penuh.

1. Berapa perkiraan jumlah blok dibaca untuk key yang nggak ada, dengan dan tanpa filter?
2. Untuk key yang ada di SSTable tertua?
3. Memtable 64 MB, tulis 8 MB per detik. Berapa lama sampai flush, dan berapa file per jam?

Lihat pembahasan+

1. Tanpa filter: 6 blok (satu per SSTable). Dengan filter: 6 x 0,01 = 0,06 blok rata-rata. Memtable diperiksa di memori, tanpa I/O.
2. Key ada di file tertua, jadi 5 file lebih baru dilewati oleh filter (5 x 0,01 = 0,05 blok palsu) dan 1 blok asli dibaca. Total sekitar 1,05 blok. Tanpa filter, hingga 6.
3. 64 / 8 = 8 detik per flush, jadi 3.600 / 8 = 450 file per jam (sebelum compaction). Itu menunjukkan kenapa compaction wajib: tanpa itu, jumlah file bertambah ratusan per jam dan jalur baca ikut membengkak.

Terkait

• Sebelumnya: M09.03 Bandingkan struktur penyimpanan.
• Lanjut ke M09.05 Perhitungkan compaction.
• Struktur probabilistik seperti Bloom filter dibahas lebih luas di M12. Studi kasus C06 dan lab L09 belum tersedia.

Catatan

• Asumsi: memtable 64 MB, blok 4 KB, Bloom filter 10 bit per key, satu level pembacaan per file untuk penyederhanaan.
• Yang nggak dibahas: kompresi blok, block cache, filter yang dipartisi, dan multi-version concurrency.
• Pola ini umum pada LevelDB, RocksDB, dan Cassandra, tapi detail tiap mesin berbeda.
• Terakhir ditinjau: 26 Oktober 2026.