بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
بکارگیری یک روش فرا اکتشافی جهت تخصیص قطعات داده در طراحی سیستم پایگاه داده توزیع شده
چکیده :
تخصیص قطعات داده یکی از مسائل مهم در پایگاه داده توزیع شده می باشد که عبارت از تعیین محل ذخیره سازی داده ها در گره های مختلف شبکه به نحوی که در هنگام اجرای پرس و جو ها هزینه انتقال داده ها بر روی مسیرهای شبکه کمینه گردد. در مساله تخصیص قطعات داده، تقابل بین درخواست های بازیابی و بهنگام سازی در کارایی سیستم توزیع شده به عنوان یک مشکل مطرح است. در مورد درخواست های بازیابی، تکرار قطعات داده که به صورت مشترک استفاده می شوند باعث افـزا یش کارایی سیستم خواهد شد ولی از طرفی در مورد درخواست های بروز رسانی تمامی تکرارهای قطعات داده باید بهنگام سـاز ی گردند که این سبب کاهش کارایی سیستم توزیع شده می شود،لذا در تخصیص و تکرار قطعات می بایستی مصالحه ای صـورت پذیرد. مساله تخصیص یک مساله NP-Complete بوده و راه حل های متفاوتی در سال های اخیر برای آن ارائه شدهاست. اما اغلب این روش ها از نظر میزان هزینه با حالت بهینه فاصله قابل توجه ای دارند. در این مقاله از مدلی که مبتنی بر بازتاب رفتار تراکنش ها در پایگاه داده توزیعی می باشد استفاده شده که هدف آن پیدا کردن یک موقعیت و محل بهینه بـر اسـاس حـداکثر هزینه بروز رسانی یک قطعه در سایت در نظر گرفته شده جهت تخصیص می باشد و بر اساس این مدل و اطلاعات تـراکنش هـا، یک روش مبتنی بر تخصیص مجدد برای پیدا کردن تخصیص نزدیک به بهینه توسعه داده شـده اسـت. نتـایج بدسـت آمـده از الگوریتم پیشنهادی حاکی از بهبود عملکرد و از طرفی کاهش هزینه سربار انتقال داده ها در پایگاه داده توزیع شده می باشد.
-1 مقدمه
پیشرفت در تکنولوژی های شبکه و پایگـاه داده در دهـه هـای اخیـر منجر به ایجاد سیستم های پایگاه داده توزیع شده گشته اسـت. یـک سیستم پایگاه داده توزیع شده مجموعه ای از سایت ها می باشدکـه از طریق شبکه به هم متصل شده اند که هر کدام از سایت ها پایگـاه داده مخصوص به خود را دارد، اما می تواننـد بـا یکـدیگر کـار کننـد بنابراین هر کاربری در هر سایتی می تواند به همه داده های موجـود در شبکه دسترسی داشته باشد درست مانند اینکـههمـه دادههـا در سایت کاربر ذخیره شده است. سیستمهـا ی اطلاعـاتی توزیـ ع شـده دارای پیچیدگی های متعددی بوده و طراحی و پیاده سـازی آنهـا بـا چالش های متعددی همـراه اسـت. یـا ن پیچیـ دگیبـه دلیـ ل وجـود مسائل به هم مرتبط زیادی از قبیل چگونگی قطعه بندی یک رابطـه، تعداد تکرار هر قطعـه و نحـوه تخصـ یص قطعـات بـه سـا یتهـا، در طراحی سیستم ها می باشد. حتی اگر هر یک از موارد فوق به تنهایی بررســی شــود طراحــی سیســتم اطلاعــات تــوزیعی همچنــان دارای پیچیدگی زیادی است.[1] به همین دلیـ لبـه منظـور سـاده سـازی فرض شده است که همه روابط موجود در سیستم از قبل قطعه بندی شده باشند. بنابراین در اینجا مساله اصلی، تعیین تکرار های هر قطعه و سپس پیدا کردن یک تخصیص نزدیک به بهینه برای همه قطعـات، به نحوی که هزینه کل انتقال کمینه گردد.[1] امـا مشـکل عمـده در مساله تخصیص قطعه، تقابل بین درخواسـتهـا ی بازیـ ابی و بهنگـام سازی در کارایی سیستم است. در مورد درخواست های بازیابی تکـرار داده هایی که به صورت مشترک استفادهمـ ی گردنـد باعـث افـزایش کارایی سیستم می شود ولی از طرفی در مورد درخواستهـا ی بـروز رسانی تمامی تکرار داده ها می بایست به هنگام سازی گردند که این امر سبب کاهش کارایی سیستم میشـود . لـذا در تخصـ یص و تکـرار قطعات باید مصالحه ای صورت پذیرد . هزینه اصلی در اجرایپـرس و جو در سیستم های پایگاه داده توزیع شده هزینه انتقـال داده هنگـام انتقال یک رابطه در موقـع درخواسـتپـرس وجـو از یـک سـایت و انتقال آن از یک سایت متفاوت می باشد. هدف اصلی الگـوریتم هـای تخصیص داده تعیین نسبت دادن قطعات داده به سایت های مختلـف برای کمینه کردن هزینه انتقال داده در اجرای یک مجموعه ازپـرس جو ها می باشد که معادل کمینه کردن زمان متوسط اجرایپـرس جو می باشد که اهمیت اصلی در محیط های توزیع شـده و پایگـاه داده چند رسانه ای دارد.[2]
-2 تعریف مساله
در مدل پیشنهادی ما فرض بر این است که یک شبکه به طور کامـل متصل و یا به عبـارتی Fully Connected وجـود دارد کـه شـامل مجموعه ای از سایت هاS = {S1, S2, …., Sm} است کـه هـر سایت دارای یک ظرفیت (C) و محدویت در پذیرش قطعـه (FL) و همچنین دارای یک سیستم پایگاه داده محلی است.[3]
4Tارتباط بین 14T دو سایت 14T 4Tو14T 14Tیک عدد صحیح مثبـت اسـت T(CCij)1 انتقال یک واحد داده از سایت 1T به سایت که نشان دهنده هزینهSi S j پــرس و جــو هــا مــی باشــد . هــر ســایت دارای مجموعــه ای از Si S j Q={Q1,Q2,...,Qk} می باشد. هر پرس و جـو مـی توانـد از پرس و جو K در هر سایت با یک فرکانس مشخص اجرا شود. اجرای k سایت m را می توان با m*k در ماتریس نشان داد.[3]
همچنین مجموعه قطعات داده QFi,jF3, Fn} که مـورد F={F1, F2, استفاده تراکنش ها می باشد و در خلال فاز قطعه بندی در طراحـی پایگاه داده توزیعی مشخص شده اند.[3]
برای اینکه یک تخصیص کارآمد و پویا را داشته باشیم ما نه تنها نیـاز به تعیین هر قطعه برای هر سایت داریم بلکه نیاز به پیدا کـردن یـک تخصیص مناسب برای هر یک از قطعات در سراسر سایت ها با توجـه به اطلاعاتی که قبلآ در رابطه با پرس و جو ها جمع آوری کـرده ایـم داریم.[4] دو تعریف بهینگی در این ضمینه وجود دارد: [5 ]
-1 کمترین هزینه ( هزینه ذخیره سازی هر قطعه در هـر سـایت + هزینه پرس و جو در سایت + بروز رسانی قطعه هزینه در سایت هایی که در آنها ذخیره شده + هزینه ارتباط داده ها )
-2 داشتن عملکرد و کارایی ( به حداقل رساندن زمان پاسـخ دهـی و به حداکثر رساندن توان سیستمی) در حال حاضر در این مقاله، هدف ما بهینه سازی مورد اول (کمترین هزینه) در مدل پیشنهادی می باشد. همچنین در تعریف مساله در این مقاله نماد هایی اسـتفاده شـده در زیر به اختصار توضیح داده شده است: [6]
-3 اطلاعات مورد نیاز جهت تخصـیص قطعـات داده
اطلاعات مربوط به پایگاه دادها
اطلاعات مربوط به رفتار پرس وجو ها
اطلاعات مربوط به سایت ها
اطلاعات مربوط به شبکه
-1-3 پایگاه داده
یکارتباط معمولآ شامل تعداد زیادی از قطعـات اسـت و انـدازه هـر قطعه برای حل مساله تخصیص داده باید از قبل تعریـف شـده باشـد زیرا این اندازه نقش کلیدی در محاسبه هزینه های ارتباطی دارد.[6]
در فرمــول (1) نمــاد : L طــول تکــه شــده مــی باشــد و تاپــل : Card( ) کاردینالیتی قطعـه یـا تعـداد رکـورد هـای قطعـه مـی باشــد. همچنــین طــول یــا انــدازه مــی توانــد بــه صــورت عبــارت زیر بیان شود: [6]
در فرمول (2) نماد h قطعه و حرف A ، a بنابراین :
نشان دهنده : تعداد صفات موجـود بـرای یـک امین صفت را نشان می دهد.
جویی که در هر سایت بکار گرفته شده، آن پـرس و جـو بایـد مقـدار فرکانسی را در آن سایت داشته باشد.
همچنین، بدین منظور ما ماتریس فرکانسی را برای اجرای، هر پـرس و جو در هر سایت در نظر گرفته ایم
در فرمول (3) نماد : n تعداد رکوردهای موجود در قطعه.
جهت ساده سازی، اندازه قطعات در مدل ارائه شده ما به صورت زیـر فرض شده است :
-2-3 رفتار پرس و جو ها
از آنجایی که هر پرس و جو در پایگاه داده توزیع شده یا برای بازیابی و یا برای بروز رسانی استفاده می شـود، مـا دو مـاتریس را در اینجـا تعریف می کنیم. مـاتریس RM بـرای بازیـابی و مـاتریس UM کـه برای بروز رسانی می باشد.[7]
به عنوان مثال در جدول 2، پـرس وجـوی را سه بار و را فقط یک بار بازیابی کرده است.
همچنین در جدول 3، پرس وجوی قطعـه را دوبـار و قطعـه را یکبار بروز رسانی کرده است. 2با ایـن حـال، بـرایهـر پـرس
-4-3 اطلاعات مربوط به سایت ها
در مدل ما، در ایـن بخـش اطلاعـاتی در رابطـه بـا محـدودیتهـای در نظر گرفته شـده بـرای سـایت هـا بیـان مـی شـود . در واقـع هـر ســایت دارای یــک ظرفیــت (C) و محــدویت در پــذیرش قطعــه (FL) که نشان دهنـده حـداکثر انـدازه و تعـداد قطعـاتی اسـت کـه یــک ســایت مــی توانــد اداره کنــد، باشــد. محــدودیت هــای اعمــال شــده بــرای مــدیریت پروســه تخصــیص در عبــارت زیــر نشــان داده شده است
فرمول (4 ) نشان می دهد که هر قطعه ( ( F باید به حداقل تعـدادی سایت در مرحله اول، تخصیص داده شود.
همچنین , ماتریسی می باشد که تخصیص قطعات به سایتهـا را نشان می دهد.
این ماتریس توسط ماتریس بازیابی (RM) تعیین خواهـد شـد و در مرحله تخصیص اولیه مورد استفاده قرار می گیرد :
فرمول (5) حالتی را بیان می کند که هیچ سایتی نمی تواند بیشتر از ظرفیت خودش مقداری را دریافت کند.
فرمول (6) حالتی را بیان می کند که هر سایت بیشترFL از آنQijظرفیتی که برای آن مشخص شده را نمی تواند قطعه بگیرد.
فرمول (7) حالتی را بیان می کند که یک قطعه تنها بـه یـک سـایت می تواند تخصیص داده شود.
در زیر جدول شماره 5 این محدودیت ها را نشان می دهد:
-5-3 اطلاعات مربوط به شبکه
در روش پیشنهادی ما فرض بر این استکـه سـایت هـا در سیسـتم پایگــاه داده توزیــع شــده در شــبکه کــاملآ متصــل یــا Fully Network Connected قرار دارند. هر ارتباطی که بـین سـایت های وجود داشته باشد و این ارتباط دارای یک مقدارهزینـه که بین بیانگر هزینه ارتباطی اسـت ای بنام و, می باشد که در واقع ,شده است :[8]
ما هزینه ارتباطات را در یک ماتریس نشان می دهیم.هزینـه ارتبـاط و در واقع همان هزینه ارتباط بین سایت های بین سایت های باشد.
همچنین هزینه ارتباط هر سایت با خودش برابر با صفر اسـتکـه در جدول 6 نشان داده شده است :
همچنین کمترین هزینه ارتبـاطی ممکـن بـین دو سـایت بـه عنـوان ماتریس فاصله در جدول 7 نشان داده شده است:
-4 معرفی مدل پیشنهادی و توابع هزینه
در این مدل فرض شده که ما اطلاعات مربوط به فرکانس بروز رسانی را جمع آوری کرده ایم. در واقع فرکـانس بـروز رسـانی نقـش بسـیار مهمی را در تخصیص قطعات به سایت ها بازی می کند. بـرای انجـام درست فرایند تخصیص، هر قطعه باید به یک یا چند سایت در پایگاه داده های توزیع شده در مقدار دهی اولیه اختصاص داده شود . به هـر حال از آنجایی که مساله تخصیص مستلزم پیـدا کـردن یـک توزیـع بهینه ای از قطعات در سرار سـایت هـا مـی باشـد، پـس بـرای یـک مجموعه داده شده ای از قطعات با انـدازه هـای مختلـف و همچنـین تعدادی از سایت های شـبکه کـه هـر یـک از ایـن سـایت هـا دارای تعدادی پرس و جو اجرا شده هستند، ارائه یک مدل تخصیص بهینـه مستلزم به حداقل رساندن هزینه کل بروز رسـانی در سراسـر شـبکه بدون نقض محدودیت های سایت ها می باشـد . در مـدل پیشـنهادی ما، فرض شـده کـ ه اگـر یـک پـرس و جـو یکسـانی در سـایت هـای متعددی صادر شده باشد، آن به عنوان یکپـرس و جـو متفـاوت در نظر گرفته می شود که می تواند مقادیر فرکانس های مختلفـی را در بر داشته باشد. ما به مقادیر فرکانس بـروز رسـانی پـرس و جـو هـا (جدول (UM در هر زمـان از پروسـه تخصـیص داده، نیـاز خـواهیم داشت. در روش پیشنهادی برای انجام مرحلـه اول از توزیـع قطعـات (که ممکن است شامل قطعات تکراری هم باشد) فرض شده است که قطعه مورد نظر در حال حاضر در تمام سایت های شبکه توزیع شـده است که این امر بوسیله یک ماتریس بازیابی داده یا RM و مـاتریس فرکانس پرس و جویـا QF میسـر مـی شـود . در روش پیشـنهادی فرض بر این است که درخواست های بازیابی هیچ هزینـه ارتبـاطی را برای تخصیص هر قطعه بهسـایت هـای درخواسـت کننـده متحمـل نخواهد شد. به عنوان مثال قطعه F3 در مـاتریس RM (جـدول (2 می تواند تنها بوسیله پرس و جو هـای Q3 و Q4 درخواسـت داده شود و از آنجایی که این پرس و جو ها از سایت های S1 و S3 صادر شده اند، پس قطعه F3 می تواند در هر دو این سایت ها یعنی S1 و S2 تخصیص داده شوند. این روش تخصیصتنهـا از فرکـانسهـای پرس و جو و ماتریس بروز رسانی استفاده می کنـد، زیـرا درخواسـت های
