Wawancara coding: Mengimplementasikan request coalescing per kunci (singleflight)

Petunjuk dan konteks

Implementasikan helper asinkron yang aman terhadap konkurensi, coalesce(key, task). Paling banyak satu task dapat berjalan untuk key tertentu pada satu waktu. Pemanggil konkuren dengan kunci yang sama harus menunggu (await) dan menerima nilai atau error yang persis sama; kunci yang berbeda harus berjalan secara independen.

Tugas dapat melempar error secara sinkron atau menolak (reject) secara asinkron. Pemanggil dapat mengatur batas waktu tunggu mereka sendiri. Entri harus dihapus setelah keberhasilan maupun kegagalan sehingga panggilan berikutnya dapat mencoba lagi. Jelaskan semantik pembatalan, penyebaran error, dan pengujian.

Apa yang sedang diuji oleh pewawancara

Intinya adalah mengubah deduplikasi menjadi invarian konkurensi yang dapat dibuktikan: pasang promise bersama sebelum memulai pekerjaan asinkron, hapus hanya jika map masih menunjuk ke entri tersebut, dan jaga agar kunci tetap independen. Pewawancara juga ingin Anda membedakan antara satu pemanggil yang membatalkan tunggunya dengan membatalkan pekerjaan bersama, serta mengatasi pertumbuhan memori yang tak terbatas.

Pertanyaan klarifikasi

1. Apakah kunci harus tidak kosong atau dinormalisasi? Saya akan menolak kunci kosong agar permintaan yang tidak terkait tidak tergabung secara tidak sengaja.
2. Apakah batas waktu pemanggil harus membatalkan pekerjaan di hulu (upstream)? Secara default, ini hanya menghentikan tunggu pemanggil tersebut dan membiarkan pekerjaan bersama tetap berjalan untuk penunggu lainnya.
3. Apakah error harus di-cache? Tidak. Hapus setelah penyelesaian (settlement) agar panggilan berikutnya mencoba lagi.
4. Apakah penggabungan lintas-proses diperlukan? Tidak; petunjuk ini adalah memori proses tunggal. Koordinasi lintas-proses adalah rancangan terpisah.

Jawaban 30 detik

Saya menyimpan pekerjaan in-flight dalam Map<key, Entry>. Saat masuk, kembalikan promise yang ada jika terjadi hit. Jika miss, buat promise, masukkan ke dalam map sebelum melakukan await, lalu jalankan tugas. Dalam finally, hapus hanya jika map masih berisi entri yang sama. Pemanggil dengan kunci yang sama berbagi satu eksekusi, kunci yang berbeda tidak saling memblokir, dan kegagalan melepaskan status untuk percobaan ulang. Batas waktu pemanggil bersaing dengan waktu tunggunya tanpa membatalkan pekerjaan bersama. Pengujian mencakup panggilan duplikat, kunci independen, lemparan sinkron, penolakan dan percobaan ulang, serta race condition pada pembersihan.

Pembahasan mendalam langkah demi langkah

Definisikan Entry yang dapat menampung promise bersama dan, jika diperlukan, controller internal. Urutannya adalah bagian yang penting:

const inFlight = new Map<string, Promise<unknown>>();

function coalesce<T>(key: string, task: () => Promise<T>): Promise<T> {
  if (!key) return Promise.reject(new Error("key must not be empty"));
  const existing = inFlight.get(key);
  if (existing) return existing as Promise<T>;

  let shared: Promise<T>;
  try {
    shared = Promise.resolve().then(task);
  } catch (error) {
    shared = Promise.reject(error);
  }
  inFlight.set(key, shared);
  shared.finally(() => {
    if (inFlight.get(key) === shared) inFlight.delete(key);
  }).catch(() => undefined);
  return shared;
}

Entri objek dapat secara tambahan mencatat waktu mulai, jumlah penunggu, dan AbortController. Promise.resolve().then(task) membuat lemparan sinkron dan penolakan asinkron mengikuti satu jalur yang sama. Penyisipan map harus terjadi sebelum await pertama; jika tidak, dua putaran event loop dapat mengamati kondisi miss secara bersamaan. Pemeriksaan identitas mencegah finally tugas lama menghapus entri yang lebih baru.

Batas waktu pemanggil adalah kebijakan luar:

function waitWithTimeout<T>(shared: Promise<T>, ms: number): Promise<T> {
  return Promise.race([
    shared,
    new Promise<T>((_, reject) =>
      setTimeout(() => reject(new Error("wait timeout")), ms),
    ),
  ]);
}

Tugas bersama masih selesai untuk penunggu lainnya. Jika produk memerlukan pembatalan ketika semua pemanggil pergi, tambahkan penghitungan referensi dan definisikan race condition tersebut secara eksplisit dalam kontrak dan pengujian.

Operasi map yang diharapkan adalah O(1). Dengan K kunci in-flight yang berbeda, statusnya adalah O(K); menyampaikan satu hasil membutuhkan biaya yang sebanding dengan jumlah penunggu. Kode produksi harus membatasi kardinalitas kunci dan mengekspos metrik durasi, timeout, jumlah penunggu, dan error sehingga map tidak menjadi cache yang tidak terbatas.

Contoh jawaban berkualitas tinggi

Saya akan menyatakan batasannya terlebih dahulu: proses tunggal, hanya deduplikasi in-flight, tanpa cache hasil. Map menyimpan setiap entri. Saat miss, saya segera membuat dan mendaftarkan promise, lalu memanggil tugas pengguna. Setiap pemanggil menerima promise yang sama, sehingga nilai dan error-nya identik. Pembersihan membandingkan identitas objek, mencegah penyelesaian lama menghapus generasi yang lebih baru.

Pembatalan berarti “batalkan proses menunggu, bukan pekerjaan bersama”: satu pemanggil yang kehabisan batas waktu tidak mengirimkan AbortError ke penunggu lain atau mengganggu satu-satunya operasi di hulu. Jika pembatalan sebenarnya diperlukan, saya akan menggunakan controller bersama ditambah penghitungan referensi penunggu dan membatalkan hanya ketika hitungan mencapai nol.

Untuk pengujian, saya menggunakan barrier untuk melepaskan pemanggil simultan dan memastikan satu pemanggilan tugas dan satu hasil bersama. Saya juga menguji kunci independen secara paralel, lemparan sinkron, penolakan asinkron, percobaan ulang setelah kegagalan, tugas baru setelah keberhasilan, finally lama yang bersaing dengan entri baru, dan satu pemanggil yang kehabisan batas waktu sementara yang lain masih berhasil. Saya akan mengakhirinya dengan batas kapasitas dan metrik untuk kunci berkardinalitas tinggi.

Kesalahan umum

• Menunggu (await) task() sebelum memasukkan ke dalam map, yang memungkinkan eksekusi duplikat.
• Menghapus tanpa syarat berdasarkan kunci dalam finally, memungkinkan tugas lama menghapus entri yang lebih baru.
• Meneruskan AbortSignal milik satu pemanggil langsung ke pekerjaan bersama dan membatalkan setiap penunggu.
• Menyimpan promise yang ditolak selamanya alih-alih menghapusnya untuk percobaan ulang.
• Menggunakan satu kunci global dan membuat kunci yang tidak terkait menjadi serial.
• Hanya menguji panggilan berurutan alih-alih kedatangan simultan, lemparan sinkron, dan race condition pembersihan.

Pertanyaan lanjutan dan jawaban

Bagaimana Anda mendukung pembatalan sebenarnya?

Kapan penggabungan lintas-proses diperlukan?

Bagaimana Anda mencegah kebocoran kunci berkardinalitas tinggi?

Pembatalan sebenarnya membutuhkan controller bersama, penghitungan referensi, dan kebijakan nol-penunggu yang eksplisit. Kasus lintas-proses memerlukan Redis, gateway, atau koordinator lain ditambah lease, penanganan kegagalan leader, dan toleransi eksekusi duplikat. Kunci berkardinalitas tinggi memerlukan batas kapasitas, TTL atau kebijakan penggusuran (eviction), perilaku penolakan, dan metrik; kontrol ini harus mempertahankan aturan inti bahwa hanya pekerjaan in-flight yang disimpan.