API Rate Limiter

‫ في الNetwork system بيبقى فيه حاجة اسمها API Rate Limiter و ده بيبقى موجود عشان يتحكم في عدد الrequests اللي طالعة من الclient في فترة معينة و لو عدد الrequests زاد ف بيتعملهم block و الrequest مش حيعدي

‫ فوايد الRate limiter حاجتين:

‫ 1- بيمنع الDenial of Service (DoS) attack .. تقريبًا كل الAPIs بتاعة الشركات الكبيرة بتبقى محمية ب rate limiter عشان تبقى شغالة .. على سبيل المثال تويتر بيlimit عدد التويتات بحيث متعديش 300 تويتة في 3 ساعات و Google docs بيمنع أكتر من users 300 يعملوا Read requests في خلال دقيقة.

‫ 2- السبب التاني و هو الفلوس و تقليل الcost .. زي chatGPT لما بدأ يبطأ أو يقلل من الrequests عشان الrequest بتاعه مكلّف انه ي process السؤال و يجاوب و كل دي servers بتتأجر بفلوس يمكن توفيرها.

Assumptions

‫ 1- لو حنعمل system design ل api rate limiter ف محتاجين نحط assumptions

‫ 2- يمنع الrequests اللي بتكسر الpolicy بتاعة الrate limiter

‫ 3- ميستعملش memory كتير

‫ 3- ينفع يتم استعماله في distributed system environment

‫ 4- fault tolerant

‫ عشان لو وقع ف الAPI حيبقى في خطر من الDoS attack

5- low latency ‫ مش معقول ابقى باعت request من الclient و الclient يبقى مستني كتير عشان الrequest لسه حنشوفه لو مسموحله يعدي و بعدين يعدي علينا الجمعة نكون proccessنا الrequest أصلًا عايز إيه

‫ 6- Exception handling انا ك user محتاج feedback لو الAPI request بتاعي اتعمله block و ياريت يبقى فيه رسالة تقولي ايه اللي حصل .. ف الHTTP Code ده بيبقى كود 429 Too many requests

‫ طيب هل نحط الrate limiter ف الclient ولا الserver side ?

‫ الأفضل ف الserver side عشان لو احنا مجرد رجعنا JS للكلاينت ف إحنا ف عرضة انهم يكتشفوا ثغرة و يعدلوه قبل ما يبعتوا الrequest و يهجموا ف DoS attack إنما ف السيرفر ف الورق ورقنا و الدفاتر دفاترنا

‫ فيه حاجة إسمها API Gateway و دي مسئولة عن الSSL Termination authentication و ممكن يتعمل whitelisting او blacklisting لل IPs اللي داخلة تعمل الrequest و ده بيبقى إختيار كويس نحط الAPI limiter بتاعنا فيه

‫ ممكن برضه نحط الlimiter قدام كل الservers لو احنا شغالين monolith او نحطه قدام كل microservice

.. ده بيعتمد على ال architecture بتاعة الشركة + الstack بتاع التيم

Algorithms

‫ فيه 5 algorithms مشهورين للrate limiter حنعدي عليهم بسرعة و نقول الpros &cons

1- Token bucket algorithm

‫ 1- Token bucket algorithm ‫ بيبقى فيه bucket (ممكن نستعمل stack ك datastructer) و بيبقى فيها عدد معين من الtokens احنا بنحدده .. الrequest بيجي الapi limiter و يشوف لو فيه tokens

ف الbucket ولا لأ.

‫ لو فيه ف بياخد token و عدد الtokens ف الbucket بينقص واحد و الrequest يتعمله routing للapi اللي كان عايزه و يديله الtoken عشان يثبت انه حلال و عدى على الrate limiter قبل ما يجيله. ‫ لو مفيش tokens كفاية ف الrequest بتعمله drop و بنرجع رسالة لليوزر بده.

‫ ممكن نحدد ان كل x minutes بنpopulate الbucket بtokens جديدة عشان الrequests التانية و ده بيبقى worker بنسميه refiller ‫ ف كده بيبقى عندنا 2 parameters و هما الbucket size و الrefill rate اللي بيملى الbucket ب tokens لما بيفضى

pros:

easy to implement
memory effecient ‫ و لو فيه spike ف الrequests ف مفيش مشاكل و مش حيحصل throttling او إختناق طالما فيه tokens

cons: ‫ فيه 2 parameters و ده ممكن يخلق مشاكل للsynchronization و حنشوف ده قدام

2- Leaking bucket algorithm

‫ شبه الtoken bucket لكن ده بيبقى queue فيه عدد معين من الrequests ‫ الrequests بتخش First In First Out (FIFO) ‫ لو الqueue مش مليان ف بيخشه على طول ‫ لو الqueue مليان ف بيتعمل drop للrequest

‫ و فيه fixed rate بعد فترة زمنية معينة بيتعمل processing للrequests واحد ورا التاني

pros:

memory effecient ‫ و لو الuse case بتاعتك انك ضامن ان ميحصلش spike ف الtraffic (زي امازون وقت الجمعة البيضاء) ف ده مناسب ليكي

cons: ‫ مش مناسب لو فيه spike ف الtraffic و حيبقى بطيء بسبب اننا بنعمل processing لل requests

ب fixed rate

3- Fixed counter algorithm

‫ 3- Fixed counter algorithm ‫ ده ببساطة بيقول ان كل دقيقة حيبقى فيه x number of tokens متاحين .. لو خلصوا ف حتستنى للدقيقة اللي بعدها لو مخلصوش ف خد الtoken و روح عالapi

‫ فيه edge case للalgorithm دي: لنفترض اننا بنسمح ف 5 tokens ف الدقيقة .. و جيت على آخر الدقيقة اللي انا فيها استهلكتهم في آخر 5 ثواني .. بعدين دلوقتي الدقيقة الجديدة إبتدت و فيه 5 tokens جداد و استهلكتهم كلهم برضه في اول 5 ثواني من الدقيقة الجديدة

‫ كده استهلكت 10 tokens في 10 ثواني مع اني المفروض استهلك 5 بس في الدقيقة.

ممكن نحل ده بإننا ن reset الquota في آخر الدقيقة .. بس فيه 2 algorithms باقيين بيحلوا المشكلة دي: ‫

4- ‫ Sliding Window log algorithm ‫

بيبقى فيه memory عشان تخزن الrequest logs ‫
بنخلي الrequest يجي بالtimestamp بتاع لو فيه مكان ف الmemory ‫
لو فيه timestamps اقدم من الcurrent window ف دول بيبقوا outdated و بيتعملهم drop ‫
لو الtimestamps withing الcurrent window ف بنprocessهم

‫ pros: accurate ‫ و بتشتغل زي ما الrate limiter المفروض يشتغل

cons: ‫ بتستهلك memory عشان نخزل الrequests بالlogs .. من أشهر الحاجات اللي بيتم استعمالها هي redis عشان memory effecient و سريعة

5- Sliding windows counter algorithm

‫ و دي hybrid algorithm بين ال Sliding window log و الfixed counter window algorithms ‫ لو افترضنا اننا بن process 12 requests ف الدقيقة .. و الدقيقة اللي فاتت كان فيه 9 requests و الدقيقة الحالية فيه 5 requests و جه request جديد ..

‫ عايزين نعرف نعديه ولا لأ منغير الedge case بتاعة الfixed window counter algorithm ‫ الrequest جه ف الربع الأول من الدقيقة الحالية 25% ‫ ف بنحسب بالforumula دي

Requests in current window + (requests in previous windows * percentage of overlap between the 2 windows)

5 + (9* 25%) = 5 + 2.25 = 7.25 ~= 8 ‫ ف يجوز اننا نعديه عشان الmaximum amount of requests في حالتنا بيبقى 12

‫ جدير بالذكر ان ال HTTP فيه headers مفيدة لل rate limiter

HTTP Headers

X-Ratelimit-Remaining: ‫ عدد الrequests الباقي ف الwindow دي

X-Ratelimit-limit: ‫ أقصى عدد من الrequests المسموح بيه ف time window محددة

X-Ratelimit-Retry-After: ‫ ممكن تجرب تبعت request بعد عدد معين من الثواني

‫ ‫ ‫فيه مشكلتين بنواجهمم ف الrate limiter و هما الrace condition و الsynchronization ‫ الrace condition ممكن نسيب الredis يحله .. كده كده هو single threaded ‫ ف حيتصرف و يحط lock او حاجة لو فيه كذا request ‫ اما مشكلة الsynchronization ف دي ممكن تحصل ف distributed system ‫ ب إني ببعت ريكوست على rate limiter في سيرفر معين .. بعدين ابعت request تاني على سيرفر تاني ب rate limiter تاني ‫ ف كده انا المفروض يبقى بعت 2 requests بس بسبب انفصال الrate limiters ف كده فيه مشكلة synchronization ‫ حل المشكلة دي اننا نستعمل centrilzed cache يبقى عارف الIP بتاع كل ريكوست و عارف فاضله قد ايه

المصادر

أتمنى تكونوا إستدفتدوا و دي المصادر

System Design Interview: Alex Xu engineering.classdojo.com/blog/2015/02/06/r.. tutorialspoint.com/mutex-vs-semaphore enjoyalgorithms.com/blog/design-api-rate-li.. thetechnicaltalk.com/2019/12/differentiate-.. wpbeginner.com/wp-tutorials/how-to-fix-the-.. redis.io/docs/management/optimization/bench..

‫