پاورپوینت ترمیم در سیستمهای توزیع شده

بخشی از پاورپوینت

اسلاید 1 :

ترمیم در سیستمهای توزیع شده

اسلاید 2 :

ترمیم در سیستمهای توزیع شده

هدف: بازگرداندن سیستم به حالت معمولی و نرمال خود.
تغییرات داده شده بوسیله پردازه خطا در undo شوند.
منابع اختصاص داده شده پس گرفته شوند.
ایده آل: اعمال پردازه مواجه شده با خطا از همان نقطه خطا ادامه یابد (؟).  عدم اجرای بخشهای انجام شده از پردازه فوق.

همروندی و ترمیم! اثر یک پردازه روی پردازه های دیگر.

اسلاید 3 :

ترمیم به جلو – ترمیم به عقب

وظیفه Failure Recovery برگرداندن حالت سیستم (حالت مغلوط) به یک حالت بدون خطاست.
اگر طبیعت خطای ایجاد شده دقیقاً ارزیابی شود می توان اشکال را مرتفع کرد و پردازه را قادر به حرکت به جلو کرد: Forward Error Recovery
اگر نمیتوان طبیعت خطای ایجاد شده را پیش بینی کرد، سیستم کار خود را از یک حالت بدون خطا ادامه می دهد: Backward Error Recovery
راحتتر
Performance penalty
عدم وجود تضمین برای عدم تکرار خطا در اجرای مجدد

اسلاید 4 :

ترمیم به عقب (B.E.R)

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

مدل سیستم:

در اثر بروز خطا محتوای خود
را از دست نمی دهد.
برای ذخیره Log و نقاط ترمیم
CPU
حافظه اصلی
Stable Storage
Secondary Storage

اسلاید 5 :

پیاده سازی BER

دو روش:
روش مبتنی بر اعمال (Operation Based) :
اعمال در سیستم ثبت می شوند طوری که با undo کردن اعمال می توان به حالت قبلی دست یافت. مثال: اعمال یک تراکنش

تغییر در جا (UPDATE-IN-PLACE)
نام شیئ
بروزآوری در جا و ثبت عمل در Log :: رکورد Log حالت قدیمی شیئ
حالت جدید شیئ

اسلاید 6 :

پیاده سازی BER ادامه
ترمیمپذیری تغییرات را می توان با اعمال زیر پیاده سازی کرد:
do: انجام یک عمل و ثبت در Log
Undo: خنثی کردن عمل انجام شده بوسیله do
Redo: اجرای مجدد عمل انجام شده بوسیله do
برق رفتگی بین انجام یک عمل و نوشتن log؟  WAL

در WAL:
بروزآوری وقتی انجام می شود که undo log مربوط به آن نوشته شده باشد.
قبل از نهایی شدن یک بروزآوری، مطمئن شویم که undo log, redo log ثبت شده باشند.

اسلاید 7 :

روش مبتنی بر حالت

2- روش مبتنی بر حالت
ایجاد نقطه ترمیم در هر مقطع با ثبت کل حالت سیستم ( checkpointing )
ارجاع به checkpoint پس از رخداد خطا: : roll – back

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

Shadow paging حالت خاصی از ترمیم مبتنی بر حالت

اسلاید 8 :

ترمیم در سیستمهای همروند

انجام یک کار مستلزم تبادل پیغام 

بازگشت یک پردازه به نقطه ترمیم مستلزم بازگشت دیگر پردازه ها هم هست (در پردازه های متأثر از پردازه خطادار - پس از نقطه ترمیم)

اسلاید 9 :

پیغام یتیم – اثر دامینو (Domino)
خطای X  بازگشت به X3
خطای Y  بازگشت به Y2 (!)



m ارسال نشده است ولی دریافت شده است! (پیغام یتیم) لزوم ارجاع X به X2 و

خطای Z  بازگشت به Z2  لزوم بازگشت X و Y به X1 و Y1 و متعاقب آن

بازگشت Z به Z1 :: اثر دامینو:: تأثیر بازگشت یک پردازه روی بازگشت دیگر پردازهها

اسلاید 10 :

Lost msg
ارجاع X و Y به X1 و Y1
m را پیغام گمشده نامیم.

اسلاید 11 :

LiveLock
وقتی رخ می دهد که رخداد دو خطا باعث تعدادی نامتناهی ارجاع داشته باشیم و لذا مانع پیشرفت کار سیستم.

n1 در راه است. Y به Y1و بواسطه وجود پیغام یتیم m1، X بهX1 باز می گردد.  m1 و n1 دوباره ارسال می شوند. معهذا نسخه در راه به Y میرسد. با رسیدن n1، m2 ارسال شده است. Y نیز n2 را ارسال و m2را دریافت می کند ولی در حالت سیستم اثری از ارسال n1وجود ندارد.  لزوم ارجاع به عقب در Y و.
خطا
Roll-back

اسلاید 12 :

مجموعهای سازگار از نقاط مقابله
نقطه مقابله محلی

مجموعه ای از نقاط مقابله محلی (از هر سایت یکی) را نقطه مقابله سراسری می ناميم.

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

اسلاید 13 :

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

اسلاید 14 :

الگوریتم Toueg ,Koo برای ایجاد همگام نقاط مقابله
فرضیات
کانالها FIFO
خطای ارتباطی منجر به افراز شبکه نمی شود

دو نوع نقطه مقابله:

موقت (آزمایشی): یک نقطه مقابله موقت است که ممکن است به دائمی تبدیل شود را روی حافظه پایدار ایجاد میکند.

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

اسلاید 15 :

الگوریتم Toueg ,Koo برای ایجاد همگام نقاط مقابله - ادامه

فاز اول الگوریتم:
Pi یک C آزمایشی میگیرد و از دیگر پردازهها هم درخواست C آزمایشی میکند. هر پردازة دیگر موفقیت خود را در این کار به Pi اعلام میکند. اگر همه موفق بودند Pi اعلام میکند که دائمی تلقی شود وگرنه دور ریخته شود.

فاز دوم الگوریتم:
اعلام تصمیم Pi در پایان مرحله اول به همه  یا همه C دائمی میگیرند یا نه.
فرض میکنیم که در فاصله بین C آزمایشی و دریافت تصمیم آغازگر پیغامی ارسال نمیشود.  حالت ناسازگار بوجود نخواهد آمد.

اسلاید 16 :

بهینه سازی در الگوریتم Koo، .
اگر لازم نیست که پردازهای C جدیدی بگیرد!؟

اگر X پس از دریافت m تصمیم به C بگیرد منجر به {X2, Y2, Z2} خواهد شد در حالی که X2, Y2, Z1}} هم سازگار هستند

. اگر پیغامی ارسال نشده است میتوان C آزمایشی را در یک سایت انجام نداد.
آزمایشی

اسلاید 17 :

روش اعمال

پیغامهای کنترلی موردنظر نیستند.
هر پیغام یک برچسب دارد. m.l که در هر پردازه حالت افزایشی دارد.
فرض کوچکترین و T بزرگترین برچسب باشد.
به ازاء هر Y ,X ، فرض کنیم m آخرین پیغام دریافت شده پس از آخرین C باشد.

last-label-rcvdX[Y] =

first-label-sentX[Y] =

اسلاید 18 :

روش اعمال ادامه

هرگاه X از Y درخواست میکند که یک C آزمایشی بگیرد، همراه درخواستش last-label-rcvdX[Y] را هم میفرستد. Y تنها وقتی C می گیرد که
last-label-rcvdX[Y] first-label-sentY[X] >

یعنی X رسید تعدادی پیغام را ثبت کرده است که پس از آخرین C در Y ارسال شدهاند.
Y هم باید واقعه ارسال آنها را ثبت کند.

Chkpt-cohortX = {Y | last-label-rcvdX[Y] > }
همه سایتهایی که باید درخواست C به آنها ارسال شود.