Κατανεμημένο κλείδωμα με χρήση Redis

Γεια σου Χαμπρ!

Σήμερα φέρνουμε στην προσοχή σας μια μετάφραση ενός περίπλοκου άρθρου σχετικά με την εφαρμογή του κατανεμημένου κλειδώματος με χρήση του Redis και σας προσκαλούμε να μιλήσετε για τις προοπτικές του Redis ως θέμα. Ανάλυση του εν λόγω αλγορίθμου Redlock από τον Martin Kleppmann, συγγραφέα του βιβλίου "Εφαρμογές Υψηλού Φορτίου», δεδομένο εδώ.

Το κατανεμημένο κλείδωμα είναι ένα πολύ χρήσιμο πρωτόγονο που χρησιμοποιείται σε πολλά περιβάλλοντα όπου διαφορετικές διαδικασίες πρέπει να λειτουργούν σε κοινόχρηστους πόρους με αμοιβαία αποκλειστικό τρόπο.

Υπάρχει ένας αριθμός βιβλιοθηκών και αναρτήσεων εκεί έξω που περιγράφουν τον τρόπο υλοποίησης του DLM (Distributed Lock Manager) χρησιμοποιώντας το Redis, αλλά κάθε βιβλιοθήκη ακολουθεί διαφορετική προσέγγιση και οι εγγυήσεις που παρέχουν είναι αρκετά αδύναμες σε σύγκριση με αυτό που μπορεί να επιτευχθεί με ελαφρώς πιο εξελιγμένο σχεδιασμό.

Σε αυτό το άρθρο θα προσπαθήσουμε να περιγράψουμε έναν κανονικό αλγόριθμο υπό όρους που δείχνει πώς να υλοποιήσετε το κατανεμημένο κλείδωμα χρησιμοποιώντας το Redis. Θα μιλήσουμε για έναν αλγόριθμο που ονομάζεται redlock, υλοποιεί έναν κατανεμημένο διαχειριστή κλειδαριών και, κατά τη γνώμη μας, αυτός ο αλγόριθμος είναι ασφαλέστερος από τη συνηθισμένη προσέγγιση μιας παρουσίας. Ελπίζουμε ότι η κοινότητα θα το αναλύσει, θα παράσχει σχόλια και θα το χρησιμοποιήσει ως σημείο εκκίνησης για πιο σύνθετα ή εναλλακτικά έργα.

Υλοποιήσεις

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

• Redlock-rb (υλοποίηση για τη Ruby). Υπάρχει επίσης πιρούνι Redlock-rb, που προσθέτει ένα πακέτο (πετράδι) για ευκολία διανομής και όχι μόνο γι' αυτό.
• Redlock-py (Εφαρμογή Python).
• Aioredlock (υλοποίηση για Asyncio Python).
• Redlock-php (υλοποίηση για PHP).
• PHPRedisMutex (άλλη εφαρμογή για την PHP)
• cheprasov/php-redis-lock (Βιβλιοθήκη PHP για κλειδαριές)
• Redsync (υλοποίηση για το Go).
• Ρέντισον (υλοποίηση για Java).
• Redis::DistLock (υλοποίηση για την Perl).
• Redlock-cpp (υλοποίηση για C++).
• Redlock-cs (υλοποίηση για C#/.NET).
• RedLock.net (υλοποίηση για C#/.NET). Με υποστήριξη για επεκτάσεις ασυγχρονισμού και κλειδώματος.
• ScarletLock (υλοποίηση για C# .NET με διαμορφώσιμο χώρο αποθήκευσης δεδομένων)
• Redlock4Net (υλοποίηση για C# .NET)
• κόμβος-redlock (υλοποίηση για NodeJS). Περιλαμβάνει υποστήριξη για επέκταση κλειδαριών.

Εγγυήσεις ασφάλειας και διαθεσιμότητας

Θα μοντελοποιήσουμε το σχέδιό μας με μόλις τρεις ιδιότητες που πιστεύουμε ότι παρέχουν τις ελάχιστες εγγυήσεις που απαιτούνται για την αποτελεσματική χρήση του κατανεμημένου κλειδώματος.

1. Ιδιότητα ασφαλείας: Αμοιβαίος αποκλεισμός. Ανά πάσα στιγμή, μόνο ένας πελάτης μπορεί να κρατήσει την κλειδαριά.
2. Διαθεσιμότητα Ιδιότητα Α: Χωρίς αδιέξοδα. Είναι πάντα δυνατό να αποκτήσετε τελικά ένα κλείδωμα, ακόμα κι αν ο πελάτης που κλείδωσε τον πόρο αποτύχει ή προσγειωθεί σε διαφορετικό τμήμα δίσκου.
3. Διαθεσιμότητα Ιδιότητα Β: Ανοχή σφαλμάτων. Όσο εκτελείται η πλειοψηφία των κόμβων Redis, οι πελάτες μπορούν να αποκτήσουν και να απελευθερώσουν κλειδαριές.

Γιατί η εφαρμογή που βασίζεται στην αποκατάσταση αποτυχίας δεν αρκεί σε αυτήν την περίπτωση
Για να κατανοήσουμε τι πρόκειται να βελτιώσουμε, ας αναλύσουμε την τρέχουσα κατάσταση με τις περισσότερες κατανεμημένες βιβλιοθήκες κλειδώματος που βασίζονται στο Redis.

Ο απλούστερος τρόπος για να κλειδώσετε έναν πόρο χρησιμοποιώντας το Redis είναι να δημιουργήσετε ένα κλειδί στην παρουσία. Συνήθως, δημιουργείται ένα κλειδί με περιορισμένη διάρκεια ζωής, αυτό επιτυγχάνεται χρησιμοποιώντας τη δυνατότητα λήξης που παρέχεται στο Redis, οπότε αργά ή γρήγορα αυτό το κλειδί απελευθερώνεται (ιδιότητα 2 στη λίστα μας). Όταν ο πελάτης χρειάζεται να αποδεσμεύσει τον πόρο, διαγράφει το κλειδί.

Με την πρώτη ματιά, αυτή η λύση λειτουργεί αρκετά καλά, αλλά υπάρχει ένα πρόβλημα: η αρχιτεκτονική μας δημιουργεί ένα μόνο σημείο αποτυχίας. Τι συμβαίνει εάν η παρουσία του κεντρικού υπολογιστή Redis αποτύχει; Ας προσθέσουμε έναν σκλάβο λοιπόν! Και θα το χρησιμοποιήσουμε εάν ο παρουσιαστής δεν είναι διαθέσιμος. Δυστυχώς, αυτή η επιλογή δεν είναι βιώσιμη. Κάνοντας αυτό, δεν θα μπορέσουμε να εφαρμόσουμε σωστά την ιδιότητα αμοιβαίας εξαίρεσης που χρειαζόμαστε για να διασφαλίσουμε την ασφάλεια, επειδή η αναπαραγωγή στο Redis είναι ασύγχρονη.

Προφανώς, σε ένα τέτοιο μοντέλο εμφανίζεται μια συνθήκη αγώνα:

1. Ο πελάτης Α αποκτά μια κλειδαριά στον κύριο.
2. Το master αποτυγχάνει πριν μεταφερθεί η καταχώριση κλειδιού στο slave.
3. Ο οπαδός προάγεται σε ηγέτη.
4. Ο πελάτης Β αποκτά ένα κλείδωμα στον ίδιο πόρο που ο Α έχει ήδη κλειδώσει. ΠΑΡΑΒΙΑΣΗ ΑΣΦΑΛΕΙΑΣ!

Μερικές φορές είναι απολύτως φυσιολογικό ότι σε ειδικές περιστάσεις, όπως μια αποτυχία, πολλοί πελάτες μπορούν να κρατήσουν την κλειδαριά ταυτόχρονα. Σε τέτοιες περιπτώσεις, μπορεί να εφαρμοστεί μια λύση που βασίζεται στην αναπαραγωγή. Διαφορετικά, προτείνουμε τη λύση που περιγράφεται σε αυτό το άρθρο.

Σωστή υλοποίηση με ένα μόνο παράδειγμα

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

Για να αποκτήσετε μια κλειδαριά, κάντε το εξής:

SET resource_name my_random_value NX PX 30000

Αυτή η εντολή εγκαθιστά ένα κλειδί μόνο εάν δεν υπάρχει ήδη (επιλογή NX), με περίοδο ισχύος 30000 χιλιοστά του δευτερολέπτου (επιλογή PX). Το κλειδί έχει οριστεί σε "myrandomvalue" Αυτή η τιμή πρέπει να είναι μοναδική σε όλους τους πελάτες και σε όλα τα αιτήματα κλειδώματος.
Βασικά, χρησιμοποιείται μια τυχαία τιμή για την ασφαλή απελευθέρωση της κλειδαριάς, με ένα σενάριο που λέει στον Redis: αφαιρέστε το κλειδί μόνο εάν υπάρχει και η τιμή που είναι αποθηκευμένη σε αυτό είναι ακριβώς η αναμενόμενη. Αυτό επιτυγχάνεται χρησιμοποιώντας το ακόλουθο σενάριο Lua:

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

Αυτό είναι σημαντικό για να αποτρέψετε την αφαίρεση μιας κλειδαριάς που κρατά ένας άλλος πελάτης. Για παράδειγμα, ένας πελάτης μπορεί να αποκτήσει μια κλειδαριά, στη συνέχεια να κλειδωθεί σε κάποια λειτουργία που διαρκεί περισσότερο από την πρώτη κλειδαριά (έτσι ώστε το κλειδί να έχει χρόνο να λήξει) και αργότερα να αφαιρέσει την κλειδαριά που είχε τοποθετήσει κάποιος άλλος πελάτης.
Η χρήση ενός απλού DEL δεν είναι ασφαλής επειδή ένας πελάτης μπορεί να αφαιρέσει μια κλειδαριά που κρατά ένας άλλος πελάτης. Αντίθετα, όταν χρησιμοποιείτε το παραπάνω σενάριο, κάθε κλειδαριά "υπογράφεται" με μια τυχαία συμβολοσειρά, οπότε μόνο ο πελάτης που το τοποθέτησε προηγουμένως μπορεί να το αφαιρέσει.

Ποια θα πρέπει να είναι αυτή η τυχαία συμβολοσειρά; Υποθέτω ότι θα πρέπει να είναι 20 byte από το /dev/urandom, αλλά μπορείτε να βρείτε λιγότερο ακριβούς τρόπους για να κάνετε τη συμβολοσειρά αρκετά μοναδική για τους σκοπούς σας. Για παράδειγμα, θα ήταν καλό να τοποθετήσετε το RC4 με /dev/urandom και μετά να δημιουργήσετε μια ψευδοτυχαία ροή από αυτό. Μια απλούστερη λύση περιλαμβάνει έναν συνδυασμό χρόνου unix σε ανάλυση μικροδευτερόλεπτου συν το αναγνωριστικό πελάτη. δεν είναι τόσο ασφαλές, αλλά είναι πιθανώς στο χέρι στα περισσότερα περιβάλλοντα.

Ο χρόνος που χρησιμοποιούμε ως μέτρο της διάρκειας ζωής του κλειδιού ονομάζεται "ζωή κλειδαριάς". Αυτή η τιμή είναι τόσο ο χρόνος πριν από την αυτόματη απελευθέρωση της κλειδαριάς όσο και ο χρόνος που έχει ένας πελάτης για να ολοκληρώσει μια λειτουργία προτού ένας άλλος πελάτης μπορεί με τη σειρά του να κλειδώσει αυτόν τον πόρο, χωρίς στην πραγματικότητα να παραβιάσει τις εγγυήσεις αμοιβαίας εξαίρεσης. Αυτή η εγγύηση περιορίζεται μόνο σε ένα συγκεκριμένο χρονικό διάστημα, το οποίο ξεκινά από τη στιγμή της αγοράς της κλειδαριάς.

Συζητήσαμε λοιπόν έναν καλό τρόπο απόκτησης και απελευθέρωσης κλειδαριάς. Το σύστημα (αν μιλάμε για ένα μη κατανεμημένο σύστημα που αποτελείται από ένα μόνο και πάντα διαθέσιμο παράδειγμα) είναι ασφαλές. Ας επεκτείνουμε αυτή την ιδέα σε ένα κατανεμημένο σύστημα, όπου δεν έχουμε τέτοιες εγγυήσεις.

Αλγόριθμος Redlock

Η κατανεμημένη έκδοση του αλγορίθμου προϋποθέτει ότι έχουμε N Redis masters. Αυτοί οι κόμβοι είναι εντελώς ανεξάρτητοι μεταξύ τους, επομένως δεν χρησιμοποιούμε αντιγραφή ή οποιοδήποτε άλλο σιωπηρό σύστημα συντονισμού. Έχουμε ήδη καλύψει τον τρόπο με τον οποίο μπορείτε να αποκτήσετε και να απελευθερώσετε με ασφάλεια μια κλειδαριά σε μία μόνο περίπτωση. Θεωρούμε δεδομένο ότι ο αλγόριθμος, όταν εργάζεται με ένα μόνο στιγμιότυπο, θα χρησιμοποιεί ακριβώς αυτή τη μέθοδο. Στα παραδείγματά μας θέσαμε το Ν σε 5, που είναι μια λογική τιμή. Έτσι, θα χρειαστεί να χρησιμοποιήσουμε 5 Master Redis σε διαφορετικούς υπολογιστές ή εικονικές μηχανές για να διασφαλίσουμε ότι ενεργούν σε μεγάλο βαθμό ανεξάρτητα το ένα από το άλλο.

Για να αποκτήσει ένα κλείδωμα, ο πελάτης εκτελεί τις ακόλουθες λειτουργίες:

1. Λαμβάνει την τρέχουσα ώρα σε χιλιοστά του δευτερολέπτου.
2. Προσπαθεί διαδοχικά να αποκτήσει ένα κλείδωμα σε όλες τις N περιπτώσεις, χρησιμοποιώντας το ίδιο όνομα κλειδιού και τυχαίες τιμές σε όλες τις περιπτώσεις. Στο Στάδιο 2, όταν ο πελάτης ρυθμίζει ένα κλείδωμα ανά περίπτωση, ο πελάτης χρησιμοποιεί μια καθυστέρηση για να το αποκτήσει που είναι αρκετά σύντομη σε σύγκριση με το χρόνο μετά τον οποίο το κλείδωμα απελευθερώνεται αυτόματα. Για παράδειγμα, εάν η διάρκεια αποκλεισμού είναι 10 δευτερόλεπτα, τότε η καθυστέρηση μπορεί να είναι της τάξης των ~5-50 χιλιοστών του δευτερολέπτου. Αυτό εξαλείφει την κατάσταση στην οποία ο πελάτης θα μπορούσε να παραμείνει αποκλεισμένος για μεγάλο χρονικό διάστημα προσπαθώντας να φτάσει σε έναν αποτυχημένο κόμβο Redis: εάν το στιγμιότυπο δεν είναι διαθέσιμο, τότε προσπαθούμε να συνδεθούμε με άλλο στιγμιότυπο το συντομότερο δυνατό.
3. Για να κλειδώσει, ο πελάτης υπολογίζει πόσος χρόνος έχει παρέλθει. Για να γίνει αυτό, αφαιρεί από την πραγματική τιμή χρόνου τη χρονική σήμανση που λήφθηκε στο βήμα 1. Εάν και μόνο εάν ο πελάτης ήταν σε θέση να αποκτήσει το κλείδωμα στην πλειονότητα των περιπτώσεων (τουλάχιστον 3) και τον συνολικό χρόνο που χρειάστηκε για να αποκτήσετε την κλειδαριά, μικρότερη από τη διάρκεια της κλειδαριάς, η κλειδαριά θεωρείται ότι έχει ληφθεί.
4. Εάν έχει αποκτηθεί ένα κλείδωμα, η διάρκεια κλειδώματος θεωρείται ότι είναι η αρχική διάρκεια κλειδώματος μείον τον χρόνο που έχει παρέλθει που υπολογίζεται στο βήμα 3.
5. Εάν ο πελάτης δεν καταφέρει να αποκτήσει το κλείδωμα για κάποιο λόγο (είτε δεν μπόρεσε να κλειδώσει N/2+1 παρουσίες είτε η διάρκεια του κλειδώματος ήταν αρνητική), τότε θα προσπαθήσει να ξεκλειδώσει όλες τις παρουσίες (ακόμη και εκείνες που νόμιζε ότι δεν μπορούσε να αποκλείσει ).

Είναι ο αλγόριθμος ασύγχρονος;

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

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

Το παρακάτω ενδιαφέρον άρθρο λέει περισσότερα για τέτοια συστήματα που απαιτούν συντονισμό χρονικών διαστημάτων: Μισθώσεις: ένας αποτελεσματικός μηχανισμός ανοχής σε σφάλματα για τη συνοχή της κατανεμημένης προσωρινής μνήμης αρχείων.

Προσπαθήστε ξανά στην αποτυχία

Όταν ένας πελάτης αποτυγχάνει να αποκτήσει ένα κλείδωμα, πρέπει να προσπαθήσει ξανά μετά από μια τυχαία καθυστέρηση. Αυτό γίνεται για τον αποσυγχρονισμό πολλών πελατών που προσπαθούν να αποκτήσουν ένα κλείδωμα στον ίδιο πόρο ταυτόχρονα (πράγμα που μπορεί να οδηγήσει σε μια κατάσταση "διχασμένου εγκεφάλου" στην οποία δεν υπάρχουν νικητές). Επιπλέον, όσο πιο γρήγορα ένας πελάτης προσπαθεί να αποκτήσει ένα κλείδωμα στις περισσότερες περιπτώσεις Redis, τόσο στενότερο είναι το παράθυρο στο οποίο μπορεί να εμφανιστεί μια κατάσταση διαίρεσης του εγκεφάλου (και τόσο μικρότερη είναι η ανάγκη για επαναλήψεις). Επομένως, στην ιδανική περίπτωση, ο πελάτης θα πρέπει να προσπαθήσει να στείλει εντολές SET σε N παρουσίες ταυτόχρονα χρησιμοποιώντας πολυπλεξία.

Αξίζει εδώ να τονιστεί πόσο σημαντικό είναι για τους πελάτες που αποτυγχάνουν να αποκτήσουν το μεγαλύτερο μέρος των κλειδαριών να απελευθερώσουν τις (μερικώς) αποκτημένες κλειδαριές, ώστε να μην χρειάζεται να περιμένουν να λήξει το κλειδί για να μπορέσει να αποκτήσει ξανά το κλείδωμα στον πόρο (αν και εάν προκύψει κατακερματισμός δικτύου και ο πελάτης χάσει την επαφή με τα στιγμιότυπα Redis, τότε θα πρέπει να πληρώσετε ένα πρόστιμο διαθεσιμότητας ενώ περιμένετε να λήξει το κλειδί).

Απελευθερώστε την κλειδαριά

Η απελευθέρωση μιας κλειδαριάς είναι μια απλή λειτουργία που απαιτεί απλώς ξεκλείδωμα όλων των παρουσιών, ανεξάρτητα από το αν ο πελάτης φαίνεται να έχει κλειδώσει με επιτυχία μια συγκεκριμένη παρουσία.

Θέματα ασφαλείας

Είναι ασφαλής ο αλγόριθμος; Ας προσπαθήσουμε να φανταστούμε τι συμβαίνει σε διαφορετικά σενάρια.

Αρχικά, ας υποθέσουμε ότι ο πελάτης μπόρεσε να λάβει ένα κλείδωμα στις περισσότερες περιπτώσεις. Κάθε στιγμιότυπο θα περιέχει ένα κλειδί με την ίδια διάρκεια ζωής για όλους. Ωστόσο, καθένα από αυτά τα κλειδιά εγκαταστάθηκε σε διαφορετική στιγμή, επομένως θα λήξουν σε διαφορετικές χρονικές στιγμές. Αλλά, εάν το πρώτο κλειδί εγκαταστάθηκε σε χρόνο όχι χειρότερο από το T1 (την ώρα που επιλέγουμε πριν επικοινωνήσουμε με τον πρώτο διακομιστή), και το τελευταίο κλειδί εγκαταστάθηκε σε χρόνο όχι χειρότερο από το T2 (τη στιγμή που ελήφθη η απάντηση από τον τελευταίο διακομιστή), τότε είμαστε βέβαιοι ότι το πρώτο κλειδί στο σύνολο που λήγει θα επιβιώσει τουλάχιστον MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Όλα τα άλλα κλειδιά θα λήξουν αργότερα, επομένως μπορούμε να είμαστε σίγουροι ότι όλα τα κλειδιά θα ισχύουν ταυτόχρονα τουλάχιστον αυτή τη φορά.

Κατά τη διάρκεια του χρόνου που τα περισσότερα κλειδιά παραμένουν έγκυρα, άλλος πελάτης δεν θα μπορεί να αποκτήσει το κλείδωμα, καθώς οι λειτουργίες N/2+1 SET NX δεν μπορούν να επιτύχουν εάν υπάρχουν ήδη κλειδιά N/2+1. Επομένως, από τη στιγμή που έχει αποκτηθεί ένα λουκέτο, είναι αδύνατο να το αποκτήσετε ξανά την ίδια στιγμή (αυτό θα παραβίαζε την ιδιότητα αμοιβαίου αποκλεισμού).
Ωστόσο, θέλουμε να διασφαλίσουμε ότι πολλοί πελάτες που προσπαθούν να αποκτήσουν μια κλειδαριά ταυτόχρονα δεν μπορούν να πετύχουν ταυτόχρονα.

Εάν ο πελάτης έχει κλειδώσει τις περισσότερες παρουσίες για περίπου ή περισσότερο από τη μέγιστη διάρκεια κλειδώματος, θα θεωρήσει το κλείδωμα άκυρο και θα ξεκλειδώσει τις παρουσίες. Επομένως, πρέπει να λάβουμε υπόψη μόνο την περίπτωση κατά την οποία ο πελάτης κατάφερε να αποκλείσει την πλειονότητα των περιπτώσεων σε χρόνο μικρότερο από την ημερομηνία λήξης. Εν προκειμένω, ως προς το παραπάνω επιχείρημα, κατά το χρόνο MIN_VALIDITY κανένας πελάτης δεν θα πρέπει να μπορεί να αποκτήσει ξανά την κλειδαριά. Επομένως, πολλοί πελάτες θα μπορούν να κλειδώνουν N/2+1 παρουσίες ταυτόχρονα (το οποίο τελειώνει στο τέλος του σταδίου 2) μόνο όταν ο χρόνος κλειδώματος της πλειοψηφίας ήταν μεγαλύτερος από τον χρόνο TTL, γεγονός που καθιστά το κλείδωμα άκυρο.

Μπορείτε να παράσχετε μια επίσημη απόδειξη ασφάλειας, να υποδείξετε υπάρχοντες παρόμοιους αλγόριθμους ή να βρείτε ένα σφάλμα στα παραπάνω;

Θέματα προσβασιμότητας

Η διαθεσιμότητα του συστήματος εξαρτάται από τρία κύρια χαρακτηριστικά:

1. Αυτόματη απελευθέρωση κλειδαριών (καθώς τα κλειδιά λήγουν): Τα κλειδιά θα είναι τελικά ξανά διαθέσιμα για χρήση για κλειδαριές.
2. Το γεγονός ότι οι πελάτες συνήθως βοηθούν ο ένας τον άλλον αφαιρώντας κλειδαριές όταν δεν έχει αποκτηθεί η επιθυμητή κλειδαριά ή έχει αποκτηθεί και η εργασία έχει ολοκληρωθεί. οπότε είναι πιθανό να μην χρειαστεί να περιμένουμε να λήξουν τα κλειδιά για να αποκτήσουμε ξανά την κλειδαριά.
3. Το γεγονός ότι όταν ένας πελάτης χρειάζεται να προσπαθήσει ξανά για να αποκτήσει μια κλειδαριά, περιμένει για ένα συγκριτικά μεγαλύτερο χρονικό διάστημα από το διάστημα που απαιτείται για την απόκτηση των περισσότερων κλειδαριών. Αυτό μειώνει την πιθανότητα να προκύψει μια κατάσταση διχασμού κατά τον ανταγωνισμό για πόρους.

Ωστόσο, υπάρχει μια ποινή διαθεσιμότητας ίση με το TTL των τμημάτων δικτύου, επομένως εάν υπάρχουν συνεχόμενα τμήματα, η ποινή μπορεί να είναι αόριστη. Αυτό συμβαίνει κάθε φορά που ένας πελάτης αποκτά μια κλειδαριά και στη συνέχεια σχίζεται σε άλλο τμήμα προτού μπορέσει να την απελευθερώσει.

Κατ' αρχήν, με δεδομένα άπειρα συνεχόμενα τμήματα δικτύου, ένα σύστημα μπορεί να παραμείνει μη διαθέσιμο για άπειρο χρονικό διάστημα.

Απόδοση, failover και fsync

Πολλοί άνθρωποι χρησιμοποιούν το Redis επειδή χρειάζονται υψηλή απόδοση διακομιστή κλειδώματος όσον αφορά τον λανθάνοντα χρόνο που απαιτείται για την απόκτηση και την απελευθέρωση κλειδαριών και τον αριθμό των αποκτήσεων/εκδόσεων που μπορούν να ολοκληρωθούν ανά δευτερόλεπτο. Για να ικανοποιηθεί αυτή η απαίτηση, υπάρχει μια στρατηγική επικοινωνίας με διακομιστές N Redis για μείωση της καθυστέρησης. Αυτή είναι μια στρατηγική πολυπλεξίας (ή "πολυπλεξία του φτωχού", όπου η πρίζα τίθεται σε λειτουργία μη αποκλεισμού, στέλνει όλες τις εντολές και διαβάζει τις εντολές αργότερα, υποθέτοντας ότι ο χρόνος μετ' επιστροφής μεταξύ του πελάτη και κάθε παρουσίας είναι παρόμοιος) .

Ωστόσο, πρέπει επίσης να λάβουμε υπόψη τη σημασία που σχετίζεται με τη μακροπρόθεσμη αποθήκευση δεδομένων εάν προσπαθούμε να δημιουργήσουμε ένα μοντέλο με αξιόπιστη ανάκτηση από βλάβες.

Βασικά, για να διευκρινίσουμε το ζήτημα, ας υποθέσουμε ότι ρυθμίζουμε το Redis χωρίς καθόλου μακροπρόθεσμη αποθήκευση δεδομένων. Ο πελάτης καταφέρνει να μπλοκάρει 3 από τις 5 περιπτώσεις. Μία από τις περιπτώσεις που κατάφερε να αποκλείσει ο πελάτης επανεκκινείται και αυτή τη στιγμή υπάρχουν ξανά 3 περιπτώσεις για τον ίδιο πόρο, τους οποίους μπορούμε να αποκλείσουμε και ένας άλλος πελάτης μπορεί, με τη σειρά του, να αποκλείσει την επανεκκίνηση, παραβιάζοντας την ιδιότητα ασφαλείας που προϋποθέτει την αποκλειστικότητα των κλειδαριών.

Εάν ενεργοποιήσετε τα προηγούμενα δεδομένα (AOF), η κατάσταση θα βελτιωθεί ελαφρώς. Για παράδειγμα, μπορείτε να προωθήσετε έναν διακομιστή στέλνοντας την εντολή SHUTDOWN και επανεκκινώντας τον. Δεδομένου ότι οι λειτουργίες λήξης στο Redis υλοποιούνται σημασιολογικά με τέτοιο τρόπο ώστε ο χρόνος να συνεχίζει να ρέει ακόμα και όταν ο διακομιστής είναι απενεργοποιημένος, όλες οι απαιτήσεις μας είναι καλές. Αυτό είναι φυσιολογικό εφόσον εξασφαλίζεται κανονική διακοπή λειτουργίας. Τι να κάνετε σε περίπτωση διακοπής ρεύματος; Εάν το Redis έχει ρυθμιστεί από προεπιλογή, με το fsync να συγχρονίζεται στο δίσκο κάθε δευτερόλεπτο, τότε είναι πιθανό μετά από επανεκκίνηση να μην έχουμε το κλειδί μας. Θεωρητικά, εάν θέλουμε να εγγυηθούμε την ασφάλεια κλειδώματος κατά τη διάρκεια οποιασδήποτε επανεκκίνησης, θα πρέπει να το ενεργοποιήσουμε fsync=always στις ρυθμίσεις για μακροπρόθεσμη αποθήκευση δεδομένων. Αυτό θα σκοτώσει εντελώς την απόδοση, μέχρι το επίπεδο των συστημάτων CP που χρησιμοποιούνται παραδοσιακά για την ασφαλή εφαρμογή κατανεμημένων κλειδαριών.

Όμως η κατάσταση είναι καλύτερη από ό,τι φαίνεται με την πρώτη ματιά. Κατ' αρχήν, η ασφάλεια του αλγορίθμου διατηρείται επειδή όταν το στιγμιότυπο επανεκκινείται μετά από αποτυχία, δεν συμμετέχει πλέον σε κανένα κλείδωμα που είναι ενεργό αυτήν τη στιγμή.

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

Χρησιμοποιώντας καθυστερημένες επανεκκινήσεις, είναι καταρχήν δυνατό να επιτευχθεί ασφάλεια ακόμη και αν δεν υπάρχει μακροπρόθεσμη παραμονή στο Redis. Σημειώστε, ωστόσο, ότι αυτό μπορεί να οδηγήσει σε πρόστιμο για παραβίαση προσβασιμότητας. Για παράδειγμα, εάν η πλειονότητα των περιπτώσεων αποτύχει, το σύστημα δεν θα είναι παγκοσμίως διαθέσιμο για το TTL (και κανένας πόρος δεν μπορεί να αποκλειστεί κατά τη διάρκεια αυτής της περιόδου).

Αυξάνουμε τη διαθεσιμότητα του αλγορίθμου: επεκτείνουμε το μπλοκάρισμα

Εάν η εργασία που εκτελείται από τους πελάτες αποτελείται από μικρά βήματα, είναι δυνατό να μειωθεί η προεπιλεγμένη διάρκεια κλειδώματος και να εφαρμοστεί ένας μηχανισμός για την επέκταση των κλειδαριών. Κατ 'αρχήν, εάν ο πελάτης είναι απασχολημένος με υπολογιστές και η τιμή λήξης κλειδώματος είναι επικίνδυνα χαμηλή, μπορείτε να στείλετε ένα σενάριο Lua σε όλες τις περιπτώσεις που επεκτείνει το TTL του κλειδιού, εάν το κλειδί εξακολουθεί να υπάρχει και η τιμή του εξακολουθεί να είναι μια τυχαία τιμή που λαμβάνεται όταν αποκτήθηκε η κλειδαριά.

Ένας πελάτης θα πρέπει να εξετάσει το ενδεχόμενο επανάκτησης ενός κλειδώματος μόνο εάν έχει καταφέρει να κλειδώσει την πλειονότητα των περιπτώσεων εντός της περιόδου ισχύος.

Είναι αλήθεια ότι τεχνικά ο αλγόριθμος δεν αλλάζει, επομένως ο μέγιστος αριθμός επαναλαμβανόμενων προσπαθειών απόκτησης κλειδαριών πρέπει να είναι περιορισμένος, διαφορετικά θα παραβιαστούν οι ιδιότητες προσβασιμότητας.

Πηγή: www.habr.com