Έτσι μοιάζει ο πλεονασμός
Οι κωδικοί πλεονασμού* χρησιμοποιούνται ευρέως σε συστήματα υπολογιστών για την αύξηση της αξιοπιστίας της αποθήκευσης δεδομένων. Στο Yandex χρησιμοποιούνται σε πολλά έργα. Για παράδειγμα, η χρήση κωδικών πλεονασμού αντί της αναπαραγωγής στον εσωτερικό χώρο αποθήκευσης αντικειμένων μας εξοικονομεί εκατομμύρια χωρίς να θυσιάζεται η αξιοπιστία. Όμως, παρά την ευρεία χρήση τους, οι σαφείς περιγραφές του τρόπου λειτουργίας των κωδικών πλεονασμού είναι πολύ σπάνιες. Όσοι θέλουν να καταλάβουν έρχονται αντιμέτωποι με περίπου τα εξής (από ):
Το όνομά μου είναι Vadim, στο Yandex αναπτύσσω εσωτερική αποθήκευση αντικειμένων MDS. Σε αυτό το άρθρο, θα περιγράψω με απλά λόγια τις θεωρητικές βάσεις των κωδικών πλεονασμού (κώδικες Reed-Solomon και LRC). Θα σας πω πώς λειτουργεί, χωρίς πολύπλοκα μαθηματικά και σπάνιους όρους. Στο τέλος θα δώσω παραδείγματα χρήσης κωδικών πλεονασμού στο Yandex.
Δεν θα εξετάσω λεπτομερώς ορισμένες μαθηματικές λεπτομέρειες, αλλά θα παράσχω συνδέσμους για όσους θέλουν να βουτήξουν πιο βαθιά. Θα σημειώσω επίσης ότι ορισμένοι μαθηματικοί ορισμοί μπορεί να μην είναι αυστηροί, αφού το άρθρο δεν προορίζεται για μαθηματικούς, αλλά για μηχανικούς που θέλουν να κατανοήσουν την ουσία του ζητήματος.
* Στην αγγλόφωνη βιβλιογραφία, οι κωδικοί πλεονασμού ονομάζονται συχνά κωδικοί διαγραφής.
1. Η ουσία των κωδικών πλεονασμού
Η ουσία όλων των κωδικών πλεονασμού είναι εξαιρετικά απλή: αποθήκευση (ή μετάδοση) δεδομένων έτσι ώστε να μην χάνονται όταν συμβαίνουν σφάλματα (αστοχίες δίσκου, σφάλματα μεταφοράς δεδομένων κ.λπ.).
Στους περισσότερους* κώδικες πλεονασμού, τα δεδομένα χωρίζονται σε n μπλοκ δεδομένων, για τα οποία μετρώνται m μπλοκ κωδικών πλεονασμού, με αποτέλεσμα συνολικά n + m μπλοκ. Οι κωδικοί πλεονασμού κατασκευάζονται με τέτοιο τρόπο ώστε n μπλοκ δεδομένων να μπορούν να ανακτηθούν χρησιμοποιώντας μόνο ένα τμήμα n + m μπλοκ. Στη συνέχεια, θα εξετάσουμε μόνο τους κωδικούς πλεονασμού μπλοκ, δηλαδή αυτούς στους οποίους τα δεδομένα χωρίζονται σε μπλοκ.
Για να ανακτήσετε και τα n μπλοκ δεδομένων, πρέπει να έχετε τουλάχιστον n από n + m μπλοκ, καθώς δεν μπορείτε να λάβετε n μπλοκ έχοντας μόνο n-1 μπλοκ (σε αυτήν την περίπτωση, θα πρέπει να πάρετε 1 μπλοκ "από λεπτό αέρας"). Είναι αρκετά n τυχαία μπλοκ n + m μπλοκ για την ανάκτηση όλων των δεδομένων; Αυτό εξαρτάται από τον τύπο των κωδικών πλεονασμού, για παράδειγμα, οι κωδικοί Reed-Solomon σάς επιτρέπουν να ανακτήσετε όλα τα δεδομένα χρησιμοποιώντας αυθαίρετα n μπλοκ, αλλά οι κωδικοί πλεονασμού LRC δεν το κάνουν πάντα.
Αποθήκευση δεδομένων
Στα συστήματα αποθήκευσης δεδομένων, κατά κανόνα, καθένα από τα μπλοκ δεδομένων και τα μπλοκ κώδικα πλεονασμού εγγράφεται σε ξεχωριστό δίσκο. Στη συνέχεια, εάν ένας αυθαίρετος δίσκος αποτύχει, τα αρχικά δεδομένα μπορούν να επαναφερθούν και να διαβαστούν. Τα δεδομένα μπορούν να ανακτηθούν ακόμη και αν αποτύχουν πολλοί δίσκοι ταυτόχρονα.
Μεταφορά δεδομένων
Οι κωδικοί πλεονασμού μπορούν να χρησιμοποιηθούν για την αξιόπιστη μετάδοση δεδομένων μέσω ενός αναξιόπιστου δικτύου. Τα μεταδιδόμενα δεδομένα χωρίζονται σε μπλοκ και υπολογίζονται οι κωδικοί πλεονασμού για αυτά. Τόσο τα μπλοκ δεδομένων όσο και τα μπλοκ κώδικα πλεονασμού μεταδίδονται μέσω του δικτύου. Εάν προκύψουν σφάλματα σε αυθαίρετα μπλοκ (μέχρι έναν ορισμένο αριθμό μπλοκ), τα δεδομένα μπορούν να μεταδοθούν μέσω του δικτύου χωρίς σφάλματα. Οι κώδικες Reed-Solomon, για παράδειγμα, χρησιμοποιούνται για τη μετάδοση δεδομένων μέσω οπτικών γραμμών επικοινωνίας και σε δορυφορικές επικοινωνίες.
* Υπάρχουν επίσης κωδικοί πλεονασμού στους οποίους τα δεδομένα δεν χωρίζονται σε μπλοκ, όπως κωδικοί Hamming και κωδικοί CRC, που χρησιμοποιούνται ευρέως για μετάδοση δεδομένων σε δίκτυα Ethernet. Αυτοί είναι κωδικοί για κωδικοποίηση διόρθωσης σφαλμάτων, έχουν σχεδιαστεί για να ανιχνεύουν σφάλματα και όχι να τα διορθώνουν (ο κώδικας Hamming επιτρέπει επίσης μερική διόρθωση σφαλμάτων).
2. Κώδικες Reed-Solomon
Οι κωδικοί Reed-Solomon είναι ένας από τους πιο ευρέως χρησιμοποιούμενους κωδικούς πλεονασμού, που εφευρέθηκε στη δεκαετία του 1960 και χρησιμοποιήθηκε για πρώτη φορά ευρέως τη δεκαετία του 1980 για τη μαζική παραγωγή δίσκων συμπαγούς δίσκου.
Υπάρχουν δύο βασικά ερωτήματα για την κατανόηση των κωδίκων Reed-Solomon: 1) πώς να δημιουργήσετε μπλοκ κωδικών πλεονασμού. 2) πώς να ανακτήσετε δεδομένα χρησιμοποιώντας μπλοκ κώδικα πλεονασμού. Ας βρούμε απαντήσεις σε αυτά.
Για απλότητα, θα υποθέσουμε περαιτέρω ότι n=6 και m=4. Άλλα σχήματα εξετάζονται κατ' αναλογία.
Πώς να δημιουργήσετε μπλοκ κώδικα πλεονασμού
Κάθε μπλοκ κωδικών πλεονασμού μετράται ανεξάρτητα από τα άλλα. Και τα n μπλοκ δεδομένων χρησιμοποιούνται για την καταμέτρηση κάθε μπλοκ. Στο παρακάτω διάγραμμα, τα X1-X6 είναι μπλοκ δεδομένων, τα P1-P4 είναι μπλοκ κωδικών πλεονασμού.
Όλα τα μπλοκ δεδομένων πρέπει να έχουν το ίδιο μέγεθος και μπορούν να χρησιμοποιηθούν μηδενικά bit για ευθυγράμμιση. Τα μπλοκ κώδικα πλεονασμού που θα προκύψουν θα έχουν το ίδιο μέγεθος με τα μπλοκ δεδομένων. Όλα τα μπλοκ δεδομένων χωρίζονται σε λέξεις (για παράδειγμα, 16 bit). Ας υποθέσουμε ότι χωρίζουμε τα μπλοκ δεδομένων σε k λέξεις. Τότε όλα τα μπλοκ κωδικών πλεονασμού θα χωριστούν επίσης σε k λέξεις.
Για την καταμέτρηση της i-ης λέξης κάθε μπλοκ πλεονασμού, θα χρησιμοποιηθούν οι i-ες λέξεις όλων των μπλοκ δεδομένων. Θα υπολογιστούν σύμφωνα με τον ακόλουθο τύπο:
Εδώ οι τιμές x είναι οι λέξεις των μπλοκ δεδομένων, το p είναι οι λέξεις των μπλοκ κωδικών πλεονασμού, όλα τα άλφα, βήτα, γάμμα και δέλτα είναι ειδικά επιλεγμένοι αριθμοί που είναι ίδιοι για όλα τα i. Πρέπει να πούμε αμέσως ότι όλες αυτές οι τιμές δεν είναι συνηθισμένοι αριθμοί, αλλά στοιχεία του πεδίου Galois· οι πράξεις +, -, *, / δεν είναι πράξεις οικείες σε όλους μας, αλλά ειδικές πράξεις που εισάγονται σε στοιχεία του Galois πεδίο.
Γιατί χρειάζονται τα πεδία Galois;
Φαίνεται ότι όλα είναι απλά: χωρίζουμε τα δεδομένα σε μπλοκ, τα μπλοκ σε λέξεις, χρησιμοποιώντας τις λέξεις των μπλοκ δεδομένων μετράμε τις λέξεις των μπλοκ κωδικών πλεονασμού - παίρνουμε μπλοκ κώδικα πλεονασμού. Γενικά έτσι λειτουργεί, αλλά ο διάβολος είναι στις λεπτομέρειες:
- Όπως αναφέρθηκε παραπάνω, το μέγεθος της λέξης είναι σταθερό, στο παράδειγμά μας 16 bit. Οι παραπάνω τύποι για τους κώδικες Reed-Solomon είναι τέτοιοι που όταν χρησιμοποιούνται συνηθισμένοι ακέραιοι, το αποτέλεσμα του υπολογισμού του p μπορεί να μην είναι αναπαραστάσιμο χρησιμοποιώντας μια λέξη έγκυρου μεγέθους.
- Κατά την ανάκτηση δεδομένων, οι παραπάνω τύποι θα θεωρηθούν ως ένα σύστημα εξισώσεων που πρέπει να λυθούν προκειμένου να ανακτηθούν τα δεδομένα. Κατά τη διαδικασία επίλυσης, μπορεί να είναι απαραίτητο να διαιρεθούν ακέραιοι αριθμοί μεταξύ τους, με αποτέλεσμα έναν πραγματικό αριθμό που δεν μπορεί να αναπαρασταθεί με ακρίβεια στη μνήμη του υπολογιστή.
Αυτά τα προβλήματα εμποδίζουν τη χρήση ακεραίων για κώδικες Reed-Solomon. Η λύση στο πρόβλημα είναι πρωτότυπη, μπορεί να περιγραφεί ως εξής: ας βρούμε ειδικούς αριθμούς που μπορούν να αναπαρασταθούν χρησιμοποιώντας λέξεις του απαιτούμενου μήκους (για παράδειγμα, 16 bit) και το αποτέλεσμα της εκτέλεσης όλων των πράξεων στις οποίες (προσθήκη , αφαίρεση, πολλαπλασιασμός, διαίρεση) θα παρουσιαστούν επίσης στη μνήμη του υπολογιστή χρησιμοποιώντας λέξεις του απαιτούμενου μήκους.
Τέτοιοι «ειδικοί» αριθμοί έχουν μελετηθεί από τα μαθηματικά εδώ και πολύ καιρό· ονομάζονται πεδία. Ένα πεδίο είναι ένα σύνολο στοιχείων με πράξεις πρόσθεσης, αφαίρεσης, πολλαπλασιασμού και διαίρεσης που ορίζονται γι' αυτά.
Τα πεδία Galois* είναι πεδία για τα οποία υπάρχει ένα μοναδικό αποτέλεσμα κάθε πράξης (+, -, *, /) για οποιαδήποτε δύο στοιχεία του πεδίου. Τα πεδία Galois μπορούν να κατασκευαστούν για αριθμούς που είναι δυνάμεις 2: 2, 4, 8, 16 κ.λπ. (στην πραγματικότητα οι δυνάμεις οποιουδήποτε πρώτου αριθμού p, αλλά στην πράξη μας ενδιαφέρουν μόνο οι δυνάμεις του 2). Για παράδειγμα, για λέξεις 16-bit, αυτό είναι ένα πεδίο που περιέχει 65 στοιχεία, για κάθε ζεύγος των οποίων μπορείτε να βρείτε το αποτέλεσμα οποιασδήποτε πράξης (+, -, *, /). Οι τιμές των x, p, άλφα, βήτα, γάμμα, δέλτα από τις παραπάνω εξισώσεις θα θεωρηθούν στοιχεία του πεδίου Galois για υπολογισμούς.
Έτσι, έχουμε ένα σύστημα εξισώσεων με το οποίο μπορούμε να κατασκευάσουμε μπλοκ κωδικών πλεονασμού γράφοντας ένα κατάλληλο πρόγραμμα υπολογιστή. Χρησιμοποιώντας το ίδιο σύστημα εξισώσεων, μπορείτε να πραγματοποιήσετε ανάκτηση δεδομένων.
* Αυτός δεν είναι αυστηρός ορισμός, αλλά μάλλον περιγραφή.
Πώς να ανακτήσετε δεδομένα
Απαιτείται αποκατάσταση όταν λείπουν μερικά από τα n + m μπλοκ. Αυτά μπορεί να είναι τόσο μπλοκ δεδομένων όσο και μπλοκ κώδικα πλεονασμού. Η απουσία μπλοκ δεδομένων και/ή μπλοκ κώδικα πλεονασμού θα σημαίνει ότι οι αντίστοιχες μεταβλητές x και/ή p είναι άγνωστες στις παραπάνω εξισώσεις.
Οι εξισώσεις για τους κώδικες Reed-Solomon μπορούν να θεωρηθούν ως ένα σύστημα εξισώσεων στο οποίο όλες οι τιμές άλφα, βήτα, γάμμα, δέλτα είναι σταθερές, όλα τα x και p που αντιστοιχούν στα διαθέσιμα μπλοκ είναι γνωστές μεταβλητές και τα υπόλοιπα x και p είναι άγνωστοι.
Για παράδειγμα, αφήστε τα μπλοκ δεδομένων 1, 2, 3 και το μπλοκ κωδικών πλεονασμού 2 να μην είναι διαθέσιμα, τότε για την i-η ομάδα λέξεων θα υπάρχει το ακόλουθο σύστημα εξισώσεων (τα άγνωστα σημειώνονται με κόκκινο χρώμα):
Έχουμε ένα σύστημα 4 εξισώσεων με 4 αγνώστους, που σημαίνει ότι μπορούμε να το λύσουμε και να επαναφέρουμε τα δεδομένα!
Από αυτό το σύστημα εξισώσεων προκύπτει μια σειρά από συμπεράσματα σχετικά με την ανάκτηση δεδομένων για κώδικες Reed-Solomon (n μπλοκ δεδομένων, m μπλοκ κωδικών πλεονασμού):
- Τα δεδομένα μπορούν να ανακτηθούν εάν χαθούν m μπλοκ ή λιγότερα. Εάν χαθούν m+1 ή περισσότερα μπλοκ, τα δεδομένα δεν μπορούν να αποκατασταθούν: είναι αδύνατο να λυθεί ένα σύστημα εξισώσεων m με m + 1 αγνώστους.
- Για να ανακτήσετε έστω και ένα μπλοκ δεδομένων, πρέπει να χρησιμοποιήσετε οποιοδήποτε n από τα υπόλοιπα μπλοκ και μπορείτε να χρησιμοποιήσετε οποιονδήποτε από τους κωδικούς πλεονασμού.
Τι άλλο πρέπει να γνωρίζετε
Στην παραπάνω περιγραφή, αποφεύγω μια σειρά από σημαντικά ζητήματα που απαιτούν μια βαθύτερη κατάδυση στα μαθηματικά για να ληφθούν υπόψη. Συγκεκριμένα, δεν λέω τίποτα για τα εξής:
- Το σύστημα εξισώσεων για τους κώδικες Reed-Solomon πρέπει να έχει μια (μοναδική) λύση για οποιονδήποτε συνδυασμό αγνώστων (όχι περισσότερο από m αγνώστους). Με βάση αυτή την απαίτηση, επιλέγονται οι τιμές άλφα, βήτα, γάμμα και δέλτα.
- Ένα σύστημα εξισώσεων πρέπει να μπορεί να κατασκευαστεί αυτόματα (ανάλογα με το ποια μπλοκ δεν είναι διαθέσιμα) και να λυθεί.
- Πρέπει να δημιουργήσουμε ένα πεδίο Galois: για ένα δεδομένο μέγεθος λέξης, να μπορούμε να βρούμε το αποτέλεσμα οποιασδήποτε πράξης (+, -, *, /) για οποιαδήποτε δύο στοιχεία.
Στο τέλος του άρθρου υπάρχουν αναφορές στη βιβλιογραφία για αυτά τα σημαντικά θέματα.
Επιλογή n και m
Πώς να επιλέξετε n και m στην πράξη; Στην πράξη, στα συστήματα αποθήκευσης δεδομένων, οι κωδικοί πλεονασμού χρησιμοποιούνται για εξοικονόμηση χώρου, επομένως το m επιλέγεται πάντα μικρότερο από το n. Οι συγκεκριμένες τιμές τους εξαρτώνται από διάφορους παράγοντες, όπως:
- Αξιοπιστία αποθήκευσης δεδομένων. Όσο μεγαλύτερο είναι το m, τόσο μεγαλύτερος είναι ο αριθμός των αστοχιών του δίσκου που μπορούν να επιβιώσουν, δηλαδή τόσο μεγαλύτερη είναι η αξιοπιστία.
- Περιττή αποθήκευση. Όσο υψηλότερη είναι η αναλογία m/n, τόσο υψηλότερος θα είναι ο πλεονασμός αποθήκευσης και τόσο πιο ακριβό θα είναι το σύστημα.
- Χρόνος επεξεργασίας αιτήματος. Όσο μεγαλύτερο είναι το άθροισμα n + m, τόσο μεγαλύτερος θα είναι ο χρόνος απόκρισης στα αιτήματα. Εφόσον η ανάγνωση δεδομένων (κατά την ανάκτηση) απαιτεί ανάγνωση n μπλοκ που είναι αποθηκευμένα σε n διαφορετικούς δίσκους, ο χρόνος ανάγνωσης θα καθοριστεί από τον πιο αργό δίσκο.
Επιπλέον, η αποθήκευση δεδομένων σε πολλά DC επιβάλλει πρόσθετους περιορισμούς στην επιλογή n και m: εάν 1 DC είναι απενεργοποιημένο, τα δεδομένα πρέπει να είναι ακόμα διαθέσιμα για ανάγνωση. Για παράδειγμα, κατά την αποθήκευση δεδομένων σε 3 DC, πρέπει να πληρούται η ακόλουθη συνθήκη: m >= n/2, διαφορετικά μπορεί να υπάρξει μια κατάσταση όπου τα δεδομένα δεν είναι διαθέσιμα για ανάγνωση όταν είναι απενεργοποιημένο 1 DC.
3. LRC - Τοπικοί Κώδικες Ανασυγκρότησης
Για να ανακτήσετε δεδομένα χρησιμοποιώντας κωδικούς Reed-Solomon, πρέπει να χρησιμοποιήσετε n αυθαίρετα μπλοκ δεδομένων. Αυτό είναι ένα πολύ σημαντικό μειονέκτημα για τα κατανεμημένα συστήματα αποθήκευσης δεδομένων, επειδή για να επαναφέρετε δεδομένα σε έναν σπασμένο δίσκο, θα πρέπει να διαβάσετε δεδομένα από τα περισσότερα από τα άλλα, δημιουργώντας ένα μεγάλο πρόσθετο φορτίο στους δίσκους και στο δίκτυο.
Τα πιο συνηθισμένα σφάλματα είναι η μη προσβασιμότητα ενός μπλοκ δεδομένων λόγω αστοχίας ή υπερφόρτωσης ενός δίσκου. Είναι δυνατόν να μειωθεί με κάποιο τρόπο το υπερβολικό φορτίο για την ανάκτηση δεδομένων σε αυτήν την (πιο συνηθισμένη) περίπτωση; Αποδεικνύεται ότι μπορείτε: υπάρχουν κωδικοί πλεονασμού LRC ειδικά για αυτόν τον σκοπό.
Το LRC (Local Reconstruction Codes) είναι κωδικοί πλεονασμού που εφευρέθηκαν από τη Microsoft για χρήση στο Windows Azure Storage. Η ιδέα του LRC είναι όσο το δυνατόν πιο απλή: χωρίστε όλα τα μπλοκ δεδομένων σε δύο (ή περισσότερες) ομάδες και διαβάστε μέρος των μπλοκ κωδικών πλεονασμού για κάθε ομάδα ξεχωριστά. Στη συνέχεια, ορισμένα μπλοκ κώδικα πλεονασμού θα μετρηθούν χρησιμοποιώντας όλα τα μπλοκ δεδομένων (στο LRC ονομάζονται καθολικοί κώδικες πλεονασμού) και μερικά - χρησιμοποιώντας μία από τις δύο ομάδες μπλοκ δεδομένων (ονομάζονται τοπικοί κώδικες πλεονασμού).
Το LRC συμβολίζεται με τρεις αριθμούς: nrl, όπου n είναι ο αριθμός των μπλοκ δεδομένων, r είναι ο αριθμός των παγκόσμιων μπλοκ κώδικα πλεονασμού, l είναι ο αριθμός των μπλοκ τοπικών κωδικών πλεονασμού. Για να διαβάσετε δεδομένα όταν ένα μπλοκ δεδομένων δεν είναι διαθέσιμο, πρέπει να διαβάσετε μόνο μπλοκ n/l - αυτό είναι l φορές λιγότερο από ό,τι στους κωδικούς Reed-Solomon.
Για παράδειγμα, εξετάστε το σχήμα LRC 6-2-2. X1–X6 — 6 μπλοκ δεδομένων, P1, P2 — 2 μπλοκ καθολικού πλεονασμού, P3, P4 — 2 μπλοκ τοπικού πλεονασμού.
Τα μπλοκ κωδικών πλεονασμού P1, P2 μετρώνται χρησιμοποιώντας όλα τα μπλοκ δεδομένων. Μπλοκ κωδικού πλεονασμού P3 - χρήση μπλοκ δεδομένων X1-X3, μπλοκ κωδικού πλεονασμού P4 - χρήση μπλοκ δεδομένων X4-X6.
Τα υπόλοιπα γίνονται σε LRC κατ' αναλογία με τους κώδικες Reed-Solomon. Οι εξισώσεις για την καταμέτρηση των λέξεων των μπλοκ κωδικών πλεονασμού θα είναι:
Για να επιλέξετε τους αριθμούς άλφα, βήτα, γάμμα, δέλτα, πρέπει να πληρούνται ορισμένες προϋποθέσεις για να διασφαλιστεί η δυνατότητα ανάκτησης δεδομένων (δηλαδή επίλυσης του συστήματος εξισώσεων). Μπορείτε να διαβάσετε περισσότερα για αυτούς στο .
Επίσης στην πράξη, η λειτουργία XOR χρησιμοποιείται για τον υπολογισμό των τοπικών κωδικών πλεονασμού P3, P4.
Από το σύστημα εξισώσεων για το LRC προκύπτουν ορισμένα συμπεράσματα:
- Για να ανακτήσετε οποιοδήποτε 1 μπλοκ δεδομένων, αρκεί να διαβάσετε μπλοκ n/l (n/2 στο παράδειγμά μας).
- Εάν τα μπλοκ r + l δεν είναι διαθέσιμα και όλα τα μπλοκ περιλαμβάνονται σε μία ομάδα, τότε δεν είναι δυνατή η επαναφορά των δεδομένων. Αυτό είναι εύκολο να εξηγηθεί με ένα παράδειγμα. Ας μην είναι διαθέσιμα τα μπλοκ X1–X3 και P3: αυτά είναι μπλοκ r + l από την ίδια ομάδα, 4 στην περίπτωσή μας. Τότε έχουμε ένα σύστημα 3 εξισώσεων με 4 αγνώστους που δεν μπορούν να λυθούν.
- Σε όλες τις άλλες περιπτώσεις μη διαθεσιμότητας μπλοκ r + l (όταν τουλάχιστον ένα μπλοκ είναι διαθέσιμο από κάθε ομάδα), τα δεδομένα στο LRC μπορούν να αποκατασταθούν.
Έτσι, το LRC ξεπερνά τους κωδικούς Reed-Solomon στην ανάκτηση δεδομένων μετά από μεμονωμένα σφάλματα. Στους κωδικούς Reed-Solomon, για να ανακτήσετε έστω και ένα μπλοκ δεδομένων, πρέπει να χρησιμοποιήσετε n μπλοκ και στο LRC, για να ανακτήσετε ένα μπλοκ δεδομένων, αρκεί να χρησιμοποιήσετε n/l μπλοκ (n/2 στο παράδειγμά μας). Από την άλλη πλευρά, το LRC είναι κατώτερο από τους κωδικούς Reed-Solomon όσον αφορά τον μέγιστο αριθμό επιτρεπόμενων σφαλμάτων. Στα παραπάνω παραδείγματα, οι κωδικοί Reed-Solomon μπορούν να ανακτήσουν δεδομένα για οποιαδήποτε 4 σφάλματα και για το LRC υπάρχουν 2 συνδυασμοί των 4 σφαλμάτων όταν τα δεδομένα δεν μπορούν να ανακτηθούν.
Αυτό που είναι πιο σημαντικό εξαρτάται από τη συγκεκριμένη κατάσταση, αλλά συχνά η εξοικονόμηση υπερβολικού φορτίου που παρέχει η LRC υπερβαίνει την ελαφρώς λιγότερο αξιόπιστη αποθήκευση.
4. Άλλοι κωδικοί πλεονασμού
Εκτός από τους κωδικούς Reed-Solomon και LRC, υπάρχουν πολλοί άλλοι κωδικοί πλεονασμού. Διαφορετικοί κωδικοί πλεονασμού χρησιμοποιούν διαφορετικά μαθηματικά. Ακολουθούν μερικοί άλλοι κωδικοί πλεονασμού:
- Κωδικός πλεονασμού χρησιμοποιώντας τον τελεστή XOR. Η λειτουργία XOR εκτελείται σε n μπλοκ δεδομένων και λαμβάνεται 1 μπλοκ κωδικών πλεονασμού, δηλαδή ένα σχήμα n+1 (n μπλοκ δεδομένων, 1 κωδικός πλεονασμού). Χρησιμοποιείται σε , όπου μπλοκ δεδομένων και κωδικοί πλεονασμού εγγράφονται κυκλικά σε όλους τους δίσκους του πίνακα.
- Αλγόριθμος ζυγός-περιττός βασισμένος στη λειτουργία XOR. Σας επιτρέπει να δημιουργήσετε 2 μπλοκ κωδικών πλεονασμού, δηλαδή το σχήμα n+2.
- Αλγόριθμος STAR βασισμένος στη λειτουργία XOR. Σας επιτρέπει να δημιουργήσετε 3 μπλοκ κωδικών πλεονασμού, δηλαδή το σχήμα n+3.
- Οι πυραμιδικοί κωδικοί είναι άλλοι κωδικοί πλεονασμού από τη Microsoft.
5. Χρήση στο Yandex
Ορισμένα έργα υποδομής Yandex χρησιμοποιούν κωδικούς πλεονασμού για αξιόπιστη αποθήκευση δεδομένων. Να μερικά παραδείγματα:
- Εσωτερική αποθήκευση αντικειμένων MDS, για την οποία έγραψα στην αρχή του άρθρου.
- — Σύστημα MapReduce του Yandex.
- (Yandex DataBase) - κατανεμημένη βάση δεδομένων newSQL.
Το MDS χρησιμοποιεί κωδικούς πλεονασμού LRC, σχήμα 8-2-2. Τα δεδομένα με κωδικούς πλεονασμού εγγράφονται σε 12 διαφορετικούς δίσκους σε διαφορετικούς διακομιστές σε 3 διαφορετικούς DC: 4 διακομιστές σε κάθε DC. Διαβάστε περισσότερα για αυτό στο .
Το YT χρησιμοποιεί τόσο κωδικούς Reed-Solomon (Σχήμα 6-3), οι οποίοι ήταν οι πρώτοι που εφαρμόστηκαν, όσο και κωδικούς πλεονασμού LRC (Σχήμα 12-2-2), με το LRC να είναι η προτιμώμενη μέθοδος αποθήκευσης.
Το YDB χρησιμοποιεί κωδικούς πλεονασμού που βασίζονται σε άρτιο-μονό (Εικόνα 4-2). Σχετικά με τους κωδικούς πλεονασμού στο YDB ήδη .
Η χρήση διαφορετικών σχημάτων κωδικών πλεονασμού οφείλεται σε διαφορετικές απαιτήσεις για συστήματα. Για παράδειγμα, στο MDS, τα δεδομένα που αποθηκεύονται με χρήση LRC τοποθετούνται σε 3 DCs ταυτόχρονα. Είναι σημαντικό για εμάς τα δεδομένα να παραμένουν διαθέσιμα για ανάγνωση εάν αποτύχει 1 από οποιονδήποτε DC, επομένως τα μπλοκ πρέπει να κατανέμονται στα DC έτσι ώστε εάν κάποιο DC δεν είναι διαθέσιμο, ο αριθμός των μη προσβάσιμων μπλοκ δεν είναι μεγαλύτερος από επιτρεπτός. Στο σχήμα 8-2-2, μπορείτε να τοποθετήσετε 4 μπλοκ σε κάθε DC και, στη συνέχεια, όταν απενεργοποιηθεί οποιοδήποτε DC, 4 μπλοκ δεν θα είναι διαθέσιμα και τα δεδομένα μπορούν να διαβαστούν. Όποιο σχήμα και να επιλέξουμε κατά την τοποθέτησή του σε 3 DC, σε κάθε περίπτωση θα πρέπει να υπάρχει (r + l) / n >= 0,5, δηλαδή ο πλεονασμός αποθήκευσης θα είναι τουλάχιστον 50%.
Στο YT η κατάσταση είναι διαφορετική: κάθε σύμπλεγμα YT βρίσκεται εξ ολοκλήρου σε 1 DC (διαφορετικά συμπλέγματα σε διαφορετικά DCs), επομένως δεν υπάρχει τέτοιος περιορισμός. Το σχήμα 12-2-2 παρέχει πλεονασμό 33%, δηλαδή, η αποθήκευση δεδομένων είναι φθηνότερη και μπορεί επίσης να επιβιώσει έως και 4 ταυτόχρονες διακοπές λειτουργίας δίσκου, ακριβώς όπως το σχήμα MDS.
Υπάρχουν πολλά περισσότερα χαρακτηριστικά της χρήσης κωδικών πλεονασμού σε συστήματα αποθήκευσης και επεξεργασίας δεδομένων: αποχρώσεις της ανάκτησης δεδομένων, ο αντίκτυπος της ανάκτησης στον χρόνο εκτέλεσης ερωτήματος, χαρακτηριστικά εγγραφής δεδομένων κ.λπ. Θα μιλήσω ξεχωριστά για αυτά και άλλα χαρακτηριστικά της χρήσης των κωδικών πλεονασμού στην πράξη, εάν το θέμα θα είναι ενδιαφέρον.
6. Σύνδεσμοι
- Μια σειρά άρθρων σχετικά με τους κώδικες Reed-Solomon και τα πεδία Galois:
Ρίχνουν μια βαθύτερη ματιά στα μαθηματικά σε προσιτή γλώσσα. - Άρθρο από τη Microsoft σχετικά με το LRC:
Η ενότητα 2 εξηγεί συνοπτικά τη θεωρία και στη συνέχεια συζητά τις εμπειρίες με το LRC στην πράξη. - Σχέδιο άρτιο-περιττό:
- Σχέδιο STAR:
- Κωδικοί πυραμίδας:
- Κωδικοί πλεονασμού στο MDS:
- Κωδικοί πλεονασμού στο YT:
- Κωδικοί πλεονασμού στο YDB:
Πηγή: www.habr.com