بخشی از مقاله
الگوريتم هاي تخصيص داده پويا
در سيستم هاي پايگاه داده توزيعي
مقدمه
پيشرفت در تکنولوژيهاي شبکه و پايگاه داده در دهه هاي اخير منجر به ايجاد سيستم هاي پايگاه داده توزيع شده گشته است .يک سيستم پايگاه داده توزيع شده مجموعه اي از سايتها مي باشد که از طريق شبکه به هم متصل شده اند که هر کدام از سايت ها پايگاه داده مخصوص به خود دارد اما مي توانند با يکديگر کار کنند بنابراين هر کاربري در هر سايتي مي تواند به همه داده هاي موجود در شبکه دسترسي داشته باشد درست مانند اينکه همه داده ها در سايت کاربر ذخيره شده است .
دغدغه اصلي سيستم هاي پايگاه داده توزيع شده قطعه قطعه کردن و تخصيص پايگاه داده اصلي مي باشد واحد قطعه داده مي تواند يک فايل باشد که در اين حالت موضوع تخصيص همان تخصيص فايل خواهد بود مشکل تخصيص داده يک مسئله 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]
شکل 4 :چهارچوب incremental growth
الگوريتم Threshold
در اين روش قطعه داده افقي ، عمودي يا ترکيبي از اينها مي تواند استفاده شود و واحدهاي تخصيص مي تواند به اندازه رکورد يا صفت باشد.
همانطور که قبلاً گفتيم در سيستم هاي پايگاه داده توزيع شده با قرار دادن قطعه داده ها در سايتهايي که بيشترين دسترسي به اين قطعه داده دارند کارايي افزايش پيدا مي کند . مشکل اساسي ما اين است که براي يک قطعه داده بتوانيم سايت مناسب را پيدا کنيم يک راه حل اين مشکل اين است که براي يک
قطعه داده خاص تعداد دسترسي تمام سايتها را بشماريم آن سايتي که بيشترين دسترسي به اين قطعه داده را داشته باشد اولين کانديد براي ذخيره سازي آن مي باشد. براي اين کار يک ماتريس m*n در نظر مي گيريم که m نشان دهنده تعداد قطعه هاي داده و n نشان دهنده تعداد سايتها مي باشد که در اين ماتريس هر عنصر sij از S نشان دهنده تعداد دسترسي هاي سايت j به نود i مي باشد.[8]
ابتدا همه قطعه هاي داده با استفاده از يکي از روشها بين نودها توزيع مي شوند سپس هر نود j الگوريتم optimal را براي هر قطعه داده i که در آن نود ذخيره شده اجرا مي کند.
الگوريتم optimal به صورت زير مي باشد:
الگوريتم optimal :
1. براي هر قطعه داده که به صورت محلي ذخيره شده سطر شمارنده دسترسي را برابر 0 قرار بده ( Sik=0 که k=1,2,…,n )
2. درخواست دسترسي به قطعه داده ذخيره شده را پراسس کن
3. شمارنده دسترسي نودي که به اين قطعه داده دسترسي پيدا کرده را يکي افزايش بده ( اگر نود x به قطعه داده i دسترسي پيدا کند قرار بده six=six+1 )
4. اگر نودي که به آن دسترسي شده همان نود جاري باشد که قطعه داده در آن قرار دارد برو به مرحله 2 ( دسترسي محلي )
5. اگر شمارنده نود دور بيشتر از نودي باشد که قطعه داده در آن قرار دارد مالکيت اين قطعه داده همراه با آرايه مربوط به آن را به نود دور منتقل کن ( اگر نود x به قطعه داده i دسترسي پيدا کند و six>sij باشد قطعه داده i را به نود x بفرست )
6. برو به مرحله 2
شکل 5 : الگوريتم Optimal
مزيت الگوريتم Optimal استقلال نود مرکزي مي باشد بدين معنا که چون هر نود الگوريتم را به طور خودکار اجرا مي کند هيچ وابستگي به نود مرکزي وجود ندارد و تمامي نودها اهميت يکسان دارند. هر زمان که يک نود خراب شود الگوريتم مي تواند به عمليات خود به عمليات خود البته بدون وجود قطعه داده موجود در اين سايت ادامه دهد.[6]
الگوريتم optimal داراي دو عيب مي باشد : اول اينکه مشکل ذخيره سازي بالقوه وجود دارد با کاهش اندازه قطعه داده يا افزايش تعداد نودها اندازه ماتريس شمارنده دسترسي افزايش پيدا مي کند و اين افزايش سايز ماتريس باعث مي شود که به فضاي ذخيره سازي زيادي نياز داشته باشيم. مشکل دوم مشکل مقياس بندي براي نوع داده اي است که مقادير شمارنده دسترسي را ذخيره مي کنند . چون مقدار شمارنده دسترسي بطور مداوم افزايش پيدا مي کند ممکن است موجب ناهنجاري شود . مشکل بالقوه وقت يعني زمان انتقال قطعه هاي داده از يک سايت به سايت ديگر نيز وجود دارد و ممکن است به صورت نمايي افزايش پيدا کند . در الگوريتم Threshold فقط يک شمارنده براي براي هر قطعه داده ذخيره مي شود در مقايسه با الگوريتم Optimal اين الگوريتم فضاي ذخيره سازي کمتري نياز دارد چون براي هر قطعه داده فقط يک شمارنده ذخيره مي شود دو استراتژي براي انتخاب سايت اي که قرار است يک قطعه داده در آن قرار گيرد وجود دارد : يا اين به صورت تصادفي انتخاب شود و يا نودي که آخرين دسترسي را داشته است انتخاب شود در استراتژي اولين نودي که انتخاب مي شود ممکن است نودي باشد که قبلاً هرگز به اين قطعه داده دسترسي نداشته بود بنابراين استفاده از استراتژي دوم منطقي تر مي باشد .
در ابتدا قطعه هاي داده به طور تصادفي با استفاده از يک متد در بين نودها توزيع مي شود. يک مقدار آستانه t انتخاب مي شود ، سپس هر نود j براي هر قطعه داده i که در آن ذخيره شده است الگوريتم Threshold را اجرا مي کند اين الگوريتم به صورت زير مي باشد:[4]
الگوريتم Threshold :
1. براي هر قطعه داده که به صورت محلي ذحيره شده مقدار شمارنده را برابر صفر قرار بده ( براي هر قطعه داده i قرار بده si=0 )
2. درخواست دسترسي به قطعه داده را پراسس کن.
3. اگر اين دسترسي يک دسترسي محلي باشد مقدار شمارنده اين قطعه داده را دوباره صفر کن ( اگر نود j به قطعه داده i دسترسي پيدا کند قرار بده si=0 ) برو به مرحله 2
4. اگر اين دسترسي يک دسترسي دور باشد شمارنده مربوط به اين قطعه داده را يکي افزايش بده ( اگر قطعه داده i به صورت دور دسترسي شود قرار بده si=si+1
5. اگر شمارنده اين قطعه داده از مقدار حد آستانه بيشتر باشد اين شمارنده را صفر کن و آن را به نود دور منتقل کن ( اگر si>t قرار بده si=0 و قطعه داده را به نود دور منتقل کن)
6. برو به مرحله 2
شکل 5 : الگوريتم Threshold
نکته مهم در اين الگوريتم انتخاب حد آستانه مي باشد که روي انتقال قطعه هاي داده تاثير مي گذارد از الگوريتم بالا واضح است که اگر مقدار حد آستانه زياد باشد قطعه داده تمايل دارد که براي مدت طولاني در نود بماند و اگر مقدار حد آستانه کم باشد اين قطعه داده در نودهاي گوناگوني مستقر خواهد شد. نکته ديگري توزيع احتمالات دسترسي مي باشد اگر احتمالات دسترسي همه نودها براي يک قطعه داده يکسان باشد اين قطعه داده همه نودها را ملاقات خواهد کرد.[12]
در اين الگوريتم قطعه داده تمايل دارد که در نودي باقي بماند که بيشترين احتمال دسترسي دارد با افزايش احتمال دسترسي يک نود تمايل براي باقي ماندن قطعه داده در اين نود افزايش پيدا مي کند همچنين در اين الگوريتم با افزايش حد آستانه قطعه داده تمايل دارد که در نودي که بيشترين احتمال دسترسي دارد باقي بماند.
الگوريتم Near Neighborhood Allocation با حد آستانه نسبي (RTNNA):
الگوريتمNNA حالت خاصي از الگوريتم Optimal مي باشد در الگوريتم optimal تمام قطعه هاي داده با استفاده از يک متد استاتيک بين تمام سايتها توزيع مي شود سپس هر نود j براي قطعه داده i الگوريتم optimal را مطابق شکل 4 اجرا مي کند . مشکل اين الگوريتم ( optimal ) اين است که اگر الگوهاي تکرار دسترسي به قطعه هاي داده زياد باشد زمان زيادي براي انتقال قطعه هاي داده به نودهاي مختلف صرف مي شود بنابراين زمان پاسخ و تاخير افزايش پيدا مي کند در الگوريتم NNA اين مشکل حل مي شود در الگوريتم NNA شرايط لازم براي اينکه قطعه داده منتقل شود درست مانند الگوريتم optimal مي باشد اما مقصد يعني محلي که قرار است داده به آن منتقل شود فرق مي کند در اين روش توپولوژي شبکه و مسيريابي براي مشخص کردن مقصد در نظر گرفته مي شود به عبارت ديگر مقصد قطعه داده اي که مي خواهد منتقل شود نودي مي باشد که همسايه نود مبدا است و اين نود همسايه يعني نودي که قرار است قطعه داده به آن منتقل شود در مسيري قرار دارد که نودهاي موجود در اين مسير بيشترين دسترسي به اين قطعه داده را دارند در اين الگوريتم ( NNA ) از الگوريتم link state براي مسيربابي استفاده شده است با استفاده از اين روش انتقال مکرر قطعه هاي داده به دليل اينکه اين قطعه هاي داده در نودي قرار مي گيرد که براي همه نودهايي که به اين قطعه داده دسترسي دارند هزينه دسترسي ميانگين دارد کاهش مييابد بنابراين تاخير اين انتقالات کاهش مي يابد و زمان پاسخ بهتر مي شود [11]در الگوريتم NNA يک حد آستانه اي که مقدار آن برابر 5 بود براي انتقال قطعه هاي داده در نظر گرفته مي شد يعني اگر شمارنده مربوط به يک قطعه داده که توسط نودهاي ديگر دسترسي مي شد مساوي 5 مي شد اين قطعه داده با استفاده از الگوريتم هاي مسير يابي به يکي از نودهاي همسايه منتقل مي شد در حاليکه در الگوريتم RTNNA اين مقدار آستانه نسبي مي باشد بدين معنا که با توجه به مرحله دوم الگوريتم شمارنده ساده ( Simple Counter Algorithm ) تصميم گيري درباره انتقال قطعه داده به اين صورت انجام مي شود که سطرهاي يک بلاک در صورتي که شمارنده مربوط به آن بلاک در يک سايت بيشتر از سايتي باشد که بلاک هم اکنون در آن قرار دارد تصميم گيري درباره انتقال قطعه داده با استفاده از الگوريتم هاي مسير يابي انجام مي شود که در اين پروژه ما مانند الگوريتم NNA از الگوريتم link state استفاده کرديم براي اينکه مشخص کنيم که قطعه داده بايستي در کدام نود قرار گيرد که ميانگين دسترسي نودهاي ديگر به اين قطعه داده کمترين مقدار را داشته باشد در اين الگوريتم ( RTNNA ) بهبود قابل ملاحظه اي نسبت به الگوريتم NNA حاصل شد که نتايج آن در ادامه آورده شده است .
با توجه به شکل 6 فرض کنيد نود G ،H ،I وE به طور مکرر براي قطعه داده i که در نود A قرار دارد درخواست مي فرستند با توجه به الگوريتم RTNNA هنگامي که شمارنده مربوط به يکي از اين نودها بالاتر از بقيه نودها و نود مبدا باشد قطعه داده i به نود C منتقل مي شود اگر اين درخواستها بعد از انتقال قطعه داده ادامه پيدا کند قطعه داده به نود B منتقل مي شود اين روش ادامه پيدا مي کند تا وقتي که قطعه داده به نود G منتقل شود . با قرار گرفتن اين قطعه داده در نود G ، درخواستها از نودهاي G ،H ،I و E با کمترين تاخير و نه تاخير کمينه جواب داده مي شود در اين مرحله داده در يک وضعيت پايدار قرار مي گيرد بعد از اين مرحله اگر يکي از نودهاي H ،G وE بيشتر از ديگران درخواست قطعه داده بدهند اين قطعه داده در اين نود قرار مي گيرد .
شکل 6 : توپولوژي آزمايش
در آزمايشات انجام شده ما دو فاکتور در نظر مي گيريم : تاخير متوسط براي دريافت پاسخ از درخواست يک قطعه داده ( زمان پاسخ ) و زمان سپري شده براي انتقال داده از يک نود به نود ديگر ( زمان انتقال قطعه داده ) .
