מקודד לשוא וידויים של מוח מקוון

CAP – אתה יכול לבחור רק שניים

משפט CAP מתאר מערכת בעלת עם מבנה נתונים או מצב זיכרון (state) העונים על המאפיינים הבאים:

1. עקביות (Consistency) - כל לקוח של המערכת מקבל את אותם נתונים גם אם התבצעו עדכונים במקביל.
2. זמינות (Availability) - המערכת משרתת את כל בקשה של לקוחותיה.
3. סבילות חלוקה (Partition tolarance) - ניתן לפצל את מבנה הנתונים או מצב הזיכרון על פני מספר שרתים, או במילים אחרות לפצל את השירות על פני כמה צמתים ברשת.

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

להלן ההוכחה  (מקור ג'וליאן בראון)

התרשים מראה מערכת מחולקת אשר מכילה שני צמתים ברשת , N1 ו N2. שניהם חולקים פיסת מידע V (כמה עותקים לספר במלאי), עם הערך V0. על הצומת N1 רץ אלגוריתם שנקרא A ואנו יוצאים מנקודת הנחה שהוא צפוי, חסר באגים, ומהימן.על הצומת N2 רץ אלגוריתם דומה שנקרא B . בניסוי A כותב ערכים חדשים של V ו-B קורא ערכים של V.

התמונה למעלה מתארת תרחיש רגיל (המערכת עובדת כשורה) ,והפעולות הבאות יקרו:
1. Aכותב ערך חדש ל V (נקרא לו V1)
2. הודעה M עוברת מ N1 ל N2 ומעדכנת את העותק של V
3. כל קריאה של B תחזיר את הערך החדש V1

התמונה הזו מתארת טעות, הודעת העדכון (M) לא עברה. מכאן שבשלב 3 קריאה ל B תחזיר ערך לא עדכני.

קריאה ל A ו B יחזירו תוצאות שונות אני מקווה שכאן הבעיה כבר מובנת, נגדיל את קנה המידה לכמה מאות פעולות וזה הופך לבעיה גדולה. אם M הוא הודעה אסינכרונית אז לN1 אין דרך לדעת אם N2 קיבל את ההודעה. אפילו עם מסירה מובטחת של M , אין ל N1 דרך לדעת אם הודעה מתעכבת או שמשהו כשל בN2. הפיכת M לסינכרונית לא עוזרת כי התייחסות לסנכרון כפעולה אטומית יגרום לעקבת (latency בהעדר תרגום מתאים) וזה מפר את עקרון הזמינות. ההוכחה, באמצעות וריאציה,מראה כי אפילו במודל סינכרוני חלקי לא ניתן להבטיח אטומיות.

אז מה CAP אומר לנו ? שאם אנחנו רוצים ש A ו-B יהיו בעלי זמינות גבוהה (כלומר לעבוד עם עקבת מינימלית) ואנחנו רוצים שהצמתים N1 עד *N (כאשר * יכול להיות מאות או אפילו אלפים) יהיו בעלי סבילות חלוקה (שידעו להתמודד עם אבדון הודעות, הודעות שלא נשלחו, תקלות חומרה ותקלות תוכנה) אז לפעמים אנחנו הולכים לקבל מקרים שבהם הצמתים לא מסונכרנים וצומת אחד חושב כי V הוא V0 (עותק של ספר אחד) וצמתים אחרים יחשבו כי V הוא V1 (לא אותו עותק).