1

CdL MAGISTRALE in INFORMATICA

A.A. 2014-2015

corso di “Sistemi Distribuiti”

5. IPC (Inter Process Communication) (parte 2):

comunicazione M.O., pub_sub, sincronizzazione e multicasting

Prof. S.Pizzutilo

InterProcess Communication (IPC)

Modelli e tecnologie per la comunicazione e la sincronizzazione fra processi:

I tipi di comunicazione: •  Comunicazione discreta (es. socket) e a flussi (streaming) •  Comunicazione diretta (es. client/server) e indiretta (es.multicast)

Le forme ed i modelli della comunicazione : Ø Sistema di comunicazione basato sui messaggi ( MOM = Message Oriented

Middleware). Ø La sincronizzazione. Ø Comunicazione Multicast. Ø Chiamata a procedura remota (es. RPC) e la comunicazione tra oggetti (es. RMI).

CdL in Informatica- Magistrale Università di Bari Sistemi Distribuiti

2

Comunicazione orientata ai messaggi

Per risolvere i problemi relativi alla natura prevalentemente sincrona dell’ IPC, si ricorre a soluzioni basate sulla comunicazione basata sullo scambio di messaggi (conservati o meno in code).

Problemi relativi alla persistenza ed alla sincronizzazione nella comunicazione

Architettura di un Message-Queuing System (1)

Relazione tra indirizzamento a livello di sender e receiver (ad es. DNS per localizzare server e-mail su Internet)

CdL in Informatica- Magistrale Università di Bari - Sistemi Distribuiti -

Rif.: A.Tanenbaum,M.Van Steen “Sistemi distribuiti” Pearson Prentice Hall 2007 )

3

Architettura di un Message-Queuing System (2)

Ad es. l’organizzazione generale di un sistema message-queuing (ad es: router, reti overlay,…).

2-29

CdL in Informatica- Magistrale Università di Bari Sistemi Distribuiti

Rif.: A.Tanenbaum,M.Van Steen “Sistemi distribuiti” Pearson Prentice Hall 2007 )

Il Message Broker

Organizzazione generale di un sistema message-queuing mediante broker. (ad es. : sistemi publish/subscribe)

CdL in Informatica- Magistrale Università di Bari Sistemi Distribuiti

Rif.: A.Tanenbaum,M.Van Steen “Sistemi distribuiti” Pearson Prentice Hall 2007 )

Architettura di un Message-Queuing System (3):

4

Altre forme di comunicazione con sincronia virtuale

o  Message queueing: modello point to point o point to many o  Publish/Subscribe: modello many to many

Il Message Oriented Middleware (MOM) è caratterizzato da funzionalità di : ü  publish/subscribe topic-based, ü  message queueing. ü  Servizio di message storing e tipizzazione dei messaggi, ü  Interfacce e strutture dati a supporto dello scambio di informazioni su file

multimediali, come musica e film, ü  Gestione automatica del salvataggio dei messaggi, ü  Supporto per la comunicazione sincrona e asincrona, ü  Implementazione schema di comunicazione point-to-point e point-to-many per quanto

riguarda il message queueing, ü  Tecnica di replicazione hot stand by, ü  Invio e ricezione dei messaggi con semantica at-most-once e once-and-only-once.

Applicazioni P2P

Il Peer to Peer è una forma di comunicazione nella quale non vi è distinzione tra chi genera informazioni (il server) e chi ne usufruisce (il client) . Questa forma di comunicazione è fondamentale nei Sistemi Distribuiti.

Ad es. : il WEB è P2P ? Facebook è P2P ? E-mail è una applicazione P2P ? Bit Torrent è P2P ? Un WEB service è P2P ?

Il P2P è realizzato attraverso tecniche di multicasting, publish/subscribe e overlay network.

5

Altre forme di comunicazione sincronizzata

Publish/subscribe (pub/sub) è un paradigma di messaging asincrono nel quale i mittenti (sender o publisher) non indirizzano messaggi a specifici destinatari (receiver o subscriber), bensì ad un data manager. Quest’ultimo, utilizzando tecniche di message queuing, può organizzare i messaggi ricevuti in code “tematiche” (di interesse) o “classi” diverse. I destinatari (subscriber) accedono solo alla parte di messaggi pubblicati di loro interesse attraverso un processo di filtering che può essere topic-based o content-based.

In alcuni sistemi i messaggi vengono gestiti da un intermediary broker che svolge la funzione di store-and-forward tra publisher e subscriber. Il Content-based filtering viene svolto dallo subscriber, prima che i messaggi vengano passati alla applicazione.

Esempi di sistemi di content filtering: WEB services ( SOA), CORBA, SCRIBE, TERA, GRYPHON, JEDI, IBM WebShere MQ,….

MOM Publish/Subscribe Ø A u t h o r i n g s e r v i c e :

fornisce funzionalità di a u t e n t i c a z i o n e a l sistema.

Ø Discovery service: si occupa della gestione nomi dei servizi.

Ø  Publ i sh-Subscr ibe subsytem: implementa le funzionalità definite dal modello P/S.

Ø M e s s a g e Q u e u e i n g : i m p l e m e n t a l e funzionalità definite dal modello MQ.

Ø Data Manager: si occupa della gestione dei dati. Fornisce interfacce di accesso trasparenti al s i s t e m a d i memorizzazione delle informazioni.

Tratto da : Andrea Antonio Garganico Implementazione MOM basata sul paradigma “Publish/Subscribe” e “Message Queueing”

6

La sincronizzazione nella comunicazione

In un sistema distribuito il tema della sincronizzazione delle comunicazioni tra processi su macchine remote è centrale per consentire la cooperazione necessaria alla computazione distribuita. Sincronismo = «Contemporaneità di svolgimento di azioni e fatti diversi» La sincronizzazione riguarda quindi il problema dell’ordinamento temporale delle operazioni , per cui il concetto di «tempo», in particolare nei sistemi distribuiti (ma non solo), è centrale per risolvere i potenziali conflitti che sorgono nella computazione parallela e concorrente utilizzando componenti HW/SW diversi.

Alcuni conflitti si possono risolvere garantendo la mutua esclusione, il tipo più semplice di sincronizzazione. Per evitare altri tipi di conflitti, in particolare nei sistemi distribuiti, sono però necessarie forme più complesse di sincronizzazione basate essenzialmente in tecniche per concordare il clock (orologio fisico) dei diversi sistemi o per ordinare gli eventi (orologio logico) dei diversi componenti di un sistema distribuito.

Il clock (orologio fisico) per la sincronizzazione dei processi in un

sistema distribuito

Network

Sincronizzazione del clock del sistema distribuito mediante un Time Service

Algoritmi di tipo:

“master-slave”

“gossiping”

Un processo master invia il proprio valore di clock ai suoi slave che aggiornano il proprio clock.

Ogni processo invia il proprio valore di clock a tutti, in modo che ciascun processo possa ridurre lo scostamento del proprio clock da quello degli altri.

7

Il Time Service per la sincronizzazione

m r

m t p Time server,S

m r

m t p Time server,S

Centralizzato : servizio implementato su un solo server (dotato di ricevitore UTC) che eroga ai diversi sistemi il suo clock. - Algoritmo di Cristian (1989) Request-driven - Algoritmo di Berkeley Broadcast.based (1989)

Distribuito : L'UTC è distribuito dinamicamente attraverso Internet . - Algoritmo Network Time Protocol.

Il tempo viene calcolato sulla base dell’ UTC= Coordinated Universal Time = orario di riferimento per tutti i fusi orari terrestri, calcolato con orologi atomici (che calcolano il secondo come un numero di circa 9 miliardi di transizioni del cesio 133).

Algoritmo di Cristian

Algoritmo di Berkeley

1.  Il Master è attivo e chiede in broadcast a tutti gli slave il loro valore di clock (mt). 2.  Il master effettua la differenza d tra il suo valore di clock e quelli ricevuti dagli slave

corretti con RTT. Il Round Trip Time (RTT) è il tempo impiegato da un pacchetto per viaggiare da un computer ad un altro e tornare indietro.

3. Calcola la media M delle differenze dei clock. 4. Invia agli slave il valore calcolato (M) per correggere i clock degli slave.

p1 Time server,S

p2

p3 mt3

mt1 m

t2

M3 M1

M2

8

NTP (Network Time Protocol)

1 2

3 2

3 3

T i

T i-1 T i-2

T i - 3

Server B

Server A

Time m m'

Time

- B (server allo strato 2) chiede ad A (server allo strato 1) il suo clock. - B calcola l’RTT e sulla base di tale stima corregge il suo clock . - Questo processo si ripete tra i server di ogni strato. - Sulla base della stima migliore dei clock è possibile che un server possa cambiare strato.

E’ un protocollo per sincronizzare i clock dei computer all'interno di una rete a commutazione di pacchetto, quindi con tempi di latenza variabili.

I diversi server NTP sono organizzati in una struttura gerarchica a "strati", dove lo strato 1 è sincronizzato con UTC.

Un server si sincronizza confrontando il suo orologio con quello di diversi altri server di strato superiore.

Orologi logici : il Timestamping

Nei sistemi distribuiti asincroni la infrastruttura di comunicazione, non consente la sincronizzazione in tempo reale dei clock fisici dei nodi .

In tal caso si usa la tecnica del TIMESTAMP, ovvero di un valore intero che si associa alla generazione degli eventi all’interno di ciascun processo e che viene quindi scambiato tra i processi comunicanti, al fine di assicurare diverse forme di sincronizzazione.

Timestamps Ti

e21 e1

2

e22 e2

3 e2

1 e23

e11

e13

concorrenti

e11 1

2

2 1

3 4

5 1

p 1

p 2

p 3

e21

e12 e2

2

e23

e13

9

Timestamping scalare

Per associare un valore di timestamp agli eventi di un sistema distribuito si usa l’algoritmo di Lamport , che basa la sincronizzazione sulla relazione di precedenza tra gli eventi.

Ogni processo Pi mantiene e gestisce un contatore Ci inizializzato a 0 ed aggiornato secondo il seguente algoritmo:

1)  Quando Pi processa un evento (ei), incrementa il contatore Ci ed associa all’evento stesso un timestamp Tk con lo stesso valore di Ci (ek

i ) 2)  Quando Pi invia un messaggio, associa al messaggio inviato il valore di Tk calcolato

con la regola 1) ; 3)  Quando Pi riceve un messaggio ( con associato un valore Tk ) , esso pone Ci = max

(Ci , Tk ) e quindi esegue l’evento (eki) di ricezione applicando sempre la regola 1).

e11

2 1

3 4

5 1

p 1

p 2

p 3

e21

e32 e4

2

e53

e13

e12

e23

1

2

Se C(a)<C(b) non è detto che “a” preceda temporalmente “b”

Timestamping vettoriale Per associare un vettore V(i) di timestamp agli eventi di un sistema distribuito si

usa l’algoritmo di Mattern (1988) Ogni processo Pi mantiene e gestisce un contatore Ci inizializzato a 0 ed aggiornato

secondo il seguente algoritmo: 1) Quando Pi processa un evento, incrementa il contatore Ci ed associa all’evento

stesso un timestamp Tk con lo stesso valore di Ci, che inserisce nel vettore V(i) 2) Quando Pi invia un messaggio, associa al messaggio inviato il valore di Tk calcolato

con la regola 1) ; 3) Quando Pi riceve un messaggio ( con associato un valore Tk) , esso pone in V(i) =

max (Ci , Tk) e quindi esegue l’evento di ricezione applicando sempre la regola 1) .

e11 e2

1

e12 e2

2

e13 e2

3

m 1

m 2

(2,0,0) (1,0,0)

(2,1,0) (2,2,0)

(2,2,2) (0,0,1)

p 1

p 2

p 3

time

e33

(2,2,3)

10

La comunicazione multicast

Affidabilità del multicast :   affidabilità 0 (nessuna risposta)   affidabilità 1 (almeno 1 risposta)   affidabilità M su N (M risposte.su N nodi)   affidabilità completa (risposta da N nodi)

L’atomic multicast è una tecnica di trasmissione multicast ad un gruppo che gode della proprietà che un messaggio è ricevuto da almeno un membro del gruppo cui il messaggio è stato inviato oppure da nessuno. Il multicast atomico gestisce la comunicazione tra coppie di processi mediante un ordinamento casuale o FIFO: i messaggi spediti da un client ad un particolare server sono consegnati (dal kernel al processo ricevente) nello stesso ordine in cui sono stati spediti o ricevuti.

E’ uno schema di comunicazione asincrono con un singolo mittente ed un insieme (>1) di riceventi (gruppo). La broadcast communication è un caso particolare della multicast, in cui il messaggio è spedito a tutti i processori connessi alla rete.

Multicast buffered e unbuffered

Il multicast è un meccanismo di comunicazione asincrono. Infatti il send multicast non può essere sincrono perché: •  è irrealistico aspettarsi che un send in multicast possa bloccare il sender finchè il

messaggio non sia stato ricevuto da tutti i membri del gruppo, •  il processo sender potrebbe non avere la consapevolezza della ricezione del

messaggio da parte di tutti i membri del gruppo. Il multicast può prevedere che il messaggio inviato venga conservato in un buffer dei processi riceventi, così da garantire che tutti i membri del gruppo possano ricevere il messaggio.

Ahamad e Bernstein (1985) descrissero due fondamentali tipi di semantica della comunicazione multicast : send-to-all : una copia del messaggio viene inviato a ciascun processo del gruppo e il messaggio viene bufferizzato finchè non viene accettato dal processo. bullettin-board : il messaggio viene indirizzato ad un canale anziché essere spedito a ciascun processo del gruppo. Dal punto di vista logico il canale corrisponde ad un bulletin board . I processi riceventi copiano il messaggio dal canale (e non lo cancellano)

11

Una coda per conservare i messaggi multicast

Messageprocessing

Delivery queueHold-back

queue

deliver

Incomingmessages

When delivery guarantees aremet

Comunicazione molti a molti

Nel caso di comunicazione di molti a molti la sincronizzazione dei messaggi (l’ordinamento dei messaggi in ricezione) non è banale.

1 t t

m 1

X Y

Z

A t 6 3

m 2 m

1 m

2

No ordering message delivery

t2 t3 t4 t5

12

Absolute Ordering

m m 1

X Y Z A

t1

t2

2 m

1 m

2

Consistent Ordering

Questa semantica assicura che tutti i messaggi vengano ricevuti nell’esatto ordine con cui sono stati spediti. Un metodo che si utilizza per ottenere questa proprietà è la tecnica del “timestamp” come identificatore del messaggio.Si assume che il sistema abbia un clock sincronizzato su ciascuna macchina. Quando viene spedito il messaggio il valore del clock (timestamp) viene preso come identificatore del messaggio . Il kernel che riceve il messaggio riceve quindi anche il suo timestamp e provvede ad inviare i messaggi ai riceventi secondo il valore del timestamp.

X Y Z A

m 1 t1

t2

2 m

1 m

2

m

Questa semantica richiede un orologio globale sincronizzato ed assicura che i messaggi vengano ricevuti dai processi riceventi tutti nello stesso ordine, indipendentemente dall’ordine con cui sono stati inviati. Un metodo per realizzare questa semantica prevede che il kernel delle macchine invianti mandino i messaggi ad un singolo ricevente ( sequenziatore) che assegna un numero sequenziale a ciascun messaggio e provvede quindi alla loro spedizione. Il kernel delle macchine riceventi salva i messaggi in code separate ed invia immediatamente i messaggi con numero sequenziale corretto. In caso contrario aspetta che arrivi il messaggio con il numero successivo prima di spedire. (ABCAST protocol del sistema ISIS - Birman 1991)

Causal ordering

m1

m1 m2

p1

p3

p4

p5

p2

m3

m2 m3

m1

Questa forma di ordinamento assicura che se un evento inviante un messaggio è correlato (relazione di causalità) con un evento di sending di un altro messaggio, i due messaggi sono consegnati a tutti i riceventi nell’ordine corretto (m1-m3). Altrimenti, se gli eventi di invio non sono correlati, i messaggi possono essere ricevuti in un ordine qualsiasi (m2). (CBCAST protocol del sistema ISIS - Birman 1991)

13

…ancora sulla comunicazione multicast

  Nei sistemi distribuiti il supporto per l’invio di dati a molteplici destinatari ( “comunicazione multicast”), che può essere realizzato a livello di protocolli di rete (IP - IGMP) oppure a livello applicativo.

  La comunicazione multicast a livello applicativo può essere realizzata sia in maniera strutturata (creando “communication path” espliciti), sia non strutturata (affidandosi a tecniche applicative che simulano la diffusione delle epidemie).

  Un elemento di progettazione fondamentale per il multicast strutturato a livello applicativo è la costruzione di una rete “overlay” = una rete virtuale atta a fornire meccanismi non nativamente supportati dalla rete sottostante (ad es. il multicast).

Il multicast strutturato applicativo

Esistono due approcci fondamentali per l’implementazione del multicast strutturato applicativo con una rete overlay: Ø il primo è che i nodi si possono organizzare direttamente in un albero, il che significa che c’è un unico percorso tra una coppia di nodi ( ad es. CHORD); Ø  l’altro vede i nodi organizzati in una rete a maglia in cui ogni

nodo ha molti vicini, creando cosi molti percorsi diversi per ogni coppia di nodi.

La differenza principale tra i due approcci è che di solito il secondo è più robusto: infatti se cadesse un nodo, ci sarebbe ancora la possibilità di distribuire le informazioni senza la necessità di riorganizzare immediatamente l’intera rete.

14

Overlay network

I PEER (nodi, risorse) si organizzano sovrapponendo (overlay) alla rete fisica una rete logica in modo da consentire la loro localizzazione senza dover specificare indirizzi IP, ma solo indirizzi logici (generati con una funzione hash e memorizzati in una hash table distribuita (DHT)). I peer si organizzano creando dei link virtuali fra loro.

Problema : STRETCH (o Relative Delay Penalty = RDP) ovvero rapporto tra il tempo di trasferimento del messaggio tra due nodi nella rete overlay ed il tempo nella rete fisica sottostante.

Rete Overlay con Distributed Hash Table (1)

Ciascun nodo (processo) mantiene un set di link agli altri nodi (i suoi vicini). Tutti insieme questi nodi formano una Overlay Network, con una sua topologia logica ad anello. Tutte le topologie di Overlay Network condividono la proprietà essenziale: Ad ogni peer viene assegnato un ID univoco (k) generato con una funzione hash . Per ciascuna chiave k, o il nodo possiede k oppure ha un collegamento ad un nodo che è più vicino a k in termini di distanza. Ad esempio in una rete ad anello (sistema CHORD):

1

3(0, 1, 2)

2

4

7

89

0(3, 4)

(7, 8, 9)

Sistema basato su DHT con topologia logica ad anello in cui ai dati ed ai nodi viene assegnata una chiave generata all’interno di uno spazio di identificatori di 160 bit, con uno schema di mappatura tra nodi e dati attraverso la loro chiave. Nella figura ad es. si hanno 3 nodi e complessivamente 5 dati (due dati associati al nodo 2, 1 al nodo 4 e 2 al nodo 9).

Per inserire un nuovo dato, viene generata la chiave k e viene mappato nel nodo con id >= k cioè nel nodo successore di k (succ(k)).

Per inserire un nuovo nodo, viene generata la chiave k che sarà l’id del nodo e così il nodo viene inserito logicamente tra il predecessore (pred(id)) ed il succ(id).

15

DHT (1)

Le tabelle hash distribuite (DHT) sono una tipologia di infrastruttura di sistemi basata su tabelle di coppie (key, value) relative ai nodi/risorse del sistema, nelle quali il valore delle key è calcolato con una funzione hash applicata al valore. Tale infrastruttura consente di disporre di un servizio efficiente di lookup su ad un vasto numero di nodi (peer).

Questo tipo di infrastruttura viene utilizzata per implementare servizi complessi, quali file system distribuiti, sistemi peer-to-peer di file sharing, multicast e domain name services,….

DHT (2)

Una DHT è costruita attorno ad un keyspace astratto, come un set di stringhe di 160-bit. L’appartenenza al keyspace è divisa tra i nodi partecipanti in base ad un ben definito schema per il partizionamento.

Un tipico funzionamento di una DHT per immagazzinare e poi recupare un dato può avvenire nel seguente modo:

Ø  Si supponga che il keyspace sia un set di stringhe di 160-bit. Ø  Per immagazzinare nella DHT un file caratterizzato dai parametri filename e dati,

viene inizialmente calcolato l’SHA1 del filename, producendo così una chiave k di 160-bit.

Ø  In seguito, un messaggio put(k, data) può essere inviato ad un qualsiasi nodo della rete DHT. Il messaggio è inoltrato di nodo in nodo attraverso l’overlay network (tra i succ(k)) fino a che esso non raggiunge il singolo nodo che è responsabile per la chiave k (laddove la coppia (k, data) è già stata immagazzinata).

Ø  Qualsiasi altro client può quindi successivamente recuperare i contenuti del file calcolando a sua volta l’hash del filename (per ottenere k) e chiedere ad un qualsiasi nodo della rete DHT di trovare il dato associato a k, tramite un messaggio get(k).

Ø  Il messaggio verrà quindi inoltrato attraverso l’overlay verso il nodo responsabile per k, che risponderà con una copia del dato immagazzinato.

16

A questo punto risulta quindi facile inoltrare un messaggio al proprietario di una qualsiasi chiave k utilizzando il seguente algoritmo :

a)   ad ogni passo successivo, inoltra il messaggio al vicino il cui ID è più vicino a k; b)  quando non esiste un vicino con queste caratteristiche, allora si è giunti al nodo

effettivamente più vicino, il quale deve essere il proprietario di k. Questo tipo di routing viene talvolta definito come key based routing.

Al di là della correttezza di fondo di questo tipo di routine, vi sono due vincoli chiave nella

topologia: - che il numero massimo di passi successivi in un qualsiasi percorso (dilazione) sia basso,

in modo tale che la richiesta sia soddisfatta velocemente, e - che il numero massimo di vicini di ciascun nodo (il grado del nodo) sia basso, al fine di

mantenere basso l’overhead di mantenimento.

Rete Overlay con DHT (3)

L’overlay network connette i nodi, consentendo loro di trovare il proprietario di una determinata chiave nel keyspace della DHT.

Modelli non strutturati per la diffusione dei dati

Algoritmi epidemici

E’ una tecnica (utilizzata nei sistemi distribuiti a larga scala) basata su un modello di propagazione dei dati che consiste nel diffondere le informazioni su un host (scelto a caso e detto “infetto”). Il nodo infetto provvede a sua volta a diffondere l’informazione sugli host con cui è collegato. Il nodo che non ha ancora ricevuto i dati è detto “suscettibile”. Un nodo che ha già ricevuto i dati o non può diffonderli è detto “rimosso”.

Modello anti-entropia Modello gossiping

Un nodo sceglie a caso un altro nodo al quale inviare (spingere) ) i dati o dal quale ricevere (attrarre) i dati :

a)  PUSH = P (nodo infetto) invia i dati al nodo Q (solo se suscettibile) b)  PULL = Q (suscettibile) accoglie i dati da P (infetto), c)  PUSH/PULL = P e Q si mandano reciprocamente i dati (push-pull).

Se P è aggiornato con il dato x, prova ad inviare x ad un nodo arbitrario Q. Se Q ha già ricevuto x da un altro nodo, P perde l’interesse a diffondere ulteriormente x (viene rimosso). Tale tecnica non garantisce che tutti i nodi ricevano l’informazione, ma è molto efficiente nella propagazione del dato.