Vector Clocks: איך קובעים מי קדם למי בלי שעון גלובלי

מאת צוות מדיה דיל · 30.06.2026 · טכנולוגיה · 7 דק׳ קריאה

Happened-Before מול Concurrent, מונים לכל Node, Causal Order, Amazon Dynamo, Conflict Detection, ו-Physical Clock.

שני עדכונים הגיעו לאותה רשומה בזמנים שונים בשני data centers שונים. timestamp רגיל אומר שהעדכון מ-14:03:02.445 קדם לעדכון מ-14:03:02.451, אבל אם שעוני המכונות לא מסונכרנים במדויק, או אם שני העדכונים בכלל קרו במקביל בלי שהאחד ידע על השני, סדר לפי שעון פיזי הוא פשוט שקר שמחפה אמת אחרת. Vector Clocks נותנים דרך לקבוע סדר סיבתי אמיתי (causal order) בין אירועים במערכת מבוזרת, בלי להזדקק לשעון גלובלי מסונכרן בכלל.

איך זה עובד: מונה לכל Node

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

קביעת סדר: Happened-Before מול Concurrent

בהינתן שני וקטורים A ו-B, אפשר לקבוע יחס ביניהם באופן מתמטי: אם כל רכיב ב-A קטן או שווה לרכיב המקביל ב-B (ולפחות אחד קטן ממש), אז A happened-before B, כלומר A השפיע סיבתית על B. אם אף אחד מהם לא קדם לשני, שני האירועים concurrent, קרו במקביל בלי קשר סיבתי, וזה בדיוק המקרה שדורש טיפול מיוחד: המערכת לא יכולה לדעת איזה גובר, כי מבחינה סיבתית שניהם לגיטימיים באותה מידה.

מתי זה עדיף על Timestamp רגיל

Timestamp רגיל (physical clock) תמיד נותן סדר מוחלט, גם בין אירועים שלא היה ביניהם שום קשר סיבתי, מה שיוצר רושם שווא של מי היה ראשון כשבפועל אין תשובה נכונה. Vector Clock, לעומת זאת, חושף במפורש מתי אי אפשר לקבוע סדר, וזה בדיוק המידע שצריך כדי להחליט אם למזג את שני העדכונים, להעלות conflict למשתמש, או להפעיל last-write-wins בכוונה. במערכות שבהן דיוק סיבתי קריטי, Vector Clocks מספקים מידע ש-timestamp פשוט לא יכול לתת.

שימוש קלאסי: Amazon Dynamo

Amazon Dynamo (ומאוחר יותר Riak) השתמשו ב-Vector Clocks כדי לזהות מתי גרסאות מקבילות של אותה רשומה התנגשו אמיתית, ולהחזיר את כל הגרסאות ה-concurrent ללקוח כדי שהוא יחליט איך למזג אותן, למשל למזג עגלת קניות משתי גרסאות שונות במקום לאבד פריטים. זו דוגמה קלאסית לארכיטקטורת Leaderless Replication, שבה בלי leader יחיד שקובע סדר, Vector Clocks הם המנגנון היחיד שמאפשר להבחין בין עדכון חדש שדרס ישן לבין שני עדכונים שבאמת התנגשו.

העלות: גודל הווקטור גדל עם מספר הצמתים

המחיר המעשי של Vector Clocks הוא שגודל הווקטור גדל ליניארית עם מספר ה-nodes באשכול, מה שהופך אותו לכבד באשכולות גדולים עם node churn תדיר. גרסאות מעשיות משתמשות ב-pruning, השמטת ערכים ישנים מהווקטור, או עוברות למבנים דחוסים יותר כמו dotted version vectors. מבנים כמו CRDT לפעמים משלבים גרסה מצומצמת של הרעיון כדי לזהות עדכונים concurrent בלי לשאת את כל המשקל של וקטור מלא לכל רשומה.

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

Version Vectors מול Vector Clocks - הבדל דק אך חשוב

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

Dotted Version Vectors - התמודדות עם הגודל בפועל

כדי לצמצם את בעיית הגידול הליניארי בגודל הווקטור עם מספר ה-nodes, מימושים מודרניים משתמשים ב-Dotted Version Vectors: במקום לשמור מונה נפרד לכל node שאי פעם נגע ברשומה, שומרים "נקודה" שמזהה את הכתיבה האחרונה של כל node יחד עם וקטור מצומצם יחסית. זה מאפשר לזהות במדויק אילו כתיבות כבר נבלעו לתוך גרסה ממוזגת, ולנקות מהווקטור מידע ישן שכבר לא נחוץ להבחנה בין גרסאות, בלי לאבד את היכולת לזהות קונפליקט אמיתי.

מה קורה בפועל כשהמערכת מזהה קונפליקט

כשהמערכת מזהה שני עדכונים concurrent, יש לה שלוש אסטרטגיות אפשריות. הראשונה, Last-Write-Wins, בוחרת את הכתיבה עם ה-timestamp הפיזי המאוחר יותר ומוחקת את השנייה - פשוט אבל מסוכן כי היא יכולה לאבד מידע לגיטימי. השנייה, מיזוג אוטומטי, מתאימה למקרים שבהם יש חוק מיזוג ברור, כמו עגלת קניות שאפשר לאחד לפי כל הפריטים בשתי הגרסאות. השלישית, החזרת שתי הגרסאות ללקוח ותן לו להחליט, מתאימה כשאין דרך אוטומטית בטוחה למזג - וזו בדיוק הגישה ש-Dynamo נקט במקור עבור עגלות קניות.

מיזוג בפועל: מתי Vector Clock לא מספיק

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

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

כלי דיבוג: שחזור סדר אירועים אחרי תקלה

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

Lamport Timestamps מול Vector Clocks

שווה להכיר גם את Lamport Timestamps, מבנה קודם ופשוט יותר מ-Vector Clocks: הוא נותן לכל אירוע מספר בודד שמבטיח שאם אירוע A השפיע סיבתית על B, אז המספר של A קטן מזה של B. אבל בכיוון ההפוך זה לא נכון - אפשר לקבל שני אירועים עם מספרים שונים בלי שהיה ביניהם כל קשר סיבתי, מה שאומר ש-Lamport Timestamp לא יכול להבחין בין happened-before אמיתי לבין concurrent. Vector Clocks פותרים בדיוק את החוסר הזה, במחיר של מבנה נתונים גדול יותר.

הבחירה בין השניים היא בעצם בחירה בין פשטות לדיוק סיבתי מלא: מערכות שבאמת צריכות לזהות קונפליקטים בין עדכונים מקבילים חייבות Vector Clocks; מערכות שרק צריכות סדר עקבי כלשהו יכולות להסתפק ב-Lamport Timestamps הפשוטים יותר.

אסטרטגיות Pruning להקטנת הווקטור

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

שאלות נפוצות

האם Vector Clocks שימושיים גם במערכות עם leader יחיד?

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

מה קורה אם node חדש מצטרף לאשכול - צריך לבנות מחדש את כל הווקטורים הקיימים?

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

האם אפשר להשתמש ב-Vector Clocks גם ברמת אפליקציה, לא רק בתוך מסד הנתונים?

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

איך זה משפיע על ביצועים - האם בדיקת הסדר בין וקטורים איטית?

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

מה ההבדל בין קונפליקט שנפתר אוטומטית לקונפליקט שדורש התערבות משתמש?

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

תגיות: Vector Clocks · Causal Order · Happened-Before · Amazon Dynamo · סדר סיבתי

← חזרה לבלוג · צור קשר