DBMS distribuido - Control de replicación

Este capítulo analiza el control de la replicación, que es necesario para mantener datos consistentes en todos los sitios. Estudiaremos las técnicas de control de la replicación y los algoritmos necesarios para el control de la replicación.

Como se discutió anteriormente, replicationes una técnica utilizada en bases de datos distribuidas para almacenar múltiples copias de una tabla de datos en diferentes sitios. El problema de tener varias copias en varios sitios es la sobrecarga de mantener la coherencia de los datos, especialmente durante las operaciones de actualización.

Para mantener datos mutuamente consistentes en todos los sitios, es necesario adoptar técnicas de control de replicación. Hay dos enfoques para el control de la replicación, a saber:

  • Control de replicación sincrónica
  • Control de replicación asincrónica

Control de replicación sincrónica

En el enfoque de replicación síncrona, la base de datos se sincroniza para que todas las replicaciones siempre tengan el mismo valor. Una transacción que solicita un elemento de datos tendrá acceso al mismo valor en todos los sitios. Para asegurar esta uniformidad, una transacción que actualiza un elemento de datos se expande para que realice la actualización en todas las copias del elemento de datos. Generalmente, el protocolo de compromiso de dos fases se utiliza para este propósito.

Por ejemplo, consideremos una tabla de datos PROJECT (PId, PName, PLocation). Necesitamos ejecutar una transacción T1 que actualice PLocation a 'Mumbai', si PLocation es 'Bombay'. Si no hay réplicas, las operaciones en la transacción T1 serán:

Begin T1: 
   Update PROJECT Set PLocation = 'Mumbai' 
   Where PLocation = 'Bombay'; 
End T1;

Si la tabla de datos tiene dos réplicas en el Sitio A y el Sitio B, T1 necesita generar dos hijos T1A y T1B correspondientes a los dos sitios. La transacción expandida T1 será:

Begin T1: 
   Begin T1A : 
      Update PROJECT Set PLocation = 'Mumbai' 
      Where PLocation = 'Bombay'; 
   End T1A;  
	
   Begin T2A : 
      Update PROJECT Set PLocation = 'Mumbai'
      Where PLocation = 'Bombay'; 
   End T2A; 
	
End T1;

Control de replicación asincrónica

En el enfoque de replicación asincrónica, las réplicas no siempre mantienen el mismo valor. Una o más réplicas pueden almacenar un valor desactualizado y una transacción puede ver los diferentes valores. El proceso de traer todas las réplicas al valor actual se llamasynchronization.

Un método popular de sincronización es el método de almacenamiento y reenvío. En este método, un sitio se designa como sitio principal y los otros sitios son sitios secundarios. El sitio principal siempre contiene valores actualizados. Todas las transacciones ingresan primero al sitio principal. A continuación, estas transacciones se ponen en cola para su aplicación en los sitios secundarios. Los sitios secundarios se actualizan mediante el método de implementación solo cuando se programa una transacción para ejecutarse en ellos.

Algoritmos de control de replicación

Algunos de los algoritmos de control de replicación son:

  • Algoritmo de control de replicación maestro-esclavo.
  • Algoritmo de votación distribuida.
  • Algoritmo de consenso mayoritario.
  • Algoritmo de token circulante.

Algoritmo de control de replicación maestro-esclavo

Hay un sitio maestro y sitios esclavos 'N'. Un algoritmo maestro se ejecuta en el sitio maestro para detectar conflictos. Una copia del algoritmo esclavo se ejecuta en cada sitio esclavo. El algoritmo general se ejecuta en las siguientes dos fases:

  • Transaction acceptance/rejection phase- Cuando una transacción ingresa al monitor de transacciones de un sitio esclavo, el sitio esclavo envía una solicitud al sitio maestro. El sitio principal busca conflictos. Si no hay ningún conflicto, el maestro envía un mensaje "ACK +" al sitio esclavo que luego comienza la fase de solicitud de transacción. De lo contrario, el maestro envía un mensaje "ACK-" al esclavo, que luego rechaza la transacción.

  • Transaction application phase- Al entrar en esta fase, el sitio esclavo donde ha entrado la transacción transmite una solicitud a todos los esclavos para ejecutar la transacción. Al recibir las solicitudes, los esclavos pares ejecutan la transacción y envían un "ACK" al esclavo solicitante al finalizar. Una vez que el esclavo solicitante ha recibido mensajes "ACK" de todos sus pares, envía un mensaje "DONE" al sitio maestro. El maestro entiende que la transacción se ha completado y la elimina de la cola pendiente.

Algoritmo de votación distribuida

Esto comprende 'N' sitios pares, todos los cuales deben "OK" una transacción antes de que comience a ejecutarse. Las siguientes son las dos fases de este algoritmo:

  • Distributed transaction acceptance phase- Cuando una transacción ingresa al administrador de transacciones de un sitio, envía una solicitud de transacción a todos los demás sitios. Al recibir una solicitud, un sitio de pares resuelve los conflictos utilizando reglas de votación basadas en prioridades. Si todos los sitios pares están "bien" con la transacción, el sitio solicitante comienza la fase de solicitud. Si alguno de los sitios pares no “OK” una transacción, el sitio solicitante rechaza la transacción.

  • Distributed transaction application phase- Al entrar en esta fase, el sitio donde ha entrado la transacción, transmite una solicitud a todos los esclavos para ejecutar la transacción. Al recibir las solicitudes, los esclavos pares ejecutan la transacción y envían un mensaje "ACK" al esclavo solicitante al finalizar. Una vez que el esclavo solicitante ha recibido mensajes "ACK" de todos sus pares, le permite al administrador de transacciones saber que la transacción se ha completado.

Algoritmo de consenso mayoritario

Esta es una variación del algoritmo de votación distribuida, donde se permite que una transacción se ejecute cuando la mayoría de los pares "OK" una transacción. Esto se divide en tres fases:

  • Voting phase- Cuando una transacción ingresa al administrador de transacciones de un sitio, envía una solicitud de transacción a todos los demás sitios. Al recibir una solicitud, un sitio de pares prueba los conflictos utilizando reglas de votación y mantiene las transacciones en conflicto, si las hay, en cola pendiente. Luego, envía un mensaje "OK" o "NO OK".

  • Transaction acceptance/rejection phase- Si el sitio solicitante recibe una mayoría "OK" en la transacción, acepta la transacción y transmite "ACEPTAR" a todos los sitios. De lo contrario, transmite "REJECT" a todos los sitios y rechaza la transacción.

  • Transaction application phase- Cuando un sitio similar recibe un mensaje "RECHAZAR", elimina esta transacción de su lista pendiente y reconsidera todas las transacciones diferidas. Cuando un sitio de pares recibe un mensaje "ACEPTAR", aplica la transacción y rechaza todas las transacciones diferidas en la cola pendiente que están en conflicto con esta transacción. Envía un "ACK" al esclavo solicitante al finalizar.

Algoritmo de token circulante

En este enfoque, las transacciones en el sistema se serializan utilizando un token circulante y se ejecutan en consecuencia contra cada réplica de la base de datos. Por tanto, se aceptan todas las transacciones, es decir, no se rechaza ninguna. Esto tiene dos fases:

  • Transaction serialization phase- En esta fase, todas las transacciones están programadas para ejecutarse en un orden de serialización. A cada transacción en cada sitio se le asigna un ticket único de una serie secuencial, que indica el orden de la transacción. Una vez que se ha asignado un ticket a una transacción, se transmite a todos los sitios.

  • Transaction application phase- Cuando un sitio recibe una transacción junto con su ticket, coloca la transacción para su ejecución de acuerdo con su ticket. Una vez que la transacción ha terminado de ejecutarse, este sitio transmite un mensaje apropiado. Una transacción finaliza cuando ha completado la ejecución en todos los sitios.