Penelitian utama dalam artikel ini adalah kode algoritma consistenthashing.
Algoritma Hashing yang konsisten diusulkan oleh MIT pada tahun 1997 (lihat 0). Tujuan desainnya adalah untuk memecahkan masalah hotpot di internet, dan niat aslinya sangat mirip dengan ikan mas. Hashing yang konsisten mengoreksi masalah yang disebabkan oleh algoritma hashing sederhana yang digunakan oleh ikan mas, sehingga DHT dapat benar -benar diterapkan di lingkungan P2P.
Hashing yang konsisten mengusulkan empat kondisi adaptasi yang harus dipenuhi oleh algoritma hashing dalam lingkungan cache yang berubah secara dinamis:
Balance berarti bahwa hasil hash dapat didistribusikan ke semua cache sebanyak mungkin, sehingga semua ruang cache dapat digunakan. Banyak algoritma hash dapat memenuhi kondisi ini.
Monotonitas mengacu pada jika beberapa konten telah dikirim ke cache yang sesuai melalui hashing, dan cache baru ditambahkan ke sistem. Hasil hash harus memastikan bahwa konten yang dialokasikan asli dapat dipetakan ke cache baru tanpa dipetakan ke buffer lain dalam koleksi cache lama.
Algoritma hashing sederhana seringkali tidak dapat memenuhi persyaratan monotonisitas, seperti hash linear paling sederhana:
x → ax + b mod (p)
Dalam rumus di atas, P mewakili ukuran semua cache. Tidak sulit untuk melihat bahwa ketika ukuran cache berubah (dari P1 ke P2), semua hasil hash asli akan berubah, sehingga tidak memenuhi persyaratan monotonisitas.
Perubahan hasil hash berarti bahwa ketika ruang cache berubah, semua hubungan pemetaan perlu diperbarui dalam sistem. Dalam sistem P2P, perubahan cache setara dengan peer gabungan atau keluar dari sistem. Situasi ini sering terjadi dalam sistem P2P, yang akan membawa komputasi besar dan beban transmisi. Monotonitas mensyaratkan bahwa algoritma hash dapat menghindari situasi ini.
Dalam lingkungan terdistribusi, terminal mungkin tidak melihat semua cache, tetapi hanya dapat melihat beberapa dari mereka. Ketika terminal ingin memetakan konten ke cache melalui proses hashing, karena rentang cache yang dilihat oleh terminal yang berbeda mungkin berbeda, hasil hashing tidak konsisten. Hasil akhirnya adalah bahwa konten yang sama dipetakan ke area cache yang berbeda dengan terminal yang berbeda. Situasi ini jelas harus dihindari karena menyebabkan konten yang sama disimpan dalam buffer yang berbeda, mengurangi efisiensi penyimpanan sistem. Definisi dispersi adalah keparahan situasi di atas. Algoritma hashing yang baik harus dapat menghindari ketidakkonsistenan sebanyak mungkin, yaitu, untuk meminimalkan dispersi.
Masalah beban sebenarnya melihat masalah desentralisasi dari perspektif lain. Karena terminal yang berbeda dapat memetakan konten yang sama ke buffer yang berbeda, untuk buffer tertentu, itu juga dapat dipetakan ke konten yang berbeda oleh pengguna yang berbeda. Seperti dispersi, situasi ini harus dihindari, jadi algoritma hashing yang baik harus dapat meminimalkan beban buffer.
Di permukaan, Hashing yang konsisten menargetkan masalah buffering terdistribusi, tetapi jika Anda menganggap buffering sebagai rekan dalam sistem P2P dan konten yang dipetakan sebagai berbagai sumber daya bersama (data, file, aliran media, dll.), Anda akan menemukan bahwa keduanya benar -benar menggambarkan masalah yang sama.
Dalam algoritma Hashing yang konsisten, setiap node (sesuai dengan rekan dalam sistem P2P) memiliki ID yang ditetapkan secara acak. Saat memetakan konten ke sebuah node, operasi hash yang konsisten dilakukan dengan menggunakan kata kunci konten dan ID node dan memperoleh nilai kunci. Hashing yang konsisten mensyaratkan bahwa nilai kunci dan ID simpul berada dalam kisaran nilai yang sama. Nilai kunci dan ID paling sederhana dapat berupa satu dimensi, seperti satu set bilangan bulat dari 0000 hingga 9999.
Saat menyimpan konten berdasarkan nilai kunci, konten disimpan pada node dengan ID paling dekat dengan nilai kuncinya. Misalnya, jika nilai kunci adalah 1001, ada node dengan ID 1000, 1010, 1100 dalam sistem, dan konten akan dipetakan ke 1000 node.
Untuk membangun rute yang diperlukan untuk kueri, hash konsistensi mengharuskan setiap node untuk menyimpan informasi lokasi (alamat IP) dari simpul uplink -nya (nilai ID lebih besar dari yang terkecil di antara node sendiri) dan node downlink (nilai ID kurang dari yang terbesar di antara node sendiri). Ketika sebuah node perlu menemukan konten, ia dapat memutuskan untuk memulai permintaan kueri ke simpul uplink atau downlink berdasarkan nilai kunci konten. Jika sebuah simpul yang menerima permintaan kueri menemukan bahwa ia memiliki target yang diminta, ia dapat secara langsung mengembalikan konfirmasi ke simpul yang memulai permintaan kueri; Jika menemukan bahwa itu bukan milik ruang lingkupnya sendiri, ia dapat meneruskan permintaan ke simpul uplink/downlink.
Untuk mempertahankan informasi perutean yang disebutkan di atas, ketika sebuah node bergabung/keluar dari sistem, node yang berdekatan harus memperbarui informasi perutean secara tepat waktu. Ini mensyaratkan bahwa node tidak hanya menyimpan informasi lokasi simpul downlink yang terhubung langsung, tetapi juga mengetahui informasi simpul downlink tidak langsung pada kedalaman tertentu (N-hop), dan secara dinamis mempertahankan daftar node. Ketika sebuah node keluar dari sistem, simpul uplink -nya akan mencoba untuk terhubung langsung ke simpul downlink terdekat. Setelah koneksi berhasil, ia akan mendapatkan daftar simpul downlink dari simpul downlink baru dan memperbarui daftar simpulnya sendiri. Demikian pula, ketika sebuah simpul baru ditambahkan ke sistem, pertama temukan node downlink sesuai dengan ID sendiri dan dapatkan daftar node downlink, dan kemudian minta simpul uplink untuk memodifikasi daftar simpul downlink -nya, sehingga memulihkan hubungan perutean.
membahas
Hash yang konsisten pada dasarnya memecahkan masalah paling kritis dalam lingkungan P2P - cara mendistribusikan penyimpanan dan perutean dalam topologi jaringan yang dinamis. Setiap node hanya perlu mempertahankan informasi dari sejumlah kecil node tetangga, dan ketika node bergabung/keluar dari sistem, hanya sejumlah kecil node yang relevan yang berpartisipasi dalam pemeliharaan topologi. Semua ini menjadikan hash yang konsisten sebagai algoritma DHT praktis pertama.
Namun, algoritma perutean hashing yang konsisten masih memiliki kekurangan. Selama proses kueri, pesan kueri harus melalui langkah O (n) (O (n) menunjukkan hubungan proporsional dengan n, dan n mewakili jumlah total node dalam sistem) sebelum dapat mencapai node kueri. Tidak sulit untuk membayangkan bahwa ketika sistem ini sangat besar, jumlah node dapat melebihi satu juta, dan efisiensi permintaan semacam itu jelas sulit untuk memenuhi kebutuhan penggunaan. Dari perspektif lain, bahkan jika pengguna dapat mentolerir penundaan yang lama, sejumlah besar pesan yang dihasilkan selama proses kueri akan membawa beban yang tidak perlu ke jaringan.
Paket Herotrix; impor java.util.collection; import java.util.sortedmap; impor java.util.treemap; kelas publik konsistenthash <t> {// hash algoritma private hashfunction hashfunction final;//jumlah node virtual final inter final number darireplicas; private hashfunction; T> (); public consexenthash (hashfunction hashFunction, int numberOfreplicas, collection <t> node) {this.hashfunction = hashFunction; this.numberofreplicas = numberOfreplicas; untuk (t node: node) {add (node);}} public void add (t node) {for (int i = 0; i <numberofreplicas; i ++) {circle.put (hashfunction.hash (node.tostring ()+i), node);}} public void (node.tostring ()+i), node);}} public void (node.tostring ()+i), node);}} public void (node.tostring ()+i, node); i ++) {circle.remove (hashfunction.hash (node.toString ()+i));}} // algoritma kunci t publik t get (kunci objek) {if (circle.isempty ()) {return null;} // Hitung nilai hash ini hash hash = hashfunction.hash (key); if (! Circle.containskey (hash)) {sortedmap <integer, t> tailmap = circle.tailmap (hash); hash = tailmap.isempty ()? circle.firstkey (): tailmap.firstkey ();} return circle.get (hash);}}Di atas adalah seluruh konten artikel ini tentang catatan pembelajaran algoritma hash bahasa Java (contoh kode). Saya harap ini akan membantu semua orang. Teman yang tertarik dapat terus merujuk ke topik terkait lainnya di situs ini. Jika ada kekurangan, silakan tinggalkan pesan untuk menunjukkannya. Terima kasih teman atas dukungan Anda untuk situs ini!