مدیریت انتشار و جایگذاری داده بر اساس دسترسی Managing Data Replication and Placement Based on Availability

1. مقدمه

شبکه­ی داده، تکنولوژی امیدبخشی برای تمامی سیستم­های توزیع است. این تکنولوژی در دست بودن مقادیر زیاد داده [16] را ارائه می­کند، اما مسئله در این نوع از محیط­های شبکه­ای، اطمینان از دسترسی پیوسته داده­ها و پاسخ به نیاز کاربران در حد امکان،با توجه به گستردگی جغرافیایی (گره­ها) و رواج عمومی داده­هاست. راه­حل عمومی این مساله استفاده از انتشار است. [17] انتشار داده روشی برای تولید کپی همسان داده در سایت­های پراکنده­ی جغرافیایی است( فایل­ها، پایگاه داده­ها). هر کپی از داده ها را یک نسخه بدل(Replica) می­نامیم.[7] هدف از این پژوهش اطمینان از در دسترس بودن مطلوب، با کمترین نسخه­ها و بدون کاهش عملکرد سیستم است. تحقق این هدف با استراتژی جایگذاری امکان­پذیر است که مطابق آن در دسترس بودن مورد نظر، پایداری گره­ها در سیستم و خطاها در نظر گرفته می­شود.

این تحقیق به صورت زیر ارائه خواهد شد: در بخش دوم برخی از آثار مرتبط با انتشار و جایگذاری نسخه­بدل­ها مورد بررسی قرار می­گیرد، در بخش سوم توپولوژی مورد استفاده در این پژوهش بررسی خواهد شد. بخش چهارم مباحث ویژه­ این پژوهش را ارائه می­کند که طرحی برای انتشار پویای موثر ارائه می­شود که به جایگذاری نسخه­ها و خطاهای سیستم در آن توجه می­شود. در بخش پنجم نتایج تجربی در شبیه­سازی متفاوت ما ارائه خواهد شد. بخش نهایی نیز با ذکر خلاصه­ای از پژوهش، نگاهی کوتاه به مسیر پژوهش­های آتی خواهیم افکند.

1. آثار مرتبط

استراتژی­های جایگذاری متفاوتی برای نسخه­های شبکه ارائه شده­اند که از توپولوژی سلسله­مراتبی بهره­مند هستند. طرح ارائه­شده در [3] هزینه­های ارتباط(انتقال داده) و ذخیره­سازی(هزینه­ی جایگزینی نسخه­ها) را کاهش می­دهد. در مقاله [5] از دو الگوی جایگذاری استفاده می­شود. در الگوی نخست، نویسندگان هزینه­های خواندن/نوشتن را به عنوان پارامترهای جایگزینی در نظر می­گیرند. در الگوی دوم، آنها همچنین بار ناشی از ذخیره­سازی مورد نیاز برای هر گره را نیز در نظر می­گیرند. در [11] نویسندگان مساله­ی جایگذاری را با توجه به تعادل بار میان گره­ها تعداد نسخه­های همزمان مورد توجه قرار داده­اند. در [5 و 11] تعداد گره­های شبکه ثابت است که تحقق آن در شبکه­هایی که گره­های به صورت پیش­بینی ناپذیر قطع و وصل می­شوند آسان نیست. در [8] نسخه­بدل­ها در گره­هایی تولید می­شوند که با درخواست­های زیادی مواجه است. در ادامه آنها به درخواست کاربران یا زمانی که داده­ها مورد استفاده نباشد و یا در زمانی که ظرفیت ذخیره سازی تکمیل شده و نیاز به ایجاد کپی­های ضروری باشد، پاک خواهند شد.تصمیم جایگذاری نسخه­ها از الگویی مبتنی بر هزینه پیروی می­کند. نویسندگان [6] رویکرد جایگذاری را در شبکه­های توزیعی پیاده­سازی کرده­اند. شبکه به عنوان نودهای رنگی که در گرافی دو جهتی ساختاردهی شده­اندالگوسازی شده­اند. در زمان تولید نسخه­ها، گره­های دارای نسخه­های مشابه از رنگی مشابه برخوردار می­شوند. اصل پروتکل در [6] آن است که هر نود، برای حداقل­سازی فاصله­ی میان گره­هایی با رنگ متفاوت و حداکثرسازی نودهای با رنگ یکسان، گرافی رنگی را انتخاب می­کند. مشکل این رویکرد آن است که تنها یک داده را برای هر نود در نظر می­گیردف به این معنا که هر گره تنها می­تواند یک رنگ داشته باشد.

1. الگوی سیستم

الگوی سیستم مورد استفاده توسط ما مجموعه­ای(فدراسیونی) از خوشه­ها با ریشه­ای واحد برای پیوند میان آنها است. سیستم­های متعددی مانند Internet [10] و DIET [1] از این توپولوژی استفاده می­کنند. شکل 1 مثالی از سیستم را با اجزای آن نشان می­دهد.

شکل 1 – توپولوژی مورد استفاده

ریشه در این توپولوژی برای مرتبط ساختن خوشه­ها مورد استفاده قرار می­گیرد. سرخوشه (CH) که اعضای خوشه را مشخص می­کند، جدول مسیریابی دارند که گره­های خوشه را مدیریت می­کند. دیگر گره­ها عناصر ذخیره­سازی هستند و حاوی یک یا چند نسخه­بدل از داده­ها هستند. در این سیستم، گره­ها رفتار اسنادی دارند[4] و یافتن خطاها بر اساس پیام حیاتی [9] صورت می­پذیرد. اگر خطایی تشخیص داده شود، خود پایداری[2] برای اتصال توپولوژی راه­اندازی می­شود.

1. رویکرد پیشنهادی

پژوهش حاضر الگوی جدیدی را برای انتشار و جایگذاری مورد استفاده قرار می­دهد. هدف اصلی این الگو حداقل ساختن تعداد نسخه­ها است که درجه­ی در دسترس بودن قطعی داده­ها را تضمین می­کند بدون آنکه از عملکرد سیستم بکاهد. استراتژی ما گره­های باثبات متفاوت و مستقلی را بر خلاف اکثر آثار [10] [13] [14] [17] مورد توجه قرار می­دهد. هر سرخوشه از کنترل­کننده­ی جایگذاری برای مدیریت انتشار و جایگذاری نسخه­ها در خوشه­ها برخوردار است.

1. تعداد نسخه­های ضروری

برای محاسبه­ی دسترسی Avail_j برای سیستم j می­توانیم از فرمول زیر استفاده کنیم :

که در آن :

j : داده

Avail_j: در دسترس بودن داده j . 1>=  Avail_j>= 0

α : تعداد نسخه­های داده j . α ε N

pi : ثبات گره i جایی که نسخه­ی داده j ذخیره شود. در تمامی مقاله ما میان ثبات گره و ثبات داده­ها تمایز می­گذاریم و به STAB نخست و p دوم اشاره می­کنیم. لذا اگر j در گره i ذخیره شود آنگاه : STAB_i = p_j

در مورد سیستمی که گره­ها از ثبات مستقل یکسانی برخوردارند آنگاه فرمول (1) به صورت زیر[9] در می­آید :

 

بسیاری از آثار [10] [14] [17] گره­ها برای استفاده از فرمول 2 سطح مشابهی از ثبات را فرض می­کنند. در [13] نویسنده از گره­هایی با سطح متفوتی از ثبات را مورد استفاده قرار داده اما او انتشار داده­ها را در گره­هایی با سطح یکسان ثبات ارائه کرده است. این طرح به او اجازه می­دهد از فرمول 2 برای محاسبه­ی تعداد نسخه­های ضروری در ایجاد دسترسی مطلوب استفاده کند. در سیستم ما، گره­ها ثبات مستقل و متفاوت دارند که در سیستم­های موجود یافتنی است. برای محاسبه­ی تعداد نسخه­های ضروری αکه سطح دسترسی Avail را تامین می­کنند، ما با سه امکان مواجه هستیم :

خوشبینانه : زمانی که تمامی نسخه­های داده j در گره­هایی با ثبات خوب خیره شده­اند. لذا دسترسی­پذیری Avail با کمترین تعداد نسخه تضمین می­شود. Opαتعداد نسخه­های ضروری برای دسترسی مطلوب در حالتی خوشبینانه است. این امر توسط فرمول 2 محاسبه می­شود که در آن p بهترین ثبات سیستم است.

بدبینانه : زمانی که تمامی نسخه­های داده j در گره­هایی با ثبات خوب خیره شده­اند. لذا دسترسی­پذیری Avail با بیشترین تعداد نسخه تضمین می­شود.Pesαتعداد نسخه­های ضروری برای دسترسی مطلوب در حالتی بدبینانه است. این امر توسط فرمول 2 محاسبه می­شود که در آن p کمترین ثبات سیستم است.

ترکیبی : زمانی که تمامی نسخه­های داده j در گره­هایی با ثبات متفاوت خیره شده­اند. لذا دسترسی­پذیری Avail با بیشترین تعداد نسخه تضمین می­شود. Hybαدر بازه­ای [OpαPes, α] قرار دارد. تعداد Hybαنمی­تواند پس از جایگذاری نسخه­ها محاسبه شود زیرا نمی­توانید pi مرتبط را در فرمول 1 را انتخاب کنید.

برای تضمین دسترسی Availj برای داده j در سیستمی که حاوی گره­های با سطوح متفاوت ثبات است، راه­حل­های متفاوتی پیشنهاد می­شود :

• نسخه­ی Pes αتولید شود، که در آن تضمین  دسترسی مورد توجه قرار می­گیرد. اما در محیطی که تولید و مدیریت نسخه­ها پرهزینه باشد، این رویکرد موثر نیست.


• نسخه­ی Opαتولید شود، که در آن تعداد نسخه­ها حداقل می­شود اما این راه­حل به گره­هایی با بهترین ثبات که بیشتر یا معادلOpα باشد نیازمند است.این راه­حل بار زیادی روی گره­هایی با بیشترین ثبات وارد می­کند که شمار فایل­های از دست رفته در اثر خطاها را افزایش می­دهد.

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

هر سرخوشه سطح خاصی از در دسترس بودن AvialD را برای خوشه خود مشخص می­کند.  AvailD با استفاده از تاریخچه­ی داده­ها و اهمیت آن در دوره­های پیشین تخمین زده می­شود. پس از محاسبه­ی AvailD ، سرخوشه دسترسی­پذیری واقعی داده­ها AvailR در خوشه را با دسترسی پذیری مطلوب AvailD مقایسه می­کند.

• اگر AvailD <=  AvailR : در این مورد دسترسی­پذیری برآورده می­شود. لذا سرخوشه کاری انجام نمی­دهد و در انتظار آزمودن دوباره­ی محدودیت­ها می­ماند.


• اگرAvailD >=  AvailR : در این مورد سرخوشه آغاز به تولید نسخه­بدل­ها می­کند و آنها و در جای مناسب ذخیره می­کند تا سطح دسترسی مطلوب AvailD برآورده شود.

ما گره­ای را که نسخه­ در آن ذخیره می­شود بهترین مقصد می­نامیم.

1. جایگذاری نسخه­ها

جایگذاری نسخه­ها نقش بسیار مهمی در سیستم ایفا می­کند. در [17] نویسنده نشان می­دهد که جایگذاری چندین نسخه از داده­ای واحد در گرهی مشابه دسترسی سیستم و تحمل خطا را کاهش نمی­دهد. از این رو،ذخیره­ی یک نسخه در یک گره سودمند خواهد بود. اما بهترین نامزد برایاین ذخیره­سازی چیست؟ در سیستم ما، گره­ها می­توانند خطاها را پیش­بینی کنند. در موارد مشکوک به خطا، گره تمامی داده­های خود را برای تضمین دسترسی مطلوب در گره دیگری ذخیره می­کند.

ما از پارامتر دیگری به نام درجه­ی پاسخ­گویی(DR) استفاده می­کنیم که میزان بایت­هایی را که باید در موارد مشکوک به خطا جایگزین شود را نشان می­دهد.

که در آن

Nj : گره

k : تعداد داده­های گره Nj

Dij : داده i که در گره j است

درجه­ی بالای پاسخ­گویی نشان می­دهد که گره میزان بایت زیادیرا در مورد مشکوک به خطا برای انتقال دارد. در این مورد زمان احیا میزان زمان مورد نیاز برای انتقال داده­ها از گره مشکوک به گره دیگر را نشان می­دهد. ما میزان DR را در تمام گره­ها 1 فرض می­کنیم.

گره­های نامزد که بهترین مقصد نامیده می­شود به صورت زیر مشخص می­گردند :

• در حال حاضر داده­ای ندارد


• میزان فضای کافی برای ذخیره داده وجود داشته باشد


• عامل دسترسی مناسب(AF) داشته باشد.

AF از طریق فرمول زیر محاسبه می­شود :