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

(گزارش شماره 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] . اين روش موجب مي شود كه حداقل تا حدودي از انجام دوباره كارهايي كه تا به اينجا انجام شده است جلوگيري شود.