Temu duga pengekodan: Laksanakan penggabungan permintaan bagi setiap kunci (singleflight)

Gesaan dan konteks

Laksanakan pembantu tak segerak yang selamat untuk konkurensi, coalesce(key, task). Paling banyak satu task boleh berjalan untuk key tertentu pada satu masa. Pemanggil serentak dengan kunci yang sama mesti menunggu (await) dan menerima nilai atau ralat yang sama persis; kunci yang berbeza mesti berjalan secara bebas.

Tugas boleh melontarkan ralat secara segerak atau menolak (reject) secara tak segerak. Pemanggil boleh menetapkan had masa menunggu mereka sendiri. Entri mesti dialih keluar selepas kejayaan dan kegagalan supaya panggilan terkemudian boleh mencuba semula. Terangkan semantik pembatalan, penyebaran ralat, dan ujian.

Perkara yang diuji oleh penemu duga

Terasnya adalah mengubah penyahduplikasian menjadi invarian konkurensi yang boleh dibuktikan: pasang janji (promise) yang dikongsi sebelum memulakan kerja tak segerak, padam hanya apabila peta masih merujuk kepada entri tersebut, dan pastikan kunci kekal bebas. Penemu duga juga mahu anda membezakan antara satu pemanggil yang membatalkan penantiannya daripada membatalkan kerja yang dikongsi, dan menangani pertumbuhan memori yang tidak terhad.

Soalan penjelasan

1. Adakah kunci mesti tidak kosong atau dinormalkan? Saya akan menolak kunci kosong supaya permintaan yang tidak berkaitan tidak bergabung secara tidak sengaja.
2. Patutkah had masa tamat pemanggil membatalkan kerja huluan (upstream)? Secara lalai, ia hanya menghentikan penantian pemanggil tersebut dan membiarkan kerja yang dikongsi terus berjalan untuk penunggu lain.
3. Patutkah ralat dicache? Tidak. Padam selepas penyelesaian (settlement) supaya panggilan seterusnya mencuba semula.
4. Adakah penggabungan rentas proses diperlukan? Tidak; gesaan ini adalah untuk memori proses tunggal. Penyelarasan rentas proses adalah reka bentuk yang berasingan.

Jawapan 30 saat

Saya menyimpan kerja in-flight dalam Map<key, Entry>. Semasa masuk, kembalikan janji sedia ada jika terdapat padanan (hit). Jika tiada padanan (miss), cipta janji tersebut, masukkannya ke dalam peta sebelum melakukan await, dan kemudian jalankan tugas. Dalam finally, padam hanya jika peta masih mengandungi entri yang sama. Pemanggil dengan kunci yang sama berkongsi satu pelaksanaan, kunci berbeza tidak menyekat antara satu sama lain, dan kegagalan melepaskan keadaan untuk percubaan semula. Had masa tamat pemanggil berlumba dengan penantiannya tanpa membatalkan kerja yang dikongsi. Ujian meliputi panggilan pendua, kunci bebas, lontaran segerak, penolakan dan percubaan semula, serta perlumbaan pembersihan.

Selaman mendalam langkah demi langkah

Tentukan Entry yang boleh memegang janji yang dikongsi dan, jika perlu, pengawal dalaman. Susunan adalah bahagian 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 boleh merekodkan masa mula, bilangan penunggu, dan AbortController secara tambahan. Promise.resolve().then(task) menjadikan lontaran segerak dan penolakan tak segerak mengikut satu laluan yang sama. Kemasukan ke dalam peta mesti berlaku sebelum await pertama; jika tidak, dua giliran gelung acara (event loop) kedua-duanya boleh memerhatikan keadaan miss. Pemeriksaan identiti menghalang finally tugas lama daripada memadam entri yang lebih baharu.

Had masa tamat pemanggil adalah dasar luaran:

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 yang dikongsi masih selesai untuk penunggu lain. Jika produk memerlukan pembatalan apabila semua pemanggil meninggalkannya, tambah pengiraan rujukan dan tentukan perlumbaan itu secara jelas dalam kontrak dan ujian.

Operasi peta yang dijangkakan ialah O(1). Dengan K kunci in-flight yang berbeza, keadaan adalah O(K); menyampaikan satu hasil menelan kos berkadar dengan bilangan penunggu. Kod pengeluaran harus mengehadkan kardinaliti kunci dan mendedahkan metrik tempoh masa, had masa tamat, bilangan penunggu, dan ralat supaya peta tidak menjadi cache tanpa had.

Contoh jawapan berkualiti tinggi

Saya akan menyatakan batasannya terlebih dahulu: proses tunggal, penyahduplikasian in-flight sahaja, tiada cache hasil. Map menyimpan setiap entri. Sekiranya tiada padanan, saya mencipta dan mendaftarkan janji dengan segera, kemudian memanggil tugas pengguna. Setiap pemanggil menerima janji yang sama, jadi nilai dan ralat adalah sama. Pembersihan membandingkan identiti objek, menghalang penyelesaian lama daripada memadam generasi yang lebih baharu.

Pembatalan bermaksud "batalkan penantian, bukan kerja yang dikongsi": seorang pemanggil yang tamat masa tidak menghantar AbortError kepada penunggu lain atau mengganggu satu-satunya operasi huluan. Jika pembatalan sebenar diperlukan, saya akan menggunakan pengawal yang dikongsi ditambah dengan pengiraan rujukan penunggu dan membatalkan hanya apabila kiraan mencapai sifar.

Untuk ujian, saya menggunakan halangan (barrier) untuk melepaskan pemanggil serentak dan memastikan satu pemanggilan tugas dan satu hasil yang dikongsi. Saya juga menguji kunci bebas secara selari, lontaran segerak, penolakan tak segerak, percubaan semula selepas kegagalan, tugas baharu selepas kejayaan, finally lama yang berlumba dengan entri baharu, dan seorang pemanggil yang tamat masa manakala pemanggil lain masih berjaya. Saya akan mengakhirinya dengan had kapasiti dan metrik untuk kunci berkardinaliti tinggi.

Kesilapan biasa

• Menunggu (await) task() sebelum memasukkan ke dalam peta, yang membenarkan pelaksanaan pendua.
• Memadam mengikut kunci tanpa syarat dalam finally, membenarkan tugas lama memadam entri yang lebih baharu.
• Menghantar AbortSignal milik satu pemanggil secara terus kepada kerja yang dikongsi dan membatalkan setiap penunggu.
• Menyimpan janji yang ditolak selama-lamanya daripada memadamkannya untuk percubaan semula.
• Menggunakan satu kunci global dan mensirilah kunci yang tidak berkaitan.
• Hanya menguji panggilan berurutan dan bukannya ketibaan serentak, lontaran segerak, dan perlumbaan pembersihan.

Soalan susulan dan jawapan

Bagaimanakah anda menyokong pembatalan sebenar?

Bilakah penggabungan rentas proses diperlukan?

Bagaimanakah anda menghalang kebocoran kunci berkardinaliti tinggi?

Pembatalan sebenar memerlukan pengawal yang dikongsi, pengiraan rujukan, dan dasar sifar-penunggu yang jelas. Kes rentas proses memerlukan Redis, get laluan (gateway), atau penyelaras lain berserta pajakan (leases), pengendalian kegagalan ketua (leader), dan toleransi pelaksanaan pendua. Kunci berkardinaliti tinggi memerlukan had kapasiti, TTL atau dasar pengusiran (eviction), tingkah laku penolakan, dan metrik; kawalan ini mesti mengekalkan peraturan teras bahawa hanya kerja in-flight yang disimpan.