נושאים בביזור – Distributed Transaction באמצעות 2PC ו- 3PC

אחד ה- primitives העיקריים בעבודה עם DB-ים רלציוניים (ולא רק) זאת הטרנזקציה. טרנזקציה, היא אוסף של פעולות שמובטח לנו שכולן הצליחו להתבצע, או לחלופין שאף אחת מהן לא התבצעה. בואו נניח כעת שאנחנו רוצים לעשות טרנזקציה, שמערבת מס’ רכיבים, שכל אחד מהם בנפרד יודע לעשות טרנזקציה, ואנחנו רוצים לעשות טרנזקציה שכוללת פעולות מול כל אחד ואחד מהרכיבים הללו. למשל, נדמיין שרת Oracle ו- SQL Server (או שני שרתי SQL Server שונים), שאנחנו רוצים לעשות בכל אחד מהם בנפרד רצף פעולות כטרנזקציה.

איך לא עושים Distributed Transaction?

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

SERVER A: BEGIN TRANSACTION
  SERVER B: BEGIN TRANSACTION	
    SERVER A: UPDATE tblA SET Balance = 1 WHERE ID = 1
    SERVER B: UPDATE tblB SET Balance = 1 WHERE ID = 1
  SERVER B: COMMIT TRANSACTION
SERVER A: COMMIT TRANSACTION

בדוגמא הזאת, אנחנו מפעילים טרנזקציה בשני השרתים, ועושים את הפעולה לאחר שהופעלה הטרנזקציה בשני השרתים. אבל – מה קורה עם במקרה הזה, שרת A נופל לאחר ביצוע שורה 5 (ה- COMMIT על שרת B) אבל לפני ביצוע שורה 6 (ה- COMMIT לשרת B)? נשים לב, שבמקרה כזה, כאשר שרת A יעלה בחזרה, הוא יעשה rollback לטרנזקציה שלו, שלא הסתיימה. אולם, הטרנזקציה כבר כן הסתיימה בשרת B – וכך נסיים עם תוצאה לא קונסיסטנטית. שזה לא מה שרצינו.

2PC (2 Phase Commit)

פרוטוקול פופולרי לפיתרון בעיית ה- distributed transaction נקרא two-phase commit, או בשמו המקוצר – 2pc. בפרוטוקול הזה יש לנו שני סוגים של שחקנים:

  • ה- coordinator – מדובר ברכיב שמנהל את התהליך של הטרנזקציה. הרכיב הזה הוא לא (בהכרח) אחד הדטאבייסים שמשתתפים בה, והתפקיד שלו למעשה לתאם בין המשתתפים האחרים. אנחנו מניחים שה- coordinator מחזיק לוג פעולות (WAL), שמאפשר לו גם במקרה של נפילה להמשיך מנק' מסויימת (חשוב עבור חלק מהשלבים).
  • הרכיבים עצמם שעליהם רצה הטרנזקציה – כדי לתמוך בתהליך של 2PC, כל אחד מהם חייב לדעת איך לעשות טרנזקציה. כלומר, חייב לקיים את הדברים הבאים:
    • להחזיק transaction log, שמתעד את כל הפעולות, כאשר כל פעולה מבוצעת עליו קודם לכך שהיא מבוצעת על ה- data עצמו
    • אנחנו מניחים גם שה- transaction log הזה לא יכול ללכת לאיבוד או להיפגם (אם זה יקרה, בפועל זה אומר שאנחנו נאבד את הקונסיסטנטיות).
    • אנחנו מניחים שגם אם node נופל, זה לא יהיה לעד, וה- transaction log שלו שורד נפילות

הפרוטוקול עצמו עובד בצורה הבאה:

  1. הטרנזקציה מתחילה, מול כל אחד מה- nodes בנפרד
  2. בשלב הזה, מבוצעות הפעולות עצמן שאנחנו רוצים לעשות כחלק מהטרנזקציה. למשל, בדוגמא הקודמת שלנו, הפעולות UPDATE מול כל אחד מה- nodes.
  3. לאחר סיום הפעולות, מגיע השלב שבו אנחנו רוצים לעשות את ה- commit. פה בא לידי ביטוי האלמנט של ה- "two phase". במקום ישר לעשות commit, אנחנו מוסיפים שלב נוסף לתהליך שנקרא PREPARE. ה- coordinator שולח לכל ה- nodes הודעת PREPARE, שהמשמעות שלה היא "תגיעו למצב שבו אתם יודעים בוודאות שאתם מסוגלים לעשות COMMIT, לא משנה מה קרה". לאחר ש- node מקבל את הודעת ה- PREPARE, הוא עושה כל מה שהוא צריך כדי לוודא שכשהוא יקבל הודעת COMMIT, היא בוודאות תצליח. אחרי שהוא יודע את זה, הוא שולח הודעת AGREEMENT ל- master.
    מה זה אומר "יודע בוודאות שהוא מסוגל לעשות COMMIT"? זה אומר שאנחנו נהיה במצב שבו אם ה- node יעשה reboot בשלב שלאחר ה- PREPARE, הוא לא יבצע rollback לטרנזקציה, אלא יעשה לה redo עד לאותה הנקודה. אבל, הוא עדיין לא יעשה את ה- COMMIT הסופי לדיסק ויאפשר עדיין ביצוע rollback יזום (שלא באמצעות reboot).
  4. כאן אנחנו מפרידים בין שני המצבים – מצב שבו כל ה- nodes שלחו AGREEMENT  לבין מצב שבו יש איזשהו node ששלח DISAGREEMENT – כלומר, הוא לא הצליח לבצע את ה- PREPARE. מצב אפשרי נוסף, הוא ש-node נעלם באמצע ואנחנו שמים איזשהו timeout על התהליך PREPARE. למצב הזה, אנחנו מתייחסים כאילו הוא שלח DISAGREEMENT.
    1. אם כולם שלחו agreement:
      1. ה- coordinator רושם ב-log הפנימי שלו שהוא הגיע לשלב ה- commit. כלומר, גם אם הוא ייפול, כשהוא יחזור הוא ימשיך בביצוע ה- commit-ים.
      2. ה- coordinator שולח לכולם הודעת COMMIT, כלומר עושים COMMIT לכל אחת מהטרנזקציות
      3. לאחר שכל node הצליח לבצע את ה- COMMIT, הוא משחרר נעילות ומחזיר ACK על ה- commit. אם מישהו לא ענה לבקשה של לעשות commit, כלומר שהוא למטה (כי אמרנו שמי שהגיע לשלב הזה, אחרי ה- PREPARE, בוודאות מסוגל לעשות את ה- commit) – אז ה-coordinator ינסה שוב ושוב להגיד לו לעשות את ה- commit.
      4. לאחר שכל ה- ACK-ים התקבלו, ה- coordinator מסיים את הטרנזקציה ומשחרר את המשאבים שלו
    2. אם מישהו שלח DISAGREEMENT, או שהגענו ל- timeout (אם לא נשלב מנגנון timeout, עלולים להיתקע במצב הנ"ל לעד):
      1. ה- coordinator שולח ROLLBACK לכל אחד ואחד מה- nodes
      2. כל node עושה את ה- rollback שלו, משחרר נעילות ושולח ACK בסיום
      3. לאחר שכל ה-ACK-ים התקבלו, ה- coordinator מסיים את הטרזנקציה (הפעם, ב- state של כישלון), ומשחרר את המשאבים שלו.

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

  • נניח שאחד ה- nodes מת במהלך ביצוע הפעולות, בשלב 2. במקרה כזה, לא נגיע בשלב 3 למצב שבו כולם אומרים שהם מוכנים ל- commit, ולכן לא יתבצע commit מול אף אחד מה-nodes. כלומר, כישלון באחד ה- nodes בזמן ביצוע הפעולות לא גורם למצב לא קונסיסטנטי. כישלון כזה עלול לגרום למצב של "תקיעה" שבו הטרנזקציה נשארת פתוחה, אם אנחנו לא דואגים להתמודדות עם מצב כזה. ההתמודדות יכולה להיות באמצעות יהוי הכישלון בביצוע הפעולות מול איזשהו node, ודילוג ישר לשלב 4.2, או באמצעות שימוש במנגנון timeouts.
  • נניח ש- node נכשל בשלב 2 (אבל לא מת), אז הוא ישלח disagreement, ונגיע לשלב 4.2 ונעשה rollback.
  • נניח ש- node מת בשלב 3 – באמצעות timeout, נוכל להבטיח שנגיע לשלב 4.2, כלומר נתנהג כאילו קיבלנו ממנו הודעת DISAGREEMENT.
  • נניח ש- node מת בשלב 4, לאחר שחלק ביצעו commit וחלק טרם. פה, אנחנו נכנסים למצב קצת טריקי – אנחנו לא בשלב שבו ניתן לשים timeouts ולקפוץ לשלב 4.2, כלומר לביצוע rollback – מאחר שחלק מה- nodes כבר ביצעו commit, שזה השלב הסופי, ואין להם דרך לעשות rollback. כלומר, במקרה הזה נהיה במצב שבו אין התקדמות עד שה- node שכשל יחזור לחיים. כאשר הוא חזר לחיים, מההגדרה של ה- PREPARE, אנחנו יודעים שהוא יגיע שוב למצב שבו אפשר לקרוא ל- commit, ולהגיע לסוף מוצלח.
    בכל אופן, גם אם הוא לא יעלה, נהיה במצב שחלק מה- nodes עשו commit וחלק מה- nodes לא עשו commit, אבל אנחנו כן קונסיסטנטיים. איך זה יכול להיות? כי ה- node שלא עשה commit למטה (ולכן העובדה שהוא לא עשה commit לא משנה), וכשהוא יעלה – הוא יהיה במצב שבו הוא מוכן לבצע commit (מהגדרת ה- PREPARE). ולכן, אנחנו שומרים על מצב קונסיסטנטי גם במקרה הזה (על אף שייתכן שהמצב "תקוע").

כמו שאנחנו רואים, הפרוטוקול הזה מאפשר ביצוע distributed transaction בצורה בטוחה, ע"י הוספה של תפקיד ה- coordinator והוספה של שלב נוסף בתהליך (בין ביצוע הפקודות לבין ה- COMMIT עצמו), שהוא שלב ה- PREPARE.

2PC בעולם

כיום, מרבית המנגנונים שמאפשרים distributed transaction מממשים את הפרוטוקול הנ"ל, ומרבית הדאבייסים תומכים בו. למעשה, אם אתם כותבים קוד .NET ועושים שימוש בטרנזקציות, אתם ככל הנראה משתמשים ב- TransactionScope. כידוע, תחת TransactionScope ניתן לכתוב קוד שכולל resource-ים מרובים (מס' דטאבייסים, למשל) ועדיין לנהל טרנזקציה מולם. הטרנזקציה האחודה הזאת, מתבצעת בהתאם לפרוטוקול ה- 2PC.
אם אתם מעוניינים, אתם גם יכולים לכלול באותה הטרנזקציה המבוזרת גם resource-ים נוספים, כולל כאלה שאין עבורם מימוש מובנה לפרוטוקול ה- 2PC. במקרה הזה, אתם יכולים לממש את ה-interface שנקרא IEnlistmentNotification ולרשום את המימוש שלכם כחלק מה- instance של ה- TransactionScope, כדי לקבל את אותן ההודעות (PREPARE, COMMIT וכו') שנשלחות כחלק מניהול הטרנזקציה המבוזרת, כך שניתן לשלב resource-ים נוספים בתהליך (בתנאי כמובן שהם מספקים את התנאים המקדימים שנדרשים כדי להיות חלק מתהליך two-phase commit, שהם אותם התנאים שהוזכרו קודם).
עבור ניהול הטרנזקציה בפועל (כלומר, תפקיד ה- coordinator עליו דיברנו קודם) – עושים שימוש פעמים רבות ברכיב שנקרא ה- Transaction Manager (או ה- TM). בעולם המיקרוסופטי, כאשר עושים טרנזקציה (למשל, באמצעות TransactionScope), הרכיב שמשמש בתור ה- TM נקרא Microsoft Distributed Transaction Coordinator, או בקיצור MSDTC.

חסרונות של 2PC

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

אם ה- coordinator נופל ולא חוזר לאחר מכן, אנחנו נהיה במצב תקוע: ה- nodes ששלחו AGREEMENT ממתינים עד לקבלת הודעת COMMIT או עד לקבלת הודעת ROLLBACK. אם ה- coordinator למטה, אין מי שישלח להם את ההודעה.
את הבעייה הזאת לפעמים פותרים באמצעות הרחבת הפרוטוקול עם מנגנון שמאפשר ל- node אחר לקחת את מקום ה- coordinator. במקרה הזה, לאחר נפילת ה- coordinator, איזשהו node אחר ייקח את התפקיד (יש סוגייה של מי ה- node שלוקח את התפקיד, ואיך עושים master election, אבל נניח לשם הפשטות שיש node בודד שהוא זה שמסומן להיות אחראי במקרה של נפילה). במקרה הזה, לאחר שה- node המחליף לקח את האחריות, הוא יכול לשלוח מחדש את הודעות ה- PREPARE ולאסוף מחדש את הודעות ה- agreement, עד שיקבל מכולם הודעות agreement וימשיך לשלב ה- commit, או שיחליט לעשות abort.
על אף שפיתרון כזה אמנם מצמצם את הבעייה, הוא אינו פותר אותה לחלוטין. אם במקרה נפל לנו גם ה- coordinator וגם node נוסף כלשהו – ל- node המחליף אין מספיק מידע לגבי מה לעשות. הוא לא יודע, גם אם הוא קיבל הודעות AGREEMENT מכולם, האם ה- node הנוסף גם שלח הודעת AGREEMENT ל- coordinator שנפל, או לחלופין אם הוא שלח הודעת DISAGREE ל- coordinator טרם הנפילה, ובמקרה כזה בכלל צריך לעשות rollback. גם ללכת על rollback זאת לא בחירה טובה, כי יכול להיות שה- coordinator קיבל AGREEMENT מכולם, כולל מה- nodes שנפל, התחיל לשלוח הודעות commit, וה- node היחיד שהספיק לקבל הודעת commit לפני שה- coordinator נפל, הוא אותו node שהתרסק מיד אח"כ. ואז, זה אומר שעל אף ששאר ה- nodes שמשתתפים בטרנזקציה לא יודעים האם החליטו על commit או rollback, יש node אחד שאולי כבר עשה commit.
במצב כזה, הפרוטוקול תקוע עד שה- node או ה- coordinator המקורי חוזרים לחיים.

3PC (three-phase commit)

כדי לפתור את החיסרון שתיארנו קודם, של היותו של 2PC פרוטוקול blocking, קיים גם פרוטוקול 3PC.
הצורה שבה הפרוטוקול הזה פותר את הבעייה, היא ע"י פיצול שלב ה- commit מפרוטוקול ה- 2PC (שלב 4 בתיאור ממקודם) לשני שלבים: pre-commit ו- commit.

בשלב ה- pre-commit, שקורה אם קיבלנו AGREE מכל ה- nodes, כל אחד מה- nodes מקבל הודעת pre-commit מה- coordinator, שבמסגרתה הוא נכנס ל- state של מוכנות לביצוע commit, אבל לא עושה עדיין commit בפועל (ובפרט, עדיין יכולים לבצע rollback). רק אחרי שה- coordinator יקבל ACK מכל ה- nodes שהם ביצעו את ה- pre-commit, הוא ישלח את ההודעה לבצע commit, שבה כולם באמת יבצעו את ה- commit.

כלומר, אנחנו מוסיפים פה עוד שלב שבו נמצאים ב-"חצי- commit". איך השלב הזה עוזר לנו בחיים? למעשה, השלב הזה מיועד כדי לאפשר ל- node אחר לקחת את תפקיד ה- coordinator בביטחה, אם ה- coordinator נפל. ראינו שהבעייה שלנו היא שאם נופל ה- coordinator, וגם נופל node, יש לנו את הספק האם יכול להיות שהתקבלה למעשה החלטה לבצע את הטרנזקציה, וה- node שנפל כבר עשה commit- ואנחנו לא יודעים את זה (כי גם ה- coordinator, וגם ה- node היחיד שביצע commit נפלו).
הוספת השלב של ה- pre-commit אומרת שאם ה- node שנפל עשה commit, כל ה- nodes האחרים קיבלו לכל הפחות את הודעת ה- pre-commit (ייתכן שעוד מתוכם עשו כבר commit). כלומר, אם ה- coordinator החדש רואה שיש nodes שקיבלו את הודעת ה- pre-commit, הוא יודע שההחלטה שהתקבלה ע"י ה- coordinator הקודם היא לעשות commit, ולכן הוא יכול לשלוח מחדש את הודעות ה- pre-commit ולהמשיך מאותה הנקודה.
אם הוא רואה שיש node אחד לפחות שלא קיבל הודעת pre-commit, הוא יודע שזה אומר בוודאות שאף node לא המשיך ל- commit עצמו (כי שליחת ה- commit מתבצעת רק אחרי שכל ה- nodes האחרים אישרו ל- coordinator שהם הצליחו לבצע את ה- pre-commit), ולכן ה- coordinator החדש יכול ללכת על בטוח, לעשות rollback לטרנזקציה ולהתחיל מחדש.

האם זה פותר את כל הבעיות? רק בעולם תיאורטי שבו הרשת אף פעם לא מתחלקת במצב כזה שבו לא נוצרת חלוקה בתוך הרשת (אין partitioning). ברשתות אמיתיות, יכול להיות partitioning (כלומר, להיווצר שתי בועות מנותקות ברשת בגלל תקלה או עיכוב בתקשורת), ובו הפרוטוקול הזה כבר לא עובד.
זאת אחת הסיבות לכך שהפרוטוקול הזה גם לא הפרוטוקול שמשמש בפועל transaction managers – הוא יקר יותר מ- 2PC (במונחי סיבוכיות תקשורת וביצועים), ועדיין איננו פותר בעייה מהותית שקיימת בעולם האמיתי (של network partitioning), ולכן בפועל יכול לגרור מצב לא קונסיסטנטי.  אם מעניין אתכם לקרוא עוד על פרוטוקולים שיודעים להגיע להסכמה ולהתמודד גם עם network partitioning (ולכן יכולים לפתור גם את בעיית ה- distributed transaction), מוזמנים לקרוא על Paxos ו- Raft.

 

2 Replies to “נושאים בביזור – Distributed Transaction באמצעות 2PC ו- 3PC”

  1. תודה על הפוסט המעמיק! תוכל לספר קצת על מקרים שנתקלת בהם שהיה צורך להכנס לעומקי ה distributed transactions?

    1. אלכס, רוב המקרים אכן לא דורשים להכיר לעומק את המנגנון. למעשה, הרבה מאד אנשים שמפתחים לא מודעים בכלל לכך שהטרנזקציה שלהם, שעטופה ב- TransactionScope, מצאה את עצמה עובדת מול MSDTC (בגלל, למשל, שהם עבדו מול שני דטאבייסים בפנים) – ולא מודעים לעלויות הנוספות של זה, ולאיך המנגנון ממומש. אז כמובן שכדאי להכיר.
      מקרה נוסף שנתקלתי בו, זה שדווקא כן רצו להשיג distributed transaction, ולכן מימשו IEnlistmentNotification, אבל בלי להכיר בדיוק מה אומר הפרוטוקול ומה צריך להתקיים כדי שהפרוטוקול אכן יעבוד. במקרה הזה, המימוש למעשה לא ישיג את התוצאה הרצוייה בכל מיני מצבי קצה (שזאת אחת הסיבות העיקריות לכך שמלכתחילה משתמשים בטרנזקציות…).

השאר תגובה