نمایش مبدأ برای جدول درهم‌سازی توزیع‌شده

[[پرونده:DHT en.svg|500px|بندانگشتی|جدول درهم‌سازی توزیع‌شده]]

'''جدول درهم‌سازی توزیع‌شده''' {{انگلیسی|Distributed hash table}} به صورت کوتاه شده '''DHT''' یک [[رایانش توزیع‌شده|سیستم توزیع شده‌است]] که خدمات جستجویی مشابه [[جدول درهمک‌سازی|جدول هش]] ارائه می‌دهد: [[جفت ارزش کلیدی|جفت‌های کلید-مقدار]] در یک DHT ذخیره می‌شوند و هر [[گره (شبکه)|گره]] شرکت کننده می‌تواند به‌طور مؤثر مقدار مربوط به یک [[کلید (محاسبات)|کلید]] داده شده را بازیابی کند. مزیت اصلی DHT این است که گره‌ها را می‌توان با حداقل کار در مورد توزیع مجدد کلیدها اضافه یا حذف کرد. ''کلیدها'' شناسه‌های منحصربه‌فردی هستند که به ''مقادیر'' خاصی نگاشت می‌شوند، که به نوبه خود می‌توانند هر چیزی از آدرس‌ها، [[سند الکترونیکی|اسناد]] و [[داده (رایانش)|داده‌های]] دلخواه باشند.<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> مسئولیت حفظ نقشه‌برداری از کلیدها به مقادیر بین گره‌ها توزیع می‌شود، به گونه ای که تغییر در مجموعه شرکت کنندگان باعث ایجاد حداقل اختلال می‌شود. این به یک DHT اجازه می‌دهد تا به تعداد بسیار زیادی از گره‌ها [[مقیاس‌پذیری|گسترده]] شود و ورود، خروج و خرابی مداوم گره‌ها را مدیریت کند.

DHTها زیرساختی را تشکیل می‌دهند که می‌تواند برای ساخت سرویس‌های پیچیده‌تر، مانند [[انیکست|anycast]]، [[حافظه نهان وب|ذخیره‌سازی وب]] مشارکتی، [[سیستم فایل توزیع شده|سیستم‌های فایل توزیع شده]]، [[سامانه نام دامنه|خدمات نام دامنه]]، [[پیام‌رسانی فوری|پیام‌های فوری]]، [[چندپخشی]] و همچنین اشتراک گذاری فایل و سیستم‌های [[توزیع دیجیتال|توزیع محتوا]] [[اشتراک فایل همتا به همتا|به صورت همتا استفاده]] شود. شبکه‌های توزیع شده قابل توجهی که از DHT استفاده می‌کنند عبارت هستند از: ردیاب توزیع شده [[بیت‌تورنت|BitTorrent]]، [[شبکه کاد|شبکه Kad]]، [[بات نت طوفان|بات نت Storm]]، [[تاکس (پروتکل)|پیام رسان فوری Tox]]، [[فری نت|Freenet]]، موتور جستجوی [[YaCy]]، و [[سیستم پرونده بین سیاره ای|سیستم فایل]] بین سیاره ای است.{{-}}

== تاریخچه ==
تحقیقات DHT در اصل، تا حدی توسط سیستم‌های [[همتابه‌همتا (رایانه)|همتا به همتا]] (P2P) مانند [[فری نت|Freenet]]، [[ناتلا|Gnutella]]، [[بیت‌تورنت (نرم‌افزار)|BitTorrent]] و [[نپستر|Napster]] انجام شد که از منابع توزیع شده در سراسر اینترنت برای ارائه یک [[نرم‌افزار کاربردی|برنامه کاربردی]] مفید استفاده کردند. به ویژه، آنها از افزایش [[پهنای باند (پردازش)|پهنای باند]] و ظرفیت [[درایو دیسک سخت|هارد دیسک]] برای ارائه خدمات اشتراک فایل استفاده کردند.<ref>{{Cite journal|last=Liz, Crowcroft|display-authors=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|citeseerx=10.1.1.109.6124|doi=10.1109/COMST.2005.1610546}}</ref>

این سیستم‌ها در نحوه مکان‌یابی داده‌های ارائه شده توسط همتایان خود متفاوت بودند. Napster، که اولین سیستم تحویل محتوای P2P در مقیاس بزرگ بود، به یک سرور شاخص مرکزی نیاز داشت: هر گره، پس از پیوستن، فهرستی از فایل‌های محلی را به سرور ارسال می‌کرد که جستجوها را انجام می‌داد و درخواست‌ها را به گره‌هایی ارجاع می‌داد. نتایج. این سیستم را در برابر حملات آسیب‌پذیر می‌کرد.

Gnutella و شبکه‌های مشابه به یک مدل [[پرس و جو سیل|سیل پرس و جو]] منتقل شدند{{Spaced ndash}}در اصل، هر جستجو منجر به پخش پیامی برای هر ماشین دیگر در شبکه می‌شود. در حالی که اجتناب از یک [[نقطه تکی شکست|نقطه شکست]]، این روش به‌طور قابل توجهی کمتر از Napster کارآمد بود. نسخه‌های بعدی مشتریان Gnutella به یک مدل [[پرس و جو پویا]] منتقل شدند که کارایی را بسیار بهبود بخشید.<ref>{{Cite journal|last=Richter, Stevenson|display-authors=et al|date=2009|title=Analysis of the impact of dynamic querying models on client-server relationships|journal=Trends in Modern Computing|pages=682–701}}</ref>

Freenet به‌طور کامل توزیع شده‌است، اما از یک [[مسیریابی مبتنی بر کلید]] [[الگوریتم جستجوی کاشف|اکتشافی]] استفاده می‌کند که در آن هر فایل با یک کلید مرتبط است، و فایل‌هایی با کلیدهای مشابه تمایل دارند در مجموعه‌ای از گره‌های مشابه خوشه شوند. پرس و جوها احتمالاً از طریق شبکه به چنین خوشه ای بدون نیاز به بازدید از همتایان زیادی هدایت می‌شوند.<ref>{{Citation|url=https://freenetproject.org/papers/lic.pdf|title=Searching in a Small World Chapters 1 & 2|access-date=2012-01-10|archive-date=۱۶ مارس ۲۰۱۲|archive-url=https://web.archive.org/web/20120316102141/https://freenetproject.org/papers/lic.pdf|url-status=dead}}</ref> با این حال، Freenet تضمین نمی‌کند که داده‌ها پیدا شوند.

جداول هش توزیع‌شده از مسیریابی مبتنی بر کلید ساختاریافته‌تر برای دستیابی به تمرکززدایی Freenet و Gnutella و کارایی و نتایج تضمین‌شده Napster استفاده می‌کنند. یک اشکال این است که، مانند Freenet, DHTها به جای جستجوی کلمه کلیدی، فقط مستقیماً از جستجوی تطابق دقیق پشتیبانی می‌کنند، اگرچه [[مسیریابی (شبکه)|الگوریتم مسیریابی]] فری نت را می‌توان به هر نوع کلیدی تعمیم داد که در آن عملیات نزدیکی تعریف شود.<ref>{{Citation|chapter-url=https://freenetproject.org/papers/ddisrs.pdf|title=A Distributed Decentralized Information Storage and Retrieval System|chapter=Section 5.2.2|access-date=2012-01-10|archive-date=۱۶ مارس ۲۰۱۲|archive-url=https://web.archive.org/web/20120316102156/https://freenetproject.org/papers/ddisrs.pdf|url-status=dead}}</ref>

در سال ۲۰۰۱، چهار سیستم &#x2014; [[شبکه آدرس‌دهی محتوا|CAN]] ,<ref name="Ratnasamy01">{{Cite journal|last=Ratnasamy|display-authors=etal|year=2001|title=A Scalable Content-Addressable Network|url=http://www.eecs.berkeley.edu/~sylvia/papers/cans.pdf|publisher=In Proceedings of ACM SIGCOMM 2001|access-date=2013-05-20}}</ref> [[کورد (نظیر به نظیر)|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> [[شیرینی (DHT)|Pastry]]، و [[ملیله (DHT)|Tapestry]] &#x2014; DHTها را به عنوان یک موضوع تحقیقاتی محبوب روشن کردند. پروژه ای به نام زیرساخت برای سیستم‌های اینترنتی مقاوم (Iris) با کمک مالی ۱۲ میلیون دلاری از [[بنیاد ملی علوم]] ایالات متحده در سال ۲۰۰۲ تأمین.<ref>{{Cite news|title=New P2P network funded by US government|last=David Cohen|work=New Scientist|date=October 1, 2002|url=https://www.newscientist.com/article.ns?id=dn2861|accessdate=November 10, 2013}}</ref> محققان شامل [[سیلویا راتناسامی]]، [[یون استویکا]]، [[هاری بالاکریشنان]] و [[اسکات شنکر]] بودند.<ref>{{Cite news|title=MIT, Berkeley, ICSI, NYU, and Rice Launch the IRIS Project|work=Press release|publisher=MIT|date=September 25, 2002|url=https://iris.pdos.csail.mit.edu/MITPressRelease1.doc|accessdate=November 10, 2013|archiveurl=https://web.archive.org/web/20150926070618/https://iris.pdos.csail.mit.edu/MITPressRelease1.doc|archivedate=September 26, 2015}}</ref> در خارج از دانشگاه، فناوری DHT به عنوان جزئی از BitTorrent و در شبکه توزیع محتوای Coral پذیرفته شده‌است.

== ویژگی‌ها ==
DHTها به‌طور مشخص بر ویژگی‌های زیر تأکید دارند:
* [[محاسبات غیرمتمرکز|خودمختاری و عدم تمرکز]]: گره‌ها به‌طور جمعی سیستم را بدون هیچ هماهنگی مرکزی تشکیل می‌دهند.
* [[تاب‌آوری خطا|تحمل خطا]]: سیستم باید قابل اعتماد (به نوعی) حتی با پیوستن، خروج و خرابی پیوسته گره‌ها باشد.<ref>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>
* [[مقیاس‌پذیری|مقیاس پذیری]]: سیستم باید حتی با هزاران یا میلیون‌ها گره به‌طور مؤثر عمل کند.

یک تکنیک کلیدی که برای دستیابی به این اهداف مورد استفاده قرار می‌گیرد این است که هر گره نیاز به هماهنگی تنها با چند گره دیگر در سیستم دارد - معمولاً [[نماد O بزرگ|O]] (log ''n'') از ''n'' شرکت کننده (به زیر مراجعه کنید) - به‌طوری که فقط مقدار محدودی از برای هر تغییر در عضویت باید کار انجام شود.

برخی از طرح‌های DHT به دنبال [[ارتباط امن|ایمن بودن]] در برابر شرکت‌کنندگان مخرب<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> هستند و به شرکت‌کنندگان اجازه می‌دهند [[ناشناسی|ناشناس]] باقی بمانند، اگرچه این نسبت در بسیاری از سیستم‌های همتا به همتا (به ویژه [[اشتراک پرونده|اشتراک‌گذاری فایل]]) کمتر رایج است. [[پیش‌نویس:Anonymous P2P|P2P ناشناس]] را ببینید.

== ساختار ==
ساختار یک DHT را می‌توان به چندین جزء اصلی تجزیه کرد.<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|url=https://web.archive.org/web/20040910154927/http://www-db.stanford.edu/~manku/phd/index.html|date=2004-09-10}}. Ph. D. Thesis (Stanford University), August 2004.</ref> پایه یک [[Keyspace (ذخیره داده‌های توزیع شده)|فضای کلید]] انتزاعی است، مانند مجموعه [[رشته (علوم رایانه)|رشته]]‌های ۱۶۰ بیتی. یک طرح [[پارتیشن (پایگاه داده)|پارتیشن‌بندی]] فضای کلید، مالکیت این فضای کلیدی را بین گره‌های شرکت کننده تقسیم می‌کند. سپس یک [[شبکه‌های همپوشان|شبکه همپوشانی]] گره‌ها را به هم متصل می‌کند و به آن‌ها اجازه می‌دهد تا صاحب هر کلیدی را در فضای کلید پیدا کنند.

هنگامی که این اجزا در جای خود قرار گرفتند، استفاده معمولی از DHT برای ذخیره‌سازی و بازیابی ممکن است به شرح زیر انجام شود. فرض کنید فضای کلید مجموعه ای از رشته‌های ۱۶۰ بیتی است. برای نمایه سازی فایل با داده شده{{Varserif|filename}} و {{Mvar|data}} در DHT، هش [[اس‌اچ‌ای-۱|SHA-1]] {{Mvar|filename}} تولید می‌شود و یک کلید ۱۶۰ بیتی {{Mvar|k}} تولید می‌شود و یک پیام {{ریاضی|''put''(''k, data'')}} به هر گره ای که در DHT شرکت می‌کند ارسال می‌شود. پیام از طریق شبکه همپوشانی از گره ای به گره دیگر ارسال می‌شود تا زمانی که به گره تکی مسئول کلید {{Mvar|k}} که توسط [[پارتیشن‌بندی]] فضای کلید مشخص شده‌است برسد. سپس آن گره کلید و داده‌ها را ذخیره می‌کند. سپس هر کلاینت دیگری می‌تواند محتویات فایل را با هش کردن مجدد {{Mvar|filename}} برای تولید {{Mvar|k}} و درخواست از هر گره DHT برای یافتن داده‌های مرتبط با {{Mvar|k}} با پیام {{ریاضی|''get''(''k'')}} بازیابی کند. پیام دوباره از طریق پوشش به گره مسئول {{Mvar|k}} هدایت می‌شود که با {{Mvar|data}} ذخیره شده پاسخ می‌دهد.

پارتیشن‌بندی فضای کلید و اجزای شبکه همپوشانی در زیر با هدف گرفتن ایده‌های اصلی مشترک در اکثر DHTها توضیح داده شده‌است. بسیاری از طرح‌ها در جزئیات متفاوت هستند.

== پارتیشن بندی فضای کلیدی ==
اکثر DHT ها از نوعی [[کش سازگار|هش ثابت یا هش]] [[هش قرار ملاقات|قرار ملاقات]] برای نگاشت کلیدها به گره ها استفاده می کنند. به نظر می رسد که این دو الگوریتم به‌طور مستقل و به‌طور همزمان برای حل مشکل جدول هش توزیع شده ابداع شده اند.

هر دو هش ثابت و هش جابجاشونده این ویژگی اساسی را دارند که حذف یا افزودن یک گره تنها مجموعه کلیدهای متعلق به گره‌ها با شناسه‌های مجاور را تغییر می‌دهد و همه گره‌های دیگر را بی‌تأثیر می‌گذارد. این را با [[جدول درهمک‌سازی|جدول هش]] سنتی مقایسه کنید که در آن اضافه یا حذف یک سطل باعث می‌شود تقریباً کل فضای کلید دوباره نقشه‌برداری شود. از آنجایی که هر تغییری در مالکیت معمولاً مربوط به حرکت پهنای باند فشرده اشیاء ذخیره شده در DHT از یک گره به گره دیگر است، به حداقل رساندن چنین سازماندهی مجدد برای پشتیبانی کارآمد از نرخ های بالای [[نرخ ریزش|ریزش]] (ورود و شکست گره) مورد نیاز است.

== هش کردن مداوم ==
هش ثابت یک تابع را به کار می گیرد <math>\delta(k_1, k_2)</math> که یک مفهوم انتزاعی از فاصله بین کلیدها را تعریف می کند <math>k_1</math> و <math>k_2</math> ، که با فاصله جغرافیایی یا [[تأخیر (مهندسی)|تاخیر]] شبکه ارتباطی ندارد. به هر گره یک کلید به نام ''شناسه'' آن (ID) اختصاص داده می شود. یک گره با شناسه <math>i_x</math> همه کلیدها را در اختیار دارد <math>k_m</math> برای کدام <math>i_x</math> نزدیکترین شناسه است که بر اساس اندازه گیری می شود <math>\delta(k_m, i_x)</math> .

به عنوان مثال، [[کورد (نظیر به نظیر)|Chord DHT]] از هش ثابت استفاده می کند، که گره ها را به عنوان نقاط روی یک دایره در نظر می گیرد، و <math>\delta(k_1, k_2)</math> مسافتی است که در جهت عقربه های ساعت به دور دایره از آن طی می شود <math>k_1</math> به <math>k_2</math> . بنابراین، فضای کلید دایره‌ای به بخش‌های پیوسته تقسیم می‌شود که نقاط پایانی آن‌ها شناسه گره هستند. اگر <math>i_1</math> و <math>i_2</math> دو شناسه مجاور، با فاصله کمتر در جهت عقربه های ساعت از <math>i_1</math> به <math>i_2</math> ، سپس گره با شناسه <math>i_2</math> مالک تمام کلیدهایی است که بین آنها قرار می گیرند <math>i_1</math> و <math>i_2</math> .

== هش قرار ملاقات(Rendezvous) ==
در هش قرار ملاقات که هش با بالاترین وزن تصادفی (HRW) نیز نامیده می شود، همه مشتریان از یک تابع هش استفاده می کنند. <math>h()</math> (انتخاب زودتر از زمان) برای مرتبط کردن یک کلید به یکی از ''n'' سرور موجود. هر مشتری فهرست یکسانی از شناسه‌های {{ریاضی|{{mset|''S''<sub>1</sub>, ''S''<sub>2</sub>, ..., ''S''<sub>''n''</sub> }}}} {{ریاضی|{{mset|''S''<sub>1</sub>, ''S''<sub>2</sub>, ..., ''S''<sub>''n''</sub> }}}} {{ریاضی|{{mset|''S''<sub>1</sub>, ''S''<sub>2</sub>, ..., ''S''<sub>''n''</sub> }}}}, یکی برای هر سرور. با توجه به کلید ''k'' ، یک کلاینت ''n'' وزن هش {{ریاضی|1=''w''<sub>1</sub> = ''h''(''S''<sub>1</sub>, ''k''), ''w''<sub>2</sub> = ''h''(''S''<sub>2</sub>, ''k''), ..., ''w''<sub>''n''</sub> = ''h''(''S''<sub>''n''</sub>, ''k'')}} را محاسبه می کند. مشتری آن کلید را با سرور مربوط به بالاترین وزن هش برای آن کلید مرتبط می کند. سرور با شناسه <math>S_x</math> همه کلیدها را در اختیار دارد <math>k_m</math> که برای آن وزن هش <math>h(S_x, k_m)</math> از وزن هش هر گره دیگری برای آن کلید بیشتر است.

== هش با حفظ محلیت ==
هش با حفظ محلیت تضمین می کند که کلیدهای مشابه به اشیاء مشابه اختصاص داده می شوند. این می تواند اجرای کارآمدتر پرس و جوهای محدوده را امکان پذیر کند، با این حال، برخلاف استفاده از هش ثابت، اطمینان بیشتری وجود ندارد که کلیدها (و بنابراین بار) به‌طور تصادفی یکنواخت در فضای کلید و همتاهای شرکت کننده توزیع شده اند. پروتکل های DHT مانند Self-Cord و Oscar <ref>{{Cite journal|last=Girdzijauskas|first=Šarūnas|last2=Datta|first2=Anwitaman|last3=Aberer|first3=Karl|date=2010-02-01|title=Structured overlay for heterogeneous environments|url=http://infoscience.epfl.ch/record/134972|journal=ACM Transactions on Autonomous and Adaptive Systems|volume=5|issue=1|pages=1–25|doi=10.1145/1671948.1671950|issn=1556-4665}}</ref> به چنین مسائلی می پردازند. Self-Cord کلیدهای شی را از شناسه‌های همتا جدا می‌کند و کلیدها را در امتداد حلقه با رویکردی آماری بر اساس الگوی [[هوش ازدحامی|هوش ازدحام]] دسته‌بندی می‌کند.<ref>{{Cite journal|last=Forestiero|first=Agostino|last2=Leonardi|first2=Emilio|last3=Mastroianni|first3=Carlo|last4=Meo|first4=Michela|date=October 2010|title=Self-Chord: A Bio-Inspired P2P Framework for Self-Organizing Distributed Systems|url=http://porto.polito.it/2370172/|journal=IEEE/ACM Transactions on Networking|volume=18|issue=5|pages=1651–1664|doi=10.1109/TNET.2010.2046745}}</ref> مرتب‌سازی تضمین می‌کند که کلیدهای مشابه توسط گره‌های همسایه ذخیره می‌شوند و روش‌های کشف، از جمله [[جستجوی محدوده (ساختارهای داده)|پرس‌وجوهای محدوده]] ، می‌توانند در زمان لگاریتمی انجام شوند. اسکار یک [[شبکه جهان‌کوچک|شبکه جهان کوچک]] قابل کشتیرانی را بر اساس نمونه‌برداری [[ولگشت|تصادفی پیاده‌روی]] ایجاد می‌کند و همچنین زمان جستجوی لگاریتمی را تضمین می‌کند.

== شبکه همپوشانی ==
هر گره مجموعه ای از [[لینک اطلاعات|پیوندها]] را به گره های دیگر ( ''همسایگان'' یا [[جدول مسیریابی]] خود) حفظ می کند. این پیوندها با هم شبکه همپوشانی را تشکیل می دهند.<ref>{{Citation|last=Galuba|first=Wojciech|title=Peer to Peer Overlay Networks: Structure, Routing and Maintenance|date=2009|journal=Encyclopedia of Database Systems|pages=2056–2061|editor-last=LIU|editor-first=LING|publisher=Springer US|language=en|doi=10.1007/978-0-387-39940-9_1215|isbn=9780387399409|last2=Girdzijauskas|first2=Sarunas|editor2-last=ÖZSU|editor2-first=M. TAMER}}</ref> یک گره همسایگان خود را بر اساس ساختار خاصی انتخاب می [[هم‌بندی شبکه|کند که توپولوژی شبکه]] نامیده می شود.

همه توپولوژی‌های DHT نوعی از اساسی‌ترین ویژگی را به اشتراک می‌گذارند: برای هر کلید {{Mvar|k}} ، هر گره یا شناسه گره‌ای دارد که دارای {{Mvar|k}} است یا پیوندی به گره‌ای دارد که شناسه گره آن به {{Mvar|k}} ''نزدیک‌تر'' است، از نظر فاصله فضای کلید تعریف‌شده در بالا. . سپس با استفاده از [[الگوریتم حریصانه]] زیر (که لزوماً بهینه جهانی نیست) یک پیام را به صاحب هر کلید {{Mvar|k}} هدایت کنید: در هر مرحله، پیام را به همسایه ای که شناسه آن به {{Mvar|k}} نزدیکتر است، ارسال کنید. وقتی چنین همسایه ای وجود ندارد، پس باید به نزدیکترین گره رسیده باشیم، که همان‌طور که در بالا تعریف شد، صاحب {{Mvar|k}} است. این سبک از مسیریابی گاهی [[مسیریابی مبتنی بر کلید]] نامیده می شود.

فراتر از صحت مسیریابی اولیه، دو محدودیت مهم در توپولوژی تضمین این است که حداکثر تعداد [[هاپ (شبکه)|پرش]] ها در هر مسیر (طول مسیر) کم است، به‌طوری که درخواست ها به سرعت تکمیل می شوند. و اینکه حداکثر تعداد همسایگان هر گره (حداکثر [[مدرک (نظریه گراف)|درجه]] گره) کم است، به‌طوری که سربار تعمیر و نگهداری بیش از حد نباشد. البته داشتن مسیرهای کوتاهتر مستلزم [[حداکثر مدرک تحصیلی|درجه حداکثری]] بالاتر است. برخی از انتخاب های رایج برای حداکثر درجه و طول مسیر به شرح زیر است، که در آن {{Mvar|n}} تعداد گره ها در DHT با استفاده از [[نماد O بزرگ|نماد Big O است]] :

{| class="wikitable"
!حداکثر درجه
!حداکثر طول مسیر
!استفاده شده در
!توجه داشته باشید
|-
|<math>O(1)</math>
|<math>O(n)</math>
|
|بدترین طول جستجو، با زمان جستجوی احتمالی بسیار کندتر
|-
|<math>O(1)</math>
|<math>O(\log n)</math>
|[[کورده]] (با درجه ثابت)
|پیاده سازی پیچیده تر، اما زمان جستجوی قابل قبولی را می توان با تعداد ثابتی از اتصالات یافت
|-
|<math>O(\log n)</math>
|<math>O(\log n)</math>
|[[کورد (نظیر به نظیر)|آکورد]][[کادملیا]][[شیرینی (DHT)|شیرینی]][[ملیله (DHT)|ملیله کاری]]
|رایج ترین، اما نه بهینه (درجه/طول مسیر). آکورد ابتدایی ترین نسخه است، به نظر می رسد Kademlia محبوب ترین نسخه بهینه شده است (باید جستجوی متوسط بهبود یافته باشد)
|-
|<math>O(\log n)</math>
|<math>O(\log n/\log (\log n))</math>
|[[کورده|Koorde]] (با جستجوی بهینه)
|پیاده‌سازی پیچیده‌تر است، اما جستجوها ممکن است سریع‌تر باشند (بدترین حالت کمتری دارند)
|-
|<math>O(\sqrt{n})</math>
|<math>O(1)</math>
|
|بدترین نیازهای ذخیره سازی محلی، با ارتباطات زیاد پس از اتصال یا قطع شدن هر گره
|}

رایج ترین انتخاب، <math>O(\log n)</math> طول درجه/مسیر، از نظر مبادله طول درجه/مسیر بهینه نیست، اما چنین توپولوژی‌هایی معمولاً انعطاف‌پذیری بیشتری را در انتخاب همسایگان فراهم می‌کنند. بسیاری از DHT ها از این انعطاف پذیری برای انتخاب همسایه هایی استفاده می کنند که از نظر تأخیر در شبکه فیزیکی زیربنایی نزدیک هستند. به‌طور کلی، همه DHT ها توپولوژی های شبکه جهان کوچک قابل کشتیرانی را ایجاد می کنند که طول مسیر را با درجه شبکه مقایسه می کند.<ref name="Cite book">{{Cite book}}</ref>

حداکثر طول مسیر ارتباط نزدیکی با [[فاصله در گراف|قطر دارد]] : حداکثر تعداد پرش ها در هر کوتاه ترین مسیر بین گره ها. واضح است که طول مسیر شبکه در بدترین حالت حداقل به اندازه قطر آن است، بنابراین DHT ها توسط مبادله درجه/قطر <ref>{{Citation|url=http://maite71.upc.es/grup_de_grafs/table_g.html|title=The (Degree,Diameter) Problem for Graphs|publisher=Maite71.upc.es|access-date=2012-01-10|archiveurl=https://web.archive.org/web/20120217054532/http://maite71.upc.es/grup_de_grafs/table_g.html/|archivedate=2012-02-17}}</ref> که در [[نظریه گراف]] اساسی است، محدود می شوند. طول مسیر می تواند بیشتر از قطر باشد، زیرا الگوریتم مسیریابی حریصانه ممکن است کوتاه ترین مسیرها را پیدا نکند.<ref>Gurmeet Singh Manku, Moni Naor, and Udi Wieder. [http://citeseer.ist.psu.edu/naor04know.html "Know thy Neighbor's Neighbor: the Power of Lookahead in Randomized P2P Networks"]. Proc. STOC, 2004.</ref>

== الگوریتم های شبکه های همپوشانی ==
جدای از مسیریابی، الگوریتم‌های زیادی وجود دارد که از ساختار شبکه همپوشانی برای ارسال پیام به تمام گره‌ها یا زیر مجموعه‌ای از گره‌ها در یک DHT استفاده می‌کنند.<ref>{{Cite web|last=[[Ali Ghodsi]]|url=http://www.sics.se/~ali/thesis/|title=Distributed k-ary System: Algorithms for Distributed Hash Tables|archiveurl=https://web.archive.org/web/20070522060750/http://www.sics.se/~ali/thesis/|archivedate=4 January 2007|date=22 May 2007}}. KTH-Royal Institute of Technology, 2006.</ref> این الگوریتم ها توسط برنامه های کاربردی برای انجام [[شبکه‌های همپوشان|چندپخشی همپوشانی]] ، پرس و جوهای محدوده یا جمع آوری آمار استفاده می شود. دو سیستمی که مبتنی بر این رویکرد هستند، Structella، <ref>{{Cite journal|last=Castro|first=Miguel|last2=Costa|first2=Manuel|last3=Rowstron|first3=Antony|date=1 January 2004|title=Should we build Gnutella on a structured overlay?|url=http://nms.lcs.mit.edu/HotNets-II/papers/structella.pdf|journal=ACM SIGCOMM Computer Communication Review|volume=34|issue=1|pages=131|citeseerx=10.1.1.221.7892|doi=10.1145/972374.972397}}</ref> که flooding و پیمایش های تصادفی را بر روی یک پوشش Pastry پیاده‌سازی می‌کند، و DQ-DHT، که یک الگوریتم جستجوی پویا را بر روی یک شبکه آکورد پیاده‌سازی می‌کند.<ref>{{Cite journal|last=Talia|first=Domenico|last2=Trunfio|first2=Paolo|date=December 2010|title=Enabling Dynamic Querying over Distributed Hash Tables|journal=Journal of Parallel and Distributed Computing|volume=70|issue=12|pages=1254–1265|doi=10.1016/j.jpdc.2010.08.012}}</ref>

== امنیت ==
به دلیل عدم تمرکز، تحمل خطا و مقیاس پذیری DHT ها، ذاتاً در برابر یک مهاجم متخاصم انعطاف پذیرتر از یک سیستم متمرکز هستند.

سیستم‌های باز برای [[ذخیره سازی داده های توزیع شده|ذخیره‌سازی داده‌های توزیع‌شده]] که در برابر مهاجمان خصمانه عظیم قوی هستند، امکان‌پذیر هستند.<ref>Baruch Awerbuch, Christian Scheideler. "Towards a scalable and robust DHT". 2006. {{DOI|10.1145/1148109.1148163}}</ref>

یک سیستم DHT که به دقت طراحی شده است تا دارای [[تحمل خطای بیزانس|تحمل خطای بیزانسی باشد،]] می‌تواند در برابر ضعف امنیتی، معروف به [[حمله سیبیل|حمله Sybil]] ، که بیشتر طرح‌های DHT فعلی را تحت تأثیر قرار می‌دهد، دفاع کند.<ref>Maxwell Young; Aniket Kate; Ian Goldberg; Martin Karsten. [http://www.cypherpunks.ca/~iang/pubs/robustMessagePassing.pdf "Practical Robust Communication in DHTs Tolerating a Byzantine Adversary"].</ref><ref>Natalya Fedotova; Giordano Orzetti; Luca Veltri; Alessandro Zaccagnini. "Byzantine agreement for reputation management in DHT-based peer-to-peer networks". {{DOI|10.1109/ICTEL.2008.4652638}}</ref> Whanau یک DHT است که برای مقاومت در برابر حملات Sybil طراحی شده است.<ref>Whanau: A Sybil-proof Distributed Hash Table https://pdos.csail.mit.edu/papers/whanau-nsdi10.pdf</ref>

پتار میمونکوف، یکی از نویسندگان اصلی [[کادملیا|Kademlia]] ، راهی را برای دور زدن ضعف حمله Sybil با گنجاندن روابط اعتماد اجتماعی در طراحی سیستم پیشنهاد کرده است.<ref>{{Cite journal|last=Chris Lesniewski-Laas|title=A Sybil-proof one-hop DHT|url=http://pdos.csail.mit.edu/papers/sybil-dht-socialnets08.pdf|pages=20}}</ref> سیستم جدید که با [[اسم رمز|نام رمز]] Tonika یا با نام دامنه آن به عنوان 5ttt شناخته می شود، بر اساس طراحی [[الگوریتم|الگوریتمی]] به نام "مسیریابی الکتریکی" و با همکاری ریاضیدان جاناتان کلنر ساخته شده است.<ref>{{Cite journal|last=Jonathan Kelner, Petar Maymounkov|year=2009|title=Electric routing and concurrent flow cutting|url=https://archive.org/details/arxiv-0909.2859|arxiv=0909.2859|bibcode=2009arXiv0909.2859K}}</ref> مایمونکوف اکنون یک تلاش جامع برای اجرای این سیستم جدید را انجام داده است. با این حال، تحقیق در مورد دفاع مؤثر در برابر حملات Sybil به‌طور کلی یک سؤال باز در نظر گرفته می شود، و انواع گسترده ای از دفاع های بالقوه هر ساله در کنفرانس های تحقیقاتی امنیتی برتر پیشنهاد می شود.{{مدرک|date=May 2020}}

== پیاده سازی ها ==
مهم‌ترین تفاوت‌هایی که در نمونه‌های عملی پیاده‌سازی DHT مشاهده می‌شود، حداقل شامل موارد زیر است:

* فضای آدرس، پارامتری از DHT است. چندین DHT از فضای کلید 128 بیتی یا 160 بیتی استفاده می کنند.
* برخی از DHT های دنیای واقعی از [[تابع هش|توابع هش]] غیر از [[اس‌اچ‌ای-۱|SHA-1]] استفاده می کنند.
* در دنیای واقعی کلید{{Varserif|k}} می‌تواند هش ''محتوای'' یک فایل باشد تا هش ''نام'' فایل برای ارائه [[ذخیره سازی آدرس پذیر محتوا|فضای ذخیره‌سازی آدرس‌پذیر محتوا]] ، به‌طوری که تغییر [[نام پرونده (رایانه)|نام فایل]] مانع از یافتن آن توسط کاربران نشود.
* برخی از DHT ها نیز ممکن است اشیاء انواع مختلف را منتشر کنند. مثلا کلید{{Varserif|k}} می تواند گره باشد{{Varserif|ID}} و داده‌های مرتبط می‌توانند نحوه تماس با این گره را توضیح دهند. این امکان انتشار اطلاعات حضوری را فراهم می کند و اغلب در برنامه های IM و غیره استفاده می شود. در ساده ترین حالت،{{Varserif|ID}} فقط یک عدد تصادفی است که مستقیماً به عنوان کلید استفاده می شود{{Varserif|k}} (بنابراین در DHT 160 بیتی{{Varserif|ID}} یک عدد 160 بیتی خواهد بود که معمولاً به صورت تصادفی انتخاب می شود. در برخی از DHT ها، انتشار شناسه گره ها نیز برای بهینه سازی عملیات DHT استفاده می شود.
* افزونگی را می توان برای بهبود قابلیت اطمینان اضافه کرد. در{{Varserif|(k, data)}}جفت کلید  را می توان در بیش از یک گره مربوط به کلید ذخیره کرد. معمولاً به جای انتخاب فقط یک گره، الگوریتم‌های DHT دنیای واقعی انتخاب می‌کنند{{Varserif|i}} گره های مناسب، با{{Varserif|i}} یک پارامتر خاص اجرای DHT هستم. در برخی از طرح‌های DHT، گره‌ها موافقت می‌کنند که محدوده خاصی از فضای کلید را مدیریت کنند، که اندازه آن ممکن است به‌جای کدگذاری سخت، به صورت پویا انتخاب شود.
* برخی از DHT های پیشرفته مانند [[کادملیا|Kademlia]] ابتدا جستجوهای تکراری را از طریق DHT انجام می دهند تا مجموعه ای از گره های مناسب را انتخاب کرده و ارسال کنند.{{Varserif|put(k, data)}}پیام‌ها  فقط به آن گره‌ها ارسال کنید، بنابراین ترافیک بی‌فایده را به شدت کاهش می‌دهد، زیرا پیام‌های منتشر شده فقط به گره‌هایی ارسال می‌شوند که برای ذخیره‌سازی کلید مناسب به نظر می‌رسند.{{Varserif|k}} ; و جستجوهای مکرر فقط مجموعه کوچکی از گره ها را به جای کل DHT پوشش می دهند و ارسال بی فایده را کاهش می دهند. در چنین DHT ها، ارسال از{{Varserif|put(k, data)}}پیام‌های  ممکن است فقط به عنوان بخشی از یک الگوریتم خوددرمانی رخ دهند: اگر یک گره هدف دریافت کند{{Varserif|put(k, data)}}پیام  ، اما معتقد است که{{Varserif|k}} خارج از محدوده کنترل شده خود است و یک گره نزدیکتر (از نظر فضای کلید DHT) شناخته شده است، پیام به آن گره ارسال می شود. در غیر این صورت، داده ها به صورت محلی نمایه می شوند. این منجر به یک رفتار DHT تا حدی متعادل کننده می شود. البته، چنین الگوریتمی به گره ها نیاز دارد تا داده های حضور خود را در DHT منتشر کنند تا جستجوهای تکراری انجام شود.
* از آنجایی که در بیشتر ماشین‌ها ارسال پیام بسیار گران‌تر از دسترسی‌های جدول هش محلی است، منطقی است که بسیاری از پیام‌های مربوط به یک گره خاص را در یک دسته جمع کنیم. با فرض اینکه هر گره دارای یک دسته محلی است که حداکثر از آن تشکیل شده است ، روش بسته‌بندی به شرح زیر است. هر گره ابتدا دسته محلی خود را بر اساس شناسه گره مسئول عملیات مرتب می کند. با استفاده از [[مرتب‌سازی سطلی|مرتب سازی سطلی]] ، می توان این کار را در داخل انجام داد{{Varserif|O(b + n)}} ، که در آن{{Varserif|n}} تعداد گره ها در DHT است. هنگامی که چندین عملیات برای آدرس دادن یک کلید در یک دسته وجود دارد، دسته قبل از ارسال به بیرون متراکم می شود. به عنوان مثال، جستجوی چندگانه یک کلید را می توان به یک یا چند افزایش را می توان به یک عملیات افزودن کاهش داد. این کاهش را می توان با کمک یک جدول هش محلی موقت اجرا کرد. در نهایت عملیات به گره های مربوط ارسال می شود.<ref name="Cite book"/>

== مثال ها ==

=== پروتکل ها و پیاده سازی های DHT ===

* [[آپاچی کسندرا|آپاچی کاساندرا]]
* [[پوشش باتون]]
* [[DHT خط اصلی|DHT خط اصلی – DHT]] استاندارد مورد استفاده توسط BitTorrent (بر اساس [[کادملیا|Kademlia]] که توسط خاشمیر ارائه شده است) <ref>[http://www.tribler.org/trac/wiki/Khashmir Tribler wiki] {{Webarchive|url=https://web.archive.org/web/20101204111423/http://www.tribler.org/trac/wiki/Khashmir|date=December 4, 2010}} retrieved January 2010.</ref>
* [[شبکه آدرس‌دهی محتوا|شبکه آدرس‌پذیر محتوا]] (CAN)
* [[کورد (نظیر به نظیر)|آکورد]]
* [[کورده]]
* [[کادملیا]]
* [[شیرینی (DHT)|شیرینی]]
* [[P-Grid]]
* [[ریاک]]
* [[ملیله (DHT)|ملیله کاری]]
* [[TomP2P]]
* [[ولدمورت (ذخیره داده های توزیع شده)|ولدمورت]]

== برنامه های کاربردی با استفاده از DHT ==

* [[BTDigg]] : موتور جستجوی BitTorrent DHT
* [[کدن]] : کش وب
* [[فری نت|Freenet]] : یک شبکه ناشناس مقاوم در برابر سانسور
* [[گلاستر کورپوریشن|GlusterFS]] : یک سیستم فایل توزیع شده که برای [[مجازی‌سازی|مجازی سازی]] ذخیره سازی استفاده می شود
* [[گنونت|GNUnet]] : شبکه توزیع مانند Freenet شامل اجرای DHT
* [[پروژه اینترنت مخفی|I2P]] : یک شبکه همتا به همتا ناشناس منبع باز
* [[پروژه اینترنت مخفی|I2P-Bote]] : ایمیل ناشناس امن بدون سرور
* [[سیستم پرونده بین سیاره ای|IPFS]] : یک پروتکل توزیع [[ابررسانه]] ای قابل آدرس دهی محتوا و همتا به همتا
* [[جی اکس تی ای|JXTA]] : پلتفرم منبع باز P2P
* [[LBRY]] : یک پروتکل به اشتراک گذاری محتوا مبتنی بر بلاک چین که از سیستم DHT تحت تاثیر [[کادملیا|Kademlia]] برای توزیع محتوا استفاده می کند.
* [[Oracle Coherence]] : یک شبکه داده در حافظه که بر روی اجرای جاوا DHT ساخته شده است
* [[تاریک کامل (P2P)|Perfect Dark]] : یک برنامه [[اشتراک پرونده|به اشتراک گذاری فایل]] [[همتابه‌همتا (رایانه)|نظیر به نظیر]] از ژاپن
* [[رتروشر (نرم‌افزار)|اشتراک گذاری مجدد]] : یک شبکه [[دوست به دوست]] <ref>[http://retroshare.sourceforge.net/wiki/index.php/Frequently_Asked_Questions#4-1_How_does_RetroShare_know_my_friend.27s_IP_address_and_port.3F_Why_don.27t_I_need_a_static_IP_address.3F_What_is_DHT_for.3F Retroshare FAQ] {{Webarchive|url=https://web.archive.org/web/20130717094704/http://retroshare.sourceforge.net/wiki/index.php/Frequently_Asked_Questions#4-1_How_does_RetroShare_know_my_friend.27s_IP_address_and_port.3F_Why_don.27t_I_need_a_static_IP_address.3F_What_is_DHT_for.3F |date=۱۷ ژوئیه ۲۰۱۳ }} retrieved December 2011</ref>
* [[جمی (نرم‌افزار)|جامی]] : یک پلت فرم ارتباطی صوتی، ویدیویی و چت برای حفظ حریم خصوصی، مبتنی بر DHT مانند Kademlia
* [[تاکس (پروتکل)|Tox]] : یک سیستم [[پیام‌رسانی فوری|پیام رسانی فوری]] که به عنوان جایگزین [[اسکایپ]] در نظر گرفته شده است
* [[Twister (نرم افزار)|Twister]] : یک پلتفرم [[میکروبلاگینگ]] [[همتابه‌همتا (رایانه)|نظیر به همتا]]
* [[YaCy]] : یک [[موتور جستجوی وب|موتور جستجوی]] توزیع شده

=== همچنین ببینید ===

* [[مم‌بیس|سرور Couchbase]] : یک سیستم ذخیره سازی اشیاء توزیع شده پایدار، تکراری و خوشه ای سازگار با پروتکل memcached.
* [[مم‌کشد|Memcached]] : یک سیستم ذخیره سازی اشیاء حافظه توزیع شده با کارایی بالا.
* [[پیشوند درخت هش|درخت هش پیشوند]] : پرس و جوی پیچیده روی DHT.
* [[درخت درهم‌سازی|درخت مرکل]] : درختی که هر گره غیربرگی را با هش برچسب‌های گره‌های فرزندش برچسب‌گذاری کرده است.
* اکثر [[ذخیره داده های توزیع شده|فروشگاه های داده توزیع شده]] از نوعی DHT برای جستجو استفاده می کنند.
* [[رد شدن از نمودار|نمودارهای پرش]] یک [[ساختمان داده‌ها|ساختار داده]] کارآمد برای پیاده سازی DHT ها هستند.

== منابع ==
{{پانویس|چپ‌چین=بله|۲}}

[[رده:اشتراک پرونده]]
[[رده:درهم‌سازی]]
[[رده:ذخیره‌سازی داده توزیع‌شده]]
[[رده:معماری شبکه]]