بخشی از مقاله
بهبود جستجو در شبکه ي نظير به نظير Chord با استفاده از جدول کش مکان
چکيده
شبکه هاي نظير به نظير، يکسري شبکه هاي منطقي متشکل از گره هاي مستقل هستند. اين نوع شبکه ها در بالاي شبکه هاي فيزيکي تشکيل مي شوند و از اين جهت به آنها، شبکه هاي روئين نيز گفته مي شود. وظيفه ي اصلي شبکه ي نظير به نظير، جستجوي کارآمد داده است ؛ با کليد مشخصي ، گرهي که شئ متناظر را ذخيره کرده است ، پيدا مي شود. بسياري از پروتکل هاي روئين ساختاريافته ، نظير Chord براي ذخيره ي زوج هاي کليد مقدار، از هش يکنواخت در جداول هش توزيع شده استفاده مي کنند. اين نوع هش ، کليدها را بطور يکنواخت و يکسان در ميان گره هاي شبکه توزيع مي کند. جستجوي داده در يک شبکه ي N گرهي ، با احتمال بالا به (O(logN ايستگاه ارتباطي نياز دارد. در اين مقاله ، در مورد سيستم Chord و نحوه ي انجام جستجو در آن صحبت مي کنيم و روش پيشنهادي خود را براي بهبود محليت جستجو بيان مي کنيم .
کليد واژه - جانشين ، جدول انگشتي ، پرسجو، نظير به نظير، گره .
١- مقدمه
با گسترش سريع و کاربرد وسيع کامپيوتر و تکنولوژي ارتباطات ، تقاضاهاي زيادي در زمينه ي ارتباطات پديدار گشته است که نقطه ضعف مدل ارتباطي و سنتي کلاينت .سرور را نشان 1 مي دهد؛ در اين مدل ، وجود سرور بعنوان نقطه ي شکست واحد و خرابي آن ، منجر به از کارافتادگي ٢ کل سيستم خواهد شد.
خوشبختانه ، مدل نظير به نظير پديدار شد.
نظير به نظير، نوعي سيستم توزيع شده است که گره هاي سيستم ، منابع شان را به اشتراک مي گذارند و زيرساخت را با هم مديريت مي کنند. سيستم نظير به نظير، از مسأله ي گلوگاه ٣ جلوگيري مي کند و مزاياي مقياس پذيري و موازنه ي بار را دارد که همه ي آنها، توسط مدل سنتي شبکه پشتيباني نمي شود.
در سيستم نظير به نظير، شبکه ي نظير به نظير ساخت يافته ، مبتني بر هش است و قابليت هاي مقياس پذيري و اطمينان پذيري را ارائه مي کند [١,٢].
Chord، سرويس جستجوي توزيع شده ي کارآمدي سيستم است که مبتني بر پروتکل Chord است . اين سيستم ، پنج نوع عمليات را پشتيباني مي کند: الحاق و خروج گره هاي Chord، درج و آپديت و جستجوي سرويس دهنده ي زوج هاي کليد مقدار. تمام اين عمليات اصلي ، توسط پروتکل Chord ارائه مي شود [٣].
پروتکل Chord، تنها يک عمل را پشتيباني مي کند: کليد مشخصي را به يک گره نگاشت مي کند. بسته به کاربرد استفاده از Chord، آن گره مي تواند مسئول ذخيره سازي مقدار متناظر با کليد باشد. Chord يک نوع هش يکنواخت ٤ [٤] را براي تخصيص کليدها به گره هاي Chord استفاده مي کند. هش يکنواخت به موازنه ي بار٥ تمايل دارد، چون هر گره تعداد تقريبا يکساني کليد را دريافت مي کند و جابجايي نسبتا کم کليدها را (وقتي گره ها به سيستم مي پيوندند و از سيستم جدا مي شوند) سبب مي شود.
کارهاي قبلي انجام شده در رابطه با هش يکنواخت ، فرض مي کردند که گره ها از اکثر گره هاي ديگر سيستم آگاه بودند که ، اين امر، مانع مقياس پذيري هش يکنواخت به تعداد زياد گره ها [٤]. در مقابل ، هر گره ي Chord نياز به اطلاعات مسيريابي ٦ بود
تعداد کمي از ساير گره ها دارد. بدليل اينکه ، جدول مسيريابي توزيع مي شود، يک گره ، عمل هش را از طريق برقراري ارتباط با تعداد کمي از ساير گره ها حل مي کند. در حالت پايدار و در يک سيستم N گرهي ، هر گره ، اطلاعات (O(logN گره ي ديگر را نگهداري مي کند و تمام جستجوها را از طريق (O(logN پيام به ساير گره ها، انجام مي دهد. Chord اطلاعات مسيريابي اش را
هنگامي که گره ها به سيستم مي پيوندند و سيستم را ترک مي کنند، تعمير و نگهداري مي کند؛ به احتمال زياد، هر يک از چنين رويدادي به حداکثر (O(log2N پيام منجر مي شود.
سه ويژگي که Chord را از بسياري از پروتکل هاي جستجوي نظير به نظير متمايز مي کند عبارت است از : سادگي ، صحت و درستي ٧ عملکرد و کارآيي [٥,٦]. عملکرد Chord ساده است ، کليد را از طريق دنباله اي از (O(logN گره ي ديگر به سمت مقصد مسيريابي مي کند. گره ي Chord براي مسيريابي کارآ، به اطلاعات (O(logN گره ي ديگر نياز دارد، اما زماني که اطلاعات آپديت نيست کارآيي کاهش مي يابد. اين موضوع عملا مهم است ، زيرا گره ها داوطلبانه به سيستم مي پيوندند و سيستم را ترک مي کنند. تنها يک تکه اطلاعات در هر گره نياز است صحيح باشد تا Chord درستي مسيريابي (هر چند کند) پرسجوها را تضمين کند؛ Chord الگوريتم ساده اي براي تعمير و نگهداري اين اطلاعات در محيط پويا دارد.
ادامه ي اين مقاله به اينصورت ترتيب داده شده است : در بخش ٢، در مورد هش يکنواخت و دليل استفاده از آن در سيستم Chord صحبت شده است . بخش ٣، به مکانيزم جستجوي ساده ي گره ي محتوي کليد مورد نظر اشاره مي کند.
در بخش ٤، مکانيزم بهينه ي جستجوي کليد را شرح مي دهيم .
در بخش ٥، روش پيشنهادي خود را براي بهبود جستجوهاي سيستم Chord را ارائه خواهيم نمود. در انتهاي مقاله ، نتيجه گيري خود از اين مقاله را بيان مي کنيم .
٢- هش يکنواخت
نقاط داغ ، هر زمان که تعداد زيادي کلاينت مي خواهند به طور همزمان به داده اي از سرور واحدي دسترسي داشته باشند، رخ مي دهد. اگر سايت براي مواجهه با تمام اين کلاينت هاي همزمان مهيا نشده است ، سرويس ممکن است افت کند يا از کار بيفتد.
بسياري از ما پديده ي نقطه ي داغ را در فضاي وب تجربه کرده ايم . يک وب سايت مي تواند بطور ناگهاني خيلي محبوب شود و درخواست هاي بيشماري را در مدت زمان نسبتا کمتري نسبت به مدت زماني که اساسا براي مديريتش پيکربندي و تعريف شده بود، دريافت کند. در واقع ، سايت ممکن است درخواست هاي خيلي زيادي را دريافت کند که باعث خفقانش شود و معمولا آن را غيرقابل استفاده مي سازد. علاوه بر غيرقابل دسترس کردن سايت ، ترافيک سنگين به سمت يک مکان ، مي تواند شبکه ي نزديک آن را دچار ازدحام کند (ايجاد اختلال همراه با ترافيک در سايت هاي مجاور) [٤].
در سيستم Chord نيز، هش يکنواخت با توزيع يکنواخت کليدها در ميان گره هاي حاضر در شبکه ، مانع بروز نقاط داغ مي شود. تابع هش يکنواخت با استفاده از يک تابع هش پايه مثل
١-SHA، به هر گره و هر کليد، يک شناسه ي m بيتي تخصيص مي دهد. شناسه ي گره ، از طريق هش آدرس IPي گره انتخاب مي شود، در حالي که شناسه ي کليد، توسط هش کليد توليد مي شود. طول شناسه (m) بايستي به اندازه کافي بزرگ باشد تا احتمال هش دو گره يا دو کليد به شناسه ي يکسان ناچيز باشد.
هش يکنواخت به اينصورت کليدها را به گره ها تخصيص مي دهد که ، شناسه ها در يک حلقه ي شناسه ي ٨ به پيمانه ي m٢ مرتب مي شوند. کليد k به اولين گرهي که شناسه ي آن گره ، برابر با شناسه ي k يا پس از شناسه ي k در فضاي شناسه مي آيد تخصيص داده مي شود. اين گره ، گره ي جانشين ٩ کليد k ناميده مي شود و با (successor(k نشان مي دهيم . اگر شناسه ها بصورت حلقه اي از ٠ تا ١-m٢ نمايش داده شوند، در اينصورت (successor(k، اولين گره در جهت حرکت عقربه هاي ساعت از k است .
بطور دقيقتر، در سيستم Chord عمل ذخيره و بازيابي داده مي تواند به اين صورت باشد: فضاي کليدي را در نظر بگيريد که حاوي کليدهايي در دامنه ي (٢١٦٠ ,٠] است . براي ذخيره ي يک فايل (که نام مشخصي دارد) در جدول هش توزيع شده ، هش
١-SHA ي نام فايل ، محاسبه مي شود، کليد ١٦٠ بيتي توليد مي شود و پيام (insert(key, value به گره ي دلخواهي از شبکه ارسال مي شود (value، محتواي فايل است ). اين پيام ، گره به گره ، از طريق شبکه ي روئين فوروارد مي شود تا پيام ، به گره ي مسؤول کليد (يا همان ، گره ي جانشين ) برسد. در اين گره ، زوج (key, value) ذخيره خواهد شد. اکنون ، هر کلاينت با پيام (lookup(key مي تواند محتويات فايل را، توسط هش مجدد نام فايل (براي توليد کليد) و درخواست از هر گره براي يافتن مقدار متناظر با کليد، بازيابي کند. اين پيام ، مجددا از طريق شبکه ي روئين به سمت گره ي مسؤول کليد مسيريابي مي شود که با زوج ذخيره شده ي کليد مقدار به کلاينت درخواست کننده پاسخ خواهد داد [٧].
شکل ١، حلقه ي شناسه ي با ٦= m را نشان مي دهد. اين حلقه ي شناسه ، ١٠ گره دارد و ٥ کليد را ذخيره مي کند.
جانشين شناسه ي ١٠، در جهت حرکت عقربه هاي ساعت ، گره ي ١٤ است ، بنابراين کليد ١٠ در گره ي ١٤ قرار داده خواهد شد. به همين نحو، کليد ٢٤ و کليد ٣٠ در گره ي ٣٢، کليد ٣٨ در گره ي ٣٨ و کليد ٥٤ در گره ي ٥٦ قرار داده خواهد شد.
از سوي ديگر، هش يکنواخت طراحي شده است تا به گره ها اجازه دهد بدون اختلال به شبکه وارد و از آن خارج شوند.
بمنظور حفظ و ادامه ي نگاشت هش يکنواخت ، وقتي يک گره (n) به شبکه مي پيوندد، کليدهاي مشخصي که قبلا به جانشين n تخصيص داده شده اند اکنون به گره ي n تخصيص داده مي شوند. در مثال بالا، اگر گرهي با شناسه ي ٢٦ براي الحاق وجود داشت ، اين گره ، کليد با شناسه ي ٢٤ را از گره ي با شناسه ي ٣٢ تصرف خواهد کرد. وقتي گره ي n شبکه را ترک مي کند، تمام کليدهاي تخصيص يافته اش مجددا به جانشين گره ي n تخصيص داده مي شود.
٣- مکانيابي ساده ي گره ي ذخيره کننده ي کليد
اين بخش يک الگوريتم ساده اما کند جستجوي Chord را شرح مي دهد. در بخش بعد شرح خواهيم داد که چگونه اين الگوريتم را براي افزايش کارآيي جستجو توسعه خواهيم .
هر گره ي موجود در Chord فقط نياز دارد که بداند چگونه با گره ي جانشين فعلي اش در حلقه ي شناسه ارتباط برقرار کند.
پرسجوها براي يک شناسه ي کليد مشخص مي تواند توسط اين اشاره گرهاي جانشين حول حلقه پيموده شود؛ اين عمل ، تا زماني ادامه مي يابد که اين پرسجوها با زوج گرهي مواجه شوند که شناسه ي کليد موردنظر در بين اين زوج گره قرار بگيرد؛ گره ي دوم اين زوج ، گرهي است که پرسجو را ارضا مي کند. شبه کدي که فرآيند اين پرسجو را پياده سازي مي کند در شکل ٢ نشان داده شده است .
شکل ٣ مثالي را نشان مي دهد که در آن ، گره ي ٨ يک جستجو براي کليد ٥٤ را انجام مي دهد. گره ي ٨، روال ()find_successor را براي کليد ٥٤ فراخواني مي کند که سرانجام جانشين آن کليد (يعني ، گره ي ٥٦) را برمي گرداند. اين پرسجو، هر گره ي روي حلقه مابين گره هاي ٨ و ٥٦ را ملاقات مي کند. نتيجه ي پرسجو، در امتداد عکس مسير طي شده توسط
پرسجو به گره ي ٨ برمي گردد.
٤- مکانيابي بهينه ي گره ي ذخيره کننده ي گره
در روش جستجويي که در بخش قبل بيان شد تعداد پيام هايي که به گره ها ارسال مي شود با افزايش تعداد گره ها، بطور خطي رشد مي کند. براي تسريع جستجوها، Chord اطلاعات اضافي مسيريابي را نگهداري مي کند. اين اطلاعات اضافي براي صحت و درستي عملکرد سيستم ضروري نيست و تا زماني که هر گره ، جانشين صحيحش را بداند بدست آورده مي شود.
همانگونه که قبلا نيز گفتيم ، m را تعداد بيت هاي شناسه هاي گره .کليد در نظر بگيريد. هر گره ي n، يک جدول مسيريابي با حداکثر m مدخل را نگهداري مي کند، که اين جدول ، "جدول انگشتي ١٠" ناميده مي شود. i امين مدخل جدول گره ي n، حاوي هويت اولين گرهي (s) است که با فاصله ي شناسه اي حداقل 1-2i نسبت به n روي حلقه ي شناسه قرار دارد، يعني (و تمام محاسبات به پيمانه ي 2m است ). گره ي s را i امين انگشت گره ي n مي ناميم و آن را با نشان مي دهيم (جدول ١). يک مدخل جدول انگشتي شامل شناسه ي Chord و آدرس IP (و شماره ي پورت ) گره ي مربوطه است . توجه کنيد که اولين انگشت گره ي n، جانشين بلافصل n در حلقه است ؛ بطور قراردادي به اولين انگشت ، جانشين مي گوييم .
مثال شکل ٤ (الف )، جدول انگشتي گره ي ٨ را نشان مي دهد (٦= m).
