طراحی یک محدود کننده نرخ (RATE LIMITER)

در یک سیستم تحت شبکه، یک محدود کننده نرخ برای کنترل نرخ ترافیک ارسال شده توسط یک کلاینت یا یک سرویس استفاده می شود. در دنیای HTTP، یک محدودکننده نرخ، تعداد درخواست‌های مجاز کلاینت به ارسال در یک دوره مشخص را محدود می‌کند. اگر تعداد درخواست های API از آستانه تعیین شده توسط محدود کننده نرخ بیشتر شود، همه ارتباط های اضافی (excess calls) مسدود می شوند. بطور مثال:• کاربر نمی تواند بیش از 2 پست در ثانیه بنویسد.• می توانید حداکثر 10 حساب در روز از یک آدرس IP ایجاد کنید.• شما نمی توانید بیش از 5 بار در هفته از همان دستگاه پاداش دریافت کنید.مزایای استفاده از یک محدود کننده نرخ API:• جلوگیری از خارج از دسترس شدن منابع، ناشی از حمله بندآوری سرویس Denial of Service (DoS) attac [1]. تقریباً تمام API های منتشر شده توسط شرکت های بزرگ فناوری نوعی محدودیت نرخ را اعمال می کنند. به عنوان مثال، توییتر تعداد توییت ها را به 300 توییت در هر 3 ساعت محدود می کند [2]. API های اسناد Google دارای محدودیت پیش‌فرض زیر هستند: 300 برای هر کاربر در 60 ثانیه برای درخواست‌های خواندن [3]. یک محدودکننده نرخ با مسدود کردن ارتباط های اضافی، از حملات DoS، عمدی یا غیرعمدی جلوگیری می‌کند.• کاهش هزینه. محدود کردن درخواست‌های اضافی به معنای سرورهای کمتر و تخصیص منابع بیشتر به API های با اولویت بالا است. محدود کردن نرخ برای شرکت هایی که از API های شخص ثالث(third-party) پولی استفاده می کنند بسیار مهم است. به عنوان مثال، برای API های خارجی زیر بر اساس هر تماس هزینه دریافت می کند: اعتبار چک، پرداخت، بازیابی سوابق سلامت و غیره. محدود کردن تعداد ارتباط­ها برای کاهش هزینه‌ها ضروری است.• جلوگیری از قرارگیری بار بیش از حد روی سرورها. برای کاهش بار سرور، یک محدود کننده نرخ برای فیلتر کردن درخواست های اضافی ناشی از ربات ها یا رفتار نادرست کاربران استفاده می شود.گام اول: درک مشکل و تعیین محدوده طراحیمحدود کردن نرخ(Rate Limiting) را می توان با استفاده از الگوریتم های مختلف پیاده سازی کرد که هر کدام مزایا و معایب خود را دارند. بررسی سوالات و پاسخ های پیشنهادی کمک می کند تا نوع محدود کننده های نرخ را که می خواهیم بسازیم روشن شود.سوال: قرار است چه نوع محدود کننده نرخی (Rate Limiter) را طراحی کنیم؟ یک محدود کننده نرخ سمت کلاینت یا محدود کننده نرخ API سمت سرور؟پاسخ: ما روی محدود کننده نرخ API سمت سرور تمرکز می کنیم.سوال: آیا محدود کننده نرخ درخواست های API را بر اساس IP، شناسه کاربری یا سایر ویژگی ها کاهش می دهد؟پاسخ: محدود کننده نرخ باید به اندازه کافی انعطاف پذیر باشد تا از مجموعه های مختلف قوانین محدودگر پشتیبانی کند.سوال: مقیاس سیستم چقدر است؟ آیا برای یک استارت آپ یا یک شرکت بزرگ با پایگاه کاربر بزرگ ساخته شده است؟پاسخ: سیستم باید قادر به رسیدگی به تعداد زیادی درخواست باشد.سوال: آیا سیستم در یک محیط توزیع شده کار خواهد کرد؟پاسخ: بله.سوال: آیا محدود کننده نرخ یک سرویس جداگانه است یا باید در کد برنامه پیاده سازی شود؟پاسخ: این یک تصمیم طراحی به عهده شماست.سوال: آیا باید به کاربرانی که محدود هستند اطلاع دهیم؟پاسخ: بله.الزاماتدر اینجا خلاصه ای از الزامات این سیستم آمده است:• محدود کردن درخواست های بیش از حد را به طور دقیق.• زمان ​​تاخیر کم. محدود کننده نرخ نباید زمان پاسخ دهی HTTP را کاهش دهد.• تا حد امکان از حافظه کمتری استفاده کند.• محدود کردن نرخ توزیع شده(Distributed rate limiting). محدود کننده نرخ را بتوان در چندین سرور یا فرآیند به اشتراک گذاشت.• رسیدگی به استثنا(Exception handling). زمانی که درخواست‌های کاربران مسدود می‌شود، استثناهای واضحی را به کاربران نشان دهد.• تحمل خطا بالا(High fault tolerance). اگر مشکلی در محدود کننده نرخ وجود داشته باشد (مثلاً یک سرور کش آفلاین شود)، بر کل سیستم تأثیر نگذارد.گام دوم: طراحی سطح بالا اجازه دهید همه چیز را ساده نگه داریم و از یک مدل اولیه کلاینت و سرور برای ارتباط استفاده کنیم.محدود کننده نرخ را کجا قرار دهیم؟به طور مستقیم، می توانید یک محدود کننده نرخ را در سمت کلاینت یا سمت سرور پیاده سازی کنید.• پیاده سازی سمت کلاینت. به طور کلی، کلاینت مکانی غیرقابل اعتماد برای اعمال محدودیت نرخ است زیرا درخواست های کلاینت می تواند به راحتی توسط عوامل مخرب جعل شود. علاوه بر این، ممکن است کنترلی بر اجرای کلاینت نداشته باشیم.• پیاده سازی سمت سرور. شکل 4-1 یک محدود کننده نرخ را نشان می دهد که در سمت سرور قرار داده شده است.علاوه بر اجرای کلاینت و سمت سرور، یک راه جایگزین نیز وجود دارد. به جای قرار دادن یک محدود کننده نرخ در سرورهای API، ما یک میان افزار محدود کننده نرخ ایجاد می کنیم که درخواست ها را به API های شما همانطور که در شکل 4-2 نشان داده شده است، کاهش می دهد.اجازه دهید از یک مثال در شکل 4-3 استفاده کنیم تا نحوه عملکرد محدود کردن نرخ در این طرح را نشان دهیم. فرض کنید API ما اجازه 2 درخواست در ثانیه را می دهد و یک کلاینت در عرض یک ثانیه 3 درخواست را به سرور ارسال می کند. دو درخواست اول به سرورهای API هدایت می شوند. با این حال، میان‌افزار محدودکننده نرخ سومین درخواست را کاهش می‌دهد و کد وضعیت HTTP 429 را برمی‌گرداند. کد وضعیت پاسخ HTTP 429 نشان می‌دهد که کاربر درخواست‌های زیادی ارسال کرده است.میکروسرویس های ابری(Cloud microservices) [4] به طور گسترده ای محبوب شده اند و محدودیت نرخ معمولاً در یک مؤلفه به نام دروازه(Gatway) API پیاده سازی می شود. دروازه API یک سرویس کاملا مدیریت شده است که از محدود کردن نرخ(rate limiting)، SSL termination، احراز هویت(authentication)، whitelisting IP، سرویس دادن به محتوای ثابت(static content) و غیره پشتیبانی می کند. در حال حاضر، فقط باید بدانیم که دروازه API یک میان افزار(Middlware) است که از محدود کردن نرخ پشتیبانی می کند.در هنگام طراحی یک محدود کننده نرخ، یک سوال مهم که باید از خود بپرسیم این است: محدود کننده نرخ در کجا باید پیاده سازی شود، در سمت سرور یا در یک دروازه؟ هیچ پاسخ مطلقی وجود ندارد. این به پشته فناوری(technology stack) فعلی، منابع مهندسی، اولویت ها، اهداف و غیره شرکت شما بستگی دارد.در اینجا چند دستورالعمل کلی(general guidelines) وجود دارد:- پشته فناوری فعلی خود را ارزیابی کنید، مانند زبان برنامه نویسی، سرویس حافظه پنهان، و غیره. مطمئن شوید که زبان برنامه نویسی فعلی شما برای اجرای محدودیت نرخ در سمت سرور کارآمد است.- الگوریتم محدود کننده نرخ را که متناسب با نیازهای کسب و کار شما است، شناسایی کنید. وقتی همه چیز را در سمت سرور پیاده سازی می کنید، کنترل کامل الگوریتم را در اختیار دارید. با این حال، اگر از دروازه شخص ثالث استفاده کنید، ممکن است انتخاب شما محدود باشد.- اگر قبلاً از معماری میکروسرویس استفاده کرده اید و یک دروازه API در طراحی برای انجام احراز هویت، لیست سفید IP و غیره قرار داده اید، می توانید یک محدود کننده نرخ به دروازه API اضافه کنید.- ایجاد خدمات محدود کننده نرخ خود زمان می برد. اگر منابع مهندسی کافی برای اجرای یک محدود کننده نرخ ندارید، یک دروازه تجاری(commercial API gateway) API گزینه بهتری است.الگوریتم های محدود کردن نرخ(Algorithms for rate limiting)محدود کردن نرخ را می توان با استفاده از الگوریتم های مختلف پیاده سازی کرد و هر کدام مزایا و معایب متمایز(distinct pros and cons) دارند. اگرچه این مطلب بر روی الگوریتم‌ها تمرکز نمی‌کند، درک آنها در سطح بالا به انتخاب الگوریتم یا ترکیبی از الگوریتم‌ها متناسب با موارد استفاده ما کمک می‌کند. در اینجا لیستی از الگوریتم های محبوب وجود دارد:• سطل توکن (Token bucket)• سطل نشتی (Leaking bucket)• شمارنده پنجره ثابت (Fixed window counter)• لاگ پنجره کشویی (Sliding window log)• شمارنده پنجره کشویی (Sliding window counter)الگوریتم سطل توکن (Token bucket)الگوریتم سطل توکن به طور گسترده برای محدود کردن نرخ استفاده می شود. این الگوریتم ساده است، به خوبی درک می شود و معمولاً توسط شرکت های اینترنتی استفاده می شود. هر دو آمازون [5] و Stripe [6] از این الگوریتم برای کاهش درخواست های API خود استفاده می کنند.الگوریتم سطل توکن به صورت زیر عمل می کند:• سطل توکن ظرفی است که دارای ظرفیت از پیش تعریف شده است. توکن ها به صورت دوره ای با نرخ های از پیش تعیین شده در سطل قرار می گیرند. پس از پر شدن سطل، هیچ توکن دیگری اضافه نمی شود. همانطور که در شکل 4-4 نشان داده شده است، ظرفیت سطل توکن 4 است. پرکننده در هر ثانیه 2 توکن را در سطل قرار می دهد. پس از پر شدن سطل، توکن های اضافی سرریز می شوند.• هر درخواست یک توکن مصرف می کند. وقتی درخواستی می رسد، بررسی می کنیم که آیا توکن های کافی در سطل وجود دارد یا خیر. شکل 4-5 نحوه عملکرد آن را توضیح می دهد.• اگر توکن های کافی وجود داشته باشد، برای هر درخواست یک توکن بیرون می آوریم و درخواست انجام می شود.• اگر نشانه های کافی وجود نداشته باشد، درخواست حذف می شود.شکل 4-6 نحوه عملکرد منطق مصرف توکن، پر کردن مجدد و نرخ محدود کننده را نشان می دهد. در این مثال، اندازه سطل توکن 4 است و نرخ پر کردن مجدد 4 در هر 1 دقیقه است.الگوریتم سطل توکن دو پارامتر دارد:• اندازه سطل(Bucket size): حداکثر تعداد توکن های مجاز در سطل• نرخ پر کردن مجدد(Refill rate): تعداد توکن هایی که در هر ثانیه در سطل قرار می گیرندچند سطل نیاز داریم؟ این متفاوت است و به قوانین محدودکننده نرخ بستگی دارد. در اینجا چند نمونه هستند.• معمولاً وجود سطل های مختلف برای نقاط انتهایی API مختلف ضروری است. به عنوان مثال، اگر کاربر مجاز است در هر ثانیه 1 پست بگذارد، 150 دوست در روز اضافه کند و 5 پست در ثانیه لایک کند، 3 سطل برای هر کاربر مورد نیاز است.• اگر بخواهیم درخواست ها را بر اساس آدرس های IP کاهش دهیم، هر آدرس IP به یک سطل نیاز دارد.• اگر سیستم حداکثر 10000 درخواست در ثانیه را مجاز کند، منطقی است که یک سطل عمومی مشترک بین همه درخواست ها وجود داشته باشد.مزایا(Pros):• پیاده سازی الگوریتم آسان است.• حافظه کارآمد (Memory efficient).• سطل توکن اجازه می دهد تا برای مدت کوتاهی از ترافیک عبور کند. تا زمانی که نشانه‌هایی باقی مانده باشد، درخواست می‌تواند انجام شود.معایب(Cons):• دو پارامتر در الگوریتم اندازه سطل و نرخ پر کردن توکن است. با این حال، تنظیم صحیح آنها ممکن است چالش برانگیز باشد.الگوریتم سطل نشت (Leaking bucket algorithm)الگوریتم سطل نشت مشابه سطل توکن است با این تفاوت که درخواست ها با نرخ ثابتی پردازش می شوند. معمولاً با صف اولین ورود، اولین خروج(FIFO) اجرا می شود. الگوریتم به صورت زیر کار میکند:• هنگامی که درخواستی می رسد، سیستم بررسی می کند که آیا صف پر است یا خیر. اگر پر نباشد، درخواست به صف اضافه می شود.• در غیر این صورت درخواست منتفی می شود.• درخواست ها از صف بیرون کشیده می شوند و در فواصل زمانی معین پردازش می شوند. شکل 4-7 نحوه عملکرد الگوریتم را توضیح می دهد.الگوریتم سطل نشت دو پارامتر زیر را می گیرد:• اندازه سطل: برابر با اندازه صف است. صف درخواست ها را برای پردازش با نرخ ثابت نگه می دارد.• نرخ خروج: تعیین می کند که چه تعداد درخواست را می توان با نرخ ثابت، معمولاً در چند ثانیه، پردازش کرد.Shopify، یک شرکت تجارت الکترونیک، از سطل های نشتی برای محدود کردن نرخ استفاده می کند [7].مزایا(Pros):• حافظه کارآمد با توجه به اندازه صف محدود.• درخواست ها با یک نرخ ثابت پردازش می شوند، بنابراین برای موارد استفاده که نرخ خروجی پایدار مورد نیاز است مناسب است.معایب(Cons):• انبوهی از ترافیک، صف را با درخواست های قدیمی پر می کند، و اگر به موقع به آنها رسیدگی نشود، درخواست های اخیر دارای نرخ محدود خواهند بود.• دو پارامتر در الگوریتم وجود دارد. ممکن است تنظیم صحیح آنها آسان نباشد.الگوریتم شمارنده پنجره ثابت(Fixed window counter algorithm)الگوریتم شمارنده پنجره ثابت به صورت زیر عمل می کند:• الگوریتم جدول زمانی را به پنجره های زمانی با اندازه ثابت تقسیم می کند و برای هر پنجره یک شمارنده اختصاص می دهد.• هر درخواست شمارنده را یک عدد افزایش می دهد.• هنگامی که شمارنده به آستانه از پیش تعریف شده رسید، درخواست های جدید حذف می شوند تا زمانی که یک پنجره زمانی جدید شروع شود.اجازه دهید از یک مثال عینی استفاده کنیم تا ببینیم چگونه کار می کند. در شکل 4-8 واحد زمان 1 ثانیه است و سیستم حداکثر 3 درخواست در ثانیه را می دهد. در هر پنجره دوم، اگر بیش از 3 درخواست دریافت شود، درخواست های اضافی همانطور که در شکل 4-8 نشان داده شده است حذف می شوند.مشکل اصلی این الگوریتم این است که یک رگبار ترافیک در لبه‌های پنجره‌های زمانی می‌تواند باعث درخواست‌های بیشتر از حد مجاز شود. مورد زیر را در نظر بگیرید:در شکل 4-9، سیستم حداکثر 5 درخواست در دقیقه را مجاز می‌سازد و سهمیه موجود در دقیقه دور انسان پسند بازنشانی می‌شود. همانطور که مشاهده شد، پنج درخواست بین ساعت 2:00:00 تا 2:01:00 و پنج درخواست دیگر بین ساعت 2:01:00 تا 2:02:00 وجود دارد. برای پنجره یک دقیقه ای بین ساعت 2:00:30 تا 2:01:30، 10 درخواست ارسال می شود. این دو برابر درخواست های مجاز است.مزایا(Pros):• حافظه کارآمد.• آسان برای درک.• بازنشانی سهمیه موجود در پایان یک پنجره زمانی واحد متناسب با موارد استفاده خاص است.معایب(Cons):• افزایش ترافیک در لبه های یک پنجره می تواند باعث درخواست‌های بیشتر از حد مجاز شود.الگوریتم لاگ پنجره کشویی(Sliding window log algorithm)همانطور که قبلاً بحث شد، الگوریتم شمارنده پنجره ثابت یک مشکل اساسی دارد: اجازه می دهد تا درخواست های بیشتری از لبه های یک پنجره عبور کنند. الگوریتم لاگ پنجره کشویی مشکل را برطرف می کند. به صورت زیر عمل می کند:• الگوریتم درخواست ها را بر اساس(timestamps) پیگیری می کند. داده های مهر زمانی(timestamp) معمولاً در حافظه پنهان(Cache) نگهداری می شوند، مانند مجموعه های مرتب شده Redis [8].• وقتی درخواست جدیدی وارد شد، تمام مُهرهای زمانی قدیمی (outdated) را حذف کنید. مهرهای زمانی منسوخ شده (outdated) به عنوان مهرهای قدیمی‌تر از شروع پنجره زمانی فعلی تعریف می‌شوند.• مُهر زمانی (timestamp) درخواست جدید را به گزارش اضافه کنید.• اگر اندازه گزارش یکسان یا کمتر از تعداد مجاز باشد، درخواست پذیرفته می شود. در غیر این صورت مردود است.ما الگوریتم را با مثالی که در شکل 4-10 نشان داده شده است توضیح می دهیم.در این مثال، محدود کننده نرخ اجازه 2 درخواست در دقیقه را می دهد. معمولاً مُهرهای زمانی(timestamp) لینوکس در لاگ ذخیره می‌شوند. با این حال، نمایش زمان قابل خواندن توسط انسان در مثال ما برای خوانایی بهتر استفاده شده است.• هنگامی که یک درخواست جدید در ساعت 1:00:01 می رسد، گزارش خالی است. بنابراین، درخواست مجاز است.• یک درخواست جدید در ساعت 1:00:30 می رسد، مهر زمانی 1:00:30 در گزارش درج می شود. پس از درج، اندازه سیاهه 2 است، نه بزرگتر از تعداد مجاز. بنابراین، درخواست مجاز است.• یک درخواست جدید در ساعت 1:00:50 می رسد و مهر زمانی در گزارش درج می شود. پس از درج، اندازه گزارش 3 است، بزرگتر از اندازه مجاز 2. بنابراین، این درخواست رد می شود حتی اگر مهر زمانی timestamp در گزارش باقی بماند.• یک درخواست جدید در ساعت 1:01:40 می رسد. درخواست‌هایی در محدوده [1:00:40،1:01:40) در آخرین بازه زمانی هستند، اما درخواست‌هایی که قبل از ساعت 1:00:40 ارسال می‌شوند قدیمی هستند. دو مهر زمانی قدیمی، 1:00:01 و 1:00:30، از گزارش حذف می‌شوند. پس از عملیات حذف، اندازه لاگ 2 می شود. لذا درخواست پذیرفته میشودمزایا(Pros):• محدودیت نرخ اجرا شده توسط این الگوریتم بسیار دقیق است. در هر پنجره متحرک، درخواست ها از حد مجاز تجاوز نمی کنند.معایب(Cons):• الگوریتم حافظه زیادی مصرف می کند زیرا حتی اگر درخواستی رد شود، ممکن است مهر زمانی آن همچنان در حافظه ذخیره شود.الگوریتم شمارنده پنجره کشویی(Sliding window counter algorithm)الگوریتم شمارنده پنجره کشویی یک رویکرد ترکیبی است که شمارنده پنجره ثابت و گزارش پنجره کشویی را ترکیب می کند. الگوریتم را می توان با دو رویکرد متفاوت پیاده سازی کرد. ما در این بخش یکی از پیاده سازی ها را توضیح خواهیم داد و در پایان بخش مرجعی را برای اجرای دیگر ارائه می دهیم. شکل 4-11 نحوه عملکرد این الگوریتم را نشان می دهد.فرض کنید محدود کننده نرخ حداکثر 7 درخواست در دقیقه را می دهد و 5 درخواست در دقیقه قبل و 3 درخواست در دقیقه فعلی وجود دارد. برای یک درخواست جدید که در دقیقه جاری به موقعیت 30% می رسد، تعداد درخواست ها در پنجره چرخشی با استفاده از فرمول زیر محاسبه می شود:• درخواست ها در پنجره فعلی + درخواست ها در پنجره قبلی * درصد همپوشانی پنجره متحرک و پنجره قبلی• با استفاده از این فرمول 3 + 5 * 0.7% = 6.5 درخواست دریافت می کنیم. بسته به مورد استفاده، عدد را می توان به بالا یا پایین گرد کرد. در مثال ما به 6 گرد شده است.از آنجایی که محدود کننده نرخ حداکثر 7 درخواست در دقیقه را می دهد، درخواست فعلی می تواند انجام شود. با این حال، پس از دریافت یک درخواست دیگر، به حد مجاز خواهد رسید.به دلیل محدودیت فضا، در اینجا به اجرای دیگر نمی پردازیم. خوانندگان علاقه مند باید به مطالب مرجع [9] مراجعه کنند. این الگوریتم کامل نیست. مزایا و معایب دارد.مزایا(Pros):• جهش های ترافیک را هموار می کند زیرا نرخ بر اساس میانگین نرخ پنجره قبلی است.• حافظه کارآمد.معایب(Cons):این فقط برای نگاه به پشت پنجره نه چندان دقیق کار می کند. این تقریبی از نرخ واقعی است زیرا فرض می کند درخواست های پنجره قبلی به طور مساوی توزیع شده اند. با این حال، این مشکل ممکن است آنقدرها هم که به نظر می رسد بد نباشد. بر اساس آزمایش‌های انجام‌شده توسط Cloudflare [10]، تنها 0.003٪ از درخواست‌ها به اشتباه مجاز هستند یا در بین 400 میلیون درخواست محدود می‌شوند.معماری سطح بالا (High-level architecture)ایده اصلی الگوریتم های محدود کننده نرخ ساده است. در سطح بالا، ما به یک شمارنده برای پیگیری تعداد درخواست ارسال شده از یک کاربر، آدرس IP و غیره نیاز داریم. اگر شمارنده بزرگتر از حد مجاز باشد، درخواست غیرمجاز است.کانترها را کجا ذخیره کنیم؟ استفاده از پایگاه داده به دلیل کندی دسترسی به دیسک ایده خوبی نیست. کش درون حافظه به این دلیل انتخاب شده است که سریع است و از استراتژی انقضا مبتنی بر زمان پشتیبانی می کند. به عنوان مثال، Redis [11] یک گزینه محبوب برای اجرای محدودیت نرخ است. این یک فروشگاه در حافظه است که دو دستور را ارائه می دهد: INCR و EXPIRE.• : در INCR شمارنده ذخیره شده را 1 افزایش می دهد.• در EXPIR: یک بازه زمانی برای شمارنده تعیین می کند. اگر مهلت زمانی منقضی شود، شمارنده به طور خودکار حذف می شود.شکل 4-12 معماری سطح بالا برای محدود کردن نرخ را نشان می دهد و این کار به شرح زیر است:• کلاینت درخواستی را به میان افزار محدود کننده نرخ می فرستد.• میان افزار محدود کننده نرخ(Rate limiting middleware)، شمارنده را از سطل مربوطه(corresponding bucket) در Redis می آورد و بررسی می کند که آیا به حد مجاز رسیده است یا خیر.• در صورت رسیدن به حد مجاز، درخواست رد می شود.• در صورت عدم رسیدن به حد مجاز، درخواست به سرورهای API ارسال می شود. در همین حال، سیستم شمارنده را افزایش می دهد و آن را به Redis ذخیره می کند.گام سوم: بررسی عمیق طراحی (Design deep dive)طراحی سطح بالا در شکل 4-12 به سوالات زیر پاسخ نمی دهد:• قوانین محدود کننده نرخ چگونه ایجاد می شوند؟ قوانین کجا ذخیره می شوند؟• چگونه به درخواست هایی رسیدگی کنیم که دارای نرخ محدود هستند؟در این بخش ابتدا به سوالات مربوط به قوانین محدود کننده نرخ پاسخ می دهیم و سپس به بررسی استراتژی های رسیدگی به درخواست های محدود با نرخ می پردازیم. در نهایت، ما محدودیت نرخ در محیط توزیع شده، طراحی دقیق، بهینه سازی عملکرد و نظارت را مورد بحث قرار خواهیم داد.قوانین محدود کننده نرخ(Rate limiting rules)در اینجا ما درون یکی از کامپوننت های شرکت Lyft، (Lyft open-sourced their rate-limiting component [12]) نگاه می کنیم و نمونه هایی از محدود کردن نرخ را بررسی می کنیم.در مثال بالا، سیستم به گونه ای پیکربندی شده است که حداکثر 5 پیام بازاریابی در روز مجاز باشد.در اینجا یک مثال دیگر وجود دارد:این قانون نشان می دهد که کلاینت ها مجاز به ورود بیش از 5 بار در 1 دقیقه نیستند. قوانین معمولاً در فایل های پیکربندی نوشته شده و روی دیسک ذخیره می شوندوضعیت خارج از محدودیت نرخ (Exceeding the rate limit)در صورتی که درخواستی با نرخ محدود مواجه شود، APIها کد پاسخ HTTP 429 (درخواست‌های بسیار زیاد) را به کلاینت برمی‌گردانند. بسته به موارد استفاده، ممکن است درخواست‌های با نرخ محدود را در نوبت قرار دهیم تا بعداً پردازش شوند. برای مثال، اگر نرخ برخی از سفارش‌ها به دلیل بارگذاری بیش از حد سیستم محدود باشد، ممکن است آن سفارش‌ها را نگه داریم تا بعداً پردازش شوند.هدرهای محدود کننده نرخ(Rate limiter headers)کلاینت چگونه متوجه می شود که در حال ارسال درخواست بیش از حد است؟ و چگونه یک کلاینت تعداد درخواست‌های باقیمانده مجاز را قبل از خنثی شدن می‌داند؟ پاسخ در هدرهای پاسخ HTTP نهفته است. محدود کننده نرخ هدرهای HTTP زیر را به کلاینتان برمی گرداند:- X-Ratelim-Remaining : تعداد باقیمانده درخواست های مجاز در پنجره.• X-Ratelimit-Limit : نشان می دهد که کلاینت می تواند در هر پنجره زمانی چند تماس برقرار کند.• X- Ratelimit-Retry-After : تعداد ثانیه هایی که باید منتظر بمانید تا بتوانید مجدداً درخواستی را بدون درنگ انجام دهد.هنگامی که یک کاربر درخواست های زیادی ارسال کرده است، خطای 429 بیش از حد درخواست و هدر X-Ratelimit-Retry-After به کلاینت برگردانده می شود.طراحی دقیق و با جزییات(Detailed design)شکل 4-13 طراحی دقیق سیستم را نشان می دهد.• قوانین روی دیسک ذخیره می شوند. کارگران(Workers) اغلب قوانین را از دیسک بیرون می کشند و آنها را در حافظه پنهان ذخیره می کنند.• هنگامی که کلاینت درخواستی را به سرور ارسال می کند، ابتدا درخواست به میان افزار محدود کننده نرخ ارسال می شود.• میان افزارهای محدود کننده نرخ قوانین را از حافظه پنهان بارگذاری می کند. شمارنده ها و آخرین زمان درخواست را از کش Redis واکشی می کند. بر اساس پاسخ، محدود کننده نرخ تصمیم می گیرد:- اگر درخواست محدود به نرخ نباشد، به سرورهای API ارسال می شود.-اگر درخواست با نرخ محدود باشد، محدود کننده نرخ 429 خطای درخواست های بسیار زیاد را به کلاینت برمی گرداند. در این بین، درخواست یا حذف می شود یا به صف ارسال می شود.محدود کننده نرخ در یک محیط توزیع شدهساختن یک محدود کننده نرخ که در یک محیط سرور تک کار می کند کار سختی نیست. با این حال، مقیاس بندی سیستم برای پشتیبانی از چندین سرور و رشته های همزمان داستان متفاوتی است. دو چالش وجود دارد:• شرایط مسابقه(Race Condition)• مشکل همگام سازی(Synchronization issue)شرایط مسابقه(Race condition)یک شرط مسابقه زمانی رخ می دهد که دو نخ به طور همزمان به یک متغیر مشترک دسترسی داشته باشند.همانطور که قبلاً بحث شد، محدود کننده نرخ در سطح بالا به شرح زیر عمل می کند:• مقدار شمارنده را از Redis بخوانید.• بررسی کنید که آیا ( شمارنده + 1 ) از آستانه فراتر رفته است یا خیر.• اگر نه، مقدار شمارنده را 1 در Redis افزایش دهید.شرایط مسابقه می تواند در یک محیط بسیار همزمان اتفاق بیفتد همانطور که در شکل 4-14 نشان داده شده است.فرض کنید مقدار شمارنده در Redis 3 باشد. اگر دو درخواست به طور همزمان مقدار شمارنده را بخوانند قبل از اینکه هر یک از آنها مقدار را به عقب بنویسد، هر کدام شمارنده را یک برابر افزایش داده و بدون بررسی رشته دیگر آن را دوباره می نویسند. هر دو درخواست (رشته ها) معتقدند که مقدار شمارنده صحیح 4 را دارند. با این حال، مقدار شمارنده صحیح باید 5 باشد.قفل ها(Locks) واضح ترین راه حل برای حل شرایط مسابقه هستند. با این حال، قفل ها به طور قابل توجهی سرعت سیستم را کاهش می دهند. دو استراتژی معمولا برای حل مشکل استفاده می شود: اسکریپت Lua [13] و ساختار داده مجموعه های مرتب شده در Redis [8]. برای خوانندگان علاقه مند به این استراتژی ها، به منابع مرجع مربوطه [8] [13] مراجعه کنید.مشکل همگام سازی(Synchronization issue)همگام سازی عامل مهم دیگری است که در یک محیط توزیع شده باید در نظر گرفته شود. برای پشتیبانی از میلیون‌ها کاربر، یک سرور محدودکننده نرخ ممکن است برای مدیریت ترافیک کافی نباشد. هنگامی که چندین سرور محدود کننده نرخ استفاده می شود، همگام سازی مورد نیاز است. به عنوان مثال، در سمت چپ شکل 4-15، کلاینت 1 درخواست ها را به محدود کننده نرخ 1 ارسال می کند، و سرویس گیرنده 2 درخواست ها را به محدود کننده نرخ 2 ارسال می کند. از آنجایی که لایه وب بدون حالت است، کلاینتان می توانند درخواست ها را به یک محدود کننده نرخ متفاوت ارسال کنند. در سمت راست شکل 4-15. اگر همگام سازی اتفاق نیفتد، محدود کننده نرخ 1 حاوی هیچ داده ای در مورد کلاینت 2 نیست. بنابراین، محدود کننده نرخ نمی تواند به درستی کار کند.یکی از راه حل های ممکن استفاده از جلسات چسبنده(sticky sessions) است که به کلاینت امکان می دهد ترافیک را به همان محدود کننده نرخ ارسال کند. این راه حل توصیه نمی شود زیرا نه مقیاس پذیر است و نه انعطاف پذیر. یک رویکرد بهتر استفاده از پایگاه داده متمرکز (centralized data stores) مانند Redis است. طرح در شکل 4-16 نشان داده شده است.بهینه سازی عملکرد(Performance optimization)بهینه سازی عملکرد یک موضوع رایج در طراحی سیستم است. ما دو حوزه را برای بهبود پوشش خواهیم داد.اولاً، راه‌اندازی چند مرکز داده برای محدودکننده نرخ بسیار مهم است، زیرا تأخیر برای کاربرانی که دور از مرکز داده هستند بالا است. اکثر ارائه دهندگان خدمات ابری مکان های سرور لبه زیادی در سراسر جهان ایجاد می کنند. به عنوان مثال، از تاریخ 5/20 2020، Cloudflare دارای 194 سرور لبه توزیع شده جغرافیایی است [14]. برای کاهش تأخیر، ترافیک به طور خودکار به نزدیکترین سرور لبه هدایت می شود.دوم، همگام سازی داده ها با یک مدل سازگاری نهایی. اگر در مورد مدل سازگاری نهایی نامشخص هستید، به بخش "ثبات" در "فصل 6: طراحی فروشگاه با ارزش کلیدی" مراجعه کنید.نظارت (Monitoring)پس از نصب محدود کننده نرخ، جمع آوری داده های تحلیلی برای بررسی اینکه آیا محدود کننده نرخ موثر است یا خیر، مهم است. در درجه اول، ما می خواهیم مطمئن شویم:• الگوریتم محدود کننده نرخ موثر است.• قوانین محدود کننده نرخ موثر هستند.برای مثال، اگر قوانین محدودکننده نرخ بسیار سخت‌گیرانه باشد، بسیاری از درخواست‌های معتبر حذف می‌شوند. در این صورت می خواهیم کمی قوانین را آرام کنیم. در مثالی دیگر، متوجه می‌شویم که محدودکننده نرخ زمانی که افزایش ناگهانی ترافیک مانند فروش فلش وجود دارد، بی‌اثر می‌شود. در این سناریو، ممکن است الگوریتمی را برای پشتیبانی از ترافیک پشت سر هم جایگزین کنیم. سطل توکن در اینجا مناسب است.منبع اصلیhttps://systeminterview.com/scale-from-zero-to-millions-of-users.phpسایر منابع[1] Rate-limiting strategies and techniques: https://cloud.google.com/solutions/rate-limiting- strategies-techniques[2] Twitter rate limits: https://developer.twitter.com/en/docs/basics/rate-limits[3] Google docs usage limits: https://developers.google.com/docs/api/limits[4] IBM microservices: https://www.ibm.com/cloud/learn/microservices[5] Throttle API requests for better throughput:https://docs.aws.amazon.com/apigateway/latest/developerguide/api-gateway-request- throttling.html[6] Stripe rate limiters: https://stripe.com/blog/rate-limiters[7] Shopify REST Admin API rate limits: https://help.shopify.com/en/api/reference/rest- admin-api-rate-limits[8] Better Rate Limiting With Redis Sorted Sets: https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/[9] System Design — Rate limiter and Data modelling: https://medium.com/@saisandeepmopuri/system-design-rate-limiter-and-data-modelling- 9304b0d18250[10] How we built rate limiting capable of scaling to millions of domains:https://blog.cloudflare.com/counting-things-a-lot-of-different-things/[11] Redis website: https://redis.io/[12] Lyft rate limiting: https://github.com/lyft/ratelimit