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

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

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

تاریخچه

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

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

Gnutella و شبکه‌های مشابه به یک مدل سیل پرس و جو منتقل شدند – در اصل، هر جستجو منجر به پخش پیامی برای هر ماشین دیگر در شبکه می‌شود. در حالی که اجتناب از یک نقطه شکست، این روش به‌طور قابل توجهی کمتر از 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 برای ذخیره‌سازی و بازیابی ممکن است به شرح زیر انجام شود. فرض کنید فضای کلید مجموعه ای از رشته‌های ۱۶۰ بیتی است. برای نمایه سازی فایل با داده شدهfilename و $data$ در DHT، هش SHA-1 $filename$ تولید می‌شود و یک کلید ۱۶۰ بیتی $k$ تولید می‌شود و یک پیام $put (k, data)$ به هر گره ای که در DHT شرکت می‌کند ارسال می‌شود. پیام از طریق شبکه همپوشانی از گره ای به گره دیگر ارسال می‌شود تا زمانی که به گره تکی مسئول کلید $k$ که توسط پارتیشن‌بندی فضای کلید مشخص شده‌است برسد. سپس آن گره کلید و داده‌ها را ذخیره می‌کند. سپس هر کلاینت دیگری می‌تواند محتویات فایل را با هش کردن مجدد $filename$ برای تولید $k$ و درخواست از هر گره DHT برای یافتن داده‌های مرتبط با $k$ با پیام $get (k)$ بازیابی کند. پیام دوباره از طریق پوشش به گره مسئول $k$ هدایت می‌شود که با $data$ ذخیره شده پاسخ می‌دهد.

پارتیشن‌بندی فضای کلید و اجزای شبکه همپوشانی در زیر با هدف گرفتن ایده‌های اصلی مشترک در اکثر 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 سرور موجود. هر مشتری فهرست یکسانی از شناسه‌های

{S 1, S 2, ..., S n}

{S 1, S 2, ..., S n}

{S 1, S 2, ..., S n}

, یکی برای هر سرور. با توجه به کلید k ، یک کلاینت n وزن هش

w 1 = h (S 1, k), w 2 = h (S 2, k), ..., w n = h (S n, k)

را محاسبه می کند. مشتری آن کلید را با سرور مربوط به بالاترین وزن هش برای آن کلید مرتبط می کند. سرور با شناسه

S_{x}

همه کلیدها را در اختیار دارد

k_{m}

که برای آن وزن هش

h(S_{x},k_{m})

از وزن هش هر گره دیگری برای آن کلید بیشتر است.

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

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

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

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

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

فراتر از صحت مسیریابی اولیه، دو محدودیت مهم در توپولوژی تضمین این است که حداکثر تعداد پرش ها در هر مسیر (طول مسیر) کم است، به طوری که درخواست ها به سرعت تکمیل می شوند. و اینکه حداکثر تعداد همسایگان هر گره (حداکثر درجه گره) کم است، به طوری که سربار تعمیر و نگهداری بیش از حد نباشد. البته داشتن مسیرهای کوتاهتر مستلزم درجه حداکثری بالاتر است. برخی از انتخاب های رایج برای حداکثر درجه و طول مسیر به شرح زیر است، که در آن $n$ تعداد گره ها در 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 استفاده می کنند.
در دنیای واقعی کلیدk می‌تواند هش محتوای یک فایل باشد تا هش نام فایل برای ارائه فضای ذخیره‌سازی آدرس‌پذیر محتوا ، به طوری که تغییر نام فایل مانع از یافتن آن توسط کاربران نشود.
برخی از DHT ها نیز ممکن است اشیاء انواع مختلف را منتشر کنند. مثلا کلیدk می تواند گره باشدID و داده‌های مرتبط می‌توانند نحوه تماس با این گره را توضیح دهند. این امکان انتشار اطلاعات حضوری را فراهم می کند و اغلب در برنامه های IM و غیره استفاده می شود. در ساده ترین حالت،ID فقط یک عدد تصادفی است که مستقیماً به عنوان کلید استفاده می شودk (بنابراین در DHT 160 بیتیID یک عدد 160 بیتی خواهد بود که معمولاً به صورت تصادفی انتخاب می شود. در برخی از DHT ها، انتشار شناسه گره ها نیز برای بهینه سازی عملیات DHT استفاده می شود.
افزونگی را می توان برای بهبود قابلیت اطمینان اضافه کرد. در(k, data)جفت کلید را می توان در بیش از یک گره مربوط به کلید ذخیره کرد. معمولاً به جای انتخاب فقط یک گره، الگوریتم‌های DHT دنیای واقعی انتخاب می‌کنندi گره های مناسب، باi یک پارامتر خاص اجرای DHT هستم. در برخی از طرح‌های DHT، گره‌ها موافقت می‌کنند که محدوده خاصی از فضای کلید را مدیریت کنند، که اندازه آن ممکن است به‌جای کدگذاری سخت، به صورت پویا انتخاب شود.
برخی از DHT های پیشرفته مانند Kademlia ابتدا جستجوهای تکراری را از طریق DHT انجام می دهند تا مجموعه ای از گره های مناسب را انتخاب کرده و ارسال کنند.put(k, data)پیام‌ها فقط به آن گره‌ها ارسال کنید، بنابراین ترافیک بی‌فایده را به شدت کاهش می‌دهد، زیرا پیام‌های منتشر شده فقط به گره‌هایی ارسال می‌شوند که برای ذخیره‌سازی کلید مناسب به نظر می‌رسند.k ; و جستجوهای مکرر فقط مجموعه کوچکی از گره ها را به جای کل DHT پوشش می دهند و ارسال بی فایده را کاهش می دهند. در چنین DHT ها، ارسال ازput(k, data)پیام‌های ممکن است فقط به عنوان بخشی از یک الگوریتم خوددرمانی رخ دهند: اگر یک گره هدف دریافت کندput(k, data)پیام ، اما معتقد است کهk خارج از محدوده کنترل شده خود است و یک گره نزدیکتر (از نظر فضای کلید DHT) شناخته شده است، پیام به آن گره ارسال می شود. در غیر این صورت، داده ها به صورت محلی نمایه می شوند. این منجر به یک رفتار DHT تا حدی متعادل کننده می شود. البته، چنین الگوریتمی به گره ها نیاز دارد تا داده های حضور خود را در DHT منتشر کنند تا جستجوهای تکراری انجام شود.
از آنجایی که در بیشتر ماشین‌ها ارسال پیام بسیار گران‌تر از دسترسی‌های جدول هش محلی است، منطقی است که بسیاری از پیام‌های مربوط به یک گره خاص را در یک دسته جمع کنیم. با فرض اینکه هر گره دارای یک دسته محلی است که حداکثر از آن تشکیل شده است ، روش بسته‌بندی به شرح زیر است. هر گره ابتدا دسته محلی خود را بر اساس شناسه گره مسئول عملیات مرتب می کند. با استفاده از مرتب سازی سطلی ، می توان این کار را در داخل انجام دادO(b + n) ، که در آنn تعداد گره ها در 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 ها هستند.

منابع

↑ Stoica, I.; Morris, R.; Karger, D.; Kaashoek, M. F.; Balakrishnan, H. (2001). "Chord: A scalable peer-to-peer lookup service for internet applications" (PDF). ACM SIGCOMM Computer Communication Review. 31 (4): 149. doi:10.1145/964723.383071. A value can be an address, a document, or an arbitrary data item.
↑ Liz, Crowcroft; et al. (2005). "A survey and comparison of peer-to-peer overlay network schemes" (PDF). IEEE Communications Surveys & Tutorials. 7 (2): 72–93. CiteSeerX 10.1.1.109.6124. doi:10.1109/COMST.2005.1610546.
↑ Richter, Stevenson; et al. (2009). "Analysis of the impact of dynamic querying models on client-server relationships". Trends in Modern Computing: 682–701.
↑ Searching in a Small World Chapters 1 & 2 (PDF), retrieved 2012-01-10
↑ "Section 5.2.2" (PDF), A Distributed Decentralized Information Storage and Retrieval System, retrieved 2012-01-10
↑ Ratnasamy; et al. (2001). "A Scalable Content-Addressable Network" (PDF). In Proceedings of ACM SIGCOMM 2001. Retrieved 2013-05-20.
↑ Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris, and Ion Stoica. Looking up data in P2P systems. In Communications of the ACM, February 2003.
↑ David Cohen (October 1, 2002). "New P2P network funded by US government". New Scientist. Retrieved November 10, 2013.
↑ "MIT, Berkeley, ICSI, NYU, and Rice Launch the IRIS Project". Press release. MIT. September 25, 2002. Archived from the original on September 26, 2015. Retrieved November 10, 2013.
↑ R Mokadem, A Hameurlain and AM Tjoa. Resource discovery service while minimizing maintenance overhead in hierarchical DHT systems. Proc. iiWas, 2010
↑ Guido Urdaneta, Guillaume Pierre and Maarten van Steen. A Survey of DHT Security Techniques. ACM Computing Surveys 43(2), January 2011.
↑ Moni Naor and Udi Wieder. Novel Architectures for P2P Applications: the Continuous-Discrete Approach. Proc. SPAA, 2003.
↑ Gurmeet Singh Manku. Dipsea: A Modular Distributed Hash Table بایگانی‌شده در ۲۰۰۴-۰۹-۱۰ توسط Wayback Machine. Ph. D. Thesis (Stanford University), August 2004.
↑ Girdzijauskas, Šarūnas; Datta, Anwitaman; Aberer, Karl (2010-02-01). "Structured overlay for heterogeneous environments". ACM Transactions on Autonomous and Adaptive Systems. 5 (1): 1–25. doi:10.1145/1671948.1671950. ISSN 1556-4665.
↑ Forestiero, Agostino; Leonardi, Emilio; Mastroianni, Carlo; Meo, Michela (October 2010). "Self-Chord: A Bio-Inspired P2P Framework for Self-Organizing Distributed Systems". IEEE/ACM Transactions on Networking. 18 (5): 1651–1664. doi:10.1109/TNET.2010.2046745.
↑ Galuba, Wojciech; Girdzijauskas, Sarunas (2009), LIU, LING; ÖZSU, M. TAMER (eds.), "Peer to Peer Overlay Networks: Structure, Routing and Maintenance", Encyclopedia of Database Systems (به انگلیسی), Springer US: 2056–2061, doi:10.1007/978-0-387-39940-9_1215, ISBN 9780387399409
↑
↑ The (Degree,Diameter) Problem for Graphs, Maite71.upc.es, archived from the original on 2012-02-17, retrieved 2012-01-10
↑ Gurmeet Singh Manku, Moni Naor, and Udi Wieder. "Know thy Neighbor's Neighbor: the Power of Lookahead in Randomized P2P Networks". Proc. STOC, 2004.
↑ Ali Ghodsi (22 May 2007). "Distributed k-ary System: Algorithms for Distributed Hash Tables". Archived from the original on 4 January 2007.. KTH-Royal Institute of Technology, 2006.
↑ Castro, Miguel; Costa, Manuel; Rowstron, Antony (1 January 2004). "Should we build Gnutella on a structured overlay?" (PDF). ACM SIGCOMM Computer Communication Review. 34 (1): 131. CiteSeerX 10.1.1.221.7892. doi:10.1145/972374.972397.
↑ Talia, Domenico; Trunfio, Paolo (December 2010). "Enabling Dynamic Querying over Distributed Hash Tables". Journal of Parallel and Distributed Computing. 70 (12): 1254–1265. doi:10.1016/j.jpdc.2010.08.012.
↑ Baruch Awerbuch, Christian Scheideler. "Towards a scalable and robust DHT". 2006. doi:10.1145/1148109.1148163
↑ Maxwell Young; Aniket Kate; Ian Goldberg; Martin Karsten. "Practical Robust Communication in DHTs Tolerating a Byzantine Adversary".
↑ 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
↑ Whanau: A Sybil-proof Distributed Hash Table https://pdos.csail.mit.edu/papers/whanau-nsdi10.pdf
↑ Chris Lesniewski-Laas. "A Sybil-proof one-hop DHT" (PDF): 20.
↑ Jonathan Kelner, Petar Maymounkov (2009). "Electric routing and concurrent flow cutting". arXiv:0909.2859. Bibcode:2009arXiv0909.2859K.
↑
↑ Tribler wiki بایگانی‌شده در دسامبر ۴, ۲۰۱۰ توسط Wayback Machine retrieved January 2010.
↑ Retroshare FAQ retrieved December 2011

[StoicaEtAl2001-1] Stoica, I.; Morris, R.; Karger, D.; Kaashoek, M. F.; Balakrishnan, H. (2001). "Chord: A scalable peer-to-peer lookup service for internet applications" (PDF). ACM SIGCOMM Computer Communication Review. 31 (4): 149. doi:10.1145/964723.383071. A value can be an address, a document, or an arbitrary data item.

[2] Liz, Crowcroft; et al. (2005). "A survey and comparison of peer-to-peer overlay network schemes" (PDF). IEEE Communications Surveys & Tutorials. 7 (2): 72–93. CiteSeerX 10.1.1.109.6124. doi:10.1109/COMST.2005.1610546.

[3] Richter, Stevenson; et al. (2009). "Analysis of the impact of dynamic querying models on client-server relationships". Trends in Modern Computing: 682–701.

[4] Searching in a Small World Chapters 1 & 2 (PDF), retrieved 2012-01-10

[5] "Section 5.2.2" (PDF), A Distributed Decentralized Information Storage and Retrieval System, retrieved 2012-01-10

[Ratnasamy01-6] Ratnasamy; et al. (2001). "A Scalable Content-Addressable Network" (PDF). In Proceedings of ACM SIGCOMM 2001. Retrieved 2013-05-20.

[7] Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris, and Ion Stoica. Looking up data in P2P systems. In Communications of the ACM, February 2003.

[8] David Cohen (October 1, 2002). "New P2P network funded by US government". New Scientist. Retrieved November 10, 2013.

[9] "MIT, Berkeley, ICSI, NYU, and Rice Launch the IRIS Project". Press release. MIT. September 25, 2002. Archived from the original on September 26, 2015. Retrieved November 10, 2013.

[10] R Mokadem, A Hameurlain and AM Tjoa. Resource discovery service while minimizing maintenance overhead in hierarchical DHT systems. Proc. iiWas, 2010

[11] Guido Urdaneta, Guillaume Pierre and Maarten van Steen. A Survey of DHT Security Techniques. ACM Computing Surveys 43(2), January 2011.

[12] Moni Naor and Udi Wieder. Novel Architectures for P2P Applications: the Continuous-Discrete Approach. Proc. SPAA, 2003.

[13] Gurmeet Singh Manku. Dipsea: A Modular Distributed Hash Table بایگانی‌شده در ۲۰۰۴-۰۹-۱۰ توسط Wayback Machine. Ph. D. Thesis (Stanford University), August 2004.

[14] Girdzijauskas, Šarūnas; Datta, Anwitaman; Aberer, Karl (2010-02-01). "Structured overlay for heterogeneous environments". ACM Transactions on Autonomous and Adaptive Systems. 5 (1): 1–25. doi:10.1145/1671948.1671950. ISSN 1556-4665.

[15] Forestiero, Agostino; Leonardi, Emilio; Mastroianni, Carlo; Meo, Michela (October 2010). "Self-Chord: A Bio-Inspired P2P Framework for Self-Organizing Distributed Systems". IEEE/ACM Transactions on Networking. 18 (5): 1651–1664. doi:10.1109/TNET.2010.2046745.

[16] Galuba, Wojciech; Girdzijauskas, Sarunas (2009), LIU, LING; ÖZSU, M. TAMER (eds.), "Peer to Peer Overlay Networks: Structure, Routing and Maintenance", Encyclopedia of Database Systems (به انگلیسی), Springer US: 2056–2061, doi:10.1007/978-0-387-39940-9_1215, ISBN 9780387399409

[17] ↑

[18] The (Degree,Diameter) Problem for Graphs, Maite71.upc.es, archived from the original on 2012-02-17, retrieved 2012-01-10

[19] Gurmeet Singh Manku, Moni Naor, and Udi Wieder. "Know thy Neighbor's Neighbor: the Power of Lookahead in Randomized P2P Networks". Proc. STOC, 2004.

[20] Ali Ghodsi (22 May 2007). "Distributed k-ary System: Algorithms for Distributed Hash Tables". Archived from the original on 4 January 2007.. KTH-Royal Institute of Technology, 2006.

[21] Castro, Miguel; Costa, Manuel; Rowstron, Antony (1 January 2004). "Should we build Gnutella on a structured overlay?" (PDF). ACM SIGCOMM Computer Communication Review. 34 (1): 131. CiteSeerX 10.1.1.221.7892. doi:10.1145/972374.972397.

[22] Talia, Domenico; Trunfio, Paolo (December 2010). "Enabling Dynamic Querying over Distributed Hash Tables". Journal of Parallel and Distributed Computing. 70 (12): 1254–1265. doi:10.1016/j.jpdc.2010.08.012.

[23] Baruch Awerbuch, Christian Scheideler. "Towards a scalable and robust DHT". 2006. doi:10.1145/1148109.1148163

[24] Maxwell Young; Aniket Kate; Ian Goldberg; Martin Karsten. "Practical Robust Communication in DHTs Tolerating a Byzantine Adversary".

[25] 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

[26] Whanau: A Sybil-proof Distributed Hash Table https://pdos.csail.mit.edu/papers/whanau-nsdi10.pdf

[27] Chris Lesniewski-Laas. "A Sybil-proof one-hop DHT" (PDF): 20.

[28] Jonathan Kelner, Petar Maymounkov (2009). "Electric routing and concurrent flow cutting". arXiv:0909.2859. Bibcode:2009arXiv0909.2859K.

[29] ↑

[30] Tribler wiki بایگانی‌شده در دسامبر ۴, ۲۰۱۰ توسط Wayback Machine retrieved January 2010.

[31] Retroshare FAQ retrieved December 2011