بانکهای اطلاعاتی توزیع شده
(گزارش شماره 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 ها افزایش می یابد.