Tabella di hash distribuita

Le tabelle di hash distribuite (in inglese distributed hash tables, indicate anche come DHT) sono una classe di sistemi distribuiti decentralizzati che partizionano l'appartenenza di un set di chiavi tra i nodi partecipanti, e possono inoltrare in maniera efficiente i messaggi all'unico proprietario di una determinata chiave. Ciascun nodo è l'analogo di un array slot in una hash table.

Le DHT sono tipicamente progettate per gestire un vasto numero di nodi, anche nei casi in cui ci siano continui ingressi o improvvisi guasti di alcuni di essi. Questo tipo di infrastruttura può essere utilizzata per implementare servizi più complessi, quali file system distribuiti, sistemi peer-to-peer di file sharing, web caching cooperativo, multicast, anycast e domain name service.

Originariamente la ricerca sulle DHT fu in parte motivata da sistemi peer-to-peer quali Napster, Gnutella, Freenet, che si basavano o basano su risorse distribuite in Internet per offrire l'applicazione desiderata. In particolare questi sistemi si avvantaggiavano dell'aumento di larghezza di banda e sull'incremento degli spazi degli hard disk per fornire un sistema di file sharing.

Questi sistemi differivano tra loro in come essi trovavano i dati contenuti dai rispettivi peer. Napster aveva un indice in un server centralizzato: ogni nodo, al suo ingresso, mandava una lista dei file che possedeva localmente al server, il quale si sarebbe occupato di effettuare le ricerche ed indicare ai richiedenti i nodi che conservavano i dati desiderati. Questa componente centralizzata rendeva il sistema vulnerabile ad attacchi. Gnutella e reti simili si spostarono verso un modello che prevedeva il flooding; in sostanza, ciascuna ricerca era di fatto costituita in un messaggio che veniva trasmesso a tutte le altre macchine della rete. Sebbene questo metodo evitasse la possibilità di un singolo punto di rottura, il meccanismo risultava assai meno efficiente rispetto a Napster. Infine ci fu Freenet che prevedeva un meccanismo completamente distribuito, ma impiegando un indirizzamento euristico basato sulle chiavi nel quale ciascun file era associato ad una chiave, e file con chiavi simili tendevano a raggrupparsi in set di nodi simili tra loro. Risultava pertanto verosimile che le richieste venissero inoltrate attraverso la rete in direzione di questi set di nodi senza dover visitare molti peer. Tuttavia, Freenet non offriva la certezza di trovare i dati richiesti.

Le tabelle di hash distribuite utilizzano un tipo di routing basato sulle chiavi maggiormente strutturato al fine di ottenere sia la decentralizzazione di Gnutella e Freenet, sia l'efficienza e l'affidabilità nelle ricerche offerte da Napster. Un aspetto negativo è che, come in Freenet, le DHT offrono una ricerca solo per titoli esatti e non su parole chiave, sebbene questo tipo di funzionalità possa essere inserita in uno strato superiore della DHT. Ad esempio, esistono delle DHT con topologia ad ipercubo che permettono la ricerca utilizzando delle parole chiave.

Le prime quattro DHT – CAN, Chord, Pastry e Tapestry – vennero presentate tutte nello stesso periodo, nel 2001. Da allora, questo settore di ricerca è abbastanza attivo. Al di là degli studi accademici, la tecnologia DHT è stata adottata come un componente di BitTorrent, eMule e nel Coral Content Distribution Network.

Le caratteristiche delle DHT enfatizzano le seguenti proprietà:

• Decentralizzazione: i nodi formano collettivamente il sistema senza alcun coordinamento centrale.
• Scalabilità: il sistema è predisposto per un funzionamento efficiente anche con centinaia di milioni di nodi.
• Tolleranza ai guasti: il sistema dovrebbe risultare affidabile anche in presenza di nodi che entrano, escono dalla rete o sono soggetti a malfunzionamenti con elevata frequenza.

La tecnica chiave utilizzata per raggiungere questi scopi è costituita dal fatto che ciascun nodo ha bisogno di rimanere in contatto solo con un piccolo numero di altri nodi della rete – solitamente … degli altri n partecipanti (vedi sotto) – in questa maniera la rete è sottoposta ad una minima quantità di lavoro per ogni modifica che avviene nel set di nodi che la costituiscono.

Alcune strutture di DHT cercano di implementare meccanismi di sicurezza per contrastare nodi partecipanti malevoli e consentire ai nodi di rimanere anonimi, sebbene ciò sia meno comune rispetto agli altri sistemi peer-to-peer (specialmente per quanto riguarda il file sharing).

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. L'overlay network connette i nodi, consentendo loro di trovare il proprietario di una determinata chiave nel keyspace.

Con queste posizioni, il tipico funzionamento di una DHT per immagazzinare e poi recuperare un dato potrebbe 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 data, viene inizialmente calcolato l'SHA1 hash 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 fino a che esso non raggiunge il singolo nodo che è responsabile per la chiave k in accordo alle regole per il partizionamento del keyspace, laddove la coppia (k,data) è 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.

Ciascuna di queste componenti è descritta qui nel seguito allo scopo di fissare i principi fondamentali comuni alla maggior parte delle DHT; alcuni meccanismi possono differire nei dettagli.

Molte DHT usano alcune varianti del consistent hashing per mappare le chiavi ai nodi. Questa tecnica impiega una funzione ${\displaystyle \delta (k_{1},k_{2})}$ che definisce la nozione astratta di distanza tra la chiave ${\displaystyle k_{1}}$ e la chiave ${\displaystyle k_{2}}$ . A ciascun nodo è assegnata una chiave che è detta identificativo (ID). Ad un nodo con ID i appartengono tutte le chiavi per cui i è l'ID più vicino, misurando in base a ${\displaystyle \delta }$.

Esempio. L'algoritmo Chord considera le chiavi come punti su una circonferenza, e ${\displaystyle \delta (k_{1},k_{2})}$ è la distanza percorsa (in senso orario) sul cerchio tra ${\displaystyle k_{1}}$ e ${\displaystyle k_{2}}$. Perciò, il keyspace circolare è diviso in segmenti contigui i cui punti terminali sono gli identificativi di nodo. Se ${\displaystyle i_{1}}$ e ${\displaystyle i_{2}}$ sono due IDs adiacenti, allora il nodo con ID ${\displaystyle i_{2}}$ è proprietario di tutte le chiavi che cadono tra ${\displaystyle i_{1}}$ e ${\displaystyle i_{2}}$.

Il consistent hashing ha la caratteristica fondamentale che la rimozione o l'addizione di un nodo modifica solo il set di chiavi posseduti dai nodi con IDs adiacenti, senza coinvolgere tutti gli altri nodi. Tutto ciò al contrario di una hash table tradizionale, nella quale l'addizione o la rimozione di un bucket causa un rimappaggio di quasi tutto l'intero keyspace. Dal momento che ogni modifica nel set di chiavi di cui un nodo è responsabile corrisponde tipicamente ad un intenso (per quanto riguarda la larghezza di banda) movimento da un nodo all'altro di oggetti immagazzinati nella DHT, una minimizzazione di questi movimenti di riorganizzazione è necessaria al fine di far fronte in maniera efficiente a peers che hanno un comportamento molto dinamico (elevato numero di ingressi, uscite o malfunzionamenti).

Ciascun nodo mantiene un set di links agli altri nodi (i suoi vicini). Tutti insieme questi nodi formano l'overlay network, e vengono organizzati in modo strutturato, dando così forma alla topologia della rete.

Tutte le topologie di DPT condividono qualche variante della proprietà più essenziale: 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 nel keyspace, come definito precedentemente. A questo punto risulta quindi facile inoltrare un messaggio al proprietario di una qualsiasi chiave k utilizzando il seguente algoritmo greedy: ad ogni passo successivo, inoltra il messaggio al vicino il cui ID è più vicino a k. Quando non esiste un vicino con queste caratteristiche, allora si è giunti al nodo effettivamente più vicino, il quale deve essere il proprietario di k in accordo con quanto definito sopra. Questo tipo di routing viene talvolta definito come key based routing.

Al di là della correttezza di fondo di questo tipo di routing, vi sono due vincoli chiave nella topologia al fine 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. Vi è un compromesso tra questi due criteri che è fondamentale nella teoria dei grafi. Alcune scelte comuni sono fra quelle illustrate qui di seguito, dove n è il numero dei nodi nella DHT:

• Grado ${\displaystyle O(1)}$, dilazione ${\displaystyle O(\log n)}$
• Grado ${\displaystyle O(\log n)}$, dilazione ${\displaystyle O(\log n/\log \log n)}$
• Grado ${\displaystyle O(\log n)}$, dilazione ${\displaystyle O(\log n)}$
• Grado ${\displaystyle O(n^{1/2})}$, dilazione ${\displaystyle O(1)}$

La terza scelta è la più comune, sebbene non sia l'ottima in termini di compromesso grado/dilazione, poiché tale topologia tipicamente consente una maggiore flessibilità in termini di scelta dei vicini. Ciò è utile, ad esempio, per scegliere dei vicini che siano conformi alla topologia e al tempo stesso simili in termini di latenza nella sottostante rete fisica.

Oltre agli algoritmi di routing, esistono diversi algoritmi che sfruttano la struttura dell'overlay network di una DHT per inviare un messaggio a tutti i nodi, o ad un sottoinsieme dei nodi, della DHT stessa^[1]. Questi algoritmi vengono utilizzati dalle applicazioni per eseguire operazioni di multicast sull'overlay, per effettuare range query, o per raccogliere statistiche. Due sistemi basati su questo approccio sono Structella^[2], che implementa flooding e random walk su sull'overlay di una rete Pastry, e DQ-DHT, che implementa un algoritmo di dynamic querying su una rete Chord^[3].

• Chord
• Kademlia
• (EN) Bamboo, su bamboo-dht.org.
• (EN) Bunshin, su planet.urv.es.
• (EN) CAN (Content Addressable Network)
• (EN) DKS system, su dks.sics.se. URL consultato l'8 maggio 2019 (archiviato dall'url originale il 20 gennaio 2012).
• (EN) JGroups DHT implementation, su jgroups.org.
• (EN) Pastry, su freepastry.org.
• (EN) Tapestry e nuova implementazione chiamata Chimera.

• BitTorrent: File distribution. BitTorrent utilizza opzionalmente una DHT come un tracker distribuito per offrire un rendezvous tra clienti che stanno scaricando un particolare file.
• Coral Content Distribution Network
• eMule: File sharing.
• NEOnet: File sharing.
• Overnet: File sharing.
• Transmission: Client Bittorent Open Source.

• (EN) Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris, Ion Stoica, Looking up data in P2P systems, in Communications of the ACM, February 2003.
• (EN) Gurmeet Singh Manku, Dipsea: A Modular Distributed Hash Table, Ph. D. Thesis (Stanford University), August 2004.
• (EN) Moni Naor and Udi Wieder, Novel Architectures for P2P Applications: the Continuous-Discrete Approach, Proc. SPAA, 2003.

• DHT su Torrent Wiki, su torrent.culturaliberap2p.it. URL consultato il 27 luglio 2010 (archiviato dall'url originale il 24 agosto 2010).
• (EN) Distributed Hash Tables, Part 1 by Brandon Wiley.
• (EN) Distributed Hash Tables links Archiviato il 5 febbraio 2006 in Internet Archive. Pagina di Carles Pairot sulle DHT e la ricerca nel P2P.
• (EN) Sloppy Hashing and Self-Organizing Clusters: pubblicazioni dal progetto Coral Content Distribution Network.
• (EN) Project IRIS (Infrastructure for Resilient Internet Systems)
• (EN) Various DHT publications Pagina di El-Ansary's Page sulla ricerca sulle DHT.

Portale Telematica: accedi alle voci di Teknopedia che parlano di reti, telecomunicazioni e protocolli di rete