جدول درهم‌سازی توزیع‌شده
جدول درهم‌سازی توزیع‌شده به صورت کوتاه شده 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 به دنبال ایمن بودن در برابر شرکت‌کنندگان مخرب هستند و به شرکت‌کنندگان اجازه می‌دهند ناشناس باقی بمانند، اگرچه این نسبت در بسیاری از سیستم‌های همتا به همتا (به ویژه اشتراک‌گذاری فایل) کمتر رایج است. را ببینید.
ساختار یک DHT را می‌توان به چندین جزء اصلی تجزیه کرد. پایه یک فضای کلید انتزاعی است، مانند مجموعه رشته‌های ۱۶۰ بیتی. یک طرح پارتیشن‌بندی فضای کلید، مالکیت این فضای کلیدی را بین گره‌های شرکت کننده تقسیم می‌کند. سپس یک شبکه همپوشانی گره‌ها را به هم متصل می‌کند و به آن‌ها اجازه می‌دهد تا صاحب هر کلیدی را در فضای کلید پیدا کنند.
هنگامی که این اجزا در جای خود قرار گرفتند، استفاده معمولی از DHT برای ذخیره‌سازی و بازیابی ممکن است به شرح زیر انجام شود. فرض کنید فضای کلید مجموعه ای از رشته‌های ۱۶۰ بیتی است. برای نمایه سازی فایل با داده شده و در DHT، هش SHA-1 تولید می‌شود و یک کلید ۱۶۰ بیتی تولید می‌شود و یک پیام به هر گره ای که در DHT شرکت می‌کند ارسال می‌شود. پیام از طریق شبکه همپوشانی از گره ای به گره دیگر ارسال می‌شود تا زمانی که به گره تکی مسئول کلید که توسط پارتیشن‌بندی فضای کلید مشخص شده‌است برسد. سپس آن گره کلید و داده‌ها را ذخیره می‌کند. سپس هر کلاینت دیگری می‌تواند محتویات فایل را با هش کردن مجدد برای تولید و درخواست از هر گره DHT برای یافتن داده‌های مرتبط با با پیام بازیابی کند. پیام دوباره از طریق پوشش به گره مسئول هدایت می‌شود که با ذخیره شده پاسخ می‌دهد.
پارتیشن‌بندی فضای کلید و اجزای شبکه همپوشانی در زیر با هدف گرفتن ایده‌های اصلی مشترک در اکثر DHTها توضیح داده شده‌است. بسیاری از طرح‌ها در جزئیات متفاوت هستند.
اکثر DHT ها از نوعی هش ثابت یا هش قرار ملاقات برای نگاشت کلیدها به گره ها استفاده می کنند. به نظر می رسد که این دو الگوریتم به طور مستقل و به طور همزمان برای حل مشکل جدول هش توزیع شده ابداع شده اند. هر دو هش ثابت و هش جابجاشونده این ویژگی اساسی را دارند که حذف یا افزودن یک گره تنها مجموعه کلیدهای متعلق به گره‌ها با شناسه‌های مجاور را تغییر می‌دهد و همه گره‌های دیگر را بی‌تأثیر می‌گذارد. این را با جدول هش سنتی مقایسه کنید که در آن اضافه یا حذف یک سطل باعث می‌شود تقریباً کل فضای کلید دوباره نقشه‌برداری شود. از آنجایی که هر تغییری در مالکیت معمولاً مربوط به حرکت پهنای باند فشرده اشیاء ذخیره شده در DHT از یک گره به گره دیگر است، به حداقل رساندن چنین سازماندهی مجدد برای پشتیبانی کارآمد از نرخ های بالای ریزش (ورود و شکست گره) مورد نیاز است.
هش ثابت یک تابع را به کار می گیرد formula_1 که یک مفهوم انتزاعی از فاصله بین کلیدها را تعریف می کند formula_2 و formula_3 ، که با فاصله جغرافیایی یا تاخیر شبکه ارتباطی ندارد. به هر گره یک کلید به نام "شناسه" آن (ID) اختصاص داده می شود. یک گره با شناسه formula_4 همه کلیدها را در اختیار دارد formula_5 برای کدام formula_4 نزدیکترین شناسه است که بر اساس اندازه گیری می شود formula_7 .
به عنوان مثال، Chord DHT از هش ثابت استفاده می کند، که گره ها را به عنوان نقاط روی یک دایره در نظر می گیرد، و formula_1 مسافتی است که در جهت عقربه های ساعت به دور دایره از آن طی می شود formula_2 به formula_3 . بنابراین، فضای کلید دایره‌ای به بخش‌های پیوسته تقسیم می‌شود که نقاط پایانی آن‌ها شناسه گره هستند. اگر formula_11 و formula_12 دو شناسه مجاور، با فاصله کمتر در جهت عقربه های ساعت از formula_11 به formula_12 ، سپس گره با شناسه formula_12 مالک تمام کلیدهایی است که بین آنها قرار می گیرند formula_11 و formula_12 .
در هش قرار ملاقات که هش با بالاترین وزن تصادفی (HRW) نیز نامیده می شود، همه مشتریان از یک تابع هش استفاده می کنند. formula_18 (انتخاب زودتر از زمان) برای مرتبط کردن یک کلید به یکی از "n" سرور موجود. هر مشتری فهرست یکسانی از شناسه‌های , یکی برای هر سرور. با توجه به کلید "k" ، یک کلاینت "n" وزن هش را محاسبه می کند. مشتری آن کلید را با سرور مربوط به بالاترین وزن هش برای آن کلید مرتبط می کند. سرور با شناسه formula_19 همه کلیدها را در اختیار دارد formula_5 که برای آن وزن هش formula_21 از وزن هش هر گره دیگری برای آن کلید بیشتر است.
هش با حفظ محلیت تضمین می کند که کلیدهای مشابه به اشیاء مشابه اختصاص داده می شوند. این می تواند اجرای کارآمدتر پرس و جوهای محدوده را امکان پذیر کند، با این حال، برخلاف استفاده از هش ثابت، اطمینان بیشتری وجود ندارد که کلیدها (و بنابراین بار) به طور تصادفی یکنواخت در فضای کلید و همتاهای شرکت کننده توزیع شده اند. پروتکل های DHT مانند Self-Cord و Oscar به چنین مسائلی می پردازند. Self-Cord کلیدهای شی را از شناسه‌های همتا جدا می‌کند و کلیدها را در امتداد حلقه با رویکردی آماری بر اساس الگوی هوش ازدحام دسته‌بندی می‌کند. مرتب‌سازی تضمین می‌کند که کلیدهای مشابه توسط گره‌های همسایه ذخیره می‌شوند و روش‌های کشف، از جمله پرس‌وجوهای محدوده ، می‌توانند در زمان لگاریتمی انجام شوند. اسکار یک شبکه جهان کوچک قابل کشتیرانی را بر اساس نمونه‌برداری تصادفی پیاده‌روی ایجاد می‌کند و همچنین زمان جستجوی لگاریتمی را تضمین می‌کند.
هر گره مجموعه ای از پیوندها را به گره های دیگر ( "همسایگان" یا جدول مسیریابی خود) حفظ می کند. این پیوندها با هم شبکه همپوشانی را تشکیل می دهند. یک گره همسایگان خود را بر اساس ساختار خاصی انتخاب می کند که توپولوژی شبکه نامیده می شود.
همه توپولوژی‌های DHT نوعی از اساسی‌ترین ویژگی را به اشتراک می‌گذارند: برای هر کلید ، هر گره یا شناسه گره‌ای دارد که دارای است یا پیوندی به گره‌ای دارد که شناسه گره آن به "نزدیک‌تر" است، از نظر فاصله فضای کلید تعریف‌شده در بالا. . سپس با استفاده از الگوریتم حریصانه زیر (که لزوماً بهینه جهانی نیست) یک پیام را به صاحب هر کلید هدایت کنید: در هر مرحله، پیام را به همسایه ای که شناسه آن به نزدیکتر است، ارسال کنید. وقتی چنین همسایه ای وجود ندارد، پس باید به نزدیکترین گره رسیده باشیم، که همان طور که در بالا تعریف شد، صاحب است. این سبک از مسیریابی گاهی اوقات مسیریابی مبتنی بر کلید نامیده می شود.
فراتر از صحت مسیریابی اولیه، دو محدودیت مهم در توپولوژی تضمین این است که حداکثر تعداد پرش ها در هر مسیر (طول مسیر) کم است، به طوری که درخواست ها به سرعت تکمیل می شوند. و اینکه حداکثر تعداد همسایگان هر گره (حداکثر درجه گره) کم است، به طوری که سربار تعمیر و نگهداری بیش از حد نباشد. البته داشتن مسیرهای کوتاهتر مستلزم درجه حداکثری بالاتر است. برخی از انتخاب های رایج برای حداکثر درجه و طول مسیر به شرح زیر است، که در آن تعداد گره ها در DHT با استفاده از نماد Big O است :
رایج ترین انتخاب، formula_22 طول درجه/مسیر، از نظر مبادله طول درجه/مسیر بهینه نیست، اما چنین توپولوژی‌هایی معمولاً انعطاف‌پذیری بیشتری را در انتخاب همسایگان فراهم می‌کنند. بسیاری از DHT ها از این انعطاف پذیری برای انتخاب همسایه هایی استفاده می کنند که از نظر تأخیر در شبکه فیزیکی زیربنایی نزدیک هستند. به طور کلی، همه DHT ها توپولوژی های شبکه جهان کوچک قابل کشتیرانی را ایجاد می کنند که طول مسیر را با درجه شبکه مقایسه می کند.
حداکثر طول مسیر ارتباط نزدیکی با قطر دارد : حداکثر تعداد پرش ها در هر کوتاه ترین مسیر بین گره ها. واضح است که طول مسیر شبکه در بدترین حالت حداقل به اندازه قطر آن است، بنابراین DHT ها توسط مبادله درجه/قطر که در نظریه گراف اساسی است، محدود می شوند. طول مسیر می تواند بیشتر از قطر باشد، زیرا الگوریتم مسیریابی حریصانه ممکن است کوتاه ترین مسیرها را پیدا نکند.
جدای از مسیریابی، الگوریتم‌های زیادی وجود دارد که از ساختار شبکه همپوشانی برای ارسال پیام به تمام گره‌ها یا زیر مجموعه‌ای از گره‌ها در یک DHT استفاده می‌کنند. این الگوریتم ها توسط برنامه های کاربردی برای انجام چندپخشی همپوشانی ، پرس و جوهای محدوده یا جمع آوری آمار استفاده می شود. دو سیستمی که مبتنی بر این رویکرد هستند، Structella، که flooding و پیمایش های تصادفی را بر روی یک پوشش Pastry پیاده‌سازی می‌کند، و DQ-DHT، که یک الگوریتم جستجوی پویا را بر روی یک شبکه آکورد پیاده‌سازی می‌کند.
به دلیل عدم تمرکز، تحمل خطا و مقیاس پذیری DHT ها، ذاتاً در برابر یک مهاجم متخاصم انعطاف پذیرتر از یک سیستم متمرکز هستند.
سیستم‌های باز برای ذخیره‌سازی داده‌های توزیع‌شده که در برابر مهاجمان خصمانه عظیم قوی هستند، امکان‌پذیر هستند.
یک سیستم DHT که به دقت طراحی شده است تا دارای تحمل خطای بیزانسی باشد، می‌تواند در برابر ضعف امنیتی، معروف به حمله Sybil ، که بیشتر طرح‌های DHT فعلی را تحت تأثیر قرار می‌دهد، دفاع کند. Whanau یک DHT است که برای مقاومت در برابر حملات Sybil طراحی شده است.  پتار میمونکوف، یکی از نویسندگان اصلی Kademlia ، راهی را برای دور زدن ضعف حمله Sybil با گنجاندن روابط اعتماد اجتماعی در طراحی سیستم پیشنهاد کرده است. سیستم جدید که با نام رمز Tonika یا با نام دامنه آن به عنوان 5ttt شناخته می شود، بر اساس طراحی الگوریتمی به نام "مسیریابی الکتریکی" و با همکاری ریاضیدان جاناتان کلنر ساخته شده است. مایمونکوف اکنون یک تلاش جامع برای اجرای این سیستم جدید را انجام داده است. با این حال، تحقیق در مورد دفاع موثر در برابر حملات Sybil به طور کلی یک سوال باز در نظر گرفته می شود، و انواع گسترده ای از دفاع های بالقوه هر ساله در کنفرانس های تحقیقاتی امنیتی برتر پیشنهاد می شود.
مهم‌ترین تفاوت‌هایی که در نمونه‌های عملی پیاده‌سازی DHT مشاهده می‌شود، حداقل شامل موارد زیر است: