موضوع مقاله: جدول درهم‌سازی توزیع‌شده | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # جدول درهم‌سازی توزیع‌شده | مقدمه: مزیت اصلی DHT این است که گره‌ها را می‌توان با حداقل کار در مورد توزیع مجدد کلیدها اضافه یا حذف کرد. | ## بخش 1: جدول درهم‌سازی توزیع‌شده | کلیدها شناسه‌های منحصربه‌فردی هستند که به مقادیر خاصی نگاشت می‌شوند، که به نوبه خود می‌توانند هر چیزی از آدرس‌ها، اسناد و داده‌های دلخواه باشند. مسئولیت حفظ نقشه‌برداری از کلیدها به مقادیر بین گره‌ها توزیع می‌شود، به گونه ای که تغییر در مجموعه شرکت کنندگان باعث ایجاد حداقل اختلال می‌شود. این به یک DHT اجازه می‌دهد تا به تعداد بسیار زیادی از گره‌ها گسترده شود و ورود، خروج و خرابی مداوم گره‌ها را مدیریت کند. DHTها زیرساختی را تشکیل می‌دهند که می‌تواند برای ساخت سرویس‌های پیچیده‌تر، مانند anycast، ذخیره‌سازی وب مشارکتی، سیستم‌های فایل توزیع شده، خدمات نام دامنه، پیام‌های فوری، چندپخشی و همچنین اشتراک گذاری فایل و سیستم‌های توزیع محتوا به صورت همتا استفاده شود. به ویژه، آنها از افزایش پهنای باند و ظرفیت هارد دیسک برای ارائه خدمات اشتراک فایل استفاده کردند. این سیستم‌ها در نحوه مکان‌یابی داده‌های ارائه شده توسط همتایان خود متفاوت بودند. Napster، که اولین سیستم تحویل محتوای P2P در مقیاس بزرگ بود، به یک سرور شاخص مرکزی نیاز داشت: هر گره، پس از پیوستن، فهرستی از فایل‌های محلی را به سرور ارسال می‌کرد که جستجوها را انجام می‌داد و درخواست‌ها را به گره‌هایی ارجاع می‌داد. Gnutella و شبکه‌های مشابه به یک مدل سیل پرس و جو منتقل شدنددر اصل، هر جستجو منجر به پخش پیامی برای هر ماشین دیگر در شبکه می‌شود. در حالی که اجتناب از یک نقطه شکست، این روش به‌طور قابل توجهی کمتر از Napster کارآمد بود. Freenet به‌طور کامل توزیع شده‌است، اما از یک مسیریابی مبتنی بر کلید اکتشافی استفاده می‌کند که در آن هر فایل با یک کلید مرتبط است، و فایل‌هایی با کلیدهای مشابه تمایل دارند در مجموعه‌ای از گره‌های مشابه خوشه شوند. پرس و جوها احتمالاً از طریق شبکه به چنین خوشه ای بدون نیاز به بازدید از همتایان زیادی هدایت می‌شوند. یک اشکال این است که، مانند Freenet, DHTها به جای جستجوی کلمه کلیدی، فقط مستقیماً از جستجوی تطابق دقیق پشتیبانی می‌کنند، اگرچه الگوریتم مسیریابی فری نت را می‌توان به هر نوع کلیدی تعمیم داد که در آن عملیات نزدیکی تعریف شود. پروژه ای به نام زیرساخت برای سیستم‌های اینترنتی مقاوم (Iris) با کمک مالی ۱۲ میلیون دلاری از بنیاد ملی علوم ایالات متحده در سال ۲۰۰۲ تأمین. ویژگی‌ها DHTها به‌طور مشخص بر ویژگی‌های زیر تأکید دارند: خودمختاری و عدم تمرکز: گره‌ها به‌طور جمعی سیستم را بدون هیچ هماهنگی مرکزی تشکیل می‌دهند. iiWas, 2010 مقیاس پذیری: سیستم باید حتی با هزاران یا میلیون‌ها گره به‌طور مؤثر عمل کند. یک تکنیک کلیدی که برای دستیابی به این اهداف مورد استفاده قرار می‌گیرد این است که هر گره نیاز به هماهنگی تنها با چند گره دیگر در سیستم دارد - معمولاً O (log n) از n شرکت کننده (به زیر مراجعه کنید) - به‌طوری که فقط مقدار محدودی از برای هر تغییر در عضویت باید کار انجام شود. هستند و به شرکت‌کنندگان اجازه می‌دهند ناشناس باقی بمانند، اگرچه این نسبت در بسیاری از سیستم‌های همتا به همتا (به ویژه اشتراک‌گذاری فایل) کمتر رایج است. یک طرح پارتیشن‌بندی فضای کلید، مالکیت این فضای کلیدی را بین گره‌های شرکت کننده تقسیم می‌کند. سپس یک شبکه همپوشانی گره‌ها را به هم متصل می‌کند و به آن‌ها اجازه می‌دهد تا صاحب هر کلیدی را در فضای کلید پیدا کنند. هنگامی که این اجزا در جای خود قرار گرفتند، استفاده معمولی از DHT برای ذخیره‌سازی و بازیابی ممکن است به شرح زیر انجام شود. برای نمایه سازی فایل با داده شده و در DHT، هش SHA-1 تولید می‌شود و یک کلید ۱۶۰ بیتی تولید می‌شود و یک پیام به هر گره ای که در DHT شرکت می‌کند ارسال می‌شود. پیام از طریق شبکه همپوشانی از گره ای به گره دیگر ارسال می‌شود تا زمانی که به گره تکی مسئول کلید که توسط پارتیشن‌بندی فضای کلید مشخص شده‌است برسد. سپس هر کلاینت دیگری می‌تواند محتویات فایل را با هش کردن مجدد برای تولید و درخواست از هر گره DHT برای یافتن داده‌های مرتبط با با پیام بازیابی کند. پارتیشن‌بندی فضای کلید و اجزای شبکه همپوشانی در زیر با هدف گرفتن ایده‌های اصلی مشترک در اکثر DHTها توضیح داده شده‌است. پارتیشن بندی فضای کلیدی اکثر DHT ها از نوعی هش ثابت یا هش قرار ملاقات برای نگاشت کلیدها به گره ها استفاده می کنند. | ## بخش 2: جدول درهم‌سازی توزیع‌شده | به نظر می رسد که این دو الگوریتم به‌طور مستقل و به‌طور همزمان برای حل مشکل جدول هش توزیع شده ابداع شده اند. هر دو هش ثابت و هش جابجاشونده این ویژگی اساسی را دارند که حذف یا افزودن یک گره تنها مجموعه کلیدهای متعلق به گره‌ها با شناسه‌های مجاور را تغییر می‌دهد و همه گره‌های دیگر را بی‌تأثیر می‌گذارد. این را با جدول هش سنتی مقایسه کنید که در آن اضافه یا حذف یک سطل باعث می‌شود تقریباً کل فضای کلید دوباره نقشه‌برداری شود. از آنجایی که هر تغییری در مالکیت معمولاً مربوط به حرکت پهنای باند فشرده اشیاء ذخیره شده در DHT از یک گره به گره دیگر است، به حداقل رساندن چنین سازماندهی مجدد برای پشتیبانی کارآمد از نرخ های بالای ریزش (ورود و شکست گره) مورد نیاز است. هش کردن مداوم هش ثابت یک تابع را به کار می گیرد که یک مفهوم انتزاعی از فاصله بین کلیدها را تعریف می کند و ، که با فاصله جغرافیایی یا تاخیر شبکه ارتباطی ندارد. یک گره با شناسه همه کلیدها را در اختیار دارد برای کدام نزدیکترین شناسه است که بر اساس اندازه گیری می شود . به عنوان مثال، Chord DHT از هش ثابت استفاده می کند، که گره ها را به عنوان نقاط روی یک دایره در نظر می گیرد، و مسافتی است که در جهت عقربه های ساعت به دور دایره از آن طی می شود به . بنابراین، فضای کلید دایره‌ای به بخش‌های پیوسته تقسیم می‌شود که نقاط پایانی آن‌ها شناسه گره هستند. اگر و دو شناسه مجاور، با فاصله کمتر در جهت عقربه های ساعت از به ، سپس گره با شناسه مالک تمام کلیدهایی است که بین آنها قرار می گیرند و . سرور با شناسه همه کلیدها را در اختیار دارد که برای آن وزن هش از وزن هش هر گره دیگری برای آن کلید بیشتر است. هش با حفظ محلیت هش با حفظ محلیت تضمین می کند که کلیدهای مشابه به اشیاء مشابه اختصاص داده می شوند. این می تواند اجرای کارآمدتر پرس و جوهای محدوده را امکان پذیر کند، با این حال، برخلاف استفاده از هش ثابت، اطمینان بیشتری وجود ندارد که کلیدها (و بنابراین بار) به‌طور تصادفی یکنواخت در فضای کلید و همتاهای شرکت کننده توزیع شده اند. Self-Cord کلیدهای شی را از شناسه‌های همتا جدا می‌کند و کلیدها را در امتداد حلقه با رویکردی آماری بر اساس الگوی هوش ازدحام دسته‌بندی می‌کند. مرتب‌سازی تضمین می‌کند که کلیدهای مشابه توسط گره‌های همسایه ذخیره می‌شوند و روش‌های کشف، از جمله پرس‌وجوهای محدوده ، می‌توانند در زمان لگاریتمی انجام شوند. اسکار یک شبکه جهان کوچک قابل کشتیرانی را بر اساس نمونه‌برداری تصادفی پیاده‌روی ایجاد می‌کند و همچنین زمان جستجوی لگاریتمی را تضمین می‌کند. شبکه همپوشانی هر گره مجموعه ای از پیوندها را به گره های دیگر ( همسایگان یا جدول مسیریابی خود) حفظ می کند. یک گره همسایگان خود را بر اساس ساختار خاصی انتخاب می کند که توپولوژی شبکه نامیده می شود. همه توپولوژی‌های DHT نوعی از اساسی‌ترین ویژگی را به اشتراک می‌گذارند: برای هر کلید ، هر گره یا شناسه گره‌ای دارد که دارای است یا پیوندی به گره‌ای دارد که شناسه گره آن به نزدیک‌تر است، از نظر فاصله فضای کلید تعریف‌شده در بالا. سپس با استفاده از الگوریتم حریصانه زیر (که لزوماً بهینه جهانی نیست) یک پیام را به صاحب هر کلید هدایت کنید: در هر مرحله، پیام را به همسایه ای که شناسه آن به نزدیکتر است، ارسال کنید. وقتی چنین همسایه ای وجود ندارد، پس باید به نزدیکترین گره رسیده باشیم، که همان‌طور که در بالا تعریف شد، صاحب است. فراتر از صحت مسیریابی اولیه، دو محدودیت مهم در توپولوژی تضمین این است که حداکثر تعداد پرش ها در هر مسیر (طول مسیر) کم است، به‌طوری که درخواست ها به سرعت تکمیل می شوند. و اینکه حداکثر تعداد همسایگان هر گره (حداکثر درجه گره) کم است، به‌طوری که سربار تعمیر و نگهداری بیش از حد نباشد. برخی از انتخاب های رایج برای حداکثر درجه و طول مسیر به شرح زیر است، که در آن تعداد گره ها در DHT با استفاده از نماد Big O است : حداکثر درجهحداکثر طول مسیراستفاده شده درتوجه داشته باشیدبدترین طول جستجو، با زمان جستجوی احتمالی بسیار کندترکورده (با درجه ثابت)پیاده سازی پیچیده تر، اما زمان جستجوی قابل قبولی را می توان با تعداد ثابتی از اتصالات یافتآکوردکادملیاشیرینیملیله کاریرایج ترین، اما نه بهینه (درجه/طول مسیر). آکورد ابتدایی ترین نسخه است، به نظر می رسد Kademlia محبوب ترین نسخه بهینه شده است (باید جستجوی متوسط بهبود یافته باشد)Koorde (با جستجوی بهینه)پیاده‌سازی پیچیده‌تر است، اما جستجوها ممکن است سریع‌تر باشند (بدترین حالت کمتری دارند)بدترین نیازهای ذخیره سازی محلی، با ارتباطات زیاد پس از اتصال یا قطع شدن هر گره رایج ترین انتخاب، طول درجه/مسیر، از نظر مبادله طول درجه/مسیر بهینه نیست، اما چنین توپولوژی‌هایی معمولاً انعطاف‌پذیری بیشتری را در انتخاب همسایگان فراهم می‌کنند. بسیاری از DHT ها از این انعطاف پذیری برای انتخاب همسایه هایی استفاده می کنند که از نظر تأخیر در شبکه فیزیکی زیربنایی نزدیک هستند. | ## بخش 3: جدول درهم‌سازی توزیع‌شده | به‌طور کلی، همه DHT ها توپولوژی های شبکه جهان کوچک قابل کشتیرانی را ایجاد می کنند که طول مسیر را با درجه شبکه مقایسه می کند. حداکثر طول مسیر ارتباط نزدیکی با قطر دارد : حداکثر تعداد پرش ها در هر کوتاه ترین مسیر بین گره ها. واضح است که طول مسیر شبکه در بدترین حالت حداقل به اندازه قطر آن است، بنابراین DHT ها توسط مبادله درجه/قطر که در نظریه گراف اساسی است، محدود می شوند. الگوریتم های شبکه های همپوشانی جدای از مسیریابی، الگوریتم‌های زیادی وجود دارد که از ساختار شبکه همپوشانی برای ارسال پیام به تمام گره‌ها یا زیر مجموعه‌ای از گره‌ها در یک DHT استفاده می‌کنند.. این الگوریتم ها توسط برنامه های کاربردی برای انجام چندپخشی همپوشانی ، پرس و جوهای محدوده یا جمع آوری آمار استفاده می شود. امنیت به دلیل عدم تمرکز، تحمل خطا و مقیاس پذیری DHT ها، ذاتاً در برابر یک مهاجم متخاصم انعطاف پذیرتر از یک سیستم متمرکز هستند. سیستم جدید که با نام رمز Tonika یا با نام دامنه آن به عنوان 5ttt شناخته می شود، بر اساس طراحی الگوریتمی به نام "مسیریابی الکتریکی" و با همکاری ریاضیدان جاناتان کلنر ساخته شده است. با این حال، تحقیق در مورد دفاع مؤثر در برابر حملات Sybil به‌طور کلی یک سؤال باز در نظر گرفته می شود، و انواع گسترده ای از دفاع های بالقوه هر ساله در کنفرانس های تحقیقاتی امنیتی برتر پیشنهاد می شود. پیاده سازی ها مهم‌ترین تفاوت‌هایی که در نمونه‌های عملی پیاده‌سازی DHT مشاهده می‌شود، حداقل شامل موارد زیر است: فضای آدرس، پارامتری از DHT است. در دنیای واقعی کلید می‌تواند هش محتوای یک فایل باشد تا هش نام فایل برای ارائه فضای ذخیره‌سازی آدرس‌پذیر محتوا ، به‌طوری که تغییر نام فایل مانع از یافتن آن توسط کاربران نشود. مثلا کلید می تواند گره باشد و داده‌های مرتبط می‌توانند نحوه تماس با این گره را توضیح دهند. این امکان انتشار اطلاعات حضوری را فراهم می کند و اغلب در برنامه های IM و غیره استفاده می شود. در ساده ترین حالت، فقط یک عدد تصادفی است که مستقیماً به عنوان کلید استفاده می شود (بنابراین در DHT 160 بیتی یک عدد 160 بیتی خواهد بود که معمولاً به صورت تصادفی انتخاب می شود. در برخی از DHT ها، انتشار شناسه گره ها نیز برای بهینه سازی عملیات DHT استفاده می شود. معمولاً به جای انتخاب فقط یک گره، الگوریتم‌های DHT دنیای واقعی انتخاب می‌کنند گره های مناسب، با یک پارامتر خاص اجرای DHT هستم. در برخی از طرح‌های DHT، گره‌ها موافقت می‌کنند که محدوده خاصی از فضای کلید را مدیریت کنند، که اندازه آن ممکن است به‌جای کدگذاری سخت، به صورت پویا انتخاب شود. برخی از DHT های پیشرفته مانند Kademlia ابتدا جستجوهای تکراری را از طریق DHT انجام می دهند تا مجموعه ای از گره های مناسب را انتخاب کرده و ارسال کنند.پیام‌ها فقط به آن گره‌ها ارسال کنید، بنابراین ترافیک بی‌فایده را به شدت کاهش می‌دهد، زیرا پیام‌های منتشر شده فقط به گره‌هایی ارسال می‌شوند که برای ذخیره‌سازی کلید مناسب به نظر می‌رسند. ; و جستجوهای مکرر فقط مجموعه کوچکی از گره ها را به جای کل DHT پوشش می دهند و ارسال بی فایده را کاهش می دهند. در چنین DHT ها، ارسال ازپیام‌های ممکن است فقط به عنوان بخشی از یک الگوریتم خوددرمانی رخ دهند: اگر یک گره هدف دریافت کندپیام ، اما معتقد است که خارج از محدوده کنترل شده خود است و یک گره نزدیکتر (از نظر فضای کلید DHT) شناخته شده است، پیام به آن گره ارسال می شود. البته، چنین الگوریتمی به گره ها نیاز دارد تا داده های حضور خود را در DHT منتشر کنند تا جستجوهای تکراری انجام شود. از آنجایی که در بیشتر ماشین‌ها ارسال پیام بسیار گران‌تر از دسترسی‌های جدول هش محلی است، منطقی است که بسیاری از پیام‌های مربوط به یک گره خاص را در یک دسته جمع کنیم. با فرض اینکه هر گره دارای یک دسته محلی است که حداکثر از آن تشکیل شده است ، روش بسته‌بندی به شرح زیر است. با استفاده از مرتب سازی سطلی ، می توان این کار را در داخل انجام داد ، که در آن تعداد گره ها در DHT است. هنگامی که چندین عملیات برای آدرس دادن یک کلید در یک دسته وجود دارد، دسته قبل از ارسال به بیرون متراکم می شود. به عنوان مثال، جستجوی چندگانه یک کلید را می توان به یک یا چند افزایش را می توان به یک عملیات افزودن کاهش داد. | ## جمع‌بندی | درخت مرکل : درختی که هر گره غیربرگی را با هش برچسب‌های گره‌های فرزندش برچسب‌گذاری کرده است.