فهرست مطالب فصل1. مقدمه21-1. مقدمه32-1. بیان مسئله33-1. اهمیت گرید داده44-1. راهحلهای ممکن55-1. راهحل پیشنهادی56-1. سؤالات پایاننامه86-1. اهداف پایاننامه87-1. ساختار پایاننامه9فصل2. مروری بر سوابق پیشین102-1. مقدمه112-2. تکنیکهای تكثير داده112-3. چارچوبي براي تكثير دادهها12فصل3. الگوریتم تکثیر پویا در گرید داده با استفاده از واکشی اولیه دادهها293-1. مقدمه303-2. معماري PDDRA303-3. مراحل انجام الگوریتم PDDRA323-3-1. فاز 1: ذخیره‌سازی الگوي دسترسي فايل333-4. فاز 2 الگوريتم واكشي اوليه383-4-1. مسئوليت مدير به‌روزرسانی كپي403-4-2. ساختار سرور محلي و سايت‌هاي گريد413-5. فاز 3: جايگزيني463-5-1. الگوريتم جايگزيني PDDRA483-6. نتیجه گیری49فصل4. الگوریتم پیشنهادی504-1. مقدمه514-2 الگوریتم پیشنهادی تکثیر داده514-3. توصيف الگوريتم534-3-1. فاز اول: درخواست فايل و انجام عمل تكثير534-3-2 فاز دوم: جايگزيني54فصل5. شبیه‌سازی الگوریتم565-1 مقدمه575-2. شبیه‌سازی الگوریتم575-2-1 الگوهاي دسترسي595-2-2. فايل‌هاي پيكربندي تنظيمات اپتورسیم615-3. نتايج شبیه‌سازی625-3-1. پیادهسازی سيستم فازي635-4. ارزيابي عملكرد636-4. بهره‌وري از شبكه66فصل6. نتیجه گیری و پیشنهادات676-1. مقدمه686-2. راهحل پیشنهادی686-3. نتیجه‌گیری685-2. کارهای آتی69مراجع.. 70 فهرست شکلها/جدولهاعنوان صفحهشكل2- 1 گره سرور13شكل2- 2 گره مشتری13شكل2- 3 تعاملات بین گرهها 14جدول 2- 1. تعاملات پارامترها 15شكل2- 4 تصويري از تعامل بين گرهها16شكل3- 1. معماری PDDRA30شكل3-2. استفاده از ساختار درخت براي ذخيره ترتيب دسترسي36شكل3-3 . درج درخواست جدید در ساختار درخت38شكل3- 4. عبور پیام بین سایتهای گرید و سرور محلی42شكل3- 5. ساختار سرور محلی و سایتهای گرید43شکل4-1. توپولوژی گرید داده مورد استفاده 52شكل 5- 1. معماری OptorSim58شکل4-2. میانگین زمان اجرای کارها64شکل4-3. تعداد نسخههای تکثیر شده65شکل4-4. بهرهوری از شبکه66 چكيدهضرورت استفاده روزافزون از دادههای توزیعشده در شبکه‌هایکامپیوتری بر همگان مشخص است. تعداد بسيار زيادي از منابع محاسباتي و ذخيره‌سازي در كنار يكديگر قرار مي‌گيرند و گريد را تشكيل مي‌دهند. در سال‌هاي اخير تكنولوژي گريد رشد چشمگيري داشته به‌طوری‌که در اكثر تحقيقات و آزمايش‌هاي علمي مورد استفاده قرار گرفته است. چالش‌هاي بزرگي كه در گريد داده وجود دارد، نياز به دسترس پذيري بالا، كارآيي و مصرف پهناي باند پايين مي‌باشد. تكثير دادهها روشي است كه با استفاده از آن مي‌توان مسائلي از قبيل دسترسي به دادهها به صورت كارا و يا قابليت دسترس پذيري بالا را حل كرد. در يك محيطي كه از تكثير استفاده مي‌شود با افزايش تعداد نسخه‌هاي تكرار شده از فايل‌ها با بهتر شدن محلي بودن دادهها، كارآيي سيستم بهبود خواهد يافت.در این پایان نامه، روش‌های مختلف تکثیر داده پویا در شبکه‌های گرید داده بررسی شده و یك الگوريتم تكثير داده پويا در گريد پيشنهاد مي‌شود كه با بهره‌گيري از عوامل مؤثر بر تكثير دادهها، موجب كاهش زمان اجراي كارها و كاهش مصرف پهناي باند و هزينه نگهداري نسخه‌ها، میشود. اين الگوريتم در شبیه‌ساز اپتورسیم پیادهسازی شده است و نتايج حاصل از شبیه‌سازی نشان ميدهد كه پارامترهايي مانند ميانگين زمان اجراي كارها، تعداد نسخه‌هاي تكثيري و بهره‌وري بهبود داشته‌اند. كلمات كليدي: گريد داده، تكثير داده، جايگزيني، الگوي دسترسي، فاصله جغرافيايي، هزينه دسترسي فصل اولمقدمه 1-1. مقدمهدر طول زمان انواع مختلفی از سیستمهای توزیع شده[1] طراحی و پیادهسازی شده است، یکی از انواع سیستمهای توزیعشده سیستمهای گرید[2] است. ویژگی این فناوری این است که تمرکز آن بر روی به اشتراک گذاری منابع با مقیاس بزرگ است. تکثیر داده سرویسی از گرید داده است که برای سهولت و تسریع در دسترسی به دادهها به وجود آمده است. 2-1. بیان مسئلهامروزه در رشته‌هاي مختلف، مجموعه داده‌هاي بزرگ در حال تبديل به بخش مهمي از منابع مشترك هستند. در زمينه‌های گوناگون از جمله انرژيهای فيزيكي، بيوانفورماتيك، مشاهدات زمين، تغييرات جهاني آب و هوايي، پردازش تصوير و داده‌کاوی حجم عظيمي از داده‌هاي مورد نظر، با مقياس ترابايت و در برخي موارد با بتابايت اندازه‌گيري مي‌شوند. چنين حجم عظيمي از اطلاعات توسط محققان و دانشمندان به‌وسیله دستگاه‌هاي محاسباتي پيچيده قابل دسترسی است. این محققان و دستگاه‌هاي محاسباتي و ذخیره‌ساز در سراسر جهان توزیع شده‌اند.حجم عظيم اطلاعات و محاسبات مشكلات جديدي را در مورد دسترسي به دادهها، پردازش و توزيع آن‌ها به وجود مي‌آورد و با حجم زيادي داده، مكان‌هاي جغرافيايي مختلف و محاسبات پيچيده درگير مي‌شود که رويارويي با چالش زيرساخت‌هاي مديريتي را دشوار مي‌کند. گريد داده یک راه حل مناسب براي تمام مشكلات ذکر شده است گرید يك معماري براي مديريت توزیع شده و تجزیه‌وتحلیل مجموعه داده‌هاي علمي است.تعداد زيادي از منابع محاسباتي و ذخيره‌سازي در كنار يكديگر قرار مي‌گيرند و گريد را تشكيل مي‌دهند. موضوع و مسئله اصلي كه سبب شكل گرفتن تكنولوژي گريد شد به اشتراك‌گذاري منابع به صورت هماهنگ و حل مسائل و مشكلات در سازمان‌هاي مجازي پويا و چند نهادي بود. منظور و مقصود از به اشتراك‌گذاري، تنها مبادله فايل‌هاي ساده نبود بلكه هدف دسترسي مستقيم به كامپيوترها، نرم‌افزارها، دادهها و ديگر منابع موجود است. گريد دسترسي آسان به همه اين منابع را فراهم مي‌كند. 3-1. اهمیت گرید دادهانگيزه اصلي براي طراحي گريد داده اين بود كه نياز كاربران با حجم زیاد داده را پاسخ دهد، كاربران و منابع توزیع شده را تحت پوشش قرار دهد و تحليل‌هاي با حجم بالاي محاسبات را پاسخگو باشد[1].دسترسي مؤثر به چنين حجم عظيم داده كه به‌طور وسيع توزیع شده است، به دليل تأخیرات شبكه و مشكلات پهناي باند كند است. با رشد اندازه يك گريد، پيچيدگي اين سيستم افزايش مي‌يابد. چالش بزرگي كه در گريد داده به وجود مي‌آيد، نياز به دسترسی‌پذیری بالا، کارایی و صرفه‌جویی در ترافيك شبكه مي‌باشد.گريد داده براي برآوردن نيازهاي مجموعه داده‌هاي بزرگ، توزيع جغرافيايي كاربران و منابع و تجزیه‌وتحلیل محاسبات طراحي شده است. اين معماري همچنين براي مجموعه عمليات در نواحي وسيع و محيط‌هاي ناهمگن توسعه داده شده است. در گريد داده، كاربردهاي فني و علمي اغلب به دسترسي حجم زيادي اطلاعات نياز دارد. مديريت چنين حجم وسيعي داده توزیع شده در روش متمركز به دلیل اینکه حجم بالايي از بار به سرور مركزي تحميل مي‌شود كارایی لازم را ندارد. علاوه بر اينكه ذخیره‌سازی در سرور مركزي صورت می‌گیرد، مشكلاتي از قبيل خرابي در يك نقطه و تنگنا را نيز دارد. بنابراين، اين حجم زياد اطلاعات بايد در مكان‌هاي مختلف از سيستم توزيعي تكرار و توزيع شوند تا از این گونه مسائل و مشكلات جلوگيري گردد. گريد، داده را از نزدیک‌ترین سايت بازيابي مي‌كند و آن‌ها را براي سايت‌هاي درخواست‌کننده تكثير مي‌نماید.بهکمکگریددادهمیتوانحجمزیاددادهرادرنقاطمختلفدرسرتاسرگریدذخیرهوسپسبازیابینمود.در اینحالتکاراییگریدبهپهنایباندموجودوتأخیرزمانیشبکه بستگیدارد،به‌طوری‌کهپهنایباندکم، بینمحلذخیرهدادهومحلپردازشباعثناکارآمدیگریدمیگردد. 4-1. راهحلهای ممکنهمانطورکهمیدانیمزماندسترسیبهداده،بهپهنایباندارتباطیدرگریددادهبستگیدارد.دریکمحیطارتباطی، اصلیترینفاکتوربرایتضمیندسترسیسریعبه دادهها،عدمتأخیربالااست.برایکاهشزماندسترسیازراهکارهای مختلفیاستفادهمی‌شود،ازجملهاینراهکارهامیتوانبهاستفادهازبرنامهریزیکاراشارهکرد.یکبرنامه‌ریزخوبمی‌تواندتاجاییکهممکناستهزینههایانتقالدادهرابرایدسترسیسریعتربااجرایکاردرمحلمناسبکاهشدهد.راه‌حلدیگراستفادهازمکانیسمتکثیر[3]استکهباایجادکپیهایی[4]ازیکنسخهباعثافزایشسرعتدسترسیبهآنمی‌شود،در واقعبرایافزایشکاراییمی‌توان چندیننسخهازفایل‌ها رادرسراسرگریدذخیرهکرد[2]. 5-1. راهحل پیشنهادیدر واقع با رشد اندازه گريد پيچيدگي ساختار هم افزايش مي‌يابد. دسترسي بالا به دادهها يك چالش عمده در گريد است. برنامه‌هاي محاسباتي كاربران مقدار بسيار زيادي داده دارند. نگهداري محلي يك كپي از داده بسيار گران قیمت و غيرعملي است. مقابله با تأخيرات شبكه و محدوديت ظرفيت ذخیره‌سازی[5] در سايت‌هاي مختلف براي تأمین دسترسي بالا يك چالش دشوار است. براي پاسخ به چالش دسترسي، تكثير داده از روش‌هاي عمده به شمار مي‌رود كه دسترسی‌پذیری بالا، مصرف پهناي باند، افزايش تحمل خطا و بهبود مقیاس‌پذیری و زمان پاسخ را ترويج ميدهد [9-3]. هنگامی‌که دادهها تكثير مي‌شوند، یک كپي از فايل‌هاي داده در مكان‌هاي مختلف از گريد داده قرار مي‌گيرد، تكثير مي‌تواند موجب صرفه‌جویی مقدار زيادي پهناي باند در مقايسه با اين شرط كه داده فقط در يك سايت موجود باشد، شود. از این رو براي تأمین دسترسي همیشگی و سريع به دادهها تكثير داده معاوضه بسيار خوبي بين حافظه در دسترس و پهناي باند موجود مي‌باشد [10].تكثير داده روشي معمول براي اصلاح کارایی در دسترسي دادهها در سيستم‌هاي توزيعي است. ايجاد نسخه تكراري نه‌تنها مصرف پهناي باند را كاهش ميدهد، بلكه تأخير دسترسي را نيز كاهش ميدهد. به‌بیان‌دیگر، افزايش کارایی خواندن داده از گره‌هاي[6] متناسب، هدف اصلي الگوريتم‌هاي تكثير داده است.علاوه بر اين مي‌توان دسترسي به دادهها، قابليت اطمينان، مقیاس‌پذیری سيستم، تعادل بار با انجام تكثير و صف آن‌ها را در ميان سايت‌هاي مختلف را افزايش داد [11].فوايد اصلي تكثير عبارت‌اند از: [12]1. دسترس‌پذیری بهتر: هنگام خطاي يك گره، سيستم مي‌تواند از گره ديگري به داده دسترسي داشته باشد كه دسترس‌پذیری را نیز بهتر مي‌كند.2. کارایی بهتر: به خاطر اينكه داده ميان چندين گره تكرار شده است، كاربر مي‌تواند داده را از نزدیک‌ترین گره يا گرهی كه بار كاري کمتری دارد، به دست آورد.تكنيك‌هاي تكثير داده مي‌توانند به دو بخش اصلي، تكثير استاتيك[7] و تكثير ديناميك[8] طبقه‌بندی شوند. در تكثير استاتيك تعداد كپي‌ها و گره ميزبان به صورت استاتيك در ابتدا انتخاب مي‌شوند و كپي بيشتري بعد از آن ايجاد نمي‌شود. از سوي ديگر استراتژي پويا، مي‌تواند با توجه به ظرفيت ذخیره‌سازی و پهناي باند، كپي را در گره جديدي ايجاد کند يا خودش را با تغييرات منطبق سازد و با توجه به درخواستها، كپي‌هايي كه ديگر مورد نیاز نيست را حذف نمايد. در تكثير داده ايستا يك نسخه تكراري تا زماني كه توسط كاربر پاك يا طول عمرش منقضي شود موجود هست. نقص تكثير ايستا زماني است كه الگوي دسترسي گرهها مرتب تغيير مي‌كند و الگوريتم‌هاي ايستا توانايي سازگاري با شرايط جديد را ندارند. پس از اينكه يك كپي در يك سايت ايجاد شد تا زماني كه توسط كاربر حذف شود در آن مكان قرار مي‌گيرد. در روش‌هاي استاتيك تعيين محل كپي در زمان طراحي صورت مي‌گيرد و اين مكان غيرقابل تغيير مي‌باشد [13].اشكال روش‌هاي تكثير استاتيك اين است كه آن‌ها نمي‌توانند خودشان را با رفتار كاربران وفق دهند، در واقع آن‌ها براي حجم زيادي داده و تعداد زيادي كاربر مناسب نيستند.اما در تكثير پويا، ايجاد نسخه‌هاي تكرار، حذف و مديريت آن‌ها خودكار است و قابليت سازگاري با تغيير شرايط رفتار كاربر را دارد [14]. استراتژي‌هاي پويا بهتر از استاتيك هستند چون آن‌ها مي‌توانند به صورت هوشمند در مورد مكان قرار گرفتن اطلاعات در گريد تصمیم‌گیری كنند. البته اشكالاتي هم وجود دارد؛ يك مركز تصمیم‌گیری متمركز مورد نیاز است كه اطلاعات را در زمان اجرا از تمام گره‌هاي موجود در گريد جمع‌آوری كند، اگر گرهها در گريد داده وارد شوند و استفاده نشوند بار واحد تصمیم‌گیری مركزي افزايش مي‌يابد.البته استراتژي‌هاي تكثير استاتيك مزيت‌هايي نظیر سرعت بالاتر از روش‌هاي پويا و زمان‌بندی كار را دارند. شبكه‌هاي گريد سيستم‌هاي ديناميك هستند و درخواست‌هاي كاربران در طول زمان متغير می‌باشد تكثير پويا براي اين سيستم‌ها مناسب‌تر است.