Other Channels:
Perfect Dev Post:
@dev_perfects
GitHub Trending:
@github_trending_daily
Daily Poems:
@iipoem
DM: @k_abolfazl
Post #277
563
Forwarded from Mahi in Tech
وقتی صحبت از پیاده‌سازی Rate Limiting (مخصوصا مدل‌هایی مثل Token Bucket یا Leaky Bucket) میشه، معمولا اولین چالش، مدیریت State هست؛ اینکه همزمان باید تعداد توکن‌های باقی‌مونده و زمان آخرین Refresh رو نگه داریم و حواس‌مون به Race Condition هم باشه.
الگوریتم GCRA (Generic Cell Rate Algorithm) که توی سیستم‌های توزیع‌شده استفاده میشه، این مسئله رو با یک ترفند ریاضی خیلی ساده حل کرده: حذف مفهوم توکن و جابجایی همه‌چیز به بردار زمان.
ایده اصلی اینه: به جای اینکه چک کنیم کاربر چند تا توکن داره یا شمارنده رو ریست کنیم، یک متغیر عددی به اسم TAT (Theoretical Arrival Time) نگه می‌داریم؛ یعنی «زمان تئوریک رسیدن درخواست بعدی».
منطق کارکرد به چه صورته؟
فرض کنید لیمیت سیستم، ۱ درخواست در ثانیه باشه و به کاربر اجازه دادید تا سقف ۳ درخواست هم ترافیک ناگهانی (Burst) داشته باشه:
هر بار که یک درخواست تایید میشه، TAT به اندازه‌ی فاصله‌ی زمانی مجاز بین درخواست‌ها، به آینده هل داده میشه.
اگر کاربر چند درخواست پشت سر هم بفرسته، TAT جلوتر و جلوتر میره. در واقع داریم میزان «جلو افتادن» جریان درخواست‌ها از نرخ مجاز رو اندازه می‌گیریم، و تا وقتی فاصله‌ی بین زمان فعلی و TAT از محدوده‌ی مجاز Burst بیشتر نشده باشه، درخواست‌ها تایید می‌شن.
اگر این فاصله از محدوده‌ی مجاز عبور کنه، کاربر درجا خطای 429 می‌گیره و مهم‌تر اینکه TAT هم برای درخواست ردشده تغییر نمی‌کنه.
به محض اینکه کاربر چند ثانیه دست نگه داره، زمان فعلی به TAT نزدیک‌تر میشه و عملاً ظرفیت Burst به‌صورت خودکار آزاد میشه؛ بدون اینکه هیچ Job پس‌زمینه‌ای نیاز باشه یا کدی برای ریست کردن شمارنده‌ها اجرا بشه.
در ساده‌ترین حالت، منطق چیزی شبیه به اینه:
و قبل از آپدیت، بررسی می‌کنیم که آیا TAT در محدوده‌ی مجاز قرار داره یا نه. نکته‌ی مهم اینه که مقدار دقیق این محدوده به نحوه‌ی تعریف Burst/Tolerance در پیاده‌سازی بستگی داره.
چرا این مدل جذابه؟
۱. استیت تک‌مقداری: کل وضعیت هر کاربر فقط یک عدد ساده (Timestamp) هست که توی ردیس میتونه به صورت یک String ساده ذخیره بشه.
۲. اجرای اتمیک و جلوگیری از Race Condition: خود GCRA به‌تنهایی Race Condition رو حذف نمی‌کنه؛ چیزی که این مشکل رو حل میکنه، اجرای اتمیک کل منطق Check + Update هست. مثلا می‌تونیم این کار رو با یک اسکریپت چند خطی Lua داخل Redis انجام بدیم، بدون اینکه چند دستور جداگانه بین Read و Write داشته باشیم.
۳. مدیریت تمیز TTL: چون زمان موردنیاز برای نگه داشتن State قابل محاسبه است، می‌تونیم TTL کلید رو بر اساس زمانی تنظیم کنیم که TAT و محدوده‌ی Burst دیگه برای تصمیم‌گیری لازم نیستن. در نتیجه، کلیدها به‌صورت خودکار expire می‌شن و نیازی به Job یا فرآیند جداگانه برای پاک‌سازی State نداریم.
در نهایت، جذابیت اصلی GCRA این هست که به جای نگه داشتن چند متغیر مثل Token Count، Last Refill و Timestamp، کل State رو به یک مفهوم زمانی تبدیل میکنه.
الگوریتم GCRA (Generic Cell Rate Algorithm) که توی سیستم‌های توزیع‌شده استفاده میشه، این مسئله رو با یک ترفند ریاضی خیلی ساده حل کرده: حذف مفهوم توکن و جابجایی همه‌چیز به بردار زمان.
ایده اصلی اینه: به جای اینکه چک کنیم کاربر چند تا توکن داره یا شمارنده رو ریست کنیم، یک متغیر عددی به اسم TAT (Theoretical Arrival Time) نگه می‌داریم؛ یعنی «زمان تئوریک رسیدن درخواست بعدی».
منطق کارکرد به چه صورته؟
فرض کنید لیمیت سیستم، ۱ درخواست در ثانیه باشه و به کاربر اجازه دادید تا سقف ۳ درخواست هم ترافیک ناگهانی (Burst) داشته باشه:
هر بار که یک درخواست تایید میشه، TAT به اندازه‌ی فاصله‌ی زمانی مجاز بین درخواست‌ها، به آینده هل داده میشه.
اگر کاربر چند درخواست پشت سر هم بفرسته، TAT جلوتر و جلوتر میره. در واقع داریم میزان «جلو افتادن» جریان درخواست‌ها از نرخ مجاز رو اندازه می‌گیریم، و تا وقتی فاصله‌ی بین زمان فعلی و TAT از محدوده‌ی مجاز Burst بیشتر نشده باشه، درخواست‌ها تایید می‌شن.
اگر این فاصله از محدوده‌ی مجاز عبور کنه، کاربر درجا خطای 429 می‌گیره و مهم‌تر اینکه TAT هم برای درخواست ردشده تغییر نمی‌کنه.
به محض اینکه کاربر چند ثانیه دست نگه داره، زمان فعلی به TAT نزدیک‌تر میشه و عملاً ظرفیت Burst به‌صورت خودکار آزاد میشه؛ بدون اینکه هیچ Job پس‌زمینه‌ای نیاز باشه یا کدی برای ریست کردن شمارنده‌ها اجرا بشه.
در ساده‌ترین حالت، منطق چیزی شبیه به اینه:
if now < TAT - tolerance:
reject
else:
TAT = max(now, TAT) + interval
accept
و قبل از آپدیت، بررسی می‌کنیم که آیا TAT در محدوده‌ی مجاز قرار داره یا نه. نکته‌ی مهم اینه که مقدار دقیق این محدوده به نحوه‌ی تعریف Burst/Tolerance در پیاده‌سازی بستگی داره.
چرا این مدل جذابه؟
۱. استیت تک‌مقداری: کل وضعیت هر کاربر فقط یک عدد ساده (Timestamp) هست که توی ردیس میتونه به صورت یک String ساده ذخیره بشه.
۲. اجرای اتمیک و جلوگیری از Race Condition: خود GCRA به‌تنهایی Race Condition رو حذف نمی‌کنه؛ چیزی که این مشکل رو حل میکنه، اجرای اتمیک کل منطق Check + Update هست. مثلا می‌تونیم این کار رو با یک اسکریپت چند خطی Lua داخل Redis انجام بدیم، بدون اینکه چند دستور جداگانه بین Read و Write داشته باشیم.
۳. مدیریت تمیز TTL: چون زمان موردنیاز برای نگه داشتن State قابل محاسبه است، می‌تونیم TTL کلید رو بر اساس زمانی تنظیم کنیم که TAT و محدوده‌ی Burst دیگه برای تصمیم‌گیری لازم نیستن. در نتیجه، کلیدها به‌صورت خودکار expire می‌شن و نیازی به Job یا فرآیند جداگانه برای پاک‌سازی State نداریم.
در نهایت، جذابیت اصلی GCRA این هست که به جای نگه داشتن چند متغیر مثل Token Count، Last Refill و Timestamp، کل State رو به یک مفهوم زمانی تبدیل میکنه.
- ❤ 3
