Transaccións
Unha transacción é unha secuencia de operacións sobre datos que ten un principio e un final.
Unha transacción é a execución secuencial de operacións de lectura e escritura. O final dunha transacción pode ser gardar os cambios (commit) ou cancelar os cambios (rollback). En relación cunha base de datos, unha transacción consta de varias solicitudes que se tratan como unha única solicitude.
As transaccións deben cumprir as propiedades ACID
Atomicidade. A transacción complétase completamente ou non se completa.
Consistencia. Ao completar unha transacción, non se deben violar as restricións impostas aos datos (por exemplo, as restricións na base de datos). A coherencia implica que o sistema será transferido dun estado correcto a outro estado correcto.
Illamento. As transaccións que se executan en paralelo non deben influír entre si, por exemplo, cambiar os datos utilizados por outra transacción. O resultado da execución de transaccións paralelas debe ser o mesmo que se as transaccións se executasen secuencialmente.
Sostibilidade. Unha vez comprometidos, os cambios non deben perderse.
Rexistro de transaccións
O rexistro almacena os cambios realizados polas transaccións, garante a atomicidade e a estabilidade dos datos en caso de fallo do sistema
O rexistro contén os valores que tiñan os datos antes e despois de ser modificados pola transacción. A estratexia de rexistro de escritura anticipada require engadir unha entrada de rexistro sobre os valores anteriores antes do inicio e sobre os valores finais despois de que se complete a transacción. En caso de parada repentina do sistema, a base de datos le o rexistro en orde inversa e cancela os cambios realizados polas transaccións. Despois de atopar unha transacción interrompida, a base de datos execútaa e fai cambios ao respecto no rexistro. Estando no estado no momento do fallo, a base de datos le o rexistro na orde de avance e devolve os cambios realizados polas transaccións. Deste xeito, consérvase a estabilidade das transaccións que xa foron cometidas e a atomicidade da transacción interrompida.
Simplemente volver executar transaccións erradas non é suficiente para a recuperación.
Exemplo. O usuario ten 500 dólares na súa conta e o usuario decide retiralos dun caixeiro automático. Dúas transaccións están en curso. O primeiro le o valor do saldo e, se hai fondos suficientes no saldo, emite diñeiro ao usuario. O segundo resta a cantidade necesaria do saldo. Digamos que o sistema fallou e fallou a primeira operación, pero a segunda. Neste caso, non podemos volver a emitir diñeiro ao usuario sen devolver o sistema ao seu estado orixinal cun saldo positivo.
Niveis de illamento
Ler Comprometido
O problema de lectura sucia é que unha transacción pode ler o resultado intermedio doutra transacción.
Exemplo. O valor do saldo inicial é de $ 0. T1 engade $50 ao teu saldo. T2 le o valor do saldo ($50). T1 descarta os cambios e sae. T2 continúa a execución con datos de saldo incorrectos.
A solución é ler datos fixos (Read Committed), que prohibe ler os datos modificados pola transacción. Se a transacción A cambiou un determinado conxunto de datos, entón a transacción B, ao acceder a estes datos, vese obrigada a esperar a que se complete a transacción A.
Lectura repetible
Problema con actualizacións perdidas. T1 garda os cambios enriba dos cambios de T2.
Exemplo. O valor do saldo inicial é de $ 0 e dúas transaccións simultaneamente repoñen o saldo. T1 e T2 len un saldo de $0. A continuación, T2 engade $200 a $0 e garda o resultado. T1 engade $100 a $0 e garda o resultado. O resultado final é de 100 dólares en lugar de 300 dólares.
Problema de lectura irrepetible. A lectura dos mesmos datos repetidamente devolve valores diferentes.
Exemplo. T1 le un valor de saldo de $ 0. A continuación, T2 engade $50 ao saldo e remata. T1 le os datos de novo e atopa unha discrepancia co resultado anterior.
Lectura repetible garante que unha segunda lectura devolverá o mesmo resultado. Os datos lidos por unha transacción non se poden cambiar noutras ata que se complete. Se a transacción A leu un determinado conxunto de datos, entón a transacción B, ao acceder a estes datos, vese obrigada a esperar a que se complete a transacción A.
Lectura ordenada (serializable)
Problema con Phantom Reads. Dúas consultas que seleccionan datos en función dunha determinada condición devolven valores diferentes.
Exemplo. T1 solicita o número de todos os usuarios cuxo saldo sexa superior a $0 pero inferior a $100. T2 desconta $1 dun usuario cun saldo de $101. T1 reemite a solicitude.
Lectura ordenada (serializable). As transaccións execútanse como completamente secuenciais. Queda prohibido actualizar ou engadir rexistros que entren dentro dos termos da solicitude. Se a transacción A solicitou datos de toda a táboa, a táboa enteira quedará conxelada para outras transaccións ata que se complete a transacción A.
Programador
Establece a orde na que se deben realizar as operacións durante as transaccións paralelas.
Proporciona un nivel específico de illamento. Se o resultado das operacións non depende da súa orde, entón tales operacións son conmutativas (permutables). As operacións de lectura e operacións sobre diferentes datos son conmutativas. As operacións de lectura-escritura e escritura-escritura non son conmutativas. A tarefa do planificador é intercalar as operacións realizadas por transaccións paralelas para que o resultado da execución sexa equivalente á execución secuencial das transaccións.
Mecanismos para controlar traballos paralelos (Concurrency Control)
O optimista baséase en detectar e resolver conflitos, o pesimista baséase en evitar que xurdan conflitos.
No enfoque optimista, varios usuarios teñen copias dos datos á súa disposición. A primeira persoa en completar a edición garda os cambios, mentres que os demais deben fusionar os cambios. Un algoritmo optimista permite que se produza un conflito, pero o sistema debe recuperarse do conflito.
Cun enfoque pesimista, o primeiro usuario que captura os datos impide que outros reciban os datos. Se os conflitos son raros, é prudente escoller a estratexia optimista, xa que proporciona un maior nivel de concorrencia.
Bloqueo
Se unha transacción ten datos bloqueados, outras transaccións deben esperar ata que se desbloquee ao acceder aos datos.
Un bloque pódese superpoñer nunha base de datos, táboa, fila ou atributo. O bloqueo compartido pode ser imposto sobre os mesmos datos mediante varias transaccións, permite a lectura de todas as transaccións (incluída a que o impuxo), prohíbe a modificación e a captura exclusiva. O bloqueo exclusivo só pode ser imposto por unha transacción, permite calquera acción da transacción impoñente, prohíbe calquera acción doutros.
Un punto morto é unha situación na que as transaccións acaban nun estado pendente que dura indefinidamente.
Exemplo. A primeira transacción agarda a que se liberen os datos capturados polo segundo, mentres que a segunda agarda a que se liberen os datos capturados polo primeiro.
Unha solución optimista para o problema do punto morto permite que se produza, pero despois recupera o sistema recuperando unha das transaccións implicadas no punto morto.
Búscanse puntos mortos a determinados intervalos. Un dos métodos de detección é polo tempo, é dicir, considerar que se produciu un punto morto se a transacción tarda demasiado en completarse. Cando se atopa un punto morto, unha das transaccións retírase, permitindo que se completen outras transaccións implicadas no punto morto. A elección da vítima pódese basear no valor das transaccións ou na súa antigüidade (esquemas Wait-Die e Wound-wait).
Cada transacción T asígnase unha marca de tempo TS que contén a hora de inicio da transacción.
Espera-Morrer.
Se TS (Ti) < TS (Tj), Entón Ti agarda, se non Ti retrocede e comeza de novo coa mesma marca de tempo.
Se unha transacción nova adquiriu un recurso e unha transacción máis antiga solicita o mesmo recurso, entón a transacción máis antiga pode esperar. Se unha transacción máis antiga adquiriu un recurso, a transacción máis nova que solicitou ese recurso volverase anular.
Ferida-espera.
Se TS (Ti) < TS (Tj), Entón Tj retrocede e comeza de novo coa mesma marca de tempo, se non Ti agardando.
Se unha transacción máis nova adquiriu un recurso e unha transacción máis antiga solicita o mesmo recurso, entón a transacción máis nova será revertida. Se unha transacción máis antiga adquiriu un recurso, a transacción máis nova que solicita ese recurso pode esperar. A selección de vítimas baseada na precedencia evita os bloqueos, pero fai retroceder as transaccións que non estean bloqueadas. O problema é que as transaccións poden revertirse moitas veces porque... unha transacción máis antiga pode manter o recurso durante moito tempo.
Unha solución pesimista para o problema do punto morto non permite que unha transacción comece a executarse se existe o risco de que se produza un punto morto.
Para detectar un punto morto, constrúese un gráfico (gráfico de espera, gráfico de espera), cuxos vértices son transaccións e os bordos diríxense desde as transaccións que agardan a liberación de datos á transacción que capturou estes datos. Considérase que se produciu un punto morto se o gráfico ten un bucle. Construír un gráfico de espera, especialmente en bases de datos distribuídas, é un procedemento caro.
Bloqueo en dúas fases: evita os bloqueos ao apoderarse de todos os recursos utilizados por unha transacción ao comezo da transacción e liberándoos ao final.
Todas as operacións de bloqueo deben preceder á primeira de desbloqueo. Ten dúas fases: a fase de crecemento, durante a cal se acumulan as pinzas, e a fase de encollemento, durante a cal se soltan as pinzas. Se é imposible capturar un dos recursos, a transacción comeza de novo. É posible que unha transacción non poida adquirir os recursos necesarios, por exemplo, se varias transaccións compiten polos mesmos recursos.
Unha confirmación en dúas fases garante que a confirmación se execute en todas as réplicas da base de datos
Cada base de datos introduce información sobre os datos que se modificarán no rexistro e responde ao coordinador OK (Fase de Votación). Despois de que todos responderon OK, o coordinador envía un sinal obrigando a todos a comprometerse. Despois de cometer, os servidores responden OK; se polo menos un non responde OK, entón o coordinador envía un sinal para cancelar os cambios a todos os servidores (Fase de finalización).
Método de marca de tempo
Unha transacción máis antiga revélase ao tentar acceder aos datos implicados nunha transacción máis nova
Cada transacción ten asignada unha marca de tempo TS correspondente á hora de inicio da execución. Se Ti ao longo Tj, Entón TS (Ti) < TS (Tj).
Cando se retrotrae unha transacción, asígnaselle unha nova marca de tempo. Cada obxecto de datos Q implicados na transacción está marcado con dúas etiquetas. W-TS(Q) — marca de tempo da transacción máis nova que completou correctamente un rexistro Q. R-TS(Q) — marca de tempo da transacción máis nova na que se realizou un rexistro de lectura Q.
Cando a transacción T solicitudes para ler datos Q Hai dúas opcións.
Se TS(T) < W-TS(Q), é dicir, os datos foron actualizados por unha transacción máis nova, entón a transacción T retrocede.
Se TS(T) >= W-TS(Q), a continuación realízase a lectura e R-TS(Q) está facendo MAX(R-TS(Q), TS(T)).
Cando a transacción T solicita cambios de datos Q Hai dúas opcións.
Se TS(T) < R-TS(Q), é dicir, os datos xa foron lidos por unha transacción máis nova e se se fai un cambio, xurdirá un conflito. Transacción T retrocede.
Se TS(T) < W-TS(Q), é dicir, a transacción tenta sobrescribir un valor máis novo, a transacción T retrovólvese. Noutros casos, o cambio realízase e W-TS(Q) faise igual TS(T).
Non é necesario construír un gráfico de espera caro. As transaccións máis antigas dependen das máis novas, polo que non hai ciclos no gráfico de espera. Non hai bloqueos porque as transaccións non se esperan, senón que se retrotraen inmediatamente. Son posibles as recuperacións en cascada. Se Ti rolou e Tj Lin os datos que cambiei Ti, Entón Tj tamén debería retroceder. Se ao mesmo tempo Tj xa se cometeu, entón haberá unha violación do principio de estabilidade.
Unha das solucións aos retrocesos en cascada. Unha transacción completa todas as operacións de escritura ao final e outras transaccións deben esperar a que se complete. As transaccións agardan a ser confirmadas antes de ser lidas.
Regra de escritura de Thomas: unha variación do método de marca de tempo na que se prohíbe que os datos actualizados por unha transacción máis nova sexan sobrescritos por outra máis antiga.
Transacción T solicita cambios de datos Q. Se TS(T) < W-TS(Q), é dicir, a transacción tenta sobrescribir un valor máis novo, a transacción T non se retrotrae como no método de marca de tempo.
Fonte: www.habr.com