Wawancara Coding: Mengimplementasikan TTL Cache dengan Kedaluwarsa

Pertanyaan dan kapan ini berlaku

Implementasikan cache dalam memori di mana setiap kunci memiliki nilai dan waktu kedaluwarsa. get tidak boleh mengembalikan nilai yang sudah kedaluwarsa. Jelaskan jam, batas, pembersihan, kapasitas, konkurensi, dan kompleksitas.

Amazon mencantumkan struktur data, algoritma, dan coding di antara topik wawancara pengembangan perangkat lunak serta menekankan penerapan pengetahuan. Redis mendokumentasikan semantik TTL dan EXPIRE, termasuk sisa masa aktif dan presisi. Tidak seperti LRU atau LFU, masalah ini berpusat pada semantik waktu dan pembersihan kedaluwarsa.

Apa yang dinilai oleh pewawancara

Pewawancara mencari unit TTL dan jam yang eksplisit, batas kedaluwarsa yang tepat, pilihan pembersihan, konsistensi konkuren, perilaku kapasitas, serta kompleksitas waktu dan ruang.

Pertanyaan untuk diklarifikasi sebelum menjawab

• Apakah TTL dalam detik atau milidetik? Apakah nol kedaluwarsa seketika?
• Apakah jamnya monotonik (monotonic)?
• Haruskah entri yang kedaluwarsa segera dihapus?
• Apakah ada kapasitas maksimum atau kebijakan LRU?
• Bagaimana set, get, dan pembersihan disinkronkan?
• Apakah memperbarui kunci akan menyetel ulang TTL?
• Apakah persistensi atau pembagian lintas-proses diperlukan?
• Haruskah beban kerja pembersihan dibatasi (bounded)?

Kerangka jawaban 30 detik

“Saya menyimpan nilai setiap kunci dan expiresAt absolut dalam tabel hash. get memeriksa jam monotonik terlebih dahulu; jika now sama dengan atau setelah expiresAt, get akan menghapus entri dan mengembalikan miss. set menggantikan nilai dan TTL. Versi dasar menggunakan pembersihan malas (lazy) dengan get O(1) teramortisasi dan ruang O(n). Min-heap atau pemindaian terbatas menangani entri dingin (cold). Kunci (locks) atau sharding melindungi pembaruan hash dan pembersihan. Pengujian mencakup TTL nol, kesetaraan batas, pembaruan (refresh), dan race condition.”

Jawaban mendalam, langkah demi langkah

Langkah 1: Definisikan item

Simpan value dan expiresAt; tidak ada TTL yang boleh menggunakan tak hingga. Gunakan satu aturan, now >= expiresAt, pada setiap jalur.

Langkah 2: Implementasikan get dan set

get mengembalikan miss untuk kunci yang tidak ada. Untuk kunci yang kedaluwarsa, get menghapusnya sebelum mengembalikan miss. set menghitung kedaluwarsa absolut dan memperbarui indeks pembersihan apa pun.

Langkah 3: Pilih jam

Gunakan jam monotonik untuk waktu yang telah berlalu sehingga penyesuaian jam dinding (wall-clock) tidak dapat memperpanjang TTL. Desain persistensi dan lintas-proses memerlukan basis waktu dan presisi yang eksplisit.

Langkah 4: Pilih pembersihan

Pembersihan malas (lazy cleanup) itu sederhana tetapi kunci dingin dapat memakan memori. Min-heap mengeluarkan kedaluwarsa paling awal terlebih dahulu; pemindaian berkala membatasi beban kerja tetapi dapat menunda penghapusan.

Langkah 5: Buat pembaruan aman secara konkuren

set, get, delete, dan pembersihan harus menyepakati nilai dan kedaluwarsa yang sama. Gunakan kunci global, kunci baca-tulis, atau sharded locks. Pembaruan heap dan tabel harus atomik secara bersamaan.

Langkah 6: Pisahkan kapasitas dari TTL

TTL tidak menentukan kapasitas. Pada batas kapasitas, pilih LRU, pengeluaran acak (random eviction), atau tolak penulisan. Lacak pengeluaran secara terpisah dari kedaluwarsa.

Langkah 7: Nyatakan kompleksitas dan pseudocode

Batas intinya adalah:

get(key):
  item = table[key]
  if item is absent: return MISS
  if clock.now() >= item.expiresAt:
    delete table[key]
    return MISS
  return item.value

get dan set malas memiliki kompleksitas O(1) teramortisasi, ruang O(n). Operasi pop pada pembersihan heap membutuhkan biaya O(log n).

Langkah 8: Uji batas-batas kasus

Uji TTL nol, kesetaraan batas, pembaruan (refresh), pembersihan berulang, perubahan jam, get/set konkuren, pengeluaran kapasitas, dan injeksi kegagalan. Injeksikan jam daripada menggunakan sleep dalam pengujian.

Contoh jawaban berkualitas tinggi

“Saya mendefinisikan CacheItem(value, expiresAt) dan menyimpan item dalam tabel hash. set mengubah TTL menjadi kedaluwarsa absolut; nol berarti langsung kedaluwarsa. get memeriksa jam monotonik dan menghapus sebelum mengembalikan miss.

Versi pertama menggunakan pembersihan malas, dengan pembacaan dan penulisan O(1) teramortisasi. Untuk banyak kunci dingin, saya menambahkan min-heap. Setiap rekaman heap memiliki versi; pembersihan memvalidasi versi sebelum menghapus, sehingga rekaman lama tidak dapat menghapus nilai yang telah diperbarui. Sharded locks melindungi tabel dan heap. Pengujian mencakup kesetaraan batas, pembaruan, pembersihan berulang, race condition, dan pengeluaran kapasitas.”

Kesalahan umum

• Membiarkan TTL nol dan kesetaraan batas tidak terdefinisi.
• Menggunakan waktu jam dinding (wall-clock) untuk TTL yang berlalu.
• Membiarkan get mengembalikan nilai yang kedaluwarsa hingga pekerja latar belakang (background worker) berjalan.
• Mengabaikan rekaman heap yang usang setelah pembaruan (refresh).
• Memperlakukan TTL sebagai kebijakan kapasitas LRU.
• Menahan kunci global selama proses pembersihan yang panjang.
• Hanya menguji hit dan miss, bukan race condition pada kondisi batas.
• Menghilangkan presisi dan kompleksitas.

Pertanyaan lanjutan dan cara menjawab

Pertanyaan lanjutan 1: Mengapa kedaluwarsa absolut?

Ini memberikan satu aturan perbandingan dan memungkinkan pembersihan mengurutkan entri berdasarkan kedaluwarsa. Pembaruan (refresh) menggantikan expiresAt.

Pertanyaan lanjutan 2: Bagaimana jika jam dinding mundur?

Gunakan jam monotonik untuk waktu yang berlalu. Cache persisten atau terdistribusi membutuhkan basis waktu yang terdokumentasi.

Pertanyaan lanjutan 3: Tidak ada thread latar belakang, tetapi banyak kunci dingin?

Lakukan pembersihan terbatas selama operasi baca atau tulis, seperti jumlah pop heap yang tetap per operasi, dan terima penundaan penghapusan yang terbatas.

Pertanyaan lanjutan 4: Bagaimana Anda menjaga konsistensi heap dan tabel?

Gunakan satu kunci atau operasi atomik dan sertakan versi pada rekaman heap. Hapus hanya jika versinya masih cocok.

Pertanyaan lanjutan 5: Apa yang terjadi saat kapasitas penuh?

Hapus entri yang kedaluwarsa terlebih dahulu, lalu terapkan kebijakan pengeluaran (eviction) yang terdokumentasi pada entri yang masih aktif dan catat alasannya.

Pertanyaan lanjutan 6: Bagaimana beberapa proses membagikannya?

Cache dalam memori hanya untuk proses tunggal. Penggunaan lintas-proses memerlukan penyimpanan eksternal atau terdistribusi dengan semantik TTL, jam, dan kegagalan yang atomik.