Temu Duga Pengekodan: Laksanakan Pemasa Hashed Timing Wheel

Gesaan dan konteks

Soalan ini menguji sama ada anda boleh memilih struktur data untuk banyak pemasa anggaran. Binary heap menyusun tarikh akhir (deadlines), jadi pemasukan dan pemadaman mengekalkan susunan heap; timing wheel memetakan tarikh akhir ke dalam baldi dan sesuai untuk tamat masa rangkaian, percubaan semula (retries), dan keepalive sambungan di mana pemasaan yang tepat tidak diperlukan. Terangkan ketepatan, kerumitan, semantik pembatalan, kelewatan yang panjang, dan sempadan benang pelaksanaan.

Perkara yang dinilai oleh penemu duga

Sama ada anda menghubungkan detik, bilangan baldi, rentang yang diliputi, dan tarikh akhir tugas secara tepat.
Sama ada anda mengendalikan tugas yang merentasi putaran, kerja dalam baldi semasa, detik yang lewat, dan pelaksanaan awal.
Sama ada pembatalan adalah murah dan nod yang dibatalkan tidak boleh dilaksanakan secara tidak sengaja.
Sama ada anda boleh menerangkan keselamatan benang (thread safety), pengasingan panggilan balik (callback), pilihan jam, dan tingkah laku lebihan beban (overload).

Soalan penjelasan untuk ditanya terlebih dahulu

Sahkan volum tugas, ralat paling awal dan paling lewat yang dibenarkan, kelewatan minimum dan maksimum, nisbah pembatalan, dan tempoh panggilan balik. Adakah tugas mesti tahan lama (durable), dan patutkah ia kekal selepas proses dimulakan semula? Bolehkah beberapa benang memanggil schedule dan cancel? Adakah panggilan balik boleh menyekat (block)? Jika satu detik mengandungi terlalu banyak tugas yang perlu dibayar, patutkah pelaksanaan dilewatkan, kerja berkeutamaan rendah digugurkan, atau tekanan balik (backpressure) dikenakan? Jawapan ini menentukan sama ada satu roda sudah mencukupi atau sama ada anda memerlukan roda berhierarki (hierarchical wheel) atau ketahanan luaran.

Rangka kerja jawapan 30 saat

Saya akan mengira tarikh akhir relatif dengan jam monotonik dan memajukan kursor pada detik yang tetap. Untuk setiap tugas, kira indeks baldi dan baki pusingan, kemudian simpannya dalam senarai pautan berganda (doubly linked list). Pada setiap detik, imbas baldi semasa sahaja: kurangkan dan kekalkan tugas dengan baki pusingan, dan alih keluar tugas yang perlu dibayar untuk pelaksanaan apabila pusingan mencapai sifar. Satu pemegang (handle) membolehkan cancel menandakan dan menyahpautkan nod. Roda menjadualkan kerja tetapi tidak pernah menjalankan panggilan balik pengguna pada benang detik; ketepatan, kekompaunan, dan tingkah laku lebihan beban disahkan dengan ujian dan metrik.

Perbincangan mendalam langkah demi langkah

1. Tentukan parameter roda dan ralat

Biar tickDuration menjadi detik dan wheelSize menjadi bilangan baldi; satu putaran meliputi tickDuration × wheelSize. Tukar tarikh akhir kepada detik relatif, kemudian kira (currentTick + remainingTicks) mod wheelSize. Detik menentukan resolusi minimum, manakala rentang putaran menentukan kelewatan yang muat secara langsung. Untuk julat yang lebih besar, gunakan roda berhierarki atau simpan nilai baki pusingan sehingga tugas boleh diletakkan dengan lebih tepat.

2. Pilih nod tugas dan struktur baldi

Setiap nod menyimpan tarikh akhir, remainingRounds, panggilan balik, bendera pembatalan, serta penunjuk sebelumnya dan seterusnya. Senarai pautan berganda memberikan pemasukan dan pengalihan keluar masa malar apabila nod diketahui; pemegang boleh menunjuk terus kepadanya, jadi cancel tidak perlu mencari. Jangan simpan setiap tugas dalam tatasusunan dan mengimbas kesemuanya pada setiap detik, kerana kos meningkat dengan jumlah bilangan tugas.

3. Majukan detik dan kendalikan putaran

Majukan jam monotonik dan kursor, kemudian tanggalkan baldi semasa. Jika remainingRounds adalah positif, kurangkannya dan masukkan semula nod tersebut. Jika tidak, bandingkan tarikh akhir sebenar: masukkan semula ke dalam baldi tugas yang masih awal dan hantar tugas yang telah matang sahaja. Jika jeda benang melangkau banyak detik, hadkan kerja mengejar (catch-up) dan rekod kelewatan supaya pemulihan tidak menyekat untuk masa yang tidak terhad.

4. Kendalikan schedule, cancel, dan perlumbaan (races)

Barisan gilir pengeluar boleh menghantar permintaan schedule dan cancel ke satu benang detik, mengurangkan pertikaian kunci baldi. Cancel menetapkan bendera sebelum cuba menyahpaut; selepas benang detik mengambil nod daripada baldi, ia memeriksa bendera sekali lagi supaya keadaan perlumbaan tidak dapat menjalankan panggilan balik yang dibatalkan. Tarikh akhir yang lebih awal daripada sekarang harus ditakrifkan sebagai "dijalankan pada detik tersedia seterusnya", bukan ditukar dengan modulo negatif ke dalam baldi masa depan yang sewenang-wenangnya.

5. Asingkan panggilan balik dan lebihan beban

Benang detik hanya memindahkan nod dan menghantar kerja; pelaksana terikat (bounded executor) menjalankan panggilan balik pengguna. Apabila ia penuh, tentukan dasar seperti had barisan gilir, menggugurkan kerja yang boleh dibuang mengikut keutamaan, melewatkan kerja bukan kritikal, atau mengembalikan ralat lebihan beban. Jejaki kelewatan luput, masa imbasan baldi, pembatalan, panjang barisan gilir pelaksana, dan kegagalan panggilan balik untuk menentukan sama ada roda atau pelaksana hiliran yang menjadi kekangan (bottleneck).

6. Tetapkan invarians teras dengan pseudokod

Gelung teras boleh dinyatakan seperti berikut; penguncian dan pemilikan benang bergantung pada bahasa pelaksanaan:

text

schedule(task, deadline):
    ticks = ceil((deadline - now) / tickDuration)
    ticks = max(ticks, 0)
    node.rounds = ticks / wheelSize
    node.bucket = (currentTick + ticks) % wheelSize
    buckets[node.bucket].append(node)
    return node.handle

advance(now):
    while currentTick <= floor(now / tickDuration):
        bucket = buckets[currentTick % wheelSize]
        for node in bucket.detachAll():
            if node.cancelled: continue
            if node.rounds > 0:
                node.rounds -= 1
                bucket.append(node)
            elif node.deadline <= now:
                executor.submit(node.callback)
            else:
                schedule(node, node.deadline)
        currentTick += 1

Contoh jawapan berkualiti tinggi

Saya akan mengesahkan toleransi ralat, julat kelewatan, nisbah pembatalan, ketahanan, dan penyekatan panggilan balik terlebih dahulu. Saya akan menggunakan jam monotonik dan detik tetap, dengan senarai baldi berpautan berganda yang nodnya menyimpan tarikh akhir, baki pusingan, bendera pembatalan, dan pemegang. Schedule mengira baldi dan pusingan; cancel menyahpaut melalui pemegang dan menetapkan bendera. Benang detik memproses baldi semasa sahaja, mengurangkan pusingan untuk putaran masa hadapan, dan menghantar panggilan balik yang matang kepada pelaksana terikat. Tindakan mengejar selepas detik yang dilangkau dihadkan dan diukur; lebihan beban pelaksana mempunyai dasar barisan gilir, keutamaan, dan kegagalan. Ujian meliputi tarikh akhir sempadan, kelewatan yang panjang, pembatalan berulang, schedule/cancel serentak, lompatan jam, pengecualian panggilan balik, dan kos imbasan dengan berjuta-juta nod. Jika ralat yang lebih ketat atau julat yang lebih luas diperlukan, tambahkan roda berhierarki atau heap dan bukannya mendakwa roda sentiasa lebih pantas.

Kesilapan biasa

Menggunakan masa jam dinding (wall-clock time) untuk kelewatan relatif dan mengabaikan pelarasan jam sistem.
Melupakan remainingRounds, menyebabkan tugas dicetuskan pada putaran pertama.
Melaksanakan atau kehilangan secara senyap tugas baldi semasa yang belum matang lagi.
Menetapkan boolean pembatalan tanpa menyemaknya semula selepas mengambil nod.
Menjalankan panggilan balik pengguna secara segerak pada benang detik dan membantutkan roda.
Mengimbas tatasusunan tetap bagi setiap tugas dan kehilangan kecekapan penjadualan jarang (sparse scheduling).
Meniadakan tingkah laku untuk detik yang dilangkau, lebihan beban, pemulihan mula semula, dan kegagalan panggilan balik.

Soalan susulan dan respons

Mengapa tidak menggunakan min-heap?

Min-heap sesuai untuk beban kerja yang lebih kecil atau susunan tarikh akhir yang ketat, tetapi setiap pemasukan atau pemadaman mengekalkan susunan heap. Timing wheel menukar ketepatan untuk penempatan dan pengalihan keluar baldi masa malar, yang sesuai untuk banyak pemasa anggaran. Pilih berdasarkan belanjawan ralat dan pengagihan operasi dan bukannya mendakwa roda sentiasa lebih pantas.

Bagaimana jika benang detik berhenti seketika selama beberapa saat?

Gunakan masa monotonik untuk mengira detik yang sepatutnya telah berlalu, hadkan bilangan baldi atau tugas yang diproses dalam satu laluan mengejar, dan tinggalkan selebihnya untuk kemudian. Ukur kelewatan penjadualan; jika lonjakan tidak dapat diterima, gabungkan pemprosesan kelompok dengan tekanan balik dan bukannya menjalankan setiap panggilan balik secara segerak semasa pemulihan.

Bagaimanakah anda memastikan cancel tidak boleh melaksanakan tugas?

Pemegang menunjuk ke nod. Cancel menandakannya secara atomik sebelum menyahpaut, dan benang detik menyemak bendera sekali lagi selepas menanggalkannya. Jika panggilan balik telah dihantar, tentukan titik kelinearan pembatalan dan minta panggilan balik menyemak keadaan tugas sebelum bermula.

Bilakah anda memerlukan hierarchical timing wheel?

Gunakan satu apabila putaran tunggal tidak dapat meliputi tarikh akhir terbesar atau kelewatan tugas merangkumi beberapa magnitud. Tambahkan tahap atas yang lebih kasar dan turunkan tugas ke bawah secara bertingkat, sambil menentukan ketepatan setiap tahap, penurunan, dan kos penghijrahan. Ketahanan dan pemulihan ranap masih memerlukan pengasingan roda daripada storan atau pemesejan yang boleh dipercayai.