Tabel Hash Terdistribusi: Perbedaan antara revisi

'''Tabel hash terdistribusi''' (Bahasa Inggris ''Distributed Hast Tabel "DHT"'' ) adalah [[Komputasi terdistribusi|sistem terdistribusi]] yang menyediakan layanan pencarian yang mirip dengan tabel hash : pasangan atribut nilai disimpan dalam Tabel Hash Terdistribusi, dan setiap ''node'' yang berpartisipasi dapat secara efisien mengambil nilai yang terkait dengan kunci yang diberikan. Keuntungan utama dari Tabel Hash Terdistribusi adalah bahwa ''node'' dapat ditambahkan atau dihapus dengan pekerjaan minimum di sekitar mendistribusikan ulang kunci. ''Kunci'' adalah pengidentifikasi unik yang memetakan ke ''nilai'' tertentu, yang pada gilirannya dapat berupa apa saja mulai dari alamat, [[dokumen elektronik|dokumen]], hingga [[data]] arbitrer.<ref name="StoicaEtAl2001">{{Cite journal|last=Stoica|first=I.|last2=Morris|first2=R.|last3=Karger|first3=D.|author-link3=David Karger|last4=Kaashoek|first4=M. F.|last5=Balakrishnan|first5=H.|author-link5=Hari Balakrishnan|year=2001|title=Chord: A scalable peer-to-peer lookup service for internet applications|url=http://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf|journal=ACM SIGCOMM Computer Communication Review|volume=31|issue=4|pages=149|doi=10.1145/964723.383071|quote=A value can be an address, a document, or an arbitrary data item.}}</ref> Tanggung jawab untuk memelihara pemetaan dari kunci ke nilai didistribusikan di antara ''node'', sedemikian rupa sehingga perubahan dalam set peserta menyebabkan gangguan minimal. Hal ini memungkinkan Tabel Hash Terdistribusi untuk [[Skalabilitas|menskalakan]] ke jumlah ''node'' yang sangat besar dan untuk menangani kedatangan, keberangkatan, dan kegagalan ''node'' yang berkelanjutan. Tabel Hash Terdistribusi membentuk infrastruktur yang dapat digunakan untuk membangun layanan yang lebih kompleks, seperti [[anycast]], cache web kooperatif, sistem file terdistribusi, [[Sistem Penamaan Domain|sistem penamaan domain]], [[pesan instan]], [[multisiar]], dan juga [[Berbagi file peer-to-peer|berbagi file ''peer-to-peer'']] dan sistem [[Distribusi digital|distribusi konten.]] Jaringan yang didistribusikan dicatat bahwa penggunaan Tabel Hash Terdistribusi termasuk didistribusikan pelacak [[BitTorrent]], [[Jaringan Distribusi Konten Karang|Coral Konten Distribution Network]], [[jaringan kad|jaringan Kad]], [[Badai botnet|Storm botnet]], [[Toks (protokol)|Tox instant messenger]], [[jaringan bebas|Freenet]], mesin pencari YaCy, dan ''InterPlanetary File System.''

Penelitian Tabel Hash Terdistribusi awalnya dimotivasi, sebagian, oleh sistem ''peer-to-peer'' (P2P) seperti [[jaringan bebas|Freenet]], [[Gnutella]], [[BitTorrent (perangkat lunak)|BitTorrent]] dan [[Napster]], yang memanfaatkan sumber daya yang didistribusikan di Internet untuk menyediakan satu aplikasi yang berguna. Secara khusus, mereka memanfaatkan peningkatan [[Bandwidth (komputasi)|bandwidth]] dan [[Cakram keras|kapasitas hard disk]] untuk menyediakan layanan berbagi file.<ref>{{Cite journal|last=Liz, Crowcroft|displayauthors=et al|date=2005|title=A survey and comparison of peer-to-peer overlay network schemes|url=http://www.cl.cam.ac.uk/teaching/2005/AdvSysTop/survey.pdf|journal=IEEE Communications Surveys & Tutorials|volume=7|issue=2|pages=72–93|doi=10.1109/COMST.2005.1610546}}</ref> Sistem ini berbeda dalam cara mereka menemukan data yang ditawarkan oleh P2P yang lain. Napster, sistem pengiriman konten P2P skala besar pertama, memerlukan server indeks pusat: setiap ''node'', setelah bergabung, akan mengirim daftar file yang disimpan secara lokal ke server, yang akan melakukan pencarian dan merujuk kueri ke ''node'' yang menyimpan hasil. Komponen utama ini membuat sistem rentan terhadap serangan dan tuntutan hukum.

Pada tahun 2001, empat sistem &#x2014; [[Jaringan beralamat konten|CAN]], <ref name="Ratnasamy01">{{Cite journal|last=Ratnasamy|displayauthors=etal|year=2001|title=A Scalable Content-Addressable Network|url=http://www.eecs.berkeley.edu/~sylvia/papers/cans.pdf|journal=|publisher=In Proceedings of ACM SIGCOMM 2001|access-date=01-12-2021}}</ref> [[Akor (peer-to-peer)|Chord]], <ref>[[Hari Balakrishnan]], [[M. Frans Kaashoek]], David Karger, [[Robert Tappan Morris|Robert Morris]], and Ion Stoica. [http://www.cs.berkeley.edu/~istoica/papers/2003/cacm03.pdf Looking up data in P2P systems]. In [[Communications of the ACM]], February 2003.</ref> [[Kue Kering (DHT)|Pastry]], dan [[Permadani (DHT)|Tapestry]] &#x2014; memicu Tabel Hash Terdistribusi sebagai topik penelitian yang populer. Sebuah proyek bernama Infrastructure for [[Resilient Internet Systems]] (Iris) didanai oleh hibah $12 juta dari United States [[Yayasan Sains Nasional|National Science Foundation]] pada tahun 2002.<ref>{{Cite news|last=David Cohen|date=October 1, 2002|title=New P2P network funded by US government|url=https://www.newscientist.com/article.ns?id=/dn2861-new-p2p-network-funded-by-us-government/|work=New Scientist|access-date=01-12-2021}}</ref> Peneliti termasuk Sylvia Ratnasamy, Ion Stoica, Hari Balakrishnan dan Scott Shenker.<ref>{{Cite news|date=September 25, 2002|title=MIT, Berkeley, ICSI, NYU, and Rice Launch the IRIS Project|url=https://iris.pdos.csail.mit.edu/MITPressRelease1.doc|work=Press release|publisher=MIT|archive-url=https://web.archive.org/web/20150926070618/https://iris.pdos.csail.mit.edu/MITPressRelease1.doc|archive-date=September 26, 2015|access-date=01-12-2021|url-status=dead}}</ref> Di luar akademisi, teknologi Tabel Hash Terdistribusi telah diadopsi sebagai komponen BitTorrent dan di [[Jaringan Distribusi Konten Karang|Coral Content Distribution Network]].

Tabel Hash Terdistribusi secara khas menekankan sifat-sifat berikut:<ref name=":0" />

* [[Toleransi kesalahan]] : Sistem harus dapat diandalkan (dalam beberapa hal) bahkan dengan ''node'' yang terus-menerus bergabung, keluar, dan gagal. <ref name=":0">R Mokadem, A Hameurlain and AM Tjoa. [https://www.irit.fr/~Riad.Mokadem/wp-content/uploads/sites/67/2020/12/Resource-discovery-service-while-minimizing-maintenance-overhead-in-hierarchical-DHT-systems-iiWas2010.pdf Resource discovery service while minimizing maintenance overhead in hierarchical DHT systems]. Proc. iiWas, 2010</ref>

* [[Skalabilitas]] : Sistem harus berfungsi secara efisien bahkan dengan ribuan atau jutaan ''node''.<ref name=":0" />

Teknik kunci yang digunakan untuk mencapai tujuan bahwa setiap ''node'' perlu berkoordinasi dengan hanya beberapa ''node'' lain dalam sistem – paling umum, [[Notasi O besar|O]] (log ''n'' ) dari ''n'' peserta (lihat di bawah) – sehingga hanya sejumlah terbatas pekerjaan yang harus dilakukan untuk setiap perubahan keanggotaan. Beberapa desain Tabel Hash Terdistribusi berusaha untuk [[Komunikasi yang aman|mengamankan]] dari peserta jahat <ref>Guido Urdaneta, Guillaume Pierre and Maarten van Steen. [http://www.globule.org/publi/SDST_acmcs2009.html A Survey of DHT Security Techniques]. ACM Computing Surveys 43(2), January 2011.</ref> dan untuk memungkinkan peserta untuk tetap [[Anonimitas|anonim]], meskipun ini kurang umum daripada di banyak sistem ''peer-to-peer'' (terutama [[Berbagi berkas|file sharing]] ).

Struktur Tabel Hash Terdistribusi dapat diuraikan menjadi beberapa komponen utama<ref>{{Cite book|last=Manku|first=Gurmeet Singh|date=2004|url=https://ol.media.proquest.com/media/hms/ORIG/1/azLCI?_a=ChgyMDIxMTIwOTE1MDgxNTI3ODo4MDQxMzQSBzEzODMzMjMaCk9ORV9TRUFSQ0giDzE4MC4yNTMuMTY0LjEyMSoFMTg3NTAyCTMwNTEzMjgwMToRT3BlbnZpZXdQYWdlSW1hZ2VCATBSBk9ubGluZVoCRlRiA1BSV2oAcgB6AIIBHVAtMTAwODc1Mi1udWxsLW51bGwtbnVsbC1udWxskgEGT25saW5lygFOTW96aWxsYS81LjAgKFdpbmRvd3MgTlQgMTAuMDsgV2luNjQ7IHg2NDsgcnY6OTQuMCkgR2Vja28vMjAxMDAxMDEgRmlyZWZveC85NC4w0gEWRGlzc2VydGF0aW9ucyAmIFRoZXNlc5oCB1ByZVBhaWSqAiZPUzpFTVMtVW5BdXRoRG9jVmlldy1nZXRQcmV2aWV3UGRmTGlua8ICAlBEygITRGlzc2VydGF0aW9uL1RoZXNpc9ICAVnyAgD6AgFOggMDV2ViigMcQ0lEOjIwMjExMjA5MTUxMTAzNTExOjEyMjQzNQ%3D%3D&_s=i0v1ckm%2FTCOqEZ9hRYzak3dXLIE%3D|title=Dipsea: A Modular Distributed Hash Table|publisher=Stanford University|language=en|url-status=live}}</ref>.<ref>Moni Naor and Udi Wieder. [http://www.wisdom.weizmann.ac.il/~naor/PAPERS/dh.pdf Novel Architectures for P2P Applications: the Continuous-Discrete Approach]. Proc. SPAA, 2003.</ref> <ref>Gurmeet Singh Manku. [http://www-db.stanford.edu/~manku/phd/index.html Dipsea: A Modular Distributed Hash Table] {{Webarchive}}. Ph. D. Thesis (Stanford University), August 2004.</ref> Fondasinya adalah ruang [[Keyspace (penyimpanan data terdistribusi)|kunci]] abstrak, seperti kumpulan [[string]] 160-bit. [[Partisi (basis data)|Skema partisi]] keyspace membagi kepemilikan keyspace ini di antara ''node'' yang berpartisipasi. Jaringan ''overlay'' kemudian menghubungkan ''node'', memungkinkan mereka untuk menemukan pemilik kunci yang diberikan di ''keyspace''. Setelah komponen-komponen ini berada di tempatnya, penggunaan Tabel Hash Terdistribusi yang khas untuk penyimpanan dan pengambilan dapat dilanjutkan sebagai berikut. Misalkan keyspace adalah kumpulan string 160-bit. Untuk mengindeks file dengan yang diberikan {{Var serif|filename}} dan {{Mvar|data}} dalam Tabel Hash Terdistribusi, hash [[SHA-1]] {{Mvar|filename}} dihasilkan, menghasilkan kunci 160-bit {{Mvar|k}}, dan pesan yang {{Math|''put''(''k, data'')}} dikirim ke setiap ''node'' yang berpartisipasi dalam Tabel Hash Terdistribusi. Pesan diteruskan dari ''node'' ke ''node'' melalui jaringan overlay hingga mencapai ''node'' tunggal yang bertanggung jawab untuk kunci {{Mvar|k}} seperti yang ditentukan oleh partisi keyspace. ''Node'' itu kemudian menyimpan kunci dan datanya. Klien lain kemudian dapat mengambil isi file dengan hashing lagi {{Mvar|filename}} untuk menghasilkan {{Mvar|k}} dan meminta ''node'' Tabel Hash Terdistribusi untuk menemukan data yang terkait dengan {{Mvar|k}} dengan pesan {{Math|''get''(''k'')}} . Pesan akan dirutekan lagi melalui overlay ke ''node'' yang bertanggung jawab untuk {{Mvar|k}}, yang akan membalas dengan {{Mvar|data}} disimpan. Partisi keyspace dan komponen jaringan overlay dijelaskan di bawah ini dengan tujuan menangkap ide-ide utama yang umum untuk sebagian besar Tabel Hash Terdistribusi; banyak desain berbeda dalam detailnya.