پروتکل‌های Roll-back Recovery در سیستم گذر دهی پیام
اسلاید 1: فصل 12 : پروتكل‌هاي Roll-back Recovery در سيستم گذر دهي پيامدرس طراحي سيتم‌هاي مطمئنP
اسلاید 2: Rollback Fualt Tolerancy2/50چارچوب مطالبمقدمهتعاريفپروتكل‌هاي checkpointingپروتكل‌هاي بر مبناي واقعه‌نگاريمقايسهمراجع
اسلاید 3: Rollback Fualt Tolerancy3/50مقدمه :امروزه سيستمهاي توزيع شده در همه جا موجود مي‌باشند و بدين سبب ما را قادر به انجام بسياري از كارها مي‌نمايد. سيستمهايClient Server و WWW و محاسبات علمي از جمله بسياري از آنها مي‌باشند.پتانسيل اين سيستمها به خاطر گستردگي محاسبات و با توجه به حساسيت آنها نسبت به وقوع خطا محدود مي‌گردد. از اينرو تكنيكهاي فراواني براي قابليت اطمينان، دسترس پذيري بالا براي سيستمهاي توزيع شده گسترش يافته است.اين تكنيكها شامل موارد زير مي‌باشد:Transactions:بر كاربردهاي داده گرا تمركز دارد.Group communications :انتزاعي از يك سيتم ارتباطي ايده‌آل كه برنامه نويس مي‌تواند برنامه‌اش را بصورت مطمئن بر روي آن توسعه دهد، پيشنهاد مي‌كند.Rollback recovery :بر روي كاربردهاي با زمان اجراي طولاني تمركز دارد، مانند محاسبات علمي و كاربردهاي ارتباطي.
اسلاید 4: Rollback Fualt Tolerancy4/50مدل سيستمسيستم گذر دهي پيام (message passing system) شامل تعداد ثابتي فرايند که بين آنها پيام رد و بدل ميشود، مي‌باشد. فرايندها براي اجراي برنامه کاربردي توزيع شده ضمن تعامل با جهان خارج با دريافت پيام ورودي و ارسال پيام خروجي، با هم همکاري مي‌کنند. يک فرايند ممکن است بدليل گم كردن حالت موقت خود يا توقف اجرا بر اساس مدل توقف به محض خرابي، دچار خرابي شود.
اسلاید 5: Rollback Fualt Tolerancy5/50مفهوم Rollback Recovery در سيستمهاي توزيع شدهدر سيستم فوق تحمل‌پذيري خطا با ذخيره حالت فرايندهاي سيستم در دوره‌هاي خاص، زمان اجراي عاري از خطا طبق سياست معين، روي منبع ذخيره پايدار Stale Storage و بازگشت به يكي از آن حالات هنگام بروز خرابي ميسر ميشود. اين كار سبب كاهش محاسبات از دست رفته ميشود.هر حالت ذخيره شده يك Checkpoint نام دارد. عمليات بازيافتي كه فرايند به محض وقوع خطا انجام مي‌دهد تا به يكي از اين Checkpoint ها بازگشت نمايد Rollback Recovery مي‌گويند.Rollback Recovery با سيستم توزيع شده بعنوان مجموعه‌اي از فرايندها كه در طول شبكه با هم در ارتباط هستند رفتار مي‌كند.پروتكل‌هاي Rollback Recovery به دو دسته تقسيم مي‌شوند:Checkpoint-based براي جلوگيري از هدر رفتن محاسبات و عمليات، بر روي هر فرايند در مواردي طبق سياست خاص از وضعيت فرايند Checkpoint گرفته ميشود. بسته به نحوه گرفتن Checkpoint به سه دسته هماهنگ، ناهماهنگ و وابسته به ارتباط تقسيم ميشود. log-basedعلاوه بر مورد بالا رخدادهاي غيرقطعي فرايندها را نيز ثبت مي‌كند تا مقدار بيشتري از عمليات انجام شده را بازيافت نمايد. بسته به نوع ثبت رخداد به سه دسته بدبينانه، خوشبينانه، سببي تقسيم ميشود.
اسلاید 6: Rollback Fualt Tolerancy6/50چارچوب مطالبمقدمهتعاريفپروتكل‌هاي checkpointingپروتكل‌هاي بر مبناي واقعه‌نگاريمقايسهمراجع
اسلاید 7: Rollback Fualt Tolerancy7/50حالت سازگار سراسري سيستمبدليل انتقال پيام بين فرايندها در سيستم گاهي پيش مي‌آيد كه يك Checkpoint نشان‌دهنده آن است كه فرايند پيامي دريافت كرده، در حالي كه هيچ Checkpoint از فرايند ديگري نشان‌دهنده ارسال آن پيام نيست. چنين پيامي را يتيم Orphan مي‌گويند.در Recovery به تركيبي از Checkpoint ها كه درRollback بدست مي‌آيد، حالت سيستم مي‌گويند.اين حالت بدليل وجود پيام يتيم به دو دسته تقسيم مي‌شوند:حالتي كه در آن پيام يتيم وجود داشته باشد حالت ناسازگار Inconsistent حالتي كه پيام يتيم نداشته باشد و يك اجراي درست را نشان دهد سازگار Consistent گويند.در Recovery هدف پيدا كردن تركيبي از Checkpoint ها بطوري كه حالت سازگار سراسري سيستم را نشان دهد، و بازگشت به آن حالت در سيستم مي‌باشد.
اسلاید 8: Rollback Fualt Tolerancy8/50پيام يتيم پيامي است که دريافت شده اما فرستنده‌اي ندارد.موقعيتي را نشان مي‌دهد که پيام از فرستنده ارسال شده و در شبکه سرگردان مي‌باشد.فرايند P2 نشان مي‌دهد m2 دريافت شده اما حالت فرايند P1 ارسال آن را منعکس نکرده است.پيام گذرا پيامي است که فرستاده شده اما هنوز دريافت نشده است.
اسلاید 9: Rollback Fualt Tolerancy9/50مسير Z و چرخه Z مسير Z (مسير زيگزاگي) دنباله خاصي از پيام‌ها است که دو checkpoint را به هم متصل مي‌کند. {m1,m2} , {m3,m4} چرخه Z مسير Z اي است که نقطه شروع و پايان آن يکي باشد. {m5,m3,m4} يک checkpoint درون چرخه Z نمي‌تواند بخشي از يک حالت سازگار در سيستمي که فقط از checkpoint استفاده مي‌کند، باشد.Z-cycleZ-pathX
اسلاید 10: Rollback Fualt Tolerancy10/50پيام‌هاي گذرا وجود پيام گذرا بسته به اين است که کانال ارتباطي امن در مدل سيستم فرض شده باشد يا نه. فرض ارتباط امن طراحي پروتکل را راحت مي‌کند اما پياده سازي را مشکل مي‌نمايد.
اسلاید 11: Rollback Fualt Tolerancy11/50اطلاعات Checkpointing و وابستگي فرايندهادر checkpointing هر فرايند حالت خود را به صورت دوره‌اي بر روي Stable Storage ذخيره مي‌كند. حالت ذخيره شده يك فرايند شامل اطلاعات كافي براي شروع مجدد آن فرايند مي‌باشد.در سيستم گذر دهي پيام بخاطر تبادل پيام بين فرايندها هنگام عمليات عاري از خطا، وابستگي ايجاد ميشود، به همين دليل داراي Rollback Recovery پيچيده مي‌باشد.هر حالت سراسري سازگار از checkpoint در سيستم مي‌تواند براي شروع مجدد فرايندها به محض وقوع خطا بكار رود.مجموعه Checkpoint هاي سراسري سازگار در سيستم يك خط ارجاع را تشكيل داده كه به آن Recovery Line گويند، اين خط هنگام Recovery مشخص و سيستم به آن حالت برمي‌گردد.
اسلاید 12: Rollback Fualt Tolerancy12/50Propagation Rollback و اثر دومينوفرايندها بسته به نيازشان هنگام اجرا با هم ارتباط برقرار مي‌كنند. بدينوسيله وابستگي بين آنها ايجاد ميشود.هنگام وقوع خرابي در يك يا چند فرايند، در زمان Rollback ، به خاطر وابستگي بين فرايندها علاوه بر فرايندي كه در آن خرابي رخ داده، ممكن است ساير فرايندها نيز مجبور به Rollback شوند. به اين پديده Rollback Propagation مي‌گويند.حالت سراسري سازگار checkpoint مي‌تواند Rollback Propagation را محدود نمايد.اگر در برخي سناريوهاي خرابي اين Rollback Propagation منجر به اين شود كه همه فرايندها به حالت اوليه خود برگردند، اثر دومينو (Domino Effect) رخ داده است. وقوع اين پديده باعث از دست رفتن تمامي محاسبات قبل از خرابي گشته و سيستم را به حالتي كه هيچ عملياتي انجام نداده بود مي‌برد. بدين جهت اين پديده نامطلوب است.
اسلاید 13: Rollback Fualt Tolerancy13/50براي اجتناب از اثر دومينو در سيستم، فرايندها بايد checkpointing خود را بصورت هماهنگ انجام داده كه سبب پيشرفت Recovery line ميشود. يا اينكه عمليات checkpointing خود را با واقعه نگاري نگاري تركيب كنند.Rollback Propagation//123456789Initial StateDomino Effect
اسلاید 14: Rollback Fualt Tolerancy14/50Checkpointing و اثر دومينوهنگامي كه هر فرايند مستقلاٌ عمليات checkpointing را انجام دهد مي‌تواند سبب پيدايش اثر دومينو شود.( عمليات checkpointing ناهماهنگ) يكي از روشهايي كه سبب ميشود عمليات checkpointing هماهنگ انجام شود اين است كه سيستم در بعد وسيع حالت سازگار خود را ذخيره نمايد.راه ديگر اينكه checkpointing بر مبناي ارتباط باشد. به اين معني كه هر فرايند را مجبور كند بر اساس اطلاعات سوار شده بر پيام‌هايي كه از فرايندهاي ديگر دريافت مي‌كند، checkpoint خود را بگيرد. Checkpoint هايي كه در كل سيستم به صورت سازگار گرفته شده‌اند، هميشه بر روي Stable Storage وجود دارند، بنابراين از اثر دومينو اجتناب ميشود.
اسلاید 15: Rollback Fualt Tolerancy15/50تعامل با دنياي خارجيك سيستم گذردهي پيام معمولا براي دريافت داده يا نشان دادن خروجي محاسبات با دنياي خارج در تعامل است. با اين تفاوت كه اگر خرابي رخ دهد دنياي خارج نمي‌تواند به Rollback تكيه نمايد.بنابراين پروتكل‌هاي Rollback براي تعامل با دنياي خارج بايد رفتار خاصي را بر گزيند.قبل از ارسال خروجي به دنياي خارج، سيستم بايد مطمئن شود حالتي كه خروجي از آن ارسال ميشود، عليرغم خرابي در آينده، قابل بدست آوردن است.(مساله صدور خروجي)براي پيام‌هاي ورودي راه حل عبارت از ذخيره پيام ورودي بر روي Stable Storage، قبل از اينكه به برنامه كاربردي اجازه پردازش آن داده شود، مي‌باشد.
اسلاید 16: Rollback Fualt Tolerancy16/50Logging Protocols vs. Checkpointingروش واقعه نگاري وقتي تعامل با دنياي خارج مكرر است، بيشتر استفاده ميشود. زيرا يك فرايند را قادر مي‌سازد اجرايش را تكرار كند و با ارسال خروجي به دنياي خارج بدون داشتن هزينه گران checkpointing قبل از ارسال خروجي سازگاري داشته باشد.XXOrphan messageXReplay delivery to recover messagesWith checkpointing
اسلاید 17: Rollback Fualt Tolerancy17/50Stable Storage & Garbage CollectionRollback Recovery از Stable Storage براي ذخيره checkpoint فرايندها، واقعه نگاري و ساير اطلاعات مربوط به بازيابي استفاده مي‌كند.Garbage Collection براي پاك كردن اطلاعات بازيابي بلا استفاده بكار مي‌رود.(زباله داني checkpoint مي‌باشد)يك راه براي Garbage collection مشخص كردن Recovery line و حذف تمامي اطلاعات مربوط به رخدادهايي كه قبل از آن خط رخ داده‌اند، مي‌باشد. اجراي الگوريتم خاص براي حذف اطلاعات بلا استفاده موجب سربار در سيستم ميشود.
اسلاید 18: Rollback Fualt Tolerancy18/50چارچوب مطالبمقدمهتعاريفپروتكل‌هاي checkpointingپروتكل‌هاي بر مبناي واقعه‌نگاريمقايسهمراجع
اسلاید 19: Rollback Fualt Tolerancy19/50Checkpointing ناهماهنگCheckpointing ناهماهنگ به هر فرايند اجازه بيشترين خود استقلالي را براي تصميم‌گيري در گرفتن checkpoint مي‌دهد.مزيت اصلي اين خود استقلالي عبارت از:هر فرايند checkpoint خود را زماني كه قادر است، مي‌گيرد. براي مثال يك فرايند مي‌تواند سربار را با checkpointing در وقتي كه مقدار حالاتي كه بايد ذخيره كند، كوچك باشد، كاهش دهد.معايب:احتمال وقوع اثر دومينو كه سبب از دست دادن مقدار وسيعي از كار انجام شده ميشود، وجود دارد.فرايند ممكن است checkpoint بلا استفاده‌اي را كه هرگز بخشي از يك حالت سازگار سراسري نخواهد بود، بگيرد. checkpoint مذكور مطلوب نيست زيرا موجب سربار شده و در پيشرفت خط بازيافت دخالتي ندارد.checkpointing ناهماهنگ فرايندها را مجبور به نگهداري چندين checkpoint مي‌كند و باعث اجراي دوره‌اي الگوريتم Garbage collection براي دور ريختن checkpoint هايي كه مدت طولاني استفاده نشده‌اند، ميشود.براي كاربردهايي كه خروجي دارند مناسب نمي‌باشد زيرا نيازمند يك هماهنگي سراسري براي محاسبه خط بازيافت مي‌باشد.
اسلاید 20: Rollback Fualt Tolerancy20/50اطلاعات وابستگيLet Ci,x be the Xth checkpoint of process Pi (X: Checkpoint index).Let Ii,x denote the interval between checkpoints Ci,x-1 & Ci,x .If Pi at Ii,x sends message m to Pj , it will piggyback the pair (i,x) on m.When Pj receives m in Ij,y , it records dependency info when Pj takes cj,y .
اسلاید 21: Rollback Fualt Tolerancy21/50چگونه بازيافت انجام ميشود؟RecoveringProcessProcess 1Process 0Process 2Process NDependency requestStop ExecutionCalculates recovery line based on global dependency informationDependency informationRecovery lineاگر حالت كنوني در طول خط بازيافت بود اجرا ادامه مي‌يابد، در غير اينصورت به checkpoint نزديك خط بازيافت عقب گرد مي‌كند.Dependency requestDependency InformationRequest for RollbackResume or Rollback
اسلاید 22: Rollback Fualt Tolerancy22/50گراف وابستگي و گراف checkpoint در محاسبه خط بازيافتNode: checkpoint D-edge: Messagefrom ci,x to cj,y if:i ≠ j, and M from Ii,x to Ij,yi = j and y = x + 1When a message sent from Ii,x to Ij,y , a D-edge drawn ci,x-1 to cj,y (instead ci,x , cj,y)Dependency GraphCheckpoint Graph
اسلاید 23: Rollback Fualt Tolerancy23/50Garbage Collection هر checkpoint اي براي هر تركيب ممكن از خرابي فرايندها كه قبل از Recovery Line باشد مي‌تواند جزو Garbage collection باشد. هنگامي كه Recovery Line پيشرفت نمي‌كند، بخاطر Rollback Propagation تعداد زيادي از checkpoint هاي غير ضروري لازم است نگهداري شوند.1. Mark all volatile checkpoints & remove all edges ending in a marked checkpoint.2. Use reachability analysis to determine the worst-case recovery line.
اسلاید 24: Rollback Fualt Tolerancy24/50Checkpointing هماهنگپروتكل checkpointing هماهنگ نياز دارد كه فرايندها checkpoint خود را به صورت هماهنگ در قالب يك حالت سراسري سازگار بگيرند. مزايا:ساده‌سازي در Recoveryدر آن اثر دومينو انتظار نمي‌رود، زيرا هميشه هر فرايند از آخرين checkpoint خود شروع مجدد مي‌نمايد.هر فرايند فقط مجبور به نگهداري يك checkpoint در stable storage مي‌باشد كه سبب كاهش سربار ذخيره، همچنين حذف نياز به Garbage collection ميشود.عيب عمده:تاخير طولاني براي صدور خروجي، زيرا يك checkpoint سراسري قبل از صدور خروجي به دنياي خارج نياز است.
اسلاید 25: Rollback Fualt Tolerancy25/50چگونه chekpoint ها هماهنگ مي‌شوند؟CoordinatorProcess 1Process 0Process 2Process NBlock communications while the checkpointing protocol executesTake a checkpointRequest messageTake a checkpointStop ExecutionFlush all Communication ChannelsTake Tentative CheckpointAcknowledgmentSend Ack.Commit messageCommit messageRemove old checkpointMakes tentative checkpoint, then free to resume execution and exchange messages
اسلاید 26: Rollback Fualt Tolerancy26/50Non-blocking Checkpoint Coordinationيك مساله ابتدائي در checkpointing هماهنگ جلوگيري فرايند از دريافت پيام مي‌باشد كه مي‌تواند checkpointرا ناسازگار سازد.
اسلاید 27: Rollback Fualt Tolerancy27/50كلاك سنكرون شده checkpointكلاك سنكرون مي‌تواند سبب تحريك عمليات checkpointing محلي همه فرايندها، تقريبا در همان زمان، بدون checkpoint شروع كننده شود.يك فرايند checkpoint مي‌گيرد و براي مدتي كه مساوي با مجموع بيشترين انحراف بين كلاك و بيشترين زمان براي تشخيص خرابي در فرايندهاي ديگر در سيستم مي‌باشد، منتظر مي‌ماند.فرايندها مي‌توانند مطمئن باشند كه همه checkpoint ها بدون نياز به تبادل هيچ پيامي به صورت هماهنگ گرفته شده‌اند.
اسلاید 28: Rollback Fualt Tolerancy28/50Minimal Checkpoint Coordinationبراي checkpoint هماهنگ لازم است كه همه فرايندها در هر عمليات checkpointing شركت كنند.اين نيازمندي به مفهوم مقياس پذيري وابسته مي‌باشد. بنابراين كاهش تعداد فرايندهايي كه در checkpoint هماهنگ شركت دارند، مطلوب مي‌باشد.در طول فاز اول، checkpoint آغاز كننده همه فرايندهايي كه با آن از checkpoint قبلي ارتباط داشته است را مشخص نموده و به آنها يك درخواست مي‌فرستد.فرايند به محض دريافت درخواست، همه فرايندهايي كه با آن فرايند از checkpoint قبلي ارتباط داشته است را مشخص نموده و به آنها يك درخواست مي‌فرستد و به همين منوال تا اينكه فرايند ديگري براي شناسايي نباشد.در طول فاز دوم، همه فرايندهايي كه در فاز اول شناسايي شدند checkpoint مي‌گيرند.
اسلاید 29: Rollback Fualt Tolerancy29/50از اثر دومينو جلوگيري مي‌كند با اينكه به فرايندها اجازه مي‌دهد برخي checkpoint ها را مستقلا بگيرند.بهرحال فرايندهاي مستقل مجبور به ضمانت تحول پيشرفت خط بازيافت مي‌باشد. بنابراين فرايندها مجبور به گرفتن checkpoint اضافي مي‌باشند.(checkpoint اجباري)Checkpoint اجباري بايد قبل از آنكه كاربرد محتواي پيام را پردازش كند، گرفته شود كه موجب تاخير و سربار زياد ميشود.در عوض با checkpoint گرفتن هماهنگ هيچ پيام خاصي رد و بدل نمي‌شود.Communication-induced Checkpointing
اسلاید 30: Rollback Fualt Tolerancy30/50چارچوب مطالبمقدمهتعاريفپروتكل‌هاي checkpointingپروتكل‌هاي بر مبناي واقعه‌نگاريمقايسهمراجع
اسلاید 31: Rollback Fualt Tolerancy31/50Log-Based Rollback Recoveryاجراي يك فرايند مي‌تواند با دنباله‌اي از بازه حالات قطعي مدل شود كه شروع هر اجرا و بعبارتي بازه با يك رخداد غير قطعي آغاز ميشود.شروع بازه قطعي فقط به دنباله‌اي از رخدادهاي غير قطعي كه قبل از شروع بازه مي‌باشد، بستگي دارد.P0P1m1m2m3m4Deterministic IntervalNondeterministic event
اسلاید 32: Rollback Fualt Tolerancy32/50Log-Based Rollback Recovery Concepts:اين روش بر قطعيت تكه‌اي تكيه دارد. فرض مي‌كند همه رخدادهاي غير قطعي مي‌تواند مشخص شود و عامل‌هاي مربوطه مي‌تواند در stable storage ذخيره شود.با واقعه نگاري و پاسخ به رخدادهاي غير قطعي به ترتيب اصلي خود، يك فرايند قطعا مي‌تواند حالت قبل از خرابي خود را بازسازي كند حتي اگر اين حالت checkpointing نشده باشد.علي الخصوص براي كاربردهايي كه با دنياي خارج در تعامل هستند كه شامل وسايل ورودي/خروجي كه نمي‌تواند Rollback نمايد، جذاب مي‌باشد.با اين حال هر فرايند براي كاهش گسترش عقب گرد در طول بازيافت checkpointing را انجام مي‌دهد.Rollback بر مبناي واقعه نگاري به حالتي فراتر از checkpoint هاي سازگار اخير مي‌رسد و ضمانت مي‌كند سيستم هيچ فرايند يتيمي را توليد نكند.
اسلاید 33: Rollback Fualt Tolerancy33/50واقعه نگاري بدبينانه در مقابل خوشبينانهدر واقعه نگاري بدبينانه كاربرد بايد بلوك شده و منتظر عامل‌هاي رخدادهاي غيرقطعي شود. و قبل از آنكه اثر آن رخداد توسط بقيه فرايندها يا دنياي خارج ديده شود، واقعه نگاري شود.خطا مي‌تواند بعد از هر رخداد غير قطعي رخ دهد.در واقعه نگاري خوشبينانه، كاربرد بلوك نمي‌شود. عاملها در يك log موقتي نگهداري ميشود و به صورت آسنكرون در stable storage تخليه شود. واقعه نگاري قبل از ايجاد خطا كامل ميشود.
اسلاید 34: Rollback Fualt Tolerancy34/50Log-base بر اساس اينكه عاملها چگونه نگاشته شوند داراي سه روش گوناگون استپروتكل بدبينانه ضمانت مي‌كند كه بخاطر خرابي يتيمي توليد نخواهد شد. اين پروتكل سبب سادگي در recovery و Garbage collection و خروجي با هزينه سربار كارايي بالاتر هنگام عاري از خطا بودن ميشود.پروتكل خوشبينانه سربار كارايي بدون خطا بودن را كاهش مي‌دهد اما اجازه ايجاد يتيم را بخاطر خطا مي‌دهد. احتمال داشتن يتيم بازيافت و Garbage collection و خروجي را پيچيده مي‌كند.پروتكل سببي سعي بر تركيب مزاياي سربار پائين كارايي و خروجي سريع را دارد. اما ممكن است نيازمند recovery و Garbage collection پيچيده گردد.
اسلاید 35: Rollback Fualt Tolerancy35/50چگونه بدبينانه بازيافت مي‌كند؟Logs determinants{m0, m4, m7}{m1, m3, m6}{m2, m5}P1, P2 FailRestart fromRoll forward use determinant logs to deliver same sequence of messages.Recovery is completeReceipt message m7 from P1Both state Z,Y is consistent with X
اسلاید 36: Rollback Fualt Tolerancy36/50در سيستم log كردن بدبينانه ....حالت قابل مشاهده هر فرايند هميشه قابل بازيافت است.مزايا:فرايندها مي‌تواند بدون اجراي پروتكل خاصي به دنياي خارج خروجي صادر كنند.فرايندها از checkpoint اخير خود به محض وقوع خرابي مجدد شروع مي‌كنند.محدود كردن گسترش اجراي مجددبازيافت ساده شد زيرا اثر خرابي فقط محصور به فرايندي كه خراب شده ميشود.يك فرايند هيچ وقت يتيم نخواهد شد. زيرا فرايند هميشه به حالتي كه شامل تعامل اخير با فراينديهاي ديگر يا دنياي خارج است، باز مي‌گردد.اطلاعات بازيافت مي‌تواند به آساني دور ريخته شود.Checkpoint هاي قديمي‌تر و عامل‌هاي رخدادهاي غيرقطعي قبل از checkpoint اخير مي‌توانند حذف شود.هزينه‌اي كه براي اين مزايا بايد پرداخت شود جريمه كارايي با واقعه نگاري سنكرون مي‌باشد.
اسلاید 37: Rollback Fualt Tolerancy37/50SMBL عامل‌هاي متناظر با انتقال پيام m را در حافظه موقت فرستنده نگهداري مي‌كند. عامل‌هاي m شامل محتوا و ترتيبي كه ارسال شده در دو مرحله ثبت ميشود.SMBL فقط مي‌تواند يك خرابي را تحمل نمايد و رخدادهاي غيرقطعي داخل يك فرايند را نمي‌تواند حل نمايد.كاهش سربار توسط روش: Sender-Based Message Logging (SBML)Then receiver responds with an ack. includes order in which the message was delivered.Sender logs its content in volatile memoryBefore Sending mSender adds to the determinant ordering information
اسلاید 38: Rollback Fualt Tolerancy38/50كاهش سربار توسط روش: Relaxing Logging Atomicityبا ارسال پيام يا رخداد و تفاوت قائل شدن ميان ثبت آنها تا زماني كه ميزبان با ميزبان‌هاي ديگر يا دنياي خارج ارتباط برقرار نمايد.در P0 ثبت پيام‌هاي m7 , m4 تا زماني كه با فرايندهاي ديگر يا دنياي خارج در ارتباط هستند، تغيير مي‌كند.پيام‌هاي m4 و m7 مجاز به اثر گذاري بر روي فرايند P0 مي‌باشند، اما اين اثر محلي است و فرايند ديگري يا دنياي خارح آن را نمي‌توانند ببينند تا اينكه پيام ثبت شود.ثبت رخداد و ارسال آن در اين واقعه‌نگاري خوشبينانه نمي‌تواند در عمليات يك لحظه‌اي انجام شود.اين طرح مي‌تواند سربار را كاهش دهد، زيرا چندين رخداد مي‌تواند در يك عملكرد كه باعث كاهش تعدد دسترسي به stable storage ميشود، ثبت شود. تاخير ارتباط بين فرايندي و صدور خروجي كاهش نمي‌يابد زيرا عمليات ثبت معمولا قبل از ارسال پيام نياز است.
اسلاید 39: Rollback Fualt Tolerancy39/50چگونه خوشبينانه بازيافت مي‌كند؟P0 roll back to undo effects of m7Before m5 is loggedXP1 become OrphanRestart from B instead DOrphan اگر در فرايندي خرابي رخ داد، عاملها در log موقتي آن از بين خواهند رفت. روش خوشبينانه شرط هميشه بدون يتيم را پياده نمي‌كند. پروتكل‌هاي خوشبينانه نياز به اين دارد كه چندين checkpoint را نگهداري نمايد. براي آسنكرون بودن صدور خروجي نيازمند هماهنگي چندين ميزبان مي‌باشد.Need toCommit outputLogAsk to logP2 rollback Orphan
اسلاید 40: Rollback Fualt Tolerancy40/50Recovery سنكرونهمه فرايندها پروتكل Recovery را براي محاسبه بيشترين حالت قابل بازيافت سيستم، بر اساس وابستگي و اطلاعات نگاشته شده انجام مي‌دهند. سپس Rollback را انجام مي‌دهند.وابستگي مستقيمانديس بازه فرستنده بر روي هر پيام خروجي براي اينكه به دريافت كننده اجازه دهد تا وابستگي كه مستقيما بواسطه پيام ايجاد شده، ضبط نمايد.وابستگي متعديوابستگي متعدي عموما سبب ايجاد سربار بالاتري براي سوار شدن بر پيام‌ها و نگهداري بردار وابستگي ميشود. اما صدور خروجي و بازيافت سريعتري را به ارمغان مي‌آورد. روش آن به شكل زير است:Each process Pi maintains a size-N vector TDi, where TDi[i] is Pi’s current state interval index, & TDi[j], j≠i, records the highest index of any state interval of Pj on which Pi depends.
اسلاید 41: Rollback Fualt Tolerancy41/50Multiple incarnations of the same process may coexist in the Asynchronous RecoveryIf a single failure causes a process to roll back an exponential number of times.In general which process Pi , i > 0, rolls back 2i-1 times in response to P0’s failure.Approach is to piggyback the original rollback announcement on any subsequent rollback announcement (P1 piggybacks r0 on r1). [i,x]: xthinterval of ithincarnationRollbackannouncementP0 failslosesr1 reaches P2 before r0
اسلاید 42: Rollback Fualt Tolerancy42/50m5 , m6 may be lostP0 at X logged determinants of m0,m1,m2,m3,m4Determinant of each events contains: order in which its original receiver delivered the corresponding message.P0 will be able to guide the recovery of P1 , P2 since it knows the order in which P1 should replay messages m1 , m3 to reach the state from which P1 sends message m4.Notice information about m5,m6 is not available anywhere.
اسلاید 43: Rollback Fualt Tolerancy43/50چارچوب مطالبمقدمهتعاريفپروتكل‌هاي checkpointingپروتكل‌هاي بر مبناي واقعه‌نگاريمقايسهمراجع
اسلاید 44: Rollback Fualt Tolerancy44/50مقايسه:
اسلاید 45: Rollback Fualt Tolerancy45/50چارچوب مطالبمقدمهتعاريفپروتكل‌هاي checkpointingپروتكل‌هاي بر مبناي واقعه‌نگاريمقايسهمراجع
اسلاید 46: Rollback Fualt Tolerancy46/50SurveyE. N. Elnozahy, D. B. Johnson, and Y. M. Wang, A survey of rollback-recovery protocols in message-passing systems, Tech. Rep. No. CMU-CS-96-181, Dept. of Computer Science, Carnegie Mellon University, 1996. L. Alvisi and K. Marzullo, Message Logging: Pessimistic, Optimistic, and Causal, Proceedings of the 15th IEEE International Conference on Distributed Computing Systems. Vancouver, Canada, June 1995, pp. 229-236.
اسلاید 47: Rollback Fualt Tolerancy47/50Model & ConsistencyK. M. Chandy and L. Lamport, Distributed Snapshots: Determining Global States of Distributed Systems, ACM Trans. on Computer Syst., vol. 3, no.1, pp. 63-75, Feb. 1985. Y. M. Wang, A. Lowry, and W. K. Fuchs, Consistent global checkpoints based on direct dependency tracking, Information Processing Letters, Vol. 50, No. 4, pp. 223-230, May 1994. Y. M. Wang, Maximum and minimum consistent global checkpoints and their applications, in Proc. IEEE Symp. Reliable Distributed Syst. (SRDS), pp. 86--95, Sept. 1995. Jian Xu and Robert H. B. Netzer, Necessary and Sufficient Conditions for Consistent Global Snapshots,(cs93-32.ps), IEEE Trans. on PADS., Vol. 6, No. 2, February 1995. D. Manivannan and M. Singhal, A Low-overhead Recovery Technique Using Quasi-Synchronous Checkpointing, In Proceedings of the 16th International Conference on Distributed Computing Systems, May 1996, pages 100-107. D. Manivannan, Robert H. B. Netzer and M. Singhal, Finding Consistent Global Checkpoints in a Distributed Computation, (OSU-CISRC-3/96-TR16) In IEEE Transactions on Parallel and Distributed Systems, 8(6):623-627, June 1997. D. Manivannan and M. Singhal, Quasi-Synchronous Checkpointing: Models, Characterization, and Classification, Submitted to IEEE Transactions on Parallel and Distributed Systems.(1999)
اسلاید 48: Rollback Fualt Tolerancy48/50Checkpointing (No logging)Jian Xu and Robert H. B. Netzer, Adaptive Independent Checkpointing for Reducing Rollback Propagation, (cs93-25.ps) In Proc. 5th IEEE Symp. on Parallel and Distributed Processing, pages 754-761, December 1993. B. Bhargava and S. R. Lian, Independent Checkpointing and Concurrent Rollback for Recovery - An Optimistic Approach, In Proc. of IEEE Symp. on Reliable Distributed Syst., pp. 2-12, 1988. R. Koo and S. Toueg, Checkpointing and Rollback-Recovery for Distributed Systems, IEEE Trans. on Software Eng., vol. SE-13, no. 1, pp. 23-31, Jan. 1997. J. L. Kim and T. Park, An Efficient Protocol for Checkpointing Recovery in Distributed Systems, IEEE Trans. on Parallel and Distributed Syst., vol. 4, no. 8, pp. 955-960, Aug. 1993. Y. M. Wang and W. K. Fuchs, Lazy checkpoint coordination for bounding rollback propagation, in Proc. IEEE Symp. on Reliable Distributed Systems (SRDS-12), pp. 78--85, Oct. 1993.Y. M.Wang, P. Y. Chung, I. J. Lin, andW. K. Fuchs. “Checkpoint space reclamation for uncoordinated checkpointing in message-passing systems.” IEEE Trans. Parallel and Distributed Syst., 6(5):546–554, May 1995.
اسلاید 49: Rollback Fualt Tolerancy49/50Implementation & PerformanceElmootazbellah Nabil Elnozahy, David B. Johnson, and Willy Zwaenepoel, The Performance of Consistent Checkpointing, In Proceedings of the 11th Symposium on Reliable Distributed Systems, pp. 39-47, IEEE Computer Society, Houston, TX, October 1992. Y. Huang, C. Kintala, and Y. M. Wang, Software Tools and Libraries for Fault Tolerance, in Bulletin of the Technical Committee on Operating Systems and Application Environment (TCOS), Vol. 7, No. 4, pp. 5--9, Winter, 1995. Y. M. Wang, Y. Huang, K.-P. Vo, P. Y. Chung, and C. Kintala, Checkpointing and its applications, in Proc. IEEE Fault-Tolerant Computing Symposium (FTCS-25), pp. 22-31, June 1995.Roberto Baldoni, Jean Michel Helary, Achour Mostefaoui, Michel Raynal. “Consistent Checkpointing in Message Passing Distributed Systems”. Institut National de Recherche en Informatique et en Automatique, Juin, 1995.Gerard P. Kavanaugh and William H. Sanders. “Performance Analysis of two Time- Based Coordinated Checkpointing Protocols.” Center for Reliable & High-Performance Computing Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, From Pacfic Rim International Symposium on Fault-Tolerant Systems, Taipei, Taiwan, December 15-16, 1997.B. Bhargava and S. R. Lian. “Independent checkpointing and concurrent rollback for recovery - An optimistic approach.” In Proc. IEEE Symp. Reliable Distributed Syst., pages 3–12, 1988.
اسلاید 50: Rollback Fualt Tolerancy50/50MiscellaneousE. Cohen, Y. M. Wang, and G. Suri, When piecewise determinism is almost true, in Proc. Pacific Rim International Symposium on Fault-Tolerant Systems, pp. 66--71, Dec. 1995. Y. M. Wang, P. Y. Chung, and W. K. Fuchs, Tight upper bound on useful distributed system checkpoints, Tech. Rep. CRHC-95-16, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 1995. Ramamurthy, B., Upadhyaya, S., Bhargava, B., Design and analysis of an integrated checkpointing and recovery scheme for distributed applications, IEEE Transactions on Knowledge and Data Engineering, Volume: 12 Issue: 2, March-April 2000 Page(s): 174 -186 Dan Pei, Dongsheng Wang, Meiming Shen, Weimin Zheng, Design and implementation of a low-overhead file checkpointing approach, High Performance Computing in the Asia-Pacific Region, 2000. Proceedings. The Fourth International Conference/Exhibition on, Volume: 1 , 2000 Page(s): 439 -441 vol.1 Meth, K.Z., Tuel, W.G., Parallel checkpoint/restart without message logging, International Workshops on Parallel Processing, 2000. Page(s): 253 -258 Yi Zhang, Jianping Hu Checkpointing and process migration in network computing environment, Info-tech and Info-net, 2001. Proceedings. ICII 2001 - Beijing. 2001 International Conferences on, Volume: 3 , 2001 Kasbekar, M.; Das, C.R., Selective checkpointing and rollbacks in multithreaded distributed systems, Distributed Computing Systems, 2001. 21st International Conference on. , 2001 Page(s): 39 -46
نقد و بررسی ها
هیچ نظری برای این پاورپوینت نوشته نشده است.