פוסט זה מסכם את אלגוריתם הקונצנזוס של רפסודה שהוצג במאמר בחיפוש אחר אלגוריתם קונצנזוס מובן מאת דייגו אונגרו וג'ון אוסטרהוט. כל הצעות המחיר למשך נלקחות מאותו נייר.
רַפסוֹדָה:
רפסודה היא אלגוריתם מבוזר של קונצנזוס. זה תוכנן כך שניתן יהיה להבין אותו בקלות. זה פותר את הבעיה לגרום לשרתים מרובים להסכים על מדינה משותפת גם לנוכח כשלים. הסטטוס המשותף הוא בדרך כלל מבנה נתונים הנתמך ביומן משוכפל. אנו זקוקים למערכת לפעולה מלאה כל עוד רוב השרתים נמצאים למעלה.
רפסודה פועלת על ידי בחירת מנהיג באשכול. המנהיג אחראי על קבלת בקשות הלקוח וניהול שכפול היומן לשרתים אחרים. הנתונים זורמים רק בכיוון אחד: ממנהיג לשרתים אחרים.
רפסודה מפרקת את הקונצנזוס לשלוש בעיות משנה:
- בחירת מנהיג: צריך לבחור מנהיג חדש במקרה של כישלון של קיים.
- שכפול יומן: המנהיג צריך לשמור על יומני כל השרתים מסונכרנים עם זה באמצעות שכפול.
- בטיחות: אם אחד השרתים ביצע ערך יומן באינדקס מסוים, אף שרת אחר לא יכול להחיל ערך יומן אחר עבור אינדקס זה.
יסודות:
כל שרת קיים באחת משלוש המדינות: מנהיג, חסיד או מועמד.
בתפעול רגיל יש בדיוק מנהיג אחד וכל השרתים האחרים הם עוקבים. העוקבים הם פסיביים: הם לא מגישים בקשות בעצמם אלא פשוט נענים לבקשות של מנהיגים ומועמדים. המנהיג מטפל בכל בקשות הלקוח (אם לקוח יוצר קשר עם עוקב, העוקב מפנה אותו למנהיג). המדינה השלישית, המועמדת, משמשת לבחירת מנהיג חדש.
רפסודה מחלקת את הזמן למונחיםבאורך שרירותי, כל אחת מהן מתחילה בבחירות. אם מועמד ינצח בבחירות, הוא נשאר המנהיג להמשך הקדנציה. אם ההצבעה מפוצלת, הקדנציה הזו מסתיימת ללא מנהיג.
מספר לטווח מגבירה באופן מונוטוני. כל שרת מאחסן את מספר המונח הנוכחישמתחלף גם בכל תקשורת.
.. אם המונח הנוכחי של שרת אחד קטן מזה של השני, הוא מעדכן את המונח הנוכחי לערך הגדול יותר. אם מועמד או מנהיג מגלים כי כהונתו אינה מעודכנת, היא חוזרת מיד למדינת העוקבים. אם שרת מקבל בקשה עם מספר מונח מעופש, הוא דוחה את הבקשה.רפט עושה שימוש בשתי קריאות פרוצדורות מרחוק (RPC) לביצוע פעולתו הבסיסית.
- RequestVotes משמש את המועמדים במהלך הבחירות
- AppendEntries משמש למנהיגים לשכפול רשומות יומן וגם כדופק (אות לבדיקת שרת או לא - הוא אינו מכיל רשומות יומן)
בחירת מנהיג
המנהיג מעביר מעת לעת פעימות לב לחסידיו לשמור על סמכות. בחירת מנהיג מופעלת כאשר חסיד מתפטר לאחר שהמתין לדופק מהמנהיג. חסיד זה עובר למדינת המועמד ומגדיל את מספר הקדנציה שלו . לאחר שהצביעה לעצמה, היא מוציאה את RPC של RequestVotes במקביל לאחרים באשכול. שלוש תוצאות אפשריות:
- המועמד מקבל קולות מרוב השרתים והופך למנהיג. לאחר מכן הוא מעביר מסר פעימות לב לאחרים באשכול להקים סמכות.
- אם מועמדים אחרים מקבלים RPC של AppendEntries, הם בודקים אםמספר מונח. אם מספר המונח גדול משלהם, הם מקבלים את השרת כמנהיג וחוזרים למצב העוקב. אם מספר המונח קטן יותר, הם דוחים את RPC ועדיין נשארים מועמדים.
- המועמד לא מפסיד ולא מנצח. אם יותר משרת אחד יהפוך למועמד בו זמנית, ניתן לפצל את ההצבעה ללא רוב ברור. במקרה זה בחירות חדשות מתחילות לאחר שאחד המועמדים מתפטר.
שכפול יומן:
ההנחות של בקשות הלקוחות הן כתובות בלבד לעת עתה. כל בקשה מורכבת מפקודה שתבוצע באופן אידיאלי על ידי מכונות המצב המשוכפלות של כל השרתים. כאשר מנהיג מקבל בקשת לקוח, הוא מוסיף אותה ליומן שלו כערך חדש. כל ערך ביומן:
- מכיל את הפקודה שצוינה על ידי הלקוח
- בעל אינדקס לזיהוי מיקום הכניסה ביומן (האינדקס מתחיל מ -1)
- בעל מספר מונח לזיהוי הגיוני מתי נכתב הערך
עליו לשכפל את הערך לכל צמתי העוקבים על מנת לשמור על יומני הרישום. המנהיג מנפיק RPCs של AppendEntries לכל שאר השרתים במקביל. המנהיג מנסה זאת עד שכל העוקבים ישחזרו בבטחה את הערך החדש.
כאשר הערך משוכפל לרוב השרתים על ידי המנהיג שיצר אותו, הוא נחשב מחויב. כל הערכים הקודמים, כולל אלה שיצרו מנהיגים קודמים, נחשבים גם כמחויבים. המנהיג מבצע את הערך לאחר ביצועו ומחזיר את התוצאה ללקוח.
המנהיג שומר על האינדקס הגבוה ביותר שהוא יודע להתחייב ביומן שלו ושולח אותו עם RPC של AppendEntries לעוקבים שלו. לאחר שהחסידים מגלים שהערך בוצע, הוא מחיל את הכניסה על מכונת המדינה שלה לפי הסדר.
Raft שומר על המאפיינים הבאים, המהווים יחד את המאפיין התואם יומן • אם לשני רשומות ביומנים שונים יש אינדקס ומונח זהים, אז הם שומרים את אותה פקודה. • אם לשני רשומות ביומנים שונים יש אותו אינדקס ומונח, אז היומנים זהים בכל הערכים הקודמים.בעת שליחת RPC של AppendEntries, המוביל כולל את מספר המונח ואינדקס הערך שקודם מייד לערך החדש. אם העוקב לא יכול למצוא התאמה לערך זה ביומן שלו, הוא דוחה את הבקשה לצרף את הערך החדש.
בדיקת עקביות זו מאפשרת למנהיג להגיע למסקנה שבכל פעם ש- AppendEntries חוזר בהצלחה ממעקב, יש להם יומנים זהים עד לאינדקס הכלול ב- RPC.
אך יומני המנהיגים והחסידים עשויים להיות לא עקביים מול קריסות מנהיגים.
ב- Raft, המנהיג מטפל בחוסר עקביות בכך שהוא מכריח את יומני העוקבים לשכפל את זה. המשמעות היא שערכים סותרים ביומני העוקבים יוחלפו בערכים ביומן המנהיג.המנהיג מנסה למצוא את האינדקס האחרון בו היומן שלו תואם לזה של העוקב, מוחק ערכים נוספים אם יש, ומוסיף את החדשים.
המנהיג שומר על NextIndex עבור כל עוקב, שהוא האינדקס של ערך היומן הבא שהמוביל ישלח לאותו העוקב. כאשר מנהיג עולה לראשונה לשלטון, הוא מאתחל את כל ערכי nextIndex לאינדקס מיד לאחר האחרון ביומן שלו.בכל פעם ש- AppendRPC חוזר עם כישלון לעוקב, המנהיג מקטין את ה- Index הבאומנפיק RPC נוסף של AppendEntries. בסופו של דבר, nextIndexיגיע לערך שבו היומנים מתכנסים. כניסות Append יצליחו כאשר זה קורה וזה יכול להסיר ערכים זרים (אם יש כאלה) ולהוסיף חדשים מתוך יומן המנהיגים (אם בכלל). לפיכך, נספח מצליח של חסיד מבטיח כי יומן המנהיג תואם אתו.
באמצעות מנגנון זה, מנהיג אינו צריך לנקוט בפעולות מיוחדות בכדי להחזיר את עקביות היומן בכל הנוגע לשלטון. זה פשוט מתחיל לפעולה רגילה והיומנים מתכנסים אוטומטית בתגובה לכשלים בבדיקת העקביות של הוספות. מנהיג לעולם אינו מחליף או מוחק רשומות ביומן שלו.בְּטִיחוּת:
רפט מוודא שהמנהיג לתקופת כהונה ביצע רשומות מכל הקדנציות הקודמות ביומן שלו. זה נדרש כדי להבטיח שכל היומנים יהיו עקביים ומכונות המדינה מבצעות את אותה קבוצה של פקודות.
במהלך בחירות למנהיגות, RPC RequestVote כולל מידע על יומן המועמד. אם הבוחר מוצא שהוא מתעדכן את המועמד יותר, הוא לא מצביע עבורו.
רפסודה קובעת איזה משני היומנים מעודכן יותר על ידי השוואת האינדקס והטווח של הערכים האחרונים ביומנים. אם ביומנים יש ערכים אחרונים עם מונחים שונים, הרי שהיומן עם המונח המאוחר יותר מעודכן יותר. אם היומנים מסתיימים באותו מונח, אז יומן הימים הארוך ביותר הוא מעודכן יותר.חברות באשכול:
כדי שמנגנון שינוי התצורה יהיה בטוח, לא חייבת להיות נקודה במהלך המעבר שבה ניתן לבחור שני מנהיגים לאותה קדנציה. למרבה הצער, כל גישה בה השרתים עוברים ישירות מהתצורה הישנה לתצורה החדשה אינה בטיחותית.רפסודה משתמשת בגישה דו-שלבית לשינוי חברות באשכולות. ראשית, הוא עובר לתצורת ביניים הנקראת קונצנזוס משותף. ואז, ברגע שזה מחויב, הוא עובר לתצורה החדשה.
הקונצנזוס המשותף מאפשר לשרתים בודדים לעבור בין תצורות בזמנים שונים מבלי לפגוע בבטיחות. יתר על כן, קונצנזוס משותף מאפשר לאשכול להמשיך לשרת בקשות לקוח לאורך כל שינוי התצורה.קונצנזוס משותף משלב בין תצורות חדשות וישנות כדלקמן:
- ערכי יומן משוכפלים לכל השרתים בשתי התצורות
- כל שרת ישן או חדש יכול להפוך למוביל
- ההסכם דורש רוב נפרד מתצורות ישנות וחדשות כאחד
כאשר מנהיג מקבל הודעת שינוי תצורה, הוא שומר ומשכפל את הערך להצטרפות לקונצנזוס C
ויזואליזציה נהדרת של אופן עבודתו של רפסודה ניתן למצוא כאן.
ניתן למצוא כאן חומר נוסף כגון שיחות, מצגות, מאמרים קשורים ויישומי קוד פתוח.
חפרתי רק בפרטי האלגוריתם הבסיסי המרכיב את רפסודה ואת ערבויות הבטיחות שהוא מספק. המאמר מכיל הרבה יותר פרטים והוא נגיש במיוחד מכיוון שהמטרה העיקרית של המחברים הייתה הבנה. אני בהחלט ממליץ לך לקרוא אותו גם אם מעולם לא קראת מאמר אחר לפני כן.
אם נהנית ממאמר זה, לחץ על כפתור המחיאות למטה כדי שאנשים נוספים יראו אותו. תודה.
נ.ב - אם הצלחת להגיע עד כה ותרצה לקבל דואר בכל פעם שאפרסם אחד מהפוסטים האלה, הירשם כאן.