Transacciones
Se denomina transacción a una secuencia de operaciones sobre datos que tiene un inicio y un final.
Una transacción es la ejecución secuencial de operaciones de lectura y escritura. El final de la transacción puede ser la confirmación de los cambios (commit) o la reversión de los cambios (rollback). En el contexto de bases de datos, una transacción consiste en varias consultas que se tratan como una única consulta.
Las transacciones deben cumplir con las propiedades ACID.
Atomicidad. La transacción se ejecuta completamente o no se ejecuta en absoluto.
Consistencia. Al finalizar la transacción no se deben violar las restricciones impuestas a los datos (por ejemplo, constraints en bases de datos). La consistencia implica que el sistema debe pasar de un estado correcto a otro estado correcto.
Aislamiento. Las transacciones que se ejecutan en paralelo no deben influir unas en otras, por ejemplo, no deben modificar datos que utiliza otra transacción. El resultado de la ejecución de transacciones en paralelo debe ser el mismo que si las transacciones se ejecutaran secuencialmente.
Durabilidad. Después de la confirmación, los cambios no deben perderse.
Registro de transacciones
El registro guarda los cambios realizados por las transacciones, asegurando la atomicidad y durabilidad de los datos en caso de fallo del sistema.
El registro contiene los valores que los datos tenían antes y después de ser modificados por la transacción. La estrategia de Write-ahead log obliga a añadir al registro información sobre los valores anteriores antes del inicio y sobre los valores finales después de finalizar la transacción. En caso de un paro inesperado del sistema, la base de datos lee el log en orden inverso y revierte los cambios realizados por las transacciones. Al encontrar una transacción interrumpida, la base de datos la ejecuta y registra los cambios realizados. Al estar en el estado en el momento de la falla, la base de datos lee el log en el orden correcto y aplica los cambios realizados por las transacciones. De este modo, se preserva la durabilidad de las transacciones que ya se habían confirmado y la atomicidad de la transacción interrumpida.
La simple repetición de transacciones erróneas no es suficiente para la recuperación.
Ejemplo. El saldo del usuario es de 500$ y el usuario decide retirar ese dinero a través de un cajero automático. Se realizan dos transacciones. La primera lee el valor del saldo y, si hay suficientes fondos, entrega el dinero al usuario. La segunda resta la cantidad necesaria del saldo. Supongamos que hubo una falla en el sistema y la primera operación no se completó, mientras que la segunda sí se ejecutó. En este caso, no podemos volver a entregar dinero al usuario sin restaurar el sistema a su estado inicial con un saldo positivo.
Niveles de aislamiento
Lectura de datos fijos (Read Committed)
El problema de la lectura sucia (Dirty Read) radica en que una transacción puede leer un resultado intermedio de otra transacción.
Ejemplo. El saldo inicial es de 0$. T1 añade 50$ al saldo. T2 lee el saldo (50$). T1 cancela los cambios y finaliza. T2 continúa ejecutándose con datos incorrectos sobre el saldo.
La solución es la lectura de datos fijos (Read Committed), que prohíbe leer datos modificados por una transacción. Si la transacción A ha modificado un conjunto de datos, la transacción B debe esperar a que la transacción A finalice para acceder a esos datos.
Lectura repetible (Repeatable Read)
El problema de las actualizaciones perdidas (Lost Updates). T1 guarda los cambios sobre los cambios de T2.
Ejemplo. El saldo inicial es de 0$ y dos transacciones suman simultáneamente al saldo. T1 y T2 leen un saldo igual a 0$. Luego, T2 suma 200$ a 0$ y guarda el resultado. T1 suma 100$ a 0$ y guarda el resultado. El saldo final es de 100$ en lugar de 300$.
El problema de la lectura no repetible (Unrepeatable read). Volver a leer los mismos datos devuelve valores diferentes.
Ejemplo. T1 lee un saldo de 0$. Luego T2 añade 50$ al saldo y finaliza. T1 vuelve a leer los datos y encuentra una discrepancia con el resultado anterior.
La lectura repetible (Repeatable Read) garantiza que una nueva lectura devolverá el mismo resultado. Los datos leídos por una transacción no se pueden modificar en otras hasta que la transacción se complete. Si la transacción A ha leído un conjunto de datos, la transacción B debe esperar a que finalice la transacción A antes de acceder a esos datos.
Lectura ordenada (Serializable)
El problema de las lecturas fantasma (Phantom Reads). Dos consultas que seleccionan datos según alguna condición devuelven diferentes valores.
Ejemplo. T1 solicita el número total de usuarios cuyo saldo es mayor a 0$ pero menor a 100$. T2 deduce 1$ del saldo de un usuario con 101$. T1 repite la consulta.
Lectura ordenada (Serializable). Las transacciones se ejecutan como si fueran completamente secuenciales. Se prohíbe actualizar y añadir registros que se vean afectados por los criterios de la consulta. Si la transacción A solicita todos los datos de la tabla, entonces la tabla queda bloqueada para las demás transacciones hasta que la transacción A finalice.
Planificador (Scheduler)
Establece el orden en que se deben ejecutar las operaciones en las transacciones que se llevan a cabo en paralelo.
Proporciona el nivel de aislamiento especificado. Si el resultado de las operaciones no depende de su orden, estas operaciones son conmutativas (Permutable). Las operaciones de lectura y las operaciones sobre diferentes datos son conmutativas. Las operaciones de lectura-escritura y escritura-escritura no son conmutativas. La tarea del planificador es alternar las operaciones realizadas por transacciones paralelas para que el resultado sea equivalente a la ejecución secuencial de las transacciones.
Mecanismos de control de tareas en paralelo (Concurrency Control)
Optimista, basado en la detección y resolución de conflictos; pesimista, en prevenir la aparición de conflictos.
Con el enfoque optimista, varios usuarios obtienen copias de los datos. El primero que complete la edición guarda los cambios, mientras que los demás deben fusionar sus cambios. El algoritmo optimista permite que el conflicto ocurra, pero el sistema debe recuperarse después del conflicto.
Con el enfoque pesimista, el primer usuario que captura los datos impide que otros usuarios accedan a ellos. Si los conflictos son raros, tiene sentido elegir la estrategia optimista, ya que proporciona un mayor nivel de paralelismo.
Bloqueo (Locking)
Si una transacción bloquea los datos, las demás transacciones que intenten acceder a esos datos deben esperar a que se desbloqueen.
Un bloque puede aplicarse a una base de datos, tabla, fila o atributo. Un bloqueo compartido (Shared Lock) puede ser impuesto en los mismos datos por varias transacciones, permitiendo a todas las transacciones (incluyendo la que impuso el bloqueo) leer, pero prohibiendo modificaciones y bloqueos exclusivos. Un bloqueo exclusivo (Exclusive Lock) solo puede ser impuesto por una transacción, permitiendo cualquier acción de la transacción que aplicó el bloqueo, pero prohibiendo cualquier acción a las demás.
Se considera un bloqueo mutuo (deadlock) cuando las transacciones quedan en un estado de espera que dura indefinidamente.
Ejemplo. La primera transacción espera la liberación de los datos bloqueados por la segunda, mientras que la segunda espera la liberación de los datos bloqueados por la primera.
Una solución optimista al problema de los bloqueos mutuos permite que se produzca el bloqueo, pero luego restaura el sistema retrocediendo una de las transacciones involucradas en el bloqueo mutuo.
Se realiza una búsqueda de bloqueos mutuos a intervalos regulares. Una forma de detección es a través del tiempo, es decir, considerar que ha ocurrido un bloqueo mutuo si una transacción está en ejecución durante demasiado tiempo. Cuando se encuentra un bloqueo mutuo, una de las transacciones se retrocede, lo que permite que otras transacciones involucradas en el bloqueo mutuo se completen. La selección de la víctima puede basarse en el costo de las transacciones o su antigüedad (esquemas Wait-Die y Wound-wait).
A cada transacción T se le asigna una marca temporal TS que contiene el tiempo de inicio de ejecución de la transacción.
Wait-Die.
Si TS(Ti) < TS(Tj), entonces Ti espera, de lo contrario Ti se retrocede y comienza de nuevo con la misma marca temporal.
Si una transacción joven ha adquirido un recurso, y una más antigua solicita el mismo recurso, entonces se permite que la transacción más antigua espere. Si una transacción más antigua ha adquirido un recurso, entonces la transacción joven que solicita ese recurso será retrocedida.
Wound-wait.
Si TS(Ti) < TS(Tj), entonces Tj se retrocede y comienza de nuevo con la misma marca temporal, de lo contrario Ti espera.
Si una transacción más joven ha capturado un recurso y una transacción más antigua solicita el mismo recurso, la transacción más joven será revertida. Si una transacción más antigua ha capturado el recurso, se permite a la transacción más joven que solicita ese recurso esperar. La elección de la víctima basada en la antigüedad previene la aparición de bloqueos mutuos, pero revierte transacciones que no están en estado de bloqueo mutuo. El problema es que las transacciones pueden ser revertidas varias veces, ya que una transacción más antigua puede retener un recurso durante mucho tiempo.
La solución pesimista al problema de los bloqueos mutuos no permite que la transacción comience su ejecución si existe el riesgo de un bloqueo mutuo.
Para detectar bloqueos mutuos se construye un gráfico (gráfico de espera, wait-for-graph), cuyos nodos son transacciones, y los arcos están dirigidos desde las transacciones que esperan la liberación de datos hacia la transacción que ha capturado esos datos. Se considera que ha ocurrido un bloqueo mutuo si el gráfico tiene ciclos. La construcción del gráfico de espera, especialmente en bases de datos distribuidas, es un procedimiento costoso.
El bloqueo en dos fases es la prevención de bloqueos mutuos mediante la captura de todos los recursos utilizados por la transacción al inicio de la misma y la liberación de estos al final.
Todas las operaciones de bloqueo deben preceder a la primera operación de desbloqueo. Tiene dos fases: la Fase de Crecimiento en la que se acumulan capturas y la Fase de Reducción en la que se liberan capturas. Si no es posible capturar uno de los recursos, la transacción comienza de nuevo. Puede darse la situación en la que una transacción no pueda capturar los recursos requeridos, por ejemplo, si varias transacciones compiten por los mismos recursos.
El compromiso en dos fases asegura la ejecución del compromiso en todas las réplicas de la base de datos.
Cada base de datos registra la información de los datos que serán modificados en un log y responde al coordinador con un OK (Fase de Votación). Después de que todos hayan respondido OK, el coordinador envía una señal que obliga a todos a realizar el compromiso. Después del compromiso, servidores respondan OK; si alguno no respondió OK, el coordinador envía una señal de cancelación de cambios a todos los servidores (Fase de Finalización).
Método de marcas de tiempo.
Una transacción más antigua se revierte al intentar acceder a datos involucrados en una transacción más joven.
A cada transacción se le asigna una marca de tiempo TS que corresponde al momento de inicio de la ejecución. Si Ti es anterior a Tj, entonces TS(Ti) < TS(Tj).
Cuando una transacción se retrocede, se le asigna una nueva marca de tiempo. Cada objeto de datos Q involucrado en la transacción se marca con dos etiquetas. W-TS(Q) — la marca de tiempo de la transacción más reciente que ha realizado una escritura sobre Q. R-TS(Q) — la marca de tiempo de la transacción más reciente que ha realizado una lectura sobre Q.
Cuando la transacción T solicita leer datos Q hay dos posibilidades.
Si TS(T) < W-TS(Q), es decir, si los datos han sido actualizados por una transacción más reciente, entonces la transacción T se retrocede.
Si TS(T) >= W-TS(Q), entonces la lectura se lleva a cabo y R-TS(Q) se convierte en MAX(R-TS(Q), TS(T)).
Cuando la transacción T solicita modificar los datos Q hay dos posibilidades.
Si TS(T) < R-TS(Q), es decir, si los datos ya han sido leídos por una transacción más reciente y si se produce una modificación, se generará un conflicto. La transacción T se retrocede.
Si TS(T) < W-TS(Q), es decir, si la transacción intenta sobrescribir un valor más nuevo, la transacción T se retrocede. En los demás casos, la modificación se realiza y W-TS(Q) se convierte en TS(T).
No se requiere la costosa construcción de un gráfico de espera. Las transacciones más antiguas dependen de las más nuevas, por lo tanto, no hay ciclos en el gráfico de espera. No hay bloqueos mutuos, ya que las transacciones no esperan, sino que se retroceden de inmediato. Pueden ocurrir retrocesos en cascada. Si Ti se retrocedió, y Tj leyó datos que modificó Ti, entonces Tj también debe retroceder. Si en ese momento Tj ya se había confirmado, se violará el principio de consistencia.
Una de las soluciones para los retrocesos en cascada. La transacción realiza todas las operaciones de escritura al final, y las demás transacciones deben esperar a que se complete esta operación. Las transacciones esperan el compromiso antes de leer.
La regla de escritura de Thomas — una variación del método de marcas de tiempo en el que los datos actualizados por una transacción más reciente no pueden ser sobrescritos por una más antigua
La transacción T solicita modificar los datos Q. Si TS(T) < W-TS(Q), es decir, si la transacción intenta sobrescribir un valor más nuevo, la transacción T no se retrocede como en el método de marcas de tiempo.
Fuente: habr.com
