Penjelasan dasar sederhana dari Tabel Hash Terdistribusi (DHT)

Adakah yang bisa memberikan penjelasan tentang cara kerja DHT?

Tidak ada yang terlalu berat, hanya dasar-dasarnya.

Ok, mereka pada dasarnya ide yang sangat sederhana. DHT memberi Anda antarmuka seperti kamus, tetapi node didistribusikan di seluruh jaringan. Trik dengan DHT adalah bahwa simpul yang dapat menyimpan kunci tertentu ditemukan dengan hashing kunci itu, sehingga efeknya tabel hash-table Anda sekarang merupakan simpul independen dalam jaringan.

Ini memberikan banyak toleransi kesalahan dan keandalan, dan mungkin beberapa manfaat kinerja, tetapi juga memunculkan banyak sakit kepala. Misalnya, apa yang terjadi ketika sebuah node meninggalkan jaringan, karena gagal atau sebaliknya? Dan bagaimana Anda mendistribusikan kunci ketika sebuah simpul bergabung sehingga bebannya seimbang. Kalau dipikir-pikir, bagaimana Anda mendistribusikan kunci secara merata? Dan ketika sebuah simpul bergabung, bagaimana Anda menghindari mengulangi semuanya? (Ingat Anda harus melakukan ini dalam tabel hash normal jika Anda menambah jumlah ember).

Salah satu contoh DHT yang menangani beberapa masalah ini adalah cincin logis n node, masing-masing bertanggung jawab atas 1 / n dari ruang kunci. Setelah Anda menambahkan node ke jaringan, ia menemukan tempat di ring untuk duduk di antara dua node lainnya, dan bertanggung jawab atas beberapa kunci dalam node saudara kandungnya. Keindahan dari pendekatan ini adalah bahwa tidak ada node lain di cincin yang terpengaruh; hanya dua simpul saudara yang harus mendistribusikan kunci.

Misalnya, dalam cincin tiga simpul, simpul pertama memiliki kunci 0-10, 11-20 kedua dan 21-30 ketiga. Jika simpul keempat muncul dan memasukkan dirinya di antara simpul 3 dan 0 (ingat, mereka berada di dalam sebuah cincin), ia dapat mengambil tanggung jawab untuk mengatakan setengah dari 3 ruang kunci, jadi sekarang ia berurusan dengan 26-30 dan simpul 3 berurusan dengan 21 -25.

Ada banyak struktur overlay lainnya seperti ini yang menggunakan perutean berbasis konten untuk menemukan simpul yang tepat untuk menyimpan kunci. Menemukan kunci dalam sebuah cincin memerlukan pencarian di sekeliling cincin satu simpul pada satu waktu (kecuali jika Anda menyimpan tabel pencarian lokal, bermasalah dalam DHT ribuan node), yang merupakan O (n) -hop routing. Struktur lain - termasuk cincin augmented - menjamin perutean O (log n) -hop, dan beberapa klaim perutean O (1) -hop dengan biaya pemeliharaan yang lebih tinggi.

Baca halaman wikipedia, dan jika Anda benar-benar ingin tahu sedikit lebih dalam, lihat kursus ini di Harvard yang memiliki daftar bacaan yang cukup komprehensif.

DHT menyediakan jenis antarmuka yang sama kepada pengguna sebagai hashtable normal (mencari nilai berdasarkan kunci), tetapi data didistribusikan melalui jumlah sembarang node yang terhubung. Wikipedia memiliki pengantar dasar yang bagus yang pada dasarnya saya akan memuntahkan jika saya menulis lebih banyak -

http://en.wikipedia.org/wiki/Distributed_hash_table

Saya ingin menambahkan ke jawaban HenryR yang bermanfaat karena saya hanya memiliki wawasan tentang hashing yang konsisten. Pencarian hash normal / naif adalah fungsi dari dua variabel, salah satunya adalah jumlah ember. Keindahan hashing yang konsisten adalah kita menghilangkan jumlah bucket "n", dari persamaan.

Dalam hashing naif, variabel pertama adalah kunci dari objek yang akan disimpan dalam tabel. Kami akan memanggil kunci "x". Variabel kedua adalah jumlah ember, "n". Jadi, untuk menentukan ember / mesin tempat objek disimpan, Anda harus menghitung: hash (x) mod (n). Karena itu, ketika Anda mengubah jumlah ember, Anda juga mengubah alamat tempat hampir setiap objek disimpan.

Bandingkan ini dengan hashing yang konsisten. Mari kita mendefinisikan "R" sebagai rentang fungsi hash. R hanya beberapa konstanta. Dalam hashing yang konsisten, alamat objek terletak di hash (x) / R. Karena pencarian kami bukan lagi fungsi dari jumlah bucket, kami berakhir dengan remapping yang lebih sedikit ketika kami mengubah jumlah bucket.

http://michaelnielsen.org/blog/consistent-hashing/