Bangun dictionary berbasis file

Pertanyaan

Bagaimana menyimpan pasangan key-value di satu file supaya bisa dibaca lagi setelah proses restart, termasuk saat ujung file rusak?

Setelah baca ini, kamu bisa merancang format record, indeks offset, checksum, dan header versi, lalu menjelaskan apa yang terjadi saat file dibuka ulang.

Prasyarat dan contoh

Kamu paham indeks dan akses berdasarkan key (M04), serta ide dasar transaksi dan atomisitas (M05). Replikasi dari M08 cukup sebagai latar: di sini kita hanya bicara satu mesin.

Bayangkan layanan konfigurasi kecil: 2 juta key, tiap value rata-rata 200 byte. Kamu menulis HashMap di memori dan membuangnya ke JSON tiap menit. Kalau proses mati di menit ke-0,9, semua perubahan menit itu hilang. Kalau mati di tengah penulisan JSON, file bisa setengah jadi dan nggak bisa di-parse sama sekali.

Dictionary berbasis file memperbaiki dua hal itu sekaligus: perubahan ditulis sebagai record kecil yang bisa divalidasi satu per satu, dan data lama nggak ditimpa.

Mekanisme

1. Bingkai record. Disk hanya menyimpan byte, jadi kamu harus menentukan di mana record berhenti. Format yang umum dipakai:

[crc32: 4 B][key_len: 4 B][val_len: 4 B][flags: 1 B][key][value]

Header 13 byte. Untuk key 16 byte dan value 200 byte, satu record makan 229 byte. flags menandai jenis record, misalnya 0 = put dan 1 = delete. CRC dihitung atas semua byte setelah field CRC itu sendiri.

2. Append-only. Update dan delete tetap ditulis sebagai record baru di ujung file. Record lama nggak disentuh. Alasannya: penulisan sekuensial murah, dan ujung file adalah satu-satunya tempat yang mungkin rusak kalau proses mati.

3. Indeks di memori. Untuk baca cepat, simpan key -> (file_id, offset, panjang). Satu pembacaan = satu lookup hash + satu pread. Dengan 2 juta key, tiap entri kira-kira 16 byte key + 16 byte penunjuk + overhead struktur, sekitar 60-80 byte, jadi total 120-160 MB. Ini harga yang kamu bayar: seluruh key harus muat di RAM.

4. Bangun ulang indeks saat startup. Indeks nggak ikut disimpan. Saat dibuka, baca file dari awal, validasi tiap record, dan tulis ulang entrinya. Record terakhir untuk sebuah key menang. File 500 MB yang dibaca sekuensial dengan 500 MB/s butuh sekitar 1 detik, tapi pada 50 GB itu jadi 100 detik. Itu alasan nanti orang menambah hint file atau snapshot indeks.

5. Header file dan versi format. Awali file dengan header tetap, misalnya magic (4 B) + format_version (2 B) + flags (2 B). Magic mencegah kamu membuka file yang bukan miliknya. Versi memungkinkan kode baru menolak, atau membaca dengan jalur khusus, format lama. Tanpa versi, mengubah satu field dari 4 byte menjadi 8 byte berarti semua file lama jadi sampah diam-diam.

6. Tangani ujung yang rusak. Saat replay, kalau header record terpotong, atau panjangnya melewati akhir file, atau CRC nggak cocok, berhenti di situ. Anggap offset record itu sebagai akhir file yang valid, lalu potong (truncate) file ke sana sebelum menulis lagi. Kalau kamu lanjut menulis di atas ekor rusak, record baru bakal ikut tak terbaca.

Saat rancangan ini gagal

• Indeks nggak muat. 2 miliar key dengan 70 byte per entri butuh sekitar 140 GB RAM. Desain ini berhenti di sana. Jalan keluarnya indeks yang sebagian ada di disk (lihat M09.04), bukan menambah RAM tanpa batas.
• File tumbuh tanpa henti. Karena append-only, key yang di-update 1.000 kali menyimpan 1.000 versi. Tanpa pembersihan (compaction, M09.05), disk habis walau data hidup cuma 1 GB.
• CRC bukan jaminan keamanan. CRC32 mendeteksi kerusakan acak, bukan manipulasi. Untuk data yang bisa diserang, pakai MAC atau hash kriptografis.
• Record yang melewati batas halaman. Penulisan 229 byte bisa terpecah di dua sektor dan hanya separuhnya sampai ke disk. CRC-lah yang menangkap ini, bukan "ukuran kecil pasti atomik".
• Contoh tandingan: tim menyimpan val_len tanpa CRC "karena disk modern dapat ECC". Setelah crash, record terpotong dengan val_len valid tapi isi nol terbaca sebagai value sah. ECC disk melindungi sektor yang sudah ditulis, bukan penulisan yang setengah jadi.

Latihan

Kamu punya file dengan header 8 byte, lalu tiga record put berturut-turut. Format record seperti di atas (header 13 byte). Record A: key a (1 B), value 100 B. Record B: key b, value 50 B. Record C: key a, value 80 B. File berakhir 20 byte setelah record C dimulai karena crash.

1. Hitung offset awal tiap record dan isi indeks setelah replay.
2. Setelah record C yang utuh, ada record D yang terpotong. Apa langkah startup?

Lihat pembahasan+

Offset. Record A mulai di 8, panjangnya 13 + 1 + 100 = 114, jadi berakhir di 122. Record B mulai di 122, panjang 13 + 1 + 50 = 64, berakhir di 186. Record C mulai di 186, panjang 13 + 1 + 80 = 94, berakhir di 280.

Indeks setelah replay: a -> offset 186 (C menimpa A), b -> offset 122. Record A masih ada di file, tapi sudah jadi sampah yang menunggu compaction.

Record D terpotong. Dimulai di offset 280. Dengan hanya 20 byte tersisa, header 13 byte terbaca, tapi val_len bisa jadi menunjuk melewati akhir file, atau CRC nggak cocok. Replay berhenti di 280, file di-truncate ke 280, dan penulisan berikutnya mulai dari sana. Tulisan D nggak pernah dianggap sukses, jadi klien yang belum menerima konfirmasi harus mengulang, bukan berasumsi D tersimpan.

Terkait

• Lanjut ke M09.02 Pulihkan sistem setelah crash untuk urutan penulisan dan asumsi fsync.
• M09.03 Bandingkan struktur penyimpanan menempatkan desain ini sebagai varian log append-only.
• Pelajari indeks di M04 dan atomisitas di M05 untuk konteks. Lab L09 dan proyek B05 belum tersedia.

Catatan

• Asumsi: satu proses penulis, satu mesin, filesystem lokal. Nggak ada akses konkuren antar-proses.
• Ukuran memori adalah estimasi kasar dan bergantung pada bahasa dan struktur hash yang dipakai.
• Yang nggak dibahas: kompresi, enkripsi, dan format dengan blok berukuran tetap.
• Ini pola umum yang dipakai banyak mesin log-structured, bukan kutipan satu sumber.
• Terakhir ditinjau: 26 Oktober 2026.