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

صفحه 1:


صفحه 2:
ترمیم ذر سیستمهای توزیع شده هدف: بازگرداندن سیستم به حالت معمولی و نرمال خود. # تغییرات داده شده بوسیله پردازه خطا در 112010 شوند. #منابع اختصاص داده شده پس گرفته شوند. #ايده طل: اعمال يردازه مواجه شده با خطا از همان نقطه خطا ادامه يابد (؟). > عدم اجراى مجدد بخشهاى انجام شده از يردازه فوق. ا ‎١‏ ‏* همروندی و ترمیم! اثر یک پردازه روى يردازه هاى ديكر. 

صفحه 3:
‎$a ۳‏ 2 ‎BE Ay pone pose‏ #وظیفه ۳660۷6177 ۳۵111176 برگرداندن حالت سیستم (حالت مفلوط) به یک حالت بدون خطاست. ۱ اگر طبيعت خطاى ايجاد شده دقيقا ارزيلبى شود مى توان اشکال را مرتفع کرد و پردازه را قادر به حرکت به جلو کرد: 5۵60۷6۵17 5۲۲۵۲ ۳0۲۵۲0 ‏۴ اگر نمی‌توان طبیعت خطای ایجاد شده را پیش بینی کرد سیستم کار خود را از یک حالت بدون خطا ادامه می دهد: 660۷617 ۳۲۳۲۵۲ 3201617۵۲0 ‏راحت تر ‎Performance penal‏ ‏م وجود تضمین برای عدم تکرار خطا در اجرای مجدد ‎ 

صفحه 4:
ترمیم به عقب #نقاطی که می توان به آنها ارجاع و اعتماد کرد را نقاط ترمیم ‎ReECOVETY)‏ ‏5) كويند. © بازيلبى نقاط ترميم يعنى جايكزينى حللت فعلى يردازه اى با حللت آن پردازه در نقطه ترميم. #مدل سيستم: ‎a 4‏ در اثر بروز خطا محتواى خود = ‎ae‏ ‏را از دست نمی دهد. ‏براى ذخيره 1-09 و نقاط ترميع_ > ‎ 

صفحه 5:
* دو روش: 1 روش مبتنى بر اعمال ‎(Operation Based)‏ : * اعمال در سیستم ثبت می شوند طوری که با 10500 كردن اعمال مى توان به حالت قبلى دست يافت. مثال: اعمال يك تراكنش لاتغيير در & ‎(UPDATE-IN-PLACE)‏ ‏= نام شیی * پروزآوری در جا و ثبت عمل در 1.08 :: رکورد 1.08 . <لهحلت قديمى شيئ #>حالت جديد شيئ 

صفحه 6:
ترميم يذيرى تغيبرات را مى توان با اعمال زیر پیاده سازی کرد: ۴ لنجام ی کعم(و ثبتقر 1.00 ‎Undo®‏ خنثیک ردنعملنجام شده بسوسیله 410 0 اجرلیمجد عملانجام شده بوسیله 10 # برق رفتگی بین انجام یک عمل و نوشتن 1100 ,۲۷۸ ندر ‎WAL‏ ‏#بروزآوری وقتی انجام می شود که 100 1112010 مربوط به آن نوشته شده باشد. قیل از نهایی شدن یک بروزآوری» مطمئن شویم که 100 ۲600 ,و10 112200 ثبت شده باشند. 

صفحه 7:
روني مبقنى بوي حالت #ايجاد نقطه ترميم در هر مقطع با ثبت كل حالت ‎(Checkpointing) pinnw‏ #ارجاع به 016016001 پس از رخداد خطا: : 101118016 #تلاش در ۲01118016 به آخرین حالت ممکن و سازگار معمولاً در طی اجرای یک پردازه 616016001 ‌های زیادی گرفته می شود. ‎cb Shadow paging *‏ خاصی از ترمیم مبتنی بر حالت ‎ 

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

صفحه 9:
خطای * 5 بازكشت به ]2 x X #خطاى = ۷ بازگشت به ولا 0 ‎x Ef}‏ Ze Eee 2 2 7 ارسا ‎sf‏ شدم لستولی دریافش ده لسل(پیغام یتیم ل زوم ایجاع 6 به یا و **خطاى © 2 بازگشت به -» و2 لزوم بازگشت 26 و ۷ به رک و لا و متعاقب أن بازگشت 2 به رم : اثر دامینو:: تأثیر بازگشت یک پردازه روی بازگشت دیگر پردازه‌ها 

صفحه 10:
#ارجاع 26و ۷ به یرو رل © «را پیفام گشده نامیم 

صفحه 11:
,11 در رله لست ۷ به ,لاو بولسطه وجود پیغام یتیم 10,۰26 بهر26 بازمی گردد ,10 > و ل اورت انا سنسدا ‎ee‏ ا سوس حا یسیدن, 111 » ,10 ایس (شده لست ۷ نیز م10 را ایساملو مرا دییافتمیکند ولی‌در حا لتسیستمثریاز ایساسل , 2لوجود ندارد. که ™ Roll-back 

صفحه 12:
راز 6۳6010001015 (SS ‏©نقطه مقابله محلى‎ ‏مجموعه اى از نقاط مقابله محلى (از هر سايت يكى) را نقطه مقابله‎ © ‏سراسرى‎ ge "مجموعه ای قوياً سازگار از نقاط مقابله: مجموعه‌ای که هیچ جریان اطلاعاتی با بیرون, از خود نداشته باشد. 2 **مجموعه اى سازكار از نقاط مقابله: مجموعهاى كه در أن هر يبغام دریافت شده ارسالش نیز ثبت شنده باشد. #با پیغام گم شده کاری نداریم. 

صفحه 13:
روش ‎abu!‏ مجموعه‌ای سازگار از نقاط مقابله ‏ با فرض اتمیک بودن ارسال و دریافت پیفام و همچنین انجام نقطه مقابله اگر هر پردازه پس از هر پیفام یک نقطه مقابله ایجاد کند. مجموعه اخیرترین نقاط مقابله هميشه سازگار خواهد بود. = بازگشت هر پردازه به آخرین حللت ثبت شده خود منجر به پیفام نمی شود. *راه حل كران است. اگر پس از هر ارسال 6 بيغام يكبار اين كار را انجام دهيم اثر دامينو داريم! 

صفحه 14:
6 برای آیجاد همکام نقاط مقاب الگوریتم 0 فرضیات #کانالها ۳1۳0 ® خطای ارتباطی منجر به افاز شبکه نمی شود #دو نوع نقطه مقابله: #موقت (آزمايشى): يك نقطه مقابله موقت است که ممكن است به دائمى تبديل شودء را روى حافظه يايدار ايجاد مىكند. #دائمى :بخشى از يك نقطه مقابله سراسرى است و به آن ارجاع می‌شود. #عدم اجراى همروند اين الكوريتم #عدم وجود خطاى سايت در حين اجراى الكوريتم 

صفحه 15:
م نقاط مقابله - ادامه الگوریتم 1>00, 1011660 برای ایجاد همگا ©فاز اول الكوريتم: 2:9 يكت آنزمليشىمم يرد و از ديكر يردازمها هم ديخولست0 آنمليشىميك ند هر يردازة ديكر موفقيتخود را در لمينكار به "1 لعا مرک ند گر همه موفقب‌ودند ۳۱ لعا میک ند که دلئمی‌تلقی‌شود وگرنه دور ریخته شود. ©فاز دوم الكوريتم: #اعلام تصميم ,2 در پایان مرحله اول به همه يا همه © دائمى مىكيرند يا نه. لسأفرض مىكنيم كه در فاصله بين © آزمايشى و دريافت تصميم آغازكر» پیفامی ارسال نمىشود. >> حالت ناسازكار بوجود نخواهد آمد. 

صفحه 16:
بهینه سازی در الگوریتم ‎we KOO‏ #اكر يس از دريافت 22 تصميم به © بكيرد منجربه [ 22 رولا ‎(Xp,‏ خواهد شد در حللى كه 21 ,ولا ,]13 هم سازكار هستند. اكر ييغامى ارسال نشده است ميتوان © آزمايشى را در يك سايت انجام نداد. 

صفحه 17:
پیفام‌های کنترلی موردنظر نیستند. هر پیغام یک برچسب دارد. 10.1 که در هر پردازه حالت افزایشی دارد. #فرض 1 کوچکترین و 7 بزرگترین برچسب باشد. به ازاء هر ار ۰۷ فرض کنیم ‎Jim‏ پیغام دریافت شده پس از آخرین © باشد. ml if mexist @ last-label-revd,[Y] =, otnerwis ml if mexist ® first-label-sent,[Y]|5_ otherwis 

صفحه 18:
رون #هرگاه »2 از ۷ درخواست می‌کند که یک 0 آزمایشی بگیرده همراه درخواستش ‎YS st de pe |, last-label-revd,[Y]‏ تنها وقتى © مى كيرد كه ‎last-label-rcvd,[Y] = first-label-sent,[X] > 1‏ ® #ايعتى 26 رسید تعدادی پیفام را ثبت کرده است که پس از آخرین 6 در ۷ ارسال شده‌اند. ۷ هم باید واقعه ارسال آنها را ثبت کند. ©» Chkpt-cohort, = {Y | last-label-rcvd,[Y] < 1( هم در سایتهایی که باید درخواست 6 به آنها ارسال شود. 

صفحه 19:
algorithm ~ © Initial state at all processes p: For all processes g do first-label-sent,[q] := 1; " yesif p iswillingotakacheckpat OK-to-take-ckpt ng otherwis ° At initiator process P,: For all processes p € ckpt-cohort p, do Send Take-a-tentative-ckpt(P,, last-label-rcvd Pipl) message; If all processes replied “yes” then for all processes p € ckpt-cohort p,do Send Make-tentative-ckpt-permanent; else For all processes p € ckpt-cohort p, do Send Undo-tentative-ckpt. 

صفحه 20:
algorithm Continue © At all processes p: © Upon receiving Take-a-tentative-ckpt(q, last-label-rcvd qipl) message from q do Begin If OK-to-take-ckpt, = “yes” AND last-label-rcvd q{p] = first-label-sent,[q] > then begin take a tentative checkpoint; for all processes r€ ckpt-cohort , do Send Take-a-tentative-ckpt(P, last-label-rcvd plrl) message; If all processes re ckpt-cohort , replied “yes” then OK-to-take-ckpt, := “yes” Else OK-to-take-ckpt, = “no” End; Send (p, OK-to-take-ckpt,) to q; End; 

صفحه 21:
‎Continue‏ موه ‎© At all processes p: ‎* Upon receiving Make-tentative-ckpt-permanent message do Begin Make tentative checkpoint permanent; For all processes re ckpt-cohort , do Send Make-tentative-ckpt-permanent message; End; ‎* Upon receiving Undo-tentative-ckpt-permanent message do Begin Undo tentative checkpoint; For all processes re ckpt-cohort , do Send Undo-tentative-ckpt-permanent message; End; ‎ ‎ 

صفحه 22:
yack-Recove *فرض: تنها یک پردازه الگوریتم را آغاز می کند و فراخولنی همروند الگوریتم را نداریم. اريم #فاز اول: آغازگر (:۳) کنترل میکند که آیا همه پردازه ها علاقمند به بازآغازی از آخرین ) خود هستند یانه؟ پردازه ای که در یا * آغاز شده بوسیله دیگری درگیر است پاسخ "۳0" می دهد. در صورت مثبت بودن پاسخ همه. بازآغازی اعلام می‌شود. #فاز دوم: رظ تصمیمش رابه همه مى فرستد و برن اساس عمل می شود. مادام که بردازه اى متنظر ياديخ ابت ييغامى در ‎a,‏ با محاسباتش نمی فرستد 

صفحه 23:
Rollback-Recovey ‏نی‎ #باز هم بهینه سازی در مواردی که لازم نیست پردازه ای با آغازی را انجام دهد: * با رخداد خطا در .۰72 26 نیازی به بازآغازی ندارد. 

صفحه 24:
1301-76 ml if mexist © Last-Label-Sent,[Y] T Otherwis a 7 Largest Value #وقتى از لاامى خواهد كه به آخرين © دائمى ‎Last-Label-Sent,[Y] 99,5 (al‏ ,| هم مى فرستد. لا به شرطى به آخرين © خود بر مى كردد كه ‎Last-Label-Rcvd,[X] > Last-Label-Sent,[Y]‏ یعنی > متملیل به ارجاع به حالتی است که ارسال یک یا چند پیغام از6< به ۰11100 شود. ‎roll-cohort, = {Y|X can send msgs to Y}‏ ® 

صفحه 25:
algorithm © Initial state at process P: Resume-execution := true; For all processes q, do Last-label-revd,[q] := Willing-to-roll, = yes/no .... © At initiator process P,: For all processes p € roll-cohort,, do Send Prepare-to-rollback(P,, last-label-sent,[p]) message; If all processes p € roll-cohort,, do Send Roll-back message; Else For all processes peroll-cohort,; do Send Donot-roll-back message; 

صفحه 26:
‘algorithm Continue © At all processes p: Upon receiving Prepare-to-rollback(q, last-label-sent[p]) Message from q do Begin If willing-to-roll, AND last-label-revd,{q] > last-label-sent,[p] AND (resume-execution,) Then Begin Resume-execution, := false; For all processes r € roll-cohort, do Send Prepare-to-rollback(p, last-label- sent,[r]) message; If all processes r roll-cohort, replied “yes” then willing-to-roll, = “yes” else “no’ End; 

صفحه 27:
algorithm Continue Upon receiving Roll-back message AND if resume- execution, = false do Begin Restart from p’s permanent checkpoint; For all processes re roll-cohort, do Send Roll-back message; End; Upon receiving Donot-roll-back message do Begin Resume execution; For all processes re roll-cohort, do Send Roll-back message; End; 

صفحه 28:
covery 0 ایب نقطه مقابله سازی همگام: 1 پیغامهای اضافی که در هر 6 مبادله می شوند. ۲ تأخیرات همگانی که در حين ") پیفام محاسباتی مبادله نمی شود. ۳ سربار زیاد درخصوص سيستمهايى كه خطاى نادر بين هر دو © متوالى دارند. ۱ در روش ناهمگام. هر پردازه (پردازنده) "6 خود را مستقل از دیگران مى گیرد. ‏ تضمینی بر سازگاری مجموعه ای از 7های محلی وجود ندارد. الگوریتم ترمیم باید اخیرترین مجموعه سازگار از ها را قبل از آغاز ترمیم پیدا کند. ‎Gi)‏ حداقل کردن میزان محاسبات 11100 شده در حین 0110016 , همه پینامهای وارده ‎sig 42 LOG‏ تا احتمالا ۳600 شوند. 

صفحه 29:
Juang & Venka ‏الگوریتم‎ #در 012621220121120 : فرض می کنيم که دو نوع 1.00 داریم : فرار: دسترسی سریع ولی فزار : هراز چندگاه یکبار ذخیره روی حافظه پایدار هر پردازه پس از هر واقعه سه تایی زیر را در حافظه فزار ثبت می کند: ‎{s, m, msg-sent}‏ © 2 مجموعه ای از یامها که در طی واقعه توسط ۳ 4 ورنارئده رسال شده أمست پینام (شامل شناسه فرستنده) که رسیدنش باعث بارت يرطره قبل اق ۷ رخدادواقمه شده است رخداد واقعه توجه: فرض بر ‎driver‏ - 6۷610 سیستم است که با انتظار برای پیفام و رسیدن پینام 133۳6 9 9 فجن بر سیستم با انتظار:برای پیغام و رسیدن يبنام می‌شود. این همان نقطه مقابله محلی برای رخداد واقعه است. 

صفحه 30:
Notations , p; ‏ساختمان داده‌های‎ © (تأططء)ن ,1101/12 معرفتعاد ييغامهائيسيده از زبه 1لستباتوجه بهلطاهاتی‌که در أ00 ذخیرد شدملست (000)ر , 1 ‎٩۳1‏ معرفتعداد پیفامهایایسا (نده از به [باتوجه به ,0100 لست #ایده اصلی #ترميم بايد بتولند مجموعه ای سازگار از نقاط مقابله محلى بيدا كند 2 هر يردازنده هت و دریافتی خود به دیگران را می شمارد. سب وقتی پردازنده ای ۳011۳02616 می کند. بلید همه کنترل کنند که یا پیغامهای دریافت شده‌اشان تیم شدهند یا ند؟ ‎i)‏ پیفامهای دریافت کرده و ارسال ‎ond‏ اگر وجود داشت ارجاع به ‎As yo‏ قبلى و .... 

صفحه 31:
#اگر ۷ به و6 عقبگرد کند. ۷ یک پیغام به 2 فرستاده است ولی 2 دوتا پیغام از ۷ دريافت كرده 3 باید به حللت قبل از یر6 عقبگرد کند تابا ۷ سازگار باشد. 2۰ هم بايد عقبكرد كند. 

صفحه 32:
پیغامی منتشر می کند که 7011 کرده بود. الگوریتم بلافاصله پس از ترمیم از خطا و بازآغازی شروع می شود و یا با اطلاع از خطای پردازنده دیگر. به خاطر پخش پیفام به همگان, الگوریتم در همه پردازنده‌ها آغاز مى شود. "در پردازنده 1: #اكر ترميم يافته از خطاست: #آخرين واقعه [06.آ شده در حافظه بايدار 0152© - ©فرض: هر بردازنده به محض بازآغازى» #در غير اینصورت #آخرين واقعه اى كه رخ داده است ,6150 - (اعم از روی حافظه فرار یا پایدار) 

صفحه 33:
for k:=1 to N do (*N is he # of processors*) begin for each neighboring process j do Send ROLLBACK(L, SENT, ,(ckpt,)) msg; wait for ROLLBACK msg from every neighbor ‏(چون همه در حال اجرای الگوریتم هستند پس به همسایه ها پیفام را می فرستند).‎ * for every ROLLBACK(j,c) received from j, i does the following: if RCVD,,(ckpt) > c then /* ‏/*وجود بيغام يتيم‎ begin find the latest event e such that RCVD,,(e)<¢; ckpt, = e; end; end; 

صفحه 34:
الکور یی ادامه متال: در نظر بگیرید #يس از رخداد خطاء لآ بهولا برهيكردد- "د 97 ‎it‏ ‏است. جون بركشت از خطا را بخش مى كند 26 و 2 هم الكوريتم را شروع 5 

صفحه 35:
در دور او در ایتدا ©» ‏ياك ع‎ ey RollBack(X,2) to Y, RollBack(X,0) to Z © Y ckpty ce, RollBack(Y,2) to X, RollBack(Y,1) to Z ۰ 2 ckpt, en RollBack(Z,0) to X, RollBack(Z,1) to Y teh lil» = RCVDy. ,(ckpty) = 3> 2 ckpty — ‏در 26 چون مره‎ © 7 © RCVD y (ey) =2<2 RollBack ‏دریافتی از ینام‎ >" #در 2دریم 1 <2 < (یاطوله), :16۷۲ پس رره < یباع0 - ارجاع به عقب بر RCVR. <(ckpf) =1< 2 RCVR_,(ckpf) =1= SENT. ,(ckpg) پس ۷ نیاز به عقبگرد در این مرحله ندارد. 

صفحه 36:
مثال ادامه #در دور دوم: پیغام ارسال سايت ‎RollBack(Y,2) to X,‏ + ‎RollBack(Y,1) to Z‏ ‎RollBack(X,0) to Z,‏ ۰ ‎RollBack(X,1) to Y‏ ‎RollBack(Z,1) to Y, RollBack(Z,0) to X‏ 57 ‎«Cy Cz, GS» Z, ¥, X »ckpt jaa”‏ و6 است. ‏#چون مجموعه رر6 و6 ۰ (ی6 (مجموعه سازگاری است لزومی به ‏بيش از اين نيست. #در مرحله دوم و سوم وضعيت جديدى ايجاد نمى شود. ‎ ‎