streamalism.org

1. סקירה כללית

במאמר זה נבחן סוגי נתונים משוכפלים ללא קונפליקטים (CRDT) וכיצד לעבוד איתם ב- Java. לדוגמאות שלנו נשתמש ביישומים מה- wurmloch-crdt סִפְרִיָה.

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

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

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

2. סוגי נתונים משוכפלים ללא סכסוך להצלה

בואו ניקח בחשבון שני צמתים, א ו ב, שהתנתקו עקב פיצול מוח.

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

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

אנו יכולים להשתמש בכמה אסטרטגיות: אנו יכולים לתת אפשרות לפתור קונפליקטים למשתמש (כפי שנעשה ב- Google Docs), או אנחנו יכוליםהשתמש ב- CRDT למיזוג נתונים מעותקים משוכפלים בשבילנו.

3. תלות של Maven

ראשית, בואו להוסיף תלות בספרייה המספקת קבוצה של CRDT שימושיים:

 com.netopyr.wurmloch wurmloch-crdt 0.1.0 

ניתן למצוא את הגרסה האחרונה ב- Maven Central.

4. סט לגידול בלבד

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

ראשית, בואו ניצור שני עותקים משוכפלים כדי לדמות מבנה נתונים מבוזר ונחבר את שני ההעתקים האלה באמצעות ה- לְחַבֵּר() שיטה:

LocalCrdtStore crdtStore1 = LocalCrdtStore חדש (); LocalCrdtStore crdtStore2 = LocalCrdtStore חדש (); crdtStore1.connect (crdtStore2);

ברגע שנקבל שני העתקים באשכול שלנו, נוכל ליצור GSet על העתק הראשון והתייחס אליו על ההעתק השני:

העתק GSet1 = crdtStore1.createGSet ("ID_1"); GSet replica2 = crdtStore2.findGSet ("ID_1"). Get ();

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

replica1.add ("תפוח"); replica2.add ("בננה"); assertThat (העתק 1). מכיל ("תפוח", "בננה"); assertThat (העתק 2). מכיל ("תפוח", "בננה");

בואו נגיד שפתאום יש לנו מחיצת רשת ואין קשר בין ההעתקים הראשונים לשניים. אנו יכולים לדמות את מחיצת הרשת באמצעות ה- לְנַתֵק() שיטה:

crdtStore1.disconnect (crdtStore2);

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

העתק 1.add ("תות"); replica2.add ("אגס"); assertThat (העתק 1). מכיל ("תפוח", "בננה", "תות"); assertThat (העתק 2). מכיל ("תפוח", "בננה", "אגס");

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

crdtStore1.connect (crdtStore2); assertThat (העתק 1). מכיל ("תפוח", "בננה", "תות", "אגס"); assertThat (העתק 2). מכיל ("תפוח", "בננה", "תות", "אגס");

5. מונה תוספת בלבד

מונה תוספת בלבד הוא CRDT שמאגד את כל התוספות באופן מקומי על כל צומת.

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

בואו ניצור מונה להגדלה בלבד באמצעות מונה GC ולהגדיל אותו משני ההעתקים. אנו יכולים לראות שהסכום מחושב כראוי:

LocalCrdtStore crdtStore1 = LocalCrdtStore חדש (); LocalCrdtStore crdtStore2 = LocalCrdtStore חדש (); crdtStore1.connect (crdtStore2); העתק GCounter = crdtStore1.createGCounter ("ID_1"); GCounter replica2 = crdtStore2.findGCounter ("ID_1"). Get (); replica1.increment (); replica2.increment (2L); assertThat (replica1.get ()). isEqualTo (3L); assertThat (replica2.get ()). isEqualTo (3L); 

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

crdtStore1.disconnect (crdtStore2); העתק 1. increment (3 ליטר); replica2.increment (5L); assertThat (replica1.get ()). isEqualTo (6L); assertThat (replica2.get ()). isEqualTo (8L);

אך ברגע שהאשכול יהיה בריא שוב, התוספות יתמזגו, ותניב את הערך הראוי:

crdtStore1.connect (crdtStore2); assertThat (replica1.get ()) .isEqualTo (11L); assertThat (replica2.get ()) .isEqualTo (11L);

6. דלפק PN

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

כאשר העתקים מסונכרנים, הערך המתקבל יהיה שווה ל-סכום כל התוספות פחות סכום כל ההדרגות:

@Test הציבור בטל נתוןPNCounter_whenReplicasDiverge_thenMergesWithoutConflict () {LocalCrdtStore crdtStore1 = LocalCrdtStore חדש (); LocalCrdtStore crdtStore2 = LocalCrdtStore חדש (); crdtStore1.connect (crdtStore2); העתק PNCounter1 = crdtStore1.createPNCounter ("ID_1"); PNCounter replica2 = crdtStore2.findPNCounter ("ID_1"). Get (); replica1.increment (); replica2.decrement (2L); assertThat (replica1.get ()). isEqualTo (-1L); assertThat (replica2.get ()). isEqualTo (-1L); crdtStore1.disconnect (crdtStore2); replica1.decrement (3L); replica2.increment (5L); assertThat (replica1.get ()). isEqualTo (-4L); assertThat (replica2.get ()). isEqualTo (4L); crdtStore1.connect (crdtStore2); assertThat (replica1.get ()). isEqualTo (1L); assertThat (replica2.get ()). isEqualTo (1L); }

7. רישום הזכייה בסופר אחרון

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

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

בואו ליצור מקבץ של שני העתקים ומופעים של LWW הרשמה מעמד:

LocalCrdtStore crdtStore1 = LocalCrdtStore חדש ("N_1"); LocalCrdtStore crdtStore2 = LocalCrdtStore חדש ("N_2"); crdtStore1.connect (crdtStore2); LWWRegister replica1 = crdtStore1.createLWWRegister ("ID_1"); LWWRegister replica2 = crdtStore2.findLWWRegister ("ID_1"). Get (); replica1.set ("תפוח"); replica2.set ("בננה"); assertThat (replica1.get ()). isEqualTo ("בננה"); assertThat (replica2.get ()). isEqualTo ("בננה"); 

כאשר ההעתק הראשון מגדיר את הערך ל- תפוח עץ והשני משנה את זה ל בננה, ה LWW הרשמה שומר רק על הערך האחרון.

בואו נראה מה יקרה אם האשכול יתנתק:

crdtStore1.disconnect (crdtStore2); replica1.set ("תות"); replica2.set ("אגס"); assertThat (replica1.get ()). isEqualTo ("תות"); assertThat (replica2.get ()). isEqualTo ("אגס");

כל העתק שומר על העותק המקומי שלו של נתונים שאינם עקביים. כשאנחנו קוראים מַעֲרֶכֶת() השיטה, LWW הרשמה מקצה באופן פנימי ערך גרסה מיוחד המזהה את העדכון הספציפי לכל המשתמש ב- וקטורקלוק אַלגוֹרִיתְם.

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

crdtStore1.connect (crdtStore2); assertThat (replica1.get ()). isEqualTo ("אגס"); assertThat (replica2.get ()). isEqualTo ("אגס");

8. מסקנה

במאמר זה הראינו את בעיית העקביות של מערכות מבוזרות תוך שמירה על זמינות.

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

ניתן למצוא את כל הדוגמאות וקטעי הקוד בפרויקט GitHub - זהו פרויקט Maven, כך שיהיה קל לייבא ולהפעיל אותו כפי שהוא.