DBMS distribuito - Controllo della replica

Questo capitolo esamina il controllo della replica, necessario per mantenere dati coerenti in tutti i siti. Studieremo le tecniche di controllo della replicazione e gli algoritmi necessari per il controllo della replicazione.

Come discusso prima, replicationè una tecnica utilizzata nei database distribuiti per archiviare più copie di una tabella di dati in siti diversi. Il problema di avere più copie in più siti è il sovraccarico di mantenere la coerenza dei dati, in particolare durante le operazioni di aggiornamento.

Per mantenere dati reciprocamente coerenti in tutti i siti, è necessario adottare tecniche di controllo della replica. Esistono due approcci per il controllo della replica, vale a dire:

  • Controllo della replica sincrona
  • Controllo della replica asincrona

Controllo della replica sincrona

Nell'approccio della replica sincrona, il database viene sincronizzato in modo che tutte le repliche abbiano sempre lo stesso valore. Una transazione che richiede un elemento di dati avrà accesso allo stesso valore in tutti i siti. Per garantire questa uniformità, una transazione che aggiorna un elemento di dati viene espansa in modo che effettui l'aggiornamento in tutte le copie dell'elemento di dati. In genere, allo scopo viene utilizzato il protocollo di commit a due fasi.

Consideriamo ad esempio una tabella dati PROJECT (PId, PName, PLocation). Dobbiamo eseguire una transazione T1 che aggiorni PLocation a "Mumbai", se PLocation è "Bombay". Se non ci sono repliche, le operazioni nella transazione T1 saranno:

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

Se la tabella di dati ha due repliche nel sito A e nel sito B, T1 deve spawnare due figli T1A e T1B corrispondenti ai due siti. La transazione ampliata T1 sarà:

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;

Controllo della replica asincrona

Nell'approccio della replica asincrona, le repliche non mantengono sempre lo stesso valore. Una o più repliche possono memorizzare un valore obsoleto e una transazione può visualizzare i diversi valori. Viene chiamato il processo per portare tutte le repliche al valore correntesynchronization.

Un metodo popolare di sincronizzazione è il metodo store and forward. In questo metodo, un sito è designato come sito primario e gli altri siti sono siti secondari. Il sito principale contiene sempre valori aggiornati. Tutte le transazioni entrano prima nel sito principale. Queste transazioni vengono quindi accodate per l'applicazione nei siti secondari. I siti secondari vengono aggiornati utilizzando il metodo di rollout solo quando è pianificata l'esecuzione di una transazione su di essi.

Algoritmi di controllo della replica

Alcuni degli algoritmi di controllo della replica sono:

  • Algoritmo di controllo della replica master-slave.
  • Algoritmo di voto distribuito.
  • Algoritmo di consenso della maggioranza.
  • Algoritmo del token circolante.

Algoritmo di controllo della replica master-slave

C'è un sito master e siti "N" slave. Un algoritmo principale viene eseguito nel sito principale per rilevare i conflitti. Una copia dell'algoritmo slave viene eseguita su ogni sito slave. L'algoritmo generale viene eseguito nelle due fasi seguenti:

  • Transaction acceptance/rejection phase- Quando una transazione entra nel monitor delle transazioni di un sito slave, il sito slave invia una richiesta al sito master. Il sito master verifica la presenza di conflitti. Se non ci sono conflitti, il master invia un messaggio "ACK +" al sito slave che quindi avvia la fase di applicazione della transazione. In caso contrario, il master invia un messaggio "ACK-" allo slave che poi rifiuta la transazione.

  • Transaction application phase- Entrando in questa fase, il sito slave in cui è entrata la transazione trasmette una richiesta a tutti gli slave per l'esecuzione della transazione. Alla ricezione delle richieste, gli slave peer eseguono la transazione e al completamento inviano un "ACK" allo slave richiedente. Dopo che lo slave richiedente ha ricevuto i messaggi "ACK" da tutti i suoi peer, invia un messaggio "FATTO" al sito master. Il master capisce che la transazione è stata completata e la rimuove dalla coda in sospeso.

Algoritmo di voto distribuito

Si tratta di siti peer "N", che devono tutti "OK" una transazione prima che inizi l'esecuzione. Di seguito sono riportate le due fasi di questo algoritmo:

  • Distributed transaction acceptance phase- Quando una transazione entra nel gestore delle transazioni di un sito, invia una richiesta di transazione a tutti gli altri siti. Alla ricezione di una richiesta, un sito peer risolve i conflitti utilizzando regole di voto basate sulla priorità. Se tutti i siti peer sono "OK" con la transazione, il sito richiedente avvia la fase di applicazione. Se uno qualsiasi dei siti peer non "OK" una transazione, il sito richiedente rifiuta la transazione.

  • Distributed transaction application phase- Entrando in questa fase, il sito in cui è inserita la transazione, trasmette a tutti gli slave una richiesta per l'esecuzione della transazione. Alla ricezione delle richieste, gli slave peer eseguono la transazione e al completamento inviano un messaggio "ACK" allo slave richiedente. Dopo che lo slave richiedente ha ricevuto i messaggi "ACK" da tutti i suoi peer, fa sapere al gestore delle transazioni che la transazione è stata completata.

Algoritmo di consenso della maggioranza

Questa è una variazione dell'algoritmo di voto distribuito, in cui una transazione può essere eseguita quando la maggioranza dei peer "OK" una transazione. Questo è diviso in tre fasi:

  • Voting phase- Quando una transazione entra nel gestore delle transazioni di un sito, invia una richiesta di transazione a tutti gli altri siti. Alla ricezione di una richiesta, un sito peer verifica la presenza di conflitti utilizzando le regole di voto e mantiene le transazioni in conflitto, se presenti, in coda in sospeso. Quindi invia un messaggio "OK" o "NON OK".

  • Transaction acceptance/rejection phase- Se il sito richiedente riceve la maggioranza "OK" sulla transazione, accetta la transazione e trasmette "ACCETTO" a tutti i siti. In caso contrario, trasmette "REJECT" a tutti i siti e rifiuta la transazione.

  • Transaction application phase- Quando un sito peer riceve un messaggio "REJECT", rimuove questa transazione dal suo elenco in sospeso e riconsidera tutte le transazioni differite. Quando un sito peer riceve un messaggio "ACCEPT", applica la transazione e rifiuta tutte le transazioni differite nella coda in sospeso che sono in conflitto con questa transazione. Al completamento, invia un "ACK" allo slave richiedente.

Algoritmo del token circolante

In questo approccio le transazioni nel sistema vengono serializzate utilizzando un token circolante ed eseguite di conseguenza su ogni replica del database. Pertanto, tutte le transazioni vengono accettate, ovvero nessuna viene rifiutata. Questo ha due fasi:

  • Transaction serialization phase- In questa fase, tutte le transazioni sono pianificate per essere eseguite in un ordine di serializzazione. Ad ogni transazione in ogni sito viene assegnato un ticket univoco da una serie sequenziale, indicante l'ordine di transazione. Una volta che a una transazione è stato assegnato un ticket, viene trasmesso a tutti i siti.

  • Transaction application phase- Quando un sito riceve una transazione insieme al suo ticket, pone la transazione per l'esecuzione in base al suo ticket. Al termine dell'esecuzione della transazione, questo sito trasmette un messaggio appropriato. Una transazione termina quando ha completato l'esecuzione in tutti i siti.