לתכנן Rate Limiter מבוזר: מי סופר את הבקשות?

החלטנו להגביל כל לקוח ל־100 בקשות בדקה. נשמע פשוט: מחזיקים מונה, מגדילים אותו בכל בקשה, וכשמגיעים למגבלה מפסיקים לאשר בקשות נוספות.

עכשיו נוסיף עוד שני שרתים.

אם כל שרת סופר בנפרד, אותו לקוח יכול לקבל בפועל שלוש מכסות. מבחינת כל שרת הכול תקין. מבחינת המערכת, אפשרנו פי שלושה ממה שהתכוונו.

אבל עוד לפני שנחליט איפה לשמור את המונה, יש שאלה פחות מובנת מאליה: מה בדיוק פירוש ההגבלה שלנו?

האם מדובר ב־100 בקשות בכל דקה שמתחילה בשעון? בכל רצף של 60 שניות? ואולי אנחנו רוצים לאפשר הרבה בקשות שמגיעות כמעט בבת אחת, כל עוד הלקוח לא ממשיך בקצב הזה לאורך זמן?

אלה דרישות שונות. כדי לבחור אלגוריתם, צריך קודם להבין איזו התנהגות אנחנו רוצים לקבל.

מה אנחנו מגבילים, ולמי?

מנגנון Rate Limiting מחליט אם לאפשר בקשה בהתאם למדיניות שהגדרנו. למשל, לכל משתמש מותר לבצע מספר מסוים של פעולות בפרק זמן נתון.

המטרה יכולה להיות הגנה על משאבי המערכת, חלוקה הוגנת בין לקוחות או הגבלת שימוש בשירות חיצוני שעולה לנו כסף.

לצורך הדוגמה נחשוב על API שמשרת מערכת ניהול. כשמשתמש פותח מסך, יכולות להישלח כמעט בבת אחת כמה בקשות: לפרטי החשבון, להרשאות, להתראות ולנתונים שמוצגים במסך. אנחנו רוצים לאפשר את זה, אבל לא לאפשר לאותו לקוח להמשיך לשלוח בקשות בקצב גבוה לאורך זמן.

וההגבלה צריכה לחול על הלקוח גם כשהבקשות שלו מגיעות לשרתים שונים.

אגב, גם המילה ״לקוח״ דורשת החלטה.

אפשר לזהות אותו לפי משתמש מחובר, מפתח API או כתובת IP. כתובת IP שימושית כשאין הזדהות, אבל כמה משתמשים מאותו משרד יכולים לצאת לרשת דרך אותה כתובת. אם נגביל אותה, הם יחלקו את אותה מכסה.

מצד שני, אי אפשר פשוט לקבל מהבקשה מזהה משתמש ולסמוך עליו. את המזהה צריך להפיק מהזדהות מאומתת. גם כותרות שמייצגות את כתובת המקור צריך לקבל רק מ־Proxy שאנחנו סומכים עליו.

חלון קבוע: Fixed Window

נתחיל מהאפשרות הפשוטה ביותר.

מחלקים את הזמן לחלונות קבועים, למשל דקות. לכל לקוח שומרים מונה עבור הדקה הנוכחית. כל בקשה שאושרה מגדילה אותו, ובתחילת הדקה הבאה מתחילים מכסה חדשה.

כך יכול להיראות המידע:

customer-42 | 12:00 | 100
customer-42 | 12:01 | 0

זה פשוט למימוש וחסכוני בזיכרון. הבעיה מופיעה בגבול שבין החלונות.

לקוח שולח 100 בקשות ב־12:00:59, ועוד 100 ב־12:01:00.

בכל דקה הוא עמד במגבלה. בפועל, המערכת קיבלה 200 בקשות בתוך זמן קצר מאוד.

אין כאן טעות בספירה. המנגנון אוכף את מה שהגדרנו: מכסה לכל דקה קבועה. הוא לא אוכף מכסה לכל רצף אפשרי של 60 שניות.

אם ההתנהגות הזאת מקובלת עלינו, ייתכן שאין צורך במשהו מורכב יותר. אם לא, נצטרך לשנות את אופן הספירה.

לספור את הבקשות עצמן: Sliding Window Log

במקום לשמור רק מונה, נשמור את זמן ההגעה של כל בקשה שאושרה.

כשמגיעה בקשה חדשה, נסתכל על 60 השניות האחרונות ביחס לרגע הזה:

1. נסיר רשומות שכבר נמצאות מחוץ לחלון.
2. נספור את הרשומות שנותרו.
3. אם נשאר מקום במכסה, נוסיף את הבקשה ונאשר אותה.

מעבר לדקה חדשה כבר לא נותן מכסה חדשה בבת אחת. בקשה מפסיקה להיספר רק כשהיא יוצאת מהחלון.

ב־Redis אפשר לייצג את המידע באמצעות Sorted Set: זמן הבקשה משמש לציון שלפיו ממיינים, ולכל רשומה יש מזהה ייחודי. המזהה חשוב, כי כמה בקשות יכולות להגיע עם אותה חותמת זמן, ועדיין צריך לספור את כולן.

היתרון הוא דיוק. המחיר הוא שמירת רשומה לכל בקשה שאושרה בחלון, לצד העבודה שנדרשת לניקוי ולספירה.

ויש כאן דיוק נוסף: האלגוריתם לא מבטיח פיזור אחיד של הבקשות. אם החלון ריק והמכסה היא 100, אפשר לאשר 100 בקשות מיד. הוא מונע חריגה מהמכסה בחלון הנע, לא הגעה של הרבה בקשות בבת אחת.

לשמור פחות מידע: Sliding Window Counter

אפשר להתקרב להתנהגות של חלון נע בלי לשמור את כל זמני הבקשות.

בגרסה הזאת שומרים שני מונים: אחד לחלון הנוכחי ואחד לחלון הקודם. את תרומת החלון הקודם מחשבים לפי החלק שלו שעדיין חופף לפרק הזמן שאנחנו בודקים.

לדוגמה, עברו 15 שניות מתחילת הדקה. ב־60 השניות האחרונות נכללות כל 15 השניות של הדקה הנוכחית, ועוד 45 שניות מהדקה הקודמת.

אם בדקה הקודמת היו 80 בקשות, ובנוכחית היו 20:

Previous window count = 80
Current window count  = 20
Previous window weight = 45 / 60 = 0.75

Estimated count = 80 × 0.75 + 20 = 80

זו הערכה של מספר הבקשות בחלון הנע. כדי לבדוק בקשה נוספת שעלותה אחת, נבדוק אם ההערכה בתוספת אחת עדיין עומדת במכסה.

למה רק הערכה? כי אנחנו לא יודעים מתי בתוך הדקה הקודמת הגיעו הבקשות.

אם כולן הגיעו בתחילתה, ייתכן שכבר יצאו מהחלון. אם הגיעו בסופה, ייתכן שכולן עדיין בתוכו. מבחינת המונה, שני המצבים זהים.

חסכנו זיכרון, אבל ויתרנו על ספירה מדויקת. בהרבה מערכות זו פשרה סבירה, כל עוד לא מציגים אותה כהבטחה קשיחה.

במקום לספור לאחור, נותנים תקציב: Token Bucket

עד עכשיו בדקנו כמה בקשות הגיעו בפרק זמן מסוים.

ב־Token Bucket מסתכלים על הבעיה אחרת: כמה בקשות מותר ללקוח לבצע עכשיו?

לכל לקוח יש דלי שמכיל אסימונים. כל בקשה צורכת אסימון, והתקציב מתחדש בקצב קבוע, עד לתקרה.

יש כאן שני פרמטרים נפרדים:

• קיבולת הדלי: כמה בקשות אפשר לאשר כמעט בבת אחת כשהוא מלא.
• קצב המילוי: באיזה קצב התקציב מתחדש, ולכן באיזה קצב אפשר להמשיך לאורך זמן.

נבחר קיבולת של 20 אסימונים וקצב מילוי של 5 אסימונים בשנייה.

כשהדלי מלא, הלקוח יכול לשלוח 20 בקשות מיד. אם ניצל את כולן, אחרי שנייה יהיו זמינים עוד חמישה אסימונים. אם לא היה פעיל במשך שעה, עדיין יהיו לו רק 20. לא צוברים תקציב ללא הגבלה.

זה מתאים לדוגמה שלנו: אפשר לטעון כמה רכיבים יחד כשפותחים מסך, אבל אי אפשר להמשיך באותו קצב ללא הפסקה.

לא צריך טיימר לכל לקוח

המילוי לא חייב להתבצע באמצעות פעולה שרצה ברקע.

אפשר לשמור את מספר האסימונים ואת זמן העדכון האחרון, ולחשב את היתרה כשמגיעה בקשה:

elapsed = now - lastUpdated

tokens = min(
    capacity,
    tokens + elapsed × refillRate
)

לאחר מכן בודקים אם יש מספיק אסימונים, מפחיתים את עלות הבקשה אם אושרה, ושומרים את היתרה ואת זמן העדכון.

זהו חישוב של מילוי רציף, ולכן היתרה יכולה לכלול גם שבר של אסימון. בקשה שעלותה אסימון אחד תאושר רק כשיש לפחות אחד שלם.

אפשר גם לתת עלויות שונות לפעולות שונות. למשל, בקשת קריאה פשוטה תצרוך אסימון אחד, והפקת דוח יקר תצרוך חמישה. במקרה כזה אנחנו מגבילים תקציב עבודה, ולא רק מספר בקשות.

זו לא מכסה קשיחה בחלון נע

קיבולת של 100 אסימונים ומילוי של 100 אסימונים בדקה אינם מבטיחים לכל היותר 100 בקשות בכל 60 שניות.

הלקוח יכול להתחיל עם דלי מלא, לנצל אותו, ולהמשיך לנצל אסימונים שמתחדשים במהלך הדקה.

במודל הרציף, עבור בקשות בעלות של אסימון אחד, הגבול לאורך פרק זמן הוא:

Allowed requests ≤ capacity + refillRate × elapsed

כלומר, יש תקציב לבקשות שמגיעות יחד ועוד תקציב שנצבר לאורך הזמן. זו בדיוק ההתנהגות שבחרנו, לא חריגה מקרית.

איפה ממקמים את המנגנון?

במערכת שלנו נמקם את בדיקת הקצב ב־API Gateway, לפני העברת הבקשה לשירות העסקי. כך בקשה שנחסמה לא תגיע מלכתחילה לחלק היקר של הטיפול.

זו לא האפשרות היחידה. אפשר לממש את הבדיקה בתוך האפליקציה או בשירות ייעודי. אבל Gateway מתאים כשאנחנו רוצים להחיל מדיניות משותפת על כמה שירותים.

עד כאן נשמע שריכזנו את הבעיה במקום אחד. אלא שגם ה־Gateway יכול לרוץ בכמה מופעים.

אם לכל מופע יהיה דלי משלו, חזרנו לנקודת ההתחלה.

לכן נשמור את מצב הדליים במאגר משותף, למשל Redis. לכל לקוח ולכל מדיניות יהיה מפתח משלו:

rate-limit:customer-42:orders-api

כל מופעי ה־Gateway יבדקו ויעדכנו את אותו מצב.

המילה ״משותף״ חשובה כאן, אבל היא עדיין לא מספיקה.

אסימון אחד, שתי בקשות

נשאר בדלי אסימון אחד. שתי בקשות של אותו לקוח מגיעות במקביל לשני מופעי Gateway.

שניהם קוראים את היתרה. שניהם רואים אסימון. שניהם מאשרים.

אפשר לחשוב שנפתור את זה באמצעות טרנזקציה בזמן השמירה:

Read current state
Calculate new state

MULTI
    Save tokens
    Save lastUpdated
EXEC

אבל הקריאה נעשתה לפני הטרנזקציה. שתי הבקשות עדיין יכולות לחשב את ההחלטה על בסיס אותה יתרה.

העדכונים נשמרו יחד, אבל ההחלטה התקבלה על מידע שכבר לא בהכרח היה עדכני.

מה שצריך להיות אטומי הוא כל הרצף:

Read
→ Calculate refill
→ Check available tokens
→ Consume if allowed
→ Save

איך Redis עוזר לנו לבצע את הכול יחד?

עד עכשיו התייחסנו ל־Redis כמקום משותף לשמירת היתרה. אבל Redis הוא שירות שמסוגל גם לבצע פעולות על הנתונים שהוא שומר, ולא רק להחזיר אותם לאפליקציה.

אחת האפשרויות שלו היא להריץ קטע קוד בשפה שנקראת Lua. זו שפת תכנות שאפשר לשלב בתוך תוכנות אחרות, ובמקרה שלנו Redis הוא שמריץ את הקוד.

במקום שה־Gateway יבקש מ־Redis את היתרה, יחשב בעצמו אם לאשר את הבקשה ואז ישלח עדכון, הוא מבקש מ־Redis לבצע את התהליך כולו:

״קרא את היתרה של הלקוח, חשב כמה אסימונים נוספו מאז העדכון האחרון, בדוק אם יש מספיק לבקשה, ואם כן הפחת אסימון. שמור את התוצאה והחזר לי אם הבקשה אושרה״.

את ההוראות האלה אנחנו כותבים בסקריפט Lua.

היתרון החשוב כאן אינו השפה עצמה, אלא האופן שבו Redis מריץ את הסקריפט: פקודות של בקשות אחרות לא משתלבות באמצע הביצוע שלו.

נחזור למקרה שבו נשאר אסימון אחד ושתי בקשות מגיעות יחד. הסקריפט של הבקשה הראשונה יבדוק את היתרה ויפחית את האסימון. רק לאחר שיסיים, הסקריפט של הבקשה השנייה יוכל לבדוק את המצב, וכעת הוא יראה שהאסימון כבר נוצל.

זה מה שהתכוונו אליו במילה ״אטומי״: מבחינת הבקשות האחרות, הבדיקה והעדכון מתבצעים כפעולה אחת, בלי אפשרות להיכנס ביניהם.

לכן גם חשוב שהסקריפט יהיה קצר ויעשה רק את העבודה הנחוצה. בזמן שהוא רץ, הוא מעכב ביצוע של פקודות אחרות באותו שרת Redis. את הטיפול העסקי בבקשה נשאיר באפליקציה; כאן אנחנו רק מחליטים אם מותר לה להמשיך.

גם את הזמן כדאי לחשב ממקור משותף, למשל באמצעות שעון Redis, במקום להסתמך על שעונים שונים של שרתי האפליקציה.

מה מחזירים כשאין תקציב?

בקשה שנחסמה בגלל המכסה תקבל תשובה:

HTTP/1.1 429 Too Many Requests
Retry-After: 1

בדוגמה הזאת ביקשנו מהלקוח להמתין שנייה לפני ניסיון נוסף.

ב־Token Bucket אפשר להעריך את ההמתנה עד שיהיו מספיק אסימונים לפי החוסר וקצב המילוי. זו אינה שמירת מקום: בקשות אחרות של אותו לקוח יכולות לצרוך את האסימונים בינתיים.

כדאי להחזיר גם הסבר ברור בגוף התשובה. מבחינת הלקוח, יש הבדל בין בקשה לא תקינה, תקלה בשרת ומכסה שנוצלה. אנחנו רוצים שהוא יגיב בהמתנה, לא בלולאה ששולחת מיד עוד בקשות ומחמירה את העומס.

ומה קורה כשהמאגר המשותף לא זמין?

הוספנו למערכת רכיב שכל בקשה תלויה בו. צריך להחליט מראש מה נעשה כשאי אפשר לקבל ממנו החלטה.

במדיניות Fail Open נאפשר לבקשה להמשיך למרות התקלה. השירות נשאר זמין, אבל ההגבלה עלולה לא להיאכף.

במדיניות Fail Closed לא נאפשר לה להמשיך בלי אישור. אנחנו מגינים על המשאבים, במחיר של פגיעה בזמינות.

אפשר גם לעבור זמנית להגבלה מקומית ושמרנית בכל שרת. זו הגנה חלקית, לא תחליף שקול למכסה המשותפת.

בנוסף, אטומיות בזמן פעולה תקינה לא מבטיחה ששום עדכון לא יאבד בזמן כשל. אם מעבר לשרת Redis חלופי עלול לאבד עדכונים שטרם שוכפלו, ייתכן שהיתרה שתשוחזר תהיה גבוהה מדי.

לכן צריך להחליט אם חריגה קטנה בזמן תקלה מקובלת עלינו. הגנה מפני עומס ומכסה כספית קשיחה לא בהכרח דורשות אותן הבטחות.

כשהתעבורה גדלה

מאגר משותף לא חייב להיות שרת יחיד שמחזיק את כל הלקוחות. אפשר לפזר את המפתחות בין כמה שרתי Redis, כך שהבקשות עבור אותו מפתח יגיעו לאותו מקום.

זה מפזר עבודה בין לקוחות, אבל לא פותר כל בעיית עומס. לקוח אחד ששולח כמות חריגה של בקשות עדיין יכול ליצור מפתח חם במיוחד.

גם פעילות בכמה אזורים גאוגרפיים מחייבת החלטה: פנייה למקום משותף מרוחק מוסיפה השהיה, ואילו מכסה עצמאית בכל אזור לא אוכפת אוטומטית מכסה גלובלית.

אפשר לחלק תקציב בין אזורים או להקצות אסימונים בקבוצות למופעים מקומיים, אבל אז צריך לטפל בהקצאה, בניצול ובכשל של כל חלק. לא מתחילים מהמורכבות הזאת אם אין בה צורך.

אז במה הייתי בוחר?

למערכת שתיארנו הייתי בוחר ב־Token Bucket.

הוא מאפשר לנו להגדיר בנפרד כמה בקשות מותר לשלוח כמעט בבת אחת ובאיזה קצב אפשר להמשיך לאורך זמן, שומר מעט מידע לכל לקוח, ולא דורש יומן של כל הבקשות.

אבל אם הדרישה הייתה ״לא יותר מ־100 בקשות בכל רצף של 60 שניות״, הייתי בוחן Sliding Window Log. אם הערכה מספיקה ורוצים לחסוך בזיכרון, Sliding Window Counter הוא מועמד מתאים. ואם מכסה בחלונות קבועים עונה על הצורך, גם Fixed Window יכול להספיק.

לפני העלאה לסביבת ייצור הייתי בודק לפחות שלושה מצבים: הרבה בקשות שמגיעות יחד כשהדלי מלא, תעבורה רציפה אחרי שהתרוקן, ושתי בקשות שמגיעות לשרתים שונים כשנשאר אסימון אחד.

את המקרה האחרון כדאי לבדוק במקביליות אמיתית. קל מאוד לכתוב מנגנון שעובד כשבקשות מגיעות אחת אחרי השנייה. הבעיה שבגללה התחלנו את כל התכנון הזה היא שהן לא חייבות להגיע ככה.