Abilitare condivisone di dati e risorse su vasta scala
Eliminare amministrazione centralizzata.
“exploit resources available at the edges of the Internet” [Shirky 2000].
Un sistema peer-to-peer (P2P) è un sistema distribuito nel quale i nodi hanno simili responsabilità e capacità funzionali.
Non vi è centralizzazione di attività in specifici nodi e la cooperazione tra i nodi avviene mediante interazioni tra pari (peers).
Il modello P2P trova tipicamente applicazione in sistemi di condivisione di risorse (file, cicli di CPU, documenti multimediali, …).
Ogni nodo contribuisce alla gestione delle risorse globali
utilizza i servizi degli altri nodi e fornisce loro “in cambio” analoghi servizi.
Es.: è possibile per un nodo “scaricare” un file da un altro nodo, a condizione di mettere successivamente a disposizione lo stesso file, ovvero altre risorse locali.
Architettura Client-Server
Architettura Peer-to-Peer
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.
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 garantire 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 puro
P2P
P2P Ibrido
In base alla topologia della rete, i sistemi P2P sono classificati in:
Strutturati: presenza di una policy globale per la topologia della rete, placement degli oggetti e routing.
Non Strutturati: i peer non sono interconnessi secondo una precisa struttura; la topologia della rete è ignota.
Expanded ring search: la ricerca viene effettuata inviando più messaggi con time-to-live crescente.
Random walks: vengono utilizzati messaggi che seguono percorsi diversi (scelti in maniera casuale) per fare discovery della rete.
Gossiping: le richieste vengono inoltrate a un vicino (con una certa probabilità) e da questi ad un altro e così via.
Sistema per lo sharing di file musicali lanciato nel giugno 1999.
Nel 2000, 50 milioni di utenti hanno scaricato il software per utilizzare Napster.
Picco di traffico di circa 7 TB in un giorno.
Servizio disattivato nel luglio 2001 per infrazione della legge sui diritti d’autore.
Soluzione con lookup centralizzata.
Utilizza la località della rete: per un client-peer diventerà server-peer il nodo a meno hop di distanza.
Così si evita anche che il primo a rendere disponibile un file diventi hot spot per esso.
Napster fu prova della possibilità di creare grossi sistemi costituiti da computer degli utenti di internet.
Viene lanciato nel 2000.
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.
La rete non ha una specifica topologia:
Per eseguire il lookup:
Le prestazioni (es. tempo di ricerca di un file) peggiorano all’aumentare del numero dei nodi.
I messaggi possono circolare nel sistema indefinitamente, ripassando per nodi già visitati precedentemente.
Il mittente della query potrebbe ricevere più risposte (da più nodi che hanno il file richiesto).
Ogni nodo mantiene la lista di query già valutate.
Ogni query ha associato un TTL, che viene decrementato ad ogni ricezione, cosicché quando il suo valore è nullo la query viene scartata.
La scalabilità di un protocollo é direttamente legata all’efficienza dell’algoritmo usato per il lookup.
Due obiettivi:
I peer sono distinti in:
Ogni foglia è connessa ad alcuni (max 3) ultrapeer.
Gli ultrapeer sono connessi tra loro (almeno 32).
Il lookup è realizzato attraverso il Query Routing Protocol (QRP).
Ciascun nodo produce una Query Routing Table (QRT) con indici (hash values) dei file posseduti.
La QRT viene inviata agli ultrapeer associati.
Ciascun ultrapeer genera la propria QRT come unione di quella relativa ai propri file e delle QRT ricevute.
Un nodo foglia invia una richiesta ad un ultrapeer per volta ed attende per un certo tempo risposta prima di contattare un altro ultrapeer.
Ogni query contiene l’indirizzo di rete del primo ultrapeer contattato dal nodo foglia.
In tal modo chi ha il file contatta direttamente quest’ultimo evitando di ripercorrere a ritroso tutto il path.
BitTorrent è una soluzione P2P di seconda generazione per file sharing.
Un server mantiene .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.
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).
Per migliorare l’efficienza delle operazioni di lookup è possibile considerare una rete (overlay network) costruita al di sopra del protocollo IP che interconnette i nodi del sistema P2P.
Si ottiene così una policy globale per topologia della rete, placement degli oggetti e routing che rende il sistema strutturato.
I nodi rappresentano applicazioni interconnesse per mezzo di link virtuali o logici, ognuno dei quali corrisponde a uno o più link fisici nella rete sottostante.
Un protocollo di Overlay Routing viene utilizzato per localizzare nodi ed oggetti.
Inastradamento delle richieste verso gli host che posseggono una replica dell’oggetto richiesto.
Aggiunta di un oggetto al servizio.
Eliminazione di un oggetto.
Aggiunta di un nodo.
Che si assumerà alcune delle responsabilità di altri nodi.
Eliminazione di un nodo.
I sistemi P2P strutturati fanno uso di Distributed Hash Table (DHT) per associare agli identificatori globali unici dei file (Globally Unique IDentifiers – GUID) la loro locazione.
I GUID sono generati con funzioni hash.
Ad 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.
Tutti i nodi del sistema condividono una tabella hash.
Come identificare il responsabile di una data chiave?
Nodo per oggetto con GUID=4?
1. Caratterizzazione dei sistemi distribuiti
2. Modelli di sistemi distribuiti
3. Tempo e sincronizzazione nei Sistemi Distribuiti
4. Stato globale nei Sistemi Distribuiti
5. Problemi di consenso nei sistemi distribuiti
7. Algoritmi di mutua esclusione nei sistemi distribuiti
8. Algoritmi di elezione nei sistemi distribuiti
10. Il Network File System di SUN Microsystems
11. AFS (Andrew File System) e GFS (Google File System)
12. Transazioni e controllo di concorrenza
13. Transazioni
15. Affidabilità (dependability) dei sistemi software distribuiti
16. Affidabilità dei sistemi software distribuiti
17. Software Faults
18. Classificazione e analisi dei difetti software
G. Coulouris et al.: Distributed Systems: Concepts and Design, V ed., 2011 (Cap. X, da 10.1 a 10.5, eccetto 10.5.2).
I. Stoica et al., “Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications”. In IEEE/ACM Trans. on Networking, 2003.