Ας φανταστούμε λοιπόν. 5 γάτες είναι κλειδωμένες στο δωμάτιο και για να πάνε να ξυπνήσουν τον ιδιοκτήτη, πρέπει να συμφωνήσουν όλες μαζί σε αυτό, γιατί μπορούν να ανοίξουν την πόρτα μόνο στηριζόμενοι σε αυτήν με πέντε από αυτές. Εάν μία από τις γάτες είναι η γάτα του Σρέντινγκερ και οι άλλες γάτες δεν γνωρίζουν την απόφασή του, τίθεται το ερώτημα: "Πώς μπορούν να το κάνουν αυτό;"
Σε αυτό το άρθρο, θα σας πω με απλά λόγια για τη θεωρητική συνιστώσα του κόσμου των κατανεμημένων συστημάτων και τις αρχές της δουλειάς τους. Και επίσης να εξετάσετε επιφανειακά την κύρια ιδέα που κρύβεται πίσω από τους Παξούς.
Όταν οι προγραμματιστές χρησιμοποιούν υποδομές cloud, διάφορες βάσεις δεδομένων, εργάζονται σε συμπλέγματα μεγάλου αριθμού κόμβων, είναι βέβαιοι ότι τα δεδομένα θα είναι συνεπή, ασφαλή και πάντα διαθέσιμα. Πού είναι όμως οι εγγυήσεις;
Στην πραγματικότητα, οι εγγυήσεις που έχουμε είναι εγγυήσεις προμηθευτών. Περιγράφονται στην τεκμηρίωση ως εξής: "Αυτή η υπηρεσία είναι αρκετά αξιόπιστη, έχει ένα δεδομένο SLA, μην ανησυχείτε, όλα θα λειτουργήσουν κατανεμημένα όπως περιμένετε."
Έχουμε την τάση να πιστεύουμε στο καλύτερο, γιατί έξυπνοι θείοι από μεγάλες εταιρείες μας διαβεβαίωσαν ότι όλα θα πάνε καλά. Δεν θέτουμε το ερώτημα: γιατί, στην πραγματικότητα, αυτό μπορεί να λειτουργήσει καθόλου; Υπάρχει κάποια επίσημη αιτιολόγηση για τη σωστή λειτουργία τέτοιων συστημάτων;
Πήγα πρόσφατα στο και εμπνεύστηκε πολύ από αυτό το θέμα. Οι διαλέξεις στο σχολείο έμοιαζαν περισσότερο με μαθήματα μαθηματικής ανάλυσης παρά με οτιδήποτε σχετίζεται με συστήματα υπολογιστών. Αλλά έτσι ακριβώς αποδείχτηκαν κάποτε οι πιο σημαντικοί αλγόριθμοι που χρησιμοποιούμε καθημερινά, χωρίς να το υποπτευόμαστε.
Τα περισσότερα σύγχρονα κατανεμημένα συστήματα χρησιμοποιούν τον αλγόριθμο συναίνεσης Paxos και τις διάφορες τροποποιήσεις του. Το πιο ωραίο είναι ότι η εγκυρότητα και, καταρχήν, η ίδια η πιθανότητα ύπαρξης αυτού του αλγορίθμου μπορεί να αποδειχθεί απλά με ένα στυλό και ένα χαρτί. Ταυτόχρονα, στην πράξη, ο αλγόριθμος χρησιμοποιείται σε μεγάλα συστήματα που λειτουργούν σε τεράστιο αριθμό κόμβων στα σύννεφα.
Ελαφρύ παράδειγμα αυτού που θα συζητηθεί στη συνέχεια: το πρόβλημα δύο στρατηγώνΑς ρίξουμε μια ματιά στο ζέσταμα .
Έχουμε δύο στρατούς - κόκκινο και λευκό. Τα λευκά στρατεύματα εδρεύουν στην πολιορκημένη πόλη. Κόκκινα στρατεύματα με επικεφαλής τους στρατηγούς Α1 και Α2 βρίσκονται σε δύο πλευρές της πόλης. Το καθήκον των κοκκινομάλλων είναι να επιτεθούν στη λευκή πόλη και να κερδίσουν. Ωστόσο, ο στρατός του κάθε κόκκινου στρατηγού ξεχωριστά είναι μικρότερος από τον στρατό των λευκών.
Προϋποθέσεις νίκης για τους κοκκινομάλλες: και οι δύο στρατηγοί πρέπει να επιτεθούν ταυτόχρονα για να έχουν αριθμητικό πλεονέκτημα έναντι των λευκών. Για να γίνει αυτό, οι στρατηγοί Α1 και Α2 πρέπει να συμφωνήσουν μεταξύ τους. Αν όλοι επιτεθούν χωριστά, οι κοκκινομάλλες θα χάσουν.
Για να διαπραγματευτούν, οι στρατηγοί Α1 και Α2 μπορούν να στείλουν αγγελιοφόρους ο ένας στον άλλο μέσω της επικράτειας της λευκής πόλης. Ο αγγελιοφόρος μπορεί να φτάσει με επιτυχία σε έναν σύμμαχο στρατηγό ή μπορεί να αναχαιτιστεί από τον εχθρό. Ερώτηση: υπάρχει τέτοια αλληλουχία επικοινωνιών μεταξύ των κοκκινομάλληδων στρατηγών (η αλληλουχία αποστολής αγγελιοφόρων από τον Α1 στον Α2 και αντίστροφα από τον Α2 στον Α1), στην οποία είναι εγγυημένο ότι θα συμφωνήσουν σε μια επίθεση την ώρα Χ. Εδώ, με εγγυήσεις γίνεται κατανοητό ότι και οι δύο στρατηγοί θα έχουν αδιαμφισβήτητη επιβεβαίωση ότι ένας σύμμαχος (άλλος στρατηγός) θα επιτεθεί ακριβώς την καθορισμένη ώρα Χ.
Ας υποθέσουμε ότι ο Α1 στέλνει έναν αγγελιοφόρο στον Α2 με το μήνυμα: «Ας επιτεθούμε σήμερα τα μεσάνυχτα!». Ο στρατηγός Α1 δεν μπορεί να επιτεθεί χωρίς επιβεβαίωση από τον στρατηγό Α2. Εάν ο αγγελιοφόρος από το Α1 έχει φτάσει, τότε ο στρατηγός Α2 στέλνει μια επιβεβαίωση με το μήνυμα: "Ναι, ας γεμίσουμε τα λευκά σήμερα." Αλλά τώρα ο στρατηγός Α2 δεν γνωρίζει αν ο αγγελιοφόρος του έφτασε ή όχι, δεν έχει εγγυήσεις αν η επίθεση θα είναι ταυτόχρονη. Τώρα το Γενικό Α2 χρειάζεται και πάλι επιβεβαίωση.
Αν περιγράψουμε περαιτέρω την επικοινωνία τους, προκύπτει το εξής: ανεξάρτητα από το πόσοι κύκλοι ανταλλαγής μηνυμάτων υπάρχουν, δεν υπάρχει τρόπος να εγγυηθούμε και στους δύο στρατηγούς ότι τα μηνύματά τους έχουν ληφθεί (υποθέτοντας ότι κάποιος από τους αγγελιοφόρους μπορεί να υποκλαπεί).
Το πρόβλημα των δύο γενικών είναι μια εξαιρετική απεικόνιση ενός πολύ απλού κατανεμημένου συστήματος όπου υπάρχουν δύο κόμβοι με αναξιόπιστη επικοινωνία. Άρα δεν έχουμε 100% εγγύηση ότι είναι συγχρονισμένα. Σχετικά με παρόμοια προβλήματα μόνο σε μεγαλύτερη κλίμακα αργότερα στο άρθρο.
Εισαγωγή της έννοιας των κατανεμημένων συστημάτων
Ένα κατανεμημένο σύστημα είναι μια ομάδα υπολογιστών (εφεξής καλούμενοι κόμβοι) που μπορούν να ανταλλάσσουν μηνύματα. Κάθε μεμονωμένος κόμβος είναι κάποια αυτόνομη οντότητα. Ένας κόμβος μπορεί να επεξεργαστεί εργασίες μόνος του, αλλά για να επικοινωνήσει με άλλους κόμβους, χρειάζεται να στέλνει και να λαμβάνει μηνύματα.
Πώς υλοποιούνται συγκεκριμένα τα μηνύματα, ποια πρωτόκολλα χρησιμοποιούνται - αυτό δεν μας ενδιαφέρει σε αυτό το πλαίσιο. Είναι σημαντικό οι κόμβοι ενός κατανεμημένου συστήματος να μπορούν να ανταλλάσσουν δεδομένα μεταξύ τους στέλνοντας μηνύματα.
Ο ίδιος ο ορισμός δεν φαίνεται πολύ περίπλοκος, αλλά έχετε κατά νου ότι ένα κατανεμημένο σύστημα έχει μια σειρά από χαρακτηριστικά που θα είναι σημαντικά για εμάς.
Χαρακτηριστικά κατανεμημένων συστημάτων
- Συγχρονισμός – τη δυνατότητα εμφάνισης ταυτόχρονων ή ανταγωνιστικών γεγονότων στο σύστημα. Επιπλέον, θα θεωρήσουμε ότι συμβάντα που συνέβησαν σε δύο διαφορετικούς κόμβους είναι δυνητικά ταυτόχρονα μέχρι να έχουμε μια σαφή σειρά με την οποία συμβαίνουν αυτά τα συμβάντα. Και συνήθως δεν το κάνουμε.
- Χωρίς παγκόσμιο ρολόι. Δεν έχουμε ξεκάθαρη σειρά γεγονότων λόγω έλλειψης παγκόσμιου ρολογιού. Στον συνηθισμένο κόσμο των ανθρώπων, έχουμε συνηθίσει στο γεγονός ότι έχουμε ώρες και χρόνο απολύτως. Όλα αλλάζουν όταν πρόκειται για κατανεμημένα συστήματα. Ακόμη και τα εξαιρετικά ακριβή ατομικά ρολόγια έχουν μετατόπιση και υπάρχουν καταστάσεις όπου δεν μπορούμε να πούμε ποιο από τα δύο γεγονότα συνέβη πρώτο. Επομένως, δεν μπορούμε να βασιστούμε ούτε στον χρόνο.
- Ανεξάρτητη αστοχία κόμβων συστήματος. Υπάρχει ένα άλλο πρόβλημα: κάτι μπορεί να πάει στραβά απλώς και μόνο επειδή οι κόμβοι μας δεν είναι αιώνιοι. Ο σκληρός δίσκος μπορεί να αποτύχει, η εικονική μηχανή στο cloud μπορεί να επανεκκινηθεί, το δίκτυο μπορεί να αναβοσβήνει και τα μηνύματα θα χαθούν. Επιπλέον, υπάρχουν περιπτώσεις όπου οι κόμβοι λειτουργούν, αλλά ταυτόχρονα λειτουργούν ενάντια στο σύστημα. Η τελευταία κατηγορία προβλημάτων έλαβε ακόμη και ένα ξεχωριστό όνομα: το πρόβλημα . Το πιο δημοφιλές παράδειγμα κατανεμημένου συστήματος με τέτοιο πρόβλημα είναι το Blockchain. Αλλά σήμερα δεν θα εξετάσουμε αυτήν την ειδική κατηγορία προβλημάτων. Θα μας ενδιαφέρουν καταστάσεις στις οποίες μόνο ένας ή περισσότεροι κόμβοι μπορούν να αποτύχουν.
- Μοντέλα επικοινωνίας (μοντέλα μηνυμάτων) μεταξύ κόμβων. Έχουμε ήδη ανακαλύψει ότι οι κόμβοι επικοινωνούν ανταλλάσσοντας μηνύματα. Υπάρχουν δύο γνωστά μοντέλα ανταλλαγής μηνυμάτων: η σύγχρονη και η ασύγχρονη.
Μοντέλα επικοινωνίας μεταξύ κόμβων σε κατανεμημένα συστήματα
Σύγχρονο μοντέλο - γνωρίζουμε με βεβαιότητα ότι υπάρχει ένα πεπερασμένο γνωστό δέλτα χρόνου για το οποίο το μήνυμα είναι εγγυημένο ότι θα φτάσει από τον έναν κόμβο στον άλλο. Εάν αυτός ο χρόνος έχει παρέλθει και το μήνυμα δεν έχει φτάσει, μπορούμε με ασφάλεια να πούμε ότι ο κόμβος απέτυχε. Σε ένα τέτοιο μοντέλο, έχουμε προβλέψιμο χρόνο αναμονής.
Ασύγχρονο μοντέλο – σε ασύγχρονα μοντέλα, υποθέτουμε ότι ο χρόνος αναμονής είναι πεπερασμένος, αλλά δεν υπάρχει χρονικό δέλτα μετά το οποίο μπορούμε να εγγυηθούμε ότι ο κόμβος έχει αποτύχει. Εκείνοι. ο χρόνος αναμονής για ένα μήνυμα από έναν κόμβο μπορεί να είναι αυθαίρετα μεγάλος. Αυτός είναι ένας σημαντικός ορισμός και θα μιλήσουμε για αυτόν περαιτέρω.
Η έννοια της συναίνεσης στα κατανεμημένα συστήματα
Πριν ορίσετε επίσημα την έννοια της συναίνεσης, εξετάστε ένα παράδειγμα κατάστασης όπου τη χρειαζόμαστε, δηλαδή − Αντιγραφή κατάστασης μηχανής.
Έχουμε κάποιο κατανεμημένο αρχείο καταγραφής. Θα θέλαμε να είναι συνεπής και να περιέχει πανομοιότυπα δεδομένα σε όλους τους κόμβους ενός κατανεμημένου συστήματος. Όταν ένας από τους κόμβους μαθαίνει μια νέα τιμή που πρόκειται να γράψει στο αρχείο καταγραφής, η αποστολή του είναι να προσφέρει αυτήν την τιμή σε όλους τους άλλους κόμβους, έτσι ώστε το αρχείο καταγραφής να ενημερώνεται σε όλους τους κόμβους και το σύστημα να μεταβαίνει σε μια νέα συνεπή κατάσταση. Ταυτόχρονα, είναι σημαντικό οι κόμβοι να συμφωνούν μεταξύ τους: όλοι οι κόμβοι συμφωνούν ότι η προτεινόμενη νέα τιμή είναι σωστή, όλοι οι κόμβοι αποδέχονται αυτήν την τιμή και μόνο σε αυτήν την περίπτωση μπορούν όλοι να καταγράψουν μια νέα τιμή.
Με άλλα λόγια: κανένας από τους κόμβους δεν αντιτάχθηκε ότι είχε πιο ενημερωμένες πληροφορίες και η προτεινόμενη τιμή ήταν εσφαλμένη. Μια συμφωνία μεταξύ κόμβων και συμφωνία για μια ενιαία σωστή αποδεκτή τιμή είναι η συναίνεση σε ένα κατανεμημένο σύστημα. Στη συνέχεια, θα μιλήσουμε για αλγόριθμους που επιτρέπουν σε ένα κατανεμημένο σύστημα να καταλήξει σε συναίνεση με εγγύηση.
Πιο τυπικά, μπορούμε να ορίσουμε έναν αλγόριθμο συναίνεσης (ή απλά έναν αλγόριθμο συναίνεσης) ως κάποια συνάρτηση που μεταφέρει ένα κατανεμημένο σύστημα από την κατάσταση Α στην κατάσταση Β. Επιπλέον, αυτή η κατάσταση είναι αποδεκτή από όλους τους κόμβους και όλοι οι κόμβοι μπορούν να την επιβεβαιώσουν. Όπως αποδεικνύεται, αυτό το έργο δεν είναι καθόλου τόσο ασήμαντο όσο φαίνεται με την πρώτη ματιά.
Ιδιότητες του αλγορίθμου συναίνεσης
Ο αλγόριθμος συναίνεσης πρέπει να έχει τρεις ιδιότητες προκειμένου το σύστημα να συνεχίσει να υπάρχει και να έχει κάποια πρόοδο στη μετάβαση από κατάσταση σε κατάσταση:
- Συμφωνία – όλοι οι κόμβοι που λειτουργούν σωστά πρέπει να έχουν την ίδια τιμή (στα άρθρα αυτή η ιδιότητα βρίσκεται επίσης ως ιδιότητα ασφαλείας). Όλοι οι κόμβοι που τώρα λειτουργούν (όχι εκτός λειτουργίας και δεν έχουν χαθεί η επαφή με τους υπόλοιπους) πρέπει να έρθουν σε συμφωνία και να αποδεχτούν κάποια τελική κοινή αξία.
Είναι σημαντικό να κατανοήσουμε εδώ ότι οι κόμβοι στο κατανεμημένο σύστημα που εξετάζουμε θέλουν να συμφωνήσουν. Δηλαδή, τώρα μιλάμε για συστήματα στα οποία κάτι μπορεί απλά να αποτύχει (για παράδειγμα, κάποιος κόμβος αποτυγχάνει), αλλά σε αυτό το σύστημα σίγουρα δεν υπάρχουν κόμβοι που σκόπιμα λειτουργούν εναντίον άλλων (το καθήκον των βυζαντινών στρατηγών). Λόγω αυτής της ιδιότητας, το σύστημα παραμένει συνεπές.
- Ακεραιότητα - εάν όλοι οι κόμβοι που λειτουργούν σωστά προσφέρουν την ίδια τιμή v, επομένως κάθε κόμβος που λειτουργεί σωστά πρέπει να δέχεται αυτήν την τιμή v.
- Λήξη - όλοι οι κόμβοι που λειτουργούν σωστά θα λάβουν τελικά κάποια τιμή (ιδιότητα ζωντανότητας), η οποία επιτρέπει στον αλγόριθμο να έχει πρόοδο στο σύστημα. Κάθε μεμονωμένος κόμβος που λειτουργεί σωστά πρέπει αργά ή γρήγορα να αποδεχτεί την τελική τιμή και να την επιβεβαιώσει: "Για μένα, αυτή η τιμή είναι αληθινή, συμφωνώ με ολόκληρο το σύστημα."
Ένα παράδειγμα για το πώς λειτουργεί ο αλγόριθμος συναίνεσης
Ενώ οι ιδιότητες του αλγορίθμου μπορεί να μην είναι απολύτως σαφείς. Επομένως, θα δείξουμε με ένα παράδειγμα ποια στάδια περνά ο απλούστερος αλγόριθμος συναίνεσης σε ένα σύστημα με μοντέλο σύγχρονων μηνυμάτων, στο οποίο όλοι οι κόμβοι λειτουργούν όπως αναμένεται, τα μηνύματα δεν χάνονται και τίποτα δεν σπάει (συμβαίνει αυτό πραγματικά;).
- Όλα ξεκινούν με μια πρόταση γάμου (Πρόταση). Ας υποθέσουμε ότι ένας πελάτης συνδέεται με έναν κόμβο που ονομάζεται "Node 1" και ξεκινά μια συναλλαγή, περνώντας μια νέα τιμή στον κόμβο - O. Από εδώ και πέρα, θα καλούμε "Node 1" προσφορά. Πώς πρέπει τώρα ο προτείνων "Κόμβος 1" να ειδοποιήσει όλο το σύστημα ότι έχει νέα δεδομένα και στέλνει μηνύματα σε όλους τους άλλους κόμβους: "Κοίτα! Έλαβα την τιμή "O" και θέλω να τη γράψω! Επιβεβαιώστε ότι θα καταγράψετε επίσης το "O" στο αρχείο καταγραφής σας."
- Το επόμενο στάδιο είναι η ψηφοφορία για την προτεινόμενη τιμή (Voting). Σε τι χρησιμεύει; Μπορεί να συμβεί ότι άλλοι κόμβοι έλαβαν πιο πρόσφατες πληροφορίες και έχουν δεδομένα για την ίδια συναλλαγή.
Όταν ο κόμβος "Κόμβος 1" στέλνει την πρόταση του, οι άλλοι κόμβοι ελέγχουν τα αρχεία καταγραφής τους για δεδομένα σχετικά με αυτό το συμβάν. Εάν δεν υπάρχει σύγκρουση, οι κόμβοι ανακοινώνουν: «Ναι, δεν έχω άλλα δεδομένα για αυτό το συμβάν. Η τιμή "O" είναι η πιο ενημερωμένη πληροφορία που μας αξίζει."Σε κάθε άλλη περίπτωση, οι κόμβοι μπορούν να απαντήσουν στον «Κόμβο 1»: «Ακούστε! Έχω πιο πρόσφατα στοιχεία για αυτήν τη συναλλαγή. Όχι «Ω», αλλά κάτι καλύτερο».
Στο στάδιο της ψηφοφορίας, οι κόμβοι καταλήγουν σε μια απόφαση: είτε αποδέχονται όλοι την ίδια τιμή, είτε ένας από αυτούς ψηφίζει κατά, δηλώνοντας ότι έχει πιο πρόσφατα δεδομένα.
- Εάν ο γύρος ψηφοφορίας ήταν επιτυχής, και όλοι ήταν υπέρ, τότε το σύστημα περνά σε ένα νέο στάδιο - αποδοχή της αξίας (Αποδοχή). Το "Node 1" συλλέγει όλες τις απαντήσεις από άλλους κόμβους και αναφέρει: "Όλοι συμφώνησαν στην τιμή "O"! Τώρα δηλώνω επίσημα ότι το «Ο» είναι η νέα μας σημασία, το ίδιο για όλους! Σημειώστε το στο τετράδιό σας, μην ξεχάσετε. Γράψε στο ημερολόγιο σου!"
- Οι υπόλοιποι κόμβοι στέλνουν επιβεβαίωση (Accepted) ότι έχουν σημειώσει την τιμή "O" για τον εαυτό τους, δεν έχει ληφθεί τίποτα νέο κατά τη διάρκεια αυτής της περιόδου (ένα είδος δέσμευσης δύο φάσεων). Μετά από αυτό το σημαντικό γεγονός, θεωρούμε ότι η κατανεμημένη συναλλαγή έχει ολοκληρωθεί.
Έτσι, ο αλγόριθμος συναίνεσης σε μια απλή περίπτωση αποτελείται από τέσσερα βήματα: πρόταση, ψηφοφορία (ψηφοφορία), αποδοχή (αποδοχή), επιβεβαίωση αποδοχής (αποδοχή).
Εάν σε κάποιο βήμα δεν μπορέσουμε να καταλήξουμε σε συμφωνία, τότε ο αλγόριθμος επανεκκινείται, λαμβάνοντας υπόψη τις πληροφορίες που παρέχονται από τους κόμβους που αρνήθηκαν να επιβεβαιώσουν την προτεινόμενη τιμή.
Συναινετικός αλγόριθμος σε ασύγχρονο σύστημα
Πριν από αυτό, όλα ήταν ομαλά, γιατί επρόκειτο για το μοντέλο σύγχρονων μηνυμάτων. Αλλά ξέρουμε ότι στον σύγχρονο κόσμο έχουμε συνηθίσει να κάνουμε τα πάντα ασύγχρονα. Πώς λειτουργεί ένας παρόμοιος αλγόριθμος σε ένα σύστημα με ένα μοντέλο ασύγχρονης ανταλλαγής μηνυμάτων, όπου πιστεύουμε ότι ο χρόνος αναμονής για μια απάντηση από έναν κόμβο μπορεί να είναι αυθαίρετα μεγάλος (παρεμπιπτόντως, μια αποτυχία κόμβου μπορεί επίσης να θεωρηθεί ως παράδειγμα όταν ένας κόμβος μπορεί να απαντήσει αυθαίρετα για μεγάλο χρονικό διάστημα).
Τώρα που γνωρίζουμε πώς λειτουργεί κατ' αρχήν ο αλγόριθμος συναίνεσης, το ερώτημα είναι για εκείνους τους περίεργους αναγνώστες που έχουν φτάσει σε αυτό το σημείο: πόσοι κόμβοι σε ένα σύστημα Ν κόμβων με ένα μοντέλο ασύγχρονου μηνύματος μπορούν να μειωθούν έτσι ώστε το σύστημα να μπορεί ακόμα να επιτύχει συναίνεση ?
Η σωστή απάντηση και το σκεπτικό πίσω από το spoiler.Σωστή απάντηση: 0. Εάν έστω και ένας κόμβος σε ένα ασύγχρονο σύστημα πέσει, το σύστημα δεν θα μπορέσει να επιτύχει συναίνεση. Αυτή η δήλωση αποδεικνύεται στο γνωστό θεώρημα FLP (1985, Fischer, Lynch, Paterson, σύνδεσμος προς το πρωτότυπο στο τέλος του άρθρου): «Η αδυναμία επίτευξης μιας κατανεμημένης συναίνεσης εάν αποτύχει τουλάχιστον ένας κόμβος».
Παιδιά τότε έχουμε πρόβλημα, έχουμε συνηθίσει να είναι όλα ασύγχρονα μαζί μας. Και εδώ είναι. Πώς να συνεχίσετε να ζείτε;
Μόλις μιλήσαμε για θεωρία, για μαθηματικά. Τι σημαίνει «δεν μπορεί να επιτευχθεί συναίνεση», μεταφράζοντας από τη μαθηματική γλώσσα στη δική μας - μηχανική; Αυτό σημαίνει ότι «δεν μπορεί πάντα να επιτευχθεί», δηλ. υπάρχει περίπτωση που δεν είναι εφικτή η συναίνεση. Και τι είναι αυτή η περίπτωση;
Αυτή ακριβώς είναι η παραβίαση της ιδιότητας της ζωντάνιας που περιγράφηκε παραπάνω. Δεν έχουμε κοινή συμφωνία και το σύστημα δεν μπορεί να προχωρήσει (δεν μπορεί να τερματιστεί σε πεπερασμένο χρόνο) στην περίπτωση που δεν έχουμε απόκριση από όλους τους κόμβους. Επειδή σε ένα ασύγχρονο σύστημα δεν έχουμε προβλέψιμο χρόνο απόκρισης και δεν μπορούμε να γνωρίζουμε εάν ένας κόμβος είναι εκτός λειτουργίας ή απλά χρειάζεται πολύς χρόνος για να ανταποκριθεί.
Αλλά στην πράξη, μπορούμε να βρούμε μια λύση. Αφήστε τον αλγόριθμό μας να μπορεί να λειτουργεί για μεγάλο χρονικό διάστημα σε περίπτωση αποτυχίας (ενδεχομένως μπορεί να λειτουργεί επ 'αόριστον). Αλλά στις περισσότερες περιπτώσεις, όταν οι περισσότεροι κόμβοι λειτουργούν σωστά, θα έχουμε πρόοδο στο σύστημα.
Στην πράξη, έχουμε να κάνουμε με εν μέρει σύγχρονα μοντέλα επικοινωνίας. Ο μερικός συγχρονισμός γίνεται κατανοητός ως εξής: στη γενική περίπτωση, έχουμε ένα ασύγχρονο μοντέλο, αλλά μια ορισμένη έννοια του "χρόνου παγκόσμιας σταθεροποίησης" μιας συγκεκριμένης χρονικής στιγμής εισάγεται επίσημα.
Αυτή η χρονική στιγμή μπορεί να μην έρθει για αυθαίρετα μεγάλο χρονικό διάστημα, αλλά μια μέρα πρέπει να έρθει. Το εικονικό ξυπνητήρι θα χτυπήσει και από εκείνη τη στιγμή μπορούμε να προβλέψουμε το δέλτα ώρας στο οποίο θα φτάσουν τα μηνύματα. Από αυτό το σημείο και μετά, το σύστημα μετατρέπεται από ασύγχρονο σε σύγχρονο. Στην πράξη ασχολούμαστε με τέτοια συστήματα.
Ο αλγόριθμος Paxos λύνει προβλήματα συναίνεσης
είναι μια οικογένεια αλγορίθμων που λύνουν το πρόβλημα συναίνεσης για μερικώς σύγχρονα συστήματα, υπό την προϋπόθεση ότι ορισμένοι κόμβοι μπορεί να αποτύχουν. Ο συγγραφέας των Παξών είναι . Πρότεινε μια επίσημη απόδειξη της ύπαρξης και της ορθότητας του αλγορίθμου το 1989.
Αλλά η απόδειξη δεν ήταν καθόλου ασήμαντη. Η πρώτη δημοσίευση κυκλοφόρησε μόλις το 1998 (33 σελίδες) που περιγράφει τον αλγόριθμο. Όπως αποδείχθηκε, ήταν εξαιρετικά δύσκολο να γίνει κατανοητό και το 2001 δημοσιεύτηκε μια εξήγηση για το άρθρο, η οποία πήρε 14 σελίδες. Οι τόμοι των δημοσιεύσεων δίνονται για να δείξουν ότι στην πραγματικότητα το πρόβλημα της συναίνεσης δεν είναι καθόλου απλό και πίσω από τέτοιους αλγόριθμους υπάρχει ένα τεράστιο έργο των πιο έξυπνων ανθρώπων.
Είναι ενδιαφέρον ότι ο ίδιος ο Leslie Lampor στη διάλεξή του σημείωσε ότι στο δεύτερο άρθρο-επεξήγηση υπάρχει μια δήλωση, μια γραμμή (δεν διευκρίνισε ποια), η οποία μπορεί να ερμηνευτεί με διαφορετικούς τρόπους. Και εξαιτίας αυτού, ένας μεγάλος αριθμός σύγχρονων υλοποιήσεων Paxos δεν λειτουργούν αρκετά σωστά.
Μια λεπτομερής ανάλυση του έργου των Παξών θα πάρει περισσότερα από ένα άρθρα, γι' αυτό θα προσπαθήσω να μεταφέρω την κύρια ιδέα του αλγορίθμου πολύ σύντομα. Στους συνδέσμους στο τέλος του άρθρου μου θα βρείτε υλικά για περαιτέρω κατάδυση σε αυτό το θέμα.
Ρόλοι στους Παξούς
Ο αλγόριθμος Paxos έχει μια έννοια ρόλων. Εξετάστε τρεις κύριες (υπάρχουν τροποποιήσεις με πρόσθετους ρόλους):
- Προτείνοντες (μπορεί να υπάρχουν και όροι: ηγέτες ή συντονιστές). Αυτοί είναι οι τύποι που μαθαίνουν για κάποιο νέο νόημα από τον χρήστη και αναλαμβάνουν τον ρόλο του ηγέτη. Το καθήκον τους είναι να ξεκινήσουν έναν κύκλο προτάσεων για μια νέα αξία και να συντονίσουν περαιτέρω ενέργειες των κόμβων. Επιπλέον, οι Παξοί επιτρέπουν την παρουσία πολλών ηγετών σε συγκεκριμένες καταστάσεις.
- Αποδέκτες (ψηφοφόροι). Αυτοί είναι οι κόμβοι που ψηφίζουν για την αποδοχή ή την απόρριψη μιας συγκεκριμένης τιμής. Ο ρόλος τους είναι πολύ σημαντικός, γιατί η απόφαση εξαρτάται από αυτούς: σε ποια κατάσταση θα πάει (ή όχι) το σύστημα μετά το επόμενο στάδιο του αλγορίθμου συναίνεσης.
- Μαθητές. Κόμβοι που απλώς δέχονται και γράφουν τη νέα αποδεκτή τιμή όταν έχει αλλάξει η κατάσταση του συστήματος. Δεν παίρνουν αποφάσεις, απλώς λαμβάνουν δεδομένα και μπορούν να τα δώσουν στον τελικό χρήστη.
Ένας κόμβος μπορεί να συνδυάσει πολλούς ρόλους σε διαφορετικές καταστάσεις.
Η έννοια της απαρτίας
Υποθέτουμε ότι έχουμε ένα σύστημα N κόμβους. Και οι περισσότεροι από αυτούς F οι κόμβοι μπορεί να αποτύχουν. Εάν οι κόμβοι F αποτύχουν, τότε θα πρέπει να έχουμε τουλάχιστον 2F+1 κόμβους αποδοχής.
Αυτό είναι απαραίτητο ώστε πάντα, ακόμη και στη χειρότερη κατάσταση, οι «καλοί», σωστά λειτουργικοί κόμβοι να έχουμε πλειοψηφία. Αυτό είναι f+1 "καλοί" κόμβοι που συμφώνησαν και η τελική τιμή θα γίνει αποδεκτή. Διαφορετικά, μπορεί να υπάρξει μια κατάσταση όπου διαφορετικές τοπικές ομάδες θα αποκτήσουν διαφορετικές έννοιες και δεν θα μπορούν να συμφωνήσουν μεταξύ τους. Χρειαζόμαστε λοιπόν απόλυτη πλειοψηφία για να κερδίσουμε την ψήφο.
Γενική ιδέα του αλγορίθμου συναίνεσης των Παξών
Ο αλγόριθμος Paxos υποθέτει δύο μεγάλες φάσεις, οι οποίες με τη σειρά τους χωρίζονται σε δύο βήματα το καθένα:
- Φάση 1α: Προετοιμασία. Κατά το στάδιο της προετοιμασίας, ο αρχηγός (προτάτης) ενημερώνει όλους τους κόμβους: «Ξεκινάμε ένα νέο στάδιο ψηφοφορίας. Έχουμε νέο γύρο. Ο αριθμός αυτού του γύρου είναι n. Θα αρχίσουμε να ψηφίζουμε τώρα». Μέχρι στιγμής, αναφέρει απλώς την έναρξη ενός νέου κύκλου, αλλά δεν αναφέρει τη νέα τιμή. Ο στόχος αυτού του σταδίου είναι να ξεκινήσει ένας νέος γύρος και να ενημερώσει όλους για τον μοναδικό του αριθμό. Ο αριθμός του γύρου είναι σημαντικός, πρέπει να είναι μεγαλύτερος από όλους τους προηγούμενους αριθμούς ψηφοφορίας από όλους τους προηγούμενους αρχηγούς. Δεδομένου ότι χάρη στον στρογγυλό αριθμό άλλοι κόμβοι στο σύστημα θα καταλάβουν πόσο φρέσκα είναι τα δεδομένα του ηγέτη. Πιθανώς άλλοι κόμβοι έχουν ήδη αποτελέσματα ψηφοφορίας από πολύ μεταγενέστερους γύρους και απλώς θα πουν στον αρχηγό ότι είναι πίσω από την εποχή.
- Φάση 1β: Υπόσχεση. Όταν οι κόμβοι αποδοχής έχουν λάβει τον αριθμό του νέου σταδίου ψηφοφορίας, είναι δυνατά δύο αποτελέσματα:
- Ο αριθμός n της νέας ψηφοφορίας είναι μεγαλύτερος από τον αριθμό οποιασδήποτε από τις προηγούμενες ψηφοφορίες στις οποίες συμμετείχε ο αποδέκτης. Στη συνέχεια, ο αποδέκτης στέλνει μια υπόσχεση στον αρχηγό ότι δεν θα συμμετέχει πλέον σε ψηφοφορίες με αριθμό μικρότερο από n. Εάν ο αποδέκτης έχει ήδη ψηφίσει κάτι (δηλαδή έχει ήδη αποδεχθεί κάποια αξία στη δεύτερη φάση), τότε προσαρτά την αποδεκτή τιμή και τον αριθμό της ψήφου στην οποία συμμετείχε στην υπόσχεσή του.
- Διαφορετικά, εάν ο αποδέκτης γνωρίζει ήδη για την ψηφοφορία με υψηλό αριθμό, μπορεί απλώς να αγνοήσει το βήμα προετοιμασίας και να μην απαντήσει στον αρχηγό.
- Φάση 2α: Αποδοχή. Ο ηγέτης πρέπει να περιμένει μια απάντηση από την απαρτία (οι περισσότεροι κόμβοι του συστήματος) και, εάν ληφθεί ο απαιτούμενος αριθμός απαντήσεων, τότε έχει δύο επιλογές για την ανάπτυξη γεγονότων:
- Μερικοί από τους αποδέκτες έχουν υποβάλει τιμές που έχουν ήδη ψηφίσει. Σε αυτή την περίπτωση, ο αρχηγός επιλέγει την τιμή από την ψήφο με τον μεγαλύτερο αριθμό. Ας ονομάσουμε αυτήν την τιμή x, και ας στείλουμε ένα μήνυμα όπως αυτό σε όλους τους κόμβους: "Αποδοχή (n, x)", όπου η πρώτη τιμή είναι ο αριθμός ψηφοφορίας από το δικό του βήμα Πρότασης και η δεύτερη τιμή είναι αυτό για το οποίο συγκεντρώθηκαν όλοι, π.χ. αξία για την οποία μάλιστα ψηφίζουμε.
- Εάν κανένας από τους αποδέκτες δεν έστειλε τιμές, αλλά απλώς υποσχέθηκαν να ψηφίσουν σε αυτόν τον γύρο, ο αρχηγός μπορεί να τους καλέσει να ψηφίσουν για την αξία τους, την αξία για την οποία έγινε ηγέτης. Ας το ονομάσουμε y. Στέλνει σε όλους τους κόμβους ένα μήνυμα της μορφής: "Accept (n, y)", κατ' αναλογία με το προηγούμενο αποτέλεσμα.
- Φάση 2β: Αποδεκτό. Επιπλέον, οι κόμβοι αποδέκτες, μόλις λάβουν το μήνυμα "Αποδοχή (...)", από τον αρχηγό συμφωνούν με αυτό (στείλουν επιβεβαίωση σε όλους τους κόμβους ότι συμφωνούν με τη νέα τιμή) μόνο εάν δεν έχουν υποσχεθεί κάποια (άλλα ) αρχηγός να συμμετάσχει στην ψηφοφορία με τον αριθμό του γύρου n' > nΔιαφορετικά, αγνοούν την προτροπή επιβεβαίωσης.
Εάν η πλειονότητα των κόμβων απάντησε στον οδηγό και όλοι επιβεβαίωσαν τη νέα τιμή, τότε η νέα τιμή θεωρείται αποδεκτή. Ζήτω! Εάν η πλειοψηφία δεν είναι πληκτρολογημένη ή υπάρχουν κόμβοι που αρνήθηκαν να δεχτούν τη νέα τιμή, τότε όλα ξεκινούν από την αρχή.
Έτσι λειτουργεί ο αλγόριθμος των Παξών. Κάθε ένα από αυτά τα στάδια έχει πολλές λεπτές αποχρώσεις, πρακτικά δεν εξετάσαμε διάφορους τύπους αποτυχιών, προβλήματα πολλαπλών ηγετών και πολλά άλλα, αλλά ο σκοπός αυτού του άρθρου είναι μόνο να εισαγάγει τον αναγνώστη στον κόσμο των κατανεμημένων υπολογιστών σε ανώτατο επίπεδο.
Αξίζει επίσης να σημειωθεί ότι οι Παξοί δεν είναι οι μόνοι στο είδος τους, υπάρχουν και άλλοι αλγόριθμοι, π.χ. , αλλά αυτό είναι θέμα για άλλο άρθρο.
Σύνδεσμοι με υλικό για περαιτέρω μελέτη
Επίπεδο αρχαρίων:
- , Preethi Kasireddy, άρθρο ιστολογίου στο Medium
- , Adi Kancherla, άρθρο ιστολογίου στο Medium
- Ιστολόγιο Ittai Abraham
- , Ittai Abraham, άρθρο ιστολογίου
Επίπεδο Leslie Lamport:
- Fischer, Lynch and Paterson, ερευνητική εργασία, 1985
- , Leslie Lamport, ερευνητική εργασία, 1998
- , Leslie Lamport, ερευνητική εργασία, 2001
Πηγή: www.habr.com