.
Η σειριοποιησιμότητα συγκρούσεων στις Βάσεις Δεδομενων (ΒΔ) είναι μία από τις δύο τεχνικές με την οποία μπορούμε να αποφανθούμε αν ένα χρονοπρόγραμμα είναι σειριοποιήσιμο, η άλλη τεχνική είναι η σειριοποιησιμότητα όψεως. Ο λόγος που πρέπει ένα χρονοπρόγραμμα να είναι σειριοποιήσιμο είναι διότι έτσι εξασφαλίζουμε την συνέπεια στην βάση δεδομένων μας. Η συνέπεια στην βάση μας μπορεί να χαλάσει διότι οι συναλλαγές στα χρονοπρογράμματα για μεγαλύτερη αποτελεσματικότητα και ταχύτητα δεν εκτελούνται σειριακά αλλά πολυπλεγμένα δηλαδή τα ΣΔΒΔ κατά κανόνα επιτρέπουν σε πολλές συναλλαγές να προσπελάζουν τα ίδια δεδομένα την ίδια στιγμή - και σε ένα τέτοιο σύστημα, όπως είναι γνωστό, χρειάζεται ένας μηχανισμός ελέγχου ταυτοχρονισμού, για να εξασφαλίζει ότι οι ταυτόχρονες συναλλαγές δε θα παρεμβάλλονται η μία στη λειτουργία της άλλης. Οι 2PL, αυστηρό 2PL (S2PL) και το δυνατό αυστηρό 2PL (SS2PL) είναι διαδεδομένοι μηχανισμοί ελέγχου σειριοποιησιμότητας συγκρούσεων οι οποίοι χρησιμοποιούνται στα περισσότερα συστήματα βάσεων δεδομένων.
Συναλλαγές Βάσεων Δεδομένων (ΒΔ)
Μία συναλλαγή ΒΔ είναι μία εκτέλεση ενός προγράμματος υπολογιστή το οποίο έχει πρόσβαση σε μια βάση δεδομένων ή Βάσεις Δεδομενων. Αυτό το πρόγραμμα υποθέτουμε ότι τρέχει απομονωμένα από αλλά προγράμματα τα οποία τρέχουν παράλληλα και όταν εκτελείται τα δεδομένα στα οποία έχει πρόσβαση δεν διαμορφώνονται από αλλά προγράμματα που εκτελούνται. Αν δεν γινόταν αυτό τότε τα αποτελέσματα της συναλλαγής θα ήταν εσφαλμένη και μη προβλέψιμα. Η ίδια συναλλαγή μπορεί εκτελεστεί σε διάφορες καταστάσεις π.χ. σε διαφορετικές τοποθεσίες και χρόνο και παράλληλα με άλλα προγράμματα. Μια ενεργή συναλλαγή μπορεί να έχει τρεις φάσεις/καταστάσεις:
Τρέχον – Το πρόγραμμα εκτελείται
Έτοιμο – Το πρόγραμμα έχει εκτελεστεί και περίμενε να γίνει commit η abort ανάλογα αν ήταν επιτυχημένη η εκτέλεση. Όταν γίνει commit τα πάντα τα οποία αφορούν αυτό το πρόγραμμα είναι ανακτήσιμα και οι πόροι πάνε στην τελική τους κατάσταση, την κατάσταση μετά το τρέχον. Όταν γίνεται abort, όλοι οι πόροι που χρησιμοποιήθηκαν επιστρέφουν στην αρχική τους κατάσταση, πριν τρέξει το πρόγραμμα.
Ολοκληρωμένο – Γίνεται commit ή abort .
Αν μια συναλλαγή αποτύχει για λόγους κρασαρίσματος (αποτυχία υλικού) τότε τυπικά καταλήγει σε abort.
Ορθότητα
Ορθότητα – Σειριοποιησιμότητα
Η σειριοποιησιμότητα είναι ένα χαρακτηριστικό των χρονοπρογραμμάτων των συναλλαγών. Σχετίζεται με την ιδιότητα της απομόνωσης μια συναλλαγής ΣΔΒΔ.
Η σειριοποιησιμότητα ενός χρονοπρογράμματος σημαίνει την ισότητα με ένα σειριακό χρονοπρόγραμμα μαζί με μερικές συναλλαγές. Είναι το κύριο κριτήριο για την ορθότητα όλων των ταυτόχρονων συναλλαγών σε ένα χρονοπρόγραμμα εξού και υποστηρίζεται σε όλα τα ΣΔΒΔ για γενικές χρήσεις.
Η λογική της σειριοποιησιμότητας είναι η ακόλουθη:
Αν κάθε συναλλαγή είναι ορθή από μόνη της ισχύουν κάποιοι κανόνες ακεραιότητας για αυτή, τότε ένα χρονοπρόγραμμα το οποίο αποτελείται από σειριακή εκτέλεση αυτών των συναλλαγών είναι σωστό. «Σειριακό» σημαίνει ότι όλες οι συναλλαγές δεν αλλάζουν το χρόνο εκτέλεσης τους και δεν παραμένουν η μια στην άλλη το οποίο παρεμπιπτόντως σημαίνει ότι ισχύει η ιδιότητα της απομόνωσης. Υποθέτουμε ότι οποιαδήποτε σειρά των συναλλαγών είναι θεμιτή αν δεν εξαρτάται η μία από την άλλη. Σαν αποτέλεσμα αυτών, ένα χρονοπρόγραμμα το οποίο αποτελείται από οποιαδήποτε εκτέλεση η οποία είναι ισοδύναμη με οποιαδήποτε σειριακή εκτέλεση αυτών των συναλλαγών, είναι ορθή.
Χρονοπρογράμματα τα οποία δεν είναι σειριοποιήσιμα είναι πιθανόν να βγάζουν εσφαλμένα αποτελέσματα. Γνωστά παραδείγματα είναι συναλλαγές που πιστώνουν ή χρεώνουν λογαριασμούς. Αν τα σχετικά χρονοπρογράμματα δεν είναι σειριοποιήσιμα τότε το σύνολο των χρημάτων μπορεί να μην είναι ορθό. Χρήματα θα μπορούσαν να εξαφανιστούν ή να παρουσιαστούν από το πουθενά. Αυτή και άλλες πιθανές παραβιάσεις προκαλούνται από συναλλαγές οι οποίες παρεμβαίνουν και γράφουν ή σβήνουν αυτά που γράφτηκαν από άλλες συναλλαγές πριν γίνουν commit. Αυτό δεν θα συνέβαινε αν υπάρχει σειριοποιησιμότητα.
Σχόλιο: Αν απαιτείται κάποια συγκεκριμένη σειρά συναλλαγών από κάποια εφαρμογή τότε αναγκάζεται, ανεξάρτητα από μηχανισμούς σειριοποιησιμότητας, να παρέμβει. Αυτοί οι μηχανισμοί είναι ίδιοι με μια συγκεκριμένη σειρά και παράγουν απρόβλεπτη διάταξη η οποία είναι συμβατή με πολλαπλές διατάξεις τέτοιων συναλλαγών. Αυτά τα αποτελέσματα διάταξης από προγραμματισμένες διατάξεις αποτελούμενες από λειτουργίες (διάβασμα, γράψιμο, commit, abort κλπ) ταυτόχρονων συναλλαγών που εξαρτώνται από πολλούς παράγοντες.
Ορθότητα – Ανακτησιμότητα
Ένα κύριο χαρακτηριστικό τvν συναλλαγών των βάσεων δεδομένων είναι η ατομικότητα το οποίο σημαίνει ότι είτε κάνουν commit και ισχύουν όλες οι αλλαγές τους, είτε κάνουν abort και επανέρχονται όλα στην κατάσταση πριν εκτελεστεί η συναλλαγή. Στα πραγματικά συστήματα οι συναλλαγές μπορούν να κάνουν abort για πολλούς και διάφορους λόγους και σειριοποιησιμότητα από μόνη της δεν είναι αρκετή για ορθότητα. Τα χρονοπρογράμματα χρειάζονται να κατέχουν την ιδιότητα της ανακτησιμότητας. Ανακτησιμότητα σημαίνει ότι οι συναλλαγές που έχουν κάνει commit δεν έχουν πάρει δεδομένα από συναλλαγές οι οποίες έχουν γίνει abort. Καθώς η σειριοποιησιμότητα δεν ισχύει για λόγους καλύτερης απόδοσης, το να θυσιάζεις την ανακτησιμότητα παραβιάζει την ακεραιότητα της ΒΔ και τα αποτελέσματα των συναλλαγών.
Έλεγχος σειριοποιησιμότητας συγκρούσεων
Ένα χρονοπρόγραμμα μπορεί να ελέγξει αν είναι σειριοποιήσιμο συγκρούσεων με τον γράφο σειριοποιησιμότητας για συναλλαγές που έχουν γίνει commit στο χρονοπρόγραμμα. Είναι ο κατευθυνόμενος γράφος ο οποίος αναπαριστά την παρουσίαση των συναλλαγών στο χρονοπρόγραμμα, όπως αντανακλάται από την αναπαράσταση των συγκρουόμενων λειτουργιών μιας συναλλαγής.
Στον γράφο σειριοποιησιμότητας οι συναλλαγές αναπαρίστανται με κόμβους και οι συγκρουόμενες σχέσεις αναπαρίστανται με κατευθυνόμενες ακμές. Υπάρχει μια ακμή από την πρώτη στην δεύτερη συναλλαγή, αν η δεύτερη συναλλαγή είναι σε σύγκρουση με την πρώτη και η σύγκρουση συμβαίνει (αν η ζητηθείσα ενέργεια, η οποία είναι συγκρουόμενη, πραγματοποιείται τότε σε πολλές περιπτώσεις μια ζητηθείσα ενέργεια η οποία θα καταλήξει σε σύγκρουση καθυστερείται η δεν εκτελείται από ένα κλείδωμα στο αντικείμενο της ενέργειας, το οποίο κατέχει κάποια άλλη συναλλαγή. Όσο μια τέτοια ενέργεια δεν εκτελείται τότε δεν πραγματοποιείται σύγκρουση και δεν αναπαρίσταται πάνω στο γράφο)
Σχόλιο: Σε πολλά βιβλία μόνο οι συναλλαγές οι οποίες έχουν γίνει commit συμπεριλαμβάνονται στον γράφο σειριοποιησιμότητας. Εδώ συμπεριλαμβάνονται όλες οι συναλλαγές για διευκόλυνση και συζήτηση.
Η επόμενη παρατήρηση αποτελεί κύριο χαρακτηριστικό της σειριοποιησιμότητας συγκρούσεων:
Ένα χρονοπρόγραμμα είναι σειριοποιήσιμο συγκρούσεων αν και μόνο αν έχει μη-κυκλικό γράφο συναλλαγών οι οποίες έχουν γίνει commit. Αυτό σημαίνει ότι ένας κύκλος από commited συναλλαγές υπάρχει στο γράφο σειριοποιησιμότητας αν και μόνο αν παραβιάζεται η σειριοποιησιμότητα συγκρούσεων.
Κύκλοι από συναλλαγές οι οποίες έχουν γίνει commit μπορούν να αποφευχθούν κάνοντας abort συναλλαγές οι οποίες δεν έχουν αποφασιστεί για το τι είναι σε κάθε κύκλο στον γράφο σειριοποιησιμότητας όλων των συναλλαγών οι οποίες μπορούν υπό άλλες συνθήκες να γίνουν commited. Μια συναλλαγή η οποία έχει γίνει abort ανά κύκλο είναι αρκετή για να ακυρώσει τον κύκλο (μπορούν να γίνουν και αλλά aborts αλλά δεν είναι απαραίτητα για σειριοποιησιμότητα). Η πιθανότητα για να συμβεί κύκλος είναι μικρή αλλά αν συμβεί κάτι τέτοιο τότε το χειριζόμαστε αναλόγως, αφού επιβάλλεται η ορθότητα. Οι συναλλαγές οι οποίες έχουν γίνει abort για να ισχύει η σειριοποιησιμότητα ξαναεκτελούνται αμέσως.
Οι μηχανισμοί ενδυνάμωσης σειριοποιησιμότητας δεν κατασκευάζουν γράφο σειριοποιησιμότητα αλλά φροντίζουν να μην δημιουργούνται κύκλοι κατά την εκτέλεση του χρονοπρογράμματος (πχ SS2PL, 2PL, S2PL κλπ).
Κοινοί Μηχανισμοί – SS2PL
Κύριο λήμμα: Κλείδωμα δύο Φάσεων
Το δυνατό αυστηρό πρωτόκολλο κλειδώματος δυο φάσεων (strong strict 2PL) είναι ένας κοινός μηχανισμός ο οποίος χρησιμοποιείται στις ΒΔ από το 1970 έως σήμερα για να ενισχύσει την αυστηρότητα και την σειριοποιησιμότητα ενός χρονοπρογράμματος. Σε αυτό το μηχανισμό κάθε αντικείμενο κλειδώνεται από μια συναλλαγή πριν την πρόσβαση αυτό (λειτουργία read ή write): το αντικείμενο χαρακτηρίζεται και συνδέεται με ένα κλείδωμα συγκεκριμένου τύπου ανάλογα με την ενέργεια. Σαν αποτέλεσμα αυτού η πρόσβαση από άλλη συναλλαγή μπλοκάρεται, τυπικά σε μια σύγκρουση ανάλογα με τον τύπο του κλειδώματος και τον τύπο πρόσβασης της συναλλαγής που θέλει το αντικείμενο. Παρεμβάλλοντας ένα μηχανισμό SS2PL σημαίνει ότι τα κλειδώματα απελευθερώνονται όταν τελειώσει μια συναλλαγή μαζί τους.
SS2PL είναι το όνομα της ιδιότητας του χρονοπρογράμματος που προκύπτει η οποία ονομάζεται και rigorousness. Το SS2PL είναι μια ειδική περίπτωση μεταξύ 2PL και Commitment Ordering (CO, πρόκειται για ένα άλλο μηχανισμό εγγύησης σειριοποιησιμότητας) Το αμοιβαίο μπλοκάρισμα μεταξύ συναλλαγών καταλήγει σε αδιέξοδο, όπου η εκτέλεση αυτών των συναλλαγών σταματά και δεν υπάρχει περάτωση. Έτσι τα αδιέξοδα πρέπει να επιλύονται για να ολοκληρώνονται αυτές οι συναλλαγές και να απελευθερώνονται πόροι του συστήματος. Ένα αδιέξοδο είναι ένας πιθανός κύκλος στο γράφο σειριοποιησιμότητας ο οποίος μπορεί να προκύψει χωρίς μπλοκάρισμα όταν πραγματοποιηθούν οι συγκρούσεις. Ένα αδιέξοδο μπορεί να επιλυθεί κάνοντας abort την συναλλαγή η οποία μπορεί να οδηγήσει σε κύκλο. Αυτή η συναλλαγή εντοπίζεται χρησιμοποιώντας ένα γράφο αναμονής (ένας γράφος συγκρούσεων με ακμές οι οποίες μπλοκάρονται από κλειδώματα – πρόκειται για έναν κατευθυνόμενο γράφο ο οποίος χρησιμοποιείται για την αποφυγή αδιεξόδων), ο οποίος υποδεικνύει ποιες συναλλαγές είναι έτοιμες να ελευθερώσουν το κλείδωμα τους και ποιες θέλουν να αναλάβουν το αντικείμενο και όταν υπάρχει κύκλος έχουμε αδιέξοδο. Κάνοντας abort μια συναλλαγή σε ένα κύκλο τότε απαλείφεται ο κύκλος. Συναλλαγές οι οποίες έχουν γίνει abort για επίλυση αδιεξόδων κάνουν επανεκκίνηση και εκτελούνται αμέσως.
Άλλες τεχνικές Εγγύησης Σειριοποιησιμότητας
Άλλοι γνωστοί μηχανισμοί συμπεριλαμβάνουν:
Γράφος Σειριοποιησιμότητας (precedence graph)
Κλείδωμα δύο Φάσεων (2 Phase Locking - 2PL)
Χρονοσήματα (Timestamp ordering - TO)
Commitment Ordering (CO)
Serializable snapshot isolation[1] (SerializableSI)
Αναφορές
Michael J. Cahill, Uwe Röhm, Alan D. Fekete (2008): "Serializable isolation for snapshot databases", Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 729-738, Vancouver, Canada, June 2008, ISBN 978-1-60558-102-6 (SIGMOD 2008 best paper award)
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
