Wawancara Coding: Mengimplementasikan Timer Hashed Timing Wheel

Petunjuk dan konteks

Pertanyaan ini menguji apakah Anda dapat memilih struktur data untuk banyak timer perkiraan. Binary heap mengurutkan tenggat waktu (deadline), sehingga penyisipan dan penghapusan mempertahankan urutan heap; timing wheel memetakan tenggat waktu ke dalam bucket dan cocok untuk batas waktu jaringan, percobaan ulang (retries), dan keepalive koneksi di mana ketepatan waktu yang eksak tidak diperlukan. Jelaskan presisi, kompleksitas, semantik pembatalan, penundaan lama, dan batas thread eksekusi.

Apa yang sedang dievaluasi oleh pewawancara

Apakah Anda menghubungkan tick, jumlah bucket, rentang yang dicakup, dan tenggat waktu tugas secara tepat.
Apakah Anda menangani tugas yang melintasi rotasi, pekerjaan dalam bucket saat ini, tick yang terlambat, dan eksekusi dini.
Apakah pembatalan berbiaya rendah dan node yang dibatalkan tidak dapat dieksekusi secara tidak sengaja.
Apakah Anda dapat menjelaskan thread safety, isolasi callback, pemilihan jam, dan perilaku saat kelebihan beban (overload).

Pertanyaan klarifikasi untuk diajukan terlebih dahulu

Konfirmasikan volume tugas, kesalahan paling awal dan paling lambat yang diizinkan, penundaan minimum dan maksimum, rasio pembatalan, dan durasi callback. Apakah tugas harus tahan lama (durable), dan apakah tugas tersebut harus tetap bertahan setelah proses dimulai ulang? Bisakah beberapa thread memanggil schedule dan cancel? Apakah callback boleh memblokir (blocking)? Jika satu tick berisi terlalu banyak tugas yang jatuh tempo, apakah eksekusi harus ditunda, pekerjaan berprioritas rendah dibatalkan, atau backpressure diterapkan? Jawaban-jawaban ini menentukan apakah satu wheel sudah cukup atau apakah Anda memerlukan hierarchical wheel atau persistensi eksternal.

Kerangka jawaban 30 detik

Saya akan menghitung tenggat waktu relatif dengan jam monotonik (monotonic clock) dan memajukan kursor pada tick yang tetap. Untuk setiap tugas, hitung indeks bucket dan sisa putaran (remaining rounds), lalu simpan dalam doubly linked list. Pada setiap tick, pindai hanya bucket saat ini: kurangi dan pertahankan tugas yang memiliki sisa putaran, dan hapus tugas yang jatuh tempo untuk dieksekusi ketika putaran mencapai nol. Sebuah handle memungkinkan cancel menandai dan memutuskan tautan (unlink) sebuah node. Wheel menjadwalkan pekerjaan tetapi tidak pernah menjalankan callback pengguna pada thread tick; presisi, konkurensi, dan perilaku kelebihan beban diverifikasi dengan pengujian dan metrik.

Pembahasan mendalam langkah demi langkah

1. Tentukan parameter wheel dan batas kesalahan

Misalkan tickDuration adalah tick dan wheelSize adalah jumlah bucket; satu rotasi mencakup tickDuration × wheelSize. Konversikan tenggat waktu ke tick relatif, lalu hitung (currentTick + remainingTicks) mod wheelSize. Tick menentukan resolusi minimum, sedangkan rentang rotasi menentukan penundaan mana yang cocok secara langsung. Untuk rentang yang lebih besar, gunakan hierarchical wheel atau pertahankan nilai sisa putaran hingga tugas dapat ditempatkan secara lebih presisi.

2. Pilih node tugas dan struktur bucket

Setiap node menyimpan tenggat waktu, remainingRounds, callback, flag pembatalan, serta pointer sebelumnya dan berikutnya. Doubly linked list memberikan penyisipan dan penghapusan dengan waktu konstan ketika node diketahui; sebuah handle dapat menunjuk langsung ke node tersebut, sehingga cancel tidak perlu melakukan pencarian. Jangan menyimpan setiap tugas dalam sebuah array dan memindai semuanya pada setiap tick, karena biayanya bertambah seiring dengan jumlah total tugas.

3. Majukan tick dan tangani rotasi

Majukan jam monotonik dan kursor, lalu lepaskan bucket saat ini. Jika remainingRounds bernilai positif, kurangi nilainya dan masukkan kembali node tersebut. Jika tidak, bandingkan tenggat waktu sebenarnya: masukkan kembali ke bucket tugas yang masih terlalu dini dan kirimkan hanya tugas yang sudah jatuh tempo. Jika jeda thread menyebabkan banyak tick terlewatkan, batasi pekerjaan pengejaran (catch-up) dan catat penundaan sehingga pemulihan tidak memblokir untuk waktu yang tidak terbatas.

4. Tangani schedule, cancel, dan race condition

Antrean produsen dapat mengirimkan permintaan schedule dan cancel ke satu thread tick, mengurangi perebutan kunci bucket. Cancel menetapkan flag sebelum mencoba memutuskan tautan; setelah thread tick mengambil node dari bucket, thread tersebut memeriksa flag lagi sehingga race condition tidak dapat menjalankan callback yang telah dibatalkan. Tenggat waktu yang lebih awal dari waktu sekarang harus didefinisikan sebagai "dijalankan pada tick berikutnya yang tersedia", bukan dikonversi dengan modulo negatif ke bucket masa depan yang arbitrer.

5. Isolasi callback dan kelebihan beban

Thread tick hanya memindahkan node dan mengirimkan pekerjaan; executor terbatas (bounded executor) menjalankan callback pengguna. Ketika penuh, tentukan kebijakan seperti batas antrean, membuang pekerjaan yang dapat dibuang berdasarkan prioritas, menunda pekerjaan non-kritis, atau mengembalikan kesalahan kelebihan beban. Lacak penundaan kedaluwarsa, waktu pemindaian bucket, pembatalan, panjang antrean executor, dan kegagalan callback untuk menentukan apakah wheel atau executor hilir yang menjadi penghambat (bottleneck).

6. Tetapkan invarian inti dengan pseudocode

Loop inti dapat diekspresikan sebagai berikut; penguncian dan kepemilikan thread bergantung pada bahasa implementasi:

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 jawaban berkualitas tinggi

Pertama, saya akan mengonfirmasi toleransi kesalahan, rentang penundaan, rasio pembatalan, durabilitas, dan sifat pemblokiran callback. Saya akan menggunakan jam monotonik dan tick tetap, dengan daftar bucket doubly linked yang nodenya menyimpan tenggat waktu, sisa putaran, flag pembatalan, dan handle. Schedule menghitung bucket dan putaran; cancel memutuskan tautan melalui handle dan menetapkan flag. Thread tick hanya memproses bucket saat ini, mengurangi putaran untuk rotasi masa depan, dan mengirimkan callback yang jatuh tempo ke executor terbatas. Pengejaran setelah tick yang terlewat dibatasi dan diukur; kelebihan beban executor memiliki kebijakan antrean, prioritas, dan kegagalan. Pengujian mencakup batas tenggat waktu, penundaan lama, pembatalan berulang, schedule/cancel bersamaan, lonjakan jam, pengecualian callback, dan biaya pemindaian dengan jutaan node. Jika diperlukan kesalahan yang lebih ketat atau rentang yang lebih luas, tambahkan hierarchical wheel atau heap daripada mengklaim bahwa wheel selalu lebih cepat.

Kesalahan umum

Menggunakan waktu jam dinding (wall-clock time) untuk penundaan relatif dan mengabaikan penyesuaian jam sistem.
Melupakan remainingRounds, menyebabkan tugas terpicu pada rotasi pertama.
Mengeksekusi atau menghilangkan secara diam-diam tugas di bucket saat ini yang belum jatuh tempo.
Mengatur boolean pembatalan tanpa memeriksanya kembali setelah mengambil node.
Menjalankan callback pengguna secara sinkron pada thread tick dan menghentikan laju wheel.
Memindai array tetap dari setiap tugas dan kehilangan efisiensi penjadwalan yang renggang (sparse).
Mengabaikan perilaku untuk tick yang terlewat, kelebihan beban, pemulihan setelah restart, dan kegagalan callback.

Pertanyaan lanjutan dan tanggapan

Mengapa tidak menggunakan min-heap?

Min-heap cocok untuk beban kerja yang lebih kecil atau pengurutan tenggat waktu yang ketat, tetapi setiap penyisipan atau penghapusan mempertahankan urutan heap. Timing wheel mengorbankan presisi demi penempatan dan penghapusan bucket dalam waktu konstan, yang cocok untuk banyak timer perkiraan. Pilihlah berdasarkan batas toleransi kesalahan dan distribusi operasi, bukan mengklaim bahwa wheel selalu lebih cepat.

Bagaimana jika thread tick berhenti selama beberapa detik?

Gunakan waktu monotonik untuk menghitung tick yang seharusnya telah berlalu, batasi jumlah bucket atau tugas yang diproses dalam satu putaran pengejaran, dan sisakan sisanya untuk nanti. Ukur penundaan penjadwalan; jika lonjakan tidak dapat diterima, gabungkan pemrosesan batch dengan backpressure daripada menjalankan setiap callback secara sinkron selama pemulihan.

Bagaimana Anda memastikan cancel tidak dapat mengeksekusi tugas?

Handle menunjuk ke node. Cancel menandainya secara atomik sebelum memutuskan tautan, dan thread tick memeriksa flag lagi setelah melepaskannya. Jika callback sudah dikirimkan, tentukan titik linearisasi pembatalan dan minta callback memeriksa status tugas sebelum memulai.

Kapan Anda membutuhkan hierarchical timing wheel?

Gunakan hierarchical timing wheel ketika satu rotasi tidak dapat mencakup tenggat waktu terbesar atau penundaan tugas mencakup beberapa tingkatan magnitudo. Tambahkan tingkat atas yang lebih kasar dan turunkan tugas ke bawah secara bertingkat, sambil menentukan presisi, degradasi, dan biaya migrasi setiap tingkat. Durabilitas dan pemulihan dari crash masih memerlukan pemisahan wheel dari penyimpanan atau perpesanan yang andal.