پايان نامه رشته كامپيوتر با موضوع بانك اطلاعاتي توزيع شده

یکشنبه ۱۴ آبان ۹۶ | ۲۲:۵۰ ۳۰ بازديد

پايان نامه رشته كامپيوتر با موضوع بانك اطلاعاتي توزيع شده

براي توضيحات بيشتر و دانلود كليك كنيد

دسته:

كامپيوتر و IT
بازديد: 1 بار
فرمت فايل: docx
حجم فايل: 319 كيلوبايت
تعداد صفحات فايل: 91

دانلود كامل پايان نامه رشته كامپيوتر با موضوع بانك اطلاعاتي
توزيع شده

=======================================================
تمامي فايل هاي سيستم، توسط كاربران آن آپلود مي شود. اگر در
فايلي تخلفي مشاهده كرديد و يا مالك پزوژه اي
بوديد كه از وجود آن در سايت رضايت نداشتيد با ما تماس بگيريد، در
اسرع وقت به گزارش شما رسيدگي مي شود.
=======================================================
info@cero.ir
|| cero.ir@yahoo.com
|| filecero@gmail.com
|| فرم تماس با
ما
=======================================================

بانكهاي اطلاعاتي توزيع
شده

(گزارش شماره 1)

در اين گزارش مباحثي كلي در مورد بانكهاي
اطلاعاتي توزيع شده، معماريهاي آنها و مسائل و مشكلاتي كه هنگام
حركت از بانكهاي اطلاعاتي متمركز به سمت بانكهاي اطلاعاتي توزيع
شده با آنها روبرو هستيم صحبت شده و تعدادي از كارهاي جديدي كه در
زمينه برطرف شدن مشكلات مربوطه انجام شده شرح داده شده است. از
جمله يك كار جديدي كه در زمينه سنكرون كردن داده هاي كپي شده
انجام شده در انتهاي اين گزارش شرح داده شده
است.

فهرست مطالب اين گزارش :

1. ذخيره اطلاعات به صورت توزيع
شده

2. تراكنشهاي توزيع شده

3. مديريت همزماني در بانكهاي اطلاعاتي توزيع
شده

4. مديريت بن بست

5. سنكرون كردن اطلاعت كپي
شده

6. منابع

مقدمه

بانك هاي اطلاعاتي توزيع شده متشكل از سايتهايي
غير وابسته هستند كه هيچ منبعي را به صورت فيزيكي به اشتراك نمي
گذارند. هر سايت مي تواند در اجراي تراكنشي كه منجر به دستيابي به
اطلاعات يك يا تعداد بيشتري سايت ديگر مي شود شركت نمايد. تفاوت
اصلي مابين بانكهاي اطلاعاتي متمركز و توزيع شده اين است كه در
بانكهاي اطلاعاتي متمركز همه اطلاعات در يك نقطه متمركز شده است
در حالي كه در بانكهاي اطلاعاتي توزيع شده ممكن است قسمتهاي مختلف
اطلاعات در نقاط مختلف توزيع شده باشند و يا اينكه كپي هاي مختلفي
از اطلاعات در نقاط مختلف نگهداري شوند[1].

1. ذخيره اطلاعات به صورت توزيع
شده

ذخيره اطلاعات به صورت توزيع شده به دو روش
Replication يا Fragmentationو يا تركيبي از اين دو روش انجام مي
گيرد. در روش Replication دقيقا يك كپي
فيزيكي از اطلاعات در نقاط مختلف سيستم يعني ساير سايتها ذخيره مي
گردد ولي در روش Fragmentation‌ اطلاعات
به چند بخش يا پارتيشن تقسيم مي شود و هر بخش در يكي از سايتها
نگهداري مي شود. در روش تركيبي اطلاعات به چند بخش تقسيم مي شوند
و از تعدادي از بخشها و يا همه آنها كپي هايي در سايتهاي مختلف
نگهداري مي شود. روش Fragmentation به دو
طريق عمودي و افقي صورت مي گيرد. در روش عمودي تقسيم بندي يك
Relation روي فيلدها صورت مي گيرد. يعني
هر بخش از اطلاعات مشتمل بر تعدادي از فيلدهاي Relation است ولي در روش افقي تقسيم بندي روي
ركوردهاي Relation صورت مي گيرد. براي
مثال ركوردهاي مربوط به ماه خرداد در يك بخش و ركوردهاي مربوط به
ماه تير در بخش ديگري ذخيره مي گردند. در روش عمودي براي دستيابي
به Relation اوليه بايد بين بخش هاي مختلف
join بزنيم و در روش افقي براي دستيابي به
آن بايد از اجتماع استفاده نماييم.

محاسن روش Replication
عبارتند از:

–
در دسترس بودن :‌ در شرايطي كه يكي از سايتها بنا به دليلي از
بيفتد حداقل يك سايت ديگر وجود دارد كه مي تواند دسترسي به
اطلاعات سايت از كار افتاده را امكان پذير سازد. پس اگر درخواست
دسترسي به اطلاعاتي كه مربوط به يك سايت از كار افتاده است، صادر
شود، پاسخگويي به اين درخواست از طريق سايت ديگري كه replication اي از سايت از كار افتاده را در اختيار
دارد امكان پذير مي شود.

–
افزايش توانايي موازي سازي : در صورتي كه چندكپي از اطلاعات در
سايتهاي مختلف وجود داشته باشد در هنگام درخواست خواندن اين
اطلاعات مي توان به صورت موازي بخشي از اطلاعات را از يك سايت و
بخشهاي ديگر آن را از سايتهاي ديگر خواند و به اين طريق عمل
خواندن حجم زيادي از اطلاعات را به صورت موازي و با هزينه اي كمتر
انجام داد.

معايب روش Replication
:

1-
افزايش سربار بروزرساني اطلاعات :‌ به دليل اينكه از يك داده كپي
هاي مختلفي در سايتهاي مختلف وجود دارد در هنگام تغيير دادن اين
داده بايد همه كپي هاي آن را نيز تغيير داد تا سازگاري در كل
سيستم حفظ شود كه اين كار سرباز زيادي به همراه
دارد.

2-
پيچيدگي در مديريت همزماني :‌ به دليل اينكه از يك داده چند كپي
وجود دارد مديريت Lock در اين روش پيچيدگي
بيشتري را نسبت به روش متمركز به همراه خواهد
داشت.

به طور كلي روش Replication بازدهي عمل خواندن را بالا برده و در
دسترس بودن ايجاد مي كند ولي براي عمل نوشتن بهينه نيست و سربار
اضافي دارد.

2. تراكنشهاي توزيع شده

هر سايتي يك مدير تراكنش دارد كه وظيفه آن حفظ
خصوصيت هاي ACID در همان سايت است. همچنين
هر سايت يك هماهنگ كننده تراكنش (Transaction
Coordinator) دارد كه وظيفه آن اين است كه در مورد
تراكنشهايي كه از آن سايت شروع مي شوند:

1-
تراكنش را شروع كند

2-
تراكنش را به تعدادي زير تراكنش تقسيم كند و آنها را بين مديران
تراكنش سايتهاي مربوطه توزيع كند.

3-
تراكنش را به پايان برساند يعني يا آن را commit كند و يا در صورت commit نشدن تراكنش را در همه سايتهاي شركت كننده در
آن Abort‌ كند.

علاوه بر مشكلاتي كه در سيستمهاي متمركز به
وجود مي آيد مانند خطاي نرم افزاري، خطاي سخت افزاري، خطاي ديسك و
… نوع ديگري از خطاها در سيستم هاي توزيع شده وجود دارد كه از
اين دست مي توان به از كار افتادن يك سايت، گم شدن پيغامها، قطع
شدن يك لينك ارتباطي و يا تقسيم شدن شبكه به دو بخش نا متصل اشاره
نمود.

در سيستم توزيع شده ممكن است يك پيغام گم شود و
يا خراب شود كه براي رفع اين مشكل از پروتكل هاي انتقالي مانند
TCP استفاده مي شود.

3. مديريت همزماني در بانكهاي اطلاعاتي توزيع
شده

همانطور كه در يك سيستم متمركز براي برقراري
همزماني مابين فراروندها از يك پروتكل 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 بگيريم. بازدهي
اين مكانيزم خود را در سيستمي به خوبي نشان مي دهد كه توالي
خواندن در آن بيشتر از توالي نوشتن باشد.

4. مديريت بن بست

همانگونه كه در سيستم متمركز از wait for graph استفاده مي شود در اينجا نيز از همين
روش استفاده مي شود با اين تفاوت كه در اينجا بايد wait for graph مربوط به همه سايتها را جمع كنيم و
يك global wait for graph بسازيم. اين كار
بر عهده يكي از سايتها گذاشته مي شود. در global
wait for graph به دنبال دور مي گرديم. چنانچه دوري پيدا
شد يك يا چند تا از تراكنش ها را Abort يا
Rollback مي كنيم. مشكل اينجاست كه اين
wait for graph به صورت آنلاين ساخته نمي
شود و لذا ممكن است براي مثال دوري تشخيص داده شود در حالي كه يكي
از تراكنشها بنا به دليلي Abort كرده باشد
و در واقعيت دوري وجود نداشته باشد و به خاطر تشخيص اشتباهي كه
داده شده است يكي از تراكنشهاي مفيد كه مي توانسته به پايان برسد
بيهوده Abort شود.

در هنگام به وجود آمدن بن بست براي اينكه
بتوانيم بهترين و مناسب ترين تراكنش را براي Abort كردن انتخاب كنيم بايد همه تراكنش ها و همه
منابعي كه آنها براي commit شدن نياز
دارند را بشناسيم. به اين كار مساله پيدا كردن مجموعه مينيمم
Abort مي گويند كه در[2] به آن اشاره شده
است. همچنين براي بالا بردن بازدهي كار مي توان از مكانيزم
check pointing استفاده نمود. در اين روش
به جاي Abort‌كردن تراكنش در قسمتي از آن
check point قرار مي دهيم و در صورت لزوم
به آن check point ، rollback مي كنيم[3] . اين روش موجب مي شود كه حداقل
تا حدودي از انجام دوباره كارهايي كه تا به اينجا انجام شده است
جلوگيري شود.

براي رفع مشكل Deadlock
سه روش وجود دارد: Deadlock Prevention ،
Deadlock Avoidance و Deadlock Detection and Resolution . تجربه نشان
داده است كه روشهاي اول و دوم راههاي مقرون به صرفه اي نيستند و
در برخي از موارد نمي توان حتي آنها را عملي نمود. در عمل در
جاهايي كه مساله بن بست موضوع مهمي به شمار مي رود از روش سوم
يعني Deadlock Detection and Resolution
استفاده مي شود. چنانچه در يك سيستم توزيع شده مرتبا از اين
مكانيزم استفده شود به دليل رد و بدل شدن پيغامهاي زياد، بازدهي
سيستم تا حد زيادي كاهش پيدا خواهد كرد و اين در حالي است كه ممكن
است بن بست وجود نداشته باشد و مكانيزم جستجوي بن بست كار بيهوده
اي انجام داده باشد. اگر هم اين مكانيزم دير به دير استفاده شود،
در زماني كه بن بست وجود دارد، بدون توجه به آن تراكنشهاي جديد
ديگري ممكن است به سيستم اضافه شوند و deadlock را توسعه دهند و لذا زمان Deadlock Resolution در چنين شرايطي به شدت افزايش
خواهد يافت. در [4] ثابت شده است پريود زماني خاصي جود دارد كه
چنانچه عمل جستجوي بن بست مطابق با آن صورت گيرد بازدهي عمل
مديريت بن بست به حداكثر خود خواهد رسيد. اين توالي بهينه از
O((αn)1/3) تبعيت مي كند كه در آن
α نرخ به وجود آمدن بن بست در سيستم و
n تعداد تراكنشها
است.

5. سنكرون كردن اطلاعت كپي
شده

در اين بخش به بررسي روشهايي كه براي سنكرون
كردن تعدادي client كه به يك سرور مركزي
متصل مي شوند و اطلاعات خود را با آن سنكرون مي كنند مي پردازيم.
فرض كنيد تعدادي client داريم كه هر كدام
به بخشي از اطلاعات سرور نياز دارند و اين اطلاعات را پس از
دريافت از سرور درون خود به صورت Local
نگهداري مي كنند. هر client بنا به نياز
اطلاعات Local خود را update مي كند. در بازه هاي زماني خاصي client ها update هاي خود را
به سمت سرور مي‌فرستند. update ها حتي مي
توانند بلافاصله به سمت سرور فرستاده شوند كه اين بستگي به مبايل
يا غير مبايل بودن آنها دارد زيرا در سيستم هاي مبايل اصولا براي
هر بار ارسال مقداري انرژي سربار مصرف مي شود ممكن است به صرفه
اين باشد كه اطلاعات هر چند گاه يكبار به سمت سرور ارسال شود. حال
فارغ از اينكه سياست ارسال Update ها از
سوي client ها به سمت سرور چگونه است به
اين مساله مي پردازيم كه سرور چگونه client ها را با هم سنكرون مي كند.براي روشن
تر شدن مساله فرض كنيد client1 و
client2 هر دو جدول A را از سرور دريافت كرده و در حافظه محلي خود نگه
داشته اند. client1 سه ركورد به جدول محلي
خود اضافه مي كند و client2 چهار ركورد به
جدول محلي خود اضافه مي كند و يكي از ركوردهاي جدول محلي خود را
نيز update مي كند بعد از مدتي و يا به
طور همزمان با تغييرات هر كدام از client
ها اطلاعات update شده خود را به سرور مي
فرستند. سرور بايد بعد از اينكه اطلاعات همه را دريافت كرد، در
بازه هاي زماني خاصي اطلاعات به روز شده را به همه client ها ارسال كند تا client1 از تغييراتي كه client2 در جدول محلي خود داده بود با خبر شود و
برعكس client2 نيز از تغييراتي كه
client1 در جدول محلي خود داده بود آگاهي
يابد. حال مشكل اينجاست كه عمل ارسال اطلاعات از سرور به
client ها چگونه و به چه روشي صورت گيرد
تا بهترين بازده را داشته باشد. همانطور كه مي دانيم سرور بايد
اطلاعات بروز شده را به تك تك client ها
ارسال كند و چون اين عمل به صورت سريال انجام مي‌شود لذا افزايش
تعداد client ها مي تواند مدت زمان عمل
synchronization را بسيار طولاني نمايد.
فرض كنيد كه client‌ها مبايل باشند و
پهناي باند ارتباطي نيز كم باشد و ارسال اطلاعات به روز شده به
سمت هر client حدود 30 ثانيه طول بكشد. در
چنين شرايطي چنانچه 100 عددclient داشته
باشيم زمان synchronization در بهترين
حالت 3000 ثانيه به طول مي‌انجامد. البته اين در حالتي است كه
سرور تمام جدول بروز شده جديد را براي تك تك client ها ارسال كند. علت اين امر اين است كه سرور
نمي داند كه هر كدام از client ها نسبت به
قبل چه تغييري كرده اند. اگر بخواهيم كاري كنيم كه سرور قادر باشد
اين مطلب را بفهمد بايد به ازاي هر client
يك نسخه جدول را روي سرور نگهداري كنيم و اين نسخه از جدول همواره
با محتواي موجود در حافظه محلي client‌
مطابقت داشته باشد. يعني هر بار كه سرور اطلاعات update از يك client
دريافت مي كند قبل از اينكه update را روي
جدول اصلي اعمال كند آن را روي جدول معادل با آن client روي سرور update كند.
به اين ترتيب هميشه در سمت سرور مي دانيم كه جدول محلي client نسبت به جدول سرور چه تغييري بايد بكند و لذا
فقط تغييرات را براي آن مي فرستيم و اين عمل صرفه جويي زيادي در
پهناي باند مي كند و سرعت synchronization
را نيز افزايش مي دهد ولي اين روش نياز به فضاي زيادي روي
Hard Disk دارد و در عين حال I/O‌ بيشتري دارد واين فضاي مورد نياز با افزايش
تعداد client ها افزايش مي
يابد.