امروز سه شنبه ، ۱۴۰۱/۰۳/۰۳
بدان

جدول هش توزیع شده: | Distributed hash table:

جدول هش توزیع شده:

یک جدول هش توزیع شده (DHT) یک سیستم توزیع شده است که سرویس جستجوی مشابه جدول هش را ارائه می دهد: جفت های مقدار-کلید در DHT ذخیره می شوند و هر گره شرکت کننده می تواند به طور موثر مقدار مرتبط با یک کلید داده شده را بازیابی کند.

مزیت اصلی DHT این است که می توان گره ها را با حداقل کار در توزیع مجدد کلیدها اضافه یا حذف کرد.

کلیدها شناسه های منحصر به فردی هستند که به مقادیر خاص ترسیم می شوند ، که به نوبه خود می تواند از آدرس ها ، اسناد ، داده های دلخواه باشد.

[1] مسئولیت حفظ نقشه برداری از کلیدها به مقادیر بین گره ها توزیع می شود ، به گونه ای که تغییر در مجموعه شرکت کنندگان باعث ایجاد حداقل اختلال می شود.

این به DHT اجازه می دهد تا تعداد بسیار زیادی گره را مقیاس بندی کند و ورود ، خروج و خرابی مداوم گره را کنترل کند.

DHT ها زیرساختی را تشکیل می دهند که می تواند برای ایجاد سرویسهای پیچیده تر از قبیل anycast ، caching وب تعاونی ، سیستم فایل توزیع شده ، خدمات نام دامنه ، پیام رسانی فوری ، چندپخشی و همچنین سیستم های توزیع محتوا و به اشتراک گذاری فایل های peer to-peer استفاده شود.

تاریخ:

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

به طور خاص ، آنها از افزایش پهنای باند و ظرفیت دیسک سخت برای ارائه سرویس اشتراک فایل استفاده کردند.

[2] این سیستم ها در نحوه قرارگیری داده های ارائه شده توسط همتایان خود متفاوت بودند.

Napster ، اولین سیستم تحویل محتوای P2P در مقیاس بزرگ ، به یک سرور فهرست مرکزی نیاز داشت: هر گره ، پس از پیوستن ، لیستی از فایلهای محلی را به سرور ارسال می کند ، که جستجوها را انجام می دهد و نمایش داده شد به گره هایی که نتایج.

این م componentلفه اصلی سیستم را در معرض حملات و دعاوی قرار داد.

Gnutella و شبکه های مشابه به یک مدل سیلابی پرس و جو منتقل شدند - در اصل ، هر جستجو منجر به پخش پیام برای هر دستگاه دیگری در شبکه می شود.

در حالی که از یک نقطه خرابی جلوگیری می شد ، این روش به طور قابل توجهی کمتر از ناپستر کارایی داشت.

نسخه های بعدی مشتری های Gnutella به یک مدل پرس و جو پویا منتقل شدند که بسیار کارآیی را بهبود بخشید.

[3] Freenet به طور کامل توزیع شده است ، اما از یک مسیریابی مبتنی بر کلید اکتشافی استفاده می کند که در آن هر پرونده با یک کلید مرتبط است و فایلهایی با کلیدهای مشابه تمایل دارند روی یک مجموعه مشابه از گره ها جمع شوند.

به احتمال زیاد س Quالات از طریق شبکه به چنین خوشه ای هدایت می شوند بدون اینکه نیازی به مراجعه به بسیاری از همتایان شما باشد.

[4] با این حال ، Freenet تضمین نمی کند داده ها پیدا شوند.

جداول هش توزیع شده به منظور دستیابی به عدم تمرکز Freenet و Gnutella و کارایی و نتایج تضمین شده Napster ، از یک مسیریابی مبتنی بر کلید ساختار یافته تر استفاده می کنند.

[5] در سال 2001 ، چهار سیستم - CAN ، [6] آكورد ، [7] شیرینی ، و ملیله - DHT ها را به عنوان یك موضوع پژوهشی محبوب مشتعل كردند.

پروژه ای به نام زیرساخت برای سیستم های انعطاف پذیر اینترنت (Iris) با کمک 12 میلیون دلار از بنیاد ملی علوم ایالات متحده در سال 2002 تأمین شد.

[8] محققان شامل سیلویا راتناسامی ، یون استویکا ، هاری بالاکریشنان و اسکات شنکر بودند.

[9] در خارج از دانشگاه ، فناوری DHT به عنوان م componentلفه BitTorrent و در شبکه توزیع محتوای مرجان پذیرفته شده است.

خواص:

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

خودمختاری و عدم تمرکز: گره ها بصورت جمعی و بدون هیچگونه هماهنگی مرکزی سیستم را تشکیل می دهند.

تحمل خطا: سیستم باید قابل اعتماد باشد (به تعبیری) حتی با اتصال پیوسته ، ترک و خرابی گره ها.

[10] مقیاس پذیری: سیستم باید حتی با هزاران یا میلیون ها گره به طور کارآمد کار کند.

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

برخی از طراحی های DHT به دنبال ایمنی در برابر شرکت کنندگان مخرب هستند [11] و اجازه می دهند تا شرکت کنندگان ناشناس بمانند ، هرچند این نسبت به بسیاری از سیستم های peer to-peer (مخصوصاً اشتراک فایل) معمول نیست. به P2P ناشناس مراجعه کنید.

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

ساختار:

ساختار DHT می تواند به چندین م .لفه اصلی تجزیه شود.

[12] [13] پایه یک فضای کلید انتزاعی است ، مانند مجموعه رشته های 160 بیتی.

یک طرح پارتیشن بندی فضای کلید ، مالکیت این فضای اصلی را در بین گره های شرکت کننده تقسیم می کند.

سپس یک شبکه overlay گره ها را به هم متصل می کند و به آنها اجازه می دهد صاحب هر کلید داده شده را در فضای کلید پیدا کنند.

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

فرض کنید keyspace مجموعه رشته های 160 بیتی است.

برای نمایه سازی یک پرونده با نام پرونده و داده های داده شده در DHT ، هش SHA-1 نام پرونده تولید می شود و یک کلید 160 بیتی k تولید می کند ، و یک پیام (k ، داده) برای هر گره شرکت کننده در DHT ارسال می شود.

پیام از گره به گره از طریق شبکه همپوشانی ارسال می شود تا زمانی که به گره منفرد مربوط به کلید k که توسط پارتیشن بندی فضای کلید مشخص شده است برسد.

سپس آن گره کلید و داده ها را ذخیره می کند.

سپس هر مشتری دیگری می تواند محتویات پرونده را با هش کردن مجدد نام پرونده برای تولید k و درخواست از هر گره DHT برای یافتن داده های مرتبط با k با یک پیام دریافت (k) بازیابی کند.

پیام مجدداً از طریق پوشش به گره مسئول k منتقل می شود ، که با داده های ذخیره شده پاسخ می دهد.

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