داده ی توزیع شده

سیستم­های پایگاه داده­ی توزیع شده

مقدمه

 

برای طراحی یک سیستم کارا و قابل اعتماد پایگاه داده ی توزیعی
تحقیقات و تلاش های بسیاری صورت گرفته است. در اینجا به یکی از جنبه های
مهم این تحقیقات یعنی پردازش تراکنشها شامل ارتباط, همروندی, اتمیک بودن,
Replication و ترمیم می پردازیم و می کوشیم پیاده سازی این اصول را در
سیستمهای مختلف توزیعی تجاری بررسی کنیم.

سیستمهای پایگاه های داده ی توزیعی برای برنامه های کاربردی
ای هستند که داده ها و دستیابی های به آنها در حالت توزیع شده هستند و
نیازمند آن هستیم که در دسترس بودن داده ها را در زمان مواجهه با شکست و
خطا حفظ کنیم. یک مثال ساده از از این سیستمها, سیستمهای رزرو بلیط هواپیما
و سیستمهای مالی توزیع شده هستند.

طراحان پایگاه داده معمولا می کوشند به وسیله ی Replicate و
توزیع داده ها آنها را در مقابل   های سیستم حفظ کنند. اما Replication
باعث ایجاد افزونگی و احتمال بیشتر  می شود و نیز مدیریت و پیاده سازی آن
بسیار پیچیده است [۱ ].

سیستمهای متعددی هستند که اصول طراحی این سیستمها را رعایت نموده اند: SDD-1 , سیستمهای Ingres توزیع شده, سیستمهای R* و Raid.

مسایل و مفاهیم زیادی در طراحی پایگاه های داده ی توزیعی باید
مورد توجه قرار گیرد مانند نام گذاری, ارتباطات, کنترل متمرکز و
غیرمتمرکز, همروندی, فابلیت اعتماد, replication , اتمیک بودن, و مفاهیم
تراکنشها و تراکنشهای تودرتو.

همچنین تکنیکهای مختلف توزیع داده ها و بهینه سازی پرس و جوها باید مورد توجه قرار گیرد.

در اینجا کوشش می شود نحوه ی استفاده از این تکنیکها و مفاهیم
برای طراحی و پیاده سازی یک سیستم پایگاه داده ی مناسب و کارا و نیز یک
سیستم مدیریت تراکنش کارا مورد توجه قرار گیرد.

بطور خلاصه مفاهیمی را که برای یک پیاده سازی موثر لازم
است را مرور می کنیم, مفاهیمی مانند ساختار/معماری سیستم, نرم افزار
ارتباطی, همروندی و مدیریت replication در برابر  ها است [۱].

۱-   ساختار

دو ساختار مختلف برای سیستم ها وجود دارد : سیستمهای برمبنای شیء  و سیستمهای Server based .

در ساختارهای برمبنای شیء   , فرآیندها شیء هارا مدیریت می
کنند. مثلا ممکن است یک فرآیند دستیابی همروند به یک شیء   را مدیریت می
کند و یا امکان را برای آن فراهم می کند, زیرا تراکنشها مسئول این کار
نیستند. شیء   ها مکانیسمهای مناسبی برای جداسازی داده ها و کپسوله کردن
اعمال انجام شده روی آنها می باشند. مثالهایی از سیستمهای برمبنای شیء  ,
سیستمهای Clouds, Eden و Isis هستند.

در ساختار های Server based ,فرآیندها برای اعمال مختلف مانند
سرور عمل می کنند. بطور مثال یک سرور کنترل همروندی می تواند
serializability را برای همه ی تراکنشها فراهم کند. سرور کنترل هم تضمین می
کند که همه ی آیتمهای پایگاه داده در حالت امن و مناسب روی دستگاههای
ذخیره سازی نوشته می شوند. مثال سیستمهای Server based , SDD-1  و Raid
هستند.

۲-   سرویسهای ارتباطی

 

بخاطر مسایل کارایی بسیاری از سیستمهای توزیع شده نرم
افزارهای ارتباطی مخصوص خود را دارا می باشند. در زیرسیستمهای ارتباطی,
سرویسهای سطوح بالا و پایین و ابتدایی فراهم می شوند.

در این بخش گزینه های سرویس انتقال, اصول ارتباطی و مفاهیم آنها را بررسی می کنیم.

۲-۱ سرویس انتقال سطح پایین

سرویس انتقال یک قابلیت انتقال داده بین فرآیندها فراهم می کند. دو مدل مفهومی برای انتقال وجود دارد: مدل مدار مجازی به وسیله یک مدل از کنترل خطا, یک انتقال مطمئن را بین فرآیندها فراهم می کند و مدل دیتاگرام  برمبنای
بهترین تلاش انتقال بسته های منفرد را انجام می دهد که این کار لزوما
مطمئن نیست. انتخاب یکی از این دو مدل کاملا وابسته به تصمیمات و اصول
طراحی است.

بسیاری از سیستمهای توزیعی مانند Locus , از مدل دیتاگرام
استفاده می کنند(بخاطر دلایل کارایی). یکی از دلایل عمده ی این کار این است
که در این شبکه ها احتمال خطا بسیار پایین و احتمال تحویل درست بسته بسیار
بالاست.  در بسیاری از حالات سرویس انتقال, تنها با استفاده ازRPC استفاده
می شود که ارتباط بین فرآیندهابه شکل درخواست و پاسخ است. کنترل جریان و
خطا میتواند در سرویسهای لایه های بالاتر تجمیع شود. مدیریت اتصال و ack
های لایه ی پایین تر در مدار مجازی یک سربار اضافه ایجاد می کند. بنابراین
یک نرم افزار ویژه در لایه بالاتر باید مسئول انجام این امور باشد.

بعضی از سیستمهای توزیعی از مدار مجازی در سرویس انتقال خود
استفاده می کنند. بطور مثال R* از پروتکل مدار مجازی استفاده می کند. مدار
های مجازی نه تنها کنترل خطا و جریان را انجام می دهند, بلکه اعمالی نظیر
شناسایی و ترمیم خطا را نیز انجام می دهند. البته R* از دیتاگرام هم
استفاده می کند.

۲-۲    اصول اولیه ارتباط

دو اصل اولیه ارتباط وجود دارد: message passing و Remote
Procedure Call(RPC). سیستمهایی مانندCamelot و Locus از اصول اولیه ی
send و receive استفاده می کنند و R* هم از RPC استفاده می کنند.

استفاده از اصول message-based مزایا ی خودرا درپشتیبانی
برنامه های کاربردی و زبانهای برنامه نویسی مختلف دارد, اما یک مکانیسم
تعامل inter-module درمحیطهای توزیعی معرفی می کند که متفاوت از RPC است.

ازتباط بین فرایندی می تواند همزمان و غیرهمزمان باشد. در
واقعترمهای یکسان در سطوح مختلف استفاده می شوند. درسطح message passing یک
ارسال همزمان به این معنی است که فرستنده تازمان دریافت پیام توسط گیرنده
بلاک می شود. بدین ترتیب نه تنها داده ها انتقال می یابند بلکه فرستنده و
گیرنده نیز همزمان می شوند. در حالت غیرهمزمان فرستنده پس از ارسال پیام
دیگر منتظر دریافت آن توسط گیرنده نمی شود و بدین ترتیب درجه ی موازی گری
بالاتر می رود اما ممکن است مشکلات ازدحام به وجود آید. ممکن است همزمانی
در لایه های بالاتر انجام شوند, مانند RPC .

اینجا همزمانی به این معنی است که فرآیند فرستنده پس از ارسال
تا زمان دریافت پیام توسط گیرنده بلاک می شود ولی در حالت غیر همزمان
اینگونه نیست.

۲-۳    مفاهیم قابلیت اعتماد اصول ارتباطی

درحالتیکه مشکل از کارافتادن پردازنده یا ارتباط را
نداشته باشیم, مفاهیم اصول ارتباطی به خوبی تعریف می شوند.بطور مثال یک RPC
, می تواند مفهومی مانند یک فراخوانی محلی داشته باشد, جز اینکه آن در
سرور راه دور قرار گرفته است. البته طراحان سیستم بیشتر روی حالتیکه
احتمال  وجود دار متمرکز می شوند که به آن مفاهیم قابلیت اعتماد گویند.

ازدیدگاه قابلیت اعتماد, اصول message passing از یک سیستم تا
سیستم دیگر تفاوت می کند. در یک حالت اگر message passing را برروی
دیتاگرامها بسازیم, کارایی بالا و در عین حال قابلیت اعتماد پایین را فراهم
می کند. در این حالت نرم افزار لایه بالاتر مسئولیت برطرف کردن و شناسایی
خطاها را بر عهده دارد. البته این امکان وجود دارد که به کمک زیرسیستمها
message passing رابا قابلیت اعتماد بالا فراهم نمود.

برای RPC ها مساله ی قابلیت اعتماد برمشکل درخواسهای تکراری
متمرکز است. مفهوم exactly-one به این معنی است که اگر مشتری پاسخ مثبتی از
سرور دریافت نماید, در هر سایت سرور تنها یک اجرا خواهیم داشت. برای
شناسایی تکرار ها از شماره گذاری ترتیبی استفاده می شود.

بعضی از سیستمها از مفهوم at-least-one استفاده می کنند بدین
معنی که دریافت پاسخ مثبت از یک سرور باعث اجرای حداقل یک دستور در هر سایت
خواهد شد.

بعضی سیستمها هم از RPC به عنوان یک عمل اتمیک استفاده می
کنند . به این مفهوم at-most-one می گویند بدین معنی که پس از دریافت پاسخ
مثبت در هر سایت حداکثر یک دستور اجرا می شود.

 

مدلهایی برای کنترل از راه دور سرویس

 

یک برنامه ی مشتری یک عمل را در سایت راه دور انجام داده و
سرویی یا داده ای را درخواست می کند. برنامه های کاربردی پایگاه داده
نیازمند امکاناتی مانند ساعتهای همزمان شده, اتمام اتمیک وسازگاری انحصاری 
داده های replicate شده هستند.

مدلهای مختلفی برای کنترل سرویسهای راه دور موجودند : مدل رویه, مدل فرآیند و مدل client/server.

مدل رویه

ایده اصلی این روش این است که سرویس باید به عنوان یک رویه
ساده و به عنوان بخشی از فرآیند فراخوانی شده, فراهم شود. بطور کلی یک
سرویس به وسیله ی فراخوانی رویه روی یک روتین کتابخانه ای, درخواست می شود.

مزیت عمده ی این روش سادگی آن و نیز رابط خوب و قابل درک آن
برای کاربر است. عیب عمده ی آن این است که مفهوم آن به اندازه ی syntax آن
ساده نیست.

در محیط های توزیع شده, پیاده سازی این روش بسیار دشوار است.
بیشتر طراحان می کوشند رابط فراخوانی رویه رابه عنوان لایه ای بالای یک روش
دیگر بکار برند. نکته ی منفی این است که توافق کلی روی سمانتیک این روش
وجود ندارد و سمانتیکهای فعلی برای پیاده سازی بسیار مشکل هستند. یک مشکل
لایه بندی این است که برای کاربر قابل درک می شود و این تنها مزیت این
روش(سادگی آن) را از بین می برد.

 

مدل فرآیند

تعریف اصلی این است که برای هر سرویس درخواستی یک فرایند مجزا
راه اندازی شود. این فرایند آرگومانهای خود را از فرآیند پدر خود دریافت
می کند و نتایج را معمولا به آن برمی گرداند.

مزیت عمده ی این روش این است که مسیرهای ارتباطی بین درخواست
دهنده و سرویس دهنده به شده کاهش می یابد. در هر ماشین با مکانیسم فضای
آدرس محافظت شده, روتین سرویس کاملا از روتین فراخوانی شده مجزا است.

عیب عمده ی این روش این است که این جداسازی هزینه ی بالایی دارد و سیستمهای عامل بسیار کمی هستند که این مدل را پشتیبانی می کنند.

مدل client/server

دراین مدل هر سرویس به وسیله ی یک فرآیند همیشگی و مجزا  به
عنوان سرور تولید می شود. درخواستها به وسیله ی پیامها با سرور مرتبط هستند
و سرور هم به وسیله پیام پاسخ را برمی گرداند. هردوی سیستمهای
client/server همزمان و غیرهمزمان موجود هستند.پیاده سازی های مدرن این روش
اصول شیء گرایی را پشتیبانی می کنند.

مزیت عمده ی این روش این است که یک راه طبیعی برای پیاده سازی سیستمهای توزیع شده بین چندین سایت خودمختار است.

یکی از مشکلات عمده ی این روش modularity است. دلیل این مشکل
این است که هزینه های validation برای این کار که موجب استفاده از لایه های
بیشتری می گردد, بالا است. این مشکل در سیستمهای شیء گرایی بیشتر است.

در محیطهای توزیع شده پیاده سازی یک سیستم client/server ممکن
است از آنچه گفتیم طبیعی تر باشد. مشکلترین کار این است که بتوانیم سرور
 هایی را داشته باشیم که در مقابل loss ها دوام بیاورند و آنها را کنترل
نمایند و نیز تاخیر ها را هم به نحوی مدیریت کنند. استفاده از سرور های
stateless به این کار کمک می کند. به یک سرور , stateless گویند اگر پاسخ
آن به یک درخواست به تاریخچه و درخواستهای قبلی وابسته نباشد.

۲-۴   همروندی

چندین کاربر ممکن است تراکنشهایی را در سایتهای مختلف
اجرا نمایند. یک زیرسیستم کنترل همروندی یک تاریخچه ی سریال را برای همه ی
تراکنشها فراهم می کند. Serializability نیازمند آن است که تاثیر اجرای
همروند تراکنشها روی پایگاه داده مانند اجرای سریال آنها باشد. در بعضی از
برنامه های کاربردی یک درجه ی پایین از همروندی بدون نیاز به سریالی بودن
هم قابل قبول است. البته سیستمهای بسیاری هم همروندی را بطور کامل پیاده
سازی نموده اند.

در حالت کلی سه نوع الگوریتم همروندی وجود دارد: الگوریتمهای
Locking-based , الگوریتمهای Time stamp-based و الگوریتمهای
Version-based.

الگوریتمهای Locking در مقایسه با الگوریتمهای Time stamp سخت
گیر هستند و محددیت های بیشتری را اعمال می کنند اما برای پیاده سازی ساده
تر هستند.

در بیشتر سیستمهای توزیع شده, الگوریتمهای Locking به صورت
کنترل متمرکز پیاده سازی می شوند. بدین تریتب که یک سایت مرکزی یک جدول از
Lock ها نگهداری می کند و مسئولیت دادن و گرفتن Lock ها را برعهده می گیرد.
الگوریتم محبوب و بسیار ساده برای پیاده سازی الگوریتم Two-Phase Locking
است. الگوریتمهای Time stamp برای رسیدن به درجه های بالای همروندی در
بسیاری از سیستمها پیاده سازی شده است. به هر تراکنش یک Time stamp تخصیص
داده می شود و یک رویه پیش از commit شدن تراکنشها آنها را بررسی می کند.
این بررسی می تواند در حین اجرا و یا پیش از آن ویا پس از اجرا و پیش از
commit باشد. الگوریتمهای Version-based  , نگارش های مختلفی از شیء   های
پایگاه داده را نگهداری می کنند. به ازای هر به روزرسانی یک نگارش جدید
تولید می گردد. این الگوریتمها برای طراحی های شیء گرایی مناسب است. طراحان
پایگاههای داده بیشتر این روشها را آزموده اند و اکنون در بیشتر سیستمها
از روش Two-Phase Locking استفاده می شود.

برای کنترل همروندی Time stamp – based در یک سیستم پایگاه
داده ی توزیع شده, دو نکته بسیار مهم است و باید مورد توجه قرار گیرد :
تراکنشهای محلی در مقابل تراکنشهای عمومی و به روزرسانی های اتمیک روی کپی
های replicate شده.

تراکنشهای محلی در مقابل تراکنشهای عمومی

 

در مکانیسم کنترل همروندی خوشبینانه,  یک تراکنش عمومی در
مقابل یک مجموعه از تراکنشهای از پیش commit شده validate می شود و در هر
سایت نیمه commit می شود(قبل از اینکه بصورت عمومی commit شود). بنابراین
بین commit و نیمه commit یک اختلاف زمانی وجود خواهد داشت. اما برای
تراکنشهای محلی چون به داده های توزیع شده دسترسی ندارند, اختلاف زمانی بین
commit و نیمه commit وجود ندارد.

به روزرسانی های اتمیک روی کپی های replicate شده

یک اختلاف زمانی بین زمانی که  یک تراکنش commit می شود و به
روزرسانی های آن به همه ی سایتها post می شود وجود دارد. در این مدت کنترل
کننده ی همروندی باید کنترل کند که هیچ تراکنشی دادههای نادرست را نخواند.
مشکل کلیدی بدست آوردن یک read-form درست برای هرتراکنش استکه ار آن به
عنوان مشکل به روزرسانی  اتمیک یاد می شود. در الگوریتمهای Locking-based
چون هر تراکنش تا پایان کارش پایگاه داده را lock می کند این مشکل وجود
ندارد.

یک راه حل برای این مشکل این است که هر تراکنشی که پایگاه
داده را به روزرسانی می کند یک ID از خود را در شیء   های پایگاه داده
ذخیره نماید.

یک راه حل دیگر این است که یک lock عمومی روی همه ی شیء   های
پایگاه داده قرار داده شود.(commit lock) این lock  ها دارای عمر کوتاهی
هستند.

Replication

 

شیء   های پایگاه داده برای اینکه بیشتر در دسترس باشند به
سایتهای دیگر replicate می شوند. بنابراین به یک مکانیزم کنترل کپی های
replicate شده نیازمندیم تا مطمئن شویم در زمان fail  شدن تراکنشها داده ها
همچنان سازگار باقی بمانند [۲].

یک الگوریتم ساده این است که هر تراکنش  می تواند یک کپی از
داده ها را بخواند اما یا باید همه را به روزرسانی کند یا هیچکدام را به
روزرسانی نکند. یک نوع از این الگویتم این است که بجای همه ی داده ها یک
بخش عمده ای را به روزرسانی کند.

در روش دیگر به تراکنش اجازه داده می شود که بیش از یک کپی از
داده ها را بخواند و الگوریتم هم مطمئن خواهد بود که مجموع تعداد کپی های
خوانده شده و مجموع تعداد کپی های نوشته شده بزرگتر از تعداد کپی های موجود
است. این آزادی زمانی اهمیت بیشتری می یابد که یک یا چند کپی از داده ها
به دلایلی نظری از کار افتادن شبکه یا سایتها در دسترس نباشد.

برای حفظ بعضی از این محدودیتها الگوریتمهای commit استفاده
می شوند. الگوریتمهای commit اطمینان حاصل می کنند که یا همه ی کپی ها
write شده اند و یا هیچ یک از کپی ها write نشده است. بیشتر سیستمها از
الگوریتمهای Two-phase commit استفاده می کنند.

در بسیاری موارد ممکن است  به وجود آید و این موضوع باعث می
شود داده ها کمتر در دسترس باشند. الگوریتمهایی برای مقابله با   ها طراحی
شده اند. این الگوریتمها به تراکنشها اجازه می دهند هر کپی را بخواند و نیز
همه ی داده های در دسترس را write کند. کپی های داده ی غیرقابل دسترس,  با
استفاده از fail-lock ها و تراکنشهای کپی کننده به روز می شوند. Fail-lock
ها برای این در سایتهای عملیاتی نگهداری می شوند که این واقعیت را که بعضی
از داده ها از out-of-date هستند. ای« الگوریتمها سربار های خاص خود را
دارا می باشند.

کنترل معنایی داده

 

کنترل معنایی داده مسئول حفظ درستی و اعتبار پایگاه داده با
در نظرگرفتن مجموعه ای از محدودیت ها می باشد.  کنترل معنایی داده شامل
view maintenance ,   semantic integrity و security control است. در این
قسمت از بحث, دو بخش اول را مورد بررسی قرار می دهیم [۳].

 

view maintenance می کوشد مسایل و مشکلات همزمانی
(synchronization )محیطهای پایگاه داده ها را برطرف نماید. بطور مثال سعی
می شود نتایج پرس و جو هایی که زیاد اجرا می شوند, در یک یا بیشتر سایت
ذخیره شوند تا زمان پاسخ به پرس  و جوها کاهش یابد. ما در این بخش این
نتایج پرس و جوهای ذخیره شده را materialized view می نامیم و داده هایی را
که نتایج آن query ها  هستند underlying یا base data می نامیم.

 مساله ی همزمانی برای اطمینان از این است که داده های
underlying به روزرسانی شده و به روزرسانی ها به materialized view ها
انتشار یافته است. (از این مشکل به عنوان مشکل نگهداری materialized view
ها نام برده می شود). مساله ی دیگر هم این است که وقتی materialized view
ها به روزرسانی می شوند, آن به روزرسانی ها به داده های underlying هم
انتشار یابند. (از این مشکل به عنوان مشکل به روز رسانی materialized view
ها یاد می شود.)

برای مساله ی اول تنها یک راه حل موجود است در حالیکه برای مساله ی دوم چندین راه حل دارد.

Semantic integrity controlبه مساله ی
معتبر نگه داشتن داده های توزیعی با توجه به محدودیت های جامعیت از پیش
تعیین شده , بر می گردد. بطور مثال وقتی داده ای به روزرسانی می شود, باید
مطمئن باشیم که محدودیت های جامعیت تعیین شده پس از به روزرسانی شدن داده
ها هم حفظ می شود.

یک نوع از الگوریتمها برای انجام کنترل جامعیت , به روزرسانی
هارا قبل ازاینکه اجرا شوند, بررسی می کنند که آیا محدودیت ها را درنظر می
گیرند یا خیر؟

نوع دیگر الگوریتمها همه ی به روزرسانی هارا اجرا می کنند و
پس از آن بررسی می کنند که آیا محدودیتهای جامعیت حفظ شده اند یا خیر؟ و
اگر حفظ نشده باشند سیستم می کوشد یک حداقل اصلاحاتی روی پایگاه داده انجام
دهد تا محدودیت ها اعمال گردد.

محدودیتها در پایگاههای داده ی توزیعی

یک پایگاه داده ی توزیعی بین تعدادی زیادی سایت توزیع می
شود. یکی از دلایل توزیع داده ها, مسائل کارایی است [۴]. در یک پایگاه داده
ی توزیعی داده هایی که در هر سایت هستند لزوما یک موجودی مستقل نیستند,
بلکه می توانند به داده های سایتهای دیگر مرتبط باشند. این روابط با
ادعاهای جامعیت که در مورد داده ها موجود است, به شکل محدودیت ها در
نظرگرفته می شوند. شکل۱ یک طبقه بندی از محدودیتهای داده ای ممکن که در
محیط توزیعی وجود داشته باشد را نشان می دهد. یک دسته از این محدودیتها را
محدودیتهای استاتیک می نامند که در هر برهه از زمان باید حفظ شوند. دسته ی
دیگر در یک time interval یا یک بازه ی زمانی بررسی می شوند و محدودیتهای
دینامیک نامیده می شوند.

شکل صفحه ی بعد این موضوع را نشان می دهد.

شکل ۱- طبقه بندی محدودیتها در محیط پایگاههای داده ی توزیعی

دربالاترین سطح دونوع محدودیـت استاتیک و دینامیک وجود
دارد. برای بررسی لحاظ شدن محدودیت های استاتیک در هر زمان به یک snapshot
از پایگاه داده نیازمندیم. ازسوی دیگر برای بررسی لحاظ شدن محدودیت های
دینامیک نیازمندیم اطلاعاتی درباره ی پایگاه داده در هر زمان داشته باشیم.
مثالی از محدودیت  دینامیک :

هر ۵ دقیقه  در زمان حیات پایگاه داده, یک اتفاقی می بایست رخ دهد (مثلا یک به روزرسانی  رخ دهد).

محدودیت داده می تواند جامعیت یا duplication باشد [۳].
محدودیت های مستقل از این هستند که داده ها چگونه توزیع یا duplicate شده
اند. اگر یک محدودیت برمبنای یک مجموعه ی منفرد از شیء   هاو متغیرهای
منفرد باشد, individual نامیده می شود. محدودیت های Set آنهایی هستند که
برمبنای بیش ازیک مجموعه داده یا متغیر باشند.

برای مثال در پایگاه داده توزیعی شکل ۲, محدودیت های جامعیت
individual , ممکن است شامل محدودیت های کلید اصلی در جدول R1 و R2 باشد. و
محدودیت جامعیت Set ممکن است شامل محدودیت جامعیت کلید خارجی بین دو جدول
باشد.

محدودیتهای Aggregate محدودیتهایی هستند که شامل عملگرهای aggregate مانند min , max , sum ,  count و average می باشند.

باید به این نکته توجه داشت که محدودیتهای می توانند هردوی
استاتیک و دینامیک باشند. در یک محدودیت دینامیک خاص, ممکن است درحالتیکه
یک به روزرسانی ای رخ دهد که محدودیت را خدشه دار می کند, در نظر گرفته می
شود و یک به روزرسانی دیگر برای اعمال محدودیتها صورت می گیرد. ازسوی دیگر
محدودیت جامعیت استاتیک نیازمند آن است که در لحظه برقرار باشد.

یک محدودیت duplicate به دو دسته ی replica و view تقسیم
می شود. در مثال شکل ۲ محدودیتی ازجدولR1 که به عنوان R4 به سایت ۴ کپی می
شود, محدودیت replica نامیده می شود و محدودیتی که سایت ۳ شامل یک جدول با
داده های گرفته شده (مشتق شده) از جداول R1 و R2 دارد, محدودیت view است.
ازاین پس به query های ذخیره شده روی مجموعه های داده به عنوان
materialized view یاد می شود. درشکل ۲ , V یک materialized view است چون
نتایج query که یک join بین جداول R1 و R2 در این view ذخیره می شود. ما به
جداول R1 و R2 به عنوان underlying tables مربوط به materialized view می
گوییم.

شکل ۲-  یک مثال از پایگاه داده ی توزیع شده

توجه شود که محدودیتهای replica نوعی از محدودیتهای view
هستند. چون یک محدودیت replica می تواند به عنوان محدودیت view ای باشد که
در آن query ای که view را تولید می کند, یک identity query است.

همچنین محدودیتهای duplication می توانند استاتیک یا دینامیک
باشند. در مثال شکل ۲ یک محدودیت duplication می تواند وجود داشته باشد
وقتی که جدول R1 به روز شود, و V هم باید برای اینکه تغییرات را منعکس کند ,
به روز گردد.

معرفی محدودیتها

 

بطور کل دو نوع الگوریتم برای معرفی محدودیتها وجود دارد, الگوریتمهای view maintenance و view update [2].

الگوریتمهای نوع اول برای انتشار تغییرات صورت گرفته روی داده
های underlying به materialized view بکار می روند. الگوریتمهای به روز
رسانی view برای عکس این عمل بکار می رود. هردو نوع الگوریتمها به عنوان
الگوریتمهای synchronization یا همزمانی نامیده می شوند.

بسته به اینکه synchronization در زمان هر به روز رسانی یا در
زمان دیگری پس از آن انجام شود, به آن الگوریتمها, الگوریتمهای همزمانی
داده ی  immediate و deferred گفته می شود.

جدول ۱ خلاصه تفاوتهای الگوریتمهای همزمانی نشان داده شده است :

عمل /  محدودیت

محدودیتهای به روز رسانی ایستای معرفی شده

محدودیتهای duplicate دینامیک

محدودیتهای ایستای duplicate

به روز رسانی materialized view ها

حفظ محدودیتهای جامعیت + تضمین ترجمه ی مناسب به داده های underlying

در میان الگوریتمهای به روز رسانی deferred materialized view

در میان الگوریتمهای به روز رسانی immediate materialized view

به روز رسانی داده های underlying

حفظ محدودیتهای جامعیت

در میان الگوریتمهای نگهداری deferred materialized view

در میان الگوریتمهای نگهداری immediate materialized view

جدول ۱ – محدودیتهای  duplication معرفی شده

یکی از نکاتی که در این جدول نشان داده شده است این است
که زمانیکه به روز رسانی در یک materialized view  رخ می دهد, برای آنکه
پذیرفته شود می بایست حالتی باشد که یک ترجمه مناسب از به روز رسانی به
داده های underlying وجود داشته باشد.

یک ترجمه ی مناسب یک به روز رسانی به داده های underlying ,
ترجمه ای است که تغییرات انجام شده در materialized view ها را به گونه ای
مناسب به داده های underlying با در نظر گرفتن همه ی شرایط , انتشار دهد.

همچنین این جدول نشان می دهد که یک محدودیت replica ی مشخص
شده روی پایگاه داده, در زمان اجرای به روز رسانی یا در مدت زمان کوتاهی پس
از آن باید حفظ شود. همچنین قبل از اغاز الگوریتم همزمانی می بایست پایگاه
داده با توجه به محدودیتهای جامعیت مشخص شده در حالت معتبر باشد.

برنامه های کاربردی

بیشتر برنامه های کاربردی که روی پایگاههای داده توزیع
شده کار می کنند, از materialized view ها برای افزایش سرعت بازیابی داده
ها و کاهش سربار CPU , دیسک و شبکه استفاده می کنند. مثال های زیادی از این
برنامه ها وجود دارد مانند برنامه های بانکداری, حسابداری, مدیریت شبکه و …
که از materialized view ها استفاده می کنند. برنامه های کاربردی جدیدتر
مانند data warehousing , OLAP , data replication ,data visualization ,
 سیستمهای mobile و برنامه های نظارت توزیع شده, نیز در این حوزه بکار می
روند.

مثال Data Warehouse

 

در حالت کلی یک data warehouse شامل داده های بازیابی شده
تجمیع شده از تعداد زیادی منبع داده هستند و معمولا به وسیله ی ابزارهای
OLAP یا On-Line Analytical Processing و داده کاوی برای اهداف پشتیبانی
تصمیم بکار می روند. (شکل ۳)

شکل ۳- یک مدل data warehouse

Data Visualization

هدف برنامه های کاربردی Data Visualization ساختن تصاویر
visual از مجموعه های بزرگ داده است تا کاربران سیستم بهتر بتوانند درک
بهتری نسبت به داده ها بدست آورند. ابزار های visual ممکن مانند گرافها,
نقشه ها, نمودار ها و … هستند. یک برنامه کاربردی visualization معمولی
شامل دو مولفه هستند : مولفه پرس و جوی داده و مولفه ی نمایش گراف. (شکل ۴)

شکل ۴ – Data Visualization

مولفه ی پرس و جوی داده مسئولیت محاسبه ی نتایج پرس و
جوهای کاربران را از پایگاه داده ی توزیع شده, بر عهده دارد. مولفه ی نمایش
گرافیکی, قابلیت آن را دارد که داده ها در materialized view ها را به
شکلی که کاربر می خواهد به او نشان دهد. دلیل استفاده از materialized view
ها در این سناریو این است که مولفه ی نمایش معمولا نیازمند آن است که
بصورت فیزیکی با داده ها کار کند.

 

سیستم­های Mobile

در سالهای اخیر کامپیوتر های شخصی سیار بسیار محبوب و
رایج گشته اند, نه تنها به عنوان وسیله ای برای دستیابی به اطلاعات بلکع به
عنوان وسیله ای برای برقراری ارتباط با سراسر جهان .ارتباط بین این
کامپیوترها و دنیای خارج به وسیله ی سیستمهای Geo-Positioning فراهم می
گردد. بطور مثال یک کاربر ممکن است بخواهد برای بدست آوردن یکسری اطلاعات
ویژه پرس و جو نماید. با توجه به اینکه پهنای باند انتقال بخاطر خصوصیات
فیزیکی محدود است, materialized view ها می توانند برای ذخیره ی نتایج پرس و
جوهایی که زیاد انجام می شوند استفاده گردند تا ترافیک پهنای باند کاهش
یابد.

ویژگی اصلی پرس و جوها درمحیط سیستم های سیار آن است که
موقعیت کامپیوتر می تواند به عنوان یک پارامتر پرس و جو مطرح گردد. مثلا در
شکل ۵ :

شکل ۵ – یک مثال از سیستم Mobile

یک کاربر ممکن است بخواهد درباره ی McDonald در منطقه ی
خودش اطلاعاتی بدست آورد. پرس و جو به سیستم Geo-Positioning ارسال می شود و
این سیستم پاسخ مورد نظر را برمی گرداند. نتیجه ی پرس و جو در
materialized view در کامپیوترکاربر ذخیره می گردد. اکنون اگر ۵ کیلومتر
دیگر هم کاربر همان پرس و جو را تکرار کند تناه تغییرات نقشه به او ارسال
می گردد.

سوییچ تلفن

 

برخلاف سیستمهای  mobile , در سوییچهای تلفن  مهمترین
نیازمندی کم کردن زمان پاسخ است. معمولا, هرسوییچ شامل تعدادی یک حافظه
اصلی پایگاه داده با ساختار C++ و شامل مجموعه های متعددی شیء   می باشد.
برای اینکه یک تماس تلفنی مسیریابی شود, اطلاعات ساختارهای زیادی موردنیاز
است و یک join بین آنها باید انجام شود. اگرچه انجام این join بصورت
بلادرنگ بخاطر زمان اجرای بالای آن و سرعت کم آن دلخواه نیست. به همین دلیل
نتایج این join ها در materialized view های حافظه اصلی ذخیره می گردند.

مطالعه ی موردی Replication در SQL Server

 به معنی انتشار اطلاعات می باشد . یعنی اطلاعات بین دو دیتابیس انتقال می یابد و دارای سه مدل می باشد:

۱-

۲-

۳-

در حالت  انتقال اطلاعات دو طرفه است.

برای انتقال اطلاعات دو دیتابیس یکی را به عنوان  و دیگری را
به عنوان  مشخص می کنیم.(ابتدا  را ساخته و بعد  را به آن متصل می کنیم).

در مدل چون اطلاعات در دو طرف تغییر می کند امکان  نیز موجود است که ممکن است در مواردی باعث ایجاد مشکل و خراب شدن اطلاعات گردد.

موارد کاربرد مدل:

۱-                وقتی چندین داده ها را در زمانهای مختلف  میکنند و تغییرات را به های دیگر و  انتشار می دهند.

۲-                وقتی  داده ها را بصورت  تغییر می دهند و پس از آن باها  می کنند.

۳-                زمانیکه وها به ندرت باهم در ارتباط هستند.

دو نوع داریم: .

  :  ای است که داده ها برای  با های دیگر فراهم کرده و نیز
اینکه چه داده هایی تغییر کرده اند و اطلاعاتی در مورد ‌ها در آن سایت
نگهداری میکند.

 : ای که شامل  هاست که میتواند جدا از  باشد () و یا بایکی باشد.(). در مدلهای  نقش بیشتری بازی می‌کند.

:هایی هستند که داده های  شده را دریافت می‌کنند.

نکات مهمی که در باید مورد توجه قرار بگیرد:

۱-                باید به ها رنج بدهیم.(برای هر شعبه یک رنجمشخص نسبت دهیم)

۲-                در برنامه دستور در دستور باید نام ستونها
را ذکر کنیم چون در حالتهای و ستونهایی به جداول  شده اضافه می شود و اگر
برنامه نام ستونها در دستور ذکر نکند  بوجود می آید.

۳-                از حداکثر اندازه سطرها و ستونها آگاه
باشیم. در حالتهای و  یک جدول حداکثر ۲۵۵ ستون داشته و حداکثر تعداد ستونها
۲۴۶ و حداکثر اندازه هر سطر ۸۰۰۰ بایت می باشد. در حالت اندازه هر سطر
۸۰۰۰ بایت می باشد. در حالت  حداکثر تعداد ستونها ۲۴۶ و حداکثر اندازه هر
سطر ۶۰۰۰ بایت می باشد. دلیل این محدودیت در حالتنسبت به دو حالت دیگر این
است که جداول  ساختاری شبیه جداول اصلی و با ستونهای بیشتری دارند که
اطلاعاتی را در مورد داده های اصلی و و دلایل آن آن نگهداری می کنند و به
همین دلیل به فضای اضافه ای برای این جداول نیاز است.

۴-                داده ها را به صورت منطقه ای و با توجه به
مسایل تجاری یا موقعیت جغرافیایی طوری پارتیشن بندی کنیم که از  کردن داده
های یکسان توسط  های متفاوت جلوگیری شود.

۵-                در حالتی که جدول ابتدا  و بعد می شود ها باقی می مانند. ها را می توان به عنوان  انتخاب نمود(همچنین –  ها  ها)

۶-                اگر ابتدا خالی باشد و یک رکورد در آن
 کرده و سپس آنرا  کنیم و بعد بخواهیم از  چند رکورد را در درج کنیم رکورد
ها را به همان ترتیبی که در  است و با همان فیلد  کپی می کند.

۷-                فرض میکنیم دو رکورد دارد که ربطی به
رکوردهای ندارند و هم چند رکورد دارد. وقتی  می‌کنیم اگر فیلد  ها مختلف
باشند که رکورد های  به انتهای جدول  اضافه می شود . اگر  ها باهم یکی
باشند( مثلا  یکی از رکوردهای  و یکی از رکورد های  ) آنگاه  بوجود می آید
چون نمی شود دو رکورد با فیلد  یکسان داشته باشیم (پس از  ) به همین دلیل
آن رکورد از  که اولویت کمتری نسبت به دارد می شود.

روش  کردن  برای…/ :

در روی کلیک راست کرده و گزینه‌ی  …../  را انتخاب می کنیم در
ویزارد مربوط در صفحه اول گزینه را میزنیم. در صفحه ی بعد ی گزینه ی
بالایی را انتخاب کرده و می زنیم. در پنجره ی باز شده دکمه ی  را زده و در
صفحه بعدی و نیز صفحه ی بعد از آن هم  را می زنیم. در صفحه ی بعدی مسیر  را
مشخص کرده و می زنیم. پس از تایید این مسیر در صفحه ی بعدی گزینه ی پایین
() را انتخاب کرده و می‌زنیم و در صفحه ی آخر هم  را می زنیم. پس از  شدن
 هم به ساختار درختی اضافه می شود.

روش ساختن:

روی گزینه ی  کلیک راست کرده و را زده در ویزارد ابتدا گزینه ی  را تیک زده و می زنیم.

در صفحه ی بعد  مورد نظر را انتخاب کرده و می زنیم. در صفحه ی
بعدی که مربوط به انتخاب مدل است گزینه ی را انتخاب کرده و می زنیم. در
صفحه ی بعد هم گزینه ی بالایی () را انتخاب کرده و تیک می زنیم. در صفحه ی
بعد  های مورد نظر را انتخاب می کنیم و  می‌زنیم(این می‌تواند  و یا
 باشد). در صفحه‌ی بعد اگر جداول انتخابی دارای ستون  نباشند گزینه ی  را
انتخاب می کنیم و اگر داشتند گزینه‌ی  را انتخاب کرده و می‌زنیم. در صفحه ی
بعد نام  را مشخص کرده و توضیحات لازم در مورد آنرا نوشته و می زنیم. در
صفحه ی بعد اگر خواستیم از فیلتر استفاده کنیم گزینه ی بالایی و در غیر این
صورت گزینه ی پایینی را تیک زده و  می زنیم. اگر گزینه ی پایین را انتخاب
کنیم که در صفحه ی بعد  می زنیم اگر بالایی را بزنیم هم در صفحات بعد فیلتر
ها را  کرده و بعد  را می زنیم.

روش ساختن:

روی گزینه‌ی  کلیک راست کرده و گزینه‌ی  را انتخاب کرده و
گزینه ی را تیک زده و می زنیم. در صفحه ی بعد با انتخاب گزینه بالایی تیک
می زنیم و را می زنیم. در صفحه ی بعد  مورد نظر را انتخاب کرده ومورد نظر
را انتخاب می کنیم تا به آن وصل شود. در صفحه ی بعد نیز گزینه ی بالایی را
انتخاب می‌کنیم و می زنیم. در صفحه بعد مورد نظر را انتخاب می کنیم و می
زنیم. در صفحه ی بعد گزینه ی  را انتخاب کرده وبزنیم. در صفحه ی بعد  مورد
نظر را انتخاب کرده و می زنیم. در صفحه ی بعد هم گزینه بالایی را تیک زده
و می زنیم. صفحه ی بعد را هم  زده و در صفحه ی آخر را میزنیم.

نکات زیؤ هم برای انجام یک Replication موفق باید مورد توجه قرار گیرد:

۱-                مشخص نمودن اینکه چه جداولی باید  گردند.
به همین دلیل بهتر است Replication برای Database ای استفاده شود که طراحی
آن تمام شده است و دیگر نمی خواهیم جدولی به آن اضافه کنیم.

۲-                نکته ی بسیار مهم این است که جداول به همان
ترتیبی که در برنامه باید پر شوند شوند. به همین دلیل باید ابتدا  پر شدن
جدولها را داشته باشیم و با استفاده از آن و به همان ترتیب جداول را  کنیم.

۳-                نکته ی دیگر این است که در هنگام  تریگرها
 می شوند به همین دلیل وقتی حجم  ها بالا ست برای بالا بردن  و سرعت انتقال
اطلاعات بهتر است تریگرها را  کنیم(به دلیل نمی توانیم تریگر ها را  کنیم
که برای انجام این کار ابتدا باید  را  کنیم و این کار وقتی
که برای استفاده شده است امکانپذیر نیست).

۴-                اگربرای از مدل استفاده شود و دارای شعبات
مختلفی باشیم و طبیعتا نخواهیم اطلاعات یک شعبه به شعبات دیگر ارسال گردد
می بایست اطلاعات در هنگام ارسال از دفتر مرکزی به شعبات فیلتر شوند تا هر
شعبه  تنها اطلاعات مربوط به خود را ببیند. برای این کار از یک شرط برای
فیلتر استفاده می کنیم. برای انجام این کار ستون به نام  به هر یک از جداول
مورد استفاده در طرح اضافه می کنیم و به هر یک از شعبه ها یک  منحصر به
فرد اختصاص می‌دهیم و بر اساس آن فیلتر می کنیم. (بطور کلی در مدل وقتی می
خواهیم فیلتر کنیم از این روش استفاده می کنیم) در هنگام فیلتر کردن جداول
هم باید به  ها توجه داشته باشیم. مثلا اگر جدول ۲ می بایست بعد از جدول ۱
پر شود و جدول ۱ فیلتر میشود بهتر است جدول ۲ هم فیلتر گردد چون در غیر این
صورت امکان بروز  وجود دارد.

۵-                یکی از مسائلی که باید مورد توجه قرار گیرد
هاست. وقتی در جدولی داریم و داده ها از جداول متناظر در  های دیگر به این
جدول شود  پیش می‌آید.

۶-                بحث فیلد های  هم باید مورد توجه قرار گیرد. بهتر است با توجه به ساختاراکثر ها به ها بدهیم تا با مواجه نشویم.



مقاله پایگاه داده های سیستم های توزیع شده

مقاله پایگاه داده های سیستم های توزیع شده

چکیده:
پردازش داده‌های توزیع شده یک واقعیت تبدیل شده است. دلایلی که هنوز
پردازش داده‌های توزیع شده را یک موضوع پیچیده می‌سازد عبارتند از:

 سیستم‌های توزیع شده خیلی وسیع هستند و هزاران سایت متجانس شامل کامپیوترهای شخصی و ماشینهای سرور بزرگ را در بر می‌گیرد  

حالت
سیستم‌های توزیع شده به سرعت تغییر می‌کند زیرا بارگذاری سایت‌ها از نظر
زمانی متنوع می‌باشد و سایت‌های جدید به سیستم افزوده شده است.

سیستمهای
موجود باید تکمیل گردند. از انجا که سیستم‌های موجود برای پردازش توزیعی
طراحی نشده‌اند و اینک نیاز است که با سیستم‌های  دیگر در محیط توزیعی
تعامل داشته باشند.

این مقاله چگونگی انجام پردازش پرس‌وجو در محیط‌های توزیع شده  و سیستم‌های اطلاعاتی را نمایش می‌دهد.

فهرست:

  • مقدمه
  • تکنیکها و روشهای پایه‌ایی پردازش پرس‌وجوی توزیعی
  • معماری پردازش پرس‌وجو
  • بهینه‌ساز پرس‌وجو
  • تولید طرح با استفاده از برنامه‌نویسی پویا
  • تکنیکهای اجرای پرس‌وجو
  • Row Blocking
  • بهینه‌سازی برای Multicast
  • اجرای همروند پرس‌وجو
  • پيوند داده‌های پارتیشن شده افقی
  • Semijion
  • DoublePiplined Hash Joins
  • PointerBased Joins and Distributed Object Assembly
  • Top N and Bottom N Queries
  • سیستم‌های پایگاه داده‌ای به صورت CLIENTSERVER
  • معماری‌هایCLIENTSERVER،  PEERTOPEER و MULTITIER
  • استفاده از منابع CLIENT
  • انتقال پرس‌وجو
  • انتقال داده
  • انتقال ترکیبی
  • مقایسه
  • سیستم پایگاههای داده نامتجانس
  • معماری WRAPPER برای پایگاه‌های داده نامتجانس
  • تکنیکهای اجرای پرس‌وجو
  • Bindings
  • cursor caching
  • موقعیت‌دهی پویای داده
  • REPLICATION  VS CACHING
  • الگوریتم‌های پویای REPLICATION
  • CACHE INVESTMENT
  • معماری‌های جديد برای پردازش پرس‌وجو
  • مدل‌های اقتصادی برای پردازش پرس‌وجو
  • سيستم اطلاعاتی مبتنی بر انتشار



دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

Back To Top