Transaccions
Una transacció és una seqüència d'operacions sobre dades que té un principi i un final.
Una transacció és l'execució seqüencial d'operacions de lectura i escriptura. El final d'una transacció pot ser desar els canvis (commit) o cancel·lar els canvis (rollback). En relació a una base de dades, una transacció consta de diverses sol·licituds que es tracten com una sol·licitud única.
Les transaccions han de complir les propietats ACID
Atomicitat. La transacció s'ha completat completament o no es completa.
Coherència. En completar una transacció, no s'han de violar les restriccions imposades a les dades (per exemple, les restriccions a la base de dades). La coherència implica que el sistema es transferirà d'un estat correcte a un altre estat correcte.
Aïllament. Les transaccions que s'executen en paral·lel no haurien d'influir entre elles, per exemple, canviar les dades utilitzades per una altra transacció. El resultat d'executar transaccions paral·leles hauria de ser el mateix que si les transaccions s'executessin seqüencialment.
Sostenibilitat. Un cop compromesos, els canvis no s'han de perdre.
Registre de transaccions
El registre emmagatzema els canvis fets per les transaccions, garanteix l'atomicitat i l'estabilitat de les dades en cas de fallada del sistema.
El registre conté els valors que tenien les dades abans i després de ser modificades per la transacció. L'estratègia de registre d'escriptura anticipada requereix afegir una entrada de registre sobre els valors anteriors abans de l'inici i sobre els valors finals un cop finalitzada la transacció. En cas d'aturada sobtada del sistema, la base de dades llegeix el registre en ordre invers i cancel·la els canvis fets per les transaccions. Després d'haver trobat una transacció interrompuda, la base de dades l'executa i fa canvis al registre. Estant en l'estat en el moment de la fallada, la base de dades llegeix el registre en ordre d'enviament i retorna els canvis fets per les transaccions. D'aquesta manera, es preserva l'estabilitat de les transaccions que ja s'han compromès i l'atomicitat de la transacció interrompuda.
Simplement tornar a executar transaccions fallides no és suficient per a la recuperació.
Exemple. L'usuari té 500 dòlars al seu compte i l'usuari decideix retirar-los d'un caixer automàtic. Dues transaccions estan en curs. El primer llegeix el valor del saldo i si hi ha prou fons al saldo, emet diners a l'usuari. El segon resta la quantitat necessària del saldo. Suposem que el sistema es va estavellar i la primera operació no es va completar, però la segona sí. En aquest cas, no podem tornar a emetre diners a l'usuari sense tornar el sistema al seu estat original amb un saldo positiu.
Nivells d'aïllament
Llegeix Compromesos
El problema de lectura bruta és que una transacció pot llegir el resultat intermedi d'una altra transacció.
Exemple. El valor del saldo inicial és de $0. T1 afegeix 50 $ al vostre saldo. T2 llegeix el valor del saldo (50 $). T1 descarta els canvis i surt. T2 continua l'execució amb dades de balanç incorrectes.
La solució és llegir dades fixes (Read Committed), que prohibeix llegir dades modificades per la transacció. Si la transacció A ha canviat un determinat conjunt de dades, la transacció B, quan accedeix a aquestes dades, es veu obligada a esperar que la transacció A es completi.
Lectura repetible
Problema amb les actualitzacions perdudes. T1 desa els canvis a sobre dels canvis de T2.
Exemple. El valor del saldo inicial és de $ 0 i dues transaccions simultàniament reomplen el saldo. T1 i T2 llegeixen un saldo de $0. A continuació, T2 afegeix $ 200 a $ 0 i desa el resultat. T1 afegeix $ 100 a $ 0 i guarda el resultat. El resultat final és de 100 dòlars en lloc de 300 dòlars.
Problema de lectura irrepetible. Llegir les mateixes dades repetidament retorna valors diferents.
Exemple. T1 llegeix un valor de saldo de 0 $. A continuació, T2 afegeix 50 dòlars al saldo i acaba. T1 torna a llegir les dades i troba una discrepància amb el resultat anterior.
La lectura repetible garanteix que una segona lectura retornarà el mateix resultat. Les dades llegides per una transacció no es poden canviar en altres fins que no s'hagi completat. Si la transacció A ha llegit un determinat conjunt de dades, aleshores la transacció B, quan accedeix a aquestes dades, es veu obligada a esperar que la transacció A es completi.
Lectura ordenada (serialitzable)
Problema de lectura fantasma. Dues consultes que seleccionen dades en funció d'una determinada condició retornen valors diferents.
Exemple. T1 sol·licita el nombre de tots els usuaris el saldo dels quals és superior a 0 $ però inferior a 100 $. T2 dedueix 1 $ d'un usuari amb un saldo de 101 $. T1 torna a emetre la sol·licitud.
Lectura ordenada (serialitzable). Les transaccions s'executen de manera completament seqüencial. Queda prohibit actualitzar o afegir registres que entren dins dels termes de la sol·licitud. Si la transacció A ha sol·licitat dades de tota la taula, tota la taula es congela per a altres transaccions fins que es completi la transacció A.
Programador
Estableix l'ordre en què s'han de realitzar les operacions durant les transaccions paral·leles.
Proporciona un nivell d'aïllament específic. Si el resultat de les operacions no depèn del seu ordre, llavors aquestes operacions són commutatives (permutables). Les operacions de lectura i les operacions sobre diferents dades són commutatives. Les operacions de lectura-escriptura i escriptura-escriptura no són commutatives. La tasca del planificador és intercalar les operacions realitzades per transaccions paral·leles de manera que el resultat de l'execució sigui equivalent a l'execució seqüencial de transaccions.
Mecanismes de control de treballs paral·lels (Concurrency Control)
L'optimista es basa en detectar i resoldre conflictes, el pessimista es basa en evitar que sorgeixin conflictes.
En l'enfocament optimista, diversos usuaris tenen còpies de les dades a la seva disposició. La primera persona que completa l'edició desa els canvis, mentre que les altres han de combinar-los. Un algorisme optimista permet que es produeixi un conflicte, però el sistema s'ha de recuperar del conflicte.
Amb un enfocament pessimista, el primer usuari que captura les dades evita que altres les rebin. Si els conflictes són rars, és aconsellable triar l'estratègia optimista, ja que proporciona un nivell més alt de concurrència.
Bloqueig
Si una transacció té dades bloquejades, les altres transaccions hauran d'esperar fins que es desbloquegi en accedir a les dades.
Un bloc es pot superposar a una base de dades, taula, fila o atribut. El bloqueig compartit es pot imposar a les mateixes dades per diverses transaccions, permet llegir totes les transaccions (inclòs la que l'ha imposat), prohibeix la modificació i la captura exclusiva. El bloqueig exclusiu només es pot imposar per una transacció, permet qualsevol acció de la transacció imponent, prohibeix qualsevol acció d'altres.
Un bloqueig és una situació en què les transaccions acaben en un estat pendent que dura indefinidament.
Exemple. La primera transacció espera que les dades capturades pel segon s'alliberin, mentre que la segona espera que les dades capturades pel primer s'alliberin.
Una solució optimista al problema de bloqueig permet que es produeixi el bloqueig, però després recupera el sistema recuperant una de les transaccions implicades en el bloqueig.
Els punts morts es cerquen a intervals determinats. Un dels mètodes de detecció és el temps, és a dir, considerar que s'ha produït un bloqueig si la transacció triga massa a completar-se. Quan es troba un bloqueig, una de les transaccions es torna enrere, permetent que es completin altres transaccions implicades en el bloqueig. L'elecció de la víctima es pot basar en el valor de les transaccions o la seva antiguitat (esquemes Wait-Die i Wound-wait).
Cada transacció T s'assigna una marca de temps TS que conté l'hora d'inici de la transacció.
Espera-Mori.
Si TS(Ti) < TS(Tj), Llavors Ti espera, en cas contrari Ti torna enrere i torna a començar amb la mateixa marca de temps.
Si una transacció jove ha adquirit un recurs i una transacció més antiga sol·licita el mateix recurs, llavors la transacció anterior pot esperar. Si una transacció més antiga ha adquirit un recurs, es revertirà la transacció més jove que sol·licita aquest recurs.
Ferida-espera.
Si TS(Ti) < TS(Tj), Llavors Tj torna enrere i torna a començar amb la mateixa marca de temps, en cas contrari Ti esperant.
Si una transacció més jove ha adquirit un recurs i una transacció més antiga sol·licita el mateix recurs, es revertirà la transacció més jove. Si una transacció més antiga ha adquirit un recurs, la transacció més jove que sol·licita aquest recurs pot esperar. La selecció de víctimes basada en la precedència evita els bloquejos, però desfer les transaccions que no estan bloquejades. El problema és que les transaccions es poden revertir moltes vegades perquè... una transacció més antiga pot mantenir el recurs durant molt de temps.
Una solució pessimista al problema de bloqueig no permet que una transacció comenci a executar-se si hi ha el risc d'un bloqueig.
Per detectar un bloqueig, es construeix un gràfic (gràfic d'espera, gràfic d'espera), els vèrtexs del qual són transaccions i les vores es dirigeixen des de les transaccions que esperen l'alliberament de dades a la transacció que ha capturat aquestes dades. Es considera que s'ha produït un bloqueig si el gràfic té un bucle. Construir un gràfic d'espera, especialment en bases de dades distribuïdes, és un procediment car.
Bloqueig en dues fases: evita els bloquejos en capturar tots els recursos utilitzats per una transacció al començament de la transacció i alliberant-los al final
Totes les operacions de bloqueig han de precedir la primera de desbloqueig. Té dues fases: la fase de creixement, durant la qual s'acumulen les pinces, i la fase de reducció, durant la qual s'alliberen les pinces. Si és impossible capturar un dels recursos, la transacció torna a començar. És possible que una transacció no pugui adquirir els recursos necessaris, per exemple, si diverses transaccions competeixen pels mateixos recursos.
Una confirmació en dues fases garanteix que la confirmació s'executa a totes les rèpliques de la base de dades
Cada base de dades introdueix informació sobre les dades que es canviaran al registre i respon al coordinador OK (Fase de votació). Després que tothom hagi respost d'acord, el coordinador envia un senyal obligant a tothom a comprometre's. Després de comprometre's, els servidors responen bé si almenys un no respon bé, aleshores el coordinador envia un senyal per cancel·lar els canvis a tots els servidors (Fase de finalització).
Mètode de marca de temps
Una transacció antiga es revertirà quan s'intenta accedir a les dades implicades per una transacció més jove
A cada transacció se li assigna una marca de temps TS corresponent a l'hora d'inici de l'execució. Si Ti més vella Tj, Llavors TS(Ti) < TS(Tj).
Quan es recupera una transacció, se li assigna una marca de temps nova. Cada objecte de dades Q implicats en la transacció està marcat amb dues etiquetes. W-TS(Q) — marca de temps de la transacció més jove que ha completat amb èxit un registre Q. R-TS(Q) — marca de temps de la transacció més jove que ha realitzat un registre de lectura Q.
Quan la transacció T sol·licituds de lectura de dades Q Hi ha dues opcions.
Si TS(T) < W-TS(Q), és a dir, les dades es van actualitzar per una transacció més jove, després la transacció T torna enrere.
Si TS(T) >= W-TS(Q), després es realitza la lectura i R-TS(Q) s'està convertint MAX(R-TS(Q), TS(T)).
Quan la transacció T sol·licita canvis de dades Q Hi ha dues opcions.
Si TS(T) < R-TS(Q), és a dir, les dades ja han estat llegides per una transacció més jove i si es fa un canvi, sorgirà un conflicte. Transacció T torna enrere.
Si TS(T) < W-TS(Q), és a dir, la transacció intenta sobreescriure un valor més nou, la transacció T es retrocedeix. En altres casos, el canvi es porta a terme i W-TS(Q) esdevé igual TS(T).
No es requereix cap construcció costosa de gràfics d'espera. Les transaccions més antigues depenen de les més noves, de manera que no hi ha cicles al gràfic d'espera. No hi ha bloqueigs perquè les transaccions no s'esperen, sinó que es tornen a revertir immediatament. Es poden fer retrocessos en cascada. Si Ti va rodar i Tj He llegit les dades que he canviat Ti, Llavors Tj també hauria de retrocedir. Si al mateix temps Tj ja s'ha comès, llavors hi haurà una violació del principi d'estabilitat.
Una de les solucions per a les reversions en cascada. Una transacció completa totes les operacions d'escriptura al final, i les altres transaccions han d'esperar que aquesta operació es completi. Les transaccions esperen ser compromeses abans de ser llegides.
Regla d'escriptura de Thomas: una variació del mètode de marca de temps en què les dades actualitzades per una transacció més jove no poden ser sobreescrites per una altra de més antiga.
Transacció T sol·licita canvis de dades Q. Si TS(T) < W-TS(Q), és a dir, la transacció intenta sobreescriure un valor més nou, la transacció T no es torna enrere com en el mètode de marca de temps.
Font: www.habr.com