رتبها

في ال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 بتتأجر بفلوس يمكن توفيرها.

لو حنعمل system design ل api rate limiter ف محتاجين نحط assumptions
1- يمنع الrequests اللي بتكسر الpolicy بتاعة الrate limiter
2- ميستعملش 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 بتاع التيم

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

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
ده ببساطة بيقول ان كل دقيقة حيبقى فيه 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 بتاع كل ريكوست و عارف فاضله قد ايه.
و ده كان إزاي نعمل API rate limiter .. أتمنى تكونوا إستمتعتوا and hope you found it useful 😊
دي مدونتي مكتوب فيها نفس الكلام
#heading-5-sliding-windows-counter-algorithm" target="_blank" rel="noopener" onclick="event.stopPropagation()">krietallo.hashnode.dev

krietallo.hashnode.dev/api-rate-limit…

API Rate Limiter

‫ في الNetwork system بيبقى فيه حاجة اسمها API Rate Limiter و ده بيبقى موجود عشان يتحكم في عدد الreq...

و دي المصادر لو حابين تقروا أكتر عن الموضوع :))
أتمنى تكونوا إستدفتدوا و دي المصادر
System Design Interview Book: Alex Xu
engineering.classdojo.com tutorialspoint.com enjoyalgorithms.com thetechnicaltalk.com wpbeginner.com redis.io

thetechnicaltalk.com/2019/12/differ…