دانلود با لینک مستقیم و پر سرعت .
در این پست می توانید متن کامل این پایان نامه را با فرمت ورد word دانلود نمائید:
نام تحقیق :
بانک اطلاعاتی توزیع شده
زیر نظر استاد محترم:
مهندس علیخانزاده
گرد آورنده:
اعظم شکوری نسب
مقدمه
بانک های اطلاعاتی توزیع شده متشکل از سایتهایی غیر وابسته هستند که هیچ منبعی را به صورت فیزیکی به اشتراک نمی گذارند. هر سایت می تواند در اجرای تراکنشی که منجر به دستیابی به اطلاعات یک یا تعداد بیشتری سایت دیگر می شود شرکت نماید. تفاوت اصلی مابین بانکهای اطلاعاتی متمرکز و توزیع شده این است که در بانکهای اطلاعاتی متمرکز همه اطلاعات در یک نقطه متمرکز شده است در حالی که در بانکهای اطلاعاتی توزیع شده ممکن است قسمتهای مختلف اطلاعات در نقاط مختلف توزیع شده باشند و یا اینکه کپی های مختلفی از اطلاعات در نقاط مختلف نگهداری شوند.
ذخیره اطلاعات به صورت توزیع شده
ذخیره اطلاعات به صورت توزیع شده به دو روش Replication یا Fragmentationو یا ترکیبی از این دو روش انجام می گیرد. در روش Replication دقیقا یک کپی فیزیکی از اطلاعات در نقاط مختلف سیستم یعنی سایر سایتها ذخیره می گردد ولی در روش Fragmentation اطلاعات به چند بخش یا پارتیشن تقسیم می شود و هر بخش در یکی از سایتها نگهداری می شود. در روش ترکیبی اطلاعات به چند بخش تقسیم می شوند و از تعدادی از بخشها و یا همه آنها کپی هایی در سایتهای مختلف نگهداری می شود. روش Fragmentation به دو طریق عمودی و افقی صورت می گیرد. در روش عمودی تقسیم بندی یک Relation روی فیلدها صورت می گیرد. یعنی هر بخش از اطلاعات مشتمل بر تعدادی از فیلدهای Relation است ولی در روش افقی تقسیم بندی روی رکوردهای Relation صورت می گیرد. برای مثال رکوردهای مربوط به ماه خرداد در یک بخش و رکوردهای مربوط به ماه تیر در بخش دیگری ذخیره می گردند. در روش عمودی برای دستیابی به Relation اولیه باید بین بخش های مختلف join بزنیم و در روش افقی برای دستیابی به آن باید از اجتماع استفاده نماییم.
محاسن روش Replication عبارتند از:
- در دسترس بودن : در شرایطی که یکی از سایتها بنا به دلیلی از بیفتد حداقل یک سایت دیگر وجود دارد که می تواند دسترسی به اطلاعات سایت از کار افتاده را امکان پذیر سازد. پس اگر درخواست دسترسی به اطلاعاتی که مربوط به یک سایت از کار افتاده است، صادر شود، پاسخگویی به این درخواست از طریق سایت دیگری که replication ای از سایت از کار افتاده را در اختیار دارد امکان پذیر می شود.
- افزایش توانایی موازی سازی : در صورتی که چندکپی از اطلاعات در سایتهای مختلف وجود داشته باشد در هنگام درخواست خواندن این اطلاعات می توان به صورت موازی بخشی از اطلاعات را از یک سایت و بخشهای دیگر آن را از سایتهای دیگر خواند و به این طریق عمل خواندن حجم زیادی از اطلاعات را به صورت موازی و با هزینه ای کمتر انجام داد.
معایب روش Replication :
- افزایش سربار بروزرسانی اطلاعات : به دلیل اینکه از یک داده کپی های مختلفی در سایتهای مختلف وجود دارد در هنگام تغییر دادن این داده باید همه کپی های آن را نیز تغییر داد تا سازگاری در کل سیستم حفظ شود که این کار سرباز زیادی به همراه دارد.
- پیچیدگی در مدیریت همزمانی : به دلیل اینکه از یک داده چند کپی وجود دارد مدیریت Lock در این روش پیچیدگی بیشتری را نسبت به روش متمرکز به همراه خواهد داشت.
به طور کلی روش Replication بازدهی عمل خواندن را بالا برده و در دسترس بودن ایجاد می کند ولی برای عمل نوشتن بهینه نیست و سربار اضافی دارد.
تراکنشهای توزیع شده
هر سایتی یک مدیر تراکنش دارد که وظیفه آن حفظ خصوصیت های ACID در همان سایت است. همچنین هر سایت یک هماهنگ کننده تراکنش (Transaction Coordinator) دارد که وظیفه آن این است که در مورد تراکنشهایی که از آن سایت شروع می شوند:
- تراکنش را شروع کند
- تراکنش را به تعدادی زیر تراکنش تقسیم کند و آنها را بین مدیران تراکنش سایتهای مربوطه توزیع کند.
- تراکنش را به پایان برساند یعنی یا آن را commit کند و یا در صورت commit نشدن تراکنش را در همه سایتهای شرکت کننده در آن Abort کند.
علاوه بر مشکلاتی که در سیستمهای متمرکز به وجود می آید مانند خطای نرم افزاری، خطای سخت افزاری، خطای دیسک و … نوع دیگری از خطاها در سیستم های توزیع شده وجود دارد که از این دست می توان به از کار افتادن یک سایت، گم شدن پیغامها، قطع شدن یک لینک ارتباطی و یا تقسیم شدن شبکه به دو بخش نا متصل اشاره نمود.
در سیستم توزیع شده ممکن است یک پیغام گم شود و یا خراب شود که برای رفع این مشکل از پروتکل های انتقالی مانند TCP استفاده می شود.
مدیریت همزمانی در بانکهای اطلاعاتی توزیع شده
همانطور که در یک سیستم متمرکز برای برقراری همزمانی مابین فراروندها از یک پروتکل Lock استفاده می کنیم در سیستمهای توزیع شده نیز از یک پروتکل Lock استفاده می کنیم با این تفاوت که این پروتکل برای سیستم های توزیع شده طراحی شده است. برخی از این پرتکل ها عبارتند از Single Lock Manager، Primary Copy، Majority Protocol، Biased Protocol و …
در Single Lock Manager یکی از سایتها را Lock Manager می کنیم. هر کس که بخواهد Lock یا Unlock بکند از این سایت درخواست می کند. وقتی سایتی درخواست Lock می کند اگر بتواند Lock را به آن می دهد و در غیر این صورت آن را در صف آن Lock قرار می دهد.
محاسن این روش عبارتند از : سادگی پیاده سازی و مدیریت Deadlock همانند روش متمرکز.
معایب این روش عبارتند از : تبدیل سایتی که مدیر Lock روی آن قرار دارد به گلوگاه سیستم و از کار افتادن کل سیستم در صورت از کار افتادن مدیر Lock.
در Primary Copy به ازای هر داده ای که از آن چند کپی در سیستم وجود دارد یک Primary Copy داریم و زمانی که می خواهیم Lock را بگیریم به سراغ Primary Copy می رویم.
عیب این روش این است که ممکن است سایتی که Primary Copy را در اختیار دارد از کار بیفتد ولی کپی آن موجود باشد. در این شرایط به دلیل اینکه Lock فقط باید روی Primary Copy گرفته شود لذا امکان تغییر داده وجود نخواهد داشت در حالی که باید بتوان داده را در کپی های آن در سایت های سالم تغییر داد.
در Majority Protocol باید برای گرفتن Lock از داده ای که n کپی از آن وجود دارد حد اقل به سراغ n/2+1 کپی از آن برویم و از آنها Lock بگیریم.
عیب این روش این است که ممکن است در حین Lock گرفتن روی یک داده هم بن بست به وجود بیاید. فرض کنید می خواهیم روی داده ای Lock بگیریم که 4 کپی از آن وجود دارد. اگر از دوتا از کپی ها Lock بگیریم و قبل از گرفتن Lock از سومی پروسه دیگری از دوتای دیگر Lock بگیرد در این شرایط دو پروسه منتظر همدیگر می مانند و برای دسترسی به یک داده بن بست به وجود می آید. این در حالی است که حتی در سیستم های متمرکز نیز برای دستیابی به یک داده به تنهایی به این شکل هیچگاه بن بست به وجود نمی آید.
در Biased Protocol بین خواندن و نوشتن تفاوت قائل می شویم. برای خواندن گرفتن Lock از هر کدام از سایتها کافی است اما برای نوشتن باید از تمام کپی ها Lock بگیریم. بازدهی این مکانیزم خود را در سیستمی به خوبی نشان می دهد که توالی خواندن در آن بیشتر از توالی نوشتن باشد.
مدیریت بن بست
همانگونه که در سیستم متمرکز از wait for graph استفاده می شود در اینجا نیز از همین روش استفاده می شود با این تفاوت که در اینجا باید wait for graph مربوط به همه سایتها را جمع کنیم و یک global wait for graph بسازیم. این کار بر عهده یکی از سایتها گذاشته می شود. در global wait for graph به دنبال دور می گردیم. چنانچه دوری پیدا شد یک یا چند تا از تراکنش ها را Abort یا Rollback می کنیم. مشکل اینجاست که این wait for graph به صورت آنلاین ساخته نمی شود و لذا ممکن است برای مثال دوری تشخیص داده شود در حالی که یکی از تراکنشها بنا به دلیلی Abort کرده باشد و در واقعیت دوری وجود نداشته باشد و به خاطر تشخیص اشتباهی که داده شده است یکی از تراکنشهای مفید که می توانسته به پایان برسد بیهوده Abort شود.
در هنگام به وجود آمدن بن بست برای اینکه بتوانیم بهترین و مناسب ترین تراکنش را برای Abort کردن انتخاب کنیم باید همه تراکنش ها و همه منابعی که آنها برای commit شدن نیاز دارند را بشناسیم. به این کار مساله پیدا کردن مجموعه مینیمم Abort می گویند که در به آن اشاره شده است. همچنین برای بالا بردن بازدهی کار می توان از مکانیزم check pointing استفاده نمود. در این روش به جای Abortکردن تراکنش در قسمتی از آن check point قرار می دهیم و در صورت لزوم به آن check point ، rollback می کنیم . این روش موجب می شود که حداقل تا حدودی از انجام دوباره کارهایی که تا به اینجا انجام شده است جلوگیری شود.
برای رفع مشکل Deadlock سه روش وجود دارد: Deadlock Prevention ، Deadlock Avoidance و Deadlock Detection and Resolution . تجربه نشان داده است که روشهای اول و دوم راههای مقرون به صرفه ای نیستند و در برخی از موارد نمی توان حتی آنها را عملی نمود. در عمل در جاهایی که مساله بن بست موضوع مهمی به شمار می رود از روش سوم یعنی Deadlock Detection and Resolution استفاده می شود. چنانچه در یک سیستم توزیع شده مرتبا از این مکانیزم استفده شود به دلیل رد و بدل شدن پیغامهای زیاد، بازدهی سیستم تا حد زیادی کاهش پیدا خواهد کرد و این در حالی است که ممکن است بن بست وجود نداشته باشد و مکانیزم جستجوی بن بست کار بیهوده ای انجام داده باشد. اگر هم این مکانیزم دیر به دیر استفاده شود، در زمانی که بن بست وجود دارد، بدون توجه به آن تراکنشهای جدید دیگری ممکن است به سیستم اضافه شوند و deadlock را توسعه دهند و لذا زمان Deadlock Resolution در چنین شرایطی به شدت افزایش خواهد یافت. در ثابت شده است پریود زمانی خاصی جود دارد که چنانچه عمل جستجوی بن بست مطابق با آن صورت گیرد بازدهی عمل مدیریت بن بست به حداکثر خود خواهد رسید. این توالی بهینه از O((αn)1/3) تبعیت می کند که در آن α نرخ به وجود آمدن بن بست در سیستم و n تعداد تراکنشها است.
(ممکن است هنگام انتقال از فایل ورد به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)
متن کامل را می توانید دانلود نمائید
چون فقط تکه هایی از متن پایان نامه در این صفحه درج شده (به طور نمونه)
ولی در فایل دانلودی متن کامل پایان نامه
همراه با تمام ضمائم (پیوست ها) با فرمت ورد word که قابل ویرایش و کپی کردن می باشند
موجود است
