Corso di Sistemi Distribuiti - unina.stidue.netunina.stidue.net › Sistemi Distribuiti ›...

Università degli Studi di Napoli Federico II Facoltà di Ingegneria Corso di Laurea Specialistica in Ingegneria Informatica

Corso di Sistemi Distribuiti

Prof. Stefano Russo

Sistemi distribuiti peer-to-peer

Ing. Marcello Cinque

Corso di Sistemi Distribuiti, prof. S. Russo Sistemi distribuiti peer-to-peer 2

Sommario

•  Introduzione e classificazione •  Evoluzione dei sistemi P2P•  Esempi:

o Napster, BitTorrent, o Gnutella, Freenet,o Chord, Pastry.

Riferimenti:•  G. Coulouris et al.: Distributed Systems: Concepts and Design (Cap. X, da 10.1 a

10.5.1), IV ed., 2005;•  E.K. Lua et al. “A Survey and Comparison of Peer-to-Peer Overlay Network Schemes”,

IEEE Communications Surveys and Tutorial, Vol. 7, No. 2, Second Quarter 2005;•  I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, H.

Balakrishnan, “Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications”. In IEEE/ACM Trans. on Networking, 2003.


Sistemi distribuiti peer-to-peer (P2P)

  Un sistema peer-to-peer (P2P) è un sistema distribuito nel quale ogni nodo ha identiche capacità e responsabilità e tutte le comunicazioni sono potenzialmente simmetriche;

  Obiettivi: condividere risorse e servizi (dove per risorse e servizi intendiamo: scambio di informazioni, cicli di CPU, spazio sul disco …);

  I sistemi P2P sono caratterizzati da:   controllo decentralizzato;   adattabilità;   si organizzano e si gestiscono da soli;


Peer-to-Peer vs Client-Server

Architettura Client-Server Architettura Peer-to-Peer

•  Approccio centralizzato •  Risorse poste nei server •  Localizzazione e gestione

semplificate •  Limiti di scalabilità e

affidabilità

•  Approccio distribuito •  Risorse condivise dai peer •  Consente scalabilità e

affidabilità •  Richiede algoritmi per la

localizzazione e gestione delle risorse


P2P: Applicazioni e Requisiti

  Applicazioni   File sharing system;   File storage system;   Distributed file system;   Redundant storage;   Chat service;   Distributed computation;

  Requisiti non funzionali   Availability;   Reliability;   Performance;   Scalability;   Anonymity;


Operazioni sottese ad applicazioni peer-to-peer

Il ciclo di vita di applicazioni peer-to-peer è scandito da tre fasi distinte:   Boot: un’applicazione appena avviata intende far

parte del sistema ottenendo informazioni per connettersi agli altri membri del sistema P2P;

  Lookup: un’applicazione intende acquisire una risorsa (ad esempio un file), pertanto ricerca chi dei peer del sistema detiene la risorsa di interesse;

  Resource Sharing: un’applicazione contatta un peer identificato nella fase di lookup per acquisire una risorsa e effettua lo scambio dati.


Soluzioni architetturali per boot e lookup

Le fasi di boot e di lookup possono essere realizzate secondo tre pattern archi-tetturali:

  Centralizzato: esiste un server centrale a cui ogni peer richiede informazioni di boot e lookup;

  Federato: esiste un server per ogni gruppo di peer, e i server sono interconnessi per garan-tire consistenza dei dati gestiti;

  Distribuito: non esiste un server dedicato, ma i dati sono distribuiti tra i peer e sono ottenuti applicando appositi algoritmi decentralizzati.


P2P: Classificazione

  Parleremo di:   P2P puro se:

  le fasi di boot, lookup e sharing sono P2P;   P2P se:

  le fasi di lookup e sharing sono P2P;   la fase di boot utilizza dei SERVER (centralizzati o federati);

  P2P Ibride se:   la fase di sharing è P2P;   la fase di boot utilizza dei SERVER (centralizzati o federati);   nella fase di lookup vengono usati Peer particolari (server federati):

Hub (Direct Connect) SuperPeer , Ultra Peer(Gnutella2) Supernodo (KaZaA) NodoRandezVous (JXTA) MainPeer (EDonkey) Server (WinMX)


Peer-to-peer overlay - 1/3

I nodi di un sistema peer-to-peer sono interconnessi per mezzo di una overlay network costruita al di sopra del protocollo IP:   I nodi rappresentano applicazioni interconnesse per mezzo di link virtuali o logici, ognuno dei quali corrisponde a uno o più link fisici nella rete sotto-stante;   I nodi di una overlay network realizzano opera-zioni di “store&forward” per consegnare un messaggio a destinazione.



IP routing Overlay routing Scala Gli indirizzi IP sono in numero

limitato [IPv4: 232 ma IPv6 2128] Il peer-to-peer consente di indirizzare più oggetti [>2128]

Load Balancing

Il carico dei router dipende dalla topologia ed il relativo traffico

Oggetti disposti a caso, scollegando il carico dalla topologia

Dinamiche di rete

Tabelle di routing aggiornate asincronamente ad ogni ora

Tabelle di routing aggiornate in frazioni di secondi in maniera sincrona e/o asincrona

Fault Tolerance

Ridondanza realizzata dagli ISP ed amministratori di rete

Percorsi ed oggetti replicati all’occorrenza

Identificazione destinazione

Ogni indirizzo IP identifica un singolo nodo

Messaggi indirizzati verso la replica più vicina di un oggetto

Sicurezza e anonimità

Sicurezza ottenuta solo se tutti i nodi sono affidabili, non è garantita l’anonimità

Sicurezza ottenubile anche su reti non pienamente affidabili. Una limitata anonimità è ottenibile



I sistemi peer-to-peer sono comunemente classificati in base all’organizzazione imposta all’overlay network:   P2P Strutturati: la topologia dell’overlay network

è lascamente controllata e le risorse non sono collocate a caso, ma in precise posizioni in modo da rendere la loro ricerca più efficiente;

  P2P Non Strutturati: i peer non sono interconnessi secondo una precisa struttura, ma adottando grafi casuali.

Overlay network strutturate: maggiore efficienza di ricerca, ma vulnerabilità ai fallimenti di nodo; richiedono la gestione di uno stato complesso. Overlay network non strutturate: più affidabili, ma meno efficienti per quanto riguarda i tempi di lookup.


Evoluzione sistemi P2P

First Generation

Second Generation

Third Generation

Peer-to-Peer non strutturati

Peer-to-Peer strutturati

First Generation

Second Generation

Third Generation


P2P di I generazione

Sistemi con fase di boot e lookup centra-lizzati (o federati), mentre lo sharing è realizzato in modalità peer-to-peer.Esempio: BitTorrent, Napster




  Sistema per lo sharing di file musicali

  Nel 2000, 50 milioni di utenti hanno scaricato il client di Napster;

  Napster ha avuto un picco di traffico di circa 7 TB in un giorno;

  Soluzione con lookup centralizzata

Esempio P2P di I generazione: Napster


Esempio P2P di I generazione: BitTorrent - 1/3

.torrent File

.torrent ServerTracker

BitTorrent è una solu-zione P2P di prima gene-razione per file sharing:

•  Un server mantie-ne .torrent files che contengono meta- informazioni sui file da scaricare;

•  Un Tracker tiene traccia di tutti i peer che detengono un dato file.

Un downloader contatta periodicamente il tracker per aggiornare le sue informazioni e ricevere la lista di peer che posseggono il file in download, così da contattarli. Riferimento: www.imconf.net/imc-2006/papers/p20-legout.pdf



Il tracker tiene traccia di tutti i membri dello swarm, e i frammenti di file in loro possesso.

Il downloader riceve e diffonde più frammenti del file allo stesso tempo da/verso molteplici peers.



Quale frammento del file viene richiesto dal downloader?

Inizialmente un peer richiede frammenti scelti a caso (Random First Policy), quando ne sono stati scaricati almeno 4, si passa ad eseguire il Rarest First Algorithm:

Ogni peer mantiene una peer list col numero di peer aventi ogni frammento (RepID). Gli identificativi dei frammenti con il minore RepID sono memorizzati nella rarest piece list, da cui a caso viene scelto il frammento da scaricare.

Quando un blocco di un frammento è stato scaricato, anche gli altri saranno richiesti con altissima priorità (Strict Priority Policy).


P2P di II generazione:

First Generation

Second Generation

Third Generation

Sistemi con fase di boot centralizzata (o federata), e lookup e sharing distribuite; l’overlay non presenta organizzazione.Esempio: Gnutella, Freenet




  Raccoglie l’eredità di Napster;   Nel 2000 la dimensione della rete cresce in 7 mesi da 2K

a 48K nodi;   Applicazioni più conosciute basate su Gnutella:

  BearShare;   LimeWire (anche client BitTorrent);   …

  Fase di boot centralizzata: un Server (gnutellahost.com) viene usato dai nodi per il boot.

  Fase di lookup distribuita: le richieste di Ricerca vengono propagate con tecniche di flooding.

Esempio P2P di II generazione: Gnutella


Flooding – 1/2

I sistemi di seconda generazione sono interconnessi secondo un grafo casuale, dove ogni nodo mantiene una lista degli identificativi dei vicini, che riceve a conclusione la fase di boot.

Come realizzare il lookup senza un server centralizzato o federato?

Il nodo invia una richiesta di query a tutti i vicini, i quali inoltrano la richiesta ai propri vicini se non dispongono dell’informazione cercata. Il messaggio di query si propaga all’interno del sistema fino a raggiungere un nodo che detiene l’informazione (flooding), che viene inoltrato al richiedente.


Flooding – 2/2

Il flooding presenta l’inconveniente che i messaggi possono circolare nel sistema indefinitamente, ripassando per nodi già visitati precedentemente. Soluzioni:

•  Ogni nodo mantiene la lista di query già valutate, qualora una query passata è nuovamente ricevuta, viene scartata;

•  Ogni query ha associato un TTL, che viene decrementato ad ogni ricezione, cosicché quando il suo valore è nullo la query viene scartata.

Siccome diverse repliche della stessa query sono disseminate nel sistema, sussiste l’inconveniente che il sender della query riceva l’informazione più di una volta se nel sistema più di un nodo la detiene.


Esempio P2P di II generazione: Freenet - 1/2

Freenet migliora le prestazioni del flooding strutturando scarsamente l’overlay network:

•  Ogni dato è identificato da una chiave. •  Dati con chiavi simili tendono a raggrupparsi su un

simile insieme di peer, così da ridurre i peer da visitare per il lookup.

Ogni nodo presenta due liste di chiavi: •  Quella dei propri dati; •  Quella delle locazioni dei dati noti.


Esempio P2P di II generazione: Freenet - 2/2

A

C1

2Il peer A avvia il flooding di richieste per un dato detenuto da D. Quando D riceve la richiesta, non contatta direttamente A, ma ripercorre al contrario il percorso di lookup. O g n i n o d o c o n t a t t a t o memorizza nella seconda lista la chiave e il next_hop così da def in i re una scorc iato ia ( rou t ing shor t - cu t ) pe r successive query dello stesso dato.

D

E

B

F

Richiedente

Peer con dato richiesto

Richiesta OggettoDefinizionescorciatoia

2

3

3


Scalabilità

  I protocolli di I e II generazione non sono scalabili, in quanto le prestazioni (es. tempo di ricerca di un file) peggiorano linearmente all’aumentare del numero dei nodi. In altri termini, la quantità di lavoro richiesta a un determinato nodo deve crescere linearmente in funzione del numero di nodi nel sistema;

  La scalabilità è direttamente legata all’efficienza dell’algoritmo usato per il lookup;

  Per questo motivo, diviene necessario:   Minimizzare il numero di messaggi necessari per fare lookup;   Minimizzare, per ogni nodo, le informazioni relative agli altri nodi;

  Per migliorare la scalabilità sono nati i cosiddetti protocolli P2P di terza generazione che supportano DHT (Distributed Hash Table);


P2P di III generazione:

First Generation

Second Generation

Third Generation

Sistemi con tutte le fasi completamente distribuite, con la overlay strutturata secondo il paradigma DHT.Esempi: Chord, CAN e Pastry




Distributed Hash Table (DHT)

Nei sistemi di I e II generazione le informazioni sono organizzate senza alcuno schema. N e l l a I I I g e n e r a z i o n e , g l i o g g e t t i s o n o deterministicamente collocati nei peer i cui identificatori corrispondono alla chiave associata all’informazione.

Le Distributed Hash Tables (DHT) for-niscono un’astrazio-ne simile alle hash tables, per cui a una chiave corrisponde un valore, sebbene i dati non siano locali ma distribuiti.


DHT: funzionamento di base

  A ogni file e ad ogni nodo è associata una chiave;   La chiave viene di solito creata facendo l’hash del nome

del file o dell’IP del nodo;   Ogni nodo del sistema è responsabile di un insieme di

file/chiavi e tutti realizzano una DHT;   La principale operazione che un sistema DHT deve

fornire è lookup(key), la quale restituisce l’identità del responsabile di una determinata chiave.

IP Address


DHT: funzionamento di base

  Tutti i nodi del sistema condividono una tabella hash;   Conoscono la struttura della tabella…   Ma non conoscono il responsabile di una data chiave!

Nodo x

Nodo y

Nodo z

ID 0 1 2 3 4 5 6 … 2m

…


Dimensione tabella di routing

Messaggi necessari per trovare una chiave

1

1

n -1

n -1

O(log n)

O(log n)

DHT

Grafo Totalmente connesso

Anello

n è il numero dei peer;

DHT: scalabilità


  Soluzione DHT che associa a peer e chiavi un identificativo di m bit attraverso una funzione di hash SHA-1 (in totale N = 2m identificativi);

  Si basa su un overlay ad anello in cui i peer sono ordinati in base agli id.   Il nodo responsabile di una determinata chiave K è quello con il primo

identificativo W tale che W succede K in senso orario;   Ogni nodo x di Chord mantiene due insiemi di vicini:

  gli m successori del nodo x più il predecessore.

  Fingers: Un ins ieme m nod i costituito dai responsabili delle chiavi distanziate esponenzialmente dal nodo x, vale a dire l’insieme delle chiavi che si trovano a distanza 2i da x dove 0 ≤ i ≤ m-1.

m=6

Esempio P2P di III generazione: Chord - 1/6

N4

N8

N14

N56

N51

N48

N42

N38 N32

N21

K10

K30K24

K54



N4N8

N14

N56

N51

N48

N42

N38 N32

N21

Grado del successore

NodeID

1 N14 2 N21 3 N32 4 N38 5 N42 6 N48

Predecessor N4

Successors table: utilizzata per ricerche nelle immediate vicinanze; contiene gli id degli m successori e del predecessore



Finger Table: utilizzata per velocizzare la ricerca; contiene gli id degli m peer a distanza 2i con 0 ≤ i ≤ m-1

N4

N8

N14

N56

N51

N48

N42

N38 N32

N21

+32

+16+8

+4+2

+1Grado del finger

NodeID

1 (N8+1) N14 2 (N8+2) N14 3 (N8+4) N14 4 (N8+8) N21 5 (N8+16) N32 6 (N8+32) N42


Esempio P2P di III generazione: Chord – 4/6 La Finger Table consente di realizzare un algoritmo di lookup, più scalabile, minimizzando le informazioni da memorizzare nei peer. E’ usata per identificare il nodo più prossimo alla chiave, così da ridurre i nodi da contattare.

N4

N8

N14

N56

N51

N48

N42

N38 N32

N21

Lookup 54

ALGORITMO DI LOOKUP n.find_successor(id)

if (id ∈ (n, successor])

return successor;

else

n’= closest_preceding_node(id);

return n’.find_successor(id);

n.closest_preceding_node(id)

for i = m downto 1

if (finger[i] ∈ (n, id))

return finger[i];

return n;


Esempio P2P di III generazione: Chord – 5/6

La correttezza di Chord si basa sul presupposto che ogni peer conosca esattamente i suc-cessori e i finger. Tale requisito può essere compromesso dal la dinamicità dei peer (churn o fallimenti).

P e r m a n t e n e r e l a correttezza dei dati di routing sono eseguiti periodicamente appositi algoritmi di stabiliz-zazione.

n.stabilize()

x = successor.predecessor;

if (x ∈ (n, successor))

successor = x;

successor.notify(n);

n.notify(n’)

if (predecessor is nil or n’ ∈(predecessor,n))

predecessor = n’;

n.fix_fingers()

next = next + 1 ;

if (next > m)

next = 1;

finger[next] = find_successor(n + 2next-1);

n.check_predecessor()

if (predecessor has failed)

predecessor = nil;


Analisi di Complessità   Le informazioni che il nodo deve mantenere sugli altri

nodi sono m + m + 1 = 2m +1 (O(log N));   Il numero di messaggi necessari per fare lookup è m

(O(log N));   Il costo che si paga quando un nodo lascia o si connette

alla rete è di O(log2N) messaggi;

Esempio P2P di III generazione: Chord – 6/6


Esempio P2P di III generazione: Pastry - 1/4

Anche Pastry usa un overlay ad anello, ma, a differenza di Chord, si basa sul prefisso delle chiavi:

•  Ad ogni nodo è assegnato in maniera casuale un NodeID a 128-bit, generalmente considerato come una sequenza di interi con base B (tipicamente 16);

•  Ogni query di un dato con chiave k viene istradata verso il nodo il cui NodeID è numericamente vicino a k (i primi n interi di NodeID e k coincidono);

•  Ad ogni passo dell’algoritmo di routing, un nodo inoltra la richiesta di query a un peer il cui NodeID condivide con la chiave un prefisso di almeno un intero, di dimensione maggiore di quello che la chiave condivide con il nodo corrente.


Esempio P2P di III generazione: Pastry - 2/4

Per consegnare a destinazione il messaggio di query, ogni nodo di Pastry dispone delle seguenti strutture:

1.  Routing Table (R), contiene NodeID e indirizzi IP dei peer noti. Nella n-sima righa, tutti gli elementi hanno in comune i primi n interi;

2.  Neighborhood Set (M), contiene dati sui peer vicini (per prossimità di routing) a quello corrente;

3.  Leaf Set (L), contiene informazioni dei |L|/2 peer con NodeID più piccolo prossimo a quello corrente e |L|/2 con NodeID più grande.

(R) (M) (L)


Esempio P2P di III generazione: Pastry - 3/4 Le query sono istradate secondo il seguente algoritmo:

•  Se la chiave della query è uguale al NodeID corrente o in L ci sono nodi che condividono meno interi del nodo corrente, la query è conclusa;

•  Se la destinazione è in L, il messaggio viene inoltrato a tale peer;

•  Altrimenti, si identifica (in R o in alternativa in L o in M) i l peer con i l maggior numero di interi in comune e il primo non in comune più vicino a quello della ch iave, e s i ino l t ra i l messaggio a questi.

Lookup D46A1C

0 FFFF…F

65A1FC

D13DA3

D462BA

D467C4

D471F1

D4213F

D46A1C


Esempio P2P di III generazione: Pastry - 4/4 Pastry gestisce il churn dei peer secondo un meccanismo di heartbeat per rilevare i fallimenti e di riparazione del leaf set per porvi rimedio:

•  Periodicamente i peer scambiano messaggi di PING, il peer che non risponde entro un apposito timeout è considerato fallito;

•  Il nodo che ha scoperto il fallimento, contatta il peer numericamente successivo a quello fallito, chiedendo una copia del suo leaf set;

•  Il leaf set ricevuto avrà delle sovrapposizioni con quello in possesso dal peer che ha iniziato la procedura, ma anche validi peer per sostituire quello fallito;

•  I peer vicini sono informati del fallimento e eseguono la stessa procedura.


Confronto DHT

CHORD PASTRY

Architettura Spazio NodeID unidirezionale e circolare

Mesh globale Plaxton-style

Algoritmo di Lookup

Matching chiave e NodeID

Matching chiave e prefisso NodeID

Complesità del lookup

O(logN) O(logBN)

Routing State logN BlogBN + |L| + |M|

Corso di Sistemi Distribuiti - unina.stidue.netunina.stidue.net › Sistemi Distribuiti ›...

Documents

Transcript of Corso di Sistemi Distribuiti - unina.stidue.netunina.stidue.net › Sistemi Distribuiti ›...