Wawancara coding: mengimplementasikan rate limiter token-bucket yang toleran terhadap burst

Pertanyaan dan cakupan

Implementasikan rate limiter token-bucket per pengguna. Setiap bucket memiliki maksimum capacity, laju pengisian ulang refillRate per detik, dan saldo token saat ini. Sebuah permintaan membawa ID pengguna, stempel waktu, dan biaya. Jika saldo yang telah diisi ulang mencukupi biaya tersebut, kurangi saldo dan izinkan permintaan; jika tidak, tolak permintaan tersebut. Jelaskan API, kompleksitas, presisi waktu, konkurensi, dan pengujian.

Ini cocok untuk wawancara coding backend, platform, dan infrastruktur. AWS mendeskripsikan token bucket sebagai token yang merepresentasikan permintaan, diisi ulang pada laju yang dikonfigurasi, dengan satu token dikonsumsi per permintaan, dan menyarankan untuk menguji batas sebelum meningkatkannya.

Apa yang dievaluasi oleh pewawancara

Apakah Anda menggunakan lazy refill alih-alih memulai timer untuk setiap bucket.
Apakah Anda menggunakan waktu monotonik sehingga pemunduran wall-clock tidak dapat mencetak token baru.
Apakah token dibatasi hingga batas maksimum dan permintaan yang ditolak membiarkan saldo tetap utuh.
Apakah Anda membedakan memori proses tunggal dari state bersama terdistribusi.
Apakah Anda mencakup konkurensi, presisi numerik, jeda idle yang panjang, dan parameter yang tidak valid.

Klarifikasi untuk ditanyakan terlebih dahulu

Konfirmasikan:

Apakah cost selalu berupa bilangan bulat positif, atau bisa berupa pecahan?
Apakah waktu diinjeksikan untuk pengujian deterministik, atau dibaca oleh limiter itu sendiri?
Apakah implementasi proses tunggal sudah cukup, atau instance harus berbagi kuota?
Haruskah penolakan menyertakan sisa token atau perkiraan waktu coba lagi?

Jika tidak ditentukan, asumsikan satu proses, biaya bilangan bulat non-negatif, jam monotonik nanodetik, dan burst diizinkan hingga kapasitas bucket.

Kerangka jawaban tiga puluh detik

Simpan tokens dan lastRefillAt per pengguna. Pada setiap permintaan, lakukan lazy refill dengan min(capacity, tokens + elapsed * refillRate) menggunakan waktu monotonik yang telah berlalu. Izinkan hanya ketika saldo yang telah diisi ulang mencukupi cost; jika tidak, pertahankan state dan tolak. Dalam satu proses, kunci per pengguna atau critical section atomik membuat proses baca, isi ulang, periksa, dan tulis menjadi tidak terpisahkan. Dalam deployment terdistribusi, jalankan transisi yang sama dalam skrip shared-store atau transaksi atomik. Validasi parameter, perilaku jam, batas-batas nilai, dan panggilan konkuren dengan pengujian model controllable-clock.

Pembahasan mendalam langkah demi langkah

1. State dan invarian

Simpan tokens, lastRefillAt, dan secara opsional versi per pengguna. Invariannya adalah 0 <= tokens <= capacity, dan lastRefillAt tidak pernah bergerak mundur. Validasi kapasitas positif dan laju pengisian ulang saat pembuatan. Biaya harus positif dan tidak lebih besar dari kapasitas; jika tidak, kembalikan kesalahan parameter tanpa mengubah state.

2. Pengisian ulang lambat (lazy refill)

Misalkan now adalah waktu saat ini dan elapsed = now - lastRefillAt. Tambahkan elapsed * refillRate, lalu batasi saldo dengan min(capacity, tokens + refill). Bahkan ketika bucket penuh, majukan lastRefillAt ke now agar interval tersebut tidak dihitung lagi. Nanodetik bilangan bulat dengan aritmatika rasional mengurangi drift floating-point; jika float digunakan, tentukan pembulatan dan uji operasi jangka panjang.

3. Mengizinkan dan menolak

Jika saldo yang telah diisi ulang setidaknya cost, kurangi biaya dan izinkan. Jika tidak, jangan kurangi apa pun; kembalikan penolakan dan secara opsional retryAfter. Perkirakan penundaan sebagai (cost - tokens) / refillRate, dibulatkan ke atas, sambil menangani laju pengisian ulang nol dan biaya yang lebih besar dari kapasitas. Penolakan tidak boleh terlihat seperti keberhasilan atau memindahkan kursor ke belakang.

4. Konkurensi dan penyimpanan

Kode proses tunggal harus menjaga proses baca, isi ulang, keputusan, dan tulis dalam satu critical section; kunci per pengguna yang di-shard menghindari satu kunci global. Ketika beberapa instance berbagi kuota, kunci tingkat aplikasi tidak cukup. Gunakan Redis Lua, kunci baris basis data, atau transaksi atomik lainnya untuk seluruh transisi state. Sertakan ID permintaan melalui percobaan ulang jaringan sehingga respons yang hilang tidak secara tidak sengaja mengonsumsi token bisnis dua kali.

5. Kedaluwarsa dan kardinalitas

Kedaluwarsakan state pengguna yang tidak aktif menggunakan lastRefillAt dan kebijakan sewa, sambil memastikan permintaan baru diinisialisasi dengan benar. Lindungi dari pengguna berkardinalitas tinggi dengan batas state, sharding, dan kebijakan penggusuran (eviction). Membuat ulang bucket yang digusur pada kapasitas penuh dapat memicu burst, sehingga kebijakan produksi harus menyatakan apakah hal tersebut dapat diterima. Jangan pernah membiarkan ID pengguna yang dikendalikan penyerang menumbuhkan map tanpa batas.

6. Pengujian dan observabilitas

Uji bucket yang awalnya penuh, penolakan berulang, pengisian ulang yang tepat, biaya yang sama dengan kapasitas, tidak adanya kemajuan waktu, pemunduran jam, jeda idle yang panjang, perebutan sumber daya (contention), dan panggilan duplikat. Dengan jam yang diinjeksikan, pastikan bahwa saldo tetap berada dalam batas dan biaya yang berhasil tidak pernah melebihi kapasitas awal ditambah pengisian ulang teoretis. Lacak tingkat izin dan tolak, distribusi token, jumlah state, waktu tunggu kunci, kesalahan skrip atomik, dan penggunaan memori.

Contoh jawaban berkualitas tinggi

Saya akan mengekspos allow(userId, now, cost). State pengguna hanya berisi tokens dan lastRefillAt. Di dalam satu critical section, hitung waktu yang berlalu, isi ulang, batasi ke kapasitas, dan buat keputusan. Jika berhasil, kurangi biaya dan pindahkan kursor ke now; jika ditolak, pertahankan saldo yang telah diisi ulang tetapi jangan konsumsi apa pun. Semua aritmatika waktu menggunakan jam monotonik, sehingga state tidak dapat bergerak mundur.

Untuk satu proses, saya akan menggunakan kunci per pengguna yang di-shard. Untuk beberapa instance, saya akan menempatkan transisi yang sama dalam Redis Lua atau transaksi basis data atomik daripada melakukan pembacaan dan penulisan jaringan secara terpisah. ID permintaan mendukung idempoten percobaan ulang; ini tidak membuat operasi bisnis menjadi persis sekali (exactly-once). Kedaluwarsa dan kontrol kardinalitas tinggi mencegah penyalahgunaan memori.

Pengujian menggunakan jam yang dapat dikontrol untuk waktu berlalu nol, pengisian ulang tepat, permintaan biaya penuh, periode idle panjang, pemunduran jam, dan konkurensi. Uji properti memastikan bahwa setiap saldo tetap antara nol dan kapasitas dan bahwa biaya kumulatif yang diizinkan tidak pernah melebihi kapasitas awal ditambah pengisian ulang. Di lingkungan produksi, saya akan memantau tingkat penolakan, distribusi token, pertumbuhan state, waktu tunggu kunci, dan kesalahan skrip penyimpanan; panduan AWS juga menyarankan pengujian batas yang diusulkan sebelum meningkatkannya.

Kesalahan umum

Memulai timer untuk setiap bucket, membuat biaya penjadwalan bertambah seiring bertambahnya jumlah pengguna.
Menggunakan waktu wall-clock, sehingga pemunduran NTP membuat token tambahan.
Melupakan pembatasan kapasitas (capacity clamp) dan membiarkan akumulasi tanpa batas.
Mengenakan biaya pada permintaan yang ditolak dan secara diam-diam menghabiskan kuota pengguna.
Memperlakukan kunci in-process sebagai keatomikan lintas-instance.
Menerima cost > capacity, yang dapat menunggu selamanya atau menghasilkan waktu coba lagi yang palsu.
Menggunakan floating point tanpa menentukan pembulatan dan drift jangka panjang.
Hanya menguji panggilan sekuensial dan melewatkan race condition read-modify-write konkuren.

Pertanyaan lanjutan dan tanggapan

Mengapa tidak menggunakan fixed-window counter?

Fixed window sederhana tetapi dapat mengizinkan burst ganda singkat di perbatasan jendela waktu. Token bucket mengekspresikan burst yang diizinkan dengan kapasitas dan laju berkelanjutan dengan pengisian ulang. Jika burst tidak dapat diterima sama sekali, bandingkan dengan sliding window atau leaky bucket.

Bagaimana cara Anda mengembalikan Retry-After?

Bagi saldo yang kurang dengan laju pengisian ulang dan bulatkan ke atas. Dengan laju pengisian ulang nol atau biaya di atas kapasitas, kembalikan hasil konfigurasi atau non-retryable daripada stempel waktu tak terbatas.

Bagaimana jika Redis tidak tersedia?

Pilih fail-closed, anggaran lokal terbatas, atau degradasi eksplisit sesuai dengan risiko endpoint, dan catat alasannya. Jangan biarkan setiap instance fail-open tanpa anggaran atau menyembunyikan pemadaman sebagai penolakan biasa.

Bagaimana cara Anda mengubah kapasitas dan laju pengisian ulang?

Isi ulang berdasarkan parameter lama hingga waktu perubahan, lalu batasi atau konversikan saldo berdasarkan kebijakan eksplisit dan catat versi konfigurasi. Menurunkan kapasitas harus menangani saldo yang ada di atas batas baru secara atomik.

Bagaimana Anda membuktikan tidak ada penjualan berlebih (overselling)?

Jalankan uji properti state-machine pada waktu acak dan pastikan bahwa biaya yang diizinkan dalam setiap interval dibatasi oleh token awal ditambah pengisian ulang teoretis. Tambahkan uji stres konkuren untuk memverifikasi critical section yang atomik.