مقدمه
پیشرفت در تکنولوژیهای شبکه و پایگاه داده در دهه های اخیر منجر به ایجاد سیستم های پایگاه داده توزیع شده گشته است .یک سیستم پایگاه داده توزیع شده مجموعه ای از سایتها می باشد که از طریق شبکه به هم متصل شده اند که هر کدام از سایت ها پایگاه داده مخصوص به خود دارد اما می توانند با یکدیگر کار کنند بنابراین هر کاربری در هر سایتی می تواند به همه داده های موجود در شبکه دسترسی داشته باشد درست مانند اینکه همه داده ها در سایت کاربر ذخیره شده است .
دغدغه اصلی سیستم های پایگاه داده توزیع شده قطعه قطعه کردن و تخصیص پایگاه داده اصلی می باشد واحد قطعه داده می تواند یک فایل باشد که در این حالت موضوع تخصیص همان تخصیص فایل خواهد بود مشکل تخصیص داده یک مسئله NP-complete می باشد بنابراین نیاز به هیوریستیکهای سریع برای تولید راه حل های موثر می باشد علاوه بر اینها تخصیص بهینه اشیا پایگاه داده به طور شدید بستگی به استراتژی اجرای پرس وجو که به وسیله پایگاه داده توزیع شده پیاده سازی شده دارد .
هزینه اصلی در اجرای پرس و جو در سیستمهای پایگاه داده توزیع شده هزینه انتقال داده هنگام انتقال یک رابطه در موقع درخواست پرس و جو از یک سایت و انتقال آن از یک سایت متفاوت می باشد[2] . هدف اصلی الگوریتم های تخصیص داده تعیین نسبت دادن فرگمنتها به سایتهای مختلف برای کمینه کردن هزینه انتقال داده در اجرای یک مجموعه از پرس و جو ها می باشد که معادل کمینه کردن زمان متوسط اجرای پرس و جو می باشد که اهمیت اصلی در محیط های توزیع شده و پایگاه داده چند رسانه ای دارد .
الگوریتم های استاتیک :
مسئله تخصیص داده به طور کلی یک مسئله NP-complete می باشد و نیازمند هیوریستکهایی میباشد که راه حل سریع و با کیفیت بالا تولید کند. گسترش یک هیوریستیک موثر بستگی به استراتژی اجرای پرس و جویی دارد که توسط سیستمهای پایگاه داده توزیع شده بکار گرفته می شود که به این دلیل است که استراتژی مختلف اجرای پرس و جو الگو های مختلف انتقال داده متفاوت دارند[10] . الگوریتم تخصیص داده پارامترهای زیر را به عنوان ورودی می گیرد : 1 – گراف وابستگی قطعه داده 2- هزینه انتقال واحد داده ای بین سایتها 3 – محدودیتهای تخصیص روی تعداد قطعه داده که می تواند به سایت تخصیص داده شود 4 - تعداد تکرار اجرای پرس و جو از سایتها[4]
گراف وابستگی قطعه داده یک گراف بدون سیکل جهت دار می باشد که در ریشه آن سایت اجرای پرس و جو قرار دارد و سایر نودها نودهای قطعه داده می باشد که ممکن است توسط پرس و جو مورد دسترسی قرار گیرد و این گراف وابستگی قطعه داده وابستگی بین قطعه داده و مقدار داده ای که بایستی موقع اجرای پرس و جو منتقل شود را مدل می کند .
شکل 1 : گراف وابستگی قطعه داده
الگوریتم ژنتیک
فرض کنید ri,j نشان دهنده نیازمندی سایت i به قطعه داده j می باشد ، و هر قطعه داده i بوسیله اندازه اش مشخص می شود که با si نشان داده می شود و ti,j نشان دهنده هزینه ای است که سایت i متحمل می شود تا به قطعه داده که در سایت j وجود دارد دسترسی پیدا کند مشکل تخصیص در سیستم های پایگاه داده توزیع شده پیدا کردن راه حلی است که داده ها طوری در سایت های موجود استقرار یابند که برای دسترسی به آنها کمترین هزینه را متحمل شویم . این بدین معناست که ما عمل جایگزینی
P = {p1, p2, p3,..,pj, ...,pn} ( که pj=i نشان دهنده قطعه داده j است که در سایت i واقع شده است) برای n قطعه داده پیدا می کنیم بنابراین هر سایتی از ظرفیت خودش سرریز نمی شود و
ri,j sj <= ci,j i | 1<=i<=m و ri,j ti,pj کمینه می شود.
با محدود کردن استفاده از نیازمندیهای ماتریس و هزینه انتقال صفر مسئله تخصیص پایگاه داده توزیع شده به مسئله bin packing تبدیل می شود که یک مسئله NP-complete می باشد.
الگوریتم ژنتیک یک تکنیک جستجوی تطابقی می باشد که بر پایه اصول و مکانیزمهای انتخاب طبیعی و survival of the fittest از سیر تکاملی تدریجی می باشد با شبیه سازی سیر تکاملی طبیعی الگوریتم ژنتیک می تواند به طور موثر حوزه مسئله را جستجو کند و به راحتی مسائل مشکل را حل کند . الگوریتم ژنتیک با تولید یک population اولیه شروع به کار می کند ، P (t = 0) ، و هر کدام از اعضای خود را با تابع هدف ارزیابی می کند تا موقعی که شرایط پایانی فراهم نشود یک قسمت از population انتخاب ، ارزیابی و برگردانده میشود به population.[12]
الگوریتم ژنتیک برای مسئله تخصیص داده به صورت زیر می باشد :
1- population را مقداردهی اوایه کن هر کدام از population های انفرادی اتصال نمایش دودویی تخصیص تصادفی اولیه هر قطعه داده می یاشد.
2- Population را ارزیابی کن.
3- تعداد generation=0
4- تا وقتی که no of generation < MAX GENERATION انجام بده
5- Individual ها را از population بعدی انتخاب کن
6- Crossover و Mutation را برای Individual ها انتخاب شده انجام بده
7- Population را ارزیابی کن
8- تعداد generation را یکی اضافه کن
9- اتمام حلقه While
10- تخصیص نهایی را با انتخاب fittest individual مشخص می کند اگر تخصیص نهایی قابل امکان نباشد سایتی که از نظر قطعه داده بار اضافی دارد بار آن را به سایتی منتقل می کند که کمترین هزینه انتقال را دارد .
الگوریتم ژنتیک نسبت به استفاده از هیوریستیک حریصانه روی مسئله اختصاص قطعه داده با سایزهای مختلف کارایی بیشتری دارد . هیوریستیک حریصانه زمان و تلاش زیادی برای پیاده سازی نیاز دارد در حالیکه الگوریتم عمومی ساده می باشد .[12]
الگوریتم Simulated Evolution :
تفاوت اصلی الگوریتم ژنتیک با الگوریتم Simulated Evolution این است که اولی روی crossover دارد که یک مکانیزم احتمالی می باشد و که برای تبادل اطلاعات بین راه حلها برای شناسایی بهترین راه حل مناسب می باشد در حالیکه دومی از mutation به عنوان مکانیزم جستجوی اولیه استفاده می کند. علاوه بر اینها در شمای مطرح شده نمایش chromosomal بر پایه مشکل داده می باشد و راه حل با استفاده از هیوریستیک کدگذاری ( هیوریستیک نگاشت ) به منظور نگاشت از حوزه مسئله به حوزه راه حل تولید شده است . این الگوریتم به صورت زیر است :[7]
1- اولین chromosome را براساس مسئله داده تولید کن و این chromosome را برای تولید population اولیه تغییر بده.
2- از هیوریستیک نگاشت برای تولید راه حل برای هر chromosome استفاده کن.
3- راه حل بدست آمده را ارزیابی کن
4- تعداد generation=0
5- تا وقتی که no of generations < MAX GENERATION انجام بده
6- Chromosome ها را برای population بعدی انتخاب کن
7- برای این مجموعه کروموزوم ها crossover و mutation انجام بده
8- از هیوریستیک نگاشت برای تولید راه حل برای هر chromosome استفاده کن.
9- راه حل بدست آمده را ارزیابی کن
10- تعداد generation ها را یکی اضافه کن
11- پایان حلقه While
12- بهترین راه حل پیدا شده تاکنون را به خروجی ببر
هیوریستیک نگاشت
برای هر کروموزوم یک راه حل با تخصیص قطعه داده j با الویت بالا برای سایت i پیدا می کنیم طوریکه u’i j برای تمام u’x j, 1<x <m کوچکترین باشد. اگر حد تخصیص موثر برای یک ژن موجود در قسمت a کروموزوم برای یک سایت فراتر رود ما این قطعه داده را به سایتی اختصاص می دهیم که u’ij اش کمترین مقدار بعدی ( هزینه تخصیص قطعه داده j به سایت i ) برای تمام u’yj, 1< y <m, y ≠ x باشد.این واقعیت که هر قطعه داده به یک سایت تخصیص داده می شود گارانتی می شود برای اینکه هر بار چک می شود حد تخصیص کلی بزرگتر یا مساوی تعداد قطعه های داده برای هر نسل از کروموزوم ها باشد. سپس می توانیم این فرایند را برای هر قطعه داده با الویت بالا بین قطعه داده های دیگر که هنوز به سایتی تخصیص داده نشده ادامه پیدا می کند.[9]
الگوریتم The Mean Field Annealing (MFA) :
تکنیک Mean Field Annealing ویژگی محاسباتی بهم پیوسته شبکه عصبی Hopfield را با
simulated annealing ترکیب می کند .MFA ابتدا برای حل مشکل فروشنده دوره گرد به جای استفاده از الگوریتم HHN که نمی توانست مسئله با اندازه بزرگ را حل کند مطرح گردید MFA یک راه حل عمومی است که می تواند برای حل مسئله های بهینه سازی ترکیبی مختلف استفاده شود.
شبکه عصبی Hopfield
الگوریتم MFA به صورت زیر است :
1. temperature اولیه را بدست آور قرار بده T=T0
2. میانگین spin ها را مقداردهی اولیه کن s = [s00, s01, . . . , sk−1,m−1 هر si j با یک عدد تصادفی بین 0 و 1 مقداردهی اولیه می شود
3. تا وقتی که temperature در بازه cooling می باشد انجام بده
4. تا وقتی که E کاهش می یابد انجام بده
5. قطعه داده i را به صورت تصادفی انتخاب کن
6. Mean field ، spin ها را در ردیف i محاسبه کن برای مثال : Φi j , ∀ j
7. مجموع روبرو را محاسبه کن: ∑eΦij/T
8. مقدار spin جدید را در ردیف i محاسبه کن
9. تغییرات انرژی را به خاطر این بروزرسانی های جدید محاسبه کن
10. پایان حلقه While
11. temperature ، T را مطابق با زمانبندی cooling بروز کن
12. پایان حلقه While
13. تخصیص نهایی را با تخصیص هر قطعه داده به سایت با توجه به مقدار spin بزرگ مشخص کن . اگر تخصیص نهایی قابل امکان نباشد سایتی که قطعه داده اضافی دارد این قطعه داده را به سایتی منتقل کن که کمترین هزینه را داشته باشد.[3]
الگوریتم تخصیص داده جستجوی تصادفی همسایگی
ایده اصلی در الگوریتم جستجوی همسایگی تولید یک راه حل اولیه با کیفیت مناسب می باشد سپس الگوریتم به طور احتمالی مطابق با برخی همسایگی های از قبل تعریف شده ، راه حل های مجاور در فضای جستجو را انتخاب و آزمایش می کند که آیا از حالت قبل بهتر است یا نه ، اگر راه حل جدید بهتر باشد الگوریتم از این راه حل اقتباس می کند و جستجو را در همسایگی جدید آغاز می کند در غیر اینصورت الگوریتم نقطه جدیدی را انتخاب می کند الگوریتم کار خود را موقعی به اتمام می رساند که یا تعداد قدمهای جستجوی آن به یک مقدار مشخص برسد و یا اینکه بعد از تعدادی قدم بهبودی حاصل نشود کیفیت راه حل در الگوریتم جستجوی همسایگی بطور شدیدی بستگی به راه حل همسایگی دارد الگوریتم برای مسئله تخصیص داده به صورت زیر می باشد:
1. از Divisive-Clustering برای پیدا کردن تخصیص اولیه Initial Alloc استفاده کن
2. Best Alloc = Initial Alloc
3. New Alloc = Best Alloc; iteration = 0
تکرار کن
4. searchstep = 0; counter = 0
تکرار کن
5. به طور تصادفی دو سایت از Initial Alloc انتخاب کن
6. به طور تصادفی دو قطعه داده از هر سایت انتخاب کن
7. این دو قطعه داده را با هم تبادل کن
8. اگر هزینه کاهش پیدا کرد آنگاه
خود را با این تبادل انطباق بده و counter را مساوی صفر قرار بده
در غیر این صورت undo کن و counter را یکی اضافه کن
تا وقتی که ++searchstep > MAXSTEP OR counter > MARGIN
9. اگر cost(New Alloc) < cost(Best Alloc) آنگاه
Best Alloc = New Alloc
10. دو قطعه داده از دو سایت مجزا که به طور تصادفی از New Alloc انتخاب شده اند را با هم تبادل کن
تا وقتی که iteration > MAXITERATION [10]
به طور کلی SE و GA راه حلهای بهتری نسبت به RS و MFA تولید می کنند الگوریتم RS پیچیدگی زمانی کمتری دارد بنابراین الگوریتم سریعی می باشد ولی الگوریتم SE کند می باشد برای حوزه هایی که بایستی سریع عمل کنیم و جواب بهینه مدنظر نمی باشد الگوریتم RS گزینه مناسبی می باشد ولی اگر کارایی و کیفیت راه حل اهمیت داشته باشد الگوریتم GA گزینه مناسب می باشد بنابراین داشتن همه این الگوریتم ها در سیستم پایگاه داده توزیع شده باعث می شود که راه حلهای متنوع داشته باشیم و این راه حلها یک trade-off بین پیچیدگی و کیفیت می باشد.
در [10] برای تخصیص قطعه داده یک متدی طراحی شده که نیازمندیهای خوشه کردن سایتها و تعیین تخصیص قطعه داده در سیستمهای پایگاه داده توزیع شده را برطرف می کند علاوه بر اینها هزینه ارتباط بین سایتها را کاهش می دهد و کارایی را در محیط سیستمی شبکه غیرمتجانس افزایش می دهد . متد خوشه بندی به این دلیل استفاده شد که سایتها را در یک خوشه گروه بندی کنند که این کار باعث کاهش هزینه ارتباط بین سایتها در فرآیند تخصیص داده می شود . متد تخصیص قطعه داده با افزایش قابلیت در دسترس بودن و قابلیت اطمینان ( کپی های چندگانه از قطعه های داده وجود دارد ) کارایی سیستم را افزایش می دهد.
الگوریتم تخصیص پویا :
در محیط استاتیک یعنی جایی که دسترسی به قطعه داده هایی که در سایتها وجود دارد از جانب سایتهای دیگر تغییر نمی کند تخصیص قطعه داده استاتیک بهترین راه حل می باشد در حالیکه در محیط پویا این احتمالات دسترسی که در طول زمان و به کررات عوض می شود ، تخصیص قطعه داده استاتیک کارایی پایگاه داده را کاهش می دهد . در زیر ما الگوریتم های مختلف تخصصیص قطعه داده پویا را بررسی می کنیم:
الگوریتم شمارنده ساده
در این الگوریتم با استفاده از یک شمارنده که تعداد دسترسی از هر سایت به هر بلاک را نگهداری می کند استفاده می شود برای اینکه مشخص شود کی تخصیص مجدد مورد نیاز می باشد شمارنده برای هر بلاک فقط در یکی از سایتهای موجود در سیستم پایگاه داده توزیع شده نگهداری می شود
برای مثال فرض کنید پارتیشن A در سایت 1 قرار دارد در سیستمی با تعداد سایتهای N ، سایت 1 N شمارنده برای پارتیشن A نگهداری می کند . الگوریتم شمارنده ساده سایتهایی که به این قطعه داده دسترسی پیدا می کنند را رتبه بندی می کند و بهترین سایت را انتخاب می کند این الگوریتم به صورت زیر می باشد:[3]
الگوریتم شمارنده ساده :
1. یک فرایند state در بازه های زمانی منظم شمارنده ها را برای هر بلاک چک میکند
2. سطرهای یک بلاک در صورتی که شمارنده مربوط به آن بلاک در یک سایت بیشتر از سایتی باشد که بلاک هم اکنون در آن قرار دارد به آن سایت منتقل می شود
3. بعد از چک کردن شمارنده بلاک ها ، فرایند state قبل از چک کردن دوباره شمارنده ها برای تعداد t-check از تراکنشها که قرار است کامل شوند صبر می کند
شکل 2 : الگوریتم شمارنده ساده
در این الگوریتم فرایند وضعیت فرایندی می باشد که برای هر تراکنش اطلاعات آماری مانند توان عملیاتی و میانگین زمان پاسخ و قسمتی از تراکنش کهنیازمند دسترسی به داده ای که در سایت دیگر ذخیره شده را نگهداری می کند بایستی توجه داشته باشیم که مقدار t-check به اندازه کافی کوچک باشد تا سیستم در مقابل تغییرات بار واکنش سریع نشان دهد همچنین باید به اندازه کافی بزرگ باشد تا این تعداد تکرار دسترسی به یک بلاک که در یک سایت مشخص قرار دارد به یک مقدار ثابت برسد و بتوان از روی آن تصمیم گیری کرد که بلاک باید به کدام سایت منتقل شود . مشخص کردن اینکه آیا یک بلاک بایستی به سایت دیگر منتقل شود یا نه یک تصمیم محلی می باشد به همین دلیل شمارنده هر بلاک در سایتی قرار داده می شود که بلاک هم در همان سایت قرار دارد . این الگوریتم بر الگوریتم های تخصیص داده استاتیک برتری دارد.[3]
الگوریتم Load Sensitive counter :
الگوریتم شمارنده ساده وقتی که توزیع قطعه های داده در سایتها متعادل باشد خوب کار می کند ولی اگر یک سایت به تعداد بلاک های زیادی دسترسی پیدا کند این الگوریتم همه این بلاکها را در این سایت قرار می دهد و باعث می شود بخاطر بار اضافی پردازنده و دیسک موجود در این سایت کارایی پایین بیاید الگوریتم Load Sensitive counter با در نظر گرفتن شرایط بار این مشکل را حل می کند بدون این الگوریتم اگر بلاکهای زیادی در یک سایت قرار گیرد همزمانی اجرای بین تراکنشها کاهش پیدا می کند و توان عملیاتی کاهش پیدا می کند . این الگوریتم بر الگوریتم شمارنده ساده و الگوریتم های استاتیک برتری دارد و به صورت زیر می باشد:[5]
الگوریتم Load Sensitive counter :
1. هم بر تعداد دسترسی ها و هم بر بار (توازن داده) در سیستم نظارت کن
2. اینکه بلاک داده بایستی منتقل شود یا نه مانند الگوریتم شمارنده ساده می باشد با این تفاوت که بلاک ها در صورتی منتقل می شوند که مقدار بلاک ذخیره شده در آن سایت از یک مقدار آستانه ای بالاتر نرود . پارامترهای الگوریتم عبارتند از : مقدار بلاک داده بیشینه ای که یک سایت می تواند در خود ذخیره کن و مقدار آستانه ای بار
شکل 3 : الگوریتم Load Sensitive counter
الگوریتم Incremental
چهارچوب رشد افزایشی موقعی فراخوانی می شود که کارایی سیستم از یک آستانه ای که توسط مدیر سیستم پایگاه داده مشخص می شود بالاتر رود . در این الگوریتم برای اینکه به یک وضعیت قابل قبول برسیم سرورهای جدیدی در سیستم پایگاه داده توزیع شده معرفی می شود با معرفی هر سرور جدید تخصیص مجدد داده جدید برای سیستم محاسبه می شود این فرایند به طور تکراری اجرا می شود تا موقعی که به یک کارایی قابل قبول برسیم یا اینکه تعداد سرور ها با تعداد رابطه ها در سیستم پایگاه داده توزیع شده یکسان باشد .
در یک سیستم پایگاه داده توزیع شده با افزایش بار کاری به سرورهای جدیدی نیاز پیدا می شود الگوریتم Incremental هیوریستیکهای تخصیص دوباره پر و تخصیص مجدد جزئی برای تخصیص داده موثر بکار می برد . هر دو این الگوریتم ها هیوریستیک های تکراری حریصانه و تپه نوردی می باشند که از مسیر دو بار عبور نمی کند .[6] در هر تکرار یا راه حل با کمترین هزینه را پیدا می کنند و یا تمام می شوند هر دو این الگوریتم ها اینها را به عنوان ورودی نیاز دارند : تخصیص داده کنونی ، رابطه ها ، و پرس وجوها در سیستم پایگاه داده توزیع شده . با معرفی سرورهای جدید در سیستم پایگاه داده توزیع شده هزینه کاهش پیدا می کند و علاوه براین می توان پیچیدگی را کنترل کرد . این هیوریستیک ها به خاطر پچیدگی خطی شان می توانند مسائل بزرگ ، کوچک و پیچیده را بر اساس نیازهای سازمانی حل کنند . این الگوریتم مسئله فضای جستجو را کاهش می دهد و بنابراین هزینه به طور کلی کاهش پیدا می کند.[6]
فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد
تعداد صفحات این مقاله 22 صفحه
پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید
دانلود مقاله الگوریتم های تخصیص داده پویا در سیستم های پایگاه داده توزیعی
