Semplice spiegazione di base di un Distributed Hash Table (DHT)
https://stackoverflow.com/questions/144360
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Qualcuno potrebbe dare una spiegazione su come funziona un DHT?
Niente di troppo pesante, solo le basi.
Soluzione
Ok, sono fondamentalmente un'idea piuttosto semplice. Un DHT offre un'interfaccia simile a un dizionario, ma i nodi sono distribuiti attraverso la rete. Il trucco con i DHT è che il nodo che arriva a memorizzare una chiave particolare viene trovato con l'hash della chiave, quindi in effetti i bucket della tabella hash sono nodi indipendenti in una rete.
Ciò offre molta tolleranza agli errori e affidabilità, e forse alcuni vantaggi in termini di prestazioni, ma genera anche molti mal di testa. Ad esempio, cosa succede quando un nodo lascia la rete, in caso di errore o in altro modo? E come ridistribuire le chiavi quando un nodo si unisce in modo che il carico sia approssimativamente bilanciato. Vieni a pensarci bene, come puoi distribuire uniformemente le chiavi comunque? E quando un nodo si unisce, come si evita di rimettere in ordine tutto? (Ricorda che dovresti farlo in una normale tabella di hash se aumenti il ??numero di bucket).
Un esempio di DHT che affronta alcuni di questi problemi è un anello logico di n nodi, ognuno dei quali si assume la responsabilità di 1 / n dello spazio delle chiavi. Una volta aggiunto un nodo alla rete, trova un posto nell'anello per sedersi tra altri due nodi e si assume la responsabilità di alcune delle chiavi nei suoi nodi fratelli. La bellezza di questo approccio è che nessuno degli altri nodi nell'anello è interessato; solo i due nodi fratelli devono ridistribuire le chiavi.
Ad esempio, supponiamo che in un anello a tre nodi il primo nodo abbia le chiavi 0-10, il secondo 11-20 e il terzo 21-30. Se arriva un quarto nodo e si inserisce tra i nodi 3 e 0 (ricorda, sono in un anello), può prendersi la responsabilità di dire metà dello spazio delle chiavi di 3, quindi ora si occupa di 26-30 e il nodo 3 si occupa di 21 -25.
Esistono molte altre strutture di sovrapposizione come questa che utilizzano il routing basato sul contenuto per trovare il nodo giusto su cui archiviare una chiave. Individuare una chiave in un anello richiede una ricerca intorno all'anello un nodo alla volta (a meno che non si mantenga una tabella di ricerca locale, problematica in un DHT di migliaia di nodi), che è il routing O (n) -hop. Altre strutture - compresi gli anelli aumentati - garantiscono il routing del negozio O (log n) e alcuni sostengono il routing del negozio O (1) a spese di una maggiore manutenzione.
Leggi la pagina di Wikipedia, e se vuoi davvero approfondire un po ', dai un'occhiata a coursepage presso Harvard che ha un elenco di letture piuttosto completo.
Altri suggerimenti
I DHT forniscono all'utente lo stesso tipo di interfaccia di una tabella hash normale (cerca un valore per chiave), ma i dati sono distribuiti su un numero arbitrario di nodi connessi. Wikipedia ha una buona introduzione di base che essenzialmente rigurgiterei se scrivo di più -
Vorrei aggiungere la risposta utile di HenryR dato che ho appena avuto un'idea di hashing coerente. Una ricerca hash normale / ingenua è una funzione di due variabili, una delle quali è il numero di bucket. La bellezza di un hash coerente è che eliminiamo il numero di bucket "n" dall'equazione.
Nell'hashing ingenuo, la prima variabile è la chiave dell'oggetto da archiviare nella tabella. Chiameremo la chiave " x " ;. La seconda variabile è il numero di bucket, "quot" n ". Quindi, per determinare in quale bucket / macchina è archiviato l'oggetto, devi calcolare: hash (x) mod (n). Pertanto, quando si modifica il numero di bucket, si modifica anche l'indirizzo in cui è archiviato quasi ogni oggetto.
Confronta questo con l'hash coerente. Definiamo " R " come intervallo di una funzione hash. R è solo una costante. In hashing coerente, l'indirizzo di un oggetto si trova in hash (x) / R. Dal momento che la nostra ricerca non è più una funzione del numero di bucket, finiamo per rimappare meno quando cambiamo il numero di bucket.
Dai un'occhiata a questo articolo di Wikipedia Oppure questa slide powerpoint
controlla la dinamo di Amazon, spiega un'implementazione DHT semplice ma innovativa basata sull'hash coerente del cerchio.
