Συναλλαγές
Μια συναλλαγή είναι μια ακολουθία πράξεων σε δεδομένα που έχει αρχή και τέλος.
Μια συναλλαγή είναι η διαδοχική εκτέλεση πράξεων ανάγνωσης και εγγραφής. Το τέλος μιας συναλλαγής μπορεί να είναι είτε αποθήκευση των αλλαγών (δέσμευση) είτε ακύρωση των αλλαγών (επαναστροφή). Σε σχέση με μια βάση δεδομένων, μια συναλλαγή αποτελείται από πολλά αιτήματα που αντιμετωπίζονται ως ένα μόνο αίτημα.
Οι συναλλαγές πρέπει να πληρούν τις ιδιότητες ACID
Ατομικότητα. Η συναλλαγή είτε ολοκληρώνεται πλήρως είτε καθόλου.
Συνοχή. Κατά την ολοκλήρωση μιας συναλλαγής, οι περιορισμοί που επιβάλλονται στα δεδομένα (για παράδειγμα, περιορισμοί στη βάση δεδομένων) δεν πρέπει να παραβιάζονται. Η συνέπεια συνεπάγεται ότι το σύστημα θα μεταφερθεί από μια σωστή κατάσταση σε μια άλλη σωστή κατάσταση.
Απομόνωση. Οι συναλλαγές που εκτελούνται παράλληλα δεν πρέπει να επηρεάζουν η μία την άλλη, για παράδειγμα, να αλλάζουν δεδομένα που χρησιμοποιούνται από μια άλλη συναλλαγή. Το αποτέλεσμα της εκτέλεσης παράλληλων συναλλαγών θα πρέπει να είναι το ίδιο όπως εάν οι συναλλαγές εκτελούνταν διαδοχικά.
Βιωσιμότητα. Αφού πραγματοποιηθούν, οι αλλαγές δεν πρέπει να χαθούν.
ημερολόγιο συναλλαγών
Το αρχείο καταγραφής αποθηκεύει τις αλλαγές που πραγματοποιούνται από τις συναλλαγές, εξασφαλίζει ατομικότητα και σταθερότητα των δεδομένων σε περίπτωση βλάβης του συστήματος
Το αρχείο καταγραφής περιέχει τις τιμές που είχαν τα δεδομένα πριν και μετά την αλλαγή τους από τη συναλλαγή. Η στρατηγική καταγραφής εγγραφής προϋποθέτει την προσθήκη μιας καταχώρισης αρχείου καταγραφής σχετικά με προηγούμενες τιμές πριν από την έναρξη και σχετικά με τις τελικές τιμές μετά την ολοκλήρωση της συναλλαγής. Σε περίπτωση ξαφνικής διακοπής του συστήματος, η βάση δεδομένων διαβάζει το αρχείο καταγραφής με αντίστροφη σειρά και ακυρώνει τις αλλαγές που έγιναν από τις συναλλαγές. Έχοντας αντιμετωπίσει μια διακοπείσα συναλλαγή, η βάση δεδομένων την εκτελεί και κάνει αλλαγές σχετικά με αυτήν στο αρχείο καταγραφής. Όντας στην κατάσταση τη στιγμή της αποτυχίας, η βάση δεδομένων διαβάζει το αρχείο καταγραφής με τη σειρά και επιστρέφει τις αλλαγές που έγιναν από τις συναλλαγές. Με αυτόν τον τρόπο, διατηρείται η σταθερότητα των συναλλαγών που έχουν ήδη δεσμευτεί και η ατομικότητα της διακοπείσας συναλλαγής.
Η απλή επανεκτέλεση των αποτυχημένων συναλλαγών δεν αρκεί για την ανάκτηση.
Παράδειγμα. Ο χρήστης έχει 500 $ στον λογαριασμό του και ο χρήστης αποφασίζει να τα αποσύρει από ένα ΑΤΜ. Δύο συναλλαγές βρίσκονται σε εξέλιξη. Το πρώτο διαβάζει την αξία του υπολοίπου και εάν υπάρχουν αρκετά χρήματα στο υπόλοιπο, εκδίδει χρήματα στον χρήστη. Το δεύτερο αφαιρεί το απαιτούμενο ποσό από το υπόλοιπο. Ας πούμε ότι το σύστημα κατέρρευσε και η πρώτη λειτουργία απέτυχε, αλλά η δεύτερη. Σε αυτήν την περίπτωση, δεν μπορούμε να επανεκδώσουμε χρήματα στον χρήστη χωρίς να επιστρέψουμε το σύστημα στην αρχική του κατάσταση με θετικό υπόλοιπο.
Επίπεδα μόνωσης
Διαβάστε δεσμευμένος
Το πρόβλημα Dirty Read είναι ότι μια συναλλαγή μπορεί να διαβάσει το ενδιάμεσο αποτέλεσμα μιας άλλης συναλλαγής.
Παράδειγμα. Η αρχική αξία υπολοίπου είναι $0. Το T1 προσθέτει 50 $ στο υπόλοιπό σας. Το T2 διαβάζει την τιμή του υπολοίπου (50 $). Το T1 απορρίπτει τις αλλαγές και εξέρχεται. Το T2 συνεχίζει την εκτέλεση με λανθασμένα δεδομένα υπολοίπου.
Η λύση είναι η ανάγνωση σταθερών δεδομένων (Read Committed), η οποία απαγορεύει την ανάγνωση δεδομένων που έχουν αλλάξει από τη συναλλαγή. Εάν η συναλλαγή Α έχει αλλάξει ένα συγκεκριμένο σύνολο δεδομένων, τότε η συναλλαγή Β, όταν έχει πρόσβαση σε αυτά τα δεδομένα, αναγκάζεται να περιμένει να ολοκληρωθεί η συναλλαγή Α.
Επαναλαμβανόμενη ανάγνωση
Πρόβλημα με τις χαμένες ενημερώσεις. Το T1 αποθηκεύει τις αλλαγές πάνω από τις αλλαγές του T2.
Παράδειγμα. Η αρχική αξία υπολοίπου είναι $0 και δύο συναλλαγές αναπληρώνουν ταυτόχρονα το υπόλοιπο. Το T1 και το T2 διάβασαν ένα υπόλοιπο 0 $. Στη συνέχεια, το T2 προσθέτει $200 έως $0 και αποθηκεύει το αποτέλεσμα. Το T1 προσθέτει $100 σε $0 και αποθηκεύει το αποτέλεσμα. Το τελικό αποτέλεσμα είναι $100 αντί για $300.
Ανεπανάληπτο πρόβλημα ανάγνωσης. Η επανειλημμένη ανάγνωση των ίδιων δεδομένων επιστρέφει διαφορετικές τιμές.
Παράδειγμα. Το T1 διαβάζει μια τιμή υπολοίπου $0. Στη συνέχεια, το T2 προσθέτει $50 στο υπόλοιπο και τελειώνει. Το T1 διαβάζει ξανά τα δεδομένα και βρίσκει μια ασυμφωνία με το προηγούμενο αποτέλεσμα.
Η επαναλαμβανόμενη ανάγνωση διασφαλίζει ότι μια δεύτερη ανάγνωση θα επιστρέψει το ίδιο αποτέλεσμα. Τα δεδομένα που διαβάζονται από μία συναλλαγή δεν μπορούν να αλλάξουν σε άλλες μέχρι να ολοκληρωθεί η συναλλαγή. Εάν η συναλλαγή Α έχει διαβάσει ένα συγκεκριμένο σύνολο δεδομένων, τότε η συναλλαγή Β, όταν έχει πρόσβαση σε αυτά τα δεδομένα, αναγκάζεται να περιμένει να ολοκληρωθεί η συναλλαγή Α.
Παραγγελία ανάγνωσης (Σειριοποιήσιμη)
Πρόβλημα Phantom Reads. Δύο ερωτήματα που επιλέγουν δεδομένα με βάση μια συγκεκριμένη συνθήκη επιστρέφουν διαφορετικές τιμές.
Παράδειγμα. Το T1 ζητά τον αριθμό όλων των χρηστών των οποίων το υπόλοιπο είναι μεγαλύτερο από 0 $ αλλά μικρότερο από 100 $. Το T2 αφαιρεί $1 από έναν χρήστη με υπόλοιπο 101 $. Το T1 επανεκδίδει το αίτημα.
Διατεταγμένη ανάγνωση (Σειριοποιήσιμη). Οι συναλλαγές εκτελούνται εντελώς διαδοχικά. Απαγορεύεται η ενημέρωση ή προσθήκη εγγραφών που εμπίπτουν στους όρους του αιτήματος. Εάν η συναλλαγή Α έχει ζητήσει δεδομένα από ολόκληρο τον πίνακα, τότε ολόκληρος ο πίνακας παγώνει για άλλες συναλλαγές μέχρι να ολοκληρωθεί η συναλλαγή Α.
Προγραμματιστής
Ορίζει τη σειρά με την οποία πρέπει να εκτελούνται οι λειτουργίες κατά τις παράλληλες συναλλαγές.
Παρέχει ένα συγκεκριμένο επίπεδο απομόνωσης. Εάν το αποτέλεσμα των πράξεων δεν εξαρτάται από τη σειρά τους, τότε τέτοιες πράξεις είναι ανταλλάξιμες (Permutable). Οι λειτουργίες ανάγνωσης και οι λειτουργίες σε διαφορετικά δεδομένα είναι αντισταθμιστικές. Οι λειτουργίες ανάγνωσης-εγγραφής και εγγραφής-εγγραφής δεν είναι ανταλλάξιμες. Η αποστολή του χρονοπρογραμματιστή είναι να παρεμβάλλει λειτουργίες που εκτελούνται από παράλληλες συναλλαγές έτσι ώστε το αποτέλεσμα της εκτέλεσης να είναι ισοδύναμο με τη διαδοχική εκτέλεση των συναλλαγών.
Μηχανισμοί ελέγχου παράλληλων εργασιών (Concurrency Control)
Το αισιόδοξο βασίζεται στην ανίχνευση και την επίλυση συγκρούσεων, το απαισιόδοξο βασίζεται στην αποτροπή της εμφάνισης συγκρούσεων.
Στην αισιόδοξη προσέγγιση, πολλοί χρήστες έχουν στη διάθεσή τους αντίγραφα των δεδομένων. Το πρώτο άτομο που θα ολοκληρώσει την επεξεργασία αποθηκεύει τις αλλαγές, ενώ οι άλλοι πρέπει να συγχωνεύσουν τις αλλαγές. Ένας αισιόδοξος αλγόριθμος επιτρέπει την εμφάνιση σύγκρουσης, αλλά το σύστημα πρέπει να ανακάμψει από τη σύγκρουση.
Με μια απαισιόδοξη προσέγγιση, ο πρώτος χρήστης που καταγράφει τα δεδομένα εμποδίζει τους άλλους να λάβουν τα δεδομένα. Εάν οι συγκρούσεις είναι σπάνιες, είναι συνετό να επιλέξετε την αισιόδοξη στρατηγική, καθώς παρέχει υψηλότερο επίπεδο ταυτότητος.
Κλείδωμα
Εάν μια συναλλαγή έχει κλειδωμένα δεδομένα, τότε οι άλλες συναλλαγές πρέπει να περιμένουν μέχρι να ξεκλειδωθεί κατά την πρόσβαση στα δεδομένα.
Ένα μπλοκ μπορεί να επικαλύπτεται σε μια βάση δεδομένων, πίνακα, σειρά ή χαρακτηριστικό. Το Shared Lock μπορεί να επιβληθεί στα ίδια δεδομένα από πολλές συναλλαγές, επιτρέπει σε όλες τις συναλλαγές (συμπεριλαμβανομένης αυτής που το επέβαλε) την ανάγνωση, απαγορεύει την τροποποίηση και την αποκλειστική λήψη. Το αποκλειστικό κλείδωμα μπορεί να επιβληθεί μόνο από μία συναλλαγή, επιτρέπει οποιεσδήποτε ενέργειες της επιβλητικής συναλλαγής, απαγορεύει οποιεσδήποτε ενέργειες από άλλους.
Ένα αδιέξοδο είναι μια κατάσταση όπου οι συναλλαγές καταλήγουν σε κατάσταση εκκρεμότητας που διαρκεί επ' αόριστον.
Παράδειγμα. Η πρώτη συναλλαγή περιμένει να δημοσιοποιηθούν τα δεδομένα που έχει συλλέξει ο δεύτερος, ενώ η δεύτερη περιμένει να απελευθερωθούν τα δεδομένα που έχει συλλέξει ο πρώτος.
Μια αισιόδοξη λύση στο πρόβλημα του αδιεξόδου επιτρέπει την εμφάνιση του αδιεξόδου, αλλά στη συνέχεια ανακτά το σύστημα επαναφέροντας μια από τις συναλλαγές που εμπλέκονται στο αδιέξοδο.
Τα αδιέξοδα αναζητούνται σε συγκεκριμένα χρονικά διαστήματα. Μία από τις μεθόδους ανίχνευσης είναι με το χρόνο, δηλαδή, θεωρήστε ότι έχει προκύψει αδιέξοδο εάν η συναλλαγή διαρκεί πολύ για να ολοκληρωθεί. Όταν εντοπιστεί ένα αδιέξοδο, μία από τις συναλλαγές επαναφέρεται, επιτρέποντας σε άλλες συναλλαγές που εμπλέκονται στο αδιέξοδο να ολοκληρωθούν. Η επιλογή του θύματος μπορεί να βασίζεται στην αξία των συναλλαγών ή στην αρχαιότητά τους (σχήματα Wait-Die και Wound-wait).
Κάθε συναλλαγή T εκχωρείται χρονική σήμανση TS που περιέχει την ώρα έναρξης της συναλλαγής.
Περίμενε-Πέθανε.
αν TS (Ti) < TS(Tj), Στη συνέχεια Ti περιμένει, αλλιώς Ti γυρίζει πίσω και ξεκινά ξανά με την ίδια χρονική σήμανση.
Εάν μια νέα συναλλαγή έχει αποκτήσει έναν πόρο και μια παλαιότερη συναλλαγή ζητήσει τον ίδιο πόρο, τότε η παλαιότερη συναλλαγή επιτρέπεται να περιμένει. Εάν μια παλαιότερη συναλλαγή έχει αποκτήσει έναν πόρο, τότε η νεότερη συναλλαγή που ζητά αυτόν τον πόρο θα αποσυρθεί.
Πληγή-αναμονή.
αν TS (Ti) < TS(Tj), Στη συνέχεια Tj γυρίζει πίσω και ξεκινά ξανά με την ίδια χρονική σήμανση, διαφορετικά Ti αναμονή.
Εάν μια νεότερη συναλλαγή έχει αποκτήσει έναν πόρο και μια παλαιότερη συναλλαγή ζητήσει τον ίδιο πόρο, τότε η νεότερη συναλλαγή θα επαναφερθεί. Εάν μια παλαιότερη συναλλαγή έχει αποκτήσει έναν πόρο, τότε η νεότερη συναλλαγή που ζητά αυτόν τον πόρο επιτρέπεται να περιμένει. Η επιλογή θύματος βάσει προτεραιότητας αποτρέπει τα αδιέξοδα, αλλά επαναφέρει τις συναλλαγές που δεν είναι αδιέξοδες. Το πρόβλημα είναι ότι οι συναλλαγές μπορούν να επαναληφθούν πολλές φορές επειδή... μια παλαιότερη συναλλαγή μπορεί να κρατήσει τον πόρο για μεγάλο χρονικό διάστημα.
Μια απαισιόδοξη λύση στο πρόβλημα του αδιεξόδου δεν επιτρέπει σε μια συναλλαγή να ξεκινήσει να εκτελείται εάν υπάρχει κίνδυνος αδιεξόδου.
Για τον εντοπισμό ενός αδιεξόδου, κατασκευάζεται ένα γράφημα (γράφημα αναμονής, γράφημα αναμονής), οι κορυφές του οποίου είναι συναλλαγές και οι ακμές κατευθύνονται από τις συναλλαγές που περιμένουν την απελευθέρωση δεδομένων στη συναλλαγή που έχει συλλάβει αυτά τα δεδομένα. Ένα αδιέξοδο θεωρείται ότι έχει συμβεί εάν το γράφημα έχει βρόχο. Η κατασκευή ενός γραφήματος αναμονής, ειδικά σε κατανεμημένες βάσεις δεδομένων, είναι μια δαπανηρή διαδικασία.
Κλείδωμα δύο φάσεων - αποτρέπει τα αδιέξοδα με την κατάσχεση όλων των πόρων που χρησιμοποιούνται από μια συναλλαγή στην αρχή της συναλλαγής και την απελευθέρωσή τους στο τέλος
Όλες οι λειτουργίες μπλοκαρίσματος πρέπει να προηγούνται της πρώτης λειτουργίας ξεκλειδώματος. Έχει δύο φάσεις - Φάση Ανάπτυξης, κατά την οποία συσσωρεύονται οι λαβές και Φάση Συρρίκνωσης, κατά την οποία απελευθερώνονται οι λαβές. Εάν είναι αδύνατο να συλλάβετε έναν από τους πόρους, η συναλλαγή ξεκινά από την αρχή. Είναι πιθανό μια συναλλαγή να μην μπορεί να αποκτήσει τους απαιτούμενους πόρους, για παράδειγμα, εάν πολλές συναλλαγές ανταγωνίζονται για τους ίδιους πόρους.
Μια δέσμευση δύο φάσεων διασφαλίζει ότι η δέσμευση εκτελείται σε όλα τα αντίγραφα της βάσης δεδομένων
Κάθε βάση δεδομένων εισάγει πληροφορίες σχετικά με τα δεδομένα που θα αλλάξουν στο αρχείο καταγραφής και απαντά στον συντονιστή ΟΚ (Φάση ψηφοφορίας). Αφού όλοι απαντήσουν ΟΚ, ο συντονιστής στέλνει ένα σήμα υποχρεώνοντας όλους να δεσμευτούν. Μετά τη δέσμευση, οι διακομιστές αποκρίνονται ΟΚ· εάν τουλάχιστον ένας δεν ανταποκρίνεται ΟΚ, τότε ο συντονιστής στέλνει ένα σήμα για να ακυρώσει τις αλλαγές σε όλους τους διακομιστές (Φάση Ολοκλήρωσης).
Μέθοδος χρονοσήμανσης
Μια παλαιότερη συναλλαγή επαναφέρεται όταν επιχειρείται πρόσβαση σε δεδομένα που σχετίζονται με μια νεότερη συναλλαγή
Σε κάθε συναλλαγή εκχωρείται μια χρονική σήμανση TS που αντιστοιχεί στην ώρα έναρξης της εκτέλεσης. Αν Ti πάνω Tj, Στη συνέχεια TS (Ti) < TS(Tj).
Όταν μια συναλλαγή επαναφέρεται, της εκχωρείται μια νέα χρονική σήμανση. Κάθε αντικείμενο δεδομένων Q που συμμετέχει στη συναλλαγή επισημαίνεται με δύο ετικέτες. W-TS(Q) — χρονική σήμανση της νεότερης συναλλαγής που ολοκλήρωσε επιτυχώς ένα ρεκόρ Q. R-TS(Q) — χρονική σήμανση της νεότερης συναλλαγής που πραγματοποίησε εγγραφή ανάγνωσης Q.
Όταν η συναλλαγή T αιτήματα για ανάγνωση δεδομένων Q Υπάρχουν δύο επιλογές.
αν TS(T) < W-TS(Q), δηλαδή τα δεδομένα ενημερώθηκαν από μια νεότερη συναλλαγή και μετά η συναλλαγή T κυλά πίσω.
αν TS(T) >= W-TS(Q), τότε πραγματοποιείται η ανάγνωση και R-TS(Q) γίνεται όλο και περισσότερο MAX(R-TS(Q), TS(T)).
Όταν η συναλλαγή T ζητά αλλαγές δεδομένων Q Υπάρχουν δύο επιλογές.
αν TS(T) < R-TS(Q), δηλαδή τα δεδομένα έχουν ήδη διαβαστεί από νεότερη συναλλαγή και αν γίνει αλλαγή θα προκύψει σύγκρουση. Συναλλαγή T κυλά πίσω.
αν TS(T) < W-TS(Q), δηλαδή, η συναλλαγή προσπαθεί να αντικαταστήσει μια νεότερη τιμή, η συναλλαγή T επαναφέρεται. Σε άλλες περιπτώσεις, η αλλαγή πραγματοποιείται και W-TS(Q) γίνεται ίσος TS(T).
Δεν απαιτείται ακριβή κατασκευή γραφήματος αναμονής. Οι παλαιότερες συναλλαγές εξαρτώνται από νεότερες, επομένως δεν υπάρχουν κύκλοι στο γράφημα αναμονής. Δεν υπάρχουν αδιέξοδα γιατί οι συναλλαγές δεν αναμένουν αλλά επαναφέρονται αμέσως. Είναι δυνατές διαδοχικές ανατροπές. Αν Ti κύλησε μακριά και Tj Διάβασα τα δεδομένα που άλλαξα Ti, Στη συνέχεια Tj θα πρέπει επίσης να γυρίσει πίσω. Αν την ίδια στιγμή Tj έχει ήδη διαπραχθεί, τότε θα υπάρξει παραβίαση της αρχής της σταθερότητας.
Μία από τις λύσεις για κλιμακωτές ανατροπές. Μια συναλλαγή ολοκληρώνει όλες τις λειτουργίες εγγραφής στο τέλος και άλλες συναλλαγές πρέπει να περιμένουν να ολοκληρωθεί αυτή η λειτουργία. Οι συναλλαγές περιμένουν να πραγματοποιηθούν πριν διαβαστούν.
Κανόνας εγγραφής Thomas - μια παραλλαγή της μεθόδου της χρονικής σφραγίδας κατά την οποία τα δεδομένα που ενημερώνονται από μια νεότερη συναλλαγή απαγορεύεται να αντικατασταθούν από μια παλαιότερη
Συναλλαγή T ζητά αλλαγές δεδομένων Q. Αν TS(T) < W-TS(Q), δηλαδή, η συναλλαγή προσπαθεί να αντικαταστήσει μια νεότερη τιμή, η συναλλαγή T δεν επαναφέρεται όπως στη μέθοδο της χρονικής σήμανσης.
Πηγή: www.habr.com