משך החיים של פעולות קריאה וכתיבה ב-Spanner

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

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

במסמך הזה אנחנו מתארים בפירוט איך פעולות כתיבה וקריאה פועלות ב-Spanner ואיך Spanner מבטיח מודל עקביות חזק.

נקודות התחלה

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

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

‫Spanner מספק עסקאות לקריאה בלבד ועסקאות לקריאה וכתיבה. האחרונים הם סוג העסקה המועדף לפעולות (כולל הצהרות SQL SELECT) שלא משנות את הנתונים. טרנזקציות לקריאה בלבד עדיין מספקות עקביות חזקה ופועלות כברירת מחדל על העותק העדכני ביותר של הנתונים. אבל הן יכולות לפעול בלי צורך בכל סוג של נעילה פנימית, מה שהופך אותן למהירות יותר ולכאלה שאפשר להרחיב אותן בקלות. עסקאות עם הרשאת קריאה וכתיבה משמשות לעסקאות שמוסיפות, מעדכנות או מוחקות נתונים. זה כולל עסקאות שקוראות נתונים ואז כותבות אותם. הן עדיין ניתנות להרחבה רבה, אבל עסקאות קריאה-כתיבה יוצרות נעילה וצריכות להיות מנוהלות על ידי מובילי Paxos. חשוב לדעת: הנעילה שקופה ללקוחות Spanner.

במערכות קודמות רבות של מסדי נתונים מבוזרים, בחרו שלא לספק ערבויות חזקות לעקביות, בגלל התקשורת היקרה בין המכונות שנדרשת בדרך כלל. ‫Spanner יכול לספק תמונות מצב עקביות מאוד בכל מסד הנתונים באמצעות טכנולוגיה שפותחה על ידי Google שנקראת TrueTime. בדומה ל-Flux Capacitor במכונת זמן משנת 1985 בערך, TrueTime הוא מה שמאפשר את הפעולה של Spanner. זהו API שמאפשר לכל מכונה במרכזי הנתונים של Google לדעת את השעה הגלובלית המדויקת ברמת דיוק גבוהה (כלומר, בתוך כמה אלפיות השנייה). כך מכונות Spanner שונות יכולות להסיק מסקנות לגבי הסדר של פעולות טרנזקציונליות (ולוודא שהסדר הזה תואם למה שהלקוח רואה), לרוב בלי תקשורת בכלל. כדי ש-TrueTime יפעל, Google הייתה צריכה לצייד את מרכזי הנתונים שלה בחומרה מיוחדת (שעונים אטומיים!). הדיוק והרזולוציה של הזמן שמתקבלים גבוהים בהרבה מאלה שאפשר להשיג באמצעות פרוטוקולים אחרים (כמו NTP). בפרט, Spanner מקצה חותמת זמן לכל פעולות הקריאה והכתיבה. מובטח שטרנזקציה בחותמת הזמן T1 תשקף את התוצאות של כל פעולות הכתיבה שהתרחשו לפני T1. אם מכונה רוצה לבצע קריאה ב-T2, היא צריכה לוודא שהתצוגה שלה של הנתונים עדכנית לפחות עד T2. בגלל TrueTime, בדרך כלל קל מאוד לקבוע את זה. הפרוטוקולים להבטחת עקביות הנתונים הם מורכבים, אבל הם מוסברים יותר במאמר המקורי על Spanner ובמאמר הזה על Spanner ועקביות.

דוגמה מעשית

כדי להבין איך זה עובד, נבחן כמה דוגמאות מעשיות:

CREATE TABLE ExampleTable (
 Id INT64 NOT NULL,
 Value STRING(MAX),
) PRIMARY KEY(Id);

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

פיצול KeyRange
0 ‫[-∞,3)
1 [3,224)
2 ‫[224,712)
3 [712,717)
4 [717,1265)
5 ‫[1265,1724)
6 [1724,1997)
7 [1997,2456)
8 ‫[2456,∞)

בהינתן הסכימה של ExampleTable שלמעלה, מרחב המפתחות הראשי מחולק למקטעים. לדוגמה: אם יש שורה ב-ExampleTable עם Id של 3700, היא תופיע בפיצול 8. כמו שמפורט למעלה, Split 8 עצמו משוכפל בכמה מכונות.

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

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

כתיבה עם פיצול יחיד

נניח שהלקוח רוצה להוסיף שורה חדשה (7, "Seven") ל-ExampleTable.

  1. שכבת ה-API מחפשת את הפיצול שבבעלותו טווח המפתחות שמכיל את 7. הוא נמצא בפיצול 1.
  2. שכבת ה-API שולחת את בקשת הכתיבה ל-Leader של Split 1.
  3. המוביל מתחיל עסקה.
  4. ה-Leader מנסה לקבל נעילת כתיבה בשורה Id=7. זוהי פעולה מקומית. אם עסקה אחרת של קריאה-כתיבה קוראת כרגע את השורה הזו, לעסקה האחרת יש נעילת קריאה והעסקה הנוכחית נחסמת עד שהיא יכולה לקבל את נעילת הכתיבה.
    1. יכול להיות שטרנזקציה א' ממתינה לנעילה שמוחזקת על ידי טרנזקציה ב', וטרנזקציה ב' ממתינה לנעילה שמוחזקת על ידי טרנזקציה א'. מכיוון שאף אחת מהעסקאות לא משחררת נעילה עד שהיא מקבלת את כל הנעילות, יכול להיווצר מצב של קיפאון. ‫Spanner משתמש באלגוריתם סטנדרטי למניעת מצב של קיפאון (deadlock) מסוג 'פצע והמתנה' כדי לוודא שהעסקאות מתקדמות. בפרט, עסקה 'חדשה' תמתין לנעילה שמוחזקת על ידי עסקה 'ישנה', אבל עסקה 'ישנה' תבטל עסקה 'חדשה' שמחזיקה נעילה שנדרשת על ידי העסקה הישנה. לכן, אף פעם לא יהיו לנו מחזורי קיפאון של ממתינים לנעילה.
  5. אחרי שהנעילה מתבצעת, המנהל מקצה חותמת זמן לעסקה על סמך TrueTime.
    1. חותמת הזמן הזו מובטחת להיות גדולה יותר מזו של כל עסקה קודמת שבוצעה ונגעה בנתונים. כך מוודאים שסדר העסקאות (כפי שהוא נתפס על ידי הלקוח) תואם לסדר השינויים בנתונים.
  6. הלידר מודיע על העסקה ועל חותמת הזמן שלה לכל העותקים של Split 1. אחרי שרוב העותקים האלה מאחסנים את שינוי הנתונים של העסקה באחסון יציב (במערכת הקבצים המבוזרת), העסקה מתבצעת. כך מוודאים שאפשר לשחזר את העסקה, גם אם יש כשל במספר קטן של מכונות. (הרפליקות עדיין לא מחילות את המוטציות על העותק שלהן של הנתונים).

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

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

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

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

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

כתיבה מפוצלת

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

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

1 "one"
2 ‫"two"
... ...
4000 ‪"four thousand"

נניח שהלקוח רוצה לקרוא את הערך בשורה 1000 ולכתוב ערך בשורות 2000, 3000 ו-4000 בתוך טרנזקציה. הפעולה הזו תתבצע בטרנזקציה של קריאה וכתיבה באופן הבא:

  1. הלקוח מתחיל עסקה של קריאה וכתיבה, t.
  2. הלקוח שולח בקשת קריאה לשורה 1000 לשכבת ה-API ומתייג אותה כחלק מ-t.
  3. ‫API Layer מחפש את הפיצול שבבעלותו המפתח 1000. הוא פעיל בפיצול 4.

  4. שכבת ה-API שולחת בקשת קריאה ל-Leader של Split 4 ומתייגת אותה כחלק מ-t.

  5. ה-Leader של פיצול 4 מנסה לקבל נעילת קריאה בשורה Id=1000. זו פעולה מקומית. אם לעסקה מקבילה אחרת יש נעילת כתיבה בשורה הזו, העסקה הנוכחית נחסמת עד שהיא יכולה לקבל את הנעילה. עם זאת, נעילת הקריאה הזו לא מונעת מעסקאות אחרות לקבל נעילות קריאה.

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

  6. ה-Leader מחפש את הערך של Id 1000 ("One Thousand") ומחזיר את התוצאה ללקוח.


    בהמשך...

  7. הלקוח שולח בקשת אישור (Commit) לעסקה t. בקשת השמירה הזו מכילה 3 שינויים: ([2000, "Dos Mil"],‏ [3000, "Tres Mil"] ו-[4000, "Quatro Mil"]).

    1. כל הפיצולים שקשורים לטרנזקציה הופכים למשתתפים בטרנזקציה. במקרה הזה, הפיצול 4 (שמטפל בקריאה של מפתח 1000), הפיצול 7 (שיטפל בשינוי של מפתח 2000) והפיצול 8 (שיטפל בשינויים של מפתח 3000 ומפתח 4000) הם המשתתפים.

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

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

  9. המשתתפים מקבלים נעילות. (זהו השלב הראשון בתהליך האישור הדו-שלבי).

    1. פיצול 7 מקבל נעילת כתיבה על מפתח 2000.
    2. תהליך הפיצול 8 מקבל נעילת כתיבה על מפתח 3000 ועל מפתח 4000.
    3. ‫Split 4 מוודא שהוא עדיין מחזיק בנעילת קריאה במפתח 1000 (במילים אחרות, שהנעילה לא אבדה בגלל קריסת מכונה או האלגוריתם של פצע-המתנה).
    4. כל משתתף בפיצול מתעד את קבוצת הנעילות שלו על ידי שכפול שלהן לרוב העותקים המשוכפלים של הפיצול (לפחות). כך אפשר לוודא שהנעילות יישארו בתוקף גם אם יש כשלים בשרת.
    5. אם כל המשתתפים מודיעים לרכז שהנעילות שלהם מוחזקות, אפשר לבצע את העסקה הכוללת. כך אנחנו מבטיחים שיש נקודת זמן שבה כל הנעילות שנדרשות לטרנזקציה מתבצעות, ונקודת הזמן הזו הופכת לנקודת האישור של הטרנזקציה. כך אנחנו יכולים להבטיח שאפשר יהיה לסדר את ההשפעות של הטרנזקציה הזו בצורה נכונה ביחס לטרנזקציות אחרות שהתרחשו לפני או אחרי.
    6. יכול להיות שלא תהיה אפשרות להשיג נעילות (לדוגמה, אם נגלה שיכול להיות שיש קיפאון (deadlock) באמצעות אלגוריתם הפצע-המתנה). אם אחד מהמשתתפים אומר שהוא לא יכול לבצע את העסקה, העסקה כולה מבוטלת.

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

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

  11. המתאם מעביר את תוצאת העסקה לכל המשתתפים. (זה השלב השני של אישור דו-שלבי).

    1. כל מנהיג של משתתף משכפל את החלטת האישור לשכפולים של החלק של המשתתף.

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

    1. כמו במקרה של פיצול יחיד, קוראים עוקבים של נתונים ב-Coordinator או ב-Participants צריכים לחכות עד שהנתונים יוחלו.

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

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

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

קריאה חזקה (פיצול מרובה)

נניח שהלקוח רוצה לקרוא את כל השורות שבהן Id >= 0 ו-Id < 700 כחלק מעסקה לקריאה בלבד.

  1. שכבת ה-API מחפשת את הפיצולים שכוללים מפתחות בטווח [0, 700). השורות האלה שייכות לפיצול 0, פיצול 1 ופיצול 2.
  2. מכיוון שמדובר בקריאה חזקה בכמה מכונות, API Layer בוחר את חותמת הזמן של הקריאה באמצעות TrueTime הנוכחי. כך מוודאים ששתי פעולות הקריאה יחזירו נתונים מאותה תמונת מצב של מסד הנתונים.
    1. גם סוגים אחרים של קריאות, כמו קריאות בעבר, בוחרים חותמת זמן לקריאה (אבל חותמת הזמן יכולה להיות מהעבר).
  3. שכבת ה-API שולחת את בקשת הקריאה לחלק מהרפליקות של Split 0, לחלק מהרפליקות של Split 1 ולחלק מהרפליקות של Split 2. הוא כולל גם את חותמת הזמן של הקריאה שנבחרה בשלב הקודם.

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

  5. התוצאות מהרפליקות משולבות ומוחזרות ללקוח (דרך שכבת ה-API).

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

סיכום

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