אלגוריתמי קונצנזוס

1) מהו קונצנזוס ומדוע הוא נחוץ

קונסנזוס - משא ומתן על אותו ערך/רצף ערכים בין צמתים מרובים לכישלונות ועיכובים. באופן מסורתי, הבעיה של שכפול מצב (State Machine Reception, SMR) נפתרת: יש מכונת מצבים דטרמיניסטית וסדר פעולות כללי.

• קונסנזוס (SMR): סדר פקודות כולל אחד = = אחסון/רישום ליניארי, אשכול metadata, מתאם העברות.
• פעולות קוורום ללא סדר מוחלט (Dynamo-like, CRDT): לאפשר דיברגנץ ומיזוג לאחר מכן; אין להחליף את הקונצנזוס במקום בו דרושה סריאליזציה עולמית.

2) מודל זמן וכישלון

2. מודל זמן 1

רשת אסינכרונית: עיכובים הם בלתי מוגבלים; משפט FLP אינו יכול להבטיח ביטחון ולביאה ללא הנחות נוספות.
לאחר T לא ידוע, המערכת ”מתנהגת” בצורה סינכרונית - רוב האלגוריתמים (רפסודות, פאקסוס) מסתמכים על כך.
סינכרוני: מגבלות זמן קפדניות לערוצים (לעיתים נדירות במכירות, למעט רשתות מיוחדות/PRT).

2. 2 מודל כישלון

צומתי יכול ליפול/לתלות אבל לא להתנהג בזדון.
צמתים יכולים לשקר/לזייף הודעות. דורש 3f + 1 קשר לסובלנות f ביזנטית.

3) מאפייני הקונסנזוס

בטיחות: עקביות (שני צמתים נכונים לא יפתרו ערכים שונים).
אם הרשת היא ”בריאה”, פתרון מושג.
ליניאריזביליות (ליניאריות): פעולות ”נתפסות” כאטומיות בסדר יחיד.
עמידות: החלטות המתקבלות אינן מגולגלות לאחור (log/quorum protection).

4) קוורומים, מוקדים וצמתים

בעולם ה-CFT, הקלאסי: quorum> N/2. רשומות ובחירות מנהיג להשתמש חציית מניין, כך שני הפעולות ”תקפות” לא לסכסך.
בעולם BFT: מניין 2f + 1 של 3f + 1 מספק צומת של לפחות f + 1 צמתים ישרים.

כלל מעבר: כל שני מניין חייב להיות בעל צומת הוגן משותף 1 (CFT) או f + 1 (BFT).

5) שכפול מצב (יישום רישום +)

• Snapshots (פרוסה מהמצב שאחריו ניתן למחוק את הרישומים המוקדמים).
• דחיסה יומנית וטריאם יומן.
• בדיקת דטרמיניזם (אותה גרסת קוד/הגדרה).

6) מנהיגות ומזימות שאינן מנהיגות

מנהיגות (Rapt, Multi-Paxos, ZAB): מנהיג אחד מקליט רשומות פי יותר קלות מבחינה מנטלית ומבחינה אופרטיבית.
מנהיג/רב-מנהיג (EPaxos, Caesar): יותר מקביליות וסובלנות למנהיג, אבל יותר קשה ליישם ולפתרון-קונפליקט; רווח גלוי לעימותים קטנים של צוותים.

7) אלגוריתמי CFT קלאסיים

7. 1 Paxos/Multi-Paxos (ופרקטיקות)

הרעיון: שני שלבים (הכן/הצע), הבטחות של קבלה, קוורום הרוב. Multi-Paxos משאיר ”מנהיג יציב” והופך את הפעילות לסיבוב אחד (לכניסות חדשות) לאחר ”התחממות”.

• גמיש אבל קשה ליישם מודל.
• הגדרות מחדש באמצעות רשומות מיוחדות (קונצנזוס משותף).
• בפועל, ספריות/מנועים (דור Chubby/Spanner).

7. 2 רפסודה

מפורק ללמידה: בחירת מנהיג, שכפול יומן, הגדרה מחדש.

בחירות: פסקי זמן אקראיים, הצבעה במונחים; מנהיג אחד לכל כהונה.
נספחים: רשומות זרמים מובילות, מנטר את ההתאמה של הקידומת (אינדקס/מונח), מתחייב לקיבוע הרוב.
קריאה-נתיב: חכירה-קריאות (עם מנהיג חזק) או קריאה-אינדקס לקריאות לינאריות.
התאמה מחדש: ”ג 'וינט” - צמתים מצביעים בשני אשכולות לפני ההחלפה.

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

7. 3 ZAB (שידור אטומי שומר )/שכפול חותמת צפייה (VRR)

ZAB: מוביל משדר עסקאות, שלב התאוששות, zxid (אינדקס epoch +).
VRR: "Views' עם העתק עיקרי, בדומה ל-Multi-Paxos ברוח.

8) Non-Leader/Multi-Leader CFTs

8. 1 EPaxos

אין מנהיג קבוע: כל צומת יכול ליזום פקודה.
צוותי קונפליקט מקבלים סדר חלקי; ללא סכסוך - להתחייב 1-2 RTT מקומי.
רווח בהתפלגות גאו עם קונפליקט נמוך, אבל תלות/קודי גרף מורכבים.

8. 2 קיסר, מנסיוס

וריאציות שמייעל איזון/איזון והפעלת WAN.

9) אלגוריתמי BFT ומשפחת POS

9. 1 PBFT (BFT מעשי)

שלושה שלבים (הכן/הכן/התחייב), דורשים 3f + 1 קודקודים.
איחור נמוך ברשתות מקומיות, כבישים רבי שלבים והודעות O (N).

9. 2 Tendermint (סגנון BFT-POS)

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

9. 3 דברים חמים (ונגזרות)

סכימת שלושת השלבים מאוחדת ל ”חבילות” עם תעודות מניין (QC).
המורכבות הליניארית של תקשורת, תמיכה באריזה וצנרת מקבילה, נוחה ליישומים בשרשראות חסומות (לדוגמה, המערכת האקולוגית Diem/Move).
עם חתימות סף, התנועה מופחתת.

9. 4 PoW/קונצנזוס מצטבר (בקיצור)

לא BFT במובן הקפדני, אלא התכנסות הסתברותית (השרשרת עם הכי הרבה עבודה). יתרונות: פשטות/פתיחות; חסרונות: אנרגיה, ~ שניות דקות עד סופיות.

10) קורא: לינארי, רציף, ומטמון

ליניארי קורא: Leader עם חכירה פעילה או באמצעות Read-index (רפסודה) = אישור באמצעות מניין.
ניתן לקרוא אותו מכל צומת, אך ללא ערבויות של רעננות.
העוקב קורא: מותר תחת דרישות חלשות; עבור מטמונים - בסדר.

11) הגדרות מחדש (שינוי הרכב אשכול)

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

12) ביצועים וכיוונון

12. עיכובים 1

אלגוריתמי מנהיגות: 1 RTT לכל כתב (עם מוביל יציב) + שכפול.
הפצה גאוגרפית: WAN RTT שולט = = שימוש באזורים מקומיים + שכפול חוצה-אזורי או גישות EPaxos/HotStuff.

12. 2 תפאורה

חבורה (מקבץ פקודות), נספחים מקבילים, מטמון דף יומן, יישום מקביל (כאשר מבצעים מתחלפים).
דיסקים: NVMe/Log על התקן נפרד, 'O _ Direct '/AIO, מרווח גדול' fsync 'עם הגבלות SLA (פשרת עמידות/איחור).

12. 3 פלי 99

הימנע מקשרים חמים (תמיד יש מנהיג אחד): סיבוב תקופתי או קריאה-לפרוק על עוקבים.
Monitor GC Pauses (JVM/Go), CPU pins, NUMA.

13) גאוגרפיה וטופולוגיות

1 אזור, 3 אזורים: אשכול CFT קלאסי (N = 3/5).
2 אזורים: להימנע - אין מניין אמין ב 1-1 פיצול.
3 + אזורים: מוביל באלגוריתמים ”באמצע” או ללא הנהגה; חזיתות אזוריות/מקומיות עם יומן אסינכרוני אפשריות.

14) סוגיות מעשיות

14. 1 צילומים והתאוששות

סף לפי גודל היומן/מספר העסקאות.
העברה של תמונה לצמתים חדשים; בדיקת צ 'קסום.

14. 2 ניטור

מנהיגות: מי המנהיג, כמה מונחים השתנו.
Signative: "append _ latency", "polise _ index - applied_index'.

בריאות מניין: ”האם הרוב בחיים/2f + 1?”

גודל רישום/מהירות דחיסה, תור תמונות.

נתח הצבעה, חתימות זרוק, עיכובי QC

14. 3 אבטחת קוד/עקביות

פרוטוקול גיבוש על החוט, נדידה עם תאימות יומן.
סיוף אסימונים על אפקטים חיצוניים (ראו ”מנעולים מבוזרים”): עופרת בזמן (מונח) להעברה ל CRON/עבודות.

15) אנטי דפוסים

שימו את הקונסנזוס ”למען האופנה” שבו די בקריאת DBMS או מניין ללא סריאליזציה.
Mix CP ו ־ AP ללא גבולות ברורים (CAP) # UX בלתי צפוי.
הערכת יתר של PoW/POS עבור משימות יזמות עם עשרות צמתים (קשה/יקר).
התעלם מהתצורה מחדש ו ”צומת מניין” כאשר ההרכב משתנה.
מחסור במחסום קריאה (חכירה/קריאה) = קריאה מלוכלכת.
הפעלת אשכולות 2-צומת (ללא רוב).
ממעיט בערכו של דיסקים ו ־ fsync: ”הכל עף בזיכרון” - עד האתחול הראשון.

16) רשימת בדיקות בחירה

1. מודל כישלון: CFT (קריסות) או BFT (זדוני)?
2. גאוגרפיה: אזור אחד/שלושה אזורים או WAN? אר-טי-טי מחליט.
3. קריאת סמנטיקה: האם קריאות לינאריות נחוצות? חכירה/קריאה-אינדקס/המשך.
4. עומס: ציפיות ב ־ p50/p99, תפוקה; האם יש צורך במנהיגות מרובה.
5. מורכבות תפעולית: Library/off-the-shef engine (etcd/ZK/Consul/Raft-liebs) נגד יישום מקומי.
6. הגדרה מחדש: תכוף? אנחנו צריכים קונצנזוס משותף וכלי נדידה.
7. אינטגרציה: תופעות לוואי חיצוניות - האם יש סיף על ידי epoch/מונח?
8. אבטחה: אימות מארח, הצפנת ערוץ, בקרת גירסה פרוטוקול.
9. ספרי משחק: מחיצה, ג 'י-סי-סטופ, המנהיג ההרוג, הדיסק האיטי, השעון.
10. תצפית: Leader/Lags/Journal and Assess Metrics מוגדרים.

17) מיני-מדריך: מתי לקחת מה

אשכול etcd/רפסודה עבור תצורות/מנעולים/תיאום בתוך הבירה.
שומרת/זק ”א לשירותים שכבר קשורים לז” ק (ערימות ישנות, תורים, מנהיגות).
Multi-Paxos באמצעות שירות/ספרייה מוכן במערכות מיוחדות מאוד.
EPaxos עבור גיאו-הפצה וקונפליקט פיקוד נמוך.

& gt; & gt; & gt; & gt; & gt; & gt; & gt; & gt; & gt; & gt; & gt; & gt; & gt; & gt; & gt; & gt; & gt; & gt; & gt; & gt; & g

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

18) דוגמאות של ממשקים (פסאודו)

18. רישומים מחויבים 1 (סגנון רפסודה)

pseudo client -> leader: Propose(cmd)
leader. appendLog(cmd)
leader. replicateToQuorum()
if quorum_acked:
leader. commit(index)
leader. apply(index)
leader. reply(client, ok)

18. 2 קריאה-אינדקס לקריאה לינארית (רפסודה)

pseudo client -> any: LinearizableRead node -> leader: ReadIndex?
leader -> quorum: Heartbeat (barrier)
leader -> node: ReadIndex=commit_index node. wait_until(applied_index >= ReadIndex)
node. reply(client, state_at(ReadIndex))

18. 3 תצורה משותפת

pseudo old_conf + new_conf # quorums must intersect commit (entries under joint)
switch_to(new_conf)

18. 4 BFT (חומר חם משוער)

pseudo propose(block)
collect votes -> QC lock on highest QC commit when have consecutive QCs across phases

19) FAQ

קיו: למה לא להשתמש בשני קשרים ושובר שוויון?
א ': שני צמתים ללא פוסק שלישי לא נותנים מניין בחלוקה. יש צורך ב- 3 (CFT) או 3f + 1 (BFT).

קיו: מהו פסוס ”הפשוט” יותר? ‏

א ': פירוק ברור, אינווריאנטים מובנים של הלוג והתצורה; קל יותר ליישם ולשמור.

קיו: איך אתה קורא מהר בלי להעמיס את המנהיג?
A: Follower-reades (ברצף) עבור לא-ביקורתי, או חכירה-קריאה/קריאה-אינדקס עבור ליניארי; מטמון.

קיו: מה הורג את פי ־ 99? ‏

א ': WAN-RTT, Disk fsync, GC-stop, מנהיג חם מדי, תמונות גדולות בשעת העומס.

Q: האם המטמון/קטלוג זקוק לקונסנזוס?
א ': אם מספיק בסופו של דבר עקביות - לא. אם נדרשים ביקושים עסקיים, כן.

20) סיכומים

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