Transacciones
Una transacción es una secuencia de operaciones sobre datos que tiene un principio y un final.
Una transacción es la ejecución secuencial de operaciones de lectura y escritura. El final de una transacción puede ser guardar los cambios (confirmar) o cancelar los cambios (revertir). En relación con una base de datos, una transacción consta de varias solicitudes que se tratan como una sola solicitud.
Las transacciones deben satisfacer las propiedades ACID.
Atomicidad. La transacción se completa por completo o no se completa en absoluto.
Consistencia. Al completar una transacción, no se deben violar las restricciones impuestas a los datos (por ejemplo, restricciones en la base de datos). La coherencia implica que el sistema se transferirá de un estado correcto a otro estado correcto.
Aislamiento. Las transacciones que se ejecutan en paralelo no deben influirse entre sí, por ejemplo, cambiar los datos utilizados por otra transacción. El resultado de ejecutar transacciones paralelas debe ser el mismo que si las transacciones se ejecutaran secuencialmente.
Sostenibilidad. Una vez comprometidos, los cambios no deben perderse.
Registro de transacciones
El registro almacena los cambios realizados por las transacciones, garantiza la atomicidad y la estabilidad de los datos en caso de una falla del sistema.
El registro contiene los valores que tenían los datos antes y después de que la transacción los cambiara. La estrategia de registro de escritura anticipada requiere agregar una entrada de registro sobre los valores anteriores antes del inicio y sobre los valores finales una vez completada la transacción. En caso de una parada repentina del sistema, la base de datos lee el registro en orden inverso y cancela los cambios realizados por las transacciones. Al encontrar una transacción interrumpida, la base de datos la ejecuta y realiza cambios en el registro. Al estar en el estado en el momento de la falla, la base de datos lee el registro en orden directo y devuelve los cambios realizados por las transacciones. De esta forma se preserva la estabilidad de las transacciones que ya se han comprometido y la atomicidad de la transacción interrumpida.
Simplemente volver a ejecutar las transacciones fallidas no es suficiente para la recuperación.
Ejemplo. El usuario tiene $500 en su cuenta y decide retirarlos de un cajero automático. Hay dos transacciones en curso. El primero lee el valor del saldo y, si hay fondos suficientes en el saldo, emite dinero al usuario. El segundo resta la cantidad requerida del saldo. Digamos que el sistema falló y la primera operación falló, pero la segunda sí. En este caso, no podemos volver a emitir dinero al usuario sin devolver el sistema a su estado original con un saldo positivo.
Niveles de aislamiento
Leer comprometido
El problema de la lectura sucia es que una transacción puede leer el resultado intermedio de otra transacción.
Ejemplo. El valor del saldo inicial es $0. T1 agrega $50 a tu saldo. T2 lee el valor del saldo ($50). T1 descarta los cambios y sale. T2 continúa la ejecución con datos de saldo incorrectos.
La solución es leer datos fijos (lectura comprometida), que prohíbe leer datos modificados por la transacción. Si la transacción A ha cambiado un determinado conjunto de datos, entonces la transacción B, al acceder a estos datos, se ve obligada a esperar a que se complete la transacción A.
Lectura repetible
Problema de actualizaciones perdidas. T1 guarda los cambios además de los cambios de T2.
Ejemplo. El valor del saldo inicial es $0 y dos transacciones simultáneamente reponen el saldo. T1 y T2 leen un saldo de $0. Luego, T2 suma $200 a $0 y guarda el resultado. T1 suma $100 a $0 y guarda el resultado. El resultado final es $100 en lugar de $300.
Problema de lectura irrepetible. Leer los mismos datos repetidamente devuelve valores diferentes.
Ejemplo. T1 lee un valor de saldo de $0. Luego, T2 agrega $50 al saldo y finaliza. T1 vuelve a leer los datos y encuentra una discrepancia con el resultado anterior.
La lectura repetible garantiza que una segunda lectura arrojará el mismo resultado. Los datos leídos por una transacción no se pueden cambiar en otras hasta que se complete la transacción. Si la transacción A ha leído un determinado conjunto de datos, entonces la transacción B, al acceder a estos datos, se ve obligada a esperar a que se complete la transacción A.
Lectura ordenada (Serializable)
Problema de lecturas fantasma. Dos consultas que seleccionan datos en función de una determinada condición devuelven valores diferentes.
Ejemplo. T1 solicita el número de todos los usuarios cuyo saldo es mayor que $0 pero menor que $100. T2 deduce $1 de un usuario con un saldo de $101. T1 vuelve a emitir la solicitud.
Lectura ordenada (Serializable). Las transacciones se ejecutan de forma completamente secuencial. Está prohibido actualizar o agregar registros que se encuentren dentro de los términos de la solicitud. Si la transacción A ha solicitado datos de toda la tabla, entonces toda la tabla se congela para otras transacciones hasta que se complete la transacción A.
Programador
Establece el orden en el que se deben realizar las operaciones durante las transacciones paralelas.
Proporciona un nivel específico de aislamiento. Si el resultado de las operaciones no depende de su orden, entonces dichas operaciones son conmutativas (permutables). Las operaciones de lectura y las operaciones con diferentes datos son conmutativas. Las operaciones de lectura-escritura y escritura-escritura no son conmutativas. La tarea del planificador es intercalar operaciones realizadas por transacciones paralelas para que el resultado de la ejecución sea equivalente a la ejecución secuencial de transacciones.
Mecanismos de control de trabajos paralelos (Control de Concurrencia)
El optimista se basa en detectar y resolver conflictos, el pesimista se basa en evitar que surjan conflictos.
En el enfoque optimista, varios usuarios tienen copias de los datos a su disposición. La primera persona que completa la edición guarda los cambios, mientras que las demás deben fusionar los cambios. Un algoritmo optimista permite que ocurra un conflicto, pero el sistema debe recuperarse del conflicto.
Con un enfoque pesimista, el primer usuario que captura los datos impide que otros los reciban. Si los conflictos son raros, es aconsejable elegir la estrategia optimista, ya que proporciona un mayor nivel de concurrencia.
Cierre
Si una transacción tiene datos bloqueados, otras transacciones deben esperar hasta que se desbloqueen para acceder a los datos.
Un bloque se puede superponer en una base de datos, tabla, fila o atributo. El bloqueo compartido se puede imponer a los mismos datos mediante varias transacciones, permite la lectura de todas las transacciones (incluida la que lo impuso), prohíbe la modificación y la captura exclusiva. El bloqueo exclusivo puede ser impuesto solo por una transacción, permite cualquier acción de la transacción imponente y prohíbe cualquier acción de otros.
Un punto muerto es una situación en la que las transacciones terminan en un estado pendiente que dura indefinidamente.
Ejemplo. La primera transacción espera a que se liberen los datos capturados por la segunda, mientras que la segunda espera a que se liberen los datos capturados por la primera.
Una solución optimista al problema del punto muerto permite que se produzca el punto muerto, pero luego recupera el sistema al revertir una de las transacciones involucradas en el punto muerto.
Los puntos muertos se buscan a determinados intervalos. Uno de los métodos de detección es por tiempo, es decir, considerar que se ha producido un punto muerto si la transacción tarda demasiado en completarse. Cuando se encuentra un punto muerto, una de las transacciones se revierte, permitiendo que se completen otras transacciones involucradas en el punto muerto. La elección de la víctima puede basarse en el valor de las transacciones o en su antigüedad (esquemas Wait-Die y Wound-wait).
Cada transacción T se asigna una marca de tiempo TS que contiene la hora de inicio de la transacción.
Espera-muere.
si TS(Ti) < TS(Tj)entonces Ti espera, de lo contrario Ti retrocede y comienza de nuevo con la misma marca de tiempo.
Si una transacción joven ha adquirido un recurso y una transacción más antigua solicita el mismo recurso, entonces la transacción más antigua puede esperar. Si una transacción anterior ha adquirido un recurso, la transacción más reciente que solicita ese recurso se revertirá.
Espera herida.
si TS(Ti) < TS(Tj)entonces Tj retrocede y comienza de nuevo con la misma marca de tiempo; de lo contrario Ti esperando.
Si una transacción más joven ha adquirido un recurso y una transacción más antigua solicita el mismo recurso, entonces la transacción más joven se revertirá. Si una transacción más antigua ha adquirido un recurso, entonces la transacción más joven que solicita ese recurso puede esperar. La selección de víctimas basada en precedencia evita los puntos muertos, pero deshace las transacciones que no están en punto muerto. El problema es que las transacciones se pueden revertir muchas veces porque... una transacción más antigua puede retener el recurso durante mucho tiempo.
Una solución pesimista al problema del punto muerto no permite que una transacción comience a ejecutarse si existe riesgo de que se produzca un punto muerto.
Para detectar un punto muerto, se construye un gráfico (gráfico de espera, gráfico de espera), cuyos vértices son transacciones, y los bordes se dirigen desde las transacciones que esperan la liberación de datos a la transacción que ha capturado estos datos. Se considera que se ha producido un punto muerto si el gráfico tiene un bucle. Construir un gráfico de espera, especialmente en bases de datos distribuidas, es un procedimiento costoso.
Bloqueo de dos fases: evita interbloqueos al apoderarse de todos los recursos utilizados por una transacción al comienzo de la misma y liberarlos al final.
Todas las operaciones de bloqueo deben preceder a la primera de desbloqueo. Tiene dos fases: fase de crecimiento, durante la cual se acumulan los agarres, y fase de contracción, durante la cual se liberan los agarres. Si es imposible capturar uno de los recursos, la transacción comienza de nuevo. Es posible que una transacción no pueda adquirir los recursos necesarios, por ejemplo, si varias transacciones compiten por los mismos recursos.
Una confirmación de dos fases garantiza que la confirmación se ejecute en todas las réplicas de la base de datos.
Cada base de datos ingresa información sobre los datos que se cambiarán en el registro y responde al coordinador OK (Fase de votación). Después de que todos hayan respondido OK, el coordinador envía una señal obligando a todos a comprometerse. Después de confirmar, los servidores responden OK; si al menos uno no responde OK, entonces el coordinador envía una señal para cancelar los cambios a todos los servidores (Fase de finalización).
Método de marca de tiempo
Una transacción anterior se revierte cuando se intenta acceder a los datos involucrados en una transacción más reciente.
A cada transacción se le asigna una marca de tiempo TS correspondiente a la hora de inicio de la ejecución. Si Ti mayores Tjentonces TS(Ti) < TS(Tj).
Cuando se revierte una transacción, se le asigna una nueva marca de tiempo. Cada objeto de datos Q involucrado en la transacción está marcado con dos etiquetas. W-TS(Q) — marca de tiempo de la transacción más reciente que completó con éxito un registro durante Q. R-TS(Q) — marca de tiempo de la transacción más reciente que realizó un registro de lectura en Q.
cuando la transacción T solicitudes para leer datos Q Hay dos opciones.
si TS(T) < W-TS(Q), es decir, los datos fueron actualizados por una transacción más reciente, luego la transacción T retrocede.
si TS(T) >= W-TS(Q), luego se realiza la lectura y R-TS(Q) становится MÁX.(R-TS(Q), TS(T)).
cuando la transacción T solicita cambios de datos Q Hay dos opciones.
si TS(T) < R-TS(Q), es decir, los datos ya han sido leídos por una transacción más joven y si se realiza un cambio, surgirá un conflicto. Transacción T retrocede.
si TS(T) < W-TS(Q), es decir, la transacción intenta sobrescribir un valor más nuevo, la transacción T se revierte. En otros casos, el cambio se lleva a cabo y W-TS(Q) se vuelve igual TS(T).
No se requiere una costosa construcción de gráficos de espera. Las transacciones más antiguas dependen de las más nuevas, por lo que no hay ciclos en el gráfico de espera. No hay puntos muertos porque las transacciones no se esperan sino que se revierten inmediatamente. Es posible realizar reversiones en cascada. Si Ti rodado y Tj Leí los datos que cambié. Tientonces Tj también debería retroceder. Si al mismo tiempo Tj ya se ha cometido, entonces habrá una violación del principio de estabilidad.
Una de las soluciones a las reversiones en cascada. Una transacción completa todas las operaciones de escritura al final y otras transacciones deben esperar a que se complete esa operación. Las transacciones esperan a ser confirmadas antes de ser leídas.
Regla de escritura de Thomas: una variación del método de marca de tiempo en el que se prohíbe que los datos actualizados por una transacción más reciente sean sobrescritos por una más antigua.
transacción T solicita cambios de datos Q. Si TS(T) < W-TS(Q), es decir, la transacción intenta sobrescribir un valor más nuevo, la transacción T no se revierte como en el método de marca de tiempo.
Fuente: habr.com