دانلود با لینک مستقیم و پر سرعت .
بانکهای اطلاعاتی توزیع شده
(گزارش شماره 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 ها افزایش می یابد.
با توجه به مطالبی که گفته شد در می یابیم که در عمل synchronization دو پارامتر پهنای باند و I/O نقش کلیدی بازی می کنند که این دو پارامتر در مقابل یکدیگرند. یعنی چنانچه پهنای باندکمی داشته باشیم برای رسیدن به سرعت synchronization بالا باید فضای دیسک بیشتری داشته باشیم و برعکس چنانچه فضای دیسک کمی با نرخ I/O پایین داشته باشیم باید برای رسیدن به سرعت بیشتر در synchronization پهنای باند بیشتری داشته باشیم.
علاوه بر پارامترهایی که ذکر شد پارامترهای دیگری نیز در سرعت synchronization دخالت دارند . برای مثال تعداد فایلهایی که باز میشود به علت سرباری که اطلاعات بخش header هر فایل دارد اهمیت دارد و برای کاهش تعداد فایلها و در نتیج کاهش میزان نقل و انتقال سربار می توان چند فایل را با هم یکی کرد. پارامتر دیگر تعداد connection هایی است که به سرور صورت می گیرد. اگر تعداد فایلها زیاد باشد تعداد connection ها نیز ممکن است زیاد باشد. لذا به کمک برخی تکنیکها می توان تعداد این connection ها را کم کرد. برای مثال چنانچه یکی از clientها سه جدول را در اختیار دارد اگر فایل مربوط به آن سه جدول در سمت سرور یک فایل باشد و به ازای هر جدول فایل جداگانه ای در نظر گرفته نشده باشد، در چنین شرایطی با یک connection و با یکبار باز کردن آن فایل می توان محتوای هر سه جدول را به یکباره و بدون سربارهای اضافی header و connection به سمت سرور فرستاد. حال با در نظر داشتن دو پارامتر اول به بررسی دو پارامتر اخیر می پردازیم و با فرض اینکه مساله چگونگی پیدا کردن تفاضل میان داده های روی سرور و داده های محلی روی client حل شده است و الان اطلاعات مورد نیاز برای update کردن هر کدام از client ها آماده است به بررسی متدهای مختلفی می پردازیم که با تکیه بر آنها می توانیم به حداکثر سرعت و در نتیجه کاهش زمان synchronization در شرایط مختلف بپردازیم. در مقاله [5] به بررسی سه مدل موجود برای گروه بندی جدولها یا به طور کلی آبجکت های اطلاعاتی بینclient های مختلف در سیستمی که معرفی شد پرداخته شده است و قدرت و ضعف این روشها در شرایط مختلف مورد تحلیل قرار گرفته است.
این سه مدل عبارتد از :
1- One-Per Object [OP]
2- Client-Centric [CC]
3- One-Giant [OG]
این مدلها بر اساس دسته بندی Update File ها بنا شده اند و علت این دسته بندی یکی کردن Update file هایی است که به صورت فیزیکی توسط هر client مورد دسترسی قرار خواهند گرفت . همانطور که قبلا هم گفته شد چنانچه یک client با n جدول سر و کار داشته باشد به ازای هر کدام از آن جدول ها در سمت سرور update file ای وجود خواهد داشت که اطلاعاتی که باید به سمت client فرستاده شود پس از محاسبات مربوطه در اینupdate file قرار دارد. حال مساله ای که وجود دارد این است که چنانچه این update file ها از همدیگر مجزا باشند برای ارسال آنها به صورت تک تک هزینه سربار برای connection و header فایل خواهیم داشت. از طرفی برخی از این Update file ها بین client های مختلف مشترک اند. برای روشن تر شدن موضوع فرض کنید Update file های 1تا 5 موجود باشند. client اول شماره های 1و2 را نیاز داشته باشد. client دوم شماره های 1و2و3و5 را نیاز داشته باشد و client سوم شماره های 4و5 را . در چنین شرایطی یکی کردن این Update file ها درون یک فایل ممکن نیست مگر اینکه به صورت فیزیکی شماره های 1و2 را در یک فایل قرار دهیم و در فایل دیگری شماره های 1و2و3و5 را و در فایل دیگری 4و5 را . این راه حل موجب افزونگی در نگهداری اطلاعات می شود و در نهایت 3 فایل خواهیم داشت که بخشهایی از آنها تکراری خواهد بود ولی در عوض هر کدام از client ها می‌توانند با ایجاد یک connectionو باز کردن یک فایل همه اطلاعات update خود را دریافت کنند. مسلما افزونگی ایجاد شده ممکن است در مواردی که با تنگنای دیسک روبرو هستیم مشکل آفرین باشد. پس راه حل دیگر این است که همه update file ها را در یک فایل بریزیم و آن فایل را به همه client ها ارسال کنیم و خود client ها اطلاعات به درد بخور را از آن استخراج کنند که این روش مسلما مشکل پهنای باند را به دنبال خواهد داشت . زیرا در هر بار فایل بزرگی که مقدار زیادی از آن بلا استفاده است به سمت clientها ارسال می شود. حال به مدل های ارائه شده در مقاله بازمی گردیم.
همانگونه که در شکل می بینید در اولین مدل که OP نام دارد هر Update file در فایل مجزایی نگه داشته می شود و لذا به ازای دسترسی به هرکدام از آنها باید یک connection برقرار شود. در دومین مدل به ازای هر client یک فایل در نظر گرفته می شود که update file های مربوط به آن client در آن فایل ریخته می شود و client کافی است که برای دسترسی به همه اطلاعات مورد نیازش فقط همان فایل را باز کند. در سومین مدل همه update file ها در یک فایل ریخته می شوند و همه client ها یک connection برای دسترسی به آن فایل ایجاد می کنند و همه فایل را دریافت می کنند و بخشهای مربوط به خود را استفاده می کنند.
همانگونه که گفته شد پارامترهای دیسک ، نرخ I/O، تعداد connection ها ، تعداد فایلها، پهنای باند و حجم Update file ها پارامترهای تعیین کننده ای هستند که مشخص می کنند استفاده از کدام مدل مناسب تر است.
در ادامه مقاله به مقایسه مدلهای ارائه شده با توجه به این پارامترها پرداخته شده است. ابتدا این مدلها از لحاظ میزان مصرف دیسک در تعداد client های مختلف با یکدیگر مقایسه شده اند.
همانطور که دراین نمودار می بینیم فقط در حالتی که یک client داریم روش CC از دو روش دیگر بهتر است. در این حالت روش OG به دلیل سربارheader فایل کمتر از OP بهتر است. اما همانگونه که مشاهده می نمایید با بالا رفتن تعداد client ها روش CC از دو روش دیگر بدتر می شود و این بدان دلیل است که به ازای هر client یک فایل که شامل تعدادی Update file است در سرور ساخته می شود و در واقع Update file ها تکراری تر می شوند. در این حالت مشاهده می شود که روش OG همواره اندکی از OP بهتر است و این به دلیل سربار ناشی از header فایلها است.
در این نمودار به مقایسه مدلها از لحاظ زمان لازم برای Synchronizationبا توجه به تعداد client ها در پهنای باند 57.6Kbps پرداخته شده است. همانگونه که می بینید در حالتی که یک Client داریم OP از دو مدل دیگر بدتر است و علت آن، تعداد connection های زیاد و زمانی است که برای برقراری این connection ها صرف می شود. در این حالت CC از OG بهتر است زیرا فقط Update file های مربوط به client را به یکباره برای آن ارسال می دارد ولی OG همه update fileها را به یکباره برای آن ارسال می دارد و باید از بین آنها update file های مربوط به خود را جدا نماید. در واقع این اختلاف اندک مابین ایندو به دلیل حجم اطلاعات ارسالی است.
با افزایش تعداد client ها مشاهده می شود که OG از دو روش دیگر به شدت بدتر می شود و این به دلیل پهنای باند پایین و ارسال همه update file ها به همه client ها می باشد. درواقع پهنای باند کمی داریم و در این پهنای باند کم اطلاعات اضافی زیادی فرستاده می شود که زمان Synchronization را به شدت افزایش می دهد. دو روش دیگر در این شرایط تقریبا مانند هم عمل می کنند.
فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد
تعداد صفحات این مقاله 48 صفحه
پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید
