به نام خدا

 

 

پايگاه داده پيشرفته

دكتر رهگذر

 

 

پدرام قدس نيا

اشكان بياتي

 

 

 

گزارش شماره 1

فايل persentation

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

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

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

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

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

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

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

6. منابع

 

گزارش شماره 2

فايل presentatoin

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

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

1. مكانيزمهاي سنتي براي كنترل همزماني

1-1. روش S2PL

1-2. روش خوشبينانه (Optimistic)

2. روشهاي جديد و بهبود يافته براي كنترل توزيع شده همزماني

2-1. گراف توالي پذيري

2-2. روش تست گراف توالي پذيري نامتمركز (DSGT)

3. مقايسه DSGT‌ با S2PL

4. Replication و پروتكل DSGT

5. منابع

 

گزارش شماره 3

فايل presentation

در اين گزارش در مورد سيستمهاي توزيع شده همتا به همتا و كاربردهاي آنها توضيحاتي داده شده است. در ادامه يك الگوريتم جالب و قوي براي حل مساله انتخاب چندگانه به صورت توزيع شده بيان شده است و در انتها در مورد معماري data grid ها و مديريت replication‌ در آنها مطالبي از مقالات جديد ارائه شده است.

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

1.بررسي الگوريتمهاي انتخاب چندگانه در سيستم هاي همتا به همت

2-1.مشكلات موجود در استفاده از بانكهاي اطلاعاتي توزيع شده مبتني بر P2P

2-2.الگوريتم توزيع شده انتخاب چندگانه

2-3-مراحل الگوريتم

2-4.محاسبات پيچيدگي الگوريتم

2-5.آزمايشات تجربي

3.الگوريتم پوياي Replication براي Data Grid هاي چند لايه

3-1.انواع الگوريتمهاي موجود

3-2.معماري سيستم

3-3.پيشنهاد بهبود معماري

3-4.الگوريتمهاي replication‌ به صورت پويا

3-4-1.روش SBU

3-4-2.روش ABU

4.منابع

 

پروژه1

در پروژه انجام شده شبيه سازي كه توسط آقاي باصدا طراحي شده بود، به گونه اي تغيير داده شد كه براي آزمايش يك پروتكل جديد به نام BGBR آماده شود. اين شبيه ساز كه به زبان جاوا نوشته شده است يك سيستم بانك اطلاعاتي توزيع شده همتا به همتا را كه داده هاي آن به روش Fragmentation‌ بين سايت هاي مختلف توزيع شده اند شبه سازي مي كند. الگوريتم BGBR روشي براي تصميم گيري در مورد چگونگي جا به جا كردن Data Fragment‌ ها بين سايت ها با توجه الگوي دستيابي كاربران سيستم به صورت پويا و هوشمند است. اين الگوريتم به گونه اي تصميم گيري مي كندكه در در حاصل كار هزينه جابجايي Data Fragment‌ ها و همچنين هزينه پرس و جوهاي انجام شده كمينه شود. طبق آزمايشاتي كه انجام شد، مشخص گرديد كه اين روش نسبت به دو روش قبلي يعني روش Optimal و روش NNA‌ بسيار بهتر عمل مي كند.

مستندات پروژه

پروژه 2

فايل exe

فايل swf

در اين پروژه كه با استفاده از زبان Action Script‌ و به صورت تحت وب پياده سازي شده است امكان رسم توپولوژي توزيع شده دلخواه به صورت گرافيكي وجود دارد. به كمك اين ابزار كه Topology Editor‌ نام دارد مي‌توان از توپولوژي رسم شده فايل xml استخراج كرد و از فايل استخراج شده براي آزمايشات مربوط به تغيير Topology استفاده نمود و در واقع تاثير تغيير توپولوژي را بر نتايج آزمايش كرد. در حال حاضر تنها نسخه مقدماتي از اين پروژه پياده سازي شده است و در آينده اي نزديك پياده سازي نسخه نهايي به پايان خواهد رسيد.

 

‍Conference Paper

فايل presentation

نسخه doc‌ از مقاله

در اين مقاله الگوريتم BGBR توضيح داده شده است و در مورد ساختار آن و همچنين علت برتري آن بحث شده است. در نهايت نتايج آزمايشات تجربي انجام شده با شبيه ساز تغيير يافته آورده شده و به كمك اين نتايج ادعاهاي صورت پذيرفته به اثبات رسيده است.

 

گزارش فني در مورد جزئيات پروژه

نسخه doc

 

آدرس این سایت این است برای گرفتن پاورپویت و پی دی اف به سایت زیر بروید

http://ece.ut.ac.ir/DBRG/seminars/BaiatiAshkan-GhodsniaPedram/CD1/index.html

 

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

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

 

پدرام قدس نيا

اشكان بياتي

 

دانشکده مهندسی برق و کامپيوتر

دانشگاه تهران

 

 

فهرست مطالب

 

1.بررسي الگوريتمهاي انتخاب چندگانه در سيستم هاي همتا به همتا 1

2-1.مشكلات موجود در استفاده از بانكهاي اطلاعاتي توزيع شده مبتني بر P2P.. 2

2-2.الگوريتم توزيع شده انتخاب چندگانه. 3

2-3-مراحل الگوريتم.. 4

2-4.محاسبات پيچيدگي الگوريتم.. 8

2-5.آزمايشات تجربي.. 9

3.الگوريتم پوياي Replication براي Data Grid هاي چند لايه. 11

3-1.انواع الگوريتمهاي موجود. 11

3-2.معماري سيستم.. 12

3-3.پيشنهاد بهبود معماري.. 13

3-4.الگوريتمهاي replication‌ به صورت پويا 14

3-4-1.روش SBU... 14

3-4-2.روش ABU... 15

4.منابع. 15

 

 

 

 

1.بررسي الگوريتمهاي انتخاب چندگانه در سيستم هاي همتا به همتا

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

امروزه بحث محاسبات همتا به همتا (peer-to-peer) يكي از مباحث داغ در زمينه سيستم هاي توزيع شده به شمار مي‌رود. به كمك معماري هاي موجود در اين زمينه مي توان قدرت پردازش و همچنين اطلاعات موجود در تعداد زيادي كامپيوتر را كه در گستره جغرافيايي پهناوري وجود دارند و تنها از طريق شبكه و يا اينترنت به هم متصل هستند به اشتراك گذاشت و در نتيجه سيستم توزيع شده اي داشت كه به كمك آن بتوان به قدرت پردازشي بالايي دست يافت و يا به حجم عظيمي از اطلاعات توزيع شده در سيستم هاي مختلف دسترسي پيدا نمود. در سالهاي گذشته بيش از نيم بيليون دلار در شركتهايي كه در اين زمينه فعاليت مي كنند سرمايه گذاري شده است. شدت علاقه به اينگونه سيستمها از موفقيت چشمگير نرم افزارهاي شناخته شده و معروفي مثل Napster (نرم افزار به اشتراك گذاري فايل هاي موزيك) و يا پروژه ضد سرطان دانشگاه آكسفورد(به اشتراك گذاري قدرت پردازش براي شركت در محاسبات لازم براي تحقيقات بيولوژيك در زمينه سرطان) نشات مي گيرد. به دنبال محبوبيت اين نرم افزار ها تعدادي پروژه به اشتراك گذاري فايل و پردازش ديگر هم شكل گرفت كه از جمله آنها مي توان به نرم افزار هاي Kaza، Emull، Edonkey و ... براي به اشتراك گذاري فايل و پروژه شبيه سازي ژنتيكي گوگل براي استفاده از قدرت پردازش كامپيوتر هاي دنيا در انجام تحقيقات ژنتيكي نام برد.

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

-         نياز به امنيت اطلاعات بيشتر براي جلوگيري از فاش شدن اطلاعات خصوصي كمپاني در هنگام به اشتراك گذاري فايلها و قدرت پردازش.

-         كمتر بودن تعداد كامپيوتر هاي شركت كننده در كل سيستم

-         پيچيده تر بودن دستورالعملهاي بانك اطلاعاتي و نياز به الگوريتمهاي توزيع شده بهينه

-         تعلق كامپيوتر هاي شركت كننده به كمپاني به جاي افراد حقيقي

اين تغييرات مواردي هستند كه مشكلات جديدي را مطرح مي كنند كه براي حل آنها پنجره جديدي از تحقيقات باز شده است.

2-1.مشكلات موجود در استفاده از بانكهاي اطلاعاتي توزيع شده مبتني بر P2P

اگر چه سيستم هاي P2P‌ موفقيت چشمگيري داشته اند ولي هنوز به كار بردن آنها در بعضي از كاربردها با مشكلاتي روبروست. يكي از جدي ترين اين مشكلات در حوزه عمليات بانك اطلاعاتي حاكم است. بسياري از دستورالعملهاي بانك اطلاعاتي در روي يك كامپيوتر در زمان كوتاهي قابل اجرا هستند ولي اجراي همين دستورالعملها در يك بانك اطلاعاتي توزيع شده ممكن است به رد و بدل شدن پيامهاي ارتباطي زيادي نياز داشته باشد و در نتيجه زمان بيشتري ببرد.

يكي از اين دستورالعملهاي زمانبر Selection است مثالي براي عمل Selection‌ در [1] آمده است.

يك راه حل براي اين مشكل اين است كه همه اطلاعات را روي يك كامپيوتر بياوريم و سپس عمل Select‌ را به شكل بهينه اي روي آن كامپيوتر اعمال كنيم. ولي اين راه حل مشكلات زير را دارد :

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

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

-         پهناي باند مصرفي : انتقال حجم زيادي از اطلاعات در شبكه مي تواند بار زيادي را به شبكه تحميل كند و ترافيك شبكه را به شدت بالا ببرد.

 

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

2-2.الگوريتم توزيع شده انتخاب چندگانه

الگوريتم توضيح داده شده در اين مقاله از الگوريتم انتخاب تكي اي گرفته شده است كه توسط نويسنده همين مقاله قبلا ارائه شده است. نكته حائز اهميت اين است كه اين الگوريتم از لحاظ پيچيدگي و بازدهي مقدار كمي با الگوريتم قبلي تفاوت دارد و از اين لحاظ بهبود قابل توجه اي صورت گرفته است.

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

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

يك مورد خاص از پيدا كردن(انتخاب) كليدهاي چند گانه كه در اين مقاله مورد بحث قرار گرفته و مثالهاي ارائه شده از اين الگو پيروي مي كنند به اين صورت است كه هدف پيدا كردن p-1 كليد است (كليدهايي با مرتبه هاي n/p، 2n/p، ... و (p-1)n/p ) در سيستمي با n ركورد و p‌ كامپيوتر (سايت). براي مثال پيدا كردن 30 امين و 60 امين كليد در سيستمي با 90 ركورد و 3 كامپيوتر.

شرايط و فرضياتي كه در نظر گرفته شده است عبارتند از :

-         همه كامپيوتر ها با قابليت broadcast/multicast به يكديگر متصل شده اند.(مثلا در يك LAN)

-      يك فايل بزرگ به صورت فيزيكي مابين p كامپيوتر توزيع شده است و تعداد n ركورد به صورت تقريبا uniform بين اين n كامپيوتر تقسيم شده است(يعني n/p ركورد در هر كامپيوتر)

-      كليدهاي موجود در فايل به صورت X(i,k) نمايش داده مي شوند كه k عددي بين 1 و n/p‌ است و i شماره كامپيوتر را مشخص مي كند. كليدها در هر كامپيوتر مرتب شده اند و لذا داريم :

X(i,1) < X(i,2) < ...< X(i, k) < ... < X(i, n/p)

 

-         هيچ ترتيبي مابين كليدها در سايت هاي مختلف وجود ندارد. يعني مثلا دليلي ندارد كه كليد اول سايت اول از كليد اول سايت دوم كوچكتر باشد.

-         نحوه توزيع كليدها در كامپيوتر هاي مختلف مي تواند از هر توزيع آماري دلخواهي پيروي كند ولي در اين مقاله براي راحت تر شدن فهم مثالها از توزيع ساده uniform‌ استفاده شده است.

هدف اين الگوريتم پيدا كردن p-1 كليد هدف است. مرتبه كليدهاي مورد نظر در كل فايل jn/p است به طوري كه (1 . براي مثال پيد اكردن 30 امين و 60 امين كليد در سيستم 90 ركوردي با 3 كامپيوتر.

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

2-3-مراحل الگوريتم

فاز اول :

مرحله اول : يك كامپيوتر به عنوان coordinator انتخاب مي شود. هر كامپيوتري بزرگترين و كوچكترين كليد خود را به coordinator‌ اعلام مي كند. coordinator از روي مقادير دريافت شده MAX (بزرگترين كليد كل فايل) و MIN (كوچكترين كليد كل فايل) را پيدا مي كند و از روي آنها با استفاده از فرمول زير مقادير آغازين جدا كننده ها را پيدا مي كند:

DELIMITER_j = MIN + (MAX-MIN)j / p (1 <= j <= p-1)

 

مرحله دوم :

coordinator‌ مقادير p-1‌ جداكننده را به همه كامپيوتر ها ارسال مي كند.

مرحله سوم :

هر كامپيوتر p-1‌ محور (pivot) انتخاب مي كند. Pivot _i,j بزرگترين مقدار در كامپيوتر iام است كه از DELIMITER_j‌ كوچكتر است(يا با آن برابر است).

مراحل اول و دوم در صورتي كه MIN‌ و MAX‌ از قبل براي همه كامپيوتر ها مشخص باشد اختياري است و لذا ارسال پيامهاي مربوط به اين دو مرحله قابل كاهش است. در شكل زير مراحل 1 و 2 را مشاهده مي كنيد.

فاز دوم :

در اين فاز هر كامپيوتر به طور همزمان دو وظيفه را بر عهده دارد. اين دو وظيفه عبارتند از محاسبه محور و محاسبه رتبه. در هر مرحله هر كامپيوتر محور و رتبه محاسبه شده توسط خودش را منتشر مي كند. اين كار به صورت نوبتي و پشت سر هم انجا مي شود.

محاسبه رتبه :

r[i,j] را به صورت تعداد كليدهاي كوچكتر از محور i,j‌ در كامپيوتر i‌ تعريف مي كنيم. هر كامپيوتر p-1‌ محور از ساير كامپيوتر ها به صورت broadcast دريافت مي كند. و كامپيوتر ها مقادير كليدهاي محلي خود را با اين كليدها مقايسه مي كنند و به ترتيب و پشت سرهم كامپيوتر ها رتبه خود را نسبت به اين محور هاي اعلام شده به همه منتشر مي‌كنند.

محاسبه محور:

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

در صورتي كه كليد پيدا نشده باشد هر كامپيوتر محور جديدي با استفاده از متدي كه در زير معرفي شده است محاسبه مي كند.

محاسبه محور جديد :

در واقع بعد از هر مرحله هر فايل محلي به دو زير فايل تقسيم مي شود. همه كليدهاي موجود در زير فايل اول كوچكتر يا مساوي با محور i,j‌ هستند در حالي كه همه كليدهاي موجود در زير فايل دوم از اين مقدار بزرگتر هستند.

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

كه Offset_j به صورت زير محاسبه مي شود.

كوچكترين كليد در زير فايل دوم كه بزرگتر يا مساوي با NP‌ باشد به عنوان محور جديد در نظر گرفته مي شود. در صورتي كه به سراغ فايل اول رفته باشيم بزرگترين كليد در فايل اول كه كوچكتر يا مساوي با NP باشد به عنوان محور جديد در نظر گرفته مي شود.

در واقع الگويتم به صورت لگاريتمي عمل مي كند و هر دفعه فايل هاي محلي كامپيوتر ها را به دو قسمت تقسيم مي‌كند و در واقع مجازا در كل فايل چنين عملي در حال انجام است.

براي روشن تر شدن موضوع به مثال زير توجه كنيد :

مثال :

در شكل زير سه جدول Table1، Table2و Table3 كه در كامپيوتر هاي 1 و 2 و3 قرار دارند به همراه كليدهاي موجود در هر كدام مشاهده مي كنيد.

 

پيغام هاي رد و بدل شده بين كامپيوتر هاي مختلف در مراحل اجراي الگوريتم را در جدول زير مشاهده مي نماييد.

 

 

همانگونه كه مشاهده مي كنيد 30 امين كليد بعد از سه مرحله پيدا شد و از آنجا به بعد با ارسال حرف E‌ به ديگران گفته مي شود كه عمليات پيدا كردن اين كليد به پايان رسيده و نيازي به ادامه محاسبات روي اين كليد نيست. ولي همانگونه كه مشاهده مي كنيد كليد 60 ام هنوز پيدا نشده است، لذا عمليات براي پيدا كردن آن همچنان ادامه مي يابد تا اينكه در 5 مرحله اين كليد هم پيدا ميشود و عمليات كلا به پايان مي رسد.

در شكل زير نحوه انتقال پيغام ها بين كامپيوتر ها را در اولين مرحله‌ مشاهده مي كنيد.

 

2-4.محاسبات پيچيدگي الگوريتم

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

 

حد بالاي تعداد كل مراحل عبارت است از :

حد بالاي مجموع كليدهايي كه هر كامپيوتر نياز دارد تا براي ساير كامپيوتر ها در حين پروسه الگوريتم اعلام كند عبارت است از :

همچنين در مورد سيستمي كه قابليت Broadcast‌ ندارد نيز محاسبات پيچيدگي زماني و تعداد پيامها صورت گرفته است.

براي مثال حد بالاي تعداد پيغامهاي لازم براي پيدا كردن كليدي با رتبه J‌ در سيستمي بدون قابليت Broadcasting به صورت زير است :

 

2-5.آزمايشات تجربي

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

 

 

نمودار تعداد مراحل بر حسب تعداد كامپيوتر ها

 

همانطور كه مشاهده مي كنيد بالا رفتن تعداد كامپيوتر ها تاثيري بر تعداد مراحل ندارد.

 

 

نمودار تعداد پيغامها بر حسب تعداد كامپيوتر ها

 

همانگونه كه مشاهده مي كنيد با بالا رفتن تعداد كامپيوترها تعداد پيغامها به صورت خطي بالا مي رود.

 

نمودار تعداد مراحل بر اساس حجم فايل (تعداد ركوردها) در تعداد كامپيوتر هاي مختلف

 

نمودار تعداد پيامها بر حسب حجم فايل (تعداد ركوردها) در تعداد كامپوتر هاي مختلف

 

نمودار زمان بر حسب تعداد ركوردها در تعداد كامپيوتر هاي مختلف

 

در ادامه مقايسه اي صورت گرفته است مابين روشهاي قبلي و اين روش آماري ارائه شده.

 

 

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

 

 

3.الگوريتم پوياي Replication براي Data Grid هاي چند لايه

 

الگوريتم Dynamic Replication اي كه در اين قسمت معرفي مي شود برگرفته از [2] است. با اين حال براي بهبود كارايي الگوريتم پيشنهادهايي ارائه شده است كه در ادامه ذكر خواهيم نمود. data grid‌ ساختاري براي نگهداري فايلهاي اطلاعاتي با ابعاد بزرگ است و قابليت محاسباتي قدرتمندي براي سازمانهاي بزرگ و يا سيستمهاي اطلاعاتي مبتني بر community بزرگ فراهم مي كند. در data grid‌ اصولا كپي هاي متعددي از هر داده نگهداري مي شود و كاربران براي دسترسي به اطلاعات به در دسترس ترين و نزديك ترين و سريعترين كپي هدايت مي شوند. براي مديريت data grid ها مكانيزمهاي مختلفي تا كنون پيشنهاد شده است. يكي از مهمترين مسائلي كه در مديريت data grid‌ ها مطرح است ، چگونگي سيستم برخورد با replicate ها است. اينكه از كدام فايلها replicate ‌ بسازيم، چه موقع از داده ها replicate‌ ايجاد كنيم و اين replicate را در كجاي سيستم قرار دهيم تا بازدهي كلي data grid بالا برود از جمله مسائلي است كه پيرامون آنها بحث و تبادل نظر و تحقيقات وسيعي در جريان است. همچنين رعايت سازگاري ميان كپي هاي مختلف داده ها در سيستم هاي مبتني بر replication ازجمله مسائلي است كه تحقيقاتي براي حل مشكلات مربوط به آن صورت گرفته است [3].

3-1.انواع الگوريتمهاي موجود

با نگاهي به سوابق تحقيقاتي در اين زمينه روشهاي replication‌ را به دو دسته كلي تقسيم كرده اند.

دسته اول Static Replication است كه در آن سياست Replication از ابتدا به صورت ثابت و ايستا مشخص مي گردد و در واقع جزئي از پيكربندي سيستم محسوب مي شود. مسلما با تغيير توپولوژي شبكه data grid و يا تغيير الگوي درخواستها تغييري در اين سياست داده نخواهد شد. لذا بازدهي سيستم به شدت پايين مي آيد و ممكن است از منابع به شكل مناسب و مطلوب استفاده نشود. به عنوان مثال ممكن است تعداد استفاده كنندگان از سيستم در زمان تعيين سياست ها به صورت ايستا 50 عدد در نظر گرفته شده باشد، در حالي كه پس از گذشت مدتي تعداد كاربران به 500 عدد برسد و يا تعداد كاربران متصل به يك نود خاص بيشتر از بقيه بوده باشد و بعد از گذشت مدتي اين الگو تغيير كند و ترافيك نود ديگري بالا برود.

در مقابل اين روش، روش دايناميك وجود دارد كه در آن data grid‌ با توجه به تغيير الگوهاي دسترسي و موارد متغير ديگر به صورت اتوماتيك در زمان نياز به ساخت replicate‌ مي پردازد و آن را در جاي مناسب قرار مي دهد تا فركانس دسترسي به آن بهينه باشد و باعث بالا رفتن هزينه نگردد.

3-2.معماري سيستم

معماري سيستمي را كه از replication به صورت پويا استفاده مي كند در شكل زير مشاهده مي كنيد.

 

همانطور كه در شكل مشاهده مي كنيد، وقتي يك كاربر مي خواهد به يك فايل داده اي دسترسي داشته باشد، براي دسترسي به آن فايل نام آن را به RS(Replica Selector) ارسال مي دارد. وظيفه RS‌ انتخاب يك replica‌ مناسب براي سرويس دهي با درخواست اين كاربر است. معيارهايي كه براي انتخاب replica مناسب در نظر گرفته مي شود عموما نزديكي replica‌ به كاربري كه درخواست داده است و همچنين ميزان ترافيك فعلي replica‌ ها براي دسترسي است. يعني بايد replica‌ اي كه نزديكتر است و سرش خلوت تر است انتخاب شود. به اين ترتيب پهناي باند شبكه كمتر مصرف خواهد شد و زمان پاسخگويي به درخواست هم بالا خواهد رفت.

وقتي كه RS‌ مكان درست فايل داده اي را به درخواست كننده اعلام كرد، درخواست كننده با LRM(Local Replica Manager) مربوط به آن نود ارتباط برقرار مي كند. وظيفه LRM مديريت replica هاي موجود در يك سايت است.

براي هر انتقال فايل موفقيت آميزي كه صورت مي گيرد، LRM ، DRS(Dynamic Replica Scheduler) را صدا ميزند و اين انتقال موفق را به او خبر مي دهد.

DRS مسوول زمانبندي Replication‌ است. يعني تعيين مي كند كه چه زماني نياز است يك replication‌ جديد از فايل داده اي خاصي ايجاد شود. هرگاه كه خبر انتقال موفقيت آميزي به DRS‌ داده مي شود، اين خبر را log‌ مي كند. درواقع شمارنده تعداد دسترسي هاي انجام شده به آن فايل داده اي را يكي افزايش مي دهد.

در واقع DRS‌ وظيفه دارد كه اين log‌ ها را نگهداري كند و در بازه هاي زماني خاصي فايلهاي داده اي با محبوبيت بيشتر را شناسايي كند و براي آنها يك مكان كناسب در نظر بگيرد و دستور ساخت replica از آنها را صادر نمايد و سپس تعداد دسترسي هاي انجام شده را صفر كند و اين كار را دوباره ادامه بدهد. هر گاه DRS تشخيص بدهد كه بايد جابجايي صورت بگيرد دستور لازم را به LRM‌ سايت مربوطه ارسال مي كند و LRM خودش ساخت Replica‌ جديد را انجام مي دهد و نتيجه را به DRS‌ خبر مي دهد. DRS‌ با شنيدن خبر ساخت موفقيت آميز يك replica‌ جديد موضوع را به RC (Replica Catalogue)‌ خبر مي دهد تا خود را بروزرساني كند و ظهور replica‌ جديد را در سيستم در نظر بگيرد. RC‌ همانند يك name server‌ عمل مي كند و نگاشتي مابين فايلهاي منطقي و مكان فيزيكي آنها اعمال مي كند. براي اطمينان از سازگاري سيستم، خبر ساخت و يا حذف replica‌ ها بايد به RC‌ اعلام شود. توجه داشته باشد كه lock‌ ها هم در RC نگهداري مي شود ولي توسط DRS‌ مديريت مي شوند. هنگامي كه عمل نوشتن در يكي از replica‌ ها مي خواهد صورت بگيرد، DRS روي داده Lock مي گذارد و بعد از اينكه نوشتن به پايان رسيد DRS‌ همه replica‌ هاي متناظر را با تغيير داده شده هماهنگ مي كند و پس از اطمينان از اينكه كپي هاي مختلف نگهداري شده در سيستم با هم سازگار شدند، Lock‌ را از روي داده بر مي دارد.

3-3.پيشنهاد بهبود معماري

از آنچه كه تا كنون گفتيم اينگونه مي توان نتيجه گرفت كه وظايف DRS، RS و RC روي يك نود قرار گرفته است و همانطور كه مشخص است، سيستم وابستگي زيادي به اين اجزا دارد. لذا از بين رفتن يا خراب شدن هر كدام از اين اجزا مي تواند كل سيستم را از كار بيندازد. براي رفع اين مشكل پيشنهاد مي كنيم معماري ارائه شده در اين مقاله به صورت زير تغيير كند.

همانطور كه مشاهده مي كنيد در اين معماري بهبود يافته براي اين اجزاي حساس، كپي هاي متعددي در نظر گرفته شده و به كمك اين كي ها سيستم توزيع شده تر مي گردد. اين كپي ها در بازه هاي زماني خاصي نسخه فعلي را بررسي مي كنند و چنانچه متوجه شوند كه از كار افتاده است با استفاده از الگوريتم توزيع شده bully [4] از بين خود يكي را انتخاب مي كنند و از اين پس وظيفه بر عهده كپي منتخب خواهد بود. به اين ترتيب تحمل سيستم در برابر خرابي بالا خواهد رفت سيستم توزيع شده تر عمل خواهد نمود.

حال كه با معماري سيستم آشنا شديم به بررسي الگوريتم هاي ارائه شده براي زمانبندي replication‌ خواهيم پرداخت.

3-4.الگوريتمهاي replication‌ به صورت پويا

3-4-1.روش SBU

اولين روشSBU يا Single Bottom Up‌ نام دارد. ايده اصلي نهفته در اين الگوريتم قرار دادن replica‌ ها تا جايي كه ممكن است، نزديك نودهايي است كه استفاده بيشتري از اين replica دارند.

وقتي كه تعداد درخواستهاي كاربران از حد آستانه مشخصي مي گذرد، عمل replication‌ صورت مي گيرد. در واقع الگوريتم در DRS انجام مي شود و در دوره هاي زماني خاصي log‌ هاي گرفته شده جستجو مي شوند و دسترسي هايي كه از حد آستانه خود گذشته اند براي انتقال replica‌ به سمت آنها در نظر گرفته مس شوند. در اين الگوريتم ساده در ساختار درختي data grid سعي بر اين است كه replica‌ دقيقا در والد نودي كه درخواست كننده بيش از حد آستاده داشته قرار داده شود. ولي چنانچه اين نود پر بود و جا نداشت به سراغ والد آن مي رويم و اين كار را تا ريشه درخت ادامه مي دهيم. چنانچه در حال حاضر replica‌ در والد نود مورد نظر قرار داشت از انجام عمليات replication خودداري مي كنيم و به صفر كردن تعداد دسترسي ها در فايل log‌ مبادرت مي ورزيم.

3-4-2.روش ABU

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

شكل زير را در نظر بگيريد :

 

همانگونه كه در اين شكل مشاهده مي كنيد نود C1 به فايل داده اي x‌ تعداد 10 بار دستيابي كرده است و نود c2‌ به فايل داده اي Y تعداد 9 بار دستيابي كرده و فايل داده اي y توسط C3 تعداد 8 بار مورد دستيابي قرار گرفته است. همانگونه كه مي بينيد فايل داده اي y‌ مجموعا توسط نودهايي كه به والد S1 متصل هستند 17 بار مورد دستيابي قرار گرفته شده است. پس انتقال Y‌ به S1‌ ضروري به نظر مي رسد. چنانچه از روش SBU با حد آستانه 10 استفاده كنيم، فايل X‌ به S1‌ منتقل مي شود در حالي كه نود Y كه انتقال آن ضروري تر به نظر مي رسد منتقل نخواهد شد. به همين منظور از روش ABU به عنوان روش بهبود يافته SBU استفاده مي شود. در اين روش دسترسي هايي كه به فايل داده‌اي يكساني انجام شده است با هم جمع مي شوند حد آستانه براي مجموع در نظر گرفته مي شود. به اين ترتيب معيار بهتري براي تشخيص زمان و مكان replication به دست مي آيد كه كارايي سيستم را بالاتر خواهد برد.

 

4.منابع

 

1. A. Loo, “Distributed multiple selection algorithm for peer-to-peer systems” Elsevier, 25 Agust 2004
2. M. Tang, B. Lee, C. Yeo, X. Tang, “Dynamic Replication Algorithms For The Multitier Data Grid” Elsevier, October 2004.
3. A. Domenici, F. Donnob,G. Pucciani, H. Stockingerc,K. Stockinger, “Replica consistency in a Data Grid” Elsevier, July 2004
4. Ramkrishnan, Gehrke, “Database Management Systems Third Edition”

 

 

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

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

 

پدرام قدس نيا

اشكان بياتي

 

دانشکده مهندسی برق و کامپيوتر

دانشگاه تهران

 

فهرست مطالب

 

1. مكانيزمهاي سنتي براي كنترل همزماني

1-1. روش S2PL

1-2. روش خوشبينانه (Optimistic)

2. روشهاي جديد و بهبود يافته براي كنترل توزيع شده همزماني

2-1. گراف توالي پذيري

2-2. روش تست گراف توالي پذيري نامتمركز (DSGT)

3. مقايسه DSGT‌ با S2PL

4. Replication و پروتكل DSGT

5. منابع

 

 

 

 

 

 

 

1. مكانيزمهاي سنتي براي كنترل همزماني

 

بانكهاي اطلاعاتي توزيع شده و يا متمركز به صورت سنتي براي اطمينان از توالي پذير بودن و قابل برگشت بودن زمانبندي ها از مكانيزمها و پروتكل هاي قفل گذاري (Locking) استفاده مي كنند. پروتكلهاي قفل گذاري تضمين مي كنند كه تراكنشهاي برگ برگ شده(interleaved) و يا توزيع شده در اثر تاثير شبكه اي به وجود آمده مجازا به صورت معادل با تراكنشهايي كه نظم سريالي دارند اجرا شوند. يكي از متداولترين پروتكلهاي قفل گذاري كه در سيستمهاي متمركز و توزيع شده استفاده مي شود قفل گذاري محدود در دو فاز ياstrict two phase locking نام داردكه به اختصار به آن S2PL مي گويند[1].

 

1-1. روش S2PL

در فاز اول اين پروتكل، يك تراكنش T‌، روي اشياي داده اي مورد نيازش، قفلهاي اشتراكي و يا انحصاري لازم را مي‌گيرد. يك مكانيزم پيش فرض براي گرفتن قفل توسط تراكنش T اين است كه تراكنش براي گرفتن قفل بلاك مي‌شود تا زماني كه امكان گرفتن قفل به وجود آيد. خود DBMS‌ شروط Mutual Exclusion را تضمين مي كند و از گرفته شدن يك قفل انحصاري توسط دو تراكنش جلوگيري به عمل مي آورد.

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

 

S2Pl بانك اطلاعاتي را در يك وضعيت سازگار نگه مي دارد. اگر دو تراكنش به دو بخش مستقل از اطلاعات بانك اطلاعاتي دسترسي داشته باشند مي توانند به صورت همزمان قفل هاي مورد نياز خود را دريافت كنند و كار خود را با موفقيت ادامه داده و به پايان ببرند. از طرف ديگر اگر دو تراكنش به داده هاي يكساني دسترسي داشته باشند و بخواهند اين داده ها را تغيير دهند فعاليتهاي آنها به صورت سريال يا پشت سر هم انجام خواهد شد. يعني تراكنشي كه زودتر براي تغيير آن اطلاعات قفل دريافت كرده همه عمليات درون خود را انجام مي دهد و به پايان مي رساند و سپس كنترل به دست تراكنش ديگر مي افتد و كارهايش را از اول تا آخر انجام مي دهد. از آنجايي كه در S2PL‌ تراكنشهايي كه زودتر قفل را گرفته اند تا زماني كه commit نشوند قفلهاي در اختيار خود را آزاد نمي كنند، لذا در صورتي كه تراكنشهاي بزرگي باشند، ساير تراكنشها كه منتظر اين قفلها هستند ممكن است مدت انتظارشان خيلي طولاني بشود.

 

1-2. روش خوشبينانه (Optimistic)

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

اين روش كه در [2] آمده است مزاياي زير را به همراه دارد:

1-    از آنجايي كه روش خوشبينانه بر مبناي قفل گذاري كار نمي كند، لذا امكان به وجود آمدن بن بست وجود نخواهد داشت و لذا سيستم به علت بروز بن بست در يك توقف كامل نخواهد افتاد و لذا ديگر نيازي به بكارگيري الگوريتمهاي تشخيص بن بست و همچنين رفع بن بست نخواهيم داشت. همانطور كه مي دانيم استفاده از اين الگوريتم ها سر بار زيادي را براي سيستم به دنبال دارد و اين سربار زماني كه بن بست وجود ندارد و بيهوده الگوريتم تشخيص بن بست اجرا مي شود بيشتر باعث اتلاف منابع سيستم مي شود[3].

2-    روش خوشبينانه به خصوص وقتي فايده عدم استفاده از قفل را نمايان مي سازد كه بخش بزرگي از بانك اطلاعاتي در حافظه جانبي باشد و اين بدان دليل است كه يك شي داده اي تحت فشار از لحاظ دسترسي مي‌تواند توسط يك تراكنش قفل شده، و به تراكنشهاي ديگر اجازه استفاده از اين شي‌ء داده نشود در حالي كه تراكنشي كه قفل را در دست دارد در حال بازيابي اطلاعات از حافظه جانبي است.

3-    استفاده از روشهاي مدرن كه درشت دانگي قفل ها را امكانپذير مي سازند در زماني كه در پروتكل مبتني بر قفل تداخل به وجود مي آيد زياد مقرون به صرفه نيست. در چنين شرايطي اولا قفل گذاشتن روي سطوح بالاتر ميزان همزماني را پايين خواهد آورد و در ثاني قفل گذاشتن روي سطوح پايين نيز با سربار بسيار زيادي روبرو خواهد بود و بازدهي سيستم را به شدت پايين خواهد آورد.

 

ايده اصلي مكانيزم خوشبينانه حول محور برگرداندن (rollback) تراكنشي كه با تراكنش ديگر تداخل پيدا كرده است به حالت اول مي گردد. براي تشخيص تراكنشي كه با تراكنش ديگر تداخل كرده است روش خوشبينانه سه فاز را در نظر مي‌گيرد. اين سه فاز عبارتند از read، validationو write. البته ممكن است فاز write‌ وجود نداشته باشد.

 

‌شكل 1

 

در شكل 1 سه فاز مذكور را مشاهده مي نماييد. در حين فاز read‌ همه نوشتنها روي كپي هاي محلي از اطلاعات انجام مي گيرد. در فاز validation‌ چنانچه تشخيص داده شود كه انتقال كپي هاي محلي به سرجاي خودشان در بانك اطلاعاتي اصلي يكپارچكي داده ها را به هم نمي زند فاز write آغاز مي شود و اطلاعات محلي به صورت سرتاسري در خواهند آمد و در غير اين صورت تراكنش برگشت داده خواهد شد. در مقايسه با روشهاي قفل گذاري مي توان گفت كه قفل گذاري هر جا كه احتمال تداخل وجود داشت انجام مي شد واگر تراكنشي به قفلي مي رسيد كه نمي‌توانست آن را بگيرد بلاك مي شد ولي در اينجا تراكنش تا فاز validation‌ به اميد اينكه تداخلي وجود نخواهد داشت پيش مي‌رود و لذا همزماني بيشتري در اين روش مابين تراكنشها امكانپذير خواهد شد. در ضمن برگشت تراكنش حتما به ابتداي آن صورت نمي گيرد بلكه ممكن است به يك checkpoint صورت گيرد و به اين ترتيب كارايي را بالاتر هم ببرد. نكته حائز اهميت اين است كه كپي محلي اي كه براي انجام تغييرات در فاز read در نظر گرفته شده است براي ساير تراكنشها سرتاسري نخواهد شد تا زماني كه فاز write‌ كاملا به پايان برسد. در واقع كل فاز write‌ بايد به صورت درشت دانه و يكجا انجام شود و در حين عمل write‌ تراكنش ديگري به اين اطلاعات در حال تغيير دست نزند تا از به وجود آمدن ناسازگاري در اطلاعات جلوگيري شود.

 

براي اينكه يك تراكنش بتواند فاز validation‌ را با موفقيت به پايان برساند بايد يكي از شرايط زير برقرار باشد :

1- T(i) فاز write خودر را به پايان ببرد، پيش از اينكه T(j) فاز read خود را آغاز كند.

2- مجموعه نوشتنهاي T(i) با مجموعه خواندنهاي T(j) اشتراكي نداشته باشد و T(i) فاز write خود را به پايان برساند قبل از اينكه T(j)‌ فاز write خود را آغاز كند.

3- مجموعه نوشتنهاي T(i) با مجموعه نوشتنها و يا خواندنهاي T(j)‌ اشتراكي نداشته باشد و T(i)‌ قبل از T(j) فاز read خود را به پايان ببرد.

شرايط شماره 1 بيانگر اين است كه T(i) قبل از شروع T(j)‌ به طور كامل به پايان مي رسد و لذا به كلي تداخلي وجود نخواهد داشت.

شرايط شماره 2 حالتي را نشان مي دهد كه در آن نوشتنهاي T(i)‌ تاثيري روي فاز خواندن T(j)‌ نخواهند داشت و T(i)‌ نوشتن خود را قبل از شروع نوشتن T(j)‌ به پايان مي برد و لذا T(j)‌ را بازنويسي نخواهد كرد.

و در نهايت شرايط شماره 3 حالتي را نشان مي دهد كه در آن T(i) فازهاي read يا write‌ مربوط به T(j)‌ را تحت تاثير قرار نخواهد داد . دياگرام هاي شكل 2 براي روشن تر شدن موضوع شرايط بالا را نشان مي دهند:

 

شكل 2

 

در اينجا يك سوال مهم اين است كه در اين روش چه زماني بايد شماره تراكنش را به آن تخصيص داد؟

در نگاه اول اينگونه به نظر مي رسد كه اين شماره بايد در ابتداي فاز read اختصاص يابد. به طور كلي تراكنشي كه شماره بالاتري دارد بايد منتظر تراكنشهاي با شماره پايين تر از خود بماند و اين صبر كردن به اين دليل است كه فاز validation‌ در يك تراكنش به مجموعه نوشتن هاي تراكنشهايي كه قبل از آن شروع شده اند و در واقع شماره كوچكتري از آن دارند وابسته است.بنابراين براي اينكه اين مجموعه را كاهش بدهيم بهتر است كه تخصيص شماره به يك تراكنش را تا پايان فاز read يا شروع فاز validation به تعويق بيندازيم. به اين ترتيب، ترتيب دو تراكنشي كه زمان شروع آنها حدودا با هم برابر است به اين بستگي پيدا مي كند كه كدام يك فاز read‌ خود را زودتر به پايان برسانند. در شكل 3 شرايطي را مي بينيد كه در آن T1‌ زودتر از T2 شروع شده است ولي فاز read‌ خود را ديرتر از T2‌ به پايان برده است.

 

شكل 3

 

انتخاب پايان فاز read به عنوان زمان اختصاص شماره تراكنش موجب مي شود كه زمان لازم براي فاز validation كاهش يابد و در كل بازدهي را بهبود خواهد بخشيد.

 

2. روشهاي جديد و بهبود يافته براي كنترل توزيع شده همزماني

 

با وجود اينكه مي توان از متدهاي ذكر شده (S2PL و روش خوشبينانه) در سيستمهاي توزيع شده بهره جست، با اين حال اين روشها مشكلاتي را به دنبال دارند. براي اسنفاده از روش قفل گذاري محدود دو مرحله اي در يك محيط توزيع شده بايد از يك پروتكل توزيع شده مديريت بن بست و يك پروتكل commit دو مرحله اي (2PC) ياري جست. لذا استفاده از اين روش هنگامي كه تراكنشها طولاني هستند با كاهش بازدهي جدي روبرو خواهد بود. روش خوشبينانه نيز زماني در يك محيط توزيع شده قابل استفاده است كه در اين محيط مكانيزمي براي انجام فاز validation به صورت توزيع شده وجود داشته باشد. بعلاوه اين روش در زماني كه طول تراكنشها زياد است با مشكل پايين بودن بازدهي شديد روبرو خواهد بود زيرا ممكن است به rollback هاي زيادي بيانجامد. مكانيزم ديگري كه در [4] بحث شده است از مهر زماني (timestamp) كمك مي گيرد. هر تراكنشي هنگام ورودش به سيستم زمان ورودش را ثبت مي كند. در توالي اجراي دستكاري هاي اشياء اطلاعاتي بايد اين ترتيب ورود در نظر گرفته شود. اين مكانيزم نيز با مشكل تعداد rollback‌ هاي زياد در هنگام طولاني بودن طول تراكنشها روبروست. علاوه بر مشكل بازدهي، اين روش با مشكل شناخته شده و معروف ديگري تحت عنوان زمان سراسري و همزمان سازي ساعت در سيستمهاي توزيع شده نيز دست و پنجه نرم مي كند[4]. در ادامه اين گزارش به بحث پيرامون يك روش اشتقاقي از روش تست گراف توالي پذيري نا متمركز يا Decentralized Serialization Graph Test(DSGT) پرداخته خواهد شد. اين روش در [5] توضيح داده شده است و بازدهي آن در مقايسه با روش S2PL‌ در محيط توزيع شده مورد بررسي قرار گرفته است.

 

2-1. گراف توالي پذيري

قبل از اينكه DSGT‌ توضيح داده شود، شرح مختصري خواهيم داشت درباره گراف توالي پذيري. اين گراف براي مشخص كردن همه تداخلات ممكن (بالقوه)‌ ميان تراكنشها مورد استفاده قرار مي گيرد. يك گراف توالي پذيري براي يك زمانبندي S مشتمل است بر :

1-     يك گره براي هر تراكنش commit شده در S.

2-     يك يال از T(i) به T(j) اگر يكي از اعمال T(i)‌ قبل از يكي از اعمال T(j) انجام شود و در عين حال با آن تداخل هم داشته باشد [1].

 

با يك مثال با موضوع بيشتر آشنا خواهيم شد.زمانبندي شكل 4 را در نظر بگيريد:

 

شكل 4

گراف توالي پذيري اين زمانبندي در شكل 5 مشخص شده است:

 

شكل 5

 

مهمترين نكته در مورد گراف توالي پذيري اين است كه يك زمانبندي توالي پذير متداخل (conflict serializable) است، اگر و فقط اگر گراف توالي پذيري آن دور داشته باشد[1].

 

2-2. روش تست گراف توالي پذيري نامتمركز (DSGT)

حال كه با مقدمات لازم آشنا شديم مي توانيم نگاه عميقتري به پروتكل DSGT داشته باشيم. در اين پروتكل هر تراكنش گراف توالي پذيري محلي مربوط به خود را نگهداري مي كند كه بيانگر تداخل هايي است كه اين تراكنش در آنها شركت دارد. اساسا، اين گراف حداقل شامل همه تداخل هايي است كه باعث مي شود تراكنش به تراكنشهاي ديگر وابسته باشد. به زودي خواهيم ديد كه چرا همين اطلاعات مختصر براي تصميم گيري در مورد اينكه چه موقع تراكنش commit‌ بشود كافي است. به خاطر داشته باشيد كه به تراكنشها زماني اجازه داده مي شود commit بشوند كه تمام تراكنشهايي كه اين تراكنش به آنها وابسته بوده است commit شوند.

پروتكل DSGT مبتني بر ملاحضات زير است :

1-    وابستگيهاي مابين تراكنشها توسط خود آنها قابل تشخيص و مديريت است، لذا به هيچ هماهنگ كننده مركزي اي نيازي وجود ندارد و پروتكل كاملا به صورت توزيع شده عمل مي كند.

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

در ادامه اين ملاحضات DSGT تضمين مي كند كه يك تراكنش تنها زماني commit‌ شود كه همانند روش خوشبينانه همه تراكنشهاي قبل از آن commit شده باشند. يك تراكنش اطلاعات مربوط به تراكنشهاي پيش از خود را از طريق برقراري ارتباط و رد و بدل كردن پيغامهايي با سايتهايي كه تراكنشهاي پيش از خودش مشغول خواندن و يا اعمال تغييرات در آنها هستند به دست مي آورد. اصولا هر سايتي كه كه شامل تعدادي شيء داده اي براي درخواست و يا تغيير است ليستي از داده هايي كه روي آنها تداخل وجود دارد و تراكنشهايي كه موجب اين تداخلات روي اين اشياء داده اي شده اند نگهداري مي كند. تراكنشي كه اين اشياء داده اي را براي خواندن و يا تغيير از سايت مربوطه درخواست مي كند اطلاعات جانبي مربوط به تداخلات را نيز از ليست تداخلات آن سايت دريافت مي كند و از روي اين اطلاعات گراف محلي خود را تكميل مي كند. اين اطلاعات براي اين منظور استفاده مي شود كه تراكنش به صورت اتوماتيك خودش بتواند تصميم بگيرد كه commit بشود يا نه. اگر در زمان commit يك تراكنش متوجه بشود كه به تراكنش ديگري وابسته است صبر مي كند تا commit آن تراكنش را از سايت مربوطه دريافت كند. بنابراين به عنوان يك بخش ضروري در اين پروتكل هر تراكنش موظف است كه پس از commit شدن، اين مطلب را به همه تراكنشهايي كه منتظر commit شدن او هستند اطلاع دهد.

از آنجايي كه اين روش نيز يك روش خوشبينانه است همه خواندن ها و تغييرات قبل از چك كردن براي تداخل انجام مي گيرد و چك كردن تداخل بعدا صورت مي گيرد(مثل روش خوشبينانه سنتي). همانند روش خوشبينانه سنتي براي حل وابستگيهاي دوري انجام عمل rollback در بسياري موارد ضروري مي شود. همچنين به دليل خوشبينانه بودن اين روش همانند روش سنتي از rollback هاي موضعي استفاده مي شود تا زماني كه وابستگيهاي دوري خود را نشان دهند. توجه داشته باشيد كه در اين مكانيزم برعكس همه فعاليت ها نيز مي تواند انجام پذيرد. اين سرويسها تحت عنوان سرويسهاي جبران شناخته مي شوند و در حين rollback‌ هاي موضعي مورد استفاده قرار مي گيرند. وقتي تراكنشي تصميم به commit مي گيرد پيغامي به همه سايتهايي كه داده هاي آنها را دست كاري كرده يا خوانده ارسال مي كند و در پاسخ ليستي از تراكنشهايي كه منتظر او هستند را از آن سايتها دريافت مي كند و از اين ليست براي مطلع كردن آنها از commit‌ شدن خود استفاده مي كند.

در شكل 6 وضعيت هاي مختلفي كه يك تراكنش در حين اجراي سرويسهاي موجود روي سايت هاي مختلف مي‌تواند به خود بگيرد را مشاهده مي نماييد:

شكل 6

تغيير وضعيت هاي زير در اين دياگرام در نظر گرفته شده اند:

-      تغيير ازforward execution به validation : اگر يك تراكنش اجراي همه سرويسهاي درخواستي خود را با موفقيت به پايان برساند وارد فاز validation مي شود.

-      تغيير از validation‌ به backward execution : اگر تراكنشي تشخيص بدهد كه در يك دور قرار گرفته و بايد rollback شود به وضعيت backward execution‌ مي رود.

-      تغيير از forward execution‌ به backward execution : اين تغيير وقتي رخ مي دهد كه تراكنش بايد rollback‌ شود به دليل rollback شدن يكي از تراكنش هايي كه به آنها وابسته است و يا وقتي كه گراف توالي پذيري محلي شامل دور است و اين تراكنش طعمه rollback‌ شناخته مي شود.

-      تغيير از backward execution‌ به forward execution : به محض اينكه تمام سرويسهاي احضار شده مورد نياز جبران شدند تراكنش دوباره به وضعيت forward execution‌ باز مي گردد.

-      تغيير از validation به inform peers : اين تغيير وضعيت زماني رخ مي دهد كه در حاصل validation‌ مشخص شود كه اين تراكنش در گراف توالي پذيري محلي داراي يال ورودي است و به عبارت ديگر تراكنشهاي ديگري منتظر commit‌ شدن اين تراكنش هستند.

-      تغيير از inform peers به inform Txs : اين تغيير وضعيت زماني رخ مي دهد كه تمام سايتهايي كه خبر commit‌ شدن به آنها ارسال شده بود پاسخ بدهند.

 

از آنجايي كه هيچ تراكنشي قبل از اينكه تمام تراكنشهايي كه به آنها وابسته است commit‌ نشوند، commit نمي‌شود، لذا اين پروتكل يك زمانبندي توالي پذير را تضمين مي كند[7].

 

در يك جمع بندي كلي پروتكل DSGT اجراي سرتاسري درست تراكنشها را بدون نياز به يك هماهنگ كننده مركزي (coordinator) امكانپذير مي سازد. ايده اصلي اين پروتكل اين است كه وابستگيهاي مابين تراكنشها توسط خود آنها مديريت شود. فرايند موجود شباهت زيادي به روش خوشبينانه سه مرحله اي دارد، البته از اين لحاظ كه هيچ مكانيزم قفل گذاري اي براي نوشتن و يا خواندن اشياء داده اي در آن استفاده نمي شود، در عوض تراكنشها انجام مي‌شوند تا به فاز validatoin‌ برسند و در آنجا بر اساس اينكه تداخلي با تراكنشهاي ديگر دارند يا خير rollback‌ يا commit‌ مي شوند. مكانيرم تشخيص تداخل با ساير تراكنشها از طريق گراف توالي پذيري صورت ميگيرد. يكي از نكات حائز اهميت در اين روش استفاده از rollback‌ هاي موضعي است. استفاده از اين پروسه به خصوص زماني اهميت خود را نشان مي دهد كه از انتشار abort در سيستم جلوگيري مي كند و به اين ترتيب در بازدهي كار تاثير به سزايي بر جاي خواهد گذاشت.

 

 

3. مقايسه DSGT‌ با S2PL

در ادامه مقاله نتايج تجربي پروتكل توزيع شده DSGT‌ با تكيه بر rollback‌ ها موضعي آورده شده است اين نتايج با S2PL مقايسه شده است. در دياگرام زير مقايسه بازدهي DSGT‌ را با S2PL در شرايطي كه تداخلي نداريم مشاهده مي كنيد.

شكل 7

همانطور كه در نمودار شكل 7 مي بينيد، DSGT (منحني بالايي) در بالاي S2Pl‌ (منحني پاييني) قرار دارد. در شرايطي كه تداخل وجود ندارد همانگونه كه مي بينيد با بالا رفتن تعداد سرويسها بازدهي بالا مي رود. در اين شرايط S2PL به دليل سربار ناشي از گرفتن قفل هاي بيهوده(با اينكه تداخل وجود ندارد باز هم قفل مي گيرد) همواره پايين‌تر از DSGT است. در شرايطي كه تداخل وجود داشته باشد بديهي است باز هم كارايي روش DSGT‌ از S2PL پايين تر خواهد بود. در اين شرايط پايين بودن كارايي S2PL به اين دليل است كه با گرفتن قفلها ساير تراكنشها نمي توانند ادامه پيدا كنند و تراكنشهاي كوچك ممكن است پشت تراكنشهاي طولاني تر منتظر بمانند و اين پديده با افزايش تعداد سرويسها شدت بيشتري خواهد گرفت و بازدهي را پايين تر خواهد آورد. بعلاوه ميزان رد و بدل شدن پيامها نيز در روش S2PL بسيار بيشتر از روش DSGT‌ خواهد بود كه اين واقعيت پهناي باند زيادي را از شبكه هدر خواهد داد.

 

4. Replication و پروتكل DSGT

در پروتوكل DSGT‌ اي كه شرح داده شد فرض بر اين است كه در سيستم نوعي partitioning‌ صورت گرفته و هر بخش از اطلاعات در سايت به خصوصي قرار دارد و در يك سيستم peer2peer‌ سايت ها با يكديگر ارتباط دارند. آنچه حائز اهميت است اين است كه در چنين سيستمي نمي توانيم replication‌ داشته باشيم. لذا روش ارائه شده براي سيستمهاي توزيع شده اي كه مبتني بر replication‌ هستند مناسب نمي باشد. علت اين مطلب اين است در روش شرح داده شده هر تراكنش براي دستيابي به اطلاعات يك وب سايت محدوديتي ندارد و عمل چك كردن محدوديتها تنها در فاز validation صورت مي گيرد. فرض كنيد داده اي در چند سايت replicate‌ شده باشد و سه تراكنش مختلف هر كدام يكي از replica‌ ها را دستكاري اطلاعاتي كنند. در چنين شرايطي مكانيزمي براي ايجاد سازگاري ميان كپي هاي مختلف داده اجباري است و در غير اين صورت مفهوم replication را نخواهيم داشت. براي بهبود اين روش و تغيير آن به گونه اي كه از replication نيز پشتيباني نمايد تا روشي ارائه نشده است. در گزارش بعدي در صورت پيدا كردن روشي مناسب براي حل اين مشكل، روش ارائه شده شرح داده خواهد شد.

 

 

5. منابع

 

[1] Ramkrishnan, Gehrke, “Database Management Systems Third Edition”

[2] H. T Kung, J. T. Robinson, “On Optimistic Methods for Concurrency

Control”, ACM 0362-5915/81/0600 1981.

[3] S. Chen, Y. Ling, “Stochastic Analysis of Distributed Deadlock Scheduling” ACM 1-58113-994-2/05/0007 2005.

[4] G. Coulouris, J. Dollimore, T. Kindberg, “Distributed Systems Concepts and Design” third Edition 2001

[5] K. Haller, H. Schuldt, C. Turker, “Decentralized Coordination of Transactional Processes in Peer-to-Peer Environments.

ACM 1-59593-140-6/05/0010 2005.

[6] A.Silberschatz, H.F.Korth, S. Sudarshan, Database System Concepts(Book)

[7] K. Haller, H. Shuldt, C. Turker. A fully Decentralized approach to coordionating Tranactional processes in peer-to-peer environments. Technical report 463, ETH Zurich, Switzerland, 2004.

 

 

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

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

 

پدرام قدس نيا

اشكان بياتي

 

دانشکده مهندسی برق و کامپيوتر

دانشگاه تهران

 

 

فهرست مطالب :

 

مقدمه

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

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

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

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

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

6. منابع

 

 

مقدمه

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

 

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

 

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

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

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

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

معايب روش Replication :

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

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

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

 

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

 

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

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

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

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

 

اين سه مدل عبارتد از :

·        One-Per Object [OP]

·        Client-Centric [CC]

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

 

در اين نمودار به مقايسه مدلها از لحاظ زمان لازم براي Synchronization‌با توجه به تعداد client ها در پهناي باند 10Mbps پرداخته شده است. همانگونه كه مشاهده مي فرماييد در اينجا به دليل اينكه پهناي باند افزايش يافته تاخير مدل OG كاهش يافته است. در واقع در اينجا فرستادن همه update file‌ ها براي همه client‌ ها يك ضعف محسوب نمي شود زيرا به علت بالا بودن پهناي باند اين عمل سريع انجام مي شود. در اين حالت پارامتري كه اهميت خود را بيش از پارامترهاي ديگر نشان مي‌دهد زمان ساخته شدن update file‌ ها است. در مدل CC‌ به دليل تكرار شدن زياد داده ها عمل كپي كردن در ديسك زمانبر است. و در واقع حال كه پهناي باند زياد شده سرعت ديسك از آن عقب مانده است. پس مدلي كه سرعت ديسك كمتري نياز دارد موفق تر خواهد بود. به همين دليل مدل CC در اين حالت از دو مدل ديگر به شدت نا موفق تر است.

در واقع از اين مقاله نتيجه مي شود كه مدل سنتي CC‌ به دليل نداشتن قابليت گسترش مدل مناسبي نمي‌باشد زيرا نياز دارد كه سرور افزونگي زيادي را در ساخت Update file‌ ها تحمل كند و در شرايطي كه سرعت افزايش پهناي باند از سرعت افزايش نرخ I/O‌ بيشتر است اين مدل موفقيت كمتري خواهد داشت. در شرايطي كه تعداد client زيادي داريم مدل OP‌ بهتر عمل مي كند و چنانچه پهناي باند خيلي بالايي داشته باشيم مدل OG بر خلاف انتظار به دليل اينكه كمترين فشار را براي ساختن update file‌ ها به سرور تحميل مي نمايد بهترين بازدهي را دارد.

 

6. منابع :

[1] A.Silberschatz, H.F.Korth, S. Sudarshan, Database System Concepts(Book)

[2] I. Terekhov,T.Camp, Time Efficient Deadlock Resolution Algorithms

[3] R.Ramakrishnan, J.Gehrke (2000) Database Management Systems(Book)

[4] S. Chen, Y. Ling, Stochastic Analysis of Distributed Deadlock Scheduling

[5] W. Yee, O. Freider, Scalable Synchronization of Intermittently Connected

Database Clients

 

اوراکل9i دارای انتخابی به نامVLM است که به اوراکل اجازه می‌دهد تا روی ماشین‌های 32 بیتی به واسطه استفاده از فایل سیستم اشتراکی (که بزرگ‌تر از چیزی هستند که سیستم‌های 32 بیتی می‌توانند آدرس‌دهی کنند) یک بانک اطلاعاتی و فضای حافظه ایجاد کند. با این حال اینگونه نتیجه‌گیری شده است که استفاده از این ویژگی می‌تواند باعث fragmentation در حافظه کرنل شود و این به‌خاطر نحوه معادل‌سازیmap) شدن) نواحی معین است. نتیجه این بود که در آنجا، روی تعداد پردازش‌هایی که می‌توانند پیوست شوند محدودیت وجود دارد. به وسیله همکاری باRedHat وSuSE ، اوراکل امکان پیشنهاد یک API به نام Remap File Pages که اکنون در RedHat Enterprise Linux 3 و در آینده در SuSE Linux Enterprise Server 9 وجود خواهد داشت را یافت Remap File Pages . ازfragmentation و نیز مورد استفاده قرارگرفتن مقدار زیادی از حافظه جلوگیری می‌کند. بنابراین سازمان‌ها می‌توانند اتصالات بیشتر و سریع‌تری داشته باشند و نیز پایداری‌شان افزایش یابد. Wim Coekaerts مدیر مهندسان شرکت اوراکل در زمینه لینوکس می‌گوید: “اگر چه این API به صورت یکpatch برای اوراکل9i در دسترس است، اما با اوراکل10g به درون خود برنامه آمده است.” او اضافه می‌کند:"بنابراین در حال حاضر، به صورت پیش‌فرض، وقتی شما پشتیبانی از VLM را فعال می‌کنید، این ویژگی به صورت اتوماتیک با استفاده از قابلیتRemap File Page راه‌اندازی خواهد شد". Direct I /O Support در گذشته، بانک اطلاعاتی اوراکل فقط در Oracle Cluster File System (OCFS) ازI /O های مستقیم پشتیبانی می‌کرد، ولی الان با اوراکل نسخه10g ، Network File System (NFS) نیزI /O مستقیم را در فایل سیستم پشتیبانی می‌کند. Coekaerts می‌گوید:"با اوراکل10g ، شما بدون نیاز داشتن به اعمالpatch ، پشتیبانی از I /O مستقیم در بانک اطلاعاتی خواهید داشت.” و اضافه می‌کند: " این می‌تواند کارآیی را واقعاً بهبود بخشد- به ویژه برایNFS که سرعت همه چیز را بالا می‌برد و واقعاً برای اجرایRAC مناسب است". بنابر گفته‌هایCoekaerts ، این ویژگی حتی روی یک سیستم تنها نیز واقعاً خوب است؛ چرا که شما مجبور نیستید در کاشه (cache) فایل سیستم OS خودend up caching data داشته باشید، اما در عوض می‌توانید از الگوریتم اوراکل برای آن استفاده کنید. نصب ساده و موثر Coekaerts می‌گوید:"در اوراکل10g ، نصب بانک اطلاعاتی فقط یکCD است؛ بنابراین شما می‌توانید در مدت 5 دقیقه یا کمی بیشتر، مراحل نصب را آغاز کنید که واقعاً زیبا و دیدنی است". برنامه سادهِ نصب‌کننده، برای نسخه‌های جدید لینوکس از جمله RedHat Enterprise Linux 3 و یا SuSE Service Pack 3 نیز به روز شده است، بنابراین مدیران سیستم هیچگونه نیازی به اعمال‌کردنpatch های ویژه سیستم عامل ندارند. ASM اوراکل10g دارای ویژگی جدیدی است که Automatic Storage Management نام دارد و به اوراکل اجازه می‌دهد تا بر روی کل فضاهای استفاده نشدهِ باقیمانده مدیریت داشته باشد. Coekaerts توضیح می‌دهد:"ما یک ماژول لینوکس اضافه کردیم که عملکرد جدید ASM را بالا می‌برد.” او ادامه می‌دهد:"ما یکDriver داریم که دیسک‌های در دسترس را اسکن می‌کند و آنها را برای اوراکل به صورت اتوماتیک آماده ساخته و مدیریت آنها را به آسانی انجام می‌دهد. اینDriver بر رویOTN در دسترس است، بنابراین مشتریانی که از اوراکل10g استفاده می‌کنند، می‌توانند از آن ماژولِ کرنل استفاده کرده و فقط دیسک‌هایی که والیوم های ‌ASM هستند را به سیستم متصل کنند. سپس وقتی اوراکل شروع به کار کرد، آنDriver فقط خبرش را به ماژول کرنل می‌دهد و همه دیسک‌ها را تعریف کرده و یکdevice ویژه می‌سازد و آن را برای انجام I /O به اوراکل اختصاص می‌دهد که خیلی شبیه است به I /O های آسنکرون (غیر همزمان) و به ما این امکان را می‌دهد که بعضی از کاوش‌های اتوماتیک دیسک‌ها را انجام دهیم و مسیرI /O را بهینه کنیم. Oracle Cluster File System اگر چه OCFS نسخه 1 همانطوری که با اوراکل9i کار می‌کرد، به خوبی با اوراکل10g نیز کار می‌کند، ولیOCFS نسخه 2 می‌تواند هر دوی Oracle Database وOracle Code را خودش بر روی لینوکس مدیریت کند. به عنوان مثال، یکAdmin ، روی چهار سیستم کهcluster شده‌اند (از معماریclustering استفاده می‌کنند) فقط باید یک نصب Oracle DB 10g انجام دهد و برنامه نصب‌کننده (installer) ، فایل سیستمcluster را متوجه خواهد شد و برنامه را در محل مناسبش بارگذاری خواهدکرد و خیلی راحت آن را گسترش داده و به‌روز رسانی می‌کند. Coekaertsتوضیح می‌دهد:"تصور کنید که شما هشت سیستم cluster شده دارید. قبل از OCFS نسخه 2، شما باید اوراکل را هشت مرتبه نصب کرده و هشت بار نیز patch ها را اعمال می‌کردید و حالا به جای آن، دارای یک home مشترک هستیم و شما می‌توانید تنها یکبار از روی یک فایل سیستم اوراکل را نصب وpatch های مورد نیاز را اعمال کنید- بنابراین OCFS مدیریت را تا حد بسیار زیادی ساده می‌سازد”.

دو اصل در هسته Grid Computing آنرا به طور منحصربفردی از دیگر روشهای Computing ازقبیل Mainframe ، Client/Server یا چند لایه ای (Multi-tier) متمایز می سازد : مجازی سازی و تأمین.

 

    * با مجازی سازی ، منابع خاص (مانند رایانه ها ، دیسکها ، اجراء نرم افزاری و منابع اطلاعاتی) به عنوان منابع درهم آمیخته و مشترک جهت دسترسی مصرف کنندگان (از قبیل افراد و برنامه های نرم افزاری) بطور انتزاعی در نظر گرفته می شود.مجازی سازی یعنی شکستن اتصالاتی که بسختی بین ارائه کننده و مصرف کننده (مشتری) منابع برقرار شده است و مهیا ساختن منابع برای سرویس دهی به نیازهای خاص ، بدون اینکه مشتری نگران چگونگی انجام آن باشد.
    * تأمین یعنی اینکه ، وقتی مشتری از طریق لایه مجازی سازی نیاز به منبع خاصی دارد ، در پشت پرده ، آن منبع جهت انجام در خواست ،شناسایی شده و به مشتری تخصیص داده شود.تأمین بعنوان بخشی از Grid Computing به این معنی است که سیستم تعیین می کند چگونه نیاز مشتری را برآورده سازد در حالیکه عملیات در کل ، به صورت بهینه انجام شود.
 

 

برای نمونه می توان از Oracle 10g به عنوان تنها DBMS پیشتاز در این زمینه یاد کرد که در مقاله بعدی این جنبه ار Oracle 10g را بررسی خواهیم نمود.

 

سیستم های Grid   نوعی از سیستم های توزیع شده یا موازی هستند که اشتراک ، انتخاب و جمع آوری منابع را در فواصل جغرافیایی فراهم می اورد. بر اساس این تعریف ملاحظه میشود که امکان اجام کارها بصورت موازی وجود دارد.شاید مهمترین دلایل استفاده از سیستم های موازی  را بتوان در 4 مورد زیر خلاصه نمود:

1-  Application ها بطور حریضانه به دنبال منابع هستند .

2-       کامپیوترهای موجود معماری تک پردازنده و ترتیبی دارند .

3-       پیشرفت تکنولوژی شبکه های کامپیوتری .

4-       محدودیت فیزیکی سخت افزارها در افزایش سرعت .

با توجه به موارد فوق درمی یابیم موازی سازی یک امر ضروری برای انجام کارهای بزرگ و سنگین می باشد.با انجام موازی سازی  قابلیتهایی نظیر ،توازن سازی ،همپام سازی ، در دسترس بودن ، انعطاف پذیری و کاهش هزینه  امکان پذیر میشود.اما برای نوشتن برنامه های موازی به محیطی نیاز است که این کار انجام گیرد .در این مورد کلا" دو دیدگاه وجود دارد .

الف – Implicit parallelism

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

ب – Explicit parallelism

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

1-       تقسیم بندی فرایندها 

2-       نگاشت روی پردازنده ها

3-       ساختارهای ارتباطی

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

1-  Share memory

در این حالت معماری مابصورت  حافظه مشترک بوده و دستورات بصورت Read  و Write می باشند.برخی از این ابزار  عبارتند از : DSM ، Java ، Openmp.

2-       Message passing

در این حالت در محیط شبکه هر سیستم حافطه و پردازنده خودش را دارد و از دستورات Send و Receive  استفاده میشود. برخی از این ابزار  عبارتند از : MPI و PVM

تذکر: نسخه تحت ویندوز MPICH می باشد که شامل توابع کتابخانه ای برای نوشتن برنامه های موازی است .در پروژه نیز ما از این ابزار استفاده کرده ایم .

3-       Hybrid

به ترکیبی از دو مدل فوق اشاره دارد .برخی از این ابزار  عبارتند از MPI,Openmp.

4-       Object & Service Oriented

این ابزار در سطح کاربر بوده و بالاتر از Middleware قرار می گیردولی کارایی کم میشود.برخی از این ابزار  عبارتند از Dcom و Corba .

برای انجام برنامه نویسی موازی می بایست بخشاهای زیر را در کد ایجاد کرد و رعایت نمود:

1-  Partitiong  که برای بخش بخش کردن Task بکار می رود.

2- Communication  برای برقرای ارتباط بین بخشهای جدا شده در فاز اول می بایست رعایت شود.

3- Agglomeration که نحوه اتصال دو بخش فوق را بعد از برقرای ارتباط و بخش بندی را مشخص می کند.

4-      Mapping/Scheduling که نسبت دادن کارها به پردازندها را انجام میهد بطوریکه زمان انجام کار حداقل شده و راندامان بالایی داشته باشیم .

برنامه نویسی موازی یک Task  پیچیده است زیرا برنامه هایی را که مینویسیم شامل بخشهای موازی است .ابزارهای برنامه نویسی کمک می کنند تا حدی این پیچیده گی کاهش یابد.برای نوشتن برنامه ای موازی به چنین محیطهایی نیاز داریم .مهمترین نکته ای که از دیدگاه کاربر مهم است آنستکه برخی از چیزها را Transparence کنیم و همچنین بتوانداز مفاهیم قبلی برنامه نویسی استفاده نماید.

در این روش برنامه به یکسری زیر برنامه تقسیم می شود و هر بخش از آن بین گره های شبکه اجرای می گردد.هر زیر برنامه بصورت ترتیبی نوشته شده است ولی چون همه پردازنده ها موازی برنامه را اجرا می کنند در نتیجه برنامه موازی اجرای میشود.متغیرهایی که روی هر پردازنده اجرا میشوند کاملا"Private هستند و برای ارتباط فقط از مبداء به مقصد پیام ارسال میشود.

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

MPICH  ابزاری است که توابع استاندارد  کتابخانه ای MPI را برای اجرا در انواع سیستم ها فراهم می آورد. این ابزار در سیستم های عامل NT4,window 2000,windows xp  و Windows server قابل استفاده است و هر جا که ارتباطات بصورت TCP/IP وجود دارد قابل بکارگیری است.همچنین برای کمپایل برنامه های نوشته شده از محیط    6.x++ VC بهره می بریم .

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

همانطور که ذکر شده این برنامه براساس Message passing کار می کند .بطور کلی به دو صورت گروهی (Collective) و نقطه به نقطه (Point to point) انتقال پیام انجام میشود.در حالت اول یک فرستنده به چندین گیرنده پیام را ارسال می کند.و در حالت نقطه به نقطه یک فرستنده و یک گیرنده داریم که پیام را بیکدیگر ارسال می نمایند.این روش خود بصورتهای زیر انجام میشود:

1-     سنکرون : در این حالت دقیقا وقتی که گیرنده می خواهد داده را بردارد، فرستنده متوجه میشود.به عبارتی وقتی کار ارسال  پیام تمام شد فرستنده متوجه میشود و ادامه کار منوط به این است گیرنده داده را بردارد. برای مثال ماشین فاکس چنین خصوصیتی دارد.

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

3-       عملیات بلوک کردن :وقتی انجام میشود و نتیجه را باز می گرداند که عملیات تکمیل شده باشد.

4-     عملیات بدون بلوک کردن : در این حالت عملیات  شروع شده و معلوم نیست چه زمانی خاتمه می یابد.به عبارتی برای اطمینان از انجام عملیات باید تست انجام شود.برای مثال سمافور در سیستم عامل اینچنین است .

با توجه به مطالب فوق می توان دریافت که ارسال سنکرون Blocking و ارسال آسنکرون Non blocking است .

در مقابل ارتباطات گروهی قادر هستند که عملیات زیر را انجام دهند :

1-       میتوان از آنها بعنوان ارتباطات نقطه به نقطه  استفاده نمود.

2-       امکان انجام پردازشهای سنکرون ( Barrier) را دارد .

3-       قابلیت انجام ارتباطات یک به چند ( Broadcast ) را دارد.

4-       قابلیت انجام عملیات Reduction بدین معنی که ترکیب داده از پردازنده های متعدد  برای تولید نتیجه نهایی و بر آیند.

 

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

MPI_Xxxxx(parameter,…);

 

عمده توابعی که در برنامه استفاده شده است تقریبا" مشابه برنامه محاسبه عدد P می باشد.با این تفاوت که در این جا عملیات ضرب ماتریس انجام میشود. به منظور تمایز پروسس های مختلف اولین روتین که بکار می رود  MPI_Initاست .این روتین یک گروه یا Communicator ایجاد می کند و به تمام پردازنده هایی که در یک گروه هستند شماره ای اختصاص می دهد.به این شماره اصطلاحا" Rankگفته میشود.بصورت پیش فرض Masterشماره Rank صفر را می گیرد و بقیه پردازندهها به ترتیب شماره گذاری میشوند.در واقع Rank به پروسه IDاست .

الگوریتم کار  بدین صورت است که بعد از تعریف متعیرها ی مورد نیاز ،زمان شروع برنامه را ثبت می کنیم سپس برای نمایش شماره و نام ماشین پردازش گر از فرمان Fprintf استفاده کرده ایم که در واقع MyID و processor name را بر می گرداند.سپس تعداد سطر و ستون ماتریس مورد نظر را تعریف می کنیم .این مقادیر ثابت می باشند و انجام تغییرات آن منوط به دستکاری در سورس برنامه است.در واقع دو ماتریس 1000 در  1000 در  این برنامه  در  هم ضرب شده اند .که بصورت ریاضی بصورت 1000*1000*1000 تعریف میشود. در ادامه بعد از تخصیص حافظه مورد نیاز ماتریسها را بصورت تصادفی مقدار دهی می کنیم و در بخش آخر عملیات ضرب ماتریسها انجام میشود.برای این منظور ابتدا توسط تابع  MPI_Bcast اندازه  هر یک  از ماتریسها  برای بقیه گره ها معرفی می کنیم . در واقع در شرط اول فقط اطلاعات ماتریس ها برای ID صفر و رد شرط دوم اطلاعات مورد نیاز سایر گره ها مشخص میشود.در بخش عمل ضرب ماتریسها بدین صورت انجام میشود هر پروسس یک سطر از ماتریس را در کل ماتریس بعدضرب می کند .در این جا نتایج خروجی توسط تابع Printf چاپ نشده است و تنها زمان محاسبه وپردازش  چاپ گردیده است .

      سورس برنامه به پیوست تقدیم شده است ( برنامه و توضیحات روی CD نیز وجود دارد). برای       درک بیشتر برنامه توابعی که در  بکار رفته است را در ادامه به تفکیک شرح می دهیم :

1- MPI_Comm_Rank  : این تابع شماره Rank را بر می گرداند .برای مثال روی Master شماره صفر را میدهد .

2-       MPI_Comm_size : این تابع سایز گروه در Communicator را بر می گرداند به عبارتی تعداد پروسه هایی که در گروه وجود دارند را می دهد.

3-     MPI_Send : این تابع که به ارسال استاندارد مشهور است و مهم آنستکه که عملیات ارسال تکمیل شده باشد.به عبارتی زمانی کامل میشود که پیام ارسال شده باشد و از نوع Blocking  است .

4-       MPI_Recv : در تابع دریافت استاندارد  بااجرای Send ،طرف گیرنده ،بهنگام اجرای  Receive یک پیام به فرستنده ارسال می کند .

5-       MPI_Wtime : این تابع Wall clock رابر می گرداند .هر وقت بخواهیم زمان را اندازه گیری کنیم این تابع را بعد از Send  و بعد از Receive  صدا می زنیم .

6-       MPI_Bcast :از این تابع برای ارسال یک به چند استفاده می کنیم .به عبارتی از گره ریشه پیام را به یک سری از زیر گره های  ارسال می کنیم .

7-       MPI_Reduce : این تابع وظیفه ارسال نتایج حاصل از پردازش زیرگره ها را به گره ریشه را دارد.

8-       MPI_Barrier :از این تابع برای سنکرون کردن گره ها استفاده میشود. به عبارتی منتظر می ماند  تا الباقی گره ها نتایج را ارسال نمایند .

این برنامه در یک محیط شبکه Workgroup با 5 سیستم اجرا شده است . مشخصات این سیستم ها طبق جدول زیر است .

 

همانطور که از جدول فوق پیداست  این 5 سیستم برای اجرای ماتریس 1000*1000 در نظر گرفته شده اند.همانطور که از نتایج خروجی و نمودار پیداست .با اجرای مرحله به مرحله برنامه زمان اجرای پردازش ثبت شده است .برای اینکه بتوانیم برنامه ها را بصورت موازی اجرا نمامیم می بایست در ابتدا MPICHرا در تمامی ماشینها نصب کنیم .بعد از نصب برای اینکه تمامی سیستم ها با هم کار کنند اولا یک کاربر مشترک با رمز عبور یکسان باید تعریف گردد و ثانیا در صورتیکه Firewall روی کارت شبکه سیستم فعال است باید غیر فعال گردد.در مرحله بعد با کاربر و رمزی که برای آن تعریف کرده ایم MPI registerرا اجرا می کنیم تا رجیستر گردد.سپس فایل کمپایل شده (فایل اجرایی برنامه ) در تمامی کامپیوترهای شبکه در یک پوشه که نام آن در تمامی سیستم ها یکسان است و به اشتراک گذاشته شده کپی می کنیم سپس از طریق MPIch Configure tool. لیست ماشینهای شبکه را اضافه می کنیم و برنامه را در ماشین Master اجرا می کینم در اولین مرحله با 1 ماشین بیشترین زمان انجام محاسبه ثبت شده است .با افزایش تعداد پردازنده ها تا 5 عدد کاملا" زمان پردازش بهینه شده و در کمترین مقدار خود قرار گرفته است .اما با زیاد کردن تعداد ماشین ها چون هر ماشین ممکن بوده است بیشتر از یک عمل را انجام دهد به علت وجود پروسه های مختلف برای تقسیم کار و همچنین به علت وجود سربار در ارتباطات زمان انجام پردازش سیر صعودی به خود میگیرد.همچنین نمودار نشان می دهد که همیشه با افزایش تعداد پردازنده ها زمان  پردازش افزایش نمی یابد و به علت وجود سربار سیستم بصورت None dedicate عمل خواهد کرد.

به دلیل قولی که به بچه ها داده بودم قسمت اول نصب را برایتان می نویسم و

 

قسمت بعد را بعد از امتحانات مینویسم 

 

 لطفا نظر دهید چه مطالبی در این وبلاگ قرار دهم

 

برای نصب Globusموارد زیر را باید در نظر بگیریم

نسبت به نرم افزاری که از Globus دانلود کردیم باید linux مربوط به آن را نصب کرده

حال برای پیاده سازی باید ورژن جاوا در linux و gcc آن را چک کنیم که اگر آن ورژن ها را ساپورت نمی کرد آنها را نصب کنیم ورژن جاوا باید 1.6 باشد

 

برای چک کردن ورژن جاوا دستور زیر را در ترمینال تایپ می کنیم

 

Java -version

و برای update  ورژن جاوا مراحل زیر را انجام می دهیم

 

با این دستور java 1.6   از zip خارج می شود    

                                   

  (اسم فایل (java    tar xzvf

 

نکته: می توان برای سریعتر نوشتن اسم فایل حرف اول را نوشته و بعد Tabرا بزنید با این کار سریع بقیه اسم فایل را به صورت اتوماتیک می آورد

 

بعد محتویات java 1.6  را در شاخه HOME\USER  که رفته ایم OverWrite      می کنیم

به این ترتیب ورژن جاوا update  می شود

 

بعد ورژن gcc   را چک میکنیم با دستور زیر

 

gcc –v

باید ورژن gcc   4.1 نباشد چون باگ دارد می توان از ورژنهای

  3.2. 3.2.1 و  2.95.x استفاده کرد

و gccرا نمی توان  updateکردو نسخه ایی از linuxکه این ورژن را دارد نصب می کنیم

 

نرم افزار Tomcatرا هم باید نصب کرد ولی در زمان کامپایل به آن نیاز نداریم و در زمان Runtime  به آن نیاز داریم

اگراز لینوکس suse  استفاده میکنید به هیچ نرم افزار جانبی احتیاجی نداریم

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

root# useradd globus

 

و از شاخه system \group and user.. می توان user