Κλείδωμα δύο Φάσεων

 

 

.

Στις βάσεις δεδομένων (ΒΔ) και σε διαδικασίες συναλλαγών το Κλείδωμα δύο Φάσεων (2PL) είναι ένα πρωτόκολλο κλειδώματος ελέγχου ταυτοχρονισμού ή μηχανισμός ο οποίος μπορεί να εγγυηθεί σειριοποιησιμότητα. Χρησιμοποιώντας κλειδώματα που μπλοκάρουν διαδικασίες το 2PL μπορεί να προκαλέσει αδιέξοδα τα οποία προκαλούνται από αμοιβαίο μπλοκάρισμα δύο ή περισσοτέρων συναλλαγών.

Το 2PL είναι μια υπερκλάση του SS2PL το οποίο χρησιμοποιείται ευρέως για έλεγχο ταυτοχρονισμού σε συστήματα ΒΔ από το 1970 έως σήμερα. Το SS2PL έχει πολλές παραλλαγές.

Υπόψη ότι το 2PL είναι διαφορετικό από το 2PC (two-phase commit protocol).

Κλειδώματα

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

Υπάρχουν 2 βασικοί τύποι κλειδωμάτων:

Κλείδωμα ανάγνωσης Read-lock (shared lock) το οποίο επιτρέπει σε μια συναλλαγή να διαβάσει δεδομένα αλλά όχι να γράψει.

Κλείδωμα εγγραφής Write-lock (exclusive lock) το οποίο επιτρέπει σε μια συναλλαγή τόσο να διαβάσει όσο και να ενημερώσει δεδομένα.

Ο μηχανισμός κλειδωμάτων λειτουργεί ως εξής:

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

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

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

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

Υπάρχουν πολλές παραλλαγές αυτών των κλειδωμάτων με αντίστοιχες παραλλαγές συμπεριφοράς κλειδωμάτων. Αν ένα κλείδωμα μπλοκάρει ένα άλλο κλείδωμα τότε αυτό ορίζεται ως μη συμβατά κλειδώματα (σύγκρουση κλειδωμάτων). Παρακάτω παρουσιάζεται ο πίνακας συγκρούσεων σύμφωνα με τους παραπάνω κανόνες:

Υπάρχουν πολλές παραλλαγές αυτών των κλειδωμάτων με αντίστοιχες παραλλαγές συμπεριφοράς κλειδωμάτων. Αν ένα κλείδωμα μπλοκάρει ένα άλλο κλείδωμα τότε αυτό ορίζεται ως μη συμβατά κλειδώματα (σύγκρουση κλειδωμάτων). Παρακάτω παρουσιάζεται ο πίνακας συγκρούσεων σύμφωνα με τους παραπάνω κανόνες:

Πίνακας συμβατότητας κλειδωμάτων Τύπος κλειδώματος κλείδωμα-ανάγνωση κλείδωμα-εγγραφή
κλείδωμα-ανάγνωση X
κλείδωμα-εγγραφή X X

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

Με χρήση του παραπάνω μηχανισμού κλειδώματος υπάρχει ενδεχόμενο τα δεδομένα μας να είναι ασυνεπή, δηλαδή το αποτέλεσμα του χρονοπρογράμματος δεν είναι ίδιο με ένα σειριακό χρονοπρόγραμμα. Το πρόβλημα εντοπίζεται στον τρόπο δέσμευσης και απελευθέρωσης των κλειδωμάτων από τις συναλλαγές. Ένας μηχανισμός κλειδώματος πρέπει να ικανοποιεί ορισμένους κανόνες που να εγγυώνται την συνέπεια των δεδομένων. Οι κανόνες αυτοί ορίζουν ένα πρωτόκολλο κλειδώματος το οποίο εγγυάται ότι το χρονοπρόγραμμα είναι σειριοποιήσιμο.
Κλείδωμα δύο Φάσεων και ειδικές περιπτώσεις
Κλείδωμα δύο Φάσεων (2PL)

Σύμφωνα με το 2PL πρωτόκολλο μια συναλλαγή διαχειρίζεται τα κλειδώματα της σε δυο διακριτές φάσεις:

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

Φάση συρρίκνωσης: Τα κλειδώματα μόνο απελευθερώνονται.

Η σειριοποιησιμότητα είναι εγγυημένη για ένα πρόγραμμα συναλλαγών που υπακούουν το πρωτόκολλο. Το 2PL schedule class χαρακτηρίζεται σαν η κλάση όλων των προγραμματισμένων συναλλαγών με διεργασίες read-write οι οποίες δημιουργούνται από το πρωτόκολλο 2PL.

Σε μια συναλλαγή στο τέλος της φασης-1, είναι ασφαλές διευκρινισμένη μόνο όταν μια συναλλαγή είναι στη φάση «έτοιμη» σε όλες της διεργασίες (read, write) της. (Η διεργασία έχει τελειώσει και είναι έτοιμη να δεσμευτεί και δεν μπορεί να πάρει περεταίρω κλειδώματα). Σε αυτή την περίπτωση η φάση-2 μπορεί να τελειώσει αμέσως αφού δεν χρειάζεται να συνεχίσει. Επίσης αν πολλές διεργασίες περιπλέκονται τότε χρειάζεται ένα σημείο συγχρονισμού μεταξύ τους για να διευκρινίζει τη φάση-1για όλες τους έτσι ώστε να αρχίσει να απελευθερώνει κλειδώματα στη φάση-2(Αλλιώς είναι πολύ πιθανό η σειριοποιησιμότητα και το 2PL να παραβιαστούν). Ένα τέτοιο σημείο συγχρονισμού κοστίζει πολύ (περιπλέκοντας ένα κατανεμημένο πρωτόκολλο παρόμοιο με το atomic commitment) και το τέλος της φάσης-1 αναστέλλεται για να συγχωνευτεί με το τέλος της συναλλαγής όπου και πάλι δεν χρειάζεται η φάση-2.
Αυστηρό Κλείδωμα δύο Φάσεων (S2PL)

Η κλάση χρονοπρογραμμάτων αυστηρού πρωτόκολλου 2PL είναι η τομή της κλάσης 2PL με την κλάση χρονοπρογραμμάτων που έχουν τις ιδιότητες Strictness.

Για να είναι συμβατή μια συναλλαγή με το S2PL πρέπει να είναι επίσης συμβατή με το 2PL και να απελευθερώσει τα κλειδώματα-εγγραφή μόλις τελειώσει.

Αντίθετα τα κλειδώματα-ανάγνωση απελευθερώνονται κανονικά κατά τη διάρκεια της φάσης-2. Υλοποιώντας γενικά το S2PL απαιτεί σαφή υποστήριξη του τέλους της φάσης-1, διαχωρισμό από το τέλος της συναλλαγής και δεν έχει ακόμη υλοποιηθεί ένα τέτοιο προϊόν. Το αυστηρό 2PL πρωτόκολλο είναι μία ειδική περίπτωση 2PL.
Δυνατό Αυστηρό Κλείδωμα δύο Φάσεων (SS2PL)

Για να συνάδει μια συναλλαγή με το SS2PL το πρωτόκολλο κλειδώματος απελευθερώνει και write και read κλειδώματα μόνο όταν η συναλλαγή τελειώσει μαζί τους. Αυτό το πρωτόκολλο συνάδει επίσης με τους κανόνες του S2PL. Μια συναλλαγή που υπακούει στο SS2PL μπορεί να την δει κανείς σαν να έχει την φάση - 1 (βλέπε παραπάνω 2PL) η οποία διαρκεί καθ’ όλη την διάρκεια εκτέλεσης της συναλλαγής και καθόλου στην φάση - 2. Έτσι βλέπουμε ότι στην ουσία μένει μόνο μια φάση και το όνομα 2PL παρέμεινε διότι έχει καθιερωθεί έκτοτε. Η SS2PL ενός χρονοπρογράμματος αποκαλείται και rigorousness. Είναι επίσης το όνομα της κλάσης των χρονοπρογραμμάτων που έχουν αυτή την ιδιότητα και επίσης ένα SS2PL χρονοπρόγραμμα αποκαλείται και αυστηρό χρονοπρόγραμμα. Ο όρος rigorousness δεν έχει να κάνει με τον μύθο των δυο φάσεων και είναι ανεξάρτητος από κάθε είδους μηχανισμό κλειδώματος. Η ιδιότητα του μηχανισμού κλειδώματος αναφέρεται και σαν αυστηρό 2PL.

To SS2PL είναι ειδική περίπτωση του S2PL λόγου χάριν η κλάση χρονοπρογραμμάτων SS2PL είναι υποκλάση του S2PL.

Το SS2PL είναι ο κατ’ επιλογήν έλεγχος ταυτοχρονισμού για τα περισσότερα συστήματα ΒΔ και χρησιμοποιείται από το 1970. Έχει αποδειχτεί ότι είναι αποδοτικός μηχανισμός σε πολλές περιπτώσεις και παρέχει σειριοποιησιμότητα, αυστηρότητα και commitment ordering, που μπορεί να χρησιμοποιηθεί και σε κατανεμημένα περιβάλλοντα όπου απαιτείται καθολική σειριοποιησιμότητα. Όντας ένα υποσύνολο Commitment Ordering μια αποδοτική υλοποίηση κατανεμημένου SS2PL υπάρχει χωρίς κατανεμημένη διεύθυνση κλειδωμάτων, καθώς κατανεμημένα αδιέξοδα επιλύονται αυτομάτως. Το γεγονός ότι το SS2PL υιοθετείται σε πολλαπλά συστήματα ΒΔ διασφαλίζει καθολική σειριοποιησιμότητα και αυτό είναι γνωστό πολύ πιο πριν από την ανακάλυψη του commitment ordering, αλλά μόνο όταν εμφανίστηκε το commitment ordering έγινε κατανοητός ο ρόλος του πρωτόκολλου ατομικής δέσμευσης (atomic commitment) για διατήρηση καθολικής σειριοποιησιμότητας αλλά και για παρακολούθηση της αυτόματης κατανεμημένης επίλυσης αδιεξόδων. Για την ακρίβεια το SS2PL κληρονομεί ιδιότητες της ανακτησιμότητας και το Commitment Ordering είναι πιο σημαντικό από το να είναι ένα υποσύνολο του 2PL, το οποίο από μόνο του δεν παρέχει SS2PL κάποιας ποιότητας.

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

Σχόλια:

Πριν και μετά το 1990 σε πολλά άρθρα και συγγράμματα ο όρος αυστηρό 2PL ήταν συχνά ορισμένος σαν το πρωτόκολλο κλειδώματος «Απελευθέρωσε όλα τα κλειδώματα αφού τελειώσει η συναλλαγή» το οποίο είναι το πρωτόκολλο κλειδώματος SS2PL. Άρα το αυστηρό 2PL δεν μπορούσε να είναι διασταύρωση του ονόματος μεταξύ αυστηρότητας και 2PLτο οποίο είναι μεγαλύτερο από την τάξη που δημιουργείται από το SS2PL πρωτόκολλο. Αυτό όπως βλέπουμε προκαλεί σύγχυση. Με μια σαφή διευκρίνιση του S2PL σαν διασταύρωση της αυστηρότητας και του 2PL ένα νέο όνομα για το SS2PL και ένα σαφή διαχωρισμό μεταξύ κλάσεων S2PL και SS2PL, τα άρθρα (Breitbart et al. 1991) και (Raz 1992) σκόπευαν να ξεκαθαρίσουν την κατάσταση. Το πρώτο χρησιμοποίησε το όνομα rigorousness και το δεύτερο SS2PL.

Μια πιο γενική ιδιότητα από το SS2PL είναι το αυστηρό Commitment Ordering (SCO) το οποίο παρέχει σειριοποιησιμότητα, αυστηρότητα και Commitment Ordering και παρόμοια συμπεριφορά κλειδώματος. Αντίθετα με το SS2PL δεν μπλοκάρει σε μια read, write σύγκρουση (ένα κλείδωμα-ανάγνωσης δεν μπλοκάρει αποκτώντας ένα κλείδωμα-ανάγνωσης. Το SCO και το SS2PL έχουν την ίδια συμπεριφορά για συγκρούσεις ανάγνωσης-εγγραφής και ανάγνωσης-ανάγνωσης.) αφού θα κοστίσει ένα καθυστερημένο commit έτσι μια σύγκρουση τύπου SCO έχει μικρότερο μέσο όρο περάτωσης συναλλαγών και καλύτερη απόδοση από το SS2PL. Το SCO υπακούει τον παρακάτω πίνακα ενώ το SS2PL υπακούει το παραπάνω πίνακα.

Πίνακας Συμβατότητας για SCO Τύπος κλειδώματος κλείδωμα-ανάγνωση κλείδωμα-εγγραφή
κλείδωμα-ανάγνωση
κλείδωμα-εγγραφή X X

Αν και το SCO απελευθερώνει όλα τα κλειδώματα στο τέλος μιας συναλλαγής και συνάδει με τους 2PL κανόνες δεν αποτελεί υποσύνολο του 2PL λόγω του διαφορετικού πίνακα κλειδωμάτων. Το SCO επιτρέπει συγκρούσεις ανάγνωσης-εγγραφής στη φάση 1 αλλά το 2PL δεν το επιτρέπει αυτό. Το 2PL επιτρέπει όμως άλλου τύπου συγκρούσεις στη φάση 2 έτσι ώστε να μην επιτρέπονται καθόλου από το SCO. Αυτό σημαίνει έμμεσα ότι οι κλάσεις χρονοπρογραμμάτων 2PL και SCO δεν συγκρίνονται.

Αδιέξοδα στο 2PL

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

Σε κατανεμημένα περιβάλλοντα απαιτείται ένα πρωτόκολλο ατομικής δέσμευσης (atomic commitment) για ατομικότητα (συνήθως το 2PC). Όταν ανακτημένα δεδομένα κατανέμονται μεταξύ συναλλαγών που χρησιμοποιούν το 2PC και έπειτα κατανέμονται καθολικά αδιέξοδα (δηλαδή αδιέξοδα τα οποία εμπλέκουν δυο συναλλαγές στο 2PC) τα οποία λύνονται αυτομάτως.

Όταν το SS2PL χρησιμοποιείται σε κατανεμημένο περιβάλλον τότε τα καθολικά αδιέξοδα για να κλειδώσουν δημιουργούν voting-deadlocks στο 2PC και επιλύονται αυτόματα από το 2PC (βλέπε commitment ordering). Γενικά στο 2PL τα καθολικά αδιέξοδα επιλύονται παρομοίως από το πρωτόκολλο σημείο συγχρονισμού στο τέλος της φάσης – 1 σε μια κατανεμημένη συναλλαγή (το σημείο συγχρονισμού επιτυγχάνεται με «voting» (το οποίο σημειώνεται το τέλος της φάσης - 1) και διαδίδεται στα μέρη της συναλλαγής όπως σε μια κατανεμημένη συναλλαγή με τον ίδιο τρόπο σαν ένα σημείο απόφασης στην ατομική δέσμευση (atomic commitment). Κατ’ αναλογία με το σημείο απόφασης στο Commitment Ordering μια συγκρουόμενη ενέργεια στο 2PL δεν μπορεί να συμβεί πριν το τέλος της φάσης – 1 στο σημείο συγχρονισμού, και αυτό έχει το ίδιο αποτέλεσμα με το voting-deadlock για περιπτώσεις αδιεξόδων καθολικής πρόσβασης δεδομένων. Το voting-deadlock λύνεται αυτόματα από το πρωτόκολλο κάνοντας abort μερικές συναλλαγές που εμπλέκονται σε αυτό, χάνοντας ένα vote, χρησιμοποιώντας timeout).

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

Για τα Commitment Ordering και στην ειδική περίπτωση του SS2PL η αυτόματη επίλυση από το πρωτόκολλο ατομικής δέσμευσης σημειώνεται μόνο σε άρθρα για το Commitment Ordering.
Για το 2PL γενικά η αυτόματη επίλυση από το πρωτόκολλο σημείου συγχρονισμού στο τέλος της φάσης – 1 (η οποία έχει τον ίδιο μηχανισμό voting με το πρωτόκολλο ατομικής δέσμευσης, και το φαινόμενο της «vote που αγνοείται» στο voting-deadlock καταλήγει σε επίλυση καθολικού αδιεξόδου) δεν αναφέρεται μέχρι το 2009. Πρακτικά χρησιμοποιείται μόνο το SS2PL και δεν χρειάζεται ούτε συγχρονισμός στο τέλος της φάσης – 1 ούτε και πρωτόκολλο ατομικής δέσμευσης.

Σε κατανεμημένα περιβάλλοντα όπου τα ανακτήσιμα δεδομένα δεν διαμοιράζονται ανάμεσα στα μέλη του 2PC χρειάζονται ειδικές τεχνικές για να επιλύσουν τα καθολικά αδιέξοδα.
Αναφορές

Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman (1987): Concurrency Control and Recovery in Database Systems, Addison Wesley Publishing Company, ISBN 0-20110-715-5
Gerhard Weikum, Gottfried Vossen (2001): Transactional Information Systems, Elsevier, ISBN 1-55860-508-8
Yuri Breitbart, Dimitrios Georgakopoulos, Marek Rusinkiewicz, Abraham Silberschatz (1991): "On Rigorous Transaction Scheduling", IEEE Transactions on Software Engineering (TSE), September 1991, Volume 17, Issue 9, pp. 954-960, ISSN: 0098-5589
Yoav Raz (1992): "The Principle of Commitment Ordering, or Guaranteeing Serializability in a Heterogeneous Environment of Multiple Autonomous Resource Managers Using Atomic Commitment", Proceedings of the Eighteenth International Conference on Very Large Data Bases (VLDB), pp. 292-312, Vancouver, Canada, August 1992, ISBN 1-55860-151-1 (also DEC-TR 841, Digital Equipment Corporation, November 1990)

Εγκυκλοπαίδεια Πληροφορικής

Κόσμος

Αλφαβητικός κατάλογος

Hellenica World - Scientific Library

Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License