Αλγόριθμοι συναίνεσης

1) Ποια είναι η συναίνεση και γιατί απαιτείται

Συναίνεση - Διαπραγμάτευση της ίδιας τιμής/ακολουθίας τιμών μεταξύ πολλαπλών κόμβων για αστοχίες και καθυστερήσεις. Παραδοσιακά, το πρόβλημα της αντιγραφής του κράτους (State Machine Replication, SMR) επιλύεται: υπάρχει μια ντετερμινιστική μηχανή κατάστασης και μια γενική σειρά λειτουργιών.

• Συναίνεση (ΚΑΔ): ενιαία συνολική σειρά εντολών → γραμμική αποθήκευση/μητρώο, μεταδεδομένα συμπλέγματος, συντονιστές συναλλαγών.
• πράξεις απαρτίας χωρίς συνολική παραγγελία (Dynamo-like, CRDT): να επιτραπεί η απόκλιση και η επακόλουθη συγχώνευση· δεν αντικαθιστούν τη συναίνεση όπου απαιτείται παγκόσμια σειρά.

2) Μοντέλο χρόνου και αστοχίας

2. 1 Χρονικό μοντέλο

Ασύγχρονο δίκτυο: οι καθυστερήσεις είναι απεριόριστες. το θεώρημα FLP ⇒ είναι αδύνατο να διασφαλιστεί τόσο η ασφάλεια όσο και η ζωντάνια χωρίς πρόσθετες υποθέσεις.
Μερικώς συγχρονισμένο (συχνά στην πράξη): μετά από ένα άγνωστο T, το σύστημα «συμπεριφέρεται» συγχρονισμένα - οι περισσότεροι αλγόριθμοι (Raft, Paxos) βασίζονται σε αυτό.
Συγχρονισμένες: αυστηρές προθεσμίες για τα κανάλια (σπάνια στις πωλήσεις, εκτός από τα ειδικά δίκτυα/PRT).

2. 2 Μοντέλο αστοχίας

Αντοχή σε βλάβη από συντριβή (CFT): Οι κόμβοι μπορεί να πέσουν/κρεμαστούν αλλά δεν συμπεριφέρονται κακόβουλα.
Ανθεκτικό στη βυζαντινή βλάβη (BFT): Οι κόμβοι μπορούν να ψεύδονται/ψεύτικα μηνύματα. Απαιτεί 3f + 1 κόμβους για ανοχή στο f βυζαντινό.

3) Ιδιότητες συναίνεσης

Ασφάλεια: συνέπεια (δύο σωστοί κόμβοι δεν θα επιλύσουν διαφορετικές τιμές).
Βιωσιμότητα: Εάν το δίκτυο είναι «υγιές», επιτυγχάνεται λύση.
Γραμμικότητα (γραμμικότητα): οι λειτουργίες «θεωρούνται» ως ατομικές με μία μόνο σειρά.
Ανθεκτικότητα: οι αποφάσεις που λαμβάνονται δεν ανατρέπονται (προστασία καταγραφής/απαρτίας).

4) Απαρτίες, πλειοψηφίες και διασταυρώσεις

Στον κόσμο της ΚΧΤ, το κλασικό: απαρτία> N/2. Τα αρχεία και οι εκλογές για την ηγεσία χρησιμοποιούν απαρτία, οπότε οι δύο «έγκυρες» επιχειρήσεις δεν συγκρούονται.
Στον κόσμο του BFT: απαρτίες 2f + 1 του 3f + 1 παρέχουν μια διασταύρωση τουλάχιστον f + 1 τίμιων κόμβων.

Κανόνας διασταύρωσης: Κάθε απαρτία πρέπει να έχει ≥1 κοινό δίκαιο κόμβο (CFT) ή ≥f+1 (BFT).

5) Αντιγραφή κατάστασης (log + εφαρμογή)

• Στιγμιότυπα (ένα κομμάτι της κατάστασης μετά την οποία οι πρώτες εγγραφές μπορούν να διαγραφούν/μεταγλωττιστούν).
• Συμπίεση εφημερίδας και τριάδα καταγραφής.
• Έλεγχοι προσδιορισμού (έκδοση του ίδιου κωδικού/config).

6) Ηγετικά και μη ηγετικά συστήματα

Ηγεσία (Raft, Multi-Paxos, ZAB): ένας ηγέτης καταγράφει → ευκολότερα διανοητικά και λειτουργικά, καλύτερη καθυστέρηση σε έναν σταθερό ηγέτη.
Leaderless/multi-leader (EPaxos, Καίσαρας): περισσότερος παραλληλισμός και ανοχή για τον ηγέτη, αλλά δυσκολότερη εφαρμογή και επίλυση συγκρούσεων· το κέρδος είναι ορατό με μικρές συγκρούσεις ομάδων.

7) Κλασικοί αλγόριθμοι ΚΧΤ

7. 1 Paxos/Multi-Paxos (και πρακτικές)

Η ιδέα: δύο φάσεις (προετοιμασία/πρόταση), υποσχέσεις αποδεκτών, απαρτίες πλειοψηφίας. Το Multi-Paxos αφήνει έναν «σταθερό ηγέτη» και μετατρέπει τις επιχειρήσεις σε ένα γύρο (για νέες συμμετοχές) μετά την «άνοδο της θερμοκρασίας».

• Ευέλικτο αλλά δύσκολο να εφαρμοστεί το μοντέλο.
• Αναδιατυπώσεις μέσω ειδικών καταχωρίσεων (κοινή συναίνεση).
• Στην πράξη, βιβλιοθήκες/κινητήρες (παραγωγή Chubby/Spanner).

7. 2 Σχεδία

Αποσύνθεση για μάθηση: επιλογή ηγέτη, αντιγραφή καταγραφής, αναδιαμόρφωση.

Εκλογές: τυχαία χρονοδιαγράμματα, ψηφοφορία θητείας. ένας ηγέτης ανά θητεία.
Προσάρτημα Καταχωρίσεις: ο επικεφαλής καταγράφει τις ροές, παρακολουθεί την αντιστοιχία του προθέματος (δείκτης/όρος), δεσμεύεται για τον καθορισμό της πλειοψηφίας.
Ανάγνωση διαδρομής: ανάγνωση μίσθωσης (με ισχυρό ηγέτη) ή δείκτης ανάγνωσης για γραμμικές αναγνώσεις.
Reconfig: «κοινό» - κόμβοι ψηφίζουν σε δύο ομάδες πριν αλλάξουν.

Pros: ευκολότερη ανάπτυξη/αποσφαλμάτωση, ισχυρή σειρά αναλλοίωτων. Cons: Το Leader είναι ένα σημείο πίεσης.

7. 3 ZAB (Ατομική εκπομπή ZooKeeper )/Αντιγραφή προβολής (VRR)

ZAB: επικεφαλής εκπέμπει συναλλαγές, φάση ανάκτησης, zxid (εποχή + δείκτης).
VRR: «θεάσεις» με πρωταρχικό αντιγραφέα, παρόμοιο με το Multi-Paxos στο πνεύμα.

8) Μη ηγετικές/Πολυεπίπεδες ΧΧΦΤ

8. 1 EPaxos

Δεν υπάρχει μόνιμος ηγέτης: οποιοσδήποτε κόμβος μπορεί να ξεκινήσει μια εντολή.
Οι ομάδες συγκρούσεων λαμβάνουν μερική τάξη. χωρίς συγκρούσεις - δέσμευση για 1-2 RTT σε τοπικό επίπεδο.
Κέρδος στη γεωγραφική κατανομή με χαμηλές συγκρούσεις, αλλά πολύπλοκους κωδικούς εξάρτησης/γραφήματος.

8. 2 Καίσαρας, Mencius

Μεταβολές που βελτιστοποιούν τη λειτουργία καθυστέρησης/εξισορρόπησης και WAN.

9) Αλγόριθμοι BFT και οικογένεια PoS

9. 1 PBFT (Πρακτικός BFT)

Τρεις φάσεις (προετοιμασία/προετοιμασία/δέσμευση), απαιτούν 3f + 1 κόμβους.
Χαμηλή καθυστέρηση στα τοπικά δίκτυα, στους δρόμους πολλαπλών σταδίων και στα μηνύματα O (N 2).

9. 2 Tendermint (στυλ BFT-PoS)

Γύροι με πρόταση και δύο ψήφους (πρόληψη/προκήρυξη).
Προσδιορισμός επικυρωτή-προτείνων, χρονοδιαγράμματα, μερική συγχρονικότητα.
Καλό για επιτρεπόμενα/PoS δίκτυα με δεκάδες/εκατοντάδες επικυρωτές.

9. 3 HotStuff (και παράγωγα)

Το τριφασικό σύστημα ενοποιείται σε «πακέτα» με πιστοποιητικά απαρτίας (QC).
Η γραμμική πολυπλοκότητα των επικοινωνιών, η υποστήριξη της συσκευασίας και ο παράλληλος αγωγός, είναι βολικό για εφαρμογές σε αλυσίδες μπλοκ (για παράδειγμα, το οικοσύστημα Diem/Move).
Με τις υπογραφές κατωφλίου, η κυκλοφορία μειώνεται.

9. 4 PoW/σωρευτική συναίνεση (εν συντομία)

Όχι BFT με την αυστηρή έννοια, αλλά πιθανολογική σύγκλιση (η αλυσίδα με την περισσότερη εργασία). Πλεονεκτήματα: απλότητα/διαφάνεια· μειονεκτήματα: ενέργεια, ~ δευτερόλεπτα έως τον οριστικό χαρακτήρα.

10) Διαβάζει: γραμμική, διαδοχική, και cached

Γραμμική γραφή: επικεφαλής με ενεργό μίσθωση ή μέσω read-index (Raft) → επιβεβαίωση μέσω απαρτίας.
Διαδοχικό: μπορεί να διαβαστεί από οποιοδήποτε κόμβο, αλλά χωρίς εγγυήσεις φρεσκάδας.
Ο ακόλουθος δηλώνει: Επιτρέπεται υπό ανεπαρκείς απαιτήσεις. για κρύπτες - εντάξει.

11) Αναδιατύπωση (αλλαγή σύνθεσης συμπλέγματος)

Απαιτεί δύο αλληλεπικαλυπτόμενες διαμορφώσεις (κοινή συναίνεση): οποιεσδήποτε δεσμεύσεις απαρτίας διέλευσης και των δύο διατάξεων → χωρίς «οπές».
Προσθήκη/αφαίρεση ενός κάθε φορά, παρατήρηση του μεγέθους απαρτίας.
Η μεταβίβαση της ηγεσίας μειώνει τις παύσεις.

12) Επιδόσεις και ρύθμιση

12. 1 Καθυστερήσεις

Αλγόριθμοι ηγεσίας: 1 RTT ανά εγγραφή (με έναν σταθερό ηγέτη) + αντιγραφή.
Γεωγραφική κατανομή: Η WAN RTT κυριαρχεί → χρησιμοποιεί τοπικές περιοχές + διαπεριφερειακή αντιγραφή ή προσεγγίσεις EPaxos/HotStuff.

12. 2 Διακίνηση

Ομαδοποίηση (ομαδοποίηση εντολών), παράλληλες καταχωρήσεις, μνήμη σελίδας καταγραφής, παράλληλη εφαρμογή (όταν οι λειτουργίες αλλάζουν).
Δίσκοι: NVMe/Log σε ξεχωριστή συσκευή, 'O _ DIRECT '/AIO, μεγάλο διάστημα' fsync 'με περιορισμούς SLA (συμβιβασμός αντοχής/καθυστέρησης).

12. 3 p99 ουρές

Αποφύγετε θερμούς κόμβους (υπάρχει πάντα ένας ηγέτης): περιοδική περιστροφή ή ανάγνωση-offload σε οπαδούς.
Παρακολούθηση παύσεων GC (JVM/Go), ακίδες CPU, NUMA.

13) Γεωγραφία και τοπολογίες

1 περιφέρεια, 3 ζώνες: κλασικό σύμπλεγμα ΚΧΤ (N = 3/5).
2 περιφέρειες: αποφυγή - καμία αξιόπιστη απαρτία σε 1-1 διαίρεση.
3 + περιφέρειες: επικεφαλής των «μεσαίων» αλγορίθμων ή αλγορίθμων χωρίς ηγέτες· είναι δυνατοί περιφερειακοί διαμεσολαβητές/τοπικά μέτωπα με ασύγχρονο ημερολόγιο.

14) Πρακτικά θέματα λειτουργίας

14. 1 Στιγμιότυπα και ανάκτηση

Κατώτατο όριο ανά μέγεθος περιοδικού/αριθμό συναλλαγών.
μεταφορά στιγμιότυπου σε νέους κόμβους· Έλεγχος των σημείων ελέγχου.

14. 2 Παρακολούθηση

Ηγεσία: ποιος είναι ο ηγέτης, πόσοι όροι (όρος/εποχή) έχουν αλλάξει.
: 'append _ latency', 'commit _ index - .

Υγεία απαρτίας: «είναι η πλειοψηφία ζωντανή/2f + 1?»

Μέγεθος καταγραφής/ταχύτητα συμπίεσης, σειρά αναμονής στιγμιότυπων.

Για τον ΤΧΣ: μερίδιο ψήφου, υπογράφοντες τη χωματερή, καθυστερήσεις QC

14. 3 Κωδικός «Ασφάλεια/Συνέπεια»

Έκδοση πρωτοκόλλου στο σύρμα, μετανάστευση με συμβατότητα καταγραφής.
Δείκτες ξιφασκίας για εξωτερικές επιπτώσεις (βλέπε «Κατανεμημένες κλειδαριές»): χρόνος (όρος) μετάβασης σε CRON/θέσεις εργασίας.

15) Αντι-μοτίβα

Βάλτε συναίνεση «για χάρη της μόδας» όπου ένα DBMS ή απαρτία διαβάζει χωρίς σειρά είναι αρκετό.
Αναμείξτε CP και AP χωρίς σαφή όρια (ΚΓΠ) → απρόβλεπτο UX.
Υπερεκτίμηση του PoW/PoS για επιχειρηματικά καθήκοντα με δεκάδες κόμβους (δύσκολο/ακριβό).
Αγνοήστε την αναδιάταξη και τις «παρεμβάλλουσες απαρτίες» όταν αλλάζει η σύνθεση.
Έλλειψη φραγμού ανάγνωσης (μίσθωση/δείκτης ανάγνωσης) → βρώμικη ανάγνωση.
Εκτέλεση συσπειρώσεων 2 κόμβων (χωρίς πλειοψηφία).
Υποτίμηση δίσκων και fsync: «όλα πετάνε στη μνήμη» - μέχρι την πρώτη επανεκκίνηση.

16) Κατάλογος επιλογών

1. Μοντέλο αστοχίας: CFT (συντριβές) ή BFT (κακόβουλος)

2. Γεωγραφία: μία περιοχή/τρεις ζώνες ή WAN Η RTT αποφασίζει.
3. Ανάγνωση σημασιολογίας: είναι απαραίτητες οι γραμμικές αναγνώσεις Μίσθωση/δείκτης ανάγνωσης/παρακολούθηση.
4. Φορτίο: προσδοκίες p50/p99, διακίνηση. κατά πόσον είναι απαραίτητη η ανάληψη πολλαπλής ηγεσίας.
5. Επιχειρησιακή πολυπλοκότητα: βιβλιοθήκη/off-the-shelf κινητήρα (etcd/ZK/πρόξενος/Raft-libs) έναντι εγγενούς εφαρμογής.
6. Αναδιαμόρφωση: Συχνές Χρειαζόμαστε κοινή συναίνεση και εργαλεία μετανάστευσης.

7. Ολοκλήρωση: εξωτερικές παρενέργειες - υπάρχει περιφρόνηση ανά εποχή/όρο

8. Ασφάλεια: επαλήθευση ταυτότητας του ξενιστή, κρυπτογράφηση καναλιών, έλεγχος έκδοσης πρωτοκόλλου.
9. Test playbooks: κατάτμηση, GC-stop, kill leader, αργός δίσκος, ρολόι skew.
10. Παρατηρησιμότητα: δημιουργούνται μετρήσεις Leader/Lags/Journal και Alert.

17) Mini-guide: πότε να πάρετε ό, τι

Κλιμάκιο etcd/Raft για διατάξεις/κλειδαριές/συντονισμό εντός ΣΡ.
ZooKeeper/ZAB για υπηρεσίες που συνδέονται ήδη με ZK (παλιές στοίβες, ουρές, ηγεσία).
Πολυ-Paxos μέσω μιας έτοιμης υπηρεσίας/βιβλιοθήκης σε εξαιρετικά εξειδικευμένα συστήματα.
EPaxos για γεωγραφική κατανομή και σύγκρουση χαμηλής εντολής.
Tendermint/HotStuff για επιτρεπόμενα δίκτυα/PoS-στρώμα με δεκάδες έως εκατοντάδες επικυρωτές και απαιτήσεις οριστικότητας.
Dynamo-like/CRDT όταν δεν απαιτείται συναίνεση, αλλά η προσβασιμότητα/κλίμακα με την επακόλουθη συγχώνευση είναι σημαντική.

18) Παραδείγματα διεπαφών (ψευδο)

18. 1 Εγγραφή εγγραφής (στυλ Raft)

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 Δείκτης ανάγνωσης για γραμμική ανάγνωση (Raft)

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 (προσέγγιση HotStuff)

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

19) ΣΥΧΝΈΣ ΕΡΩΤΉΣΕΙΣ

Ε: Γιατί να μην χρησιμοποιήσουμε δύο κόμβους και ένα σπάσιμο γραβάτα

A: Δύο κόμβοι χωρίς τρίτο κριτή δεν δίνουν απαρτία στο διαχωρισμό. Χρειάζεστε ≥3 (CFT) ή 3f + 1 (BFT).

Ε: Τι είναι η ράφα «απλούστερη» Πάξος

A: Σαφής αποσύνθεση, κατανοητές αναλλοίωτες του ημερολογίου και της διαμόρφωσης. ευκολότερη εφαρμογή και συντήρηση.

Ε: Πώς διαβάζετε γρήγορα χωρίς να φορτώνετε τον αρχηγό

A: Διαβάσεις ακολούθου (διαδοχικές) για μη κρίσιμες, ή αναγνώσεις μίσθωσης/δείκτη ανάγνωσης για γραμμικές. κρύπτη.

Ε: Τι σκοτώνει το p99

A: WAN-RTT, disk fsync, GC-stops, υπερθερμαινόμενος ηγέτης, μεγάλα στιγμιότυπα σε ώρα αιχμής.

Ε: Χρειάζεται συναίνεση η μνήμη/ο κατάλογος

A: Αν υπάρχει αρκετή συνέπεια - όχι. Εάν απαιτούνται αναλλοίωτες συναλλαγές, ναι.

20) Σύνολα

"συναίνεση είναι ένα εργαλείο για αυστηρή συνέπεια και τάξη. Επιλέγεται αλγόριθμος με βάση το μοντέλο αστοχίας και τη γεωγραφία· παρέχουν διασταυρώσεις απαρτίας, σωστή αναδιάταξη, γραμμικές διαβάσεις όπου είναι κρίσιμης σημασίας και παρατηρησιμότητα. Μην ξεχνάτε την ξιφασκία για εξωτερικά εφέ, στιγμιότυπα και πειθαρχία περιοδικών. Τότε η αντιγραφή του κράτους θα είναι προβλέψιμη και τα περιστατικά θα είναι σπάνια και κατανοητά.