Wawancara Koding: Mengimplementasikan Penyimpanan Nilai Kunci Berversi Waktu (Time-Versioned Key-Value Store)

Petunjuk dan cakupan

Implementasikan struktur dalam memori dengan set(key, value, timestamp) dan get(key, timestamp). get mengembalikan versi terbaru untuk kunci tersebut yang stempel waktunya paling lambat sama dengan waktu kueri; fungsi ini mengembalikan kondisi tidak ditemukan (miss) yang eksplisit jika tidak ada versi yang cocok. Perjelas apakah stempel waktu bersifat monotonik per kunci, apakah stempel waktu yang sama saling menimpa, apakah operasi baca dan tulis berjalan bersamaan (konkuren), serta apakah penghapusan atau persistensi diperlukan. Intinya adalah mempertahankan invarian riwayat per kunci, bukan mengurutkan dan memindai setiap rekaman secara berulang.

Hal yang dievaluasi pewawancara

Jawaban yang kuat menargetkan pencarian sebesar O(log m), di mana m adalah jumlah versi untuk kunci tersebut, dan menjelaskan kompromi penulisan antara hanya menambahkan ke akhir (append-only) dan input yang tidak berurutan (out-of-order). Pewawancara akan menguji kunci kosong, kedua batas waktu, stempel waktu duplikat, nilai null, kunci yang tidak diketahui, dan perbedaan antara versi efektif terbaru dengan versi setelah waktu kueri. Klaim keamanan thread (thread-safety) harus mencakup granularitas penguncian dan semantik snapshot.

Pertanyaan klarifikasi sebelum menulis kode

1. Apakah stempel waktu bersifat monotonik per kunci? Jika ya, tambahkan ke akhir dan gunakan pemindaian mundur singkat atau pencarian biner; jika tidak, pertahankan urutan atau tolak penulisan yang tidak berurutan.
2. Apa arti stempel waktu yang sama? Untuk strategi pemenang penulisan terakhir (last-write-wins), pertahankan urutan yang meningkat secara monotonik sebagai penentu pemecah kesamaan (tie-breaker) yang stabil; jika tidak, tolak konflik tersebut.
3. Apakah nilai bisa berupa null? Jika ya, hasil yang tidak ditemukan (miss) tidak boleh direpresentasikan dengan null; kembalikan hasil dengan bendera found yang eksplisit.
4. Apakah konkurensi diperlukan? Selesaikan invarian berutas tunggal terlebih dahulu, lalu tentukan visibilitas dan pilih kunci per-kunci atau snapshot yang tidak dapat diubah (immutable).
5. Apakah riwayat tidak terbatas? Jendela retensi atau batas versi mengubah kebijakan penggusuran (eviction) dan arti dari kueri lama.

Kerangka jawaban 30 detik

“Saya menyimpan larik (array) versi yang diurutkan berdasarkan waktu untuk setiap kunci. get menggunakan upper_bound(timestamp) untuk menemukan versi pertama yang lebih besar dari kueri dan mengembalikan entri sebelumnya, sehingga pencarian bernilai O(log m). Jika operasi tulis tidak monotonik, saya menggunakan penyisipan terurut dan memperhitungkan biayanya; jika throughput tulis mendominasi, saya menambahkan ke log dan membangun indeks secara berkelompok (batch). Nomor urut membuat stempel waktu yang sama menjadi deterministik, dan hasil tidak ditemukan memiliki status eksplisit. Saya menguji kunci kosong, batas, operasi tulis tidak berurutan, dan stempel waktu duplikat.”

Solusi langkah demi langkah

Representasikan setiap rekaman sebagai (timestamp, sequence, value) dan jaga agar larik setiap kunci tidak menurun berdasarkan (timestamp, sequence). Untuk get(k, t), temukan posisi pertama i dengan timestamp > t. Jika i bernilai nol, tidak ada versi efektif; jika tidak, kembalikan records[i - 1]. Aturan batas atas ini mencakup penulisan yang tepat pada t.

Ketika stempel waktu bersifat monotonik per kunci, penambahan ke akhir memberikan O(1) teramortisasi untuk set dan O(log m) untuk get. Dengan stempel waktu yang tidak berurutan, mencari titik penyisipan bernilai logaritmik tetapi menggeser larik bernilai O(m) dalam kasus terburuk. Pohon seimbang menghindari pergeseran dengan mengorbankan alokasi memori dan overhead penunjuk yang lebih besar. Larik terurut global tunggal tidak benar karena batas kueri bersifat independen untuk setiap kunci.

Stempel waktu duplikat memerlukan aturan deterministik. Untuk last-write-wins, tetapkan urutan yang meningkat ke setiap panggilan dan urutkan berdasarkan (timestamp, sequence); batas atas hanya membandingkan stempel waktu, sehingga rekaman terakhir pada stempel waktu tersebut yang menang. Jika stempel waktu dapat melebihi rentang integer aman dalam bahasa pemrograman, gunakan tipe integer atau pembanding (comparator) yang sesuai alih-alih mengonversinya secara diam-diam ke floating point.

Untuk konkurensi, ekstensi terkecil mengunci satu kunci saat mengganti lariknya atau menjalankan pencarian biner. Agar operasi baca tetap non-blocking, operasi tulis dapat membuat larik baru yang tidak dapat diubah (immutable) dan mengganti referensinya secara atomik; pembaca melihat snapshot lama atau baru, tidak pernah melihat larik parsial. Persistensi menambahkan log, checksum, dan kursor pemulihan, dan hal ini sebaiknya dibahas hanya jika pewawancara memperluas cakupannya.

Contoh jawaban berkualitas tinggi

“Saya akan berasumsi bahwa stempel waktu dapat tiba secara tidak berurutan, stempel waktu yang sama menggunakan last-write-wins, dan versi pertama bersifat berutas tunggal (single-threaded). Setiap kunci dipetakan ke larik yang diurutkan berdasarkan (timestamp, sequence). get melakukan pencarian batas atas untuk stempel waktu pertama yang lebih besar dari kueri dan mengembalikan versi sebelumnya, menghasilkan pencarian O(log m) dan perilaku kesetaraan yang benar. Jika stempel waktu dijamin meningkat, set menjadi O(1) teramortisasi. Jika penulisan mendominasi pembacaan, saya akan menambahkan ke log dan membangun indeks secara asinkron. Pengujian mencakup kunci yang tidak diketahui, sebelum versi pertama, sama dengan versi pertama dan terakhir, setelah versi terakhir, penulisan tidak berurutan, stempel waktu duplikat, dan nilai null.”

Kesalahan umum

• Kesalahan → memindai secara linier untuk mencari versi terakhir; alasan gagal → pencarian menjadi O(m) dan memiliki skalabilitas buruk; perbaikan → pertahankan riwayat yang terurut dan gunakan pencarian batas atas (upper-bound search).
• Kesalahan → menggunakan timestamp < t; alasan gagal → penulisan tepat pada t terlewatkan; perbaikan → temukan timestamp > t pertama.
• Kesalahan → berasumsi semua penulisan selalu meningkat; alasan gagal → peristiwa yang tidak berurutan merusak invarian larik; perbaikan → nyatakan batasannya dan gunakan penyisipan terurut atau pohon (tree).
• Kesalahan → menggunakan null untuk hasil tidak ditemukan dan nilai yang disimpan; alasan gagal → pemanggil tidak dapat membedakan statusnya; perbaikan → kembalikan { found, value } atau tipe opsi yang eksplisit.
• Kesalahan → mengabaikan stempel waktu yang sama; alasan gagal → hasil bergantung pada urutan insidental; perbaikan → tambahkan urutan atau tolak konflik tersebut.

Respons tindak lanjut

Bagaimana Anda mengoptimalkannya jika stempel waktu dijamin selalu meningkat?

Tambahkan di akhir per kunci untuk penulisan dengan biaya teramortisasi O(1). Pertahankan pencarian biner untuk pembacaan O(log m) yang dapat diprediksi, atau pindai ke belakang hanya jika pola akses menunjukkan bahwa kueri biasanya mendekati versi terbaru. Jangan mengklaim pemindaian ke belakang membutuhkan waktu konstan pada kasus terburuk.

Bagaimana Anda hanya menyimpan 30 hari terakhir per kunci?

Tentukan apakah batas waktu menggunakan waktu peristiwa atau waktu layanan, lalu hapus awalan lama secara berkala sambil mempertahankan urutan. Kueri sebelum batas waktu harus mengembalikan "riwayat tidak tersedia", bukan menyamar sebagai kondisi tidak ditemukan biasa.

Apa yang berubah untuk pembaca dan penulis konkuren?

Tentukan titik linearisasi terlebih dahulu. Desain langsung menggunakan kunci baca-tulis (read-write lock) per kunci. Untuk pembacaan non-blocking, buat larik baru dan tukar referensinya secara atomik sehingga pembaca mengamati snapshot lama atau baru yang lengkap.

Bagaimana Anda melakukan persistensi dan pemulihan setelah kerusakan sistem (crash)?

Tambahkan ke log berurutan sebelum mengonfirmasi penulisan, buat snapshot indeks secara berkala, dan putar ulang akhiran log setelah pemulihan sambil memvalidasi nomor urut. Jangan menambahkan desain basis data lengkap jika instruksi hanya meminta solusi dalam memori.