#21 Protocolos REDO/UNDO y el protocolo 2PC de confiabilidad distribuida

Protocolos REDO/UNDO.
El registro de la base de datos contiene información que es utilizada por el proceso de recuperación para restablecer la base de datos a un estado consistente. Esta información puede incluir entre otras cosas:
el identificador de la transacción,
el tipo de operación realizada,
los datos accesados por la transacción para realizar la acción,
el valor anterior del dato (imagen anterior), y
el valor nuevo del dato (imagen nueva).
Considere el escenario mostrado en la Figura de abajo. El DBMS inicia la ejecución en el tiempo 0 y en el tiempo t se presenta una falla del sistema. Durante el periodo [0, t] ocurren dos transacciones, T1 y T2. T1 ha sido concluida (ha realizado su commit) pero T2 no pudo ser concluida.
La propiedad de durabilidad requiere que los efectos de T1 sean reflejados en la base de datos estable. De forma similar, la propiedad de atomicidad requiere que la base de datos estable no contenga alguno de los efectos de T2.

Ejemplo de una falla del sistema.
A pesar que T1 haya sido terminada, puede suceder que el buffer correspondiente a la página de la base de datos modificada no haya sido escrito a la base de datos estable. Así, para este caso la recuperación tiene que volver a realizar los cambios hechos por T1. A esta operación se le conoce como REDO y se presenta en la Figura de abajo.
La operación de REDO utiliza la información del registro de la base de datos y realiza de nuevo las acciones que pudieron haber sido realizadas antes de la falla. La operación REDO genera una nueva imagen.


Operación REDO.
Por otra parte, es posible que el administrador del buffer haya realizado la escritura en la base de datos estable de algunas de las páginas de la base de datos volátil correspondientes a la transacción T2.
Así, la información de recuperación debe incluir datos suficientes para permitir deshacer ciertas actualizaciones en el nuevo estado de la base de datos y regrasarla al estado anterior. A esta operación se le conoce como UNDO y se muestra en la Figura de abajo. La operación UNDO restablece un dato a su imagen anterior utilizando la información del registro de la base de datos.



Operación UNDO.
De forma similar a la base de datos volátil, el registro de la base de datos se mantiene en memoria principal (llamada los buffers de registro) y se escribe al almacenamiento estable (llamadoregistro estable). Las páginas de registro se pueden escribir en el registro estable de dos formas: síncrona o asíncrona. En forma síncrona, también llamada un registro forzado, la adición de cada dato en el registro requiere que la página del registro correspondiente se mueva al almacenamiento estable. De manera asíncrona, las páginas del registro se mueven en forma periódica o cuando los buffers se llenan.

Protocolo 2PC de confiabilidad distribuida.
El protocolo 2PC básico un agente (un agente-DTM en el modelo) con un rol especial. Este es llamado el coordinador; todos los demás agentes que deben hacer commit a la vez son llamados participantes.
El coordinador es responsable de tomar la decisión de llevar a cabo un commit o abort finalmente. Cada participante corresponde a una subtransacción la cual ha realizado alguna acción de escritura en su base de datos local.
Se puede asumir que cada participante está en un sitio diferente. Aun si un participante y el coordinador se encuentran en el mismo sitio, se sigue el protocolo como si estuvieran en distintos sitios.
La idea básica del 2PC es determinar una decisión única para todos los participantes con respecto a hacer commit o abort en todas las subtransacciones locales.
El protocolo consiste en dos fases:

• La primera fase tiene como objetivo alcanzar una decisión común,
• La meta de la segunda fase es implementar esta decisión.

El protocolo procede como sigue:
Fase uno:
• El coordinador escribe “prepare” en la bitácora y envía un mensaje donde pregunta a todos los participantes si preparan el commit (PREPARE).
• Cada participante escribe “ready” (y registra las subtransacciones) en su propia bitácora si está listo o “abort” de lo contrario.
• Cada participante responde con un mensaje READY o ABORT al coordinador.
• El coordinador decide el commit o abort en la transacción como un resultado de las respuestas que ha recibido de los participantes. Si todos respondieron READY, decide hacer un commit. Si alguno ha respondido ABORT o no ha respondido en un intervalo de tiempo determinado se aborta la transacción.
Fase dos:
• El coordinador registra la decisión tomada en almacenamiento estable; es decir, escribe “global_commit” o “global_abort” en la bitácora.
• El coordinador envía mensaje de COMMIT o ABORT según sea el caso para su ejecución.
• Todos los participantes escriben un commit o abort en la bitácora basados en el mensaje recibido del coordinador (desde este momento el procedimiento de recuperación es capaz de asegurar que el efecto de la subtransacción no será perdido).
Finalmente:

• Todos los participantes envían un mensaje de acuse de recibo (ACK) al coordinador, y ejecutan las acciones requeridas para terminar (commit) o abortar (abort) la subtransacción.
• Cuando el coordinador ha recibido un mensaje ACK de todos los participantes, escribe un nuevo tipo de registro en la bitácora, llamado un registro “completo”.

#20 Conceptos básicos de confiabilidad

#19 Disciplinas del Interbloqueo

#18 Algoritmos de control de concurrencia

Basados en Bloqueos
En los algoritmos basados en candados, las transacciones indican sus intenciones solicitando candados al despachador (llamado el administrador de candados). Los candados son de lectura (rl), también llamados compartidos, o de escritura (wl), también llamados exclusivos. Como se aprecia en la tabla siguiente, los candados de lectura presentan conflictos con los candados de escritura, dado que las operaciones de lectura y escritura son incompatibles.

En sistemas basados en candados, el despachador es un administrador de candados (LM). El administrador de transacciones le pasa al administrador de candados la operación sobre la base de datos (lectura o escritura) e información asociada, como por ejemplo el elemento de datos que es accesado y el identificador de la transacción que está enviando la operación a la base de datos. El administrador de candados verifica si el elemento de datos que se quiere accesar ya ha sido bloqueado por un candado. Si candado solicitado es incompatible con el candado con que el dato está bloqueado, entonces, la transacción solicitante es retrasada. De otra forma, el candado se define sobre el dato en el modo deseado y la operación a la base de datos es transferida al procesador de datos. El administrador de transacciones es informado luego sobre el resultado de la operación. La terminación de una transacción libera todos los candados y se puede iniciar otra transacción que estaba esperando el acceso al mismo dato.


Basados en estampas de tiempo
A diferencia de los algoritmos basados en candados, los algoritmos basados en estampas de tiempo no pretenden mantener la seriabilidad por exclusión mutua. En lugar de eso, ellos seleccionan un orden de serialización a priori y ejecutan las transacciones de acuerdo a ellas. Para establecer este ordenamiento, el administrador de transacciones le asigna a cada transacción Ti una estampa de tiempo única ts (Ti ) cuando ésta inicia. Una estampa de tiempo es un identificador simple que sirve para identificar cada transacción de manera única. Otra propiedad de las estampas de tiempo es la monoticidad , esto es, dos estampas de tiempo generadas por el mismo administrador de transacciones deben ser monotonicamente crecientes. Así, las estampas de tiempo son valores derivados de un dominio totalmente ordenado.
Existen varias formas en que las estampas de tiempo se pueden asignar. Un método es usar un contador global monotonicamente creciente. Sin embargo, el mantenimiento de contadores globales es un problema en sistemas distribuidos. Por lo tanto, es preferible que cada nodo asigne de manera autónoma las estampas de tiempos basándose en un contador local. Para obtener la unicidad, cada nodo le agrega al contador su propio identificador. Así, la estampa de tiempo es un par de la forma


<contador local ,identificador de nodo >


Note que el identificador de nodo se agrega en la posición menos significativa, de manera que, éste sirve solo en el caso en que dos nodos diferentes le asignen el mismo contador local a dos transacciones diferentes. El administrador de transacciones asigna también una estampa de tiempo a todas las operaciones solicitadas por una transacción. Más aún, a cada elemento de datos x se le asigna una estampa de tiempo de escritura, wts (x ), y una estampa de tiempo de lectura ,rts (x ); sus valores indican la estampa de tiempo más grande para cualquier lectura y escritura de x , respectivamente.












Pruebas de validación optimistas

#17 Niveles de aislamineto, COMMIT y ROLLBACK

https://onedrive.live.com/?cid=2B362BDAC7D792D5&id=2B362BDAC7D792D5%21644
Niveles de aislamiento

#17 Los mecanismos de control de transacciones para una BDD

Una transacción de una sola instancia de Motor de base de datos que abarque dos o más bases de datos es, de hecho, una transacción distribuida. La instancia administra la transacción distribuida internamente; para el usuario funciona como una transacción local.

En la aplicación, una transacción distribuida se administra de forma muy parecida a una transacción local. Al final de la transacción, la aplicación pide que se confirme o se revierta la transacción. El administrador de transacciones debe administrar una confirmación distribuida de forma diferente para reducir al mínimo el riesgo de que, si se produce un error en la red, algunos administradores de recursos realicen confirmaciones mientras los demás revierten la transacción. Esto se consigue mediante la administración del proceso de confirmación en dos fases (la fase de preparación y la fase de confirmación), que se conoce como confirmación en dos fases (2PC).

Fase de preparación
Cuando el administrador de transacciones recibe una solicitud de confirmación, envía un comando de preparación a todos los administradores de recursos implicados en la transacción. Cada administrador de recursos hace lo necesario para que la transacción sea duradera y todos los búferes que contienen imágenes del registro de la transacción se pasan a disco. A medida que cada administrador de recursos completa la fase de preparación, notifica si la preparación ha tenido éxito o no al administrador de transacciones.

Fase de confirmación
Si el administrador de transacciones recibe la notificación de que todas las preparaciones son correctas por parte de todos los administradores de recursos, envía comandos de confirmación a cada administrador de recursos. A continuación, los administradores de recursos pueden completar la confirmación. Si todos los administradores de recursos indican que la confirmación ha sido correcta, el administrador de transacciones envía una notificación de éxito a la aplicación. Si algún administrador de recursos informó de un error al realizar la preparación, el administrador de transacciones envía un comando para revertir la transacción a cada administrador de recursos e indica a la aplicación que se ha producido un error de confirmación.

Requiere:
Existe un agente raíz que inicia toda la transacción, así que cuando el usuario requiere la ejecución de una aplicación distribuida el agente raíz es iniciado; el sitio del agente raíz es llamado el sitio origen de la transacción.
El agente raíz tiene la responsabilidad de asegurar BEGIN-TRANSACTION, COMMIT O ROLLBACK de toda la transacción distribuida.

Recuperación de transacciones distribuidas

• Para realizar la recuperación de transacción distribuidas se asume que cada sitio tiene su propio manejador de transacción local (LTM).
• Cada agente utiliza de manera local las primitivas asociadas a sus transacciones. Podemos llamar a los agentes subtransacciones, lo cual origina distinguir las primitivas BEGIN-TRANSACTION, COMMIT Y ROLLBACK asociado a la transacción distribuida de la primitivas locales utilizada por
• cada agente en LTM; para poder distinguir una de las otras, a las ultimas les llamaremos:
• LOCAL-BEGIN, LOCAL-COMMIT Y LOCALROLLBACK.
• Para propósito del manejador de transacciones distribuidas (DTM), requieren que los LTM se conformen de la siguiente manera:

1. Asegurar la atomicidad de su transacción.
2. Grabar en bitácora por ordenes de la transacción distribuida.

Para asegurar que todas las acciones de una transacción distribuida son ejecutadas o no ejecutadas dos condiciones son necesarias:

• En cada sitio todas las acciones son ejecutadas o ninguna es ejecutada.
• Todos los sitios deberán tomar la misma decisión respecto al COMMIT o ROLLBACK de la transición global.

Estados de una transacción

• Activa: Durante su ejecución Ficheros y bases de datos
• Parcialmente comprometida: Después de ejecutar su última instrucción.
• Fallida: Imposible de continuar su ejecución normal.
• Abortada: Transacción retrocedida y base de datos restaurada al estado anterior a su
ejecución. Se puede reiniciar o cancelar.

Diagrama de estados de una transacción: