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

Kademlia: یک سیستم اطلاعاتی نظیر به نظیر مبتنی بر XOR Metric

Kademlia: A Peer-to-Peer Information System Based on the XOR Metric

چکیده:

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

سیستم ما با استفاده از یک توپولوژی متریک مبتنی بر XOR جدید که الگوریتم را ساده و اثبات ما را تسهیل می کند ، گره ها را جستجو و مکان یابی می کند.

توپولوژی خاصیتی دارد که هر پیامی که رد و بدل می شود ، اطلاعات مفیدی را برای انتقال یا تقویت می کند.

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

مقدمه:

این مقاله Kademlia ، جدول هش توزیع شده نظیر به نظیر (DHT) را توصیف می کند.

Kademlia دارای چندین ویژگی مطلوب است که به طور همزمان توسط هیچ DHT قبلی ارائه نشده است.

تعداد پیام های پیکربندی گره هایی را که باید برای یادگیری یکدیگر بفرستند ، به حداقل می رساند.

اطلاعات پیکربندی به عنوان عوارض جانبی جستجوی کلید به طور خودکار پخش می شود.

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

Kademlia از کوئری های موازی و ناهمزمان استفاده می کند تا از تاخیر زمانی در گره های خراب جلوگیری کند.

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

سرانجام ، چندین ویژگی مهم Kademlia را می توان با استفاده از تنها پیش فرض های ضعیف در توزیع های uptime به طور رسمی اثبات کرد (فرضیاتی که با اندازه گیری سیستم های موجود به peer تأیید می کنیم).

Kademlia رویکرد اساسی بسیاری از DHT ها را در پیش می گیرد.

کلیدها مقادیر مات و 160 بیتی هستند (به عنوان مثال ، هش SHA-1 برخی داده های بزرگتر).

رایانه های شرکت کننده هر یک دارای یک شناسه گره در فضای کلیدی 160 بیتی هستند.

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

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

بسیاری از مزایای کادملیا در نتیجه استفاده از معیار جدید XOR برای فاصله بین نقاط در فضای اصلی است.

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

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

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

هر ورودی در جدول انگشت گره Chord باید گره دقیق قبل از برخی از فاصله ها را در فضای ID ذخیره کند.

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

در مقابل ، Kademlia می تواند در هر بازه زمانی پرس و جو را به هر گره بفرستد ، به او این امکان را می دهد که مسیرها را بر اساس تأخیر انتخاب کند یا حتی پرس و جوهای ناهمگام موازی به چندین گره به همان اندازه مناسب ارسال کند.

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

در مقابل ، سیستم های دیگر از یک الگوریتم برای نزدیک شدن به ID هدف و دیگری از چند هاپ آخر استفاده می کنند.

از میان سیستم های موجود ، Kademlia بیشتر شبیه مرحله اول Pastry [1] است ، که (گرچه توسط نویسندگان به این روش توصیف نشده است) به طور پی در پی گره هایی را پیدا می کند که تقریباً نیمی از ID هدف توسط معیار XOR Kademlia است.

در مرحله دوم ، با این وجود ، Pastry معیارهای فاصله را به تفاوت عددی بین شناسه ها تغییر می دهد.

همچنین از نسخه دوم ، اختلاف عددی در تکثیر استفاده می کند.

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

2- شرح سیستم:

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

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

Kademlia به طور موثر گره ها را به عنوان برگهای یک درخت باینری رفتار می کند ، موقعیت هر گره با کوتاه ترین پیشوند منحصر به فرد شناسه آن تعیین می شود.

شکل 1 موقعیت گره را با پیشوند 0011 منحصر به فرد در یک درخت نمونه نشان می دهد.

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

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

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

در مثال گره 0011 ، زیرشاخه ها دایره می شوند و به ترتیب از همه گره ها با پیشوندهای 1 ، 01 ، 000 و 0010 تشکیل شده اند.

پروتکل Kademlia تضمین می کند که هر گره حداقل یک گره را در هر یک از شاخه های فرعی خود می داند ، اگر این subtree شامل یک گره باشد.

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

شکل 2 نمونه ای از گره 0011 را برای مکان یابی گره 1110 نشان می دهد با جستجوی پی در پی بهترین گره ای که می داند برای یافتن مخاطب در زیر شاخه های پایین و پایین است. سرانجام جستجو به گره مورد نظر همگرا می شود.

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

ما ابتدا مفهوم دقیقی از نزدیکی ID را تعریف می کنیم ، به ما امکان می دهد از جفت های ذخیره و جستجو (کلید ، مقدار) در k نزدیکترین گره های کلید صحبت کنیم.

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

2-1- XOR متریک:

هر گره Kademlia دارای یک شناسه گره 160 بیتی است.

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

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

کلیدها نیز شناسه های 160 بیتی هستند.

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

با توجه به دو شناسه 160 بیتی x و y ، کادملیا فاصله بین آنها را بصورت انحصاری بیتی یا (XOR) تعریف می کند که به عنوان یک عدد صحیح تفسیر می شود ، d (x، y) = x y.

ابتدا توجه می کنیم که XOR یک معیار معتبر ، البته غیر اقلیدسی است.

بدیهی است که d (x، x) = 0 ، d (x ، y) & gt؛ 0 اگر x & lt؛ & gt؛ y ، و ∀x ، y:

d (x ، y) = d (y ، x).

XOR ویژگی مثلث را نیز ارائه می دهد:

d (x ، y) + d (y ، z) ≥ d (x ، z).

ویژگی مثلث از این واقعیت پیروی می کند که d (x، y) ⊕ d (y، z) = d (x، z) و ∀a ≥ 0 ، b ≥ 0:

a + b ≥ a ⊕ b.

بعد توجه می کنیم که XOR مفهوم فاصله ضمنی در طرح مبتنی بر باینری درخت از سیستم را به دست می آورد.

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

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

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

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

مانند معیار Chord در جهت عقربه های ساعت ، XOR یک جهته است.

برای هر نقطه x و فاصله مشخص شده & & gt؛ 0 ، دقیقاً یک نقطه y وجود دارد به طوری که d (x، y) = ∆.

Unidirectionality تضمین می کند که همه جستجوهای یک کلید بدون توجه به گره مبدأ در یک مسیر مشابه قرار می گیرند.

بنابراین ، جفت سازی (کلید ، مقدار) در طول مسیر جستجو نقاط داغ را کاهش می دهد.

توپولوژی XOR نیز مانند Pastry و برخلاف Chord ، متقارن است (d (x، y) = d (y، x) برای همه x و y).

2-2- حالت گره:

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

برای هر 0 ≤ من & lt؛ 160 ، هر گره لیستی از سه آدرس (آدرس IP ، پورت UDP ، Node ID) را برای گره های فاصله بین 2i تا 2i + 1 از خودش نگه می دارد.

ما به این لیست ها k-buckets می گوییم.

هر سطل k بر اساس زمان آخرین دیده شدن مرتب می شود - گره ای که کمترین میزان مشاهده شده در سر دارد و اخیراً در دم دیده می شود.

برای مقادیر کوچک i ، سطلهای k معمولاً خالی خواهند بود (زیرا هیچ گره مناسبی وجود نخواهد داشت).

برای مقادیر بزرگ i ، لیست ها می توانند تا اندازه k بزرگ شوند ، جایی که k یک پارامتر تکثیر در سیستم است.

k به گونه ای انتخاب شده است که بعید به نظر می رسد گره های k داده شده در عرض یک ساعت از یکدیگر خراب شوند (به عنوان مثال k = 20)

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

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

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

اگر سطل k مناسب پر باشد ، در این صورت ، گیرنده کمترین گره k-bucket را برای تصمیم گیری درباره اینکه چه کاری انجام می دهد ، پینگ می کند.

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

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

k-buck ها به طور م aثر سیاست تخلیه ای را که حداقل اخیراً دیده شده اجرا می کنند ، با این تفاوت که گره های زنده هرگز از لیست حذف نمی شوند.

این اولویت برای تماس های قدیمی توسط تجزیه و تحلیل ما از داده های ردیابی گوتلا جمع آوری شده توسط Saroiu و دیگران هدایت می شود. [4]

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

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

با نگه داشتن قدیمی ترین تماس های زنده ، k-bets احتمال آنلاین ماندن گره های موجود در آنها را به حداکثر می رساند.

دومین مزیت k-buckets این است که آنها در برابر برخی از حملات DoS مقاومت می کنند.

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

گره های Kademlia فقط گره های قدیمی از سیستم خارج می شوند ، گره های جدید را در سطلهای k قرار می دهند.

2-3- پروتکل کادملیا:

پروتکل Kademlia از چهار RPC تشکیل شده است:

پینگ ، ذخیره ، یافتن گره و یافتن ارزش.

RPC پینگ یک گره را بررسی می کند تا ببیند آنلاین است.

store به یک گره دستور می دهد تا یک جفت (کلید ، مقدار) را برای بازیابی بعدی ذخیره کند.

find node یک شناسه 160 بیتی را به عنوان آرگومان می گیرد.

گیرنده RPC بازگردانی می کند (آدرس IP ، پورت UDP ، Node ID) برای گره های k که از نزدیکترین شناسه هدف می داند.

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

در هر صورت ، گیرنده RPC باید k مورد را برگرداند (مگر اینکه در همه سطل های k آن تعداد گره k کمتر باشد ، در این صورت هر گره ای را که از آن مطلع است برمی گرداند).

پیدا کردن مقدار مانند یافتن گره رفتار می کند — بازگرداندن (آدرس IP ، پورت UDP ، Node ID) سه برابر می شود - با یک استثنا.

اگر گیرنده RPC RPC ذخیره ای را برای کلید دریافت کرده باشد ، فقط مقدار ذخیره شده را برمی گرداند.

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

پینگ ها همچنین می توانند در پاسخ های RPC برای گیرنده RPC به صورت piggy پشتیبانی شوند تا اطمینان بیشتری از آدرس شبکه فرستنده بدست آورند.

مهمترین روشی که یک شرکت کننده Kademlia باید انجام دهد این است که نزدیکترین k را به برخی از ID های گره داده شده قرار دهد.

ما این روش را جستجوی گره می نامیم.

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

شروع کننده جستجو با انتخاب گره های α از نزدیکترین سطل غیر خالی k آن شروع می شود (یا اگر آن سطل تعداد ورودی های α کمتر از آن باشد ، نزدیکترین α گره های α را می شناسد).

سپس آغازگر RPC های گره موازی موازی و ناهمگام را به گره های α که انتخاب کرده ارسال می کند.

α یک پارامتر همزمانی در سطح سیستم است ، مانند 3.

در مرحله بازگشتی ، آغازگر گره find را دوباره به گره هایی که از RPC های قبلی یاد گرفته ارسال می کند.

(این بازگشت می تواند قبل از بازگشت تمام α های RPC قبلی شروع شود).

از گره های k که آغازگر نزدیکترین هدف را شنیده است ، α را انتخاب می کند که هنوز سeriال نشده است و گره یافتن RPC را به آنها ارسال می کند.

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

اگر یک دور از گره های یافتن نتواند گره ای را نزدیک به نزدیکترین چیزی که قبلاً دیده شده برگرداند ، آغازگر گره یافتن را به همه k نزدیکترین گره هایی که قبلاً پرس و جو نکرده است ، ارسال می کند.

وقتی که آغازگر از نزدیکترین k گره هایی که دیده است سeriال کرده و پاسخ هایی را دریافت کرده است ، خاتمه می یابد.

وقتی α = 1 ، الگوریتم جستجو از نظر هزینه پیام و تأخیر در شناسایی گره های خراب ، شبیه Chord است.

با این حال ، Kademlia می تواند تاخیر کمتری را طی کند زیرا دارای انعطاف پذیری در انتخاب هر یک از k گره ها برای ارسال درخواست به آن است.

بیشتر عملیات از نظر روش جستجوی بالا اجرا می شوند.

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

بعلاوه ، هر گره برای زنده نگه داشتن آنها جفت (کلید ، مقدار) را مجددا منتشر می کند ، همانطور که بعداً در بخش 2.5 توضیح داده شد.

این اطمینان از ماندگاری (همانطور که در طرح اثبات خود نشان می دهیم) جفت (کلید ، مقدار) با احتمال بسیار بالا را تضمین می کند.

برای برنامه فعلی Kademlia (اشتراک فایل) ، ما همچنین به ناشر اصلی یک جفت (کلید ، مقدار) نیاز داریم که هر 24 ساعت آن را دوباره منتشر کند.

در غیر این صورت ، جفت (کلید ، مقدار) 24 ساعت پس از انتشار منقضی می شود ، بنابراین اطلاعات شاخص بیات در سیستم محدود می شود.

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

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

با این حال ، جستجوی مقدار به جای یافتن RPC گره از مقدار استفاده می کند.

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

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

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

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

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

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

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

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

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

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

شما w را در سطل مناسب k قرار دهید.

u سپس جستجوی گره را برای شناسه گره خود انجام می دهد.

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

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

2-4 جدول مسیریابی:

ساختار جدول مسیریابی اصلی Kademlia با توجه به پروتکل کاملاً رو به جلو است ، اگرچه برای اداره درختان بسیار ناموزون به ظرافت کمی نیاز است.

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

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

پیشوند موقعیت سطل k در درخت باینری است.

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

گره ها در درخت مسیریاب ، در صورت لزوم به صورت پویا اختصاص می یابند.

شکل 4 روند کار را نشان می دهد.

در ابتدا ، درخت مسیریابی گره u دارای یک گره است - یک سطل k که کل فضای شناسایی را پوشش می دهد.

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

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

در غیر این صورت ، اگر محدوده k-bucket شامل شناسه گره خودتان باشد ، سطل به دو سطل جدید تقسیم می شود ، مطالب قدیمی بین این دو تقسیم می شود و تلاش برای درج مجدد انجام می شود.

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

یک عارضه در درختان بسیار نامتعادل ایجاد می شود.

فرض کنید گره u به سیستم می پیوندد و تنها گره ای است که شناسه آن 000 شروع می شود.

بیشتر فرض کنید که این سیستم در حال حاضر بیش از k گره با پیشوند 001 دارد.

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

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

شکل 5 این تقسیمات اضافی را نشان می دهد.

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

2-5 انتشار مجدد کلید کارآمد:

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

در غیر این صورت ، دو پدیده ممکن است باعث شود که جستجو برای کلیدهای معتبر از کار بیفتد.

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

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

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

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

پیاده سازی ساده لوحانه این استراتژی به پیامهای زیادی نیاز دارد - هر كدام از گرههای k كه یك جفت مقدار كلید را ذخیره می كنند ، هر ساعت یك جستجوی گره را دنبال می كنند و RPC های فروشگاه k - 1 را دنبال می كنند.

خوشبختانه روند بازنشر می تواند به شدت بهینه شود.

اول ، هنگامی که یک گره RPC فروشگاهی را برای یک جفت مقدار کلید معین دریافت می کند ، فرض می کند که RPC به نزدیکترین گره k - 1 دیگر نیز صادر شده باشد ، بنابراین گیرنده در ساعت بعدی جفت مقدار کلید را مجددا منتشر نمی کند.

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

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

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

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

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

برای دیدن اینکه چرا جستجوی گره پس از تازه سازی سطل ها در زیر درخت با اندازه ≥ k غیرضروری است ، لازم است دو مورد را در نظر بگیرید.

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

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

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

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

گره های موجود ، با بهره گیری مشابه از دانش کامل از زیرشاخه های اطراف خود ، می دانند که گره جدید کدام جفت ارزش-کلید را ذخیره می کند.

بنابراین هر گره ای که از یک گره جدید یاد می گیرد ، RPC های ذخیره را برای انتقال جفت های مربوط به مقدار کلید به گره جدید ایجاد می کند.

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

3- طرح اثبات:

برای نشان دادن عملکرد مناسب سیستم ما ، باید ثابت کنیم که اکثر عملیات برای n ثانیه ثابت کوچک c زمان می برد و جستجوی (کلید ، مقدار) یک کلید ذخیره شده در سیستم را با احتمال قریب به اتفاق برمی گرداند.

ما با برخی تعاریف شروع می کنیم.

برای یک سطل k که محدوده فاصله را پوشش می دهد [2i ، 2i + 1) ، شاخص سطل را i تعیین کنید.

عمق ، گره گره را 160 - i تعریف کنید ، جایی که i کوچکترین شاخص سطل غیرخالی است.

ارتفاع سطل y گره را در گره x مشخص کنید تا شاخص سطلی باشد که x در آن y منهای شاخص کمترین سطل خالی x قرار می گیرد.

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

بنابراین با احتمال قریب به اتفاق ارتفاع هر گره داده شده در یک ثابت log n برای یک سیستم با n گره خواهد بود.

بعلاوه ، ارتفاع سطل نزدیکترین گره به یک ID در نزدیکترین گره احتمالاً در یک ثابت log k خواهد بود.

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

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

فرض کنید نزدیکترین گره به شناسه هدف دارای عمق h باشد.

اگر هیچ کدام از مهمترین سطلهای k این گره خالی نباشد ، روش جستجو گره ای را در هر مرحله به اندازه نصف نزدیک (یا بهتر بگوییم فاصله آن یک بیت کوتاه تر باشد) پیدا می کند و بنابراین گره را در مراحل h - log k بالا می آورید. .

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

در این حالت ، مراحل نهایی فاصله را به نصف کاهش نمی دهد.

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

بنابراین ، الگوریتم جستجوی همیشه نزدیکترین گره را در مراحل h - log k برمی گرداند.

علاوه بر این ، هنگامی که نزدیکترین گره پیدا شد ، همزمانی از α به k تغییر می یابد.

تعداد مراحل برای یافتن k - 1 نزدیکترین گره نمی تواند بیش از ارتفاع سطل نزدیکترین گره در kth-نزدیکترین گره باشد ، که بعید است بیش از یک ثابت به علاوه log k باشد.

برای اثبات درستی نامعتبر ، ابتدا اثرات تازه سازی سطل را در صورت عدم تغییر حفظ کنید.

بعد از تازه سازی ، یک سطل یا حاوی k گره معتبر است یا در صورت وجود تعداد کمتر از k ، هر گره دیگری را در محدوده خود دارد.

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

بنابراین ، تنها راه نقض نامتغیر این است که k + 1 یا بیشتر گره در محدوده یک سطل خاص وجود داشته باشد ، و k واقع در سطل وجود داشته باشد ، همه بدون جستجوی مداخله یا تازه سازی از کار بیفتند.

با این حال ، k دقیقاً برای احتمال خرابی همزمان در عرض یک ساعت (حداکثر زمان تازه سازی) انتخاب شد تا کم باشد.

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

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

علاوه بر این ، حتی اگر نامحدود برای یک سطل در یک گره از کار بیفتد ، این فقط بر زمان اجرا (با افزودن یک هاپ به برخی از جستجوها) تأثیر خواهد گذاشت ، نه بر صحت جستجوی گره.

برای از کار افتادن یک جستجوی ، k node در مسیر جستجو باید هر n گره را در یک سطل از دست بدهند ، بدون جستجوی مداخله یا تازه سازی.

اگر سطل های گره های مختلف هیچگونه همپوشانی نداشته باشند ، این امر با احتمال 2 − k2 اتفاق می افتد.

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

اکنون بازیابی یک جفت (کلید ، مقدار) را در نظر می گیریم.

هنگامی که یک جفت (کلید ، مقدار) منتشر می شود ، در گره های k ، نزدیکترین کلید قرار می گیرد.

همچنین هر ساعت دوباره منتشر می شود.

از آنجا که حتی گره های جدید (کمترین قابل اعتماد) احتمال 1/2 ماندگاری یک ساعت را دارند ، پس از یک ساعت جفت (کلید ، مقدار) همچنان در یکی از گره های k نزدیک به کلید با احتمال 1 - 2 − k وجود دارد .

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

مسلماً ، اگر نزدیکترین گره k به یک کلید از کار بیفتد و جفت (کلید ، مقدار) در جای دیگری ذخیره نشود ، Kademlia در ذخیره این جفت شکست خواهد خورد و بنابراین کلید را گم می کند.

4- یادداشت های اجرایی:

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

4-1 حسابداری تماس بهینه:

ویژگی اصلی مورد نظر k-buckets ارائه بررسی LRU و تخلیه مخاطبین نامعتبر بدون افتادن هیچگونه مخاطب معتبری است.

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

پینگ بررسی می کند که آیا حداقل تماسی که اخیراً در سطل k استفاده شده است همچنان معتبر است یا خیر.

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

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

برای کاهش ترافیک ، کادملیا جستجوی مخاطبین را به تأخیر می اندازد تا زمانی که پیام های مفیدی برای ارسال آنها داشته باشد.

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

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

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

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

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

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

وقتی مخاطبی نتواند به 5 RPC پشت سر هم پاسخ دهد ، قدیمی محسوب می شود.

اگر یک سطل k پر نشده باشد یا حافظه نهانگاه آن خالی باشد ، Kademlia فقط مخاطب کهنه را پرچم گذاری می کند تا اینکه آنها را حذف کند.

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

4-2 جستجوی سریع:

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

از نظر مفهومی ، این کار با در نظر گرفتن بیت های ID در یک بار به جای فقط یک بیت در یک زمان انجام می شود.

همانطور که قبلا توضیح داده شد ، تعداد مورد انتظار برای هاپ در هر جستجو log2 n است.

با افزایش اندازه جدول مسیریابی به سطل های انتظار 2b log2b n k ، می توانیم تعداد هاپ های مورد انتظار را به log2b n کاهش دهیم.

بخش 2.4 توضیح می دهد که چگونه گره Kademlia سطل k را هنگامی که سطل پر است و دامنه آن شامل شناسه خود گره است ، تقسیم می کند.

با این حال ، اجرا همچنین محدوده هایی را که شامل ID گره نیستند ، تقسیم می کند ، تا b - 1 سطح.

برای مثال ، اگر b = 2 باشد ، نیمی از فضای ID که شامل ID گره نیست ، یک بار تقسیم می شود (به دو دامنه). اگر b = 3 باشد ، در دو سطح حداکثر به چهار محدوده تقسیم می شود ، و غیره

قانون تقسیم کلی این است که اگر دامنه حاوی شناسه خود گره باشد یا عمق d سطل k در درخت مسیریاب d! ≡ 0 (mod b) یک سطل k کامل را تقسیم می کند.

(عمق فقط طول پیشوند مشترک برای همه گره های محدوده k-bucket است.) اجرای فعلی از b = 5 استفاده می کند.

اگرچه مسیریابی مبتنی بر XOR شبیه الگوریتم های مسیریابی مرحله اول Pastry [1] ، Tapestry [2] و الگوریتم جستجوی توزیع شده Plaxton است [3] ، هر سه این موارد پیچیده تر می شوند و به b & gt؛ 1

بدون توپولوژی XOR ، نیاز به یک ساختار الگوریتمی اضافی برای کشف هدف در گره هایی است که پیشوند مشابهی دارند اما در رقم بعدی بیت بیت متفاوت است.

هر سه الگوریتم این مسئله را به روش های مختلف حل می کنند ، هرکدام اشکالات خاص خود را دارند. همه آنها به جداول مسیریابی ثانویه با اندازه O (2b) علاوه بر جداول اصلی اندازه O (2b log2b n) نیاز دارند.

این کار هزینه بوت استراپینگ و نگهداری را افزایش می دهد ، پروتکل ها را پیچیده می کند و برای Pastry and Tapestry تجزیه و تحلیل صحیح درستی و سازگاری را پیچیده یا از آن جلوگیری می کند.

Plaxton دارای اثبات است ، اما سیستم برای محیط های بسیار مستعد خطا مانند شبکه های peer-topeer کمتر آماده شده است.

5- خلاصه:

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

علاوه بر این ، Kademlia یک پارامتر همزمانی ، α را معرفی می کند که به شما اجازه می دهد تا یک عامل ثابت در پهنای باند را برای انتخاب هاپ ناهمزمان کم تأخیر و بازیابی خطای بدون تاخیر تجارت کنید.

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