En ciencias de la computación , los algoritmos para la recuperación y el aislamiento que explotan la semántica , o ARIES, es un algoritmo de recuperación diseñado para funcionar con un enfoque de base de datos de robo y sin fuerza ; lo utilizan IBM DB2 , Microsoft SQL Server y muchos otros sistemas de bases de datos . [1] IBM Fellow Dr. C. Mohan es el inventor principal de la familia de algoritmos ARIES. [2]
Tres principios fundamentales se encuentran detrás de ARIES
- Registro de escritura anticipada : cualquier cambio en un objeto se registra primero en el registro , y el registro debe escribirse en un almacenamiento estable antes de que los cambios del objeto se escriban en el disco.
- Historial repetido durante Rehacer : al reiniciar después de un bloqueo, ARIES rastrea las acciones de una base de datos antes del bloqueo y devuelve el sistema al estado exacto en el que estaba antes del bloqueo. Luego deshace las transacciones aún activas en el momento del bloqueo.
- Registro de cambios durante Deshacer : los cambios realizados en la base de datos mientras se deshacen transacciones se registran para garantizar que dicha acción no se repita en caso de reinicios repetidos.
Inicio sesión
El algoritmo ARIES se basa en el registro de todas las operaciones de la base de datos con números de secuencia ascendentes. Por lo general, el archivo de registro resultante se almacena en el llamado "almacenamiento estable", que es un medio de almacenamiento que se supone que sobrevive a fallas y fallas de hardware.
Para recopilar la información necesaria para los registros, se deben mantener dos estructuras de datos : la tabla de páginas sucias (DPT) y la tabla de transacciones (TT).
La tabla de páginas sucias mantiene un registro de todas las páginas que se han modificado y que aún no se han escrito en el disco, y el primer número de secuencia que provocó que esa página se ensucie. La tabla de transacciones contiene todas las transacciones que se están ejecutando actualmente y el número de secuencia de la última entrada de registro que crearon.
Creamos registros de registro del formulario (Número de secuencia, ID de transacción, ID de página, Rehacer, Deshacer, Número de secuencia anterior). Los campos Rehacer y Deshacer conservan información sobre los cambios que guarda este registro y cómo deshacerlos. El número de secuencia anterior es una referencia al registro de registro anterior que se creó para esta transacción. En el caso de una transacción abortada, es posible recorrer el archivo de registro en orden inverso usando los números de secuencia anteriores, deshaciendo todas las acciones tomadas dentro de la transacción específica.
Cada transacción comienza implícitamente con el primer tipo de entrada "Actualización" para el ID de transacción dado y se confirma con la entrada "Fin de registro" (EOL) para la transacción.
Durante una recuperación, o al deshacer las acciones de una transacción abortada, se escribe un tipo especial de registro de registro, el Registro de registro de compensación (CLR), para registrar que la acción ya se ha deshecho. Los CLR tienen el formato (Número de secuencia, ID de transacción, ID de página, Rehacer, Número de secuencia anterior, Número de secuencia de siguiente deshacer). El campo Rehacer contiene la aplicación del campo Deshacer de la acción revertida, y el campo Deshacer se omite porque CLR nunca se revierte.
Recuperación
La recuperación funciona en tres fases. La primera fase, Análisis, calcula toda la información necesaria del archivo de registro. La fase Rehacer restaura la base de datos al estado exacto en el que se produjo el bloqueo, incluidos todos los cambios de transacciones no confirmadas que se estaban ejecutando en ese momento. Luego, la fase Deshacer deshace todos los cambios no confirmados, dejando la base de datos en un estado consistente.
Análisis
Durante la fase de análisis restauramos el DPT y el TT como estaban en el momento del accidente.
Pasamos por el archivo de registro (desde el principio o el último punto de control) y agregamos todas las transacciones para las que encontramos entradas de Comenzar transacción al TT. Siempre que se encuentra una entrada de registro final, se elimina la transacción correspondiente. Por supuesto, también se mantiene el último número de secuencia de cada transacción.
Durante la misma ejecución, también llenamos la tabla de páginas sucias agregando una nueva entrada cada vez que encontramos una página que se modifica y aún no está en el DPT. Sin embargo, esto solo calcula un superconjunto de todas las páginas sucias en el momento del bloqueo, ya que no verificamos el archivo de base de datos real si la página se volvió a escribir en el almacenamiento.
Rehacer
A partir del DPT, podemos calcular el número de secuencia mínimo de una página sucia. A partir de ahí, tenemos que empezar a rehacer las acciones hasta el bloqueo, en caso de que aún no hayan persistido.
Al ejecutar el archivo de registro, verificamos para cada entrada, si la página P modificada en la entrada existe en el DPT. Si no es así, entonces no tenemos que preocuparnos por rehacer esta entrada ya que los datos persisten en el disco. Si la página P existe en la tabla DPT, entonces vemos si el Número de secuencia en el DPT es menor que el Número de secuencia del registro de registro (es decir, si el cambio en el registro es más reciente que la última versión que se mantuvo). Si no es así, no rehacemos la entrada ya que el cambio ya está allí. Si es así, buscamos la página del almacenamiento de la base de datos y verificamos el Número de secuencia almacenado en la página con el Número de secuencia en el registro de registro. Si el primero es más pequeño que el segundo, la página debe escribirse en el disco. Esa verificación es necesaria porque el DPT recuperado es solo un superconjunto conservador de las páginas que realmente necesitan cambios para volver a aplicarse. Por último, cuando todas las comprobaciones anteriores hayan finalizado y hayan fallado, volvemos a aplicar la acción de rehacer y almacenamos el nuevo número de secuencia en la página. También es importante para la recuperación de un bloqueo durante la fase de rehacer, ya que el rehacer no se aplica dos veces a la misma página.
Deshacer
Después de la fase de rehacer, la base de datos refleja el estado exacto en el que se produjo el bloqueo. Sin embargo, los cambios de las transacciones no confirmadas deben deshacerse para restaurar la base de datos a un estado coherente.
Para eso, recorremos el registro hacia atrás para cada transacción en el TT (esas ejecuciones, por supuesto, se pueden combinar en una) utilizando los campos Número de secuencia anterior en los registros. Para cada registro, deshacemos los cambios (usando la información en el campo Deshacer) y escribimos un registro de compensación en el archivo de registro. Si encontramos un registro Comenzar transacción, escribimos un registro Finalizar para esa transacción.
Los registros del registro de compensación permiten la recuperación durante un bloqueo que se produce durante la fase de recuperación. Eso no es tan infrecuente como podría pensarse, ya que es posible que la fase de recuperación tarde bastante. Los CLR se leen durante la fase de análisis y se rehacen durante la fase de rehacer.
Puntos de control
Para evitar volver a escanear todo el archivo de registro durante la fase de análisis, es aconsejable guardar el DPT y el TT con regularidad en el archivo de registro, formando un punto de control. En lugar de tener que recorrer todo el archivo, solo es necesario hacerlo hacia atrás hasta que se encuentre un punto de control. A partir de ese punto, es posible restaurar el DPT y el TT como estaban en el momento del bloqueo leyendo el archivo de registro hacia adelante nuevamente. Entonces es posible proceder como de costumbre con Rehacer y Deshacer.
La forma ingenua de los puntos de control implica bloquear toda la base de datos para evitar cambios en el DPT y el TT durante la creación del punto de control. El registro difuso evita eso al escribir dos registros. Un registro difuso comienza aquí y, después de preparar los datos del punto de control, el punto de control real. Entre los dos registros se pueden crear otros registros de registro. Durante la recuperación es necesario encontrar ambos registros para obtener un punto de control válido.
Referencias
- ^ Mohan, C .; Haderle, Donald; Lindsay, Bruce; Pirahesh, Hamid; Schwarz, Peter (marzo de 1992). "ARIES: un método de recuperación de transacciones que admite el bloqueo de granularidad fina y reversiones parciales mediante el registro de escritura anticipada". Transacciones ACM en sistemas de bases de datos . 17 (1): 94-162. doi : 10.1145 / 128765.128770 .
- ^ "Repetir la historia más allá de ARIES" (PDF) . C. Mohan, Actas de la 25a Conferencia Internacional sobre Bases de Datos Muy Grandes, Edimburgo, Reino Unido, septiembre de 1999.
enlaces externos
- Impacto de la familia ARIES de algoritmos de bloqueo y recuperación - C. Mohan , archivado desde el original el 19 de agosto de 2012 , consultado el 18 de septiembre de 2013