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

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

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

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

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

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

در اثر بروز خطا محتوای خود
را از دست نمی دهد.
برای ذخیره Log و نقاط ترمیم

CPU
حافظه اصلی
Stable Storage
Secondary Storage

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

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

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

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

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

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

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

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

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

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

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

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

X
Y
X1
Y1
خطا
m1
n1
X
Y
m2
n2
Roll-back
n1

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

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

الگوریتم Toueg ,Koo برای ایجاد همگام نقاط مقابله
فرضیات
کانالها FIFO
خطای ارتباطی منجر به افراز شبکه نمی شود
دو نوع نقطه مقابله:
موقت (آزمایشی): یک نقطه مقابله موقت است که ممکن است به دائمی تبدیل شود، را روی حافظه پایدار ایجاد می کند.
دائمی :بخشی از یک نقطه مقابله سراسری است و به آن ارجاع می شود.
عدم اجرای همروند این الگوریتم
عدم وجود خطای سایت در حین اجرای الگوریتم

الگوریتم Toueg ,Koo برای ایجاد همگام نقاط مقابله – ادامه
فاز اول الگوریتم:
Pi یک C آزمایشی می گیرد و از دیگر پردازه ها هم درخواست C آزمایشی می کند. هر پردازه دیگر موفقیت خود را در این کار به Pi اعلام می کند. اگر همه موفق بودند Pi اعلام می کند که دائمی تلقی شود وگرنه دور ریخته شود.

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

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

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

X
Y
Z
X1
X2
Y1
Y2
Z1
Z2
m
آزمایشی

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

last-label-rcvdX[Y] =

first-label-sentX[Y] =

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

The algorithm
Initial 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 do
Send Take-a-tentative-ckpt(Pi, last-label-rcvd pi[p]) message;
If all processes replied “yes” then
for all processes p  ckpt-cohort pi do
Send Make-tentative-ckpt-permanent;
else
For all processes p  ckpt-cohort pi do
Send Undo-tentative-ckpt.

The algorithm Continued
At all processes p:
Upon receiving Take-a-tentative-ckpt(q, last-label-rcvd q[p]) message from q do
Begin
If OK-to-take-ckptp = “yes” AND
last-label-rcvd q[p]  first-label-sentp[q] >  then
begin
take a tentative checkpoint;
for all processes r  ckpt-cohort p do
Send Take-a-tentative-ckpt(P,last-label-rcvd p[r]) message;
If all processes r  ckpt-cohort p replied “yes” then
OK-to-take-ckptp := “yes”
Else
OK-to-take-ckptp = “no”
End;
Send (p, OK-to-take-ckptp) to q;
End;

The algorithm Continued
At all processes p:
Upon receiving Make-tentative-ckpt-permanent message do
Begin
Make tentative checkpoint permanent;
For all processes r  ckpt-cohort p do
Send Make-tentative-ckpt-permanent message;
End;
Upon receiving Undo-tentative-ckpt-permanent message do
Begin
Undo tentative checkpoint;
For all processes r  ckpt-cohort p do
Send Undo-tentative-ckpt-permanent message;
End;

Rollback-Recovery
فرض: تنها یک پردازه الگوریتم را آغاز می کند و فراخوانی همروند الگوریتم را نداریم.

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

Rollback-Recovery Continued
باز هم بهینه سازی در مواردی که لازم نیست پردازه ای با آغازی را انجام دهد:

با رخداد خطا در X ، Z نیازی به بازآغازی ندارد.

X
Y
Z
X1
X2
Y1
Y2
Z2
Z1

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

The algorithm
Initial state at process P:
Resume-execution := true;
For all processes q, do
Last-label-rcvdp[q] := T;
Willing-to-rollp = yes / no ….
 
At initiator process Pi:
For all processes p  roll-cohortpi do
Send Prepare-to-rollback(Pi, last-label-sentPi[p]) message;
If all processes p  roll-cohortpi do
Send Roll-back message;
Else
For all processes proll-cohortpi do
Send Donot-roll-back message;

The algorithm Continued
At all processes p:
Upon receiving Prepare-to-rollback(q, last-label-sentq[p])
Message from q do
Begin
If willing-to-rollp AND last-label-rcvdp[q] > last-label-sentq[p] AND (resume-executionp)
Then
Begin
Resume-executionp := false;
For all processes r  roll-cohortp do
Send Prepare-to-rollback(p, last-label- sentp[r]) message;
If all processes r  roll-cohortp replied “yes” then
willing-to-rollp := “yes”
else
willing-to-rollp := “no”
end;
Send (p, willing-to-rollp) message tp q;
End;

The algorithm Continued
Upon receiving Roll-back message AND if resume-executionp = false do
Begin
Restart from p’s permanent checkpoint;
For all processes r  roll-cohortp do
Send Roll-back message;
End;
Upon receiving Donot-roll-back message do
Begin
Resume execution;
For all processes r  roll-cohortp do
Send Roll-back message;
End; 

Async Checkpointing & Recovery
معایب نقطه مقابله سازی همگام:
پیغامهای اضافی که در هر C مبادله می شوند.
تاخیرات همگانی که در حین C پیغام محاسباتی مبادله نمی شود.
سربار زیاد درخصوص سیستمهایی که خطای نادر بین هر دو C متوالی دارند.

در روش ناهمگام، هر پردازه (پردازنده) C خود را مستقل از دیگران می گیرد. تضمینی بر سازگاری مجموعه ای از Cهای محلی وجود ندارد.
الگوریتم ترمیم باید اخیرترین مجموعه سازگار از Cها را قبل از آغاز ترمیم پیدا کند.
برای حداقل کردن میزان محاسبات undo شده در حین Rollback ، همه پیغامهای وارده Log می شوند تا احتمالا redo شوند.

  الگوریتم Juang & Venkatesan
در checkpointing ، فرض می کنیم که دو نوع Log داریم :
فرار: دسترسی سریع ولی فرّار
پایدار: هراز چندگاه یکبار ذخیره روی حافظه پایدار
هر پردازه پس از هر واقعه، سه تایی زیر را در حافظه فرّار ثبت می کند:
{s, m, msg-sent}

توجه: فرض بر event – driver سیستم است که با انتظار برای پیغام و رسیدن پیغام fire می شود.
این همان نقطه مقابله محلی برای رخداد واقعه است.

حالت پردازه قبل از رخداد واقعه

پیغام (شامل شناسه فرستنده) که رسیدنش باعث رخداد واقعه شده است
مجموعه ای از پیغامها که در طی واقعه توسط پردازنده ارسال شده است

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

الگوریتم Juang & Venkatesan ادامه

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

ex0
X
Y
Z
ex1
ex2
ex3
ey0
ey1
ey2
ey3
ez0
ez1
ez2
ez3

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

الگوریتم ادامه
for k:=1 to N do (*N is he # of processors*)
begin
for each neighboring process j do
Send 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 /* وجود پیغام یتیم*/
begin
find the latest event e such that RCVDij(e)cj;
ckpti := e;
end;
end;

الگوریتم ادامه
مثال: در نظر بگیرید:

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

X
Y
Z
ey0
ey1
ey2
ey3
ez0
ez1
ez2
ez3
ex0
ex1
ex2
ex3
X1
Y1
Z1
failure

مثال ادامه
در دور اول در ابتدا
X ckptX  eX3 RollBack(X,2) to Y, RollBack(X,0) to Z
Y ckptY  eY2 RollBack(Y,2) to X, RollBack(Y,1) to Z
Z ckptZ  eZ2 RollBack(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

مثال ادامه
در دور دوم:
پیغام ارسالی سایت
Y RollBack(Y,2) to X, RollBack(Y,1) to Z
X RollBack(X,0) to Z, RollBack(X,1) to Y
Z RollBack(Z,1) to Y, RollBack(Z,0) to X

مقدار ckpt در Z, Y, X بترتیب ex2 ، eY2، eZ1 است.
چون مجموعه ex2} ، eY2، eZ1 {مجموعه سازگاری است لزومی به عقبگرد بیش از این نیست.
در مرحله دوم و سوم وضعیت جدیدی ایجاد نمی شود.

پایان