CRDT: מבני נתונים שמתמזגים לבד בלי קונפליקטים

מאת צוות מדיה דיל · 01.07.2026 · טכנולוגיה · 4 דק׳

Commutative, Associative, Idempotent Merge, State-based מול Operation-based, עריכה שיתופית, ו-Strong Eventual Consistency.

שני משתמשים עורכים את אותו מסמך Google Docs במקביל, אחד מהם במטוס בלי אינטרנט. כששניהם חוזרים לרשת, המערכת צריכה למזג את השינויים שלהם לגרסה אחת עקבית, בלי שרת מרכזי שמחליט מי צודק ובלי לשאול את המשתמשים איזו גרסה לשמור. Conflict-free Replicated Data Types (CRDT) הם משפחת מבני נתונים שמעוצבים כך שכל שני עותקים שהתעדכנו בנפרד תמיד ניתנים למיזוג אוטומטי לתוצאה זהה, בלי תלות בסדר ההגעה של העדכונים.

התכונה המתמטית: פעולות Commutative, Associative, Idempotent

הקסם של CRDT לא מקרי, הוא נובע מכך שפעולות המיזוג שלהם עומדות בשלוש תכונות אלגבריות: commutative (סדר לא משנה), associative (קיבוץ לא משנה), ו-idempotent (הפעלה כפולה לא משנה תוצאה). כשפונקציית ה-merge מקיימת את שלוש התכונות האלה, אפשר להוכיח מתמטית שכל שני replicas שקיבלו את אותה קבוצת עדכונים, בכל סדר, גם עם כפילויות, יתכנסו לאותו מצב סופי בדיוק. זו הסיבה שקוראים לזה conflict-free: אין תרחיש שבו נדרשת החלטה שרירותית.

State-based מול Operation-based CRDTs

יש שתי גישות מימוש עיקריות. ב-state-based CRDT (CvRDT), כל replica שולח את המצב המלא שלו לשכנים, וה-merge מבצע פעולה כמו union או max על כל השדות. ב-operation-based CRDT (CmRDT), משדרים רק את הפעולה שבוצעה, למשל הוסף תו X במיקום Y, ומניחים שכל הפעולות מגיעות בסופו של דבר לכל replica לפחות פעם אחת, בעזרת ערוץ תקשורת אמין. הגישה הראשונה פשוטה יותר להוכחת נכונות אבל שולחת יותר נתונים; השנייה חסכונית ברשת אבל דורשת ערבויות משלוח חזקות יותר.

עריכה שיתופית בזמן אמת

עורכי טקסט שיתופיים כמו Google Docs ו-Figma משתמשים במבני CRDT ייעודיים לטקסט, כמו RGA או Logoot, שבהם כל תו מקבל מזהה ייחודי וקבוע שלא תלוי במיקומו הנוכחי במסמך, כך שהכנסת תו על ידי משתמש אחד והכנסת תו אחר במקביל על ידי משתמש שני תמיד מתמזגות לתוצאה קריאה, גם אם שני התווים הוכנסו כמעט באותו מקום. זה מאפשר עריכה offline-first אמיתית: כל לקוח עובד מקומית בלי המתנה לשרת, והסנכרון קורה ברקע כשיש חיבור.

שימוש במסדי נתונים מבוזרים

מסדי נתונים כמו Redis (עם CRDT counters), Riak ו-AntidoteDB בונים סוגי נתונים שלמים, counters, sets, maps, כ-CRDTs, כדי לאפשר כתיבה מקומית בכל data center בלי לחכות לתיאום גלובלי, ועדיין להגיע ל-strong eventual consistency. זה שימושי במיוחד בארכיטקטורת multi-region שבה latency בין אזורים גיאוגרפיים גדול מדי בשביל coordination סינכרוני על כל כתיבה, ובמקום זאת כל אזור כותב באופן עצמאי ומסתמך על מנגנוני הפצה כמו Gossip Protocol כדי להעביר עדכונים בין replicas.

מגבלות: לא כל מבנה נתונים ניתן להפוך ל-CRDT

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

בונים feature של עריכה שיתופית או מערכת multi-region שצריכה למזג עדכונים בלי לחכות לשרת מרכזי? נשמח לעזור לכם בוואטסאפ.

תגיות: CRDT · Conflict-free Replicated Data Types · עריכה שיתופית · Eventual Consistency · State-based CRDT

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