02 & 03 - Model & Communication (PDF)

📏 02 - modelling (1,5) Architetture software Network based è chiaramente visibile la comunicazione con altre machine Assenza di routing (comunicazioni di un singolo hop) Esempio: linux/windows + ud...

📏 02 - modelling (1,5) Architetture software Network based è chiaramente visibile la comunicazione con altre machine Assenza di routing (comunicazioni di un singolo hop) Esempio: linux/windows + udp/tcp Middleware based il middleware fornisce: servizi di comunicazione e coordinazione più semplici da utilizzare ad alto livello rispetto a scambi di messaggi udp/tcp esempio: RMI (sincrono) 02 - modelling (1,5) 1  Architettura run-time descrive come la computazione è suddivisa nelle diverse macchine, e come queste collaborano, comunicano e si coordinano. 1. Client - server è l’architettura più comune. Client e server sono chiaramente distinguibili. I server aspettano che i client chiedano un servizio e successivamente lo forniscono. Possono esserci più layer tra il client e il server (multi-tiered) esempio: il web 2. Service oriented (SOA) in astratto è un caso particolare del client server. La differenza sta che l’interazione al posto di essere un messaggio che viene passato, è una invocazione di un servizio. Il servizio è il centro di questa architettura ed è descritto da un contratto, il quale contiene il set di operazioni fornite dal servizio e il loro nome. c’è un terzo componente, il service broker, funge da intermediario tra il service provider e il service consumer. fornisce molte applicazioni ed è una specie di DNS. esempio di utilizzo: Web service 02 - modelling (1,5) 2  3. REST (REpresentational State Transfer) è un’evoluzione della SOA, è una buona descrizione di come dovrebbero essere utilizzati gli standard del web. è un caso specifico del client-server. la risposta del server è indipendente dallo stato del server ma dipende solo dalla richiesta del client. questo implica che l’interazione è stateless, per garantire la funzionalità delle applicazioni lo stato è interamente gestito dal client. vantaggi: scalabiità (garantita dal caching. il client non deve connettersi allo stesso server perchè è lui stesso in possesso del proprio stato, che fornisce tramite le richieste, quindi possono esserci tanti server che sono visti in modo univoco dal client) svantaggi: costo “appioppato” al client, che in genere ha meno potenza del server. altri vincoli: il client deve supportare il code-on-demand (opzionale), ovvero l’abilità di fornire del codice come risultato di un’operazione che viene eseguito lato client, in pratica javascript. 4. peer-to-peer c’è assenza di distinzione tra client e server, ovvero un’uniformità di ruolo tra i componenti, chiamati peer. sfrutta la potenza dei terminali “a bordo” del web, rispetto ai primi anni di internet dove la potenza di calcolo era fortemente centralizzata ai server. le prime applicazioni erano principalmente di file sharing (emule). è possibile che ci sia un server a fornire servizi ma le interazioni principlali sono tra i peer direttamente. 02 - modelling (1,5) 3  esempio: skype. 5. Object oriented i componenti (peer) sono oggetti remoti che encapsulano una struttura dati fornendo un API per accederci e modificarla, descritta da un description language (indipendente da ogni linguaggio di programmazione). gli oggetti possono essere implementati in linguaggi differenti. I peer interagiscono con RPC. vantaggi: l’information hiding nasconde la complessità nell’accesso e la gestione dei dati condivisi. gli oggetti sono facilmente riutilizzabili tra diverse applicazioni. 6. Data centered le interazioni tra i componenti sono mediate da un componente centrato logicamente (una repository passiva). per comunicare le macchine depositano e/o prendono dati dalla repo. non ci sono interazioni dirette (anonime, persistenti). vantaggio: interazioni indirette, creano un forte legame tra i componenti. Linda interazione mediata da tuple logiche, salvate in uno spazio condiviso globale e persistente. svantaggi: il metodo di tuple difficilmente scalabile 02 - modelling (1,5) 4  il modello è solo proattivo 7. Event based permette ai componenti di interagire indirettamente. ogni componente può effettuare 2 operazioni: pubblicano notifiche sugli eventi che osservano iscrivono gli eventi di cui vorrebbero ricevere le notifiche (permanentemente) le notifiche di un evento è inviato automaticamente a chiunque è iscritto a quell’evento (modello reattivo). caratteristiche della comunicazione: basata su messaggi asincrona multicast implicita anonima (chi pubblica non sa chi riceve) 8. Mobile Code introduce la possibiltà di rilocare il codice ed eventualmente lo stato dei componenti delle applicazioni distribuite a run time. paradigmi di mobile code: Remote evaluation chi richiede il servizio possiede il codice, chi lo fornisce lo esegue e ritorna il risultato. Esempio: query SQL Code on demand approccio opposto al precedente. chi richiede il servizio ha tutto eccetto il codice. una volta ricevuto lo esegue in locale. Esempio: javaScript nei browser. Mobile agent è possibile spostare il processo (codice + stato) durante l’esecuzione. chi chiede il servizio ha il codice e i dati ma non l’abilità di processare. 02 - modelling (1,5) 5  tipicamente non supportato perchè è difficile da implementare e perchè non è sicuro. tecnologie: strong mobility: abilità del sistema di permettere la migrazione sia del codice sia lo stato di esecuzione in un diverso ambiente computazionale. (pochi sistemi lo permettono) weak mobility: abilità del sistema di permettere lo spostamento di codice attraverso diversi ambienti computazionali. (fornito da Java,.NET e il web) Vantaggio: flessibilità per i programmatori (caricare/migliorare nuovi componenti senza stoppare l’applicazione) Svantaggi: la sicurezza di codici mobili è molto “incasinato” Interaction model Descrive cos’è un algoritmo distribuito. Un algoritmo distribuito è composto dalla definizione dei passaggi richiesti da ogni processo (ogni algoritmo dei vari processi) e i messaggi che questi processi si scambiano. Synchronous distributed systems (ideale) ci sono limiti ben definti sulla massima e minima velocità di esecuzione di ogni cpu, del tempo di trasporto di un messaggio di ogni link e del clock bit rate Asynchronous distributed systems (reali) non ci sono limiti. se qualcosa funziona per un sistema asincrono allora sicuramente funzionerà per uno sincrono, ma non è detto il viceversa. Failure model i processi e i canali di comunicazioni possono fallire, il failure model descrive i modi in cui i fallimenti possono capitare per capire meglio l’effetto di questi fallimenti. tipi di fallimento: 02 - modelling (1,5) 6  Omission failure (omissione di fare qualcosa) processi: omissione di esecuzione del codice (crash) canali: perdita di pacchetti (completamente) Byzantine failure (fare qualcosa di diverso) processi: esecuzione di codice diverso dal previsto. non si stoppa canali: i pacchetti vengono consegnati ma con un contenuto diverso Timing failure (per i sistemi sincronizzati) quando uno dei limiti viene violato Solitamente i processi hanno omission failure, i canali più byzantine ma sono facilmente reindirizzabili come omission. 02 - modelling (1,5) 7  💬 03 - communication (2,5) Come avviene la comunicazione tra processi all’interno di sistemi distribuiti? LAYERED PROTOCOLS Il modo più semplice è l’utilizzo di protocolli di rete, modello a strati in cui ciascun processo viene spezzato in diversi livelli. I protocolli di ciascun livello descrivono le regole necessarie per una specifica parte della comunicazione (modello iso/osi, tcp/ip) physical protocols: regole che permettono a due host direttamente connessi di comunicare attraverso segnali fisici (ethernet, segnali radio) data-link protocols: regole che permettono a due host direttamente connessi di scambiarsi data (bits o bytes) network protocols: regole che permettono a due host non direttamente connessi di comunicare (routing protocols) transport protocols: regole che permettono a due processi di comunicare (TCP/UDP) Application protocols: protocolli utilizzati in internet Il middleware è un livello aggiuntivo che offre regole e informazioni aggiuntive ai programmatori. Il completo scambio di messaggi tra due processi avviene 03 - communication (2,5) 1  mediante incapsulazione e decapsulazione (ogni livello aggiunge il proprio header, contententi le informazioni necessarie per il protocollo) TIPI DI COMUNICAZIONE TRANSIENT: i due processi devono essere attivi durante la comunicazione (chiamata telefonica) PERSISTENT: non è necessario che i due processi siano attivi (email) SINCRONA: è necessaria una forte sincronizzazione tra i due processi (tipicamente è transient) ASINCRONA: non è necessaria sincronizzazione tra i due processi UDP: transient e asincrono TCP: sincrono all’invio della richiesta REMOTE PROCEDURE CALL E’ una forma di comunicazione che simula la standard chiamata a procedure (come su C) ma su una rete. Il passaggio di parametri a una procedura può essere: per valore: come in C per i tipi di dato semplici, viene creata una copia per indirizzo: come in C per array e come in Java per oggetti, viene passato l’indirizzo di memoria per copia/ripristino: viene fatta una copia dei parametri attuali (copia) ma prima della conclusione della procedura il valore viene copiato (ripristino) attuali → formali (copy), formali → attuali (restore) 03 - communication (2,5) 2  int i = 3; void foo(int j, int k) { foo(i,i); j++; k++; -> i = 4 } Per rendere la chiamata a livello di rete il client chiama un metodo foo() con la stessa signature della procedura lato server che però non è la vera procedura il metodo foo() chiamato è un middleware che si occupa della creazione e invio del pacchetto al server, serializzando i parametri. Questo middleware è chiamato ‘stub’ stessa cosa avviene per la risposta lato server il passaggio di parametri per indirizzo non è possibile, mentre è possibile utilizzare il passaggio per valore e copia/ripristino si possono verificare Exceptions dovute alla rete, a differenza delle chiamate locali IDL (interface definition language): separa le interfacce dalle implentazioni, è una descrizione formale che permette di generare i codici degli stub sia a lato client che server anche in modo automatico Nasce il problema del binding tra client e server, ossia sapere dove si trova il processo server e di come connettersi ad esso (qual è la macchina dove si trova la procedura e quale processo): Sun’s solution: middleware che tramite un processo deamon (portmap) mappa procedure con le porte. Risolve solo il secondo problema) 03 - communication (2,5) 3  DCE’s solution: il daemon è simile al precedente, inoltre utilizza directory server (aka binder daemon) per mappare i server. Può anche essere distribuito per migliorare la scalabilità Di base RPC è sincrono, esistono però alcuni casi dove può essere utilizzato in modo asincrono. REMOTE METHOD INVOCATION Permette di richiamare metodi di oggetti remoti all’interno di una rete. Come nel caso di RPC viene utilizzato un oggetto fasullo (deve offrire la stessa interfaccia dell’oggetto remoto) che verrà chiamato dal client. Questo oggetto chiamato ‘proxy’ si occupa di effettuare la vera chiamata a livello di rete. Avremo bisogno della stessa cosa lato server, dove l’oggetto prende il nome di ‘skeleton’. Come nel caso di RPC l’implentazione del proxy e dello ‘skeleton’ può avvenire in modo automatico, conoscendo soltanto le interfacce. Il passaggio di parametri può essere fatto per indirizzo, dove l’indirizzo passato è di un oggetto proxy i cui metodi sono delle callback all’oggetto client. Esempi di RMI: Java RMI: unico linguaggio (Java) sia per le implementazioni che per le definizioni di interfacce. Permette il passaggio di parametri sia per indirizzo 03 - communication (2,5) 4  che per valore (in quanto oggetti scritti sempre in Java) OMG Corba: permette di far comunicare tra di loro oggetti scritti in linguaggi diversi. Permette passaggi di parametro per indirizzo e per valore (bisogna però garantire che i metodi abbiano la stessa semantica) Ricapitolando, RPC/RMI: offrono un modello naturale, facile da utilizzare, comodo e potente per i programmatori offrono però un modello di comunicazione sincrono, più costoso rispetto ad un modello asincrono supportano soltanto interazioni point-to-point e rigide architetture dovute al forte accoppiamento tra chiamante e chiamato MESSAGE ORIENTED COMMUNICATION Diversa tipologia di comunicazione che si basa sul concetto di messaggi/eventi. A differenza dei due precedenti non vado a chiamare codice, ma invio un messaggio. solitamente asincrono supporta interazioni multi-point e può supportare persistenza vi è meno accoppiamento tra chiamante e chiamato Modello di riferimento: per l’invio di messaggi sono presenti dei server intermedi (communication server) che si occupano del corretto invio di essi (come nel caso dei server SMTP nelle email) TCP e UDP sono due esempi di protocolli che utilizzano questo tipo di comunicazione 03 - communication (2,5) 5  SOCKET: astrazione comune per la comunicazione orientata ai messaggi tra processi. Permette comunicazioni di tipo connection-oriented (TCP) e connectionless (UDP). Sono identificate da 4 parametri: indirizzo IP del client e indirizzo IP del server porta del client e porta del server STREAM SOCKET (connection-oriented): distinzione tra client-socket e server- socket il server accetta connessioni su una determinata porta il client si connette al server tramite quella porta DATAGRAM SOCKET (connectionless): mittente e destinatario utilizzano lo stesso approccio entrambi aprono una socket su una determinata porta utilizzano essa per mandare e ricevere messaggi MULTICAST SOCKET: upgrade del datagram socket. Permette l’invio di un messaggio a un gruppo di host, identificato da un indirizzo IP. I messaggi di questo tipo sono bloccati dai router all’interno di internet open group: è possibile mandare un messaggio al gruppo anche se non si fa parte di esso (UDP multicast) closed group: bisogna fare parte del gruppo per poter mandare un messaggio ad esso Limitazione delle socket: sono di basso livello sono protocol independent (possono essere usate sia per stream-oriented che packet-oriented communication, internet socket vs unix socket), implementazioni e performance differenti MPI Middleware per attuare una message oriented communication sempre di basso livello ma è diretta ad uno scenario specifico, ossia un insieme di computer connessi allo stesso data center per effettuare high-performance computing. La comunicazione avviene tra gruppi di processi ciascuno dei quali ha un proprio ID: 03 - communication (2,5) 6  la coppia (groupID, processID) rappresenta l’indirizzo sorgente o destinazione i messaggi possono essere mandati in broadcast all’intero gruppo fault tolerance inesistente, ogni crash è fatale MESSAGE QUEUING Offre una comunicazione point-to-point, persistente e asincrona. E’ di alto livello a differenza di MPI, è come “uno scambio di email” tra processi. L’idea è che un processo possa: associarsi ad una coda (attach) gestita da un middleware aggiungere un messaggio alla coda (put) leggere un messaggio dalla coda (get) o controllare e rimuovere il primo messaggio (poll) essere notificati quando un messaggio viene aggiunto ad una determinata coda (notify) Le code sono identificate da nomi simbolici, quindi è necessario un look-up (tipicamente distribuito). Il middleware che contiene le code può essere “intelligente”, ossia contenere e eseguire del codice (broker program) per pre- processare i messaggi prima o dopo inserirli in coda PUBLISH-SUBSCRIBE E’ una forma di comunicazione offerta da un middleware che consente ai processi di effettuare solo due azioni: publish: pubblicare in modo asincrono delle event notifications subscribe: dichiarare interesse in una o più classi di eventi subject-based (o topic-based): filtro sul main topic content-based: filtro più dettagliato anche sul contenuto Publishing e subscription sono gestite dall’event dispatcher centralizzato: singola macchina che si occupa di raccogliere le subscriptions e di inoltrare i messaggi ai soli subscribers distribuito: un set di message brokers organizzati in un overlay network cooperano per raccogliere subscriptions e inoltrare i messaggi ai 03 - communication (2,5) 7  subscribers. La topologia dell’overlay network può essere: aciclica (content-based): Message forwarding: il client invia la propria subscription al broker adiacente che non la propaga agli altri broker le publications percorrono tutta l’overlay network; i broker inoltrano le publications solo ai subscribers Subscription forwarding: le subscriptions vengono propagate tra i broker le publications percorrono solo la strada corretta per raggiungere i subscribers Hierarchical forwarding: il grafo viene trattato come un albero, eleggendo un nodo come root sia publications e subscriptions vengono inoltrate al nodo root le publications percorrono solo i rami corretti per raggiungere i subscribers ciclica (content-based): PSF (Per-Source-Forwarding): ciascun nodo definisce uno shortest path tree (SPT) singola tabella (sorgente, next hop, predicate) viene seguita la path minima PRF (Per-Receiver-Forwarding): il mittente del messaggio calcola il set di ricevitori e li aggiunge all’header del messaggio due tabelle (broker-next hop, broker-pred) Distance vector Link state ciclica (topic-based): 03 - communication (2,5) 8  DHT base approach (distributed hash table) COMPLEX EVENT PROCESSING: sistema che permette di aggiungere delle regole su sequenze di messaggi al middleware per aumentarne l’intelligenza (temperatura alta e fumo → fuoco) Publish-subscribe è powerful ma ha dei problemi, i problemi sono simili a quelli incontrati nei queue base systems, ossia viene data tanta responsabilità al middleware la cui implementazione diventa molto complicata. nel caso dei sistemi a coda, per garantire persistenza è necessario che la coda venga replicata nel caso di publish-subscribe, la complessità aumenta nel caso di event dispatcher distribuito di tipo content-based con l’utilizzo di grafi aciclici e ciclici STREAM ORIENTED COMMUNICATION I messaggi che vengono scambiati sono costituiti da uno stream (sequenza) di elementi/pacchetti/bit, come nel caso dei multimedia stream. Il tempo è critico per la performance del servizio ma non per la sua correttezza Tipicamente è asincrono, ma può essere anche sincrono (massimo delay per ogni unità) o isocrono (massimo e minimo delay) Quali sono le tecniche per migliorare la QoS, ossia cercare di garantire i punti chiave offerti dalla stream oriented communication (velocità, max delay per il setup della sessione, max delay end-to-end, max varianza del delay (jitter))? Buffering: controllare il max jitter sacrificando del tempo di setup (accumulo alcuni frame prima di partire) Forward error correction: correzione dei pacchetti corrotti (è necessario avere le informazioni necessarie per la correzione) 03 - communication (2,5) 9  Interleaving data: combinazione di buffering e forward error correction, i frame vengono inviati in modo diverso per limitare l’impatto di un pacchetto perso 03 - communication (2,5) 10  ✍🏼 04 - naming (2) il “naming” è il problema di dare un nome ad ogni elemento che compone un distributed system. Concentti generali: i nomi sono usati per riferirisi alle entità. esempi: host, utenti, file, server… le entità sono accessibili dagli access point (anche più di uno contemporaneamente). un’entità speciale è caratterizzata da un indirizzo. un indirizzo è un caso speciale di un nome esempio: il DNS permette di ricordarsi il nome dei siti e non l’ip del web server. osservazione: non conviene usare l’indirizzo di un access point come nome di un entità. Name resolution è il processo utilizzato per ottenere l’indirizzo di un access point valido di un’entità avendo il suo nome. esempi: DNS, Java RMI registry, X500, … Flat naming i nomi flat sono semplici stringhe che non hanno nè struttura nè contenuto. ovvero non hanno dei pezzi distinguibili al suo interno o se presenti non sono rilevanti per risolvere il nome. ci sono diversi approcci per risolvere i nomi flat. 1. Simple solutions a. Broadcast. simile all’ARP, invia messaggi “find” in broadcast e solo chi è interessato risponde. svantaggio: efficienza, tutti gli host devono processare i messaggi. b. Multicast. uguale al precedente ma in multicast. 04 - naming (2) 1  c. Forwarding pointers. lascia il riferimento della next location alla precedente. è utilizzato per i nodi mobili. 2. Home based approches: è usata negli ip mobili e per le reti dei cellulari. si affida ad un nodo home che conosce la location dell’unità mobile. la home si assume stabile e può essere replicata per garantire robustezza. l’inidirizzo ip originale è utilizzato come identificatore. 3. Distributed Hash Table (DHT): i nodi sono organizzati in una structured overlay network con topologie differenti. La ricerca è operata attraverso la hash table distribuita tra i vari nodi. un’implementazione di questo approccio è Chord, che si basa sul fatto che i nodi e le chiavi sono organizzate in un anello logico. 4. Hierarchical approches: i nodi sono organizzati in una struttura ad albero. la radice ha le entries di ogni entità e un entry point per ogni sotto dominio (sottoalbero). le foglie contengono l’indirizzo di un’entità in quel dominio. Questo approccio non è facilmente scalabile perchè più nodi ci sono più deve essere grande il database. Il caching è generalmente inefficiente. Structured naming Sono sistemi in cui i nomi hanno una struttura interna. esempio: indirizzo completo di casa, DNS (url). sono organizzati in name space, ovvero un grafo etichettato composto da 04 - naming (2) 2  leaf nodes: rappresentato un’entità con un nome (named entity). contiene le informazioni dell’identità. directory node: contiene numerosi archi uscenti etichettati, ognuno punta ad un nodo diverso. ci si riferisce ai nomi attraverso dei path names, ad esempio: o /alpha/beta/gamma. queste path possono essere assolute o relative. più path name possono riferirsi alla stessa entità. i name space per sistemi a larga scala sono solitamente distribuiti su diversi name server, organizzati gerarchicamente. i namespace possono essere partizionati in layer logici: global level: composto dai directory nodes ad alto livello. sono stabili e cambiano raramente. sono facilmente trattati con il cashing. administrational level. managerial level: composto dai directory nodes a basso livello con una singola amministrazione. Ci sono due principali tecniche per la name resolution: Iterativo: inizialmente si chiede al Ricorsivo: inizialmente si chiede root per poi procedere ai nodi al root e poi si inoltra sottostanti fino ad arrivare al ricorsivamente ai nodi sottostanti responsabile di quella risorsa. and so on so far. questa tecnica vantaggi: ridotti costi di non utilizza caching, perchè comunicazione, caching più potrebbe rallentare i lookup. efficiente lungo la catena di risoluzione. 04 - naming (2) 3  la struttura del DNS è un esempio pratico di un sistema structured naming, il name space è organizzato gerarchicamente e il caching e la replication sono fortemente utilizzate per incrementare l’efficienza. i namespace del DNS è organizzato come un albero gerarchico con diverse autorità per ogni dominio. Ogni name server è responsabile di una zona specifica. Il DNS funziona bene su queste assunzioni: i contenuti dei layer global/administrational sono piuttosto stabili i contenuti del layer manageriale cambia spesso ma le richieste sono gestite da name server nella stessa zona. Quando un host deve spostarsi all’interno del dominio necessita solo di aggiornare i name server di quel dominio, mentre se deve spostarsi verso un altro dominio, i server DNS forniscono un nuovo indirizzo ip o creano un symbolic link per la nuova location. Attribute based naming ancora piu espressivi degli structured. l’idea degli abn è quella di sostituire ai nomi delle entità un set di attributi associati. il name system può essere interrogato a cercare le entità fornendo valori di alcuni degli attributi. più entity possono essere ritornate. I sistemi attribute based naming sono solitamente chiamati directory services. sono solitamente utilizzati nelle tecnlogie DBMS. il protocollo dominante dei directory service si chiama LDAP (Lightweight Directory Access Protocol). la sua directory consiste in diversi record (directory entries), ognuna delle quali è composta da una collezione di coppie. ogni attributo ha un tipo. esistono attributi a singolo valore o anche a valore multiplo. alcuni attributi sono parte dello standard. 04 - naming (2) 4  la collezione di tutti i record di un LDAP directory service è chiamata Directory Information Base(DIB). ogni record ha un nome unico. nelle directory di larga scala, il DIB è partizionato secondo il Directory Information Tree (DIT), i server vengono chiamati Directory Service Agents (DSA) e i client Directory User Agents (DUA) Removing unreferenced entities un problema che si riscontra spesso nella creazione dei grafi è quello di non poter eliminare un oggetto che non è raggiungibile da nessun nodo. Ci sono diversi approcci per risolver questo problema. Reference counting: ogni oggetto tiene traccia del numero di reference che ha, al momento della sua creazione il counter è settato a 1 ( il suo creatore). quando una reference non è più necessaria, il counter viene decrementato finchè, quando raggiunge 0 l’oggetto viene eliminato. problema: race condition (conflitto di concorrenza) quando si passa la reference tra processi. Weighted reference counting: ogni oggetto possiede due numeri, inizialmente uguali. quando una nuova reference viene creata, un peso viene dimezzato e dato al nuovo nodo. successivamente si applica una garbage collector quando i due numeri tornano identici. questo metodo 04 - naming (2) 5  cerca di evitare il race condition comunicando solamente i decrementi dei contatori. problema: solo un numero fisso di reference possono essere create. Reference listing: si usa una lista per tenere traccia delle identità dei nodi prossimi (a chi si riferisce direttamente). vantaggio: è più facile il mantenimento dell’evente in caso di errori di rete, visto che si “pinga” il client chiedendo se è attivo. problema: il race condition può ancora capitare nel copiare le reference. Mark and sweep: cerca di identificare gruppi di oggetti disconessi dalla root. si utilizza un grafo cercando di trasformare il problema in una “search/graph exploration”. problemi: richiede una raggiungibilità del grafo molto stabile, scalabilità ridotta. 04 - naming (2) 6  🕑 05 - syncronization (2,5) Come detto all’inizio del corso all’interno di un sistema distribuito abbiamo assenza di un clock globale assenza di una memoria condivisa failures parziali → nasce il problema di sincronizzare le operazioni e le componenti SINCRONIZZAZIONE DEI CLOCK Come nel caso di make (compilatore per c) il time stamping permette la ricostruzione cronologica degli eventi: guardando solamente il time stamp dei file il compilatore è in grado di capire se i file sono stati modificati, e di conseguenza se è necessaria la ricompilazione → problema: è necessario che le macchine vedano lo stesso global time SINCRONIZZAZIONE DEI CLOCK FISICI I clock dei computer non sono dei veri e propri orologi, ma sono solamente dei timers (ossia metronomi). Abbiamo tre problemi: sincronizzare tutti i clock con un clock globale (accuracy) sincronizzare tutti i clock tra di loro (agreement) rispettare la monotonia del tempo (non posso andare indietro) GPS Un primo modo consiste nella localizzazione dei PC tramite GPS. Vengono utilizzati dei satelliti, perfettamente sincronizzati che emettono dei messaggi comunicando l’ora corretta nell’area coperta la posizione viene determinata dalla triangolazione di un set di satelliti con posizione nota la distanza viene misurata in base al ritardo del segnale 05 - syncronization (2,5) 1  satellite e ricevitore devono essere sincronizzati e poiché non lo sono, dobbiamo tenere conto dello sfasamento dell'orologio → problema: funziona solo in spazi aperti CRISTIAN’S Si ha un time server (passivo), ogni pc periodicamente manda una richiesta per chiedere l’ora corretta e sincronizzarsi. Bisogna tenere conto del tempo che i messaggi ci mettono ad arrivare al server e tornare indietro BERKELEY Si ha un time server attivo che periodicamente chiede e raccoglie i tempi di ciascuna macchina, fa una media e ritorna a tutti il tempo sistemato NETWORK TIME PROTOCOL (NTP) E’ il sistema più utilizzato dai sistemi operativi oggi. Tutti le macchine in internet sono connesse sotto forma di albero. I server al primo strato sono direttamente connessi a un UTC source (atomic clock), i nodi foglia rappresentano i pc degli utenti i server di livelli differenti si scambiano periodicamente messaggi per sincronizzarsi, andando a stimare l’offset tra i due clock e l’accuratezza di questa stima il server NTP manda in broadcast il tempo corretto all’interno della propria LAN LOGICAL CLOCKS In tante applicazioni non è necessario accordarsi sull’esatto tempo ma è sufficiente conoscere l’ordine con cui gli eventi si sono verificati alcune volte è sufficiente conoscere l’ordine e i rapporti di causa-effetto degli eventi se due processi non interagiscono non è necessario che siano sincronizzati SCALAR CLOCKS Viene definita la relazione happens-before → l’evento e si è verificato prima di e’ (e → e’) se : 05 - syncronization (2,5) 2  e ed e’ si verificano all’interno dello stesso processo ed e si verifica prima di e’ non appartengono allo stesso processo ma e corrisponde all’invio di un messaggio ed e’ corrisponde alla ricezione dello stesso messaggio La relazione è transitiva. Inoltre se non si verifica la relazione tra due eventi (ossia non si verifica e → e’ e nemmeno e’ → e) possiamo dire che i due eventi sono concorrenti (non possiamo dire quale si è verificato prima). LAMPORT CLOCK Ogni processo Pi ha un proprio clock logico rappresentato da un numero intero Li (all’inizio vale 0). Ogni messaggio mandato da Pi contiene il proprio clock Li. Quando un processo: invia un messaggio → Li + 1 riceve un messaggio → max(msg timestamp, Li) + 1 Se un evento happens-before un altro evento il Lamport clock sarà minore dell’altro: e → e’ ⇒ L(e) < L(e’) Nota: l’implicazione non è vera letta al contrario → viene garantito solo un ordinamento parziale (ad esempio in questo caso non possiamo dire che B si è verificato dopo E nonostante 2 > 1) Per garantire un ordinamento totale è sufficiente aggiungere l’id del processo al Lamport clock (seconda foto) → Lamport clock offre un modo molto semplice per ordinare eventi. 05 - syncronization (2,5) 3  Esercizio fatto da me, non ho la soluzione corretta TOTALLY ORDERED MULTICAST Assunzioni: link affidabili e FIFO I messaggi vengono mandati in multicast con il timestamp del mittente. Quando un processo riceve un messaggio lo inserisce in una coda (ordinata in base ai timestamp) e invia in multicast un ACK a tutti gli altri processi. Un messaggio ricevuto viene poi mandato all’applicazione se: è il primo nella coda tutti gli ack sono stati ricevuti VECTOR CLOCKS Risolvono il problema del Lamport clock. Ogni processo Pi mantiene un vettore Vi di N elementi, dove N rappresenta il numero di processi. Alla posizione j- esima è contenuto il numero di eventi avvenuti in Pj (è come se ogni processo avesse il clock di tutti gli altri processi). Regole: inizialmente Vi[j] = 0, per tutti i,j evento in Pi → incremento del proprio clock (Vi[i] = Vi[i] + 1) invio di un messaggio da Pi → incremento del proprio clock e inserimento del vettore nel messaggio (t = Vi) ricezione di un messaggio in Pi → incremento del proprio clock e aggiornamento di ciascun altro valore del proprio vettore se l’elemento ricevuto è maggiore (Vi[j] = max(Vi[j], t[j] per tutti j ≠ i) A differenza dei Lamport clocks, i vector clocks rispecchiano pienamente la relazione happens-before. Infatti il confronto dei vector clocks di due eventi ci permette sia di dire se sono legati da una relazione happens-before (concludendo chi è avvenuto prima) sia di dire che due eventi sono paralleli: e → e’ ⟺ V(e) < V(e’) ossia V[j] ≤ V’[j] per tutti j e V≠ V’ 05 - syncronization (2,5) 4  e || e’ ⟺ V(e) || V(e’) ossia ¬(V < V’) ∧ ¬(V < V’) VECTOR CLOCKS FOR CAUSAL DELIVERY Versione rivisitata dei vector clocks che permette di mantenere un ordine causale corretto (utile ad esempio in chat di domande e risposte, vogliamo che vengano mostrate prima le domande delle relative risposte). il clock viene incrementato solo all’invio di un messaggio aspetto di ricevere i messaggi precedenti prima di “accettare” e mostrare il messaggio MUTUAL EXCLUSION Assunzioni: channel e processi affidabili La mutua esclusione è il processo che previene interferenza tra diversi processi e garantisce coerenza nell’accesso di risorse condivise. Consiste nel dare l’accesso ad esse a solo un processo alla volta. Requisiti: safety property: al più un processo alla volta può eseguire la sezione critica liveness property: tutte le richieste di entare/uscire dalla sezione critica prima o poi devono avere successo (no deadlock, no starvation) 05 - syncronization (2,5) 5  optional: se una richiesta happens-before un’altra richiesta, deve essere eseguita prima CENTRALIZED SOLUTION La soluzione più semplice prevede l’utilizzo di un server centrale che coordina gli accessi. Il server gestisce gli accessi utilizzando un “token”, che può essere richiesto e rilasciato dai processi tramite messaggi. Viene garantita facilmente la mutua esclusione e correttezza ma essendo centralizzato abbiamo un singolo punto di failure e il server può diventare il collo di bottiglia nelle prestazioni. MUTUAL EXCLUSION WITH LAMPORT SCALAR CLOCKS I processi collaborano tra di loro per decidere l’ordine. Per richiedere l’accesso a una risorsa il processo manda in multicast la richiesta (incluso se stesso) con il timestamp. Quando un processo riceve una richiesta: risponde con l’ACK se non ha accesso alla risorsa e non è interessato inserisce la richiesta in una coda locale se sta utilizzando la risorsa se è interessato all’utilizzo della risorsa e ha già mandato la richiesta confronta il timestamp ricevuto con il prioprio, e se: il timestamp ricevuto è minore risponde con un ACK il timestamp ricevuto è maggiore inserisce la richiesta nella coda locale Al rilascio della risorsa, il processo che la stava utilizzando manda un ACK a tutti i processi presenti nella sua coda locale. L’accesso alla risorsa viene poi concesso al processo che ha ricevuto l’ACK da tutti gli altri processi TOKEN RING I processi sono organizzati ad “anello”. L’accesso alla risorsa viene dato tramite un “token” che circola nell’anello in una singola direzione. Se un processo non è interessato, inoltra il token al processo successivo. Se un processo vuole utilizzare la risorsa trattiene il token, alla fine dell’utilizzo lo inoltra al nodo successivo. 05 - syncronization (2,5) 6  LEADER ELECTION Assunzioni: è possibile distinguere i nodi, ciascun nodo conosce gli altri nodi e il loro ID Alcuni algoritmi distribuiti richiedono un processo coordinatore (leader) e che tutti gli altri processi siano d’accordo sull’elezione del nuovo leader in caso il precedente non sia più disponibile BULLY ELECTION ALGORITHM Assunzioni: link affidabili, è possibile determinare chi è crashato Algoritmo che vede la nomina del processo con ID più alto come leader. Quando un processo nota che il leader non risponde inizia una elezione inviando un messaggio ELECT ai processi con ID maggiore. Se un processo con un ID più grande riceve un messaggio ELECT inizia una nuova elezione. Se nessuno risponde il processo vince e invia un messaggio COORD a tutti i processi con un ID inferiore. Quando il processo che è crashato “risorge” inizia una nuova elezione. RING-BASED ALGORITHM I nodi (processi) vengono organizzati in una topologia ad anello (fisicamente o logicamente). Quando un processo rileva il crash del leader invia al nodo adiacente un messaggio ELECT contenente il proprio ID. Quando un processo riceve un messaggio ELECT: se l’ID del processo non è all’interno del messaggio, lo aggiunge e inoltra il messaggio al primo nodo vivo successivo se l’ID è già presente la tipologia del messaggio diventa COORD 05 - syncronization (2,5) 7  Quando i processi ricevono il messaggio di tipo COORD considerano il processo con ID maggiore come nuovo leader. COLLECTING GLOBAL STATE Il global state di un sistema distribuito consiste nell’insieme dei local state di ciascun processo e dei messaggi in transito sui vari collegamenti. Non avendo un clock globale non è possibile catturare un global state ma è solo possibile catturare lo stato di ciascun processo in momenti diversi. Uno distributed snapshot rappresenta uno stato (coerente e globale) in cui il sistema distribuito può essere stato → per ricostruirlo viene utilizzato il tool concettuale chiamato cut: un cut si dice consistent se per ogni evento e che include esso include anche tutti gli eventi avvenuti prima di e (se un messaggio è stato ricevuto, il messaggio deve anche essere stato inviato, il contrario non è necessario) DISTRIBUTED SNAPSHOT (Chandy-Lamport) Assunzioni: FIFO, link e nodi affidabili, grafo fortemente connesso E’ un algoritmo che permette di costruire un consistent cut, senza interrompere il sistema. Ciascun processo può iniziare uno snapshot registrando il proprio stato interno mandando un token su tutti i channel in uscita per segnalare l’inizio dello snapshot iniziando a registrare i local state (messaggi in arrivo dai channel in entrata) Quando un processo riceve un token: 05 - syncronization (2,5) 8  se non ha già iniziato a registare lo snapshot locale, effettua le stesse azioni precedenti in ogni caso smette di registrare i messaggi in entrata dal channel da cui è arrivato il token Il processo termina con la ricezione dei token da tutti i canali in entrata. A questo punto è possibile inviare lo snapshot ricavato ad un collector che può ricostruire il global state. Salvandolo poi su disco permette in caso di crash totale di ripristinare l’intero sistema distribuito ad un punto in cui la correttezza è garantita. TERMINATION DETECTION Vogliamo sapere quando un’esecuzione è stata completata o è in stato di deadlock. Tutti i processi dovrebbero essere inattivi e non dovrebbero esserci messaggi in transito nel sistema (però alcuni potrebbero non essere stati processati e di conseguenza qualche processo potrebbe non essere più inattivo). Come possiamo rilevare la terminazione? Una soluzione semplice, proposta da Tanenbaum, utilizza snapshot distribuiti e la nozione di predecessori e successori nei processi che inviano e ricevono token. Tuttavia, questa soluzione si è rivelata sbagliata se ci sono nodi che sono successori di più nodi (ciclo). DIJKSTRA-SCHOLTEN TERMINATION DETECTION Funziona con specifici tipi di algoritmi chiamati diffusing computations (algoritmi in cui all’inizio tutti i processi sono in stato di idle tranne uno e un processo si attiva con la sola ricezione di messaggi) ogni processo tiene traccia dei processi a cui invia messaggi “svegliandoli” → si crea un albero dove ogni nodo padre ha come figli i processi a cui ha inviato messaggi se un nodo era già “sveglio” non deve essere aggiunto come figlio in quanto è già figlio di qualche altro processo quando un nodo non ha figli e termina comunica al padre di essere rimosso DISTRIBUTED TRANSACTIONS Transazione: insieme di operazioni READ/WRITE racchiuse tra una BEGIN_TRANSACTION e una END/ABORT_TRANSACTION. Rispetta le proprietà ACID: 05 - syncronization (2,5) 9  atomic, la transazione viene eseguita indivisibilmente consistent, la transazione non viola invarianti di sistema isolated (o serializable), transazioni concorrenti non si interferiscono durable, una volta eseguita una transazione, i cambi sono permanenti Una transazione può essere: flat: transazione centralizzata, proprietà ACID garantite facilmente nested: ogni transazione consiste in un insieme di sotto-transazioni in altri DB indipendenti; in caso di abort di una singola sotto-transazione, l’intera transazione deve fallire distributed: le transazioni possono READ/WRITE da multipli DB contemporaneamente ATOMICITY 1. Private workspace: viene creata una copia di ciò che la transazione modifica. Se la transazione viene abortita questo workspace viene eliminato, altrimenti le modifiche vengono copiate sul file → approccio pessimistico 2. Writeahead log: si va a scrivere e modificare direttamente il file ma si vanno a scrivere dei log su ciò che è stato fatto. Se la transazione va a buon fine, le modifiche sono già state effettuate, in caso contrario si annullano tutte le operazioni tramite i log → approccio ottimistico CONCURRENCY SERIALIZABILITY 05 - syncronization (2,5) 10  Sono possibili gli interleaving tra le varie transazioni. Lo scheduler deve però garantire che il risultato che si ottiene è lo stesso che si otterrebbe con l’esecuzione delle transazioni in modo seriale (una dopo l’altra). Due approcci: Two-Phase Locking (2PL): quando un processo ha bisogno di accedere a dei dati richiede allo scheduler il lock, una volta rilasciato non può più riceverlo. La serializzabilità è rispettata ma può portare a deadlock centralized 2PL: un singolo lock manager centralizzato primary 2PL: ciascun data item ha il proprio lock manager associato distributed 2PL: lock manager distribuiti timestamp ordering: non si utilizzano le lock ma si cerca di ordinare esplicitamente le operazioni per ottenere un ordine equivalente all’esecuzione seriale PESSIMISTIC TIMESTAMP ORDERING Ciascuna transazione ha una timestamp (Lamport clock). vengono definite la write timestamp (tswr(x)) e la read timestamp (tsrd(x)) che rappresentano le ultime transazioni committate di write e read quando lo scheduler riceve una richiesta di write(T,x) al tempo ts se ts > tsrd(x) e ts > tswr(x) esegue una tentative write xi con timestamp tswr(xi) altrimenti T viene abortita siccome la richiesta è arrivata troppo tardi quando lo scheduler riceve una richiesta di read(T,x) al tempo ts se ts > tswr(x) esegue la read e setta tsrd(x) = max(ts, tsrd(x)) se ts > tswr(xi) aspetta che la tentative write diventi effettiva o no altrimenti T viene abortita siccome la richiesta è arrivata troppo tardi 05 - syncronization (2,5) 11  OPTIMISTIC TIMESTAMP ORDERING Si basa sull’assunzione che i conflitti sono rari. L’idea è di eseguire le transazioni e gestire i conflitti in un secondo momento, registrando i timestamp in cui ciascuna variabile è stata “toccata” da ciascuna transazione al commit viene controllato se c’è qualche variabile “toccata” che è stata “toccata” anche da altre transazioni. In caso affermativo la transazione viene abortita, altrimenti no DISTRIBUTED DEADLOCKS Per gestire le deadlocks distribuite esistono diversi approcci: il primo consiste nell’ignorarle (poco sensato), rilevarle e sistemare (detection and recovery), evitare che si verificano a livello di design: centralized deadlock detection: ogni macchina mantiene aggiornato un grafo delle risorse inviandolo ad un coordinatore centralizzato. Gli aggiornamenti possono essere inviati periodicamente o ad ogni modifica del grafo. Non funziona molto bene a causa di false deadlock distributed deadlock detection (Chandy-Misra-Haas): i processi possono richiedere più risorse contemporaneamente. Quando un processo si blocca manda un messaggio contentente la tupla (initiator, sender, receiver) ai processi che stanno utilizzando le risorse che necessita. Se il messaggio torna al sender si ha trovato un cycle, ossia una deadlock distributed prevention: utilizzo di global timestamp per prevenire le deadlock wait-die algorithm: quando un processo necessita una risorsa utilizzata da un altro processo può aspettare (wait) solo se ha uno timestamp minore (ossia è più vecchio). Altrimenti viene killato wound-wait algorithm 05 - syncronization (2,5) 12  🚨 06 - Fault Tolerance (2) Un sistema si dice fault tolerant (tollerante ai guasti) se può fornire i propri servizi nonostante la presenza di guasti. Un sistema quindi fallisce quando non è in grado di fornire i suoi servizi. Un failure (fallimento) è il risultato di un errore. Un errore è causato da un fault (guasto). Esempio: non controllare la divisione per zero (fault) causa l’errore divisione per zero. Classificazioni dei guasti: transient: capitano una volta e svaniscono. intermittent: appaiono e svaniscono senza una ragione. permanent: continuano ad esistere finchè i componenti fallimentari non vengono riparati. Ci sono diversi tipi di failure - failure model: 1. Omission fail4ure: qualcosa che dovrebbe succedere non succede. comuni nei processi. 2. Byzantine failure: succede qualcosa di diverso del previsto. comuni nei canali. 3. Timing failure: uno dei limiti temporali viene violato (solo per sistemi sincroni). La tecnica principale di proteggersi da un failure è la ridondanza delle informazioni (oltre al pacchetto invio altre informazioni), del tempo (reinvio dei pacchetti in assenza di un ACK), fisica (usare canali multipli). 06 - Fault Tolerance (2) 1  esempio di ridondanza Fisica u Protection against process failures La ridondanza può essere usata per mascherare dai processi che causano guasti, utilizzando i redundant process group, che sono gruppi di processi che colletivamente possono fare il lavoro di un singolo processo. facendo così se alcuni dovessero fallire, i rimanenti possono continuare a lavorare. usando questi gruppi potrebbe essere difficoltoso gestire l’appartenenza a gruppi distribuiti. Per cui sono necessari degli annunci multicast di join/leave, questo però può complicare il mantenimento dell’integrità del gruppo, la cui struttura in alcuni casi andrebbe ricostruita. In generale, se un processo fallisce in modo silenzioso, k + 1processi permettono al sistema di essere k-fault-tolerant. nel caso di byzantine failure le cose si complicano: sono necessari 2k + 1processi, questo perchè servono altri server per verificare se il primo ha prodotto risultati errati, tramite un meccanismo a voti. Un numero di task potrebbe richiedere che i membri di un gruppo si accordino per procedere. visto che stiamo trattando i guasti, vogliamo che tutti i processi “sani” raggiungano un accordo. la decisione viene presa dai processi stessi, per esempio da un meccanismo a votazione. Questo è anche noto come il “consensus problem”: un gruppo di processi si deve accordare su un valore (che non può essere qualsiasi). precisamente abbiamo queste condizioni: ogni processo inizia con un valore iniziale tutti i processi sani devono raggiungere una decisione basata su questi valori Si devono tenere le seguenti prorprietà 06 - Fault Tolerance (2) 2  agreement: nessun processo decide un valore diverso validity: se tutti i processi iniziano con valore v, allora vè l’unica possibile scelta termination: prima o poi tutti i processi sani decidono. il consenso non è possibile in presenza di una arbitrary communication failure. ovvero quando i processi sono autorizzati a fallire. in particolare: per i crash failure: assunzioni: sistema sincrono, i processi evolvono in round sincroni, canali affidabili. si può raggiungere un accordo in almeno f+1 round, dove f è un limite dei numeri di fails. FloodSet algorithm: si specifica un valore di dafualt v0 , dopodichè ogni processo tiene ​ una variabile w inizializzata con il suo valore iniziale. per f + 1round ogni processo manda w agli altri e aggiunge quello ricevuto a w . finiti i round, se ∣w∣ = 1, si decide per l’unico elemento di w , altrimenti per v0 . ​ per i byzantine failure: lamport nel 1982 ha dimostrato che se ci sono mprocessi guasti, sono necessari 2m + 1processi sani per raggiungere un accordo per un totale di 3m + 1 processi. Per i sistemi asincroni Fischer, Lynch e Paterson hanno dimostrato che in generale anche un singolo failure è abbastanza per non poter raggiungere un consenso (FLT theorem). Reliable group communication Fixed groups + non-faulty processes. tutti i membri del gruppo devono ricevere il multicast. è facile da implementare su un multicast non affidabile. ci sono diversi approcci: 06 - Fault Tolerance (2) 3  1. ACK positivi: il destinatario manda un ACK dopo aver ricevuto il messaggio. se non viene ricevuto, il processo mittente lo reinvia. questo processo può causare l’ack implosion se tutti ne inviano contemporaneamente. 2. ACK negativi: il destinatario manda un NACK dopo un ritardo random indicando quale pacchetto è mancante. questo approccio ottimistico è più scalabile perchè previene che tanti NACK siano inviati contemporaneamente e riduce la probabilità di travolgere il mittente. lo svantaggio è che tutti i processi devono processare i NACK 3. Hierarchical Feedback Control: è un evoluzione dei due metodi precedenti (basic approaches). i destinatari sono raggruppati, ogni gruppo ha un coordinatore. questi gruppi formano una struttura ad albero, dove il mittente è la root. quest’ultimo gestisce gli acknoledgments e le ritrasmissioni all’interno del proprio gruppo e comunica con il suo genitore coordinatore se necessario. Groups are not fixed or faulty processes: in questo caso è spesso necessario che il messaggio sia consegnato o a tutti i membri del gruppo o a nessuno di essi, e che l’ordine dei messaggi sia lo stesso per tutti i destinatari. questo è conosciuto come l’atomic multicast problem. 1. il close synchrony non può essere raggiunto in presenza di failure. dice che i messaggi multicast possono essere considerati come eventi 06 - Fault Tolerance (2) 4  istantanei e i processi che ricevono i messaggi vedono gli eventi nello stesso ordine. 2. il virtual synchrony è il modello più debole che rimpiazza il precedente. è una forma di multicast affidabile capace di risolvere l’atomic multicast problem. ha 3 requisiti: a. i processi crashati vengono eliminati dal gruppo e dovranno joinare in seguito. b. i messaggi da un processo corretto sono processati da tutti i processi corretti c. i messaggi da un processo che sta fallendo sono processati o dai membri corretti o da nessuno. d. solo i mesaggi rilevanti sono ricevuti in un ordine specifico. il group view è il set di processi a cui un multicast dovrebbe consegnare, esattamente come visualizzato dall’utente al momento dell’invio. questo cambia ogni volta che il processo joina o lascia il gruppo. ✅ caso a) p manda il messaggio, p crasha → il messaggio viene scartato da tutti, dopo vengono informati che p è crashato. (nessuno riceve il messaggio) ✅ caso b) p manda il messaggio, viene consegnato a tutti, p crasha. 06 - Fault Tolerance (2) 5  ❌ casi c e d) p manda il messaggio, p crasha, i messaggi vengono consegnati dopo la notifica che p è crashato. Recovery techniques quando i processi riprendono a lavorare dopo un failure, devono essere riportati allo stato corretto. ci sono due diversi tipi di recupero: backward recovey: il sistema è riportato indietro da uno stato corretto precedentemente salvato forward recovery: il sistema è portato in un nuovo stato corretto. Analizziamo la prima tipologia, dove possiamo trovare due principali tecniche. 1. Checkpointing: consiste nel salvare periodicamente lo stato di ogni processo senza il bisogno di sincronizzare gli altri processi, visto che la sincronizzazione non è pratica nei ds. a. indipendent checkpointing: ogni processo registra indipendentemente il suo proprio stato. quando si verifca un failure, tutti i processi si fermano e inviano le loro informazioni al coordinatore globale, il quale costruisce un grafo di dipendenze e computa una linea di recupero. la linea di recupero può essere computata con due approcci diversi: i. rollback-dependency graph: se c’è una dipendenza tra due intervalli, transformiamo quella dipendenza nella dipedenza tra due checkpoint. dopodichè partendo da quello che viene inizialmente segnato come il “crash failures”, proseguiamo a segure le frecce e rimuovendo gli stati che sono raggiungibili da esse. la linea di recupero è computata segnando i nodi corrispondenti ai failure states e poi segnando tutti quelli che sono raggiungibili da uno di loro. ogni processo torna all’ultimo check point non segnato. ii. checkpoint-dependency graph: il processo è uguale al precedente, ma si aggiunge la dipendenza dagli stati iniziali dell’intervallo agli stati finali dell’intervallo. se due checkpoint hanno una dipendenza, il taglio è inconsistente. in quel caso serve eliminare lo stato ricevente della freccia. poi, si prende l’ultimo checkpoint di ogni processo e si controlla se hanno qualche dipendenza. in questo modo eliminiamo gli stati, fino a che tutti i checkpoint sono indipendenti tra di loro. 06 - Fault Tolerance (2) 6  b. coordinated checkpointing: la tecnica precedente non è molto conveniente a causa della compressità degli algoritmi. la soluzione è coordinare i checkpoint, non vengono mai presi checkpoint inutili. una soluzione semplice a questo può essere: il coordinatore invia 𝐶HKP-REQ (checkpoint request) i destinatari prendono un checkpoint e mettono in coda i messaggi in uscita. quando hanno fatto, inviano un ACK al coordinatore. quando hanno fatto tutti, il coordinatore invia 𝐶HKP-DONE 2. Logging: è un approccio che può essere usato insieme al checkpointing, si può iniziare da un checkpoint e riprodurre le azioni salvate in un log file. bisogna saper distinguere tra i messaggi che sono stati loggati e quelli che non lo sono. un messagio è stabile se non può più essere perso. per esempio se è stato scritto in uno storage stabile. per ogni messaggio m instabile si definisce: DEP (m) :i processi che dipendono dalla consegna di m. COP Y (m) :i processi che hanno una copia di m, ma non sono ancora salvati in uno storage stabile. sono quei processi che forniscono una copia di mche potrebbe essere per riprodurlo. 06 - Fault Tolerance (2) 7  🤝🏼 07 - agreement (2) ATOMIC COMMIT E’ una forma di agreement molto utilizzata nei DBMS. Garantisce atomicità (A in ACID) una transazione può essere committata (va a buon fine) o abortita, nessuno stato “intermedio” è possibile se viene committata, le modifiche sono durature se viene abortita non ci sono effetti In caso di DB condiviso o partizionato su nodi multipli o tutti i nodi committano o tutti abortiscono se un nodo crasha, tutti devono abortire TWO PHASE COMMIT (2PC) 2PC è un protocollo sicuro ma bloccante che soddisfa la weak termination condition, ossia permette a tutti i partecipanti di decidere. Il protocollo funziona in caso di assenza di failures. Le principali failures che possono succedere sono: se un partecipante fallisce o diventa irraggiungile, dopo un timeout il coordinatore considera come se il partecipante avesse votato “abort” 07 - agreement (2) 1  se il coordinatore fallisce se un partecipante si trova in “init state” può decidere di abortire (nessun partipante può aver già ricevuto una global commit) se un partecipante si trova in “ready state” non può decidere da solo, può aspettare il recovery del coordinatore o chiedere la decisione ad altri partecipanti Se tutti i partecipanti si trovano in “ready state” oppure aspettano tutti il recovery il protollo è bloccante! Nota: il coordinatore scrive tramite dei log tutti i suoi stati, sopravvive ai crash THREE PHASE PROTOCOL (3PC) Protocollo che cerca di risolvere il problema del 2PC (ossia il fatto che sia bloccante) aggiungendo un nuovo stato, per evitare la presenza (come in 2PC) di uno stato direttamente connesso ad abort e commit (più costoso rispetto a 2PC). Abbiamo 3 fasi: prepare: il coordinatore chiede se possono committare. I partecipanti rispondo con la loro decisione (agreement o disagreement) prepare commit: se tutti i particanti hanno risposto positivamente il coordinatore invia un messaggio pre-commit. I partecipanti si preparano a committare global commit: il coordinatore invia un messaggio global-commit per finalizzare la transazione Possibili failures: se un singolo partecipante fallisce 07 - agreement (2) 2  se il coordinatore si trova in “wait state” può assumere abort (nessun partecipante può trovarsi in “pre-commit state”) se il coordinatore è bloccato in “pre-commit state” può in modo sicuro committare e chiedere al partecipante che è fallito di commitare quando si riavvia (se si trova in pre-commit significa che ha ricevuto “agree” da parte di tutti) se il coordinatore fallisce se un partecipante si trova in “init state” può decidere di abortire se un partecipante si trova in “ready state” può contattare un altro partecipante e abortire o committare in base allo stato in cui si trova Ricapitolando: 2PC sacrifica liveness (è un protocollo bloccante) 3PC più robusto ma più costoso e poco usato. Può sacrificare liveness in presenza di partizioni di rete → FLP theorem: non puoi avere sia liveness e safety in presenza di partizioni di rete in un sistema asincrono REPLICATED STATE MACHINES E’ un algoritmo di consenso generale che permette ad un insieme di macchine (server) di lavorare come se fossero un gruppo. Lavorano su identiche copie (repliche) degli stessi dati e offrono un servizio duraturo anche se qualche macchina dovesse fallire. I client vedono esse come una singola macchina fault-tolerant. 07 - agreement (2) 3  L’idea è che il client si connetta ad un leader che scrive le operazione in un log. Questo log contiene una sequenza di operazioni che vengono propagate agli altri nodi del sistema attraverso un protocollo di consenso. L’obbiettivo è mantenere una vista del sistema coerente nonostante failures e problemi di rete. PAXOS E’ stato l’algoritmo di riferimento per il consenso per 30 anni. Presenta però alcuni problemi: permette agreement per una singola decisione, non una sequenza (risolto però da una versione successiva chiamata multi-paxos) è molto difficile da capire è molto difficile da utilizzare RAFT Protocollo equivalente a multi-paxos in termini di assunzioni, garanzie, performance con l’obbiettivo però di essere molto più semplice e facile da utilizzare. Si basa sulla gestione di un replicated log, gestito da un leader (rieletto in caso di crashes tra i server con il log aggiornato): il leader accetta comandi dai client, aggiungendoli al suo log il leader replica il suo log agli altri server, inviando un messaggio AppendEntries periodicamente Ciascun nodo può trovarsi in 3 stati: follower (iniziale per tutti), leader, candidate se i follower non hanno notizie del leader per un po’ di tempo (non ricevono AppendEntries entro un timeout) diventano candidate, iniziando una nuova 07 - agreement (2) 4  elezione. Raft utilizza dei timeout randomici per prevenire che si verifichino diverse elezioni contemporaneamente server states leader election Raft divide il tempo in terms, numerati con interi consecutivi. Ogni term inizia con un’elezione, di conseguenza ci può essere massimo un leader per term (può verificarsi però uno split vote, ossia nessuna maggioranza e nessun leader eletto). Ogni server mantiene un valore “term” corrente, scambiato in ogni comunicazione che viene utilizzato per determinare l’obsolescenza di dati se server diversi hanno lo stesso significa che salvano lo stesso comando e i log precedenti sono uguali solo i candidate con il valore di term più alto e log completi possono essere eletti leader In termini di comunicazione con i client, è garantito che il client interagiscono sempre con il leader, questo perché quando un client si avvia si connette a un server random che gli comunica il leader corrente. USE IN DISTRIBUTED DBMS Nei moderni DBMS i database sono partizionati e ogni partizione è replicata. Due livelli: replicated state machine (i.e Raft) per garantire che la singola partizione non fallisca, ossia ogni partizione viene gestita da un insieme di macchine che lavorano insieme come se fosse una sola 2PC esegue atomic commit tra le varie partizioni: si assume che sia il coordinatore (transaction manager) che i partecipanti (partizioni) non falliscano essendo replicati. Si assume che i channel siano affidabili, è 07 - agreement (2) 5  sufficiente che la maggioranza dei nodi in una determinata partizione siano raggiungibili BYZANTINE CONDITIONS Fino ad ora l’unica assunzione fatta è che non si verifichino byzanine failures. Vediamo ora come state machine replication può essere esteso per considerare anche essi. BLOCKCHAINS La blockchain, come nel caso delle criptovalute, si basa sul consenso distribuito (tutti devono essere d’accordo sul current balance di ciascun user). Le criptovalute possono essere viste come delle replicated state machines, vengono registrate e salvate in un replicated ledger (log) tutte le operazioni (transazioni/pagamenti). Si tratta di un ambiente byzantine in quanto, essendo aperta a tutti, possono “participare” degli user malintenzionati (”double spend” o creazione di copie incoerenti del log). BITCOIN BLOCKCHAIN Nel caso di Bitcoin, la blockchain rappresenta il ledger pubblico che registra le transazioni. L’aggiunta di un blocco alla catena (una transazione) richiede la risoluzione di un problema matematico complesso (si risolve con brute force ed è adattato alla potenza di calcolo) la cui verifica è però molto semplice. Di conseguenza è molto improbabile che uno user riesca a risolvere due volte il problema contemporaneamente, andando ad aggiungere due transazioni (double spend). 07 - agreement (2) 6  08 - replication and consistency (2) la replication è utilizzata per garantire fault tolerance attraverso la ridondanza, per incrementare le performance permettendo la condivisione del carico del lavoro e riducendo la latenza per le singole richieste. può anche aumentare la disponibilità replicando i dati più vicini agli utenti. esempi: piattaforme collaborative (Google Doc, Microsoft Office), file system distribuiti, Content delivery networks. Va da sè che la sfida principale della replication è garanitire la consistenza (consistency) dei dati tra tutte le repliche. la propagazione dei cambiamenti di una replica potrebbe causare dei conflitti. l’obiettivo è quindi quello di mantenere consistenza minimazzando però il communication overhead. idealmente vorremmo vedere il dato come una singola copia, che ovviamente è impossibile. bisogna quindi affidarci a dei consistency model, che sono dei contratti tra i processi e il data store. E’ possibile dividere i consistency model in base alle promesse fatte nei contratti. guarantees on content: massima “differenza” tra le versioni salvate in diverse repliche. esempio: una rete di sensori wireless che si aggiorna solo se si raggiunge una certa differenza rispetto al valore salvato precedentemente. guarantees on staleness: massimo tempo tra un cambio e la sua propagazione a tutte le repliche. esempio: la cache nei browser. guarantees on the order of the updates: vincoli dei possibili comportamenti in caso di conflitti. 08 - replication and consistency (2) 1  Consistency protocols i consistency protocols implementano consistency model. sono progettati tenendo a mente diverse strategie per gestire diverse ipotesi. Single Leader Protocols: una delle repliche è progettata per essere il leader. il client per poter scrivere deve inviare delle write request al leader, successivamente il leader procede a aggiornare le altre repliche, chiamate followers. invece le read request possono essere inviate anche ai followers. i followers possono aggiornarsi in modo: sincrono: l’operazione di scrittura si completa dopo che il leader ha ricevuto una risposta da tutti i follower. è più sicuro ma può causare molta latenza. i follower possono recuperarsi dai failure chiedendo degli aggiornamenti alle altre repliche (catch up recovery). asincrono: l’operazione di scrittura si completa dopo che il nuovo valore è salvato dal leader, dopodichè i follower si aggiorneranno in modo asincrono. ibrido (semi-sincrono): l’operazione di scrittura si completa dopo che il leader riceve una risposta da almeno k repliche, dove k è un parametro di configurazione in molti replicated database. i primi due metodi sono molto adottati nei database distribuiti (PostgreSQL, MySQL, Oracle, …). Non ci possono essere conflitti write-write ma read-write si. Multiple Leaders Protocols: le scritture vengono eseguite da diverse repliche concorrentemente. non essendoci un singolo leader vuol dire che nessuna entità singola può decidere l’ordine di scrittura, questo può condurre a conflitti write-write. Questi protocolli sono spesso adottati nei geo-replicated settings. sono più complessi dei precedenti ma si può ovviare ai conflitti in diversi modi (i conflitti non sono critici). Leaderless Protocols: i client possono contattare più repliche (a differenza dei primi due, dove contattano un singolo nodo) per mandare richieste di lettrura o scrittura. Questi protocolli usano dei protocolli basati sul quorum per evitare conflitti. ovvero serve una maggioranza di repliche che votano per la scrittura o meno, e 08 - replication and consistency (2) 2  un’altra per quale valore leggere. Data-centric consistency models 1. Sequential consistency il risultato è come se le operazioni di tutti processi fossero eseguite in un ordine sequenziale, e le operazioni di ogni processono apparissero in questa sequenza nell’ordine specificato dal suo programma in altre parole, tutti i processi si accordano su una sequenza. è il tipo più “forte” di consistency guarantee * Le operazioni all’interno di un processo non possono essere riordinate. è necessario che tutti i processi vedano lo stesso interlacciamento di operazioni senza considerare il tempo. Legenda: ogni linea rappresenta un processo (P1, P2, P3, P4), le operazioni (W (x)a: il valore a è scritto nell’oggetto data x, R(x)b: il valore bè letto dall’oggetto data x) sono in ordine cronologico. In pratica, tutte le repliche devono essere d’accordo su un dato ordine delle operazioni, questo può essere ottenuto tramite diverse implementazioni: Single Leader Implementation, con una replicazione sincrona, così che ogni scrittura passa da un solo leader che riordina le operazioni. Assunzioni: i link sono FIFO, i client sono “sticky” (leggono sempre dalla stessa replica). Leaderless implementation, con un approccio basato sul quorum, i client contattano più repliche per le richieste read/write. viene effettuato un aggiornamento solo al raggiungimento del quorum tra server sul numero di versione da assegnare. Generalmente: 08 - replication and consistency (2) 3  NR + NW > N per evirare conflitti read-write. ciò assicura che le repliche coinvolte nelle operazioni di lettura e scrittura non si sovrappongano. NW > N/2per evirare conflitti write-write. ciò assicura che più di metà delle repliche devono essere d’accordo per procedere ad una operazione di scrittura. dove NR(NW )è il numero di nodi che il client contatta per accedere alla lettura (scrittura) e N è il numero di tutte le repliche. Il sequential consistency limita la disponibilità, ciò causa un’alta latenza dovuta alle interazioni sincrone e blocca i client in caso di partizioni di rete. 2. Linearizability Ogni operazione deve sembrare che abbia effetto istantaneo in un momento tra il suo inizio e il suo completamento. è la più “forte” forma di consistency guarantee con le assunzioni che ci voglia del tempo per eseguire le operazioni, in presenza di replication. è un recency guarantee (garanzia di recenza), ovvero quando un client completa una scrittura nel data store tutti i client devono vedere l’effetto della scrittura, questo da l’illusione di avere una singola copia del data store. la differenza con la precedente è che include una notazione temporale: le operazioni si comportano come se appartengono ad un preciso istante di tempo. questo garantisce un’ordine globale. è una proprietà composta, se le operazioni su singole variabili sono linearizable allora lo è anche la global schedule. 3. Causal consistency Le scritture potenzialmente correlate causalmente devono essere viste da tutti i processi nello stesso ordine. Le scritture concorrenti possono essere viste in qualsiasi ordine su tutte le macchine. è una forma più “debole” di consistency rispetto alle precedenti, ma fornisce un bilanciamento tra disponibilità e consistency. 08 - replication and consistency (2) 4  la causal consistency indebolisce la sequential consistency basata sulla notazione Lamport di relazione happened-before, ed è un ordine parziale. ciò significa che solamente le operazioni correlate causalmente devono essere ordinate rispetto alle altre, mentre quelle concorrenti possono apparire in ordine differente. L’ordine causale viene definito nel seguente modo: la scrittura W del processo P è ordinato causalmente dopo ogni operazione O dello stesso processo, anche se W e O sono eseguiti su variabili diverse. la lettura Rdel processo P sulla variabile X è ordinata causalmente dopo una precedente scrittura W su P sulla stessa variabile. l’ordine causale è transitivo. le operazioni non ordinate causalmente sono dette concorrenti. La Causal consistency ha un overhead più piccolo, ciò favorisce il suo utilizzo negli ambienti distribuiti. è più facile da implementare. L’implementazione multi leader è possibile e abilità i concurrent updates. l’idea è quella che le scritture sono etichettate temporalmente (timestamp) con un vector clock. questa implementazione è highly available. 4. FIFO consistency. Le scritture fatte da un singolo processo sono viste da tutti gli altri nell’ordine in cui sono state emesse, le scritture da 08 - replication and consistency (2) 5  processi differenti possono essere viste in qualsiasi ordine su diverse macchine. in altre parole, la causalità tra i processi viene eliminata. è molto facile da implementare, anche con soluzioni multi-leader. Riassunto dei modelli data-centric: Consistency Descrizione Tutti i processi devono vedere tutti gli accessi condivisi nello stesso Linearizable ordine. Le operazioni si comportano come se avessero un posto preciso nel tempo. Tutti i processi vedono tutti gli accessi condivisi nello stesso ordine. Sequential Gli accessi non sono collocati nel tempo Tutti i processi vedono gli accessi condivisi collrelati causamente nello Causal stesso ordine. Tutti i processi vedono le scritture da ogni altro nell’ordine a cui sono FIFO abituati. Le scrutture di processi differenti possono essere viste in un altro ordine. Eventual consistency: Ci sono situazioni dove non ci sono gli aggiornamenti simultanei e sono presenti per lo più letture, come ad esempio nella cache dei browser o nel DNS. in questi sistemi, spesso è sufficiente l’efficient consistency. è garantito che alla fine, prima o poi, gli aggiornamenti verranno propagati a tutte le repliche. è molto popolare per 3 ragioni principali: molto facile da implementare. 08 - replication and consistency (2) 6  ci sono molti pochi conflitti nella pratica. tipi di dati dedicati. Client-centric consistency Models Viene a meno l’assunzione di sticky client. in questi modelli, il client può cambiare dinamicamente la replica a cui si connette. forniscono garanzie sugli accessi al data store dalla prospettiva del singolo client. Propietà Definizione Esempio Una volta che un processo legge un valore da una replica, non leggerà mai Monotonic Reads un thread di un forum più un valore più vecchio da un’altra replica. Le scritture di un processo vengono Monotonic Writes i commenti di un post completate in ordine. un processo vedrà le proprie scritture la home dopo che fai Read Your Writes nelle successive letture. un post le scritture di un processo rispecchiano le conversazioni Writes follow reads l’ultimo valore letto. tramite chat Design strategies Ci sono ulteriori complicanze nel progettare un replicated data store. Posizi