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

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

جدول درهم‌سازی توزیع‌شده الگو:انگلیسی به صورت کوتاه شده DHT یک سیستم توزیع شده‌است که خدمات جستجویی مشابه جدول هش ارائه می‌دهد: جفت‌های کلید-مقدار در یک DHT ذخیره می‌شوند و هر گره شرکت کننده می‌تواند به‌طور مؤثر مقدار مربوط به یک کلید داده شده را بازیابی کند. مزیت اصلی DHT این است که گره‌ها را می‌توان با حداقل کار در مورد توزیع مجدد کلیدها اضافه یا حذف کرد. کلیدها شناسه‌های منحصربه‌فردی هستند که به مقادیر خاصی نگاشت می‌شوند، که به نوبه خود می‌توانند هر چیزی از آدرس‌ها، اسناد و داده‌های دلخواه باشند. مسئولیت حفظ نقشه‌برداری از کلیدها به مقادیر بین گره‌ها توزیع می‌شود، به گونه ای که تغییر در مجموعه شرکت کنندگان باعث ایجاد حداقل اختلال می‌شود. این به یک DHT اجازه می‌دهد تا به تعداد بسیار زیادی از گره‌ها گسترده شود و ورود، خروج و خرابی مداوم گره‌ها را مدیریت کند.

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

تاریخچه

تحقیقات DHT در اصل، تا حدی توسط سیستم‌های همتا به همتا (P2P) مانند Freenet، Gnutella، BitTorrent و Napster انجام شد که از منابع توزیع شده در سراسر اینترنت برای ارائه یک برنامه کاربردی مفید استفاده کردند. به ویژه، آنها از افزایش پهنای باند و ظرفیت هارد دیسک برای ارائه خدمات اشتراک فایل استفاده کردند.

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

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

Freenet به‌طور کامل توزیع شده‌است، اما از یک مسیریابی مبتنی بر کلید اکتشافی استفاده می‌کند که در آن هر فایل با یک کلید مرتبط است، و فایل‌هایی با کلیدهای مشابه تمایل دارند در مجموعه‌ای از گره‌های مشابه خوشه شوند. پرس و جوها احتمالاً از طریق شبکه به چنین خوشه ای بدون نیاز به بازدید از همتایان زیادی هدایت می‌شوند. با این حال، Freenet تضمین نمی‌کند که داده‌ها پیدا شوند.

جداول هش توزیع‌شده از مسیریابی مبتنی بر کلید ساختاریافته‌تر برای دستیابی به تمرکززدایی Freenet و Gnutella و کارایی و نتایج تضمین‌شده Napster استفاده می‌کنند. یک اشکال این است که، مانند Freenet, DHTها به جای جستجوی کلمه کلیدی، فقط مستقیماً از جستجوی تطابق دقیق پشتیبانی می‌کنند، اگرچه الگوریتم مسیریابی فری نت را می‌توان به هر نوع کلیدی تعمیم داد که در آن عملیات نزدیکی تعریف شود.

در سال ۲۰۰۱، چهار سیستم — CAN , Chord , Pastry، و Tapestry — DHTها را به عنوان یک موضوع تحقیقاتی محبوب روشن کردند. پروژه ای به نام زیرساخت برای سیستم‌های اینترنتی مقاوم (Iris) با کمک مالی ۱۲ میلیون دلاری از بنیاد ملی علوم ایالات متحده در سال ۲۰۰۲ تأمین. محققان شامل سیلویا راتناسامی، یون استویکا، هاری بالاکریشنان و اسکات شنکر بودند. در خارج از دانشگاه، فناوری DHT به عنوان جزئی از BitTorrent و در شبکه توزیع محتوای Coral پذیرفته شده‌است.

ویژگی‌ها

DHTها به‌طور مشخص بر ویژگی‌های زیر تأکید دارند:

• خودمختاری و عدم تمرکز: گره‌ها به‌طور جمعی سیستم را بدون هیچ هماهنگی مرکزی تشکیل می‌دهند.
• تحمل خطا: سیستم باید قابل اعتماد (به نوعی) حتی با پیوستن، خروج و خرابی پیوسته گره‌ها باشد.
• مقیاس پذیری: سیستم باید حتی با هزاران یا میلیون‌ها گره به‌طور مؤثر عمل کند.

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

برخی از طرح‌های DHT به دنبال ایمن بودن در برابر شرکت‌کنندگان مخرب هستند و به شرکت‌کنندگان اجازه می‌دهند ناشناس باقی بمانند، اگرچه این نسبت در بسیاری از سیستم‌های همتا به همتا (به ویژه اشتراک‌گذاری فایل) کمتر رایج است. P2P ناشناس را ببینید.

ساختار

ساختار یک DHT را می‌توان به چندین جزء اصلی تجزیه کرد. پایه یک فضای کلید انتزاعی است، مانند مجموعه رشته‌های ۱۶۰ بیتی. یک طرح پارتیشن‌بندی فضای کلید، مالکیت این فضای کلیدی را بین گره‌های شرکت کننده تقسیم می‌کند. سپس یک شبکه همپوشانی گره‌ها را به هم متصل می‌کند و به آن‌ها اجازه می‌دهد تا صاحب هر کلیدی را در فضای کلید پیدا کنند.

هنگامی که این اجزا در جای خود قرار گرفتند، استفاده معمولی از DHT برای ذخیره‌سازی و بازیابی ممکن است به شرح زیر انجام شود. فرض کنید فضای کلید مجموعه ای از رشته‌های ۱۶۰ بیتی است. برای نمایه سازی فایل با داده شدهالگو:Varserif و الگو:Mvar در DHT، هش SHA-1 الگو:Mvar تولید می‌شود و یک کلید ۱۶۰ بیتی الگو:Mvar تولید می‌شود و یک پیام الگو:ریاضی به هر گره ای که در DHT شرکت می‌کند ارسال می‌شود. پیام از طریق شبکه همپوشانی از گره ای به گره دیگر ارسال می‌شود تا زمانی که به گره تکی مسئول کلید الگو:Mvar که توسط پارتیشن‌بندی فضای کلید مشخص شده‌است برسد. سپس آن گره کلید و داده‌ها را ذخیره می‌کند. سپس هر کلاینت دیگری می‌تواند محتویات فایل را با هش کردن مجدد الگو:Mvar برای تولید الگو:Mvar و درخواست از هر گره DHT برای یافتن داده‌های مرتبط با الگو:Mvar با پیام الگو:ریاضی بازیابی کند. پیام دوباره از طریق پوشش به گره مسئول الگو:Mvar هدایت می‌شود که با الگو:Mvar ذخیره شده پاسخ می‌دهد.

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

پارتیشن بندی فضای کلیدی

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

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

هش کردن مداوم

هش ثابت یک تابع را به کار می گیرد $\delta (k_1,k_2)$ که یک مفهوم انتزاعی از فاصله بین کلیدها را تعریف می کند $k_1$ و $k_2$ ، که با فاصله جغرافیایی یا تاخیر شبکه ارتباطی ندارد. به هر گره یک کلید به نام شناسه آن (ID) اختصاص داده می شود. یک گره با شناسه $i_x$ همه کلیدها را در اختیار دارد $k_m$ برای کدام $i_x$ نزدیکترین شناسه است که بر اساس اندازه گیری می شود $\delta (k_m,i_x)$ .

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

هش قرار ملاقات(Rendezvous)

در هش قرار ملاقات که هش با بالاترین وزن تصادفی (HRW) نیز نامیده می شود، همه مشتریان از یک تابع هش استفاده می کنند. $h()$ (انتخاب زودتر از زمان) برای مرتبط کردن یک کلید به یکی از n سرور موجود. هر مشتری فهرست یکسانی از شناسه‌های الگو:ریاضی الگو:ریاضی الگو:ریاضی, یکی برای هر سرور. با توجه به کلید k ، یک کلاینت n وزن هش الگو:ریاضی را محاسبه می کند. مشتری آن کلید را با سرور مربوط به بالاترین وزن هش برای آن کلید مرتبط می کند. سرور با شناسه $S_x$ همه کلیدها را در اختیار دارد $k_m$ که برای آن وزن هش $h(S_x,k_m)$ از وزن هش هر گره دیگری برای آن کلید بیشتر است.

هش با حفظ محلیت

هش با حفظ محلیت تضمین می کند که کلیدهای مشابه به اشیاء مشابه اختصاص داده می شوند. این می تواند اجرای کارآمدتر پرس و جوهای محدوده را امکان پذیر کند، با این حال، برخلاف استفاده از هش ثابت، اطمینان بیشتری وجود ندارد که کلیدها (و بنابراین بار) به‌طور تصادفی یکنواخت در فضای کلید و همتاهای شرکت کننده توزیع شده اند. پروتکل های DHT مانند Self-Cord و Oscar به چنین مسائلی می پردازند. Self-Cord کلیدهای شی را از شناسه‌های همتا جدا می‌کند و کلیدها را در امتداد حلقه با رویکردی آماری بر اساس الگوی هوش ازدحام دسته‌بندی می‌کند. مرتب‌سازی تضمین می‌کند که کلیدهای مشابه توسط گره‌های همسایه ذخیره می‌شوند و روش‌های کشف، از جمله پرس‌وجوهای محدوده ، می‌توانند در زمان لگاریتمی انجام شوند. اسکار یک شبکه جهان کوچک قابل کشتیرانی را بر اساس نمونه‌برداری تصادفی پیاده‌روی ایجاد می‌کند و همچنین زمان جستجوی لگاریتمی را تضمین می‌کند.

شبکه همپوشانی

هر گره مجموعه ای از پیوندها را به گره های دیگر ( همسایگان یا جدول مسیریابی خود) حفظ می کند. این پیوندها با هم شبکه همپوشانی را تشکیل می دهند. یک گره همسایگان خود را بر اساس ساختار خاصی انتخاب می کند که توپولوژی شبکه نامیده می شود.

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

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

حداکثر درجه	حداکثر طول مسیر	استفاده شده در	توجه داشته باشید
$O(1)$	$O(n)$		بدترین طول جستجو، با زمان جستجوی احتمالی بسیار کندتر
$O(1)$	$O(\log n)$	کورده (با درجه ثابت)	پیاده سازی پیچیده تر، اما زمان جستجوی قابل قبولی را می توان با تعداد ثابتی از اتصالات یافت
$O(\log n)$	$O(\log n)$	آکوردکادملیاشیرینیملیله کاری	رایج ترین، اما نه بهینه (درجه/طول مسیر). آکورد ابتدایی ترین نسخه است، به نظر می رسد Kademlia محبوب ترین نسخه بهینه شده است (باید جستجوی متوسط بهبود یافته باشد)
$O(\log n)$	$O(\log n/\log (\log n))$	Koorde (با جستجوی بهینه)	پیاده‌سازی پیچیده‌تر است، اما جستجوها ممکن است سریع‌تر باشند (بدترین حالت کمتری دارند)
$O(\sqrt{n})$	$O(1)$		بدترین نیازهای ذخیره سازی محلی، با ارتباطات زیاد پس از اتصال یا قطع شدن هر گره

رایج ترین انتخاب، $O(\log n)$ طول درجه/مسیر، از نظر مبادله طول درجه/مسیر بهینه نیست، اما چنین توپولوژی‌هایی معمولاً انعطاف‌پذیری بیشتری را در انتخاب همسایگان فراهم می‌کنند. بسیاری از DHT ها از این انعطاف پذیری برای انتخاب همسایه هایی استفاده می کنند که از نظر تأخیر در شبکه فیزیکی زیربنایی نزدیک هستند. به‌طور کلی، همه DHT ها توپولوژی های شبکه جهان کوچک قابل کشتیرانی را ایجاد می کنند که طول مسیر را با درجه شبکه مقایسه می کند.

حداکثر طول مسیر ارتباط نزدیکی با قطر دارد : حداکثر تعداد پرش ها در هر کوتاه ترین مسیر بین گره ها. واضح است که طول مسیر شبکه در بدترین حالت حداقل به اندازه قطر آن است، بنابراین DHT ها توسط مبادله درجه/قطر که در نظریه گراف اساسی است، محدود می شوند. طول مسیر می تواند بیشتر از قطر باشد، زیرا الگوریتم مسیریابی حریصانه ممکن است کوتاه ترین مسیرها را پیدا نکند.

الگوریتم های شبکه های همپوشانی

جدای از مسیریابی، الگوریتم‌های زیادی وجود دارد که از ساختار شبکه همپوشانی برای ارسال پیام به تمام گره‌ها یا زیر مجموعه‌ای از گره‌ها در یک DHT استفاده می‌کنند. این الگوریتم ها توسط برنامه های کاربردی برای انجام چندپخشی همپوشانی ، پرس و جوهای محدوده یا جمع آوری آمار استفاده می شود. دو سیستمی که مبتنی بر این رویکرد هستند، Structella، که flooding و پیمایش های تصادفی را بر روی یک پوشش Pastry پیاده‌سازی می‌کند، و DQ-DHT، که یک الگوریتم جستجوی پویا را بر روی یک شبکه آکورد پیاده‌سازی می‌کند.

امنیت

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

سیستم‌های باز برای ذخیره‌سازی داده‌های توزیع‌شده که در برابر مهاجمان خصمانه عظیم قوی هستند، امکان‌پذیر هستند.

یک سیستم DHT که به دقت طراحی شده است تا دارای تحمل خطای بیزانسی باشد، می‌تواند در برابر ضعف امنیتی، معروف به حمله Sybil ، که بیشتر طرح‌های DHT فعلی را تحت تأثیر قرار می‌دهد، دفاع کند. Whanau یک DHT است که برای مقاومت در برابر حملات Sybil طراحی شده است.

پتار میمونکوف، یکی از نویسندگان اصلی Kademlia ، راهی را برای دور زدن ضعف حمله Sybil با گنجاندن روابط اعتماد اجتماعی در طراحی سیستم پیشنهاد کرده است. سیستم جدید که با نام رمز Tonika یا با نام دامنه آن به عنوان 5ttt شناخته می شود، بر اساس طراحی الگوریتمی به نام "مسیریابی الکتریکی" و با همکاری ریاضیدان جاناتان کلنر ساخته شده است. مایمونکوف اکنون یک تلاش جامع برای اجرای این سیستم جدید را انجام داده است. با این حال، تحقیق در مورد دفاع مؤثر در برابر حملات Sybil به‌طور کلی یک سؤال باز در نظر گرفته می شود، و انواع گسترده ای از دفاع های بالقوه هر ساله در کنفرانس های تحقیقاتی امنیتی برتر پیشنهاد می شود.الگو:مدرک

پیاده سازی ها

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

• فضای آدرس، پارامتری از DHT است. چندین DHT از فضای کلید 128 بیتی یا 160 بیتی استفاده می کنند.
• برخی از DHT های دنیای واقعی از توابع هش غیر از SHA-1 استفاده می کنند.
• در دنیای واقعی کلیدالگو:Varserif می‌تواند هش محتوای یک فایل باشد تا هش نام فایل برای ارائه فضای ذخیره‌سازی آدرس‌پذیر محتوا ، به‌طوری که تغییر نام فایل مانع از یافتن آن توسط کاربران نشود.
• برخی از DHT ها نیز ممکن است اشیاء انواع مختلف را منتشر کنند. مثلا کلیدالگو:Varserif می تواند گره باشدالگو:Varserif و داده‌های مرتبط می‌توانند نحوه تماس با این گره را توضیح دهند. این امکان انتشار اطلاعات حضوری را فراهم می کند و اغلب در برنامه های IM و غیره استفاده می شود. در ساده ترین حالت،الگو:Varserif فقط یک عدد تصادفی است که مستقیماً به عنوان کلید استفاده می شودالگو:Varserif (بنابراین در DHT 160 بیتیالگو:Varserif یک عدد 160 بیتی خواهد بود که معمولاً به صورت تصادفی انتخاب می شود. در برخی از DHT ها، انتشار شناسه گره ها نیز برای بهینه سازی عملیات DHT استفاده می شود.
• افزونگی را می توان برای بهبود قابلیت اطمینان اضافه کرد. درالگو:Varserifجفت کلید را می توان در بیش از یک گره مربوط به کلید ذخیره کرد. معمولاً به جای انتخاب فقط یک گره، الگوریتم‌های DHT دنیای واقعی انتخاب می‌کنندالگو:Varserif گره های مناسب، باالگو:Varserif یک پارامتر خاص اجرای DHT هستم. در برخی از طرح‌های DHT، گره‌ها موافقت می‌کنند که محدوده خاصی از فضای کلید را مدیریت کنند، که اندازه آن ممکن است به‌جای کدگذاری سخت، به صورت پویا انتخاب شود.
• برخی از DHT های پیشرفته مانند Kademlia ابتدا جستجوهای تکراری را از طریق DHT انجام می دهند تا مجموعه ای از گره های مناسب را انتخاب کرده و ارسال کنند.الگو:Varserifپیام‌ها فقط به آن گره‌ها ارسال کنید، بنابراین ترافیک بی‌فایده را به شدت کاهش می‌دهد، زیرا پیام‌های منتشر شده فقط به گره‌هایی ارسال می‌شوند که برای ذخیره‌سازی کلید مناسب به نظر می‌رسند.الگو:Varserif ; و جستجوهای مکرر فقط مجموعه کوچکی از گره ها را به جای کل DHT پوشش می دهند و ارسال بی فایده را کاهش می دهند. در چنین DHT ها، ارسال ازالگو:Varserifپیام‌های ممکن است فقط به عنوان بخشی از یک الگوریتم خوددرمانی رخ دهند: اگر یک گره هدف دریافت کندالگو:Varserifپیام ، اما معتقد است کهالگو:Varserif خارج از محدوده کنترل شده خود است و یک گره نزدیکتر (از نظر فضای کلید DHT) شناخته شده است، پیام به آن گره ارسال می شود. در غیر این صورت، داده ها به صورت محلی نمایه می شوند. این منجر به یک رفتار DHT تا حدی متعادل کننده می شود. البته، چنین الگوریتمی به گره ها نیاز دارد تا داده های حضور خود را در DHT منتشر کنند تا جستجوهای تکراری انجام شود.
• از آنجایی که در بیشتر ماشین‌ها ارسال پیام بسیار گران‌تر از دسترسی‌های جدول هش محلی است، منطقی است که بسیاری از پیام‌های مربوط به یک گره خاص را در یک دسته جمع کنیم. با فرض اینکه هر گره دارای یک دسته محلی است که حداکثر از آن تشکیل شده است ، روش بسته‌بندی به شرح زیر است. هر گره ابتدا دسته محلی خود را بر اساس شناسه گره مسئول عملیات مرتب می کند. با استفاده از مرتب سازی سطلی ، می توان این کار را در داخل انجام دادالگو:Varserif ، که در آنالگو:Varserif تعداد گره ها در DHT است. هنگامی که چندین عملیات برای آدرس دادن یک کلید در یک دسته وجود دارد، دسته قبل از ارسال به بیرون متراکم می شود. به عنوان مثال، جستجوی چندگانه یک کلید را می توان به یک یا چند افزایش را می توان به یک عملیات افزودن کاهش داد. این کاهش را می توان با کمک یک جدول هش محلی موقت اجرا کرد. در نهایت عملیات به گره های مربوط ارسال می شود.

مثال ها

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

• آپاچی کاساندرا
• پوشش باتون
• DHT خط اصلی – DHT استاندارد مورد استفاده توسط BitTorrent (بر اساس Kademlia که توسط خاشمیر ارائه شده است)
• شبکه آدرس‌پذیر محتوا (CAN)
• آکورد
• کورده
• کادملیا
• شیرینی
• P-Grid
• ریاک
• ملیله کاری
• TomP2P
• ولدمورت

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

• BTDigg : موتور جستجوی BitTorrent DHT
• کدن : کش وب
• Freenet : یک شبکه ناشناس مقاوم در برابر سانسور
• GlusterFS : یک سیستم فایل توزیع شده که برای مجازی سازی ذخیره سازی استفاده می شود
• GNUnet : شبکه توزیع مانند Freenet شامل اجرای DHT
• I2P : یک شبکه همتا به همتا ناشناس منبع باز
• I2P-Bote : ایمیل ناشناس امن بدون سرور
• IPFS : یک پروتکل توزیع ابررسانه ای قابل آدرس دهی محتوا و همتا به همتا
• JXTA : پلتفرم منبع باز P2P
• LBRY : یک پروتکل به اشتراک گذاری محتوا مبتنی بر بلاک چین که از سیستم DHT تحت تاثیر Kademlia برای توزیع محتوا استفاده می کند.
• Oracle Coherence : یک شبکه داده در حافظه که بر روی اجرای جاوا DHT ساخته شده است
• Perfect Dark : یک برنامه به اشتراک گذاری فایل نظیر به نظیر از ژاپن
• اشتراک گذاری مجدد : یک شبکه دوست به دوست
• جامی : یک پلت فرم ارتباطی صوتی، ویدیویی و چت برای حفظ حریم خصوصی، مبتنی بر DHT مانند Kademlia
• Tox : یک سیستم پیام رسانی فوری که به عنوان جایگزین اسکایپ در نظر گرفته شده است
• Twister : یک پلتفرم میکروبلاگینگ نظیر به همتا
• YaCy : یک موتور جستجوی توزیع شده

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

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