DBMS distribuito - Controllo della concorrenza
Le tecniche di controllo della concorrenza assicurano che più transazioni vengano eseguite simultaneamente mantenendo le proprietà ACID delle transazioni e la serializzabilità nelle pianificazioni.
In questo capitolo studieremo i vari approcci per il controllo della concorrenza.
Protocolli di controllo della concorrenza basati sul blocco
I protocolli di controllo della concorrenza basati sul blocco utilizzano il concetto di blocco degli elementi di dati. UNlockè una variabile associata a un elemento di dati che determina se le operazioni di lettura / scrittura possono essere eseguite su quell'elemento di dati. In genere, viene utilizzata una matrice di compatibilità del blocco che indica se un elemento di dati può essere bloccato da due transazioni contemporaneamente.
I sistemi di controllo della concorrenza basati sul blocco possono utilizzare protocolli di blocco monofase o bifase.
Protocollo di blocco monofase
In questo metodo, ogni transazione blocca un elemento prima dell'uso e rilascia il blocco non appena ha finito di usarlo. Questo metodo di blocco fornisce la massima concorrenza ma non sempre impone la serializzabilità.
Protocollo di blocco a due fasi
In questo metodo, tutte le operazioni di blocco precedono la prima operazione di sblocco o rilascio del blocco. La transazione comprende due fasi. Nella prima fase, una transazione acquisisce solo tutti i blocchi di cui ha bisogno e non rilascia alcun blocco. Questo è chiamato espansione ogrowing phase. Nella seconda fase, la transazione rilascia i blocchi e non può richiedere nuovi blocchi. Questo è chiamatoshrinking phase.
Ogni transazione che segue il protocollo di blocco a due fasi è garantita come serializzabile. Tuttavia, questo approccio fornisce un basso parallelismo tra due transazioni in conflitto.
Algoritmi di controllo della concorrenza timestamp
Gli algoritmi di controllo della concorrenza basati sul timestamp utilizzano il timestamp di una transazione per coordinare l'accesso simultaneo a un elemento di dati per garantire la serializzabilità. Un timestamp è un identificatore univoco fornito da DBMS a una transazione che rappresenta l'ora di inizio della transazione.
Questi algoritmi assicurano che le transazioni si impegnino nell'ordine dettato dai loro timestamp. Una transazione più vecchia dovrebbe eseguire il commit prima di una transazione più recente, poiché la transazione più vecchia entra nel sistema prima di quella più giovane.
Le tecniche di controllo della concorrenza basate sul timestamp generano pianificazioni serializzabili in modo tale che la pianificazione seriale equivalente sia organizzata in base all'età delle transazioni partecipanti.
Alcuni degli algoritmi di controllo della concorrenza basati su timestamp sono:
- Algoritmo di ordinamento del timestamp di base.
- Algoritmo di ordinamento del timestamp conservativo.
- Algoritmo di multiversione basato sull'ordinamento del timestamp.
L'ordinamento basato sul timestamp segue tre regole per imporre la serializzabilità:
Access Rule- Quando due transazioni tentano di accedere allo stesso elemento di dati contemporaneamente, per operazioni in conflitto, viene data priorità alla transazione precedente. Ciò fa sì che la transazione più recente attenda prima il commit della transazione più vecchia.
Late Transaction Rule- Se una transazione più recente ha scritto un elemento di dati, una transazione più vecchia non è autorizzata a leggere o scrivere quell'elemento di dati. Questa regola impedisce il commit della transazione precedente dopo che è già stato eseguito il commit della transazione più recente.
Younger Transaction Rule - Una transazione più recente può leggere o scrivere un elemento di dati che è già stato scritto da una transazione precedente.
Algoritmo di controllo della concorrenza ottimistico
Nei sistemi con bassi tassi di conflitto, il compito di convalidare ogni transazione per la serializzabilità può ridurre le prestazioni. In questi casi, il test per la serializzabilità viene posticipato appena prima del commit. Poiché il tasso di conflitto è basso, è bassa anche la probabilità di interrompere le transazioni che non sono serializzabili. Questo approccio è chiamato tecnica di controllo della concorrenza ottimistica.
In questo approccio, il ciclo di vita di una transazione è suddiviso nelle seguenti tre fasi:
Execution Phase - Una transazione preleva elementi di dati in memoria ed esegue operazioni su di essi.
Validation Phase - Una transazione esegue controlli per garantire che il commit delle modifiche al database superi il test di serializzabilità.
Commit Phase - Una transazione riscrive su disco l'elemento di dati modificato in memoria.
Questo algoritmo utilizza tre regole per applicare la serializzabilità nella fase di convalida:
Rule 1- Date due transazioni Ti e T j , se Ti sta leggendo l'elemento di dati che T j sta scrivendo, la fase di esecuzione di T i non può sovrapporsi alla fase di commit di T j . T j può eseguire il commit solo dopo che Ti ha terminato l'esecuzione.
Rule 2- Date due transazioni Ti e T j , se Ti sta scrivendo l'elemento dati che T j sta leggendo, la fase di commit di T i non può sovrapporsi alla fase di esecuzione di T j . T j può iniziare l'esecuzione solo dopo che Ti ha già eseguito il commit.
Rule 3- Date due transazioni Ti e T j , se Ti sta scrivendo l'elemento di dati che T j sta anche scrivendo, la fase di commit di T i non può sovrapporsi alla fase di commit di T j . T j può iniziare a eseguire il commit solo dopo che Ti ha già eseguito il commit.
Controllo della concorrenza nei sistemi distribuiti
In questa sezione vedremo come le tecniche di cui sopra sono implementate in un sistema di database distribuito.
Algoritmo di bloccaggio a due fasi distribuito
Il principio di base del blocco a due fasi distribuito è lo stesso del protocollo di blocco a due fasi di base. Tuttavia, in un sistema distribuito ci sono siti designati come gestori di blocchi. Un gestore dei blocchi controlla le richieste di acquisizione dei blocchi dai monitor delle transazioni. Al fine di rafforzare il coordinamento tra i gestori dei blocchi in vari siti, almeno un sito ha l'autorità di vedere tutte le transazioni e rilevare i conflitti di blocco.
A seconda del numero di siti in grado di rilevare conflitti di blocco, gli approcci di blocco a due fasi distribuiti possono essere di tre tipi:
Centralized two-phase locking- In questo approccio, un sito è designato come gestore della serratura centrale. Tutti i siti nell'ambiente conoscono l'ubicazione del gestore della serratura centrale e ottengono il blocco da esso durante le transazioni.
Primary copy two-phase locking- In questo approccio, diversi siti sono designati come centri di controllo delle chiuse. Ciascuno di questi siti ha la responsabilità di gestire un insieme definito di blocchi. Tutti i siti sanno quale centro di controllo della serratura è responsabile della gestione del blocco di quale elemento di tabella / frammento di dati.
Distributed two-phase locking- In questo approccio, ci sono una serie di gestori di serrature, in cui ogni gestore di serrature controlla i blocchi degli elementi di dati memorizzati nel proprio sito locale. La posizione del gestore blocchi si basa sulla distribuzione e replica dei dati.
Controllo della concorrenza con timestamp distribuito
In un sistema centralizzato, il timestamp di qualsiasi transazione è determinato dalla lettura dell'orologio fisico. Tuttavia, in un sistema distribuito, le letture dell'orologio fisico / logico locale di qualsiasi sito non possono essere utilizzate come timestamp globali, poiché non sono univoche a livello globale. Quindi, un timestamp comprende una combinazione dell'ID del sito e della lettura dell'orologio di quel sito.
Per l'implementazione degli algoritmi di ordinamento del timestamp, ogni sito ha uno scheduler che mantiene una coda separata per ogni gestore delle transazioni. Durante la transazione, un gestore delle transazioni invia una richiesta di blocco allo scheduler del sito. Lo scheduler inserisce la richiesta nella coda corrispondente in ordine crescente di timestamp. Le richieste vengono elaborate dalla parte anteriore delle code nell'ordine dei loro timestamp, cioè il più vecchio per primo.
Grafici dei conflitti
Un altro metodo è creare grafici di conflitto. Per questa transazione sono definite classi. Una classe di transazione contiene due set di elementi di dati denominati set di lettura e set di scrittura. Una transazione appartiene a una particolare classe se il set di lettura della transazione è un sottoinsieme del set di lettura della classe e il set di scrittura della transazione è un sottoinsieme del set di scrittura della classe. Nella fase di lettura, ogni transazione emette le sue richieste di lettura per gli elementi di dati nel suo set di lettura. Nella fase di scrittura, ogni transazione emette le sue richieste di scrittura.
Viene creato un grafico dei conflitti per le classi a cui appartengono le transazioni attive. Questo contiene una serie di bordi verticali, orizzontali e diagonali. Un bordo verticale collega due nodi all'interno di una classe e denota conflitti all'interno della classe. Un bordo orizzontale collega due nodi tra due classi e denota un conflitto di scrittura-scrittura tra classi diverse. Un bordo diagonale collega due nodi attraverso due classi e denota un conflitto di scrittura-lettura o lettura-scrittura tra due classi.
I grafici dei conflitti vengono analizzati per accertare se due transazioni all'interno della stessa classe o tra due classi differenti possono essere eseguite in parallelo.
Algoritmo di controllo della concorrenza ottimistico distribuito
L'algoritmo di controllo della concorrenza ottimistica distribuita estende l'algoritmo di controllo della concorrenza ottimistica. Per questa estensione vengono applicate due regole:
Rule 1- Secondo questa regola, una transazione deve essere convalidata localmente in tutti i siti quando viene eseguita. Se una transazione è ritenuta non valida in qualsiasi sito, viene interrotta. La convalida locale garantisce che la transazione mantenga la serializzabilità nei siti in cui è stata eseguita. Dopo che una transazione supera il test di convalida locale, viene convalidata a livello globale.
Rule 2- Secondo questa regola, dopo che una transazione supera il test di convalida locale, dovrebbe essere convalidata a livello globale. La convalida globale garantisce che se due transazioni in conflitto vengono eseguite insieme in più di un sito, devono eseguire il commit nello stesso ordine relativo in tutti i siti che vengono eseguiti insieme. Ciò potrebbe richiedere che una transazione attenda l'altra transazione in conflitto, dopo la convalida prima del commit. Questo requisito rende l'algoritmo meno ottimista poiché una transazione potrebbe non essere in grado di eseguire il commit non appena viene convalidata in un sito.