.. meta:: :language: it :description language=it: consistenza :description language=en: consistency :keywords: distributed system, consistency :author: Luciano De Falco Alfano .. index:: consistenza .. _ref_consistenza: Consistenza =================== .. contents:: :local: *Lezione del 2019-05-23 gio*. Nella progettazione di sistemi distribuiti è importante sapere che tipo di consistenza offre il modello da utilizzare. Qui si considerano due tipi di modelli di consistenza: quelli orientati ai dati e quelli orientati ai client. Consistenza e repliche -------------------------- I dati solitamente sono replicati per migliorare l'affidabilità [#]_ o le performance [#]_. Tutto ciò è vero se si legge soltanto. Ma se vi sono scritture, la replica introduce il problema di mantenere le unità replicate consistenti. Mantenere consistenti più copie di processi, può dare luogo a seri problemi di scalabilità se si adotta una *tight consistency*. Per **tight consistency** si intende il fatto che quando si esegue una modifica in una copia, la modifica deve essere propagata in tutte le copie *prima* di effettuare la successiva operazione. Con molte repliche *tight consistency* di sistemi aggiornati frequentemente il traffico dati per la diffusione dell'aggiornamento può creare grossi problemi: la cura può essere peggiore del male. Modelli di **consistenza data-centrici**. ------------------------------------------- I modelli di *consistenza data-centrici* assumono che più processi simultaneamente accedono a dati condivisi. In queste situazioni la consistenza può essere definita secondo cosa si aspettano i processi quando leggono e modificano i dati condivisi. Tradizionalmente le consistenza è discussa nel contesto di operazioni di lettura e scrittura su dati condivisi, disponibili per mezzo di memoria condivisa. In questo contesto, se un processo *A* scrive il valore 3, il processo *B* legge lo stesso valore 3, e se scrive 4, il processo *A* legge 4. Questa è la *tight consistency*. Ci si aspetta che i sistemi distribuiti funzionino nello stesso modo. Ma se vi è una replica, è possibile che il client *A* legga un valore in un dato sistema, e il client *B* ne legga un altro nel sistema replicato. Per aver una soluzione *tight consistency* in sistemi distributi, normalmente si ricorre ad una implementazione centralizzata, dove un singolo nodo master ha il compito di ricevere i comandi di scrittura e di attuarli verso le varie repliche. Si potrebbe ottenere una *tight consistency* con un approccio distribuito, nel caso in cui fosse presente un tempo globlale, con i nodi sincronizzati su di esso, e con trasmissioni istantanee. Ma queste non sono ipotesi plausibili. Per questo motivo spesso nei sistemi distribuiti non viene assicurata la *tight consistency*, ma si rilassano le condizioni di consistenza. Ad esempio, in certi sistemi può essere sufficiente che le operazioni avvengano secondo la stessa sequenza in tutte le repliche [#]_. O, addirittura, accettare una propagazione *lazy*. Ovvero accettare che temporaneamente alcune copie non riflettano gli aggiornamenti richiesti. In pratica, l'assenza di un *global clock* rende difficile capire quale sia l'ultima operazione di scrittura. Perciò si forniscono altre definizioni, dando luogo ad un range di modelli di consistenza. Ognuno di questi modelli limita i valori che possono essere restituiti da una operazione di lettura su un dato. Quindi possiamo dire che, nell'ipotesi di un rilassamento del concetto di **consistenza**, questa *è definibile come un* **contratto** *tra processi e data store* [#]_: se il processo si attiene a determinate regole, lo *store* promette di lavorare correttamente. Consistenza continua ^^^^^^^^^^^^^^^^^^^^^ Sono possibili diversi criteri di analisi per definire la *consistenza* del dato. I seguenti sono esempi di metodi appartenenti alla famiglia di *consistenza continua*. * Si potrebbe misurare la consistenza in termini di **deviazione numerica**. Ad esempio consideriamo una applicazione per la gestione dei prezzi di vendita del mercato azionario. Un criterio di consistenza può richiedere che due copie non deviino più di 2 centesimi. * Oppure si può richiedere che due copie non si discostino più di un certo numero di aggiornamenti. * O che due copie non si discostino oltre un certo intervallo di tempo rispetto l'ultimo aggiornamento. Consistenza di ordinamento delle operazioni ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Esiste poi la famiglia di metodi relativi alla *consistenza di ordinamento delle operazioni*. Questi modelli vedono la consistenza in relazione all'ordinamento delle operazioni sui dati replicati. In questi casi i processi devono concordare riguardo l'ordine degli aggiornamenti. Tra questi, uno dei modelli più importanti è la **consistenza sequenziale**, che assicura la sequenzialità delle azioni tra tutti i processi. Secondo Leslie Lamport: "il risultato di ogni esecuzione è lo stesso *come se* [#]_ le operazioni nel data store di tutti i processi vengano eseguite nello stesso ordine sequenziale, e le operazioni di ogni singolo processo appaiono in questa sequenza nell'ordine specificato dal suo programma." Ogni inserimento di operazioni valide di lettura o scrittura è un comportamento accettabile, *purché tutti i processi vedano gli stessi inserimenti*. Usando la seguente notazione *W(x)a* per indicare la scrittura nel dato *x* del valore *a*. E *R(x)a* per indicare che la lettura nel dato *x* restituisce il valore *a*. Possiamo dire che con la consistenza sequenziale: * se il processo *P1* scrive in un oggetto *x* un nuovo valore *a*; * allora succesivamente il processo *P2*, leggendo l'oggetto *x* può ricevere prima un valore *NIL* (oggetto non istanziato) e successivamente il valore *a* scritto da *P1*. Il seguente diagramma, con un processo per riga, e con la coordinata temporale orizzontale da sx a dx, illustra il concetto predetto: .. image:: /images/29_consistenza_sequenziale.svg :align: center Per chiarire ulteriormente, prendiamo il seguente diagramma. .. image:: /images/30_consistenza_sequenziale-2.svg :align: center Nel riquadro *(a)* osserviamo che i due processi *P3* e *P4*, in lettura, osservano entrambi prima il valore *b* e poi il valore *a*. Anche se la scrittura, secondo una coordinata temporale globale, è avvenuta nell'ordine inverso. Questo è accettabile, perché entrambi i lettori osservano la stessa sequenza di avvenimenti. Invece nel riquadro *(b)* vediamo che *P3* e *P4* leggono sequenze diverse. *P3* legge prima *b* e poi *a*. Mentre *P4* al contrario. Questo non è accettabile per una consistenza sequenziale. Attenzione al fatto che in alcuni sistemi comanda il server che riceve il messaggio. Ad esempio, in un sistema d'asta, supponiamo il client *A* rilanci nell'istante *t(A)* < *t(B)* in cui rilancia (lo stesso valore) il processo client *B*. In questo scenario, vince il processo che ha rilanciato per primo. Ma non è detto sia *A*. Se *B* ha una connessione al server più performante, la sua richiesta può arrivare prima di quella di *A*, ed essere classificata di conseguenza come vincente. Altro possibile modello è la **consistenza causale**. Questo è un rilassamento del modello di *consistenza sequenziale*, in quanto fa distinzione tra eventi che sono potenzialmente correlati causalmente, rispetto quelli che non lo sono: "tutte le scritture che sono potenzialmente correlate causalmente devono essere viste da tutti i processi nello stesso ordine. Scritture concorrenti [#]_ possono essere viste in ordini diversi su macchine diverse." Se due gruppi di processi non interagiscono fra loro, non è necessario mettere nello stesso ordine operazioni di un gruppo rispetto l'altro. Ad esempio, osserviamo il seguente diagramma. .. image:: /images/31_consistenza_causale.svg :align: center Le scritture del processo *P1* sono correlate (avvengono nello stesso processo), mentre la scrittura di *P2* non è correlata (non sollecita) con *W(x)c*. Di conseguenza le letture di *P3* e *P4* sono giustificabili. Il fatto che il valore *b* sia letto prima o dopo il valore *c* non ha importanza. Quel che conta è che il valore *a* sia sempre letto prima del valore *c*. Questo comportamento invece sarebbe da respingere se volessimo un modello di consistenza sequenziale. Attenzione al fatto che questo esempio è subdolo, perché vi è correlazione tra *W(x)a* e *W(x)b* per il tramite della *R(x)a* in *P2* (si veda l'esempio successivo). Per questo motivo deve avvenire sempre la lettura di *a* prima della lettura di *b*. Ma questa condizione è verificata. Consideriamo ora il seguente scenario, in cui il processo *P2* legge l'oggetto *x* prima di scrivere. La scrittura di *P2* quindi può essere condizionata dalla lettura antecedente: di conseguenza *W(x)b* è correlato con *W(x)a* .. image:: /images/32_consistenza_causale-2.svg :align: center In questo caso la *consistenza causale* è violata, perché la correlazione tra le due scritture imporrebbe sempre la lettura di *a* prima di *b*. Cosa che non avviene. La figura [#]_ ci permette di ipotizzare una possibile causa. Utilizzando due basi dati, la scrittura *W(x)a* verso *DB2* può essere ritardata. In tal caso, se *P3* legge da *DB2*, può vedere prima *b* e poi *a*. *E i due DB sarebbero disallineati*. Invece considerando il seguente diagramma, ora non abbiamo correlazione tra *W(x)a* e *W(x)b*: *P1* e *P2* sono del tutto indipendenti. .. image:: /images/33_consistenza_causale-3.svg :align: center Per questo motivo il fatto che le sequenze di lettura dei valori *a* e *b* siano invertiti in *P3* e *P4* non viola il modello di *consistenza causale*. Questi aspetti vanno considerati con attenzione. Ad esempio si ipotizzi di dover progettare un sistema con *N* sensori, che inviano le loro misure ad un nodo centrale che implementa la logica di allarme. Supponiamo che un allarme sia del tipo: "tutti i sensori superano contemporaneamente il valore 10". A regime, è possibile che *N-1* sensori superino il valore d'allarme, e, ad un certo istante anche il sensore *N* superi questa soglia, ma questo dato viaggi con ritardo verso il nodo centrale. Dopo di che, prima che il valore di *N* arrivi al centrale, vi arrivi il valore di *N-1* che viaggia più velocemente ed è sceso sotto la soglia di criticità: il nodo centrale non rileverà la criticità perché vedrà sempre N-1 misure al di sotto di 10. In Unicam questo comportamento è stato rilevato in progetti di ricerca. Per ovviare a questo problema si è invertita la logica di collezione dei dati. Invece del push dai sensori al centrale, si è passati al pull dal centrale, imponendo una frequenza d'interrogazione superiore a quella di campionamento dei sensori. In pratica si è sincronizzato il sistema. Eventual consistency ^^^^^^^^^^^^^^^^^^^^^ Quando non vi sono conflitti di scrittura, come, ad esempio, nel WWW o nel DNS, è possibile adottare la *eventual consistency*. Ovvero le repliche diventano consistenti con gradualità. La *eventual consistency* è detta anche *lazy consistency*. La *lazy consistency* è la strategia adottata anche da Google, che non modifica subito tutte le copie dei DB con gli indici dei siti analizzati. Quando si modifica un sito, viene aggiornata una singola copia con un DB che lo indicizza. Dopo di che, nel tempo, vengono allineate le repliche di indici che sono sparse per tutta Internet. Questa scelta è possibile perché le pagine web cambiano con bassa frequenza. Modelli di consistenza **client centrici** -------------------------------------------- I modelli precedenti sono *data centrici*, nel senso che devono fornire una visione del sistema consistente in riferimento al data store. Ma si può considerare la consistenza dal punto di vista del client, considerando che possiamo avere a che fare con data store in cui gli aggiornamenti *non sono simultanei*. Ad esempio il problema più evidente dell'uso della *eventual consistency* è osservabile con i client mobile. Ipotizziamo di utilizzare un client mobile per modificare un dato. Dopo di che ci disconnettiamo, per riconnetterci da un altro punto d'ingresso. Vi è la possibilità che la nuova connessione si colleghi ad una replica non allineata a quella su cui abbiamo fatto la modifica. Di conseguenza leggeremo uno stato diverso rispetto quello che ci aspettiamo. Questo fenomeno può essere contrastato perseguendo una consistenza **Client centric**. Questo tipo di consistenza fornisce la garanzia di consistenza nell'accesso al data store *per un singolo client* e specificamente solo quando si usa quel particolare client. **Bayou** distingue tra quattro modelli di consistenza: * **monotonic reads**: (same process on data item x) "reads will always return the same value or a more recent value"; * **monotonic writes**: (same process on data item x) "write completes before any successive write"; * **read your writes**: (same process on data item x) "the effect of a write will always be seen by a successive read"; * **writes follow reads**: (same process on data item x) "a write following a previous read take place on the same or a more recent value than that was read". Si ha *monotonic reads* nel caso in cui se un processo legge il valore di un dato *x* dal data store, allora una *successiva operazione di lettura* di *x* da parte dello stesso processo *restituisce lo stesso valore o un valore più aggiornato*. Si ha *consistency write* se nel data store una operazione di scrittura su un dato *x* da parte di un processo è completata *prima che avvenga una successiva operazione di scrittura* dello stesso processo sullo stesso dato. In un modello *read your writes* possiamo contare sul fatto che una operazione di scrittura da parte di un processo sul dato *x* sarà sempre vista da una successiva operazione di lettura su *x* da parte dello stesso processo. Nel caso di *writes follow reads* una operazione di scrittura di un processo sul dato *x* dopo una operazione di lettura dello stesso processo sullo stesso dato, sicuramente avviene su un valore di *x* uguale a quello letto, o più recente. ------------------------ .. [#] Se un sistema si guasta, i dati sono disponibili in un altro sistema. .. [#] Eliminazione dei colli di bottiglia, load balancing. .. [#] Quindi: non si richiede che le operazioni avvengano nello stesso istante globale in tutte le repliche, basta che avvengano con lo stesso ordine. .. [#] Ovvero tra programmatore e sistema distribuito con repliche. .. [#] Si noti il *come se*. Significa che l'ordine delle operazioni non è fissato a priori. Ma, **dato un ordine semanticamene corretto**, questo stesso ordine è assicurato per tutte le repliche. .. [#] *Concorrenti* qui è sinonimo di mancanza di correlazione. .. [#] Questa è una ipotesi dello scrivente.