ریاضیات Rate Limiting؛ نرخ، پنجره زمانی و GCRA

پشت یک قانون ساده مثل «۱۰۰ درخواست در دقیقه» چه مدل ریاضی‌ای قرار دارد؟ Token Bucket و GCRA را از نرخ متوسط تا burst tolerance می‌سازیم.

ریاضیات سیستم‌ها و الگوریتم‌هاپیشرفته

مشاهده آموزش‌های دیگر

هدف یادگیری

رابطه میان limit، window، rate، interval و burst tolerance را بفهمید و منطق Token Bucket و GCRA را از روی فرمول توضیح دهید.

پیش‌نیازها

جبر مقدماتی
درک واحد زمان و نرخ

۱. از limit و window به rate

اگر اجازه L درخواست در بازه زمانی W داشته باشیم، نرخ متوسط مجاز از تقسیم این دو به دست می‌آید. مثلاً 100 درخواست در 60 ثانیه یعنی حدود 1.67 درخواست در ثانیه.

نرخ متوسط مجاز

r=\frac{L}{W}

۲. Token Bucket

در مدل Token Bucket، tokenها با یک نرخ مشخص وارد bucket می‌شوند و هر درخواست به اندازه cost خود token مصرف می‌کند. ظرفیت bucket مشخص می‌کند چه burstی می‌تواند در یک لحظه جذب شود.

نرخ refill

r=\frac{L}{W}

rate: سرعت تولید token
capacity: حداکثر token ذخیره‌شده
cost: هزینه منطقی هر درخواست
remaining: اعتبار باقی‌مانده

۳. ایده GCRA

GCRA به‌جای شمارش ساده درخواست‌ها، زمان رسیدن نظری را دنبال می‌کند. برای limit برابر L در window برابر W، فاصله پایه هر permit و تحمل burst از این رابطه‌ها به دست می‌آیند.

فاصله پایه هر permit

\tau=\frac{W}{L}

burst tolerance

B=\tau(L-1)

۴. مثال عددی

برای L=100 و W=60s، فاصله پایه هر permit برابر 0.6 ثانیه است. مقدار burst tolerance در این فرمول 0.6×99 یعنی 59.4 ثانیه است. این کمیت زمانی، با capacity در Token Bucket یکسان نیست.

محاسبه interval

\tau=\frac{60}{100}=0.6\;s

۵. چرا این ریاضیات در سیستم مهم است؟

در یک سامانه توزیع‌شده باید دقیقاً مشخص باشد چه چیزی شمارش می‌شود، زمان از کجا می‌آید و در نزدیکی limit چه تصمیمی برگردانده می‌شود. اینها بخشی از semantics سیستم هستند، نه جزئیات تزئینی.

۶. ارتباط مستقیم با RateLimitEngine

RateLimitEngine چهار الگوریتم Fixed Window، Sliding Window، Token Bucket و GCRA را پیاده می‌کند و برای state توزیع‌شده Redis از زمان سرور و transitionهای اتمیک استفاده می‌کند. این پروژه نمونه‌ای مستقیم از تبدیل مدل ریاضی به یک قرارداد مهندسی قابل استفاده است.

۷. تمرین

برای 60 درخواست در 30 ثانیه نرخ متوسط را حساب کنید.
تفاوت capacity در Token Bucket و burst tolerance در GCRA را توضیح دهید.
اگر cost یک درخواست 5 permit باشد، remaining چه تغییری می‌کند؟

پروژه مرتبط

RateLimitEngine

پیاده‌سازی واقعی چهار الگوریتم rate limiting برای .NET 8، شامل Token Bucket و GCRA.

باز کردن منبع

راهکارهای مرتبط

توسعه و مهندسی نرم‌افزار مدل‌سازی، الگوریتم و بهینه‌سازی

با یک مسئله rate limiting یا کنترل بار روبه‌رو هستید؟

می‌توان مدل، الگوریتم و رفتار توزیع‌شده را از مسئله تا implementation بررسی کرد.

گفت‌وگو درباره مسئله