נעילה מבוזרת באמצעות Redis

היי הבר!

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

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

ישנן מספר ספריות ופוסטים שמתארים כיצד ליישם DLM (Distributed Lock Manager) באמצעות Redis, אך כל ספריה נוקטת בגישה שונה והערבות שהן מספקות חלשות למדי בהשוואה למה שניתן להשיג עם עיצוב מעט יותר מתוחכם.

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

יישום

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

• Redlock-rb (יישום עבור רובי). יש גם מזלג Redlock-rb, שמוסיף חבילה (פנינה) לנוחות ההפצה, ולא רק בשביל זה.
• Redlock-py (יישום Python).
• אייורדלוק (יישום עבור Asyncio Python).
• Redlock-php (יישום עבור PHP).
• PHPRedisMutex (יישום נוסף עבור PHP)
• cheprasov/php-redis-lock (ספריית PHP למנעולים)
• סינכרון אדום (יישום עבור Go).
• רדיסון (יישום עבור Java).
• Redis::DistLock (יישום עבור Perl).
• Redlock-cpp (יישום עבור C++).
• Redlock-cs (יישום עבור C#/.NET).
• RedLock.net (יישום עבור C#/.NET). עם תמיכה בהרחבות אסינכרון ונעילה.
• סקרלט לוק (יישום עבור C# .NET עם מאגר נתונים ניתן להגדרה)
• Redlock4Net (יישום עבור C# .NET)
• צומת-אדום (יישום עבור NodeJS). כולל תמיכה להארכת מנעולים.

אבטחה וזמינות ערבויות

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

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

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

הדרך הפשוטה ביותר לנעול משאב באמצעות Redis היא ליצור מפתח במופע. בדרך כלל, מפתח נוצר עם אורך חיים מוגבל, זה מושג באמצעות תכונת expires המסופקת ב-Redis, כך שבמוקדם או במאוחר מפתח זה משתחרר (נכס 2 ברשימה שלנו). כאשר הלקוח צריך לשחרר את המשאב, הוא מוחק את המפתח.

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

ברור שבמודל כזה מתרחש מצב גזע:

1. לקוח א' רוכש מנעול על המאסטר.
2. המאסטר נכשל לפני שהזנת המפתח מועברת לעבד.
3. החסיד מקודם למנהיג.
4. לקוח B רוכש נעילה על אותו משאב ש-A כבר נעל. הפרת אבטחה!

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

יישום נכון עם מופע בודד

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

כדי לרכוש מנעול, עשה זאת:

SET resource_name my_random_value NX PX 30000

פקודה זו מתקינה מפתח רק אם הוא לא קיים כבר (אופציית NX), עם תקופת תוקף של 30000 אלפיות השנייה (אפשרות PX). המפתח מוגדר ל"myrandomvalue" ערך זה חייב להיות ייחודי בכל הלקוחות ובכל בקשות הנעילה.
בעיקרון, ערך אקראי משמש לשחרור בטוח של המנעול, כאשר סקריפט אומר ל-Redis: הסר את המפתח רק אם הוא קיים והערך המאוחסן בו הוא בדיוק מה שהיה צפוי. זה מושג באמצעות סקריפט Lua הבא:

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

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

מה צריכה להיות המחרוזת האקראית הזו? אני מנחש שזה צריך להיות 20 בתים מ-/dev/urandom, אבל אתה יכול למצוא דרכים פחות יקרות להפוך את המחרוזת לייחודית מספיק למטרות שלך. לדוגמה, זה יהיה בסדר להטמיע את RC4 עם /dev/urandom ולאחר מכן ליצור זרם פסאודו אקראי ממנו. פתרון פשוט יותר כולל שילוב של זמן יוניקס ברזולוציית מיקרו-שניות בתוספת מזהה הלקוח; זה לא כל כך מאובטח, אבל זה כנראה עומד במשימה ברוב ההקשרים.

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

אז דיברנו על דרך טובה לרכוש ולשחרר מנעול. המערכת (אם אנחנו מדברים על מערכת לא מבוזרת המורכבת ממופע בודד וזמין תמיד) מאובטחת. בואו נרחיב את הרעיון הזה למערכת מבוזרת, שבה אין לנו ערבויות כאלה.

אלגוריתם Redlock

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

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

1. מקבל את הזמן הנוכחי באלפיות שניות.
2. מנסה ברצף להשיג נעילה בכל N המקרים, תוך שימוש באותו שם מפתח ובערכים אקראיים בכל המקרים. בשלב 2, כאשר הלקוח מגדיר נעילה על בסיס מופע, הלקוח משתמש בהשהיה כדי לרכוש אותו קצר מספיק בהשוואה לזמן שאחריו הנעילה משוחררת אוטומטית. לדוגמה, אם משך החסימה הוא 10 שניות, ההשהיה עשויה להיות בטווח של ~5-50 מילישניות. זה מבטל את המצב שבו הלקוח יכול להישאר חסום במשך זמן רב בניסיון להגיע לצומת Redis כושל: אם המופע אינו זמין, אז אנו מנסים להתחבר למופע אחר בהקדם האפשרי.
3. כדי לקחת נעילה, הלקוח מחשב כמה זמן חלף; לשם כך, הוא מוריד מערך הזמן בפועל את חותמת הזמן שהתקבלה בשלב 1. אם ורק אם הלקוח הצליח להשיג את הנעילה ברוב המקרים (לפחות 3), ואת הזמן הכולל שלקח עד להשיג את המנעול, פחות ממשך הנעילה, המנעול נחשב כאילו הושג.
4. אם נרכש נעילה, משך הנעילה נחשב כמשך הנעילה המקורי בניכוי הזמן שחלף שחושב בשלב 3.
5. אם הלקוח לא מצליח להשיג את הנעילה מסיבה כלשהי (או שהוא לא הצליח לנעול מופעי N/2+1, או שמשך הנעילה היה שלילי), אז הוא ינסה לבטל את הנעילה של כל המופעים (גם אלו שהוא חשב שהוא לא יכול לחסום ).

האם האלגוריתם אסינכרוני?

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

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

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

נסה שוב על כישלון

כאשר לקוח לא מצליח להשיג מנעול, עליו לנסות שוב לאחר עיכוב אקראי; זה נעשה כדי לבטל סנכרון של לקוחות מרובים המנסים לרכוש נעילה על אותו משאב בו-זמנית (מה שעלול להוביל למצב של "מוח מפוצל" שבו אין מנצחים). בנוסף, ככל שלקוח מנסה להשיג נעילה מהר יותר ברוב מופעי Redis, כך החלון בו יכול להתרחש מצב של מוח מפוצל מצומצם יותר (והצורך בניסיונות חוזרים קטן יותר). לכן, באופן אידיאלי, הלקוח צריך לנסות לשלוח פקודות SET ל-N מופעים בו זמנית באמצעות ריבוי.

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

שחרר את המנעול

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

שיקולי אבטחה

האם האלגוריתם בטוח? בואו ננסה לדמיין מה קורה בתרחישים שונים.

ראשית, נניח שהלקוח הצליח להשיג נעילה ברוב המקרים. כל מופע יכיל מפתח עם אותו אורך חיים לכולם. עם זאת, כל אחד מהמפתחות הללו הותקן במועד אחר, כך שהם יפוג במועדים שונים. אבל, אם המפתח הראשון הותקן בזמן שאינו גרוע מ-T1 (הזמן שאנו בוחרים לפני פנייה לשרת הראשון), והמפתח האחרון הותקן במועד שאינו גרוע מ-T2 (הזמן שבו התגובה התקבלה מהשרת האחרון), אז אנחנו בטוחים שהמפתח הראשון בסט שפג תוקפו ישרוד לפחות MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. כל שאר המפתחות יפוג מאוחר יותר, כך שנוכל להיות בטוחים שכל המפתחות יהיו תקפים בו זמנית לפחות לזמן הזה.

במהלך הזמן שרוב המפתחות נשארים תקפים, לקוח אחר לא יוכל לרכוש את המנעול, מכיוון שפעולות N/2+1 SET NX לא יכולות להצליח אם מפתחות N/2+1 כבר קיימים. לכן, מרגע שנרכש מנעול, לא ניתן לרכוש אותו שוב באותו רגע (הדבר יפר את קניין ההדרה ההדדית).
עם זאת, אנו רוצים לוודא שמספר לקוחות המנסים לרכוש מנעול בו זמנית לא יצליחו בו זמנית.

אם הלקוח נעל את רוב המופעים למשך בערך או יותר ממשך הנעילה המרבי, הוא יחשב את הנעילה כבלתי חוקית ויבטל את הנעילה של המופעים. לכן, עלינו לקחת בחשבון רק את המקרה בו הלקוח הצליח לחסום את רוב המקרים בזמן קצר מתאריך התפוגה. במקרה זה, לגבי הטיעון הנ"ל, במהלך הזמן MIN_VALIDITY אף לקוח לא אמור להיות מסוגל לרכוש מחדש את המנעול. לכן, לקוחות רבים יוכלו לנעול מופעי N/2+1 באותו זמן (שמסתיים בסוף שלב 2) רק כאשר זמן נעילת הרוב היה גדול מזמן ה-TTL, מה שהופך את הנעילה לפסולה.

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

שיקולי נגישות

זמינות המערכת תלויה בשלושה מאפיינים עיקריים:

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

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

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

ביצועים, failover ו-fsync

אנשים רבים משתמשים ב-Redis מכיוון שהם זקוקים לביצועים גבוהים של שרת נעילה מבחינת ההשהיה הנדרשת לרכישה ושחרור של מנעולים, ומספר הרכישות/שחרורים שניתן להשלים בשנייה. כדי לעמוד בדרישה זו, קיימת אסטרטגיה לתקשורת עם שרתי N Redis כדי להפחית את זמן האחזור. זוהי אסטרטגיית ריבוי (או "ריבוב של עני", כאשר השקע מועבר למצב לא חוסם, שולח את כל הפקודות וקורא את הפקודות מאוחר יותר, בהנחה שזמן ההליכה הלוך ושוב בין הלקוח לכל מופע דומה) .

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

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

אם תפעיל נתונים קדימה (AOF), המצב ישתפר מעט. לדוגמה, אתה יכול לקדם שרת על ידי שליחת הפקודה SHUTDOWN והפעלה מחדש שלו. מכיוון שפעולות תפוגה ב- Redis מיושמות באופן סמנטי בצורה כזו שהזמן ממשיך לזרום גם כשהשרת כבוי, כל הדרישות שלנו בסדר. זה נורמלי כל עוד מובטחת כיבוי קבוע. מה לעשות במקרה של הפסקות חשמל? אם Redis מוגדר כברירת מחדל, עם סנכרון fsync בדיסק כל שנייה, אז יתכן שאחרי הפעלה מחדש לא יהיה לנו את המפתח שלנו. תיאורטית, אם ברצוננו להבטיח אבטחת נעילה במהלך הפעלה מחדש של מופע כלשהו, ​​עלינו להפעיל fsync=always בהגדרות לאחסון נתונים לטווח ארוך. זה יהרוג לחלוטין את הביצועים, עד לרמה של מערכות CP המשמשות באופן מסורתי ליישום מאובטח של מנעולים מבוזרים.

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

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

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

אנו מגדילים את זמינות האלגוריתם: אנו מרחיבים את החסימה

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

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

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

מקור: www.habr.com