Temu duga pengekodan: laksanakan pengehad kadar token-bucket toleran lonjakan (burst)

Kehendak soalan dan skop

Laksanakan pengehad kadar token-bucket bagi setiap pengguna. Setiap baldi mempunyai capacity maksimum, kadar isian semula refillRate sesaat dan baki token semasa. Suatu permintaan membawa ID pengguna, cap masa dan kos. Jika baki yang telah diisi semula mencukupi kos, gunakannya dan benarkan permintaan; jika tidak, tolak permintaan tersebut. Terangkan API, kerumitan, ketepatan masa, kekompaunan dan ujian.

Ini sesuai untuk temu duga pengekodan bahagian belakang (backend), platform dan infrastruktur. AWS menerangkan token bucket sebagai token yang mewakili permintaan, diisi semula pada kadar yang dikonfigurasikan, dengan satu token digunakan bagi setiap permintaan, dan mengesyorkan pengujian had sebelum meningkatkannya.

Perkara yang dinilai oleh penemu duga

• Sama ada anda menggunakan isian semula lewah (lazy refill) dan bukannya memulakan pemasa bagi setiap baldi.
• Sama ada anda menggunakan masa monotonik supaya pembalikan jam dinding (wall-clock rollback) tidak dapat mencipta token tambahan.
• Sama ada token dihadkan dan permintaan yang ditolak mengekalkan baki tanpa perubahan.
• Sama ada anda membezakan memori proses tunggal daripada keadaan kongsi teragih.
• Sama ada anda merangkumi kekompaunan, ketepatan berangka, jurang melahu yang panjang dan parameter tidak sah.

Penjelasan untuk ditanya terlebih dahulu

Sahkan:

1. Adakah cost sentiasa integer positif, atau bolehkah ia berupa pecahan?
2. Adakah masa disuntik untuk ujian deterministik, atau dibaca oleh pengehad itu sendiri?
3. Adakah pelaksanaan proses tunggal sudah memadai, atau perlukah tika (instance) berkongsi kuota?
4. Patutkah penolakan menyertakan baki token atau anggaran masa cuba semula?

Jika tidak dinyatakan, anggap satu proses, kos integer bukan negatif, jam monotonik nanosaat dan lonjakan dibenarkan sehingga kapasiti baldi.

Rangka jawapan tiga puluh saat

Simpan tokens dan lastRefillAt bagi setiap pengguna. Pada setiap permintaan, lakukan isian semula secara lewah dengan min(capacity, tokens + elapsed * refillRate) menggunakan masa berlalu monotonik. Benarkan hanya apabila baki yang diisi semula menampung cost; jika tidak, kekalkan keadaan dan tolak. Dalam satu proses, kunci bagi setiap pengguna atau seksyen kritikal atomik menjadikan baca, isi semula, semak dan tulis tidak boleh dibahagikan. Dalam penggunaan teragih, jalankan peralihan yang sama dalam skrip storan kongsi atomik atau transaksi. Sahkan parameter, tingkah laku jam, sempadan dan panggilan serentak dengan ujian model jam boleh kawal.

Penerangan terperinci langkah demi langkah

1. Keadaan dan invarian

Simpan tokens, lastRefillAt dan secara pilihan versi bagi setiap pengguna. Invariannya ialah 0 <= tokens <= capacity, dan lastRefillAt tidak pernah berundur ke belakang. Sahkan kapasiti positif dan kadar isian semula semasa penciptaan. Kos mestilah positif dan tidak lebih besar daripada kapasiti; jika tidak, kembalikan ralat parameter tanpa mengubah keadaan.

2. Isian semula lewah (Lazy refill)

Biarkan now sebagai masa semasa dan elapsed = now - lastRefillAt. Tambah elapsed * refillRate, kemudian apit baki dengan min(capacity, tokens + refill). Walaupun baldi penuh, majukan lastRefillAt kepada now supaya selang masa tidak dikira lagi. Integer nanosaat dengan aritmetik rasional mengurangkan hanyutan titik terapung; jika apungan digunakan, tentukan pembundaran dan uji larian jangka panjang.

3. Benarkan dan tolak

Jika baki yang diisi semula sekurang-kurangnya cost, tolak kos dan benarkan. Jika tidak, jangan tolak apa-apa; kembalikan penolakan dan secara pilihan retryAfter. Anggarkan kelewatan sebagai (cost - tokens) / refillRate, dibundarkan ke atas, sambil mengendalikan kadar isian semula sifar dan kos yang lebih besar daripada kapasiti. Penolakan tidak boleh kelihatan seperti kejayaan atau mengundurkan kursor ke belakang.

4. Kekompaunan dan storan

Kod proses tunggal mesti mengekalkan baca, isi semula, keputusan dan tulis dalam satu seksyen kritikal; kunci bagi setiap pengguna yang dishardkan mengelakkan satu kunci global. Apabila beberapa tika berkongsi kuota, kunci aplikasi tidak mencukupi. Gunakan Redis Lua, kunci baris pangkalan data atau transaksi atomik lain untuk keseluruhan peralihan keadaan. Bawa ID permintaan melalui percubaan semula rangkaian supaya respons yang hilang tidak sengaja menggunakan token perniagaan sebanyak dua kali.

5. Tamat tempoh dan kekardinalan

Tamatkan tempoh keadaan pengguna tidak aktif menggunakan lastRefillAt dan dasar pajakan, sambil memastikan permintaan baharu dimulakan dengan betul. Lindungi daripada pengguna berkardinaliti tinggi dengan had keadaan, pemecahan (sharding) dan dasar penyingkiran (eviction). Mencipta semula baldi yang disingkirkan pada kapasiti penuh boleh mewujudkan lonjakan, jadi dasar pengeluaran mesti menyatakan sama ada perkara itu boleh diterima. Jangan sekali-kali membiarkan ID pengguna yang dikawal penyerang mengembangkan peta tanpa batas.

6. Pengujian dan kebolehcerapan

Uji baldi yang pada mulanya penuh, penolakan berulang, isian semula tepat, kos sama dengan kapasiti, tiada masa berlalu, pembalikan jam, jurang melahu yang panjang, persaingan dan panggilan pendua. Dengan jam yang disuntik, pastikan baki kekal dalam batas dan kos yang berjaya tidak pernah melebihi kapasiti awal ditambah isian semula teori. Jejaki kadar benarkan dan tolak, taburan token, bilangan keadaan, masa menunggu kunci, ralat skrip atomik dan penggunaan memori.

Contoh jawapan berkualiti tinggi

Saya akan mendedahkan allow(userId, now, cost). Keadaan pengguna hanya mengandungi tokens dan lastRefillAt. Di dalam satu seksyen kritikal, kira masa berlalu, isi semula, apit mengikut kapasiti dan buat keputusan. Jika berjaya, tolak kos dan gerakkan kursor ke now; jika ditolak, kekalkan baki yang diisi semula tetapi jangan gunakan apa-apa. Semua aritmetik masa menggunakan jam monotonik, jadi keadaan tidak boleh berundur ke belakang.

Bagi satu proses, saya akan menggunakan kunci bagi setiap pengguna yang dishardkan. Bagi berbilang tika, saya akan meletakkan peralihan yang sama dalam Redis Lua atau transaksi pangkalan data atomik dan bukannya melakukan operasi baca dan tulis rangkaian secara berasingan. ID permintaan menyokong keidempotentan cuba semula; ia tidak menjadikan operasi perniagaan terlaksana tepat sekali secara tersendiri. Tamat tempoh dan kawalan kekardinalan tinggi menghalang penyalahgunaan memori.

Ujian menggunakan jam yang boleh dikawal untuk masa berlalu sifar, isian semula tepat, permintaan kos penuh, tempoh melahu yang panjang, pembalikan jam dan kekompaunan. Ujian sifat menegaskan bahawa setiap baki kekal antara sifar dan kapasiti serta kos kumulatif yang dibenarkan tidak pernah melebihi kapasiti awal ditambah isian semula. Dalam pengeluaran, saya akan memerhatikan kadar penolakan, taburan token, pertumbuhan keadaan, menunggu kunci dan ralat skrip storan; panduan AWS juga memerlukan pengujian had yang dicadangkan sebelum meningkatkannya.

Kesilapan lazim

• Memulakan pemasa bagi setiap baldi, menyebabkan kos penjadualan meningkat seiring dengan bilangan pengguna.
• Menggunakan masa jam dinding, menyebabkan pembalikan NTP mencipta token tambahan.
• Terlupa pengapitan kapasiti dan membenarkan pengumpulan tanpa had.
• Mengenakan caj pada permintaan yang ditolak dan menghabiskan kuota pengguna secara senyap.
• Menganggap kunci dalam proses sebagai keatomikan merentas tika.
• Menerima cost > capacity, yang boleh menyebabkan menunggu selama-lamanya atau menghasilkan masa cuba semula yang tidak masuk akal.
• Menggunakan titik terapung tanpa mentakrifkan pembundaran dan hanyutan jangka panjang.
• Menguji panggilan berurutan sahaja dan terlepas perlumbaan baca-ubah-tulis serentak.

Soalan susulan dan jawapan

Mengapa bukan pembilang tetingkap tetap (fixed-window counter)?

Tetingkap tetap adalah mudah tetapi boleh membenarkan lonjakan ganda pendek pada sempadan tetingkap. Token bucket menyatakan lonjakan yang dibenarkan dengan kapasiti dan kadar mampan dengan isian semula. Jika tiada lonjakan yang boleh diterima, bandingkan dengan sliding window atau leaky bucket.

Bagaimana anda mengembalikan Retry-After?

Bahagikan baki yang hilang dengan kadar isian semula dan bundarkan ke atas. Dengan isian semula sifar atau kos melebihi kapasiti, kembalikan ralat konfigurasi atau hasil yang tidak boleh dicuba semula dan bukannya cap masa infiniti.

Bagaimana jika Redis tidak tersedia?

Pilih fail-closed, bajet tempatan terhad atau penurunan taraf secara eksplisit mengikut risiko titik akhir, dan rekodkan sebabnya. Jangan biarkan setiap tika fail-open tanpa bajet atau menyembunyikan gangguan sebagai penolakan biasa.

Bagaimana anda menukar kapasiti dan kadar isian semula?

Isi semula di bawah parameter lama sehingga masa perubahan, kemudian apit atau tukar baki di bawah dasar eksplisit dan rekodkan versi konfigurasi. Menurunkan kapasiti mesti mengendalikan baki sedia ada yang melebihi had baharu secara atomik.

Bagaimana anda membuktikan tiada penjualan berlebihan (overselling)?

Jalankan ujian sifat mesin keadaan terhadap masa rawak dan tegaskan bahawa kos yang dibenarkan dalam setiap selang dihadkan oleh token awal ditambah isian semula teori. Tambah ujian tegasan serentak untuk mengesahkan seksyen kritikal atomik.