تماس با ما
 
بدان
 
امروز پنجشنبه ، ۱۳۹۹/۱۲/۰۷
 
کلیه مقالات

جداول هش توزیع شده ، قسمت اول

Distributed Hash Tables, Part I

در دنیای عدم تمرکز ، اخیراً جداول هش توزیع شده (DHT) تأثیر انقلابی دارند.

توپولوژی های بی نظم و موقت معماری همتا به نسل هم نسل ، توسط مجموعه ای از توپولوژی ها با نظم ظاهری ، خواص قابل اثبات و عملکرد عالی جایگزین شده اند.

دانش الگوریتم های DHT یکی از عناصر اصلی در پیشرفت های بعدی برنامه های توزیع شده است.

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

چند پیاده سازی اختصاصی نیز وجود دارد ، اما در حال حاضر هیچ یک به عنوان SDK در دسترس نیستند. بلکه در محصولات تجاری موجود گنجانده شده اند.

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

در واقع ، طرح های مختلف موجود همه در یک ماتریس چند بعدی جای می گیرند.

یکی را بردارید ، چند تغییر ایجاد کنید و در نهایت با یکی از موارد دیگر مواجه شوید.

DHT های تحقیقاتی موجود ، مانند آکورد ، Kademlia و Pastry ، از این رو نقطه آغازین برای توسعه طرح های سفارشی خود هستند.

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

برای بیان کامل طیف گزینه ها ، بیایید با یک طراحی اساسی شروع کنیم و سپس برای دستیابی به خواص مفید ، پیچیدگی اضافه کنیم.

اصولاً DHT عملکردهای جدول هش را انجام می دهد.

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

مقادیر لزوماً بر روی دیسک باقی نمی مانند ، اگرچه مطمئناً می توانید DHT را بالای یک جدول هش پایدار مانند Berkeley DB قرار دهید. و در واقع ، این کار انجام شده است.

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

برخلاف معماری های تکثیر موجود در پایگاه داده master / slave ، همه گره ها همتا هستند که می توانند آزادانه به شبکه بپیوندند و آن را ترک کنند.

با وجود آشفتگی آشکار تغییرات دوره ای تصادفی در عضویت در شبکه ، DHT ها تضمین های قابل قبولی در مورد عملکرد می دهند.

برای شروع بررسی طرح های DHT ، ما با یک لیست دایره ای و دارای پیوند دوگانه شروع می کنیم.

هر گره در لیست یک ماشین در شبکه است.

هر گره به گره های بعدی و قبلی موجود در لیست ، آدرس ماشین های دیگر اشاره می کند.

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

روش استفاده شده توسط Chord DHT برای تعیین گره بعدی به شرح زیر است:

به هر گره یک شناسه تصادفی منحصر به فرد از k بیت اختصاص دهید.

گره ها را در یک حلقه مرتب کنید تا شناسه ها به ترتیب در جهت عقربه های ساعت در اطراف حلقه قرار گیرند.

برای هر گره ، گره بعدی گره ای است که کمترین فاصله در جهت عقربه های ساعت باشد.

برای اکثر گره ها ، این گره ای است که شناسه آن نزدیکترین است اما هنوز از شناسه گره فعلی بیشتر است.

یک استثنا گره با بیشترین شناسه است که جانشین آن گره با کوچکترین شناسه است.

این معیار فاصله بطور دقیق تری در روش فاصله تعریف می شود (لیست 1).

هر گره خود یک جدول هش استاندارد است.

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

یک روش ساده برای تعیین اینکه کدام گره برای یک کلید خاص مناسب است (همان چیزی که آکورد استفاده می کند) همان روش تعیین جانشین یک ID گره خاص است.

ابتدا کلید را بردارید و آن را هش کنید تا یک کلید دقیقاً از k بیت تولید شود.

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

گره ای که پیدا می کنید گره مسئول ذخیره سازی و جستجوی آن کلید خاص است (لیست 2).

استفاده از هش برای تولید کلید مفید است زیرا هش ها به طور یکنواخت توزیع می شوند و کلیدهای مختلف به طور مساوی در تمام گره های شبکه توزیع می شوند.

این طراحی DHT ساده است اما کاملاً کافی است تا بتواند به یک جدول هش توزیع شده دسترسی پیدا کند.

با توجه به یک شبکه ثابت از گره ها با زمان مناسب ، می توانید با هر گره و کلیدی شروع کرده و گره مسئول آن کلید را پیدا کنید.

نکته مهمی که باید بخاطر بسپارید این است که اگرچه کد مثال تاکنون به نظر می رسد یک لیست کاملاً عادی و دارای پیوند مضاعف است ، اما این فقط شبیه سازی DHT است.

در DHT واقعی ، هر گره روی دستگاه متفاوتی قرار دارد و همه تماس ها با آنها باید از طریق نوعی پروتکل سوکت برقرار شود.

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

برای فعال کردن این ویژگی ، باید یک پروتکل join / ترک برای شبکه خود ایجاد کنیم.

اولین قدم در پروتکل Chord join جستجوی جانشین شناسه گره جدید با استفاده از پروتکل جستجوی عادی است.

گره جدید باید بین گره جانشین پیدا شده و سلف آن گره وارد شود.

گره جدید وظیفه بخشی از کلیدها را بر عهده دارد که گره قبلی به عهده آنها بوده است.

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

برگها بسیار ساده هستند. گره ترک کننده تمام اطلاعات ذخیره شده خود را در نسخه قبلی خود کپی می کند.

سلف سپس نشانگر گره بعدی خود را تغییر می دهد تا به جانشین گره ترک اشاره کند.

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

در یک لیست پیوندی عادی ، شما گره ای را حذف می کنید تا داده های موجود در آن حذف شود.

در DHT ، درج و حذف گره ها مستقل از درج و حذف داده ها است.

ممکن است مفید باشد که گره های DHT را شبیه سطل های تنظیم مجدد دوره ای مورد استفاده در پیاده سازی های جدول هش مداوم ، مانند Berkeley DB بدانید.

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

با این حال ، عملکرد وحشتناک است - O (n) با عملکرد مورد انتظار n / 2.

هر گره ای که عبور می کند نیاز به ارتباط با ماشین دیگری در شبکه دارد که بسته به نوع حمل و نقل انتخاب شده ، ممکن است نیاز به برقراری اتصال TCP / IP داشته باشد.

بنابراین ، n / 2 گره پیموده شده می تواند بسیار کند باشد.

برای دستیابی به عملکرد بهتر ، طراحی Chord یک لایه برای دسترسی به عملکرد O (ورود به سیستم) اضافه می کند.

به جای ذخیره یک اشاره گر در گره بعدی ، هر گره یک "جدول انگشت" را ذخیره می کند که حاوی آدرس k گره است.

فاصله بین شناسه گره فعلی و شناسه گره های موجود در جدول انگشت به طور تصاعدی افزایش می یابد.

هر گره پیموده شده در مسیر یک کلید خاص از نظر لگاریتمی نزدیکتر از آخرین گره است ، به طور کلی گره های O (log n) عبور می کنند.

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

جدول انگشتی به روز نشده به شرطی که هر گره دارای یک اشاره گر بعدی باشد ، جستجوها را نمی شکند ، اما جستجوها فقط در صورت درست بودن جدول انگشتی لگاریتمی هستند.

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

برای هر شکاف x ، جایی که x 1 تا k است ، انگشت [x] با گرفتن شناسه گره فعلی و جستجوی گره مسئول کلید (id + 2 (x-1)) حالت (2k) تعیین می شود (لیست 3 )

هنگام جستجوی جستجو ، اکنون k گره دارید که می توانید از هر hop به جای هر یک از آنها ، انتخاب کنید.

برای هر گره ای که از گره شروع بازدید می کنید ، ورودی جدول انگشت را دنبال می کنید که کمترین فاصله را با کلید دارد (لیست 4).

تاکنون ما نسخه اصلی طرح Chord DHT را کمابیش تعریف کردیم همانطور که توسط تیم MIT ابداع شد.

گرچه این فقط نوک کوه یخی در جهان DHT است.

بدون ایجاد عملکرد لگاریتمی و جستجوی تضمینی که وتر فراهم می کند ، می توان بسیاری از تغییرات را برای ایجاد خصوصیات متفاوت از آنچه در مقاله اصلی وتر توصیف شده است ، ایجاد کرد.

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

با استفاده از MIT Chord ، باید گره های O (log n) را برای همه k مورد موجود در جدول انگشت بزنید ، که می تواند به میزان قابل توجهی از ترافیک منجر شود.

اگر گره ای هنگام تماس با آن برای جستجوی آن ، گره دیگری را به جدول انگشت خود اضافه کند ، سودمند خواهد بود.

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

متأسفانه ، پیوندهای جدول انگشت در Chord یک جهته هستند زیرا متریک متقارن نیست.

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

یک راه حل برای این مشکل این است که معیار فاصله اضافی مدول Chord را با یکی مبتنی بر XOR جایگزین کنید.

فاصله بین دو گره ، A و B ، به عنوان XOR شناسه های گره تعریف می شود که به عنوان نمایش باینری یک عدد صحیح بدون امضا تفسیر می شود (لیست 5).

XOR به دلیل متقارن بودن ، یک معیار فاصله ای لذت بخش ایجاد می کند.

از آنجا که فاصله (A ، B) == فاصله (B ، A) ، برای هر دو گره ، اگر A در جدول انگشت B باشد ، B در جدول انگشت A است.

این بدان معناست که گره ها می توانند جداول انگشت خود را با ثبت آدرس گره هایی که از آنها س fingerال می کنند ، به روز کنند و میزان ترافیک بروزرسانی گره را به میزان قابل توجهی کاهش دهند.

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

در عوض ، هر زمان که روش جستجو فراخوانی می شود ، به سادگی به روز می کنید.

مسئله ای که در مورد طراحی ارائه شده تاکنون وجود دارد این است که مسیرهای رسیدن به یک گره مشخص شکننده هستند.

اگر گره های موجود در مسیر از همکاری امتناع ورزند ، جستجو متوقف می شود.

بین هر دو گره دقیقاً یک مسیر وجود دارد ، بنابراین مسیریابی در اطراف گره های شکسته غیرممکن است.

Kademlia DHT با تعریض میز انگشت این مسئله را حل می کند و به جای فقط یک عدد ، که در آن j به صورت جهانی برای کل شبکه تعریف شده است ، برای هر شیار میز انگشت سطری از منابع j وجود دارد.

اکنون j گزینه های مختلفی برای هر هاپ در دسترس است ، بنابراین در جایی وجود دارد j * log (n) مسیرهای ممکن.

کمتر از این وجود دارد ، هرچند که مسیرها بیشتر به هدف نزدیک می شوند.

اما ، تعداد مسیرهای ممکن احتمالاً بیشتر از 1 است ، بنابراین این یک پیشرفت است.

Kademlia فراتر رفته و گره های موجود در سطل را از نظر زمان ثبت شده سفارش می دهد.

به گره های قدیمی تر نمایش داده می شود و منابع جدید فقط در صورت عدم وجود گره های قدیمی به اندازه کافی اضافه می شوند.

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

درک این نکته مهم است که این خصوصیات مختلف با اجرای DHT خاصی ارتباط ندارند.

ما به تدریج یک طرح DHT را از ابتدا ایجاد کردیم ، آن را به چیزی شبیه آکورد توسعه دادیم ، سپس آن را تغییر دادیم تا بیشتر شبیه Kademlia باشد.

رویکردهای مختلف می تواند کم و بیش با هم مخلوط و مطابقت داشته باشد.

سطل های میز انگشتی شما بسته به اینکه از متر اضافی یا XOR برای اندازه گیری فاصله خود استفاده می کنید ، می توانند 1 شیار یا j شیار داشته باشند.

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

می توانید از چندین طرح DHT دیگر مانند Pastry ، OceanStore و Coral استفاده کنید.

شما همچنین می توانید با استفاده از ایده های خود طراحی مناسب را برای نیازهای خود طراحی کنید.

خودم ، چندین تغییر در یک طرح وتر پایه را برای افزودن خصوصیاتی مانند ناشناس بودن ، جستجوی مقاوم در برابر خطای بیزانس ، مسیریابی جغرافیایی و پخش کارآمد پیام ها برای ورود به شبکه ایجاد کرده ام.

انجام آن جالب و آسانتر از آن است که فکر می کنید.

اکنون که می دانید چگونه می توانید پیاده سازی DHT خود را ایجاد کنید ، احتمالاً از خود می پرسید که چه کارهای دیوانه ای را می توانید با این کد انجام دهید.

اگرچه احتمالاً برنامه های زیادی برای DHT وجود دارد که من هنوز به آنها فکر نکرده ام ، من می دانم که افراد در حال کار بر روی پروژه هایی مانند اشتراک فایل ، ایجاد یک دیسک سخت مشترک برای پشتیبان گیری از داده ها ، جایگزینی DNS با یک نام همتا سیستم وضوح ، چت مقیاس پذیر و بازی بدون سرور.

برای این مقاله ، من کدها را به یک برنامه کوچک سرگرم کننده متصل کرده ام که ممکن است مورد توجه خوانندگانی باشد که مصاحبه من را در وب سایت Linux Journal درباره Superworms همتا به همتا انجام داده اند (به منابع مراجعه کنید)

این برنامه یک اسکنر پورت توزیع شده است که نتایج را در DHT شبیه سازی شده ذخیره می کند (لیست 6).

با توجه به اجرای کاملاً کاربردی DHT ، این اسکریپت دارای خواص مفیدی است.

اول ، به چندین ماشین امکان می دهد تا در پویش گسترده اینترنت کمک کنند.

به این ترتیب ، تمام فعالیت های اسکن را نمی توان با یک ماشین مرتبط کرد.

علاوه بر این ، از اسکن اضافی جلوگیری می کند.

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

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

این برنامه ممکن است تا حدی موذی به نظر برسد ، اما نکته اینجاست که نوشتن با توجه به کتابخانه DHT پیش پا افتاده است.

همین روش را می توان در انواع دیگر پروژه های توزیع شده نیز به کار برد.

در این قسمت از سری دو بخشی ، ما در مورد تئوری ساخت DHT صحبت کردیم.

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