Tabella hash distribuita - Distributed hash table

Una tabella hash distribuita ( DHT ) è un sistema distribuito che fornisce un servizio di ricerca simile a una tabella hash : le coppie chiave-valore sono archiviate in un DHT e qualsiasi nodo partecipante può recuperare in modo efficiente il valore associato a una determinata chiave . Il vantaggio principale di un DHT è che i nodi possono essere aggiunti o rimossi con un lavoro minimo sulla ridistribuzione delle chiavi. Le chiavi sono identificatori univoci che mappano su valori particolari , che a loro volta possono essere qualsiasi cosa, da indirizzi, a documenti , a dati arbitrari . La responsabilità del mantenimento della mappatura dalle chiavi ai valori è distribuita tra i nodi, in modo tale che un cambiamento nell'insieme dei partecipanti provochi un disturbo minimo. Ciò consente a un DHT di scalare fino a un numero estremamente elevato di nodi e di gestire arrivi, partenze e guasti continui dei nodi.

I DHT formano un'infrastruttura che può essere utilizzata per creare servizi più complessi, come anycast , web caching cooperativo , file system distribuiti , servizi di nomi di dominio , messaggistica istantanea , multicast e anche condivisione di file peer-to-peer e sistemi di distribuzione dei contenuti . Notevoli reti distribuite che utilizzano DHT includono il tracker distribuito di BitTorrent , il Coral Content Distribution Network , la rete Kad , la botnet Storm , l' instant messenger Tox , Freenet , il motore di ricerca YaCy e l' InterPlanetary File System .

Storia

La ricerca DHT è stata originariamente motivata, in parte, da sistemi peer-to-peer (P2P) come Freenet , Gnutella , BitTorrent e Napster , che sfruttavano le risorse distribuite su Internet per fornire un'unica applicazione utile. In particolare, hanno approfittato dell'aumento della larghezza di banda e della capacità del disco rigido per fornire un servizio di condivisione di file.

Questi sistemi differivano nel modo in cui individuavano i dati offerti dai loro pari. Napster, il primo sistema di distribuzione di contenuti P2P su larga scala, richiedeva un server di indicizzazione centrale: ogni nodo, al momento dell'adesione, inviava un elenco di file conservati localmente al server, che eseguiva ricerche e indirizzava le query ai nodi che detenevano il risultati. Questo componente centrale ha lasciato il sistema vulnerabile ad attacchi e azioni legali.

Gnutella e reti simili sono passate a un modello di query flooding : in sostanza, ogni ricerca comporterebbe la trasmissione di un messaggio a tutte le altre macchine della rete. Pur evitando un singolo punto di errore , questo metodo era significativamente meno efficiente di Napster. Le versioni successive dei client Gnutella sono passate a un modello di query dinamico che ha notevolmente migliorato l'efficienza.

Freenet è completamente distribuito, ma utilizza un routing euristico basato su chiavi in cui ogni file è associato a una chiave e i file con chiavi simili tendono a raggrupparsi su un insieme simile di nodi. È probabile che le query vengano instradate attraverso la rete a un tale cluster senza dover visitare molti peer. Tuttavia, Freenet non garantisce che i dati verranno trovati.

Le hash table distribuite utilizzano un routing basato su chiavi più strutturato per ottenere sia il decentramento di Freenet e Gnutella, sia l'efficienza e i risultati garantiti di Napster. Uno svantaggio è che, come Freenet, i DHT supportano direttamente solo la ricerca con corrispondenza esatta, piuttosto che la ricerca per parole chiave, sebbene l' algoritmo di routing di Freenet possa essere generalizzato a qualsiasi tipo di chiave in cui è possibile definire un'operazione di prossimità.

Nel 2001, quattro sistemi - CAN , Chord , Pastry e Tapestry - hanno acceso i DHT come argomento di ricerca popolare. Un progetto chiamato Infrastructure for Resilient Internet Systems (Iris) è stato finanziato da una sovvenzione di 12 milioni di dollari dalla National Science Foundation degli Stati Uniti nel 2002. Tra i ricercatori c'erano Sylvia Ratnasamy , Ion Stoica , Hari Balakrishnan e Scott Shenker . Al di fuori del mondo accademico, la tecnologia DHT è stata adottata come componente di BitTorrent e nel Coral Content Distribution Network .

Proprietà

I DHT enfatizzano tipicamente le seguenti proprietà:

• Autonomia e decentralizzazione : i nodi formano collettivamente il sistema senza alcun coordinamento centrale.
• Tolleranza ai guasti : il sistema dovrebbe essere affidabile (in un certo senso) anche con nodi che si uniscono, escono e si guastano continuamente.
• Scalabilità : il sistema dovrebbe funzionare in modo efficiente anche con migliaia o milioni di nodi.

Una tecnica chiave utilizzata per raggiungere questi obiettivi è che ogni nodo deve coordinarsi solo con pochi altri nodi nel sistema - più comunemente, O (log n ) degli n partecipanti (vedi sotto) - in modo che solo una quantità limitata di lavoro deve essere fatto per ogni cambiamento di appartenenza.

Alcuni progetti DHT cercano di essere protetti da partecipanti malintenzionati e di consentire ai partecipanti di rimanere anonimi , sebbene ciò sia meno comune rispetto a molti altri sistemi peer-to-peer (in particolare la condivisione di file ); vedi P2P anonimo .

Infine, i DHT devono affrontare i problemi dei sistemi distribuiti più tradizionali come il bilanciamento del carico , l'integrità dei dati e le prestazioni (in particolare, garantendo che operazioni come il routing e l'archiviazione o il recupero dei dati vengano completate rapidamente).

Struttura

La struttura di un DHT può essere scomposta in diversi componenti principali. La base è uno spazio delle chiavi astratto , come l'insieme di stringhe a 160 bit . Uno schema di partizionamento dello spazio delle chiavi suddivide la proprietà di questo spazio delle chiavi tra i nodi partecipanti. Una rete overlay collega quindi i nodi, consentendo loro di trovare il proprietario di una determinata chiave nello spazio delle chiavi.

Una volta che questi componenti sono a posto, un uso tipico del DHT per l'archiviazione e il recupero potrebbe procedere come segue. Supponiamo che lo spazio delle chiavi sia l'insieme di stringhe a 160 bit. Per indicizzare un file con un dato nome file e dati nel DHT, viene generato l' hash SHA-1 del nome file , producendo una chiave k a 160 bit e un messaggio put ( k, dati ) viene inviato a qualsiasi nodo che partecipa al DHT. Il messaggio viene inoltrato da nodo a nodo attraverso la rete overlay fino a raggiungere il singolo nodo responsabile della chiave k come specificato dal partizionamento dello spazio delle chiavi . Quel nodo quindi memorizza la chiave e i dati. Qualsiasi altro client può quindi recuperare il contenuto del file eseguendo nuovamente l'hashing del nome del file per produrre k e chiedendo a qualsiasi nodo DHT di trovare i dati associati a k con un messaggio get ( k ) . Il messaggio verrà nuovamente instradato attraverso l'overlay al nodo responsabile di k , che risponderà con i dati memorizzati .

Il partizionamento dello spazio delle chiavi e i componenti di rete overlay sono descritti di seguito con l'obiettivo di catturare le idee principali comuni alla maggior parte dei DHT; molti disegni differiscono nei dettagli.

Partizionamento dello spazio delle chiavi

La maggior parte dei DHT usa qualche variante di hashing coerente o rendezvous hashing per mappare le chiavi ai nodi. I due algoritmi sembrano essere stati ideati indipendentemente e simultaneamente per risolvere il problema della tabella hash distribuita.

Sia l'hashing coerente che il rendezvous hashing hanno la proprietà essenziale che la rimozione o l'aggiunta di un nodo modifica solo l'insieme di chiavi di proprietà dei nodi con ID adiacenti e lascia inalterati tutti gli altri nodi. Contrasta questo con una tabella hash tradizionale in cui l'aggiunta o la rimozione di un bucket provoca la rimappatura di quasi l'intero keyspace. Poiché qualsiasi cambiamento di proprietà corrisponde tipicamente al movimento ad alta intensità di banda degli oggetti memorizzati nel DHT da un nodo all'altro, è necessario ridurre al minimo tale riorganizzazione per supportare in modo efficiente alti tassi di abbandono (arrivo e guasto del nodo).

Hashing coerente

L'hashing coerente utilizza una funzione che definisce una nozione astratta della distanza tra le chiavi e , che non è correlata alla distanza geografica o alla latenza di rete . Ad ogni nodo viene assegnata una singola chiave chiamata identificatore (ID). Un nodo con ID possiede tutte le chiavi per le quali è l'ID più vicino, misurato secondo . ${\displaystyle \delta (k_{1},k_{2})}$${\displaystyle k_{1}}$${\displaystyle k_{2}}$${\displaystyle i_{x}}$${\displaystyle k_{m}}$${\displaystyle i_{x}}$${\displaystyle \delta (k_{m},i_{x})}$

Ad esempio, il Chord DHT utilizza l'hashing coerente, che tratta i nodi come punti su un cerchio, ed è la distanza che percorre in senso orario attorno al cerchio da a . Pertanto, lo spazio delle chiavi circolare è suddiviso in segmenti contigui i cui punti finali sono gli identificatori di nodo. Se e sono due ID adiacenti, con una distanza inferiore in senso orario da a , allora il nodo con ID possiede tutte le chiavi che cadono tra e . ${\displaystyle \delta (k_{1},k_{2})}$${\displaystyle k_{1}}$${\displaystyle k_{2}}$${\displaystyle i_{1}}$${\displaystyle i_{2}}$${\displaystyle i_{1}}$${\displaystyle i_{2}}$${\displaystyle i_{2}}$${\displaystyle i_{1}}$${\displaystyle i_{2}}$

Rendezvous hashing

Nell'hashing del rendezvous, chiamato anche hash di peso casuale più elevato (HRW), tutti i client utilizzano la stessa funzione di hash (scelta in anticipo) per associare una chiave a uno degli n server disponibili. Ogni client ha lo stesso elenco di identificatori { S ₁ , S ₂ , ..., S _n } , uno per ogni server. Data una chiave k , un client calcola n pesi hash w ₁ = h ( S ₁ , k ), w ₂ = h ( S ₂ , k ), ..., w _n = h ( S _n , k ) . Il client associa quella chiave al server corrispondente al peso hash più alto per quella chiave. Un server con ID possiede tutte le chiavi per le quali il peso hash è maggiore del peso hash di qualsiasi altro nodo per quella chiave. ${\displaystyle h()}$${\displaystyle S_{x}}$${\displaystyle k_{m}}$${\displaystyle h(S_{x},k_{m})}$

Hashing che preserva la località

L'hashing di conservazione della località garantisce che chiavi simili vengano assegnate a oggetti simili. Ciò può consentire un'esecuzione più efficiente delle query di intervallo, tuttavia, a differenza dell'utilizzo dell'hashing coerente, non vi è più alcuna garanzia che le chiavi (e quindi il carico) siano distribuite uniformemente in modo casuale nello spazio delle chiavi e sui peer partecipanti. I protocolli DHT come Self-Chord e Oscar affrontano tali problemi. Self-Chord disaccoppia le chiavi oggetto dagli ID peer e ordina le chiavi lungo l'anello con un approccio statistico basato sul paradigma dell'intelligenza dello sciame . L'ordinamento garantisce che chiavi simili vengano archiviate dai nodi vicini e che le procedure di rilevamento, incluse le query di intervallo , possano essere eseguite in tempo logaritmico. Oscar costruisce una rete navigabile di un piccolo mondo basata sul campionamento random walk assicurando anche il tempo di ricerca logaritmico.

Rete sovrapposta

Ogni nodo mantiene un insieme di collegamenti ad altri nodi (i suoi vicini o la tabella di routing ). Insieme, questi collegamenti formano la rete overlay. Un nodo sceglie i suoi vicini secondo una certa struttura, chiamata topologia della rete .

Tutte le topologie DHT condividono alcune varianti della proprietà più essenziale: per ogni chiave k , ogni nodo ha un ID nodo che possiede k o ha un collegamento a un nodo il cui ID nodo è più vicino a k , in termini di distanza keyspace definita sopra . È quindi facile instradare un messaggio al proprietario di una qualsiasi chiave k utilizzando il seguente algoritmo greedy (che non è necessariamente globalmente ottimale): ad ogni passaggio, inoltra il messaggio al vicino il cui ID è più vicino a k . Quando non esiste tale vicino, allora dobbiamo essere arrivati ​​al nodo più vicino, che è il proprietario di k come definito sopra. Questo stile di routing è talvolta chiamato routing basato su chiave .

Oltre alla correttezza di base del routing, due importanti vincoli sulla topologia sono garantire che il numero massimo di hop in qualsiasi route (lunghezza del percorso) sia basso, in modo che le richieste vengano completate rapidamente; e che il numero massimo di vicini di qualsiasi nodo ( grado massimo del nodo ) è basso, in modo che l'overhead di manutenzione non sia eccessivo. Naturalmente, avere percorsi più brevi richiede un grado massimo più alto . Alcune scelte comuni per il grado massimo e la lunghezza del percorso sono le seguenti, dove n è il numero di nodi nel DHT, utilizzando la notazione Big O :

massimo livello	Lunghezza massima del percorso	Usato in	Nota
${\displaystyle O(1)}$	${\displaystyle O(n)}$		Lunghezze di ricerca peggiori, con tempi di ricerca probabilmente molto più lenti
${\displaystyle O(1)}$	${\displaystyle O(\log n)}$	Koorde (con grado costante)	Più complesso da implementare, ma è possibile trovare un tempo di ricerca accettabile con un numero fisso di connessioni
${\displaystyle O(\log n)}$	${\displaystyle O(\log n)}$	Chord Kademlia Pasticceria Arazzo	Più comune, ma non ottimale (grado/lunghezza del percorso). Chord è la versione più elementare, con Kademlia che sembra la variante ottimizzata più popolare (avrebbe dovuto migliorare la ricerca media)
${\displaystyle O(\log n)}$	${\displaystyle O(\log n/\log(\log n))}$	Koorde (con ricerca ottimale)	Più complesso da implementare, ma le ricerche potrebbero essere più veloci (hanno un limite inferiore del caso peggiore)
${\displaystyle O({\sqrt {n}})}$	${\displaystyle O(1)}$		Peggiori esigenze di archiviazione locale, con molte comunicazioni dopo che qualsiasi nodo si connette o si disconnette

La scelta più comune, grado/lunghezza del percorso, non è ottimale in termini di compromesso grado/lunghezza del percorso, ma tali topologie in genere consentono una maggiore flessibilità nella scelta dei vicini. Molti DHT utilizzano questa flessibilità per scegliere i vicini che sono vicini in termini di latenza nella rete fisica sottostante. In generale, tutti i DHT costruiscono topologie di rete navigabili di piccole dimensioni, che compensano la lunghezza del percorso rispetto al grado di rete. ${\displaystyle O(\log n)}$

La lunghezza massima del percorso è strettamente correlata al diametro : il numero massimo di salti in qualsiasi percorso più breve tra i nodi. Chiaramente, la lunghezza del percorso nel caso peggiore della rete è grande almeno quanto il suo diametro, quindi i DHT sono limitati dal compromesso grado/diametro che è fondamentale nella teoria dei grafi . La lunghezza del percorso può essere maggiore del diametro, poiché l'algoritmo di routing greedy potrebbe non trovare i percorsi più brevi.

Algoritmi per reti sovrapposte

Oltre al routing, esistono molti algoritmi che sfruttano la struttura della rete overlay per inviare un messaggio a tutti i nodi, o un sottoinsieme di nodi, in un DHT. Questi algoritmi vengono utilizzati dalle applicazioni per eseguire overlay multicast , query di intervallo o per raccogliere statistiche. Due sistemi che si basano su questo approccio sono Structella, che implementa flooding e random walk su una sovrapposizione di Pastry, e DQ-DHT, che implementa un algoritmo di ricerca di query dinamico su una rete Chord.

Sicurezza

A causa della decentralizzazione, della tolleranza ai guasti e della scalabilità dei DHT, sono intrinsecamente più resistenti contro un aggressore ostile rispetto a un sistema centralizzato.

Sono fattibili sistemi aperti per l'archiviazione di dati distribuiti che sono robusti contro aggressori ostili di massa.

Un sistema DHT accuratamente progettato per avere la tolleranza ai guasti bizantina può difendersi da una debolezza della sicurezza, nota come attacco Sybil , che colpisce tutti i progetti DHT attuali.

Petar Maymounkov, uno degli autori originali di Kademlia , ha proposto un modo per aggirare la debolezza dell'attacco Sybil incorporando relazioni di fiducia sociale nella progettazione del sistema. Il nuovo sistema, nome in codice Tonika o anche conosciuto con il nome di dominio 5ttt, si basa su un progetto di algoritmo noto come "instradamento elettrico" e co-autore con il matematico Jonathan Kelner. Maymounkov ha ora intrapreso uno sforzo completo per l'implementazione di questo nuovo sistema. Tuttavia, la ricerca sulle difese efficaci contro gli attacchi Sybil è generalmente considerata una questione aperta e ogni anno viene proposta un'ampia varietà di potenziali difese nelle principali conferenze di ricerca sulla sicurezza.

implementazioni

Le differenze più notevoli riscontrate nelle istanze pratiche delle implementazioni DHT includono almeno quanto segue:

• Lo spazio degli indirizzi è un parametro di DHT. Diversi DHT del mondo reale utilizzano uno spazio chiave a 128 o 160 bit.
• Alcuni DHT del mondo reale utilizzano funzioni hash diverse da SHA-1 .
• Nel mondo reale la chiave k potrebbe essere un hash del contenuto di un file piuttosto che un hash del nome di un file per fornire spazio di archiviazione indirizzabile al contenuto , in modo che la ridenominazione del file non impedisca agli utenti di trovarlo.
• Alcuni DHT possono anche pubblicare oggetti di tipo diverso. Ad esempio, la chiave k potrebbe essere l' ID del nodo e i dati associati potrebbero descrivere come contattare questo nodo. Ciò consente la pubblicazione delle informazioni di presenza e viene spesso utilizzato nelle applicazioni IM, ecc. Nel caso più semplice, l' ID è solo un numero casuale che viene utilizzato direttamente come chiave k (quindi in un DHT a 160 bit ID sarà un 160 bit numero, di solito scelto a caso). In alcuni DHT, la pubblicazione degli ID dei nodi viene utilizzata anche per ottimizzare le operazioni DHT.
• La ridondanza può essere aggiunta per migliorare l'affidabilità. La coppia di chiavi (k, data) può essere memorizzata in più di un nodo corrispondente alla chiave. Di solito, invece di selezionare un solo nodo, gli algoritmi DHT del mondo reale selezionano i nodi adatti, dove i è un parametro specifico dell'implementazione del DHT. In alcuni progetti DHT, i nodi accettano di gestire un determinato intervallo di keyspace, la cui dimensione può essere scelta in modo dinamico, anziché codificato.
• Alcuni DHT avanzati come Kademlia eseguono prima ricerche iterative attraverso il DHT per selezionare un insieme di nodi adatti e inviare messaggi put(k, data) solo a quei nodi, riducendo così drasticamente il traffico inutile, poiché i messaggi pubblicati vengono inviati solo ai nodi che sembrano adatti per memorizzare la chiave k ; e le ricerche iterative coprono solo un piccolo insieme di nodi anziché l'intero DHT, riducendo l'inoltro inutile. In tali DHT, l'inoltro di messaggi put(k, data) può avvenire solo come parte di un algoritmo di autoriparazione: se un nodo di destinazione riceve un messaggio put(k, data) , ma ritiene che k sia fuori dal suo intervallo gestito e è noto un nodo più vicino (in termini di keyspace DHT), il messaggio viene inoltrato a quel nodo. In caso contrario, i dati vengono indicizzati localmente. Questo porta a un comportamento DHT in qualche modo autobilanciante. Naturalmente, un tale algoritmo richiede che i nodi pubblichino i propri dati di presenza nel DHT in modo che possano essere eseguite le ricerche iterative.
• Poiché sulla maggior parte delle macchine l'invio di messaggi è molto più costoso degli accessi alle tabelle hash locali, ha senso raggruppare molti messaggi relativi a un particolare nodo in un singolo batch. Supponendo che ogni nodo abbia un batch locale composto al massimo da b operazioni, la procedura di raggruppamento è la seguente. Ciascun nodo ordina prima il proprio batch locale in base all'identificatore del nodo responsabile dell'operazione. Usando bucket sort , questo può essere fatto in O(b + n) , dove n è il numero di nodi nel DHT. Quando ci sono più operazioni che indirizzano la stessa chiave all'interno di un batch, il batch viene condensato prima di essere inviato. Ad esempio, più ricerche della stessa chiave possono essere ridotte a uno o più incrementi possono essere ridotti a una singola operazione di aggiunta. Questa riduzione può essere implementata con l'aiuto di una tabella hash locale temporanea. Infine, le operazioni vengono inviate ai rispettivi nodi.

Esempi

Protocolli e implementazioni DHT

• Apache Cassandra
• BASTONE Sovrapposizione
• Mainline DHT – DHT standard utilizzato da BitTorrent (basato su Kademlia fornito da Khashmir)
• Rete indirizzabile a contenuto (CAN)
• Accordo
• Koorde
• Kademlia
• Pasticcino
• P-Grid
• Riak
• Arazzo
• TomP2P
• Voldemort

Applicazioni che utilizzano DHT

• BTDigg : motore di ricerca DHT BitTorrent
• Codeen : web caching
• Rete di distribuzione di contenuti Coral
• Freenet : una rete anonima resistente alla censura
• GlusterFS : un file system distribuito utilizzato per la virtualizzazione dello storage
• GNUnet : rete di distribuzione simile a Freenet che include un'implementazione DHT
• I2P : una rete peer-to-peer anonima open source
• I2P-Bote : e-mail anonima sicura senza server
• IPFS : un protocollo di distribuzione ipermediale peer-to-peer indirizzabile ai contenuti
• JXTA : piattaforma P2P open source
• Oracle Coherence : una griglia di dati in memoria costruita su un'implementazione Java DHT
• Perfect Dark : un'applicazione di condivisione file peer-to-peer dal Giappone
• RetroShare : un amico-a-friend network
• Jami : una piattaforma di comunicazione vocale, video e chat che preserva la privacy, basata su un DHT simile a Kademlia
• Tox : un sistema di messaggistica istantanea destinato a funzionare come sostituto di Skype
• Twister : una piattaforma peer-to-peer di microblogging
• YaCy : un motore di ricerca distribuito

Guarda anche

• Couchbase Server : un sistema di archiviazione di oggetti distribuiti in cluster persistente, replicato e compatibile con il protocollo memcached.
• Memcached : un sistema di memorizzazione nella cache di oggetti di memoria distribuita ad alte prestazioni.
• Albero hash prefisso : query sofisticate su DHT.
• Merkle tree : albero avente ogni nodo non foglia etichettato con l'hash delle etichette dei suoi nodi figli.
• La maggior parte degli archivi dati distribuiti utilizza una qualche forma di DHT per la ricerca.
• I grafici di salto sono una struttura dati efficiente per l'implementazione di DHT.

Riferimenti

link esterno

• Tabelle hash distribuite, parte 1 di Brandon Wiley.
• Le tabelle hash distribuite collegano la pagina di Carles Pairot sulla ricerca DHT e P2P
• kademlia.scs.cs.nyu.edu Archive.org istantanee di kademlia.scs.cs.nyu.edu
• Eng-Keong Lua; Crowcroft, Jon; Pias, Marcelo; Sharma, Ravi; Lim, Steve (2005). "Indagine IEEE sugli schemi di rete sovrapposti". CiteSeerX  10.1.1.111.4197 : Cite journal richiede |journal=( help ) che copra reti di overlay decentralizzate non strutturate e strutturate, inclusi DHT (Chord, Pastry, Tapestry e altri).
• Mainline DHT Measurement presso il Dipartimento di Informatica, Università di Helsinki, Finlandia.