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

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

اسلاید 1: ترمیم در سیستمهای توزیع شدهفصل 12 از کتاب singhalAdvanced Operating SystemsSharif University of Technology

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

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

اسلاید 4: ترمیم به عقب (B.E.R)نقاطی که می توان به آنها ارجاع و اعتماد کرد را نقاط ترمیم (Recovery Points) گویند.بازیابی نقاط ترمیم یعنی جایگزینی حالت فعلی پردازه ای با حالت آن پردازه در نقطه ترمیم.مدل سیستم: در اثر بروز خطا محتوای خود را از دست نمی دهد.برای ذخیره Log و نقاط ترمیمCPUحافظه اصلیStable StorageSecondary Storage

اسلاید 5: پیاده سازی BERدو روش:روش مبتنی بر اعمال (Operation Based) : اعمال در سیستم ثبت می شوند طوری که با undo کردن اعمال می توان به حالت قبلی دست یافت. مثال: اعمال یک تراکنشتغییر در جا (UPDATE-IN-PLACE) نام شیئ بروزآوری در جا و ثبت عمل در Log :: رکورد Log حالت قدیمی شیئحالت جدید شیئ

اسلاید 6: پیاده سازی BER ادامهترمیم‌پذیری تغییرات را می توان با اعمال زیر پیاده سازی کرد:do: انجام یک عمل و ثبت در LogUndo: خنثی کردن عمل انجام شده بوسیله doRedo: اجرای مجدد عمل انجام شده بوسیله doبرق رفتگی بین انجام یک عمل و نوشتن log؟  WALدر WAL: بروزآوری وقتی انجام می شود که undo log مربوط به آن نوشته شده باشد.قبل از نهایی شدن یک بروزآوری، مطمئن شویم که undo log, redo log ثبت شده باشند.

اسلاید 7: روش مبتنی بر حالت2- روش مبتنی بر حالتایجاد نقطه ترمیم در هر مقطع با ثبت کل حالت سیستم (checkpointing)ارجاع به checkpoint پس از رخداد خطا: : rollbackتلاش در rollback به آخرین حالت ممکن و سازگارمعمولاً در طی اجرای یک پردازه، checkpointهای زیادی گرفته می شود. Shadow paging حالت خاصی از ترمیم مبتنی بر حالت

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

اسلاید 9: پیغام یتیم – اثر دامینو (Domino)خطای X  بازگشت به X3 خطای Y  بازگشت به Y2 (!)m ارسال نشده است ولی دریافت شده است! (پیغام یتیم) لزوم ارجاع X به X2 و خطای Z  بازگشت به Z2  لزوم بازگشت X و Y به X1 و Y1 و متعاقب آنبازگشت Z به Z1 :: اثر دامینو:: تأثیر بازگشت یک پردازه روی بازگشت دیگر پردازه‌هاXYZX1X2X3Y1Y2Z1Z2m

اسلاید 10: Lost msgارجاع X و Y به X1 و Y1m را پیغام گم‌شده نامیم.XYX1Y1

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

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

اسلاید 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 آزمایشی را در یک سایت انجام نداد.XYZX1X2Y1Y2Z1Z2mآزمایشی

اسلاید 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 به آنها ارسال شود.

اسلاید 19: The algorithmInitial state at all processes p:For all processes q do first-label-sentp[q] := ;OK-to-take-ckptp = At initiator process Pi:For all processes p  ckpt-cohort pi doSend Take-a-tentative-ckpt(Pi, last-label-rcvd pi[p]) message;If all processes replied “yes” thenfor all processes p  ckpt-cohort pi doSend Make-tentative-ckpt-permanent; elseFor all processes p  ckpt-cohort pi doSend Undo-tentative-ckpt.

اسلاید 20: The algorithm ContinuedAt all processes p:Upon receiving Take-a-tentative-ckpt(q, last-label-rcvd q[p]) message from q doBeginIf OK-to-take-ckptp = “yes” AND last-label-rcvd q[p]  first-label-sentp[q] >  thenbegintake a tentative checkpoint;for all processes r  ckpt-cohort p doSend Take-a-tentative-ckpt(P,last-label-rcvd p[r]) message;If all processes r  ckpt-cohort p replied “yes” thenOK-to-take-ckptp := “yes”ElseOK-to-take-ckptp = “no”End;Send (p, OK-to-take-ckptp) to q;End;

اسلاید 21: The algorithm ContinuedAt all processes p:Upon receiving Make-tentative-ckpt-permanent message doBeginMake tentative checkpoint permanent;For all processes r  ckpt-cohort p doSend Make-tentative-ckpt-permanent message;End;Upon receiving Undo-tentative-ckpt-permanent message doBeginUndo tentative checkpoint;For all processes r  ckpt-cohort p doSend Undo-tentative-ckpt-permanent message;End;

اسلاید 22: Rollback-Recoveryفرض: تنها یک پردازه الگوریتم را آغاز می کند و فراخوانی همروند الگوریتم را نداریم.فاز اول: آغازگر (Pi) کنترل میکند که آیا همه پردازه ها علاقمند به بازآغازی از آخرین C خود هستند یا نه؟ پردازه ای که در C یا R آغاز شده بوسیله دیگری درگیر است پاسخ no می دهد. در صورت مثبت بودن پاسخ همه، بازآغازی اعلام می‌شود.فاز دوم: Pi تصمیمش را به همه می فرستد و برآن اساس عمل می شود. مادام که پردازه ای منتظر پاسخ است پیغامی در رابطه با محاسباتش نمی فرستد.

اسلاید 23: Rollback-Recovery Continuedباز هم بهینه سازی در مواردی که لازم نیست پردازه ای با آغازی را انجام دهد:با رخداد خطا در X ، Z نیازی به بازآغازی ندارد.XYZX1X2Y1Y2Z2Z1

اسلاید 24: Rollback-Recovery Continuedتعریف:Last-Label-SentX[Y] = وقتی x از y می خواهد که به آخرین C دائمی اش برگردد Last-Label-SentX[Y] را هم می فرستد.Y به شرطی به آخرین C خود بر می گردد که Last-Label-RcvdY[X] > Last-Label-SentX[Y] یعنی X متمایل به ارجاع به حالتی است که ارسال یک یا چند پیغام ازX به y، undo شود.roll-cohortX = {Y|X can send msgs to Y}Largest Value

اسلاید 25: The algorithmInitial state at process P: Resume-execution := true;For all processes q, doLast-label-rcvdp[q] := T;Willing-to-rollp = yes / no …. At initiator process Pi:For all processes p  roll-cohortpi doSend Prepare-to-rollback(Pi, last-label-sentPi[p]) message;If all processes p  roll-cohortpi doSend Roll-back message;ElseFor all processes proll-cohortpi doSend Donot-roll-back message;

اسلاید 26: The algorithm ContinuedAt all processes p: Upon receiving Prepare-to-rollback(q, last-label-sentq[p])Message from q doBeginIf willing-to-rollp AND last-label-rcvdp[q] > last-label-sentq[p] AND (resume-executionp)ThenBeginResume-executionp := false;For all processes r  roll-cohortp doSend Prepare-to-rollback(p, last-label-sentp[r]) message;If all processes r  roll-cohortp replied “yes” thenwilling-to-rollp := “yes”elsewilling-to-rollp := “no”end;Send (p, willing-to-rollp) message tp q;End;

اسلاید 27: The algorithm ContinuedUpon receiving Roll-back message AND if resume-executionp = false doBeginRestart from p’s permanent checkpoint;For all processes r  roll-cohortp doSend Roll-back message;End;Upon receiving Donot-roll-back message doBeginResume execution;For all processes r  roll-cohortp doSend Roll-back message;End; 

اسلاید 28: Async Checkpointing & Recoveryمعایب نقطه مقابله سازی همگام:پیغامهای اضافی که در هر C مبادله می شوند.تأخیرات همگانی که در حین C پیغام محاسباتی مبادله نمی شود.سربار زیاد درخصوص سیستمهایی که خطای نادر بین هر دو C متوالی دارند.در روش ناهمگام، هر پردازه (پردازنده) C خود را مستقل از دیگران می گیرد. تضمینی بر سازگاری مجموعه ای از Cهای محلی وجود ندارد. الگوریتم ترمیم باید اخیرترین مجموعه سازگار از Cها را قبل از آغاز ترمیم پیدا کند. برای حداقل کردن میزان محاسبات undo شده در حین Rollback ، همه پیغامهای وارده Log می شوند تا احتمالا redo شوند.

اسلاید 29:   الگوریتم Juang & Venkatesanدر checkpointing ، فرض می کنیم که دو نوع Log داریم :فرار: دسترسی سریع ولی فرّارپایدار: هراز چندگاه یکبار ذخیره روی حافظه پایدارهر پردازه پس از هر واقعه، سه تایی زیر را در حافظه فرّار ثبت می کند:{s, m, msg-sent}توجه: فرض بر event - driver سیستم است که با انتظار برای پیغام و رسیدن پیغام fire می‌شود.این همان نقطه مقابله محلی برای رخداد واقعه است. حالت پردازه قبل از رخداد واقعه پیغام (شامل شناسه فرستنده) که رسیدنش باعث رخداد واقعه شده استمجموعه ای از پیغامها که در طی واقعه توسط پردازنده ارسال شده است

اسلاید 30: الگوریتم Juang & Venkatesan : ساختمان داده‌های لازم و Notations RCVDij(chpti) معرف تعداد پیغامهای رسیده از j به i است. باتوجه به اطلاعاتی که در chpti ذخیره شده است.SENT ij(chpti) معرف تعداد پیغامهای ارسال شده از i به j باتوجه به chpti است.ایده اصلی ترمیم باید بتواند مجموعه ای سازگار از نقاط مقابله محلی پیدا کند هر پردازنده پیغامهای ارسالی و دریافتی خود به دیگران را می شمارد.وقتی پردازنده ای rollback می کند، باید همه کنترل کنند که آیا پیغامهای دریافت شده‌اشان یتیم شده‌اند یا نه؟ (مقایسه پیغامهای دریافت کرده و ارسال شده). اگر وجود داشت، ارجاع به مرحلة قبلی و ......

اسلاید 31: الگوریتم Juang & Venkatesan ادامهاگر Y به eY1 عقبگرد کند، Y یک پیغام به X فرستاده است ولی X دوتا پیغام از Y دریافت کرده است. X باید به حالت قبل از eX2 عقبگرد کند تا با Y سازگار باشد. Z هم باید عقبگرد کند.ex0XYZex1ex2ex3ey0ey1ey2ey3ez0ez1ez2ez3

اسلاید 32: الگوریتم:فرض: هر پردازنده به محض بازآغازی، پیغامی منتشر می کند که fail کرده بود. الگوریتم بلافاصله پس از ترمیم از خطا و بازآغازی شروع می شود و یا با اطلاع از خطای پردازنده دیگر.به خاطر پخش پیغام به همگان، الگوریتم در همه پردازنده‌ها آغاز می شود.در پردازنده i :اگر ترمیم یافته از خطاست: آخرین واقعه Log شده در حافظه پایدار ckpti =در غیر اینصورتآخرین واقعه ای که رخ داده است ckpti = (اعم از روی حافظه فرار یا پایدار)

اسلاید 33: الگوریتم ادامهfor k:=1 to N do (*N is he # of processors*)beginfor each neighboring process j doSend ROLLBACK(I, SENTij(ckpti)) msg;wait for ROLLBACK msg from every neighbor(چون همه در حال اجرای الگوریتم هستند پس به همسایه ها پیغام را می فرستند).for every ROLLBACK(j,c) received from j,i does the following:if RCVDij(ckpti) > c then /* وجود پیغام یتیم*/beginfind the latest event e such that RCVDij(e)cj;ckpti := e;end;end;

اسلاید 34: الگوریتم ادامهمثال: در نظر بگیرید:پس از رخداد خطا، Y بهY1 برمی‌گردد. ey2نیز آخرین واقعة ثبت شده در log است. چون برگشت از خطا را پخش می کند X و Z هم الگوریتم را شروع می کنند.XYZey0ey1ey2ey3ez0ez1ez2ez3ex0ex1ex2ex3X1Y1Z1failure

اسلاید 35: مثال ادامه در دور اولدر ابتداX ckptX  eX3 RollBack(X,2) to Y, RollBack(X,0) to ZY ckptY  eY2RollBack(Y,2) to X, RollBack(Y,1) to ZZ ckptZ  eZ2RollBack(Z,0) to X, RollBack(Z,1) to Y در X، چون  RCVDXY(ckptX) = 3> 2 ckptX  eX2 و لذا داریم:RCVD XY(eX2) = 2  2در Z داریم RCVDZY(ckptZ) = 2> 1 پس  ckptZ = eZ1 ارجاع به عقبدر Y،پس Y نیاز به عقبگرد در این مرحله ندارد.دریافتی از پیغام RollBack

اسلاید 36: مثال ادامهدر دور دوم: پیغام ارسالیسایتY RollBack(Y,2) to X, RollBack(Y,1) to ZX RollBack(X,0) to Z, RollBack(X,1) to YZ RollBack(Z,1) to Y, RollBack(Z,0) to Xمقدار ckpt در Z, Y, X بترتیب ex2 ، eY2، eZ1 است.چون مجموعه ex2} ، eY2، eZ1 {مجموعه سازگاری است لزومی به عقبگرد بیش از این نیست.در مرحله دوم و سوم وضعیت جدیدی ایجاد نمی شود.