Centralized Recovery

[mzjahromi]

موضوع: CENTRALIZED RECOVER
ترجمه فصل 6 از کتاب:
CONCURRENCY CONTROL
AND RECOVERY
IN DATABASE SYSTEMS (http://www.barnamenevis.org/forum/showthread.php?t=43667&highlight=Concurrency)
ترجمه: محمد ذوالقدر
مهر ماه 78
اگه خیلی خوب ترجمه نشده ببخشید.

[mzjahromi]

این مطلب راباطرح یک سئوال شروع می کنیم، که چگونه یک تراکنش هنگام بروزیک خطاپردازش می شود. دراین مبحث مانتیجه این کاررابرای DBS(Data base system) مرکزی دنبال می کنیم. اولین کارمااین است که خطاهایی راکه باآنهابرخوردمی کنیم بررسی کنیم. سیستم های کامپیوتری به دلایل گوناگون باخطامواجهی می شوندوغیرممکن است که انتظارداشته باشیم یک DBS ساخته شودکه بتواندکلیه خطاهای ممکن رادرنطربگیرد. ولی یک سیستم خوب بایدبتواندبیشترخطاهای معمولی که وابسته به عوامل انسانی نیست راپوشش دهد.
بیشترخطاهابه خاطربرنامه نویسی غلط یاوروداشتباه اطلاعات است ( ارسال پارامترهای اشتباه به تراکنش). این خطاهابااعمال تکنیکهای مهندسی نرم افزاردربرنامه نویسی وتست تراکنشهایاتوسط مفاهیم ومکانیزمهای امنیت که در DBS ساخته می شودمحدودمی شوند.
بیشتر خطاهاتوسط اپراتوررخ می دهد. به عنوان مثال یک کاربرپشت رابط ممکن است اشتباهادستوری راصادرکندکه باعث ازبین یاآسیب دیدن قسمتی ازDB شودیاموجب راه اندازی مجددسیستم شود. احتمال چنین اشتباهاتی رامی توان بابهترکردن رابط کاربربرای اپراتورهاوکاهش قدرت اپراتورهاکمترکرد. جلوگیری ازچنین خطاهایی درحوزه کارDB Recovery نمی باشد.
بااین فرضهامی توان سه نمونه ازمهمترین خطاهارادر DB مرکزی درنظرگرفت که تحت عنوان خطاهایی تراکنش خطاهایی سیستم وخطاهای رسانه ای مطرح می شوند.
خطاهای تراکنش زمانی اتفاق می افتدکه یک تراکنش Abort می شود. خطاهای سیستم مربوط به واردشدن خسارت یاخراب شدن محتوای حافظه موقت( حافظه اصلی) می شود. به عنوان مثال برای حافظه های نیمه هادی باقطع برق یاخراب شدن سیستم عامل این اتفاق می افتد. ممکن است خطای سیستم عامل باعث خراب شدن کلیه اطلاعات حافظه اصلی نشودولی تعیین کردن اینکه کدام قسمتهاحقیقتاخراب شده است کاربسیاردشواری است. بنابراین مامعمولابدترین حالت رادرنظرمی گیریم وکلیه محتویات حافظه اصلی رادوباره مقداردهی می کنیم. بخاطر خطاهای سیستمی DB بایدازخوددرون حافظه ماندگارمحافظت کند.( البته مسائل مارامجبورمی کندکه قسمت عمده DB رادرون حافظه اصلی قراردهیم.) و خطاهای رسانه ای زمانی رخ می دهدکه قسمتی از حافظه ماندگارازبین برودمانندزمانی که سکتورهایی ازدیسک خراب می شوند. تکنیکهایی که برای غلبه بر خطاهای رسانه ای استفاده می شودتقریباشبیه تکنیکهایی است که برای خطاهای سیستمی استفاده می شود. برای محافظت ازداده هادربرابرخرابی دقسمتهای غیرقابل اعتماد حافظه، کپی دیگری از اطلاعات رانگه داری می کنیم که ممکن است ازنظرظاهری باکپی قبلی متفاوت باشد.
این کپی اضافی درقسمت دیگری از* ذخیره می شودکه فرض می کنیم قابل اعتماداست. مانند حافظه ماندگاردربخش خطاهای سیستمی وقسمت دیگری از حافظه ماندگارمانندیک دیسک ثانویه دربخش خطاهای رسانه ای.
مادراین مبحث روی خطاهای سیستمی متمرکزمی شویم ولی می توان همین تکنیکهابه نمونه های آنهابرای خطاهای رسانه ای گسترش داد.
______________________________________________
امنیت: Integrity
خطاهای تراکنش - Transaction failures
خطاهای سیستمی - System failures
خطاهای رسانه ای - media failures

[mzjahromi]

بیشترتمرکزمادراین مبحث روی DM(Data Manager) منتقل می شود. این DM است که حافظه رادستکاری می کند واین حافظه است که توسط خطاها آسیب می بیند. درحقیقت مانگران خطاهای سیستمی هستیم که محتویات حافظه اصلی ( ونه حافظه ماندگار) راخراب می کنند.
اجازه دهیدنگاهی به مدل یک DBS باتمرکزبرروی بخشی که مارادراین فصل سرگرم خواهدکردبیاندازیم. تراکنش هادستورالعملهای خودرابه مدیر تراکنش (Transaction manager) تقدیم می کنندوپس ازآن به زمانبند(Scheduler) ارسال می شود. زمانبند دستورات read, write, commit,Abort راازمدیر تراکنش دریافت می کند. دستور Abort رابلافاصله می تواندبه مدیر اطلاعات (Data manager) ارسال می کندولی برای دستورات read, write, commit زمانبندبایدتصمیم بگیردکه ممکن است مقداری تاخیربوجودبیایدتا دستورالعمل پذیرفته شودیابرگردانده شود. اگردستورالعمل برگردانده شودزمانبندیک پیام منفی (Negative Acknowledg) به مدیر تراکنش بازمی گرداند. که باعث برگردانده شدن دستور Abort به طرف زمانبندمی شودکه دستور Abort سریعابه مدیرداده هاارسال می شود و درصورتیکه زمانبنددستورالعمل راقبول کندآنرابه مدیرداده هاارسال می کندکه توسط دستکاری کردن حافظه دستورالعمل پردازش می شود. جزئیات دقیق دستکاری حافظه وابسته یه الگوریتم مدیرداده هااست که مهمترین زیربخش این مبحث است. زمانیکه مدیرداده ها پردازش دستورالعمل رابه اتمام رساندپیامی راجهت اطلاع به زمانبند ارسال میکندکه این پیام به مدیر تراکنش منتقل می شود.
علاوه بر Abort و read, write, commit مدیرداده هاممکن است یک دستورrestart نیزدریافت کنداین دستورتوسط یک ماژول خارجی (مانندسیستم عامل ) ارسال می شود.
restart دستوری برای آوردن DB به یک وضعیت ثابت است( پاک کردن اثرات تراکنشهای قطعی نشده واعمال کردن اثرات اعمال نشده تراکنشهای قطعی شده) آخرین مقدارقطعی شده X ، مقدارآخرین نوشتن روی X توسط یک تراکنش قطعی شده است. باتوجه به اینکه تعریف آخرین مقدارقطعی شده خودباشد. باتوجه به تعریفهای فوق هدف از restart این است که DB رابه آخرین وضعیت قطعی شده خودقبل ازوقوع خطا ی سیستمی ببرد.

شکل 1: مدل یک DBS مرکزی
T1 T2 ..... TN
Read, wrute, commit, Abort
Transction
Manager (TM)

Read, wrute, commit, Abort

Scheduler

Reastart
(recovery from system failure)
Read, wrute, commit, Abort

Recovery
Manager (RM)
Read
Write
Fetch
Flush
Cache
Manager (CM )

Cache
2-1) حافظه ماندگار:
مدیرداده هابه دوقسمت تقسیم می شودیک CM(Cache Manager) که حافظه هارابامهارت دستکاری می کندویک RM(Recovery Manager) که دستورات restart و Abort و read, write, commitرا پردازش می کند. CM دستوراتی راجهت خواندن داده ها از حافظه سخت به حافظه موقت وهمچنین تخلیه داده هااز حافظه موقت به حافظه دائم تامین می کندوRM برای اینکه تضمین کند حافظه ماندگارهمیشه حاوی اطلاعاتی است که برای پردازش restart موردنیازاست دستورات تخلیه CM راکنترل می کند.
مافرض می کنیم زمانی که CM یک دستورنوشتن، جهت نوشتن یک قلم داده در حافظه سخت صادرمی کنددستورالعمل نوشتن یابه درستی همه اطلاعات رامی نویسد یا هیچکدام رانمی نویسدوتوسط یک پیغام مشخص می کندکه کدامیک ازدوعمل فوق اتفاق افتاده است. اینگونه عملیات نوشتن راatomic write می گوییم. درصورتیکه عملیات نوشتن Atomic نباشدیک خطای رسانه ای رخ داده است( قسمتی از اطلاعات ولی نه همه رابنویسد). حال فرض می کنیم که خطای رسانه ای اتفاق نیافتد. یعنی همه دستورات نوشتن Atomic هستند.
برای دیسکهای متداول امروزی جهت استفاده به عنوان حافظه ماندگارقطعات داده ها معمولاصفحات باحجم ثابت است . زمانیکه یک بلاک روی دیسک نوشته می شود دوامکان وجوددارد:
روی مقدارقبلی بلاک نوشته می شودووضعیت جدیدتادوباره نویسی بعدی باقی
می ماند یااینکه مقدارجدیدبلاک به طریقی ازبین رفته وهنگام خواندن بعدی نوعی خطاشناخته می شود. شناسایی خطابه صورت نرمال توسط سخت افزاردیسک انجام میشود. مثلااگرتعدادکمی ازاشتباهات بیتی محتویات یک بلاک راخراب کندسخت افزاردیسک خطایی رادرطول checksum شناسایی می کند.
حتی اگرDM از atomic write پشتیبانی کندبازهم برای انواع مختلف داده هانیازبه دقت فراوانی دارد. دراینحالت ممکن استDM دستوراتی برای نوشتن رکوردهای کوتاه
(که هربلاک می تواندشامل چندرکوردباشد) ویارکوردهای طولانی ( که ممکن است چندبلاک باشند) دریافت کند. این گونه داده های قطعه قطعه نیازبه توجه خاصی هنگام طراحی الگوریتم های recovery دارند. مانندداده ها ی منحصربفردی که نمی توانندیکی پس ازدیگری ( برای رکوردهای کوتاه) یابه صورت atomic (برای رکوردهای طولانی) نوشته شوند. دراین مبحث مافرض می کنیم که قطعات داده هاازنظرDM یکسان هستند.
ما Dmهایی ارکه دقیقایک کپی ازهرقلم داده در حافظه ماندگارتهیه می کنندو
DM هایی که بیش ازیک کپی تهیه می کنندراازهم جدامی کنیم. اگرتنهایک کپی موجودباشدآنگاه زمانیکه یک قلم داده به روزرسانی می شودمقدارقبلی خراب می شود. این روش inplace updating نامیده می شودودرصورتیکه بیش ازیک کپی وجودداشته باشدآنگاه CM می تواندیک قلم داده رادر حافظه ماندگارثبت کندبه طوریکه نسخه قبلی آن ازبین نرود. دراینحالت نسخه قبلی راShadowing Copy واین تکنیک راShadowing
می نامند. درروش Shadowing موقعیت اقلام داده نسبت به زمان تغییرمی کند. درنتیجه روش مناسبی برای پیاده سازی این حالت استفاده ازدایرکتوری بایک مدخل برای هرقلم داده است که نام وموقعیت آن در حافظه ماندگاررامشخص می کند. بااستفاده ازروش Shadowing همیشه بیش ازیک دایرکتوری وجودداردکه هردایرکتوری وضعیت مختلفی ازDB رامشخص می کند. درموردروش Shadowing درانتهای بحث توضیح داده می شود.

2-2) مدیر حافظه:
برای اجتناب ازدستیاب به حافظه ماندگاردرهربارپردازش read, write بایدیک کپی ازDB رادر حافظه موقت نگهداری کنیم. برای خواندن یک قلم داده بایدآنراازکپی موجوددر حافظه موقت برداریم وبرای نوشتن یک قلم داده بایدمقدارآنراهم درون حافظه موقت وهم درون حافظه دائم ثبت کنیم کپی موجوددر حافظه ماندگاربرای recovery پس ازبروز خطای سیستمی موردنیازاست. ازآنجاکه دسترسی به حافظه ماندگارکندترازدسترسی به حافظه اصلی است این مورددربیشترحالات موجب بالارفتن کارایی سیستم می شود.
متاسفانه نگهداری یک کپی کامل ازDB در حافظه اصلی به خاطرحجم زیادDB وبالابودن نسبی قیمت حافظه اصلی امکان پذیرنیست. بنابراین بایدسعی درنگهداری کمترازکلDB در حافظه اصلی کنیم. این کار با استفاده از تکنیکی به نام Caching یا Buffering انجام می شود. بخشی از حافظه اصلی که Cache نامیده می شود جهت نگهداری قسمتی از DB درنظرگرفته می شود Cache شامل مجموعه ای از Slot ها است که هرکدام قادر به نگهداری Slot های یک قلم داده هستند. در هرزمان زیر مجموعه ای از قالام داده درون Cache Slot قرار دارند به اضافه اینکه یک موقعیت همیشگی در حافظه ماندگار هم دارند یک Slot از Cache شامل متغیری برای داده ای است که درآن ذخیره شده است و یک بیت dirty که یک است اگر و فقط اگر مقدار داده ای که درون Slot ذخیره شده است با مقدار آن درون حافظه اصلی متفاوت باشد (خواهیم دید که چگونه این مورد اتفاق می افتد) اگر بیت dirty یک باشد می گوئیم Slot ، dirty است. همچنین یک Cache directory وجود دارد که نام هر قلم داده در Cache وشماره Slot را به ما می دهد.

شکل 2: ساختار Cache

Slot Number Data Item Name Data Item Value Dirty Bit Slot Number
2 x October 12 1 1
1 y 3.1416 0 2
. .
. .
. .

کنترل ترافیک اقلام داده درون و بیرون Cache توسط (Cache manager)CM با استفاده از دو عملیات fetch و klush انجام می شود. fetch یک Slot از Cache با نام C را به عنوان پارامتر گرفته اگر dirty نباشد هیچ کاری را انجام نمی دهند ولی در صورت dirty بودن C آن را درون موقعیت خود در حافظه سخت قرار می دهد و بیت dirty را پاک
می کند. flush کنترل را تا کامل شدن به روز رسانی C در حافظه سخت، به صدازننده خود باز نمی گرداند و دستور العمل fetch کارهای زیر را انجام می دهد:
1- یک Slot خالی از Cache که C نامیده می شود را انتخاب می کند. در صورتیکه کلیه Slot ها اشغال باشد یک Slot را گرفته آنرا flush می کند و به عنوان یک Slot خالی مورد استفاده قرار می دهد.
2- مقدار x را از حافظه سخت به درون C کپی کرده و بیت dirty را پاک می کند.
3- Cache directory را به روز رسانی می کند که مشخص کند x درون C قرار دارد.
درمرحله اول اگر Slot با نام C مشغول باشد می گوئیم x جایگزین داده ای که درون c بوده شده است. تعدادی از استراتژی های جایگزینی شناخته شده (Least recontly used)LRU و FIFO می باشند. LRU داده ای را مشخص می کند که کمرین fetch درمورد آن صورت گرفته است.
برای خواندن یک قلم داده با نام x، در صورتیکه درون Cache نباشد CM آنرا fetch می کند و برای نوشتن x ، CM یک Slot خالی را درون Cache رزرو می کند (در صورتیکه x درون Cache نباشد) و مقدار جدید را در آن قرار داده بیت dirty را یک
می کند. همچنین مقدار جدید را در همین زمان یا بعداً (با تصمیم گیری RM ) درون حافظه جانبی قرار می دهد.
RM برای جایگزین کردن یک Slot باید اطمینان پیدا کند که این Slot درحال استفاده توسط یک دستورالعمل نیست برای این کار دو راه pin و unpin را ارائه می دهد. دستورالعمل pine به Cm می گوید که محتویات C را تخلیه نکند. درحالیکه unpin(c) یک Slot که قبلاً توسط دستور pin قفل شده بود را برای تخلیه آزاد می کند. بنابراین CM هیچگاه یک Slot را که توسط pin قفل شده تخلیه نمی کند.

[mzjahromi]

3) مدیر Recovery :
رابط RM پنج تابع را معرفی می کند:
1- RM-read (ti,x) که مقدار x راتوسط تراکنش Ti می خواند.
2- RM-write (Ti,x,v) که مقدار v را توسط تراکنش Ti درون x می ریزد.
3- RM-commit (ti) که تراکنش Ti رابه مرحله abort می برد.
5- restart : که DB رابه آخرین وضعیت قطعی خود قبل از وقوع خطا می برد.
درمطالب بعدی زمانیکه از مقدار بعدی یک قلم داده x نسبت به اجرای یک تراکنش صحبت می شود منظور مقداری است که توسط آن تراکنش درون x نوشته می شود و زمانیکه از مقدار قبلی صخبت می شود منظور مقداری است که قبل از اجرای تراکنش درون آن متغیر وجود داشته است.

3-1) یادداشت برداری:
فرض کنید RM از روش in place updating استفاده می کند در نتیجه هر قلم داده یک موقعیت ثابت و واحد درون حافظه جانبی دارد. بطور ایده آل DB باید برای هر قلم داده x شامل آخرین مقدار نوشته شده درون x توسط یک تراکنش قطعی شده باشد. عملاً دوفاکتور مانع این ایده آل می شود: به روز رسانی متناوب توسط تراکنشهایی که مقداری زمان برای تمام شدن نیاز دارند (تراکنشهای با عمر طولانی) و تهیه بافر از اقلام داده درون Cache. بنابراین DB ماندگار ممکن است شامل مقادیری باشد که توسط تراکنشهای قطعی نشده نوشته شده اند یا شامل مقادیری که توسط تراکنشهای قطعی شده نوشته شده اند نباشد.
در پی یک خطای سشیستمی restart باید قادر باشد حالت DB رابه حالت قطعی تبدیل کند برای انجام این کار فقط می تواند به اطلاعات موجود در حافظه ماندگار اعتماد کند. به همین دلیل RM معمولاً اطلاعات را علاوه بر DB ماندگار، درون حافظه ماندگار هم ذخیره می کند. log نمونه ای از این گونه اطلاعات است.
تصور کنید یک log تاریخچه ای از اجراهاست. یک log فیزیکی نمونه ای از log است که شامل اطلاعاتی درباره مقادیر اقلام داده ای است که توسط تراکنشها نوشته شده اند مانند (stable Data Base) SDB ساختار و محتویات log به شدت وابسته به الگوریتمهای RM است در هر صورت می توانیم تصور کنیم که یک log (فیزیکی) شامل مدخلهائی به فرم [Ti, x,v] است که مقدار v را که تراکنش Ti درون x نوشته است را مشخص می کند.
ساختمان داده ای که برای log استفاده می شود باید restart را قادر سازد تا برای هر x تصمیم بگیرد که کدام مدخل از log شامل آخرین مقدار قطعی x است. بنابراین به صورت منظم باید write های انجام شده را مشخص کند. راه مناسبی برای ثبت این اطلاعات در نظرگرفتن یک ساختار ترتیبی برای log است. بنابراین فرض می کنیم که [Ti, x,v] درون log قبل از [Ti, x,v] است اگر Wi(x) قبل از Wj(x) اجرا شده باشد.
بجای اینکه log شامی متغیرهایی که درون DB نوشته شده اند باشد می تواند شامل توضیحاتی درمورد دستورالعمل های سطح بالاتر باشد که این روش را Logical logging می نامیم. به عنوان مثال یک مدخل از log می تواند بگوید که رکورد r درون فایل F درج شده است. یا به عنوان مثالی دیگر اگرداده x مقدار پنج را در خود نگهداری کند و تراکنش T به آن دو تا اضافه کند در این صورت در Physical logging مقدار هفت درون log قرار می گیرد و درمورد Logical logging مقدار t2 درون log قرار می گیرد. با ثبت دستورالعملهای سطح بالاتر کمترین مدخلهای log مورد نیاز است. کوتاه کردن log به این روش باعث افزایش کارائی RM می شود ولی هزینه ای را برای تفسیر مدخلهای log هنگام بروز خطای سیستمی و اجرای عملیات restart ایجاد می کند. دراین مبحث زمانیکه از log صحبت می شود منظور log فیزیکی است.
RM علاوه بر اطلاعات فوق یک یا چند لیست از تراکنشهای فعال قطعی یا متوقف شده را نگهداری کند. این لیستها معمولاً در قسمتی از log ذخیره می شوند.

3) خنثی کردن و اجرای مجدد:
زمانهایی وجود دارد که RM باید به شدت مواظب تخلیه داده ها توسط Cm درون SDB باشد. دراین تخلیه ها نوشتن درون log و SDB باید هماهنگ باشد. بخاطر اینکه restart همیشه بتواند اطلاعات مورد نیاز خود را درون حافظه ماندگار بیابد. برای این کار RM باید قوانین را هنگام تخلیه داده ها رعایت کند. این موارد طبقه بندی ما را در این بخش تشکیل می دهد (الگوریتمهای RM ) .
یک RM نیاز به nndo دارد اگر اجازه دهد نتیجه تراکنشهای قطعی نشده درون SDB ذخیره شود. دراین لحظه اگر یک خطای سیستمی روی دهد هنگام recovery ، SDB شامل اثرات این تراکنش قطعی نشده است. این اثرات باید توسط restart هنگام بازگرداندن SDB به حالت قطعی خود خنثی شوند.
یک RM نیاز به redo دارد اگر اجازه دهد یک تراکنش قطعی شود قبل از آنکه کلیه مقادیر نوشته شده توسط آن تراکنش، روی SDB اعمال شود دراین لحظه اگر یک خطای سیستمی روی دهد هنگام recovery ، SDB شامل اثرات این تراکنشهای قطعی شده نیست. این عملیات باید دوباره انجام شوند تا SDB به حالت قطعی خود باز گردد.
مشاهده می شود که اصطلاحات «نیاز به undo » و «نیاز به Redo» راتنها برای خطاهای سیستمی استفاده کردیم. یعنی زمانیکه می گوئیم RM نیاز به redo دارد واقعاً این منظور را داریم که restart برای پوشش دهی خطاهای سیستمی نیاز به redo دارد.
با تنظیم ترتیب تعهدات یک تراکنش نسبت به نوشتن متغیرهایش درون SDB ، RM می تواند به undo یا Redo نیاز داشته باشد. بنابراین می توانیم الگوریتمهای RM رابه چهار دسته تقسیم کنیم:
1) آنهایی که هم به undo و هم به Redo نیاز دارند.
2) آنهایی که نیاز به undo دارند ولی نیاز به Redo ندارند.
3) آنهائی که نیاز به undo ندارند ولی نیاز به Redo دارند.
4) آنهایی که نه به Redo و نه به undo نیاز دارند.
درادامه این مبحث هرچهارمورد فوق بررسی می شود.
برای اینکه یک RM بتواند از undo یا Redo استفاده کند باید قوانین زیر را رعایت کند:
قانون undo : اگر مکان x درون SDB شامل آخرین مقدار قطعی x باشد آنگاه این مقدار باید قبل از جایگزین شدن توسط یک مقدار قطعی نشده، درون حافظه ماندگار نوشته شود.
قانون Redo : قبل از اینکه یک تراکتش بتواند قطعی شود مقادیری که برای هر قلم داده نوشته است باید درون حافظه ماندگار باشند (درون SDB یا درون log)
قوانین undo و Redo اطمینان می دهند که آخرین مقدار قطعی شده هر قلم داده همیشه درون حافظه ماندگار وجود دارد. قانون undo تضمین می دهد که آخرین مقدار قطعی x قبل از جایگزین شدن توسط یک مقدار قطعی نشده، درون حافظه ماندگارذخیره شده است و قانون Redo تضمین می کند که یک متغیر که توسط یک تراکنش قطعی شده تولید شده است درون حافظه ماندگار وجود دارد مشاهده می شود. یک RM که نیاز به undo (یا Redo) ندارد باید قوانین undo (یا Redo) را رعایت کند.

3-3) مجموعه بدون استفاده:
اگرچه مقدار حافظه جانبی معمولاً زیاد است اما باز هم از نظر حجم محدود است. همچنین RM باید اطلاعاتی که درآن نگهداری می کند را محدود کند. واضح است که حجم SDB وابسته به تعداد اقلام داده ای است که درخود نگهداری می کند. برای اعمال قوانین undo و Redo ، RM باید اطلاعات درج کردن را درون log نگهداری کند. برای محدود کردن حجم log باید زمانیکه مطمئن شد restart به اطلاعات درون log نیاز ندارد فضای مورد استفاده توسط آنها را آزاد کند. اینگونه اطلاعات غیر ضروری را garbage collection می گویند.
برای رکوردهایی به فرم [Ti,x,v] درون log، قوانین زیر به دقت بیان می کنند که اطلاعات چه زمانی می توانند از Log خارج شوند.

[mzjahromi]

مدخل [Ti,x,v] می تواند از درون Log برداشته شود اگر 1) Ti متوقف (abort) شده باشد 2) Ti قطعی شده باشدولی سایر تراکنشهای قطعی شده پس از Ti درون x نوشته باشند (بنابراین V آخرین مقدار قطعی شده x تخواهد بود)
درحالت اول زمانیکه Ti متوقف می شود برای ما مهم نیست که چه چیزی نوشته بود بنایراین کلیه نوشته های آن خنثی خواهد شد و درحالت دوم زمانیکه مقدار قطعی جدیدی درون x نوشته می شود مقدار قطعی قبلی می تواند ازاد شود چون تنها آخرین مقدار قطعی برای recovery لازم است. در هر دو حالت برداشتن [Ti,x,v] از Log هیچگاه توانائی restart در شناسائی آخرین مقدار قطعی x را تحت تأثیر قرار نمی دهد. بنابراین اگر V آخرین مقدار قطعی شده x باشد حتی اگر درون SDB ذخیره شده باشد باز هم [Ti,x,v] نمی تواند از Log برداشته شود. اگر Ti متعاقباً درون x در SDB نوشت و سپس abort شد آنگاه [Ti,x,v] برای عملیات undo مربوط به نوشتن Ti لازم است.
اگر RM نیاز به Undo نداشته باشد آنگاه نوشتن مربوط به تراکنش Ti نمی تواند قبل از اینکه Ti قطعی شود درون SDB نوشته شود. لذا این سناریو اتفاق نمی افتد. بنابراین
می توانیم جالت سومی را به قوانین garbage allocation اضافه کنیم.
3) [Ti,x,v] می تواند از Log برداشته شود اگر RM نیازی به Undo نداشته باشد.
قوانین فوق نزدیک ترین زمانیکه یک مدخل از Log می تواند حذف شود را مشخص می کند با توجه به مطالب قبلی RM تعدادی از لیستهای فعال قطعی و متوقف شده را درون حافظه ماندگار نگهداری می کند. حجم لیستهای فعال توسط تعداد تراکنشهای درحال پردازش در هر لحظه مشخص می شود که احتمالاً یک عدد قابل مدیریت است ولی حجم لیستهای فعال ومتوقف شده نیز باید محدود شود. این غیر ممکن است که کلیه تراکنشهایی که از زمان تولید سیستم قطعی یا متوقف شده اند را نگهداری کنیم. RM تنها به اطلاعاتی درمورد تراکنشهایی که از زمان تولید سیستم قطعی یا متوقف شده اند را نگهداری کنیم. RM تنها به اطلاعاتی درمورد تراکنشهایی که جدیداً قطعی یا متوقف شده اند نیاز دارد که این مورد به جزئیات الگوریتمهای RM وابسته است.


3-4) قابلیت تکرار در روال restart :
هنگام اجرای دستورات Commit , abort و read , write دستورالعمل restart می تواند هریک از آنها را متوقف کند چون یک خطای سیستمی هر لحظه ممکن است رخ بدهد. حتی restart می تواند خود رانیز متوقف کند. اینکه restart می تواند خود را متوقف کند نیاز به یک رهبر ی مهم دیگر دارد. restart باید ideempotence باشد. این بدین معناست که اگر . restart درهر لحظه متوقف شد و اجرای خود را دوباره از ابتدا شروع کذد نتیجه ای رابدهد که اگر بار اول به درستی اجرا شده بود می داد. مطلب گفته شده مطلقاً بدین معناست که هرتوالی از اجرای غیرکامل . restart که به دنبال آن یک اجرای کامل از . restart باشد باید همان اثراتی را داشته باشد که اگر تنهار یک بار . restart به طور کانمل اجرا شد می داشت.
یک مفهوم عملی این است که . restart باید مطمئن شود که حافظه ماندگار همیشه درحالتی است که اجرای جدید . restart می تواند به درستی تفسیر شود. این باعث می شود در مورد متغیرهایی که . restart درون حافظه ماندگار می نویسد و ترتیب نوشتن آنها مواظب باشیم.
در مباحث بعدی چها رروش مختلف از پیاده سازی RM که قبلاً داشتیم را شرح
می دهیم:
read/undo و read/no undo و no undo/ read و no undo/read . در هر چهار الگوریتم RM که معرفی می شود پنج پردازه را بررسی می کنیم: RM-read و RM-write و RM- commit و RM-Abort و . restart.
در بررسی این روشها هدف این است که مشخص کنیم RM چه کاری را انجام
می دهد.

[mzjahromi]

دراین بخش الگوریتمی از RM را شرح می دهیم که هم به Undo و هم به redo نیاز دارد. این یکی از پیچیده ترین چهارنوع الگوریتم است. دراین روش از Cache می توان به بهترین نحو استفاده کرد. این الگوریتم دو هدف عمده را دنبال می کند: 1- RM که از read/undo استفاده می کند تا زمانیکه مجبور نباشد یک Slot از Cach را تخلیه نمی کند در نتیجه I/O بسیار کاهش می یابد. درحالیکه یک الگوریتم noredo باید بارها یک Slot را تخلیه کند تا مطمئن شود قبل از قطعی شدن یک تراکنش تغییرات آن روی SDB اعمال شده است.
2- اجازه دهد که یک CM که از inplace updating استفاده می کند یک dirty slot را که توسط یک تراکنش قطعی نشده ایجاد شده است تخلیه کند. یک الگوریتم no undo قادر به انجام چنین کاری نیست.
باتوجه به موارد فوق الگوریتم بالاترین کارایی را در طول اجرای نرمال دستورالعملها دارد. درمقابل، کارائی پائینی در هنگام بروز خطا نسبت به سایر الگوریتمها دارد. فرض کنید تراکنش Ti مقدار v رادرون x می نویسد دراین الگوریتم در صورتیکه x درون بافر نباشد آنرا fetch می کند و مقدار v را درون Log و Slot مربوط به x برای آزاد سازی C برای یک fetch دیگرداشته باشد.
ولی ثبت کردن یک Update درون SDB وظیفه CM است نه RM اگر Cm مقدار C را جایگزین کند وپس از آن Ti ، abort شود یا قبل از قطعی شدن Ti خطائی رخ دهد آنگاه به undo نیاز است. از طرف دیگر اگر پس از قطعی شدن Ti وقبل از اینکه CM مقدار C رابنویسد سیستم با خطا مواجه شود آنگاه به redo نیاز است.
قبل از اینکه به مرحله بعدی پیش برویم فرض می کنیم داده هایی که RM از آنها پشتیبانی می کند واحدهایی atomic از انتقال به درون حافظه ماندگار هستند و همچنین یک Log فیزیکی، که لفیسیت مرتب شده ای از رکوردهایی به فرم [Ti,x,v] است با قوانین garbage collection داریم و مقدار اولیه هر قلم داده قبل از اینکه تراکنشها پردازش شوند درون Logنوشته می شود.
در زیر پنج پردازنده RM رادراین الگوریتم بررسی می کنیم.

[Ti,x,v] Read - Write :
1- اضافه کردن Ti به لیست تراکنشهای فعال در صورتیکه آنجا نیست.
2- fetch کردن x در صورتیکه درون Cache قرار ندارند.
3- اضافه کردن [Ti,x,v] به Log
4- نوشتن v درون Slot مربوط به x
5- اطلاع دادن پردازش [Ti,x,v] RM-Write به زمانبند.

[Ti,x,v] RM- read :
1- fetch کردن x در صورتیکه درون Cache قرار ندارند.
2- برگرداندن مقدار موجود در Slot مربوط به x

RM= Commit (Ti) :
1- اضافه کردن Ti بع لیست تراکنشهای قطعی شده
2- اطلاع دادن قطعی شدن Ti به زمانبند.
3- حذف کردن Ti از لیست فعال

RM- abort (ti) :
1- برای هر قلم داده x که توسط Ti به روز رسانی شده است:
الف) اگر x درون بافر نیست یک Slot رابرای آن در نظربگیر.
ب) مقدار قبلی x را درون Slot مربوطه کپی کن
2- Ti رابه لیست تراکنشهای abort شده اضافه کن
3- abort شدن Ti را به زمانبند اطلاع بده
4- Tiرا از لیست تراکنشهای فعال حذف کن

restart :
1- کلیه اطلاعات درون بافر را دور بریز
2- redone={} و undone= {}
3- با آخرین مدخل از Log شروع کن و به عقب برگرد تا به ابتدا برسی اعمال زیرین را تازمانیکه undone | redone برابر مجموعه تمامی اقلام داده درون DB شود یا اینکه هیچ مدخلی از Log برای بررسی وجود نداشته باشد تکرار کن. برای هر مدخل [Ti,x,v] اگر undone| redone X= آنگاه:
* اگر xدرون بافر نیست یه Slot رابرای آن در نظربگیر.
* اگر Ti درون لیست تراکنشهای قطعی شده است V را درون Slot مربوط به x کپی کن undone= redone
* و الا ( Ti فقط درون لیست abort یا فعال قرار دارد) مقدار قبلی x نسبت به اجرای Ti رادرون Slot مربوطه قرار بده و {x} U undone = undone
4- برای هر تراکنش Ti که درون لیست قطعی قرار دارد اگر Ti درون لیست فعال هم قرار دارد آنرا از لیست فعال حذف کن.
5- اتمام عمل restart رابه زمانبند اطلاع بده.

توضیحات:
(مرحله چهار از RM-Write ) : برای اجتناب از توضیحات تکراری مادر این مبحث فرض می کنیم زمانیکه در یک Slot از Cache نشوته می شود (بنابراین مقدار آن با مقدار موجود در SDB متفاوت است) RM بیت dirty آن را یک می کند و همچنین فرض می کنیم که RM قبل از خواندن یا نوشتن یک Slot ، آن را Pin می کند وسپس Unpin می کند بخاطر اینکه مطمئن شود دستورات نوشتن atomic هستند.
(مرحله یک از RM-Commit ) این فعالیت برای اضافه کردن Ti به لیست تراکنشهای قطعی شده است و مشخص می کند که Ti قطعی شده است. اگر یک خط قبل از اینکه این مراحل کامل شود رخ دهد Ti به عنوان یک تراکنش قطعی نشده شناخته می شود و الا حتی اگر سایر مراحل RM-Commit هم کامل نشود Ti به عنوان یک تراکنش قطعی شده شناخته می شود.
(مرحله یک از RM-abort ) دراین مرحله مقدار قبلی هر قلم داده تنها درون بافر قرار می گیرد و CM زمانیکه آنرا جایگزین می کند به درون SDB باز می گرداند.
(مرحله یک از restart ) یک خطای سیستمی محتویات حافظه موقت و درنتیجه بافر راخراب می کند. بنابراین زمانیکه restart درخواست مقادیری از بافر می کند نمی تواند به آنها اعتماد کند.
(مرحله دو از restart ) redone و undone متغیرهایی محلی برای restart هستند که مشخص می کنند کدام اقلام داده توسط یک فعالیت Undo یا Redo به آخرین وضعیت قطعی خود رسیده اند.
(مرحله سه از restart ) دراین مرحله مقدار قطعی متغیر x تنها درون بافر باز گردانیده شده است. CM هنگام جایگزینی آنرا درون SDB باز می گرداند. دراین مرحله مقدار قبلی x نسبت به اجرای Ti را می توان درون Log یافت.

[mzjahromi]

4-1) قوانین redo و Undo :
این الگوریتم قانون Undo رارعایت می کند . فرض کنید موقعیت x درون SDB شامل آخرین مقدار قطعی V است که توسط تراکنش Ti نوشته شده است. زمانیکه Ti درون x نوشت آنگاه [Ti,x,v] رادرون Log قرار می دهد (مرحله دو از RM-Write ) با توجه به قوانین garbage colleotion زمانیکه v آخرین مقدار قطعی x است این رکورد نمی تواند از درون Log برداشته شود. درنیتجه قانون Undo رعایت می شود.
همچنین قوانین redo نیز رعایت می شود چون کلیه به روز رسانی ها قبل از اینکه تراکنش قطعی شود درون Log قرار می گیرند علاوه براینکه درون SDB نیز ثبت می شوند. با قوانین garbage collection آنها باید تا قطعی شدن تراکنش درون Log باقی بمانند.
از آنجا که الگوریتم قوانین redo و Undo را ارضاء می کند restart همیشه می تواند اطلاعاتی که برای بازگرداندن آخرین مقدار قطعی هر قلم داده نیاز دارد را درون حافظه ماندگار بیابد . (مرحله سه از restart ) همچنین restart ، idempotence نیز است چون در صورتیکه توسط یک خطای سیستمی متوقف شود ودوباره از اول اجرا شود به روز رسانی هائی که درمرحله سوم redo و Undo می شوند همانطوری خواهند بود که اگر اجرای اول با موفقیت پایان پذیرفته بود و متوقف نشده بود. چون همیشه restart مقدار بلی یا بعدی یک قلم داده را بدون توجه به مقدار فعلی اش جایگزین می کند.

4-2) نقطه بررسی:
روال restart تنها برای بررسی رکوردهائی طرح شده است که درون Log قرار دارند. البته بجز آنهایی که به garbage collection تبدیل شده اند. این هنوز تعداد زیادی از رکورد ها است دراکثر مواقع بیشتر اقلام داده درون SDB شامل آخرین مقدار قطعی شان در لحظه بروز خطا هستند و restart کاری بیش از آمچه لازم است انجام می دهد. این بازده پائین restart پیامد مهمی است چون پس از یک خطای سیستمی DBS تا اتمام restart ، جهت استفاده کاربرها آزاد نمی شود.
این مشکل با استفاده از Check pointing حل می شود. در روش عمومی Check pointing عملی است که حین اجرای دستورالعملها اطلاعاتی را درون حافظه ماندگار ثبت می کند تا کار restart را پس از بروز خطا کاهش دهد. این کار با استفاده از دونوع بروز رسانی انجام می شود:
1) تنظیم Log و لیستهای قطعی و abort برای مشخص کردن اینکه کدامیک از به روز رسانی ها هم اکنون ثبت یا خنثی شده اند.
2) نوشتن مقدار قبلی به روز رسانی های abort شده یا مقدار بعدی به روز رسانی های قطعی شده درون SDB .
مرحله اول مشخص می کند که کدامیک از به روز رسانی ها نیاز به اجرای مجدد یا خنثی شدن ندارد و درمرحله دوم کارهائی که restart باید انجام دهد را توسط اعمالی که در طول Check pointing انجام می شود کاهش می دهد. مرحله اول برای کلیه انواع Check pointing لازم و ضروری است و لی مرحله دوم اختیاری است.
یک روش ساده این است که هر از چندی پردازش تراکنشها را متوقف کنیم و منتظر بمانیم که کلیه تراکنشهای فعال، قطعی یا abort شوند کلیه dirty slot ها را تخلیه کنیم و انتهای Log را علامتگذاری کنیم که تعیین کند آخرین Check pointing تاآتجا انجام شده است این روش Commit consistent check pointing نامیده می شود. دراین روش روال restart از انتهای Log شروع می کند وبررسی خود را به صورت عقب گرد انجام می دهد و عملیات redo و Undo را برای مدخلهای درون Log انجام می دهد تا زمانیکه به آخرین Check pointing برسد. همچنین ممکن است برای برگرداندن مقادیر قبلی اقلام داده به رکورهایی قبل از Check pointing نیز نیاز داشته باشد مانند مقادیر قبلی داده هایی که پس از آخرین Check pointing به روز رسانی شده اند و تراکنش آنها قطعی نشده است.
مهمترین مشکل در روال Check pointing کارائی است.. هنگام عملیت Check pointing پردازش ترامنشها متوقف می وشد و کاربران بایدتا اتمام عملیات Check pointing منتظر بمانند. بنابراین کاربرها باید زمان زیادی را تحمل کنند تا تراکنشهای فعال کامل شوند و بافر تخلیه شود. مورد اول را می توان با روش زیر که Cache consistent check pointing نامیده می شود اصلاح کرد.
دراین روش روال Check point از RM می خواهد که در طول اجرای دستورالعملها، پردازش را متوقف کند (تراکنشهای فعال را در یک حالت بلاکه رها کند) و کلیه dirty slot ها را تخلیه کند و رکورد Check point را در انتهای Log قرار دهد. حالا restart چه کاری باید انجام دهد؟ بافرض اینکه این روش استفاده شده است کلیه به روز رسانی های تراکنشهای قطعی شده که قبل از آخرین Check point رخ داده است حین آن Check point درون SDB قرار گرفته اند و نیاز به redo ندارند. به طور مشابه کلیه تراکنشهایی که قبل از آخرین Check point ، abort شده اند نیازی به Undo ندارند. تنها تراکنشهایی که قبل از آخرین Check point، abort شده اند نیازی به Undo ندارند. تنها تراکشنهایی که درون لیست فعال قرار دارند همچنین آنهایی که درون لیست قطعی قرار دارند و پس از آخرین عملیات Check pointانجام شده اند باید درنظرگرفته شوند و نیاز به خنثی کردن اثرات تراکنشهایی است که در لیست فعال قرار دارند (ولی قطعی تشده اند) یا در لیست abort قرار دارند وئ پس از آخرین نشانگذاری Check point اعمال شده اند.
این روش هنوز هم تراکنشها را هنگام تخلیه بافر به تأخیر می اندازد. این تأخیر را با استفاده از روش زیر که Check point fuzzy نامیده می شود کاهش می دهیم. دراین روش بجای تخلیه کلیه dirty slot ها تنها آنهائی را تخلیه می کنیم که درعملیات Check point قبلی تخلیه نشده اند.
هدف این است که CM در زمان اجرا عملیان جایگزینی برای Slot هایی که قبل از عملیات Check point قبلی dirty بوده اند را انجام دهد بنابراین Check point لازم نیست تعداد زیادی تخلیه را انجام دهد و درنتیجه تراکنشهای درحال اجرا تأخیر زیادی را حس نخواهد کرد. این روش تضمین می کند که در هر لحظه کلیه به روز رسانی های تراکنشهای قطعی شده ای که قبل از Check point ما قبل آخر انجام شده اند در طی آخرین عملیات Check point بر روی ٍ]قا اعمال شده اند به طور مشابه کلیه به روز رسانی هائی که تراکنشهای آنها قبل از Check point ما قبل آخر abort شده اند خنثی گشته اند.
با توجه به مطالب فوق پس بروز یک خطای سیستمی هنگام restart تنها تراکنشهایی که اسامی آنها درست قطعی وجود دارد و پس از علامت Check point ما قبل آخر درون Log قرار گرفته اند را redo می کند و اثرات تراکنشهایی را خنثی می کند که در لیست فعال قرار گرفته اند یا بعد از علامت Check point ماقبل آخر درون لیست تراکنشهای abort شده ثبت شده اند. الگوریتم Check point و restart که از این استراتژی استفاده
می کنند در بخش بعد با جزئیات بررسی می شوند.

[mzjahromi]

4-3) نمونه ای از پیاده سازی Undo / redo :
یکی از مشکلات الگوریتم Undo / redo این است که مقادیر بعدی در صورتیکه اقلام داده صفحاتی از فایل باشند می توانند حافظه زیادی را مصرف کنند آنگاه در هر به روز رسانی بر روی یک صفحه، یک صفحه به اطلاعات Log اضافه می شود که شامل آدرس صفحه و مقداری است که تراکنش روی آن نوشته است. این موارد مقدار زیادی I/O راتولید می کنند که به شدت کارائی سیستم را پائین می آورد و مقدار زیادی از فضارا برای Log مصرف می کند و GARBAGE COLLECTION را به میزان زیادی افزایش
می دهد.
این مشکلات مخصوصاً زمانی رنج آور است که بیشتر به روز رسانی ها تنها بخش کوچکی از یک قلم داده را تغییر دهند. اگر اقلام داده به صورت صفحاتی باشند آنگاه یک به روز رسانی تنها ممکن است فیلدهای کمی از ان صفحه را تغییر دهند. این مورد
می تواندبا قرار دادن تنها بخشی از داده ها درون Log بر طرف شود. به عنوان مثال قسمتهایی از یک قلم داده که واقعاً تغییر کرده است درون Log قرار گیرد. اکنون یک رکورد از Log تنها نیاز به افست و طول بخشی از یک قلم داده که تغییر کرده است دارد.
الگوریتمی که از این پس توضیح داده می شود تنها قسمتی از داده ها رادرون Log قرار می دهد و Check point puzzy استفاده می کند. ماآنرا item logging algortin partial data می نامیم.
الگوریتم لیست تراکنشهای فعال، قطعی و abort شده را درون Log که یک فایل ترتیبی است نگهداری م یکند باتوجه به اینکه قسمتهایی از داده ها که تغییر می کنند درون Log قرار می گیرند هر مدخل از Log ممکن است کوچکتر از یک قلم داده باشد.
باتوجه به مطالب فوق Log دارای چهارنمونه رکورد متفاوت است که هرکدام از رکوردها دارای محتویات زیر است:
رکورد به روز رسانی: این نمونه از رکوردها یک Write از یک تراکنش راتوضیح می دهند که شامل اطلاعات زیر است:
- نام تراکنشی که باعث نوشتن شده است.
- افست و طول بخشی از داده ها که به روز رسانی شده اند.
- - مقدار قبلی داده ای که به روز رسانی شده است.
- مقدار جدید بخشی که به روز رسانی شده است.
- یک اشاره گر به Lsn رکورد به روز رسانی شده قبلی از همان تراکنش ( Null برای اولین به روز رسانی) لازم به ذکر است که Lsn یک رکورد (Log sequence number) عبارتست از آدرس رکورد درون Log و بزرگتر بودن Lsn یک رکورد از دیگری به این معناست که آن رکورد زودتر از دیگری درون Log قرارگرفته است چون رکوردی است که درانتهای Log قرار می گیرد بزرگترین Lsn را دارد.
رکورد به روز رسانی در مرحله سه از Rm- write درون Log قرار می گیرد.
2- رکورد قطعی: این نمونه از رکوردها می گویند که یک تراکنش قطعی شده و واقعاً شامل نام تراکنش هستند این وع رکورد توسط مرحله یک از RM-commit به Log پیوست می شود.
3- رکورد abort : این نوع رکورد می گوید که یک تراکنش abort شده و شامل نام تراکنش است و توسط مرحله دو از RM-abort به Log پیوست می شود.
رکرود Check point : این نمونه از رکگوردها کامل شدن یک Check point راتوضیح می دهد و شال اطلاعات زیر است:
- لیستی از تراکنشهای فعال در زمان Check point
- لیستی از اقلام داده ای که درون dirty slot ها بوده اند به همراه LSN مربوط به این Slot ها در زمان وقوع Check point
LSN فیلد اضافه ای بر اطلاعات است که به هر Slot پیوست می کنیم و نشان دهنده آن رکورد به روز رسانی است که به آن Slot را به روز رسانی کرده است.
رکورد Check point توسط روال Check point به صورت زیر وارد Log می شود.
1- متوقف کردن RM از پردازش هرنوع دستور العمل خواندن و نوشتن و قطعی شدن و abort و منتشر ماندن برای پردازش کلیه دستور العملهای درحال اجرا (دستور العملهای atomic نه تراکنشها)
2- تخلیه کردن کلیه Slot های dirty در صورتیکه حین Check point قبلی تخلیه نشده اند. برای این کار بافر را بررسی می کند و dirty slot هائی که LSN آنها کوچکتر از LSN مربوط به رکورد Check point قبلی است را تخلیه می کند.
3- ایجاد یک رکورد Check point شامل اطلاعات مناسب
4- اطلاع دادن پردازش Check point به RM تابه پردازش دستورالعملها ادامه دهد. روال Check point توسط RM بطور متناوب به روز رسانی وارد Log شد صدابزند. افزایش فرکانس Check point باعث کاهش کار restart و درنتیجه کاهش زمان بازگردی پس از وقوع یک خطای سیستمی می شود.

[mzjahromi]

4-4) روال restart :
روال restart محتویات Log را با دو بررسی پردازش می کند. یک بررسی عقبگرد درهنگام خنثی کردن به روز رسانی تراکنشهای قطعی نشده ودرمقابل یک بررسی پیش رونده هنگام انجام دوباره به روز رسانیهای تراکنشهای قطعی شده.
بررسی عقبگرد از انتهای Log شروع می شود. در طول این بررسی restart لیستی از تراکنشهای قطعی و abort شده را می سازد که ما آنها را Cl و Al می نامیم. هنگامیکه یک رکورد قطعی یا یک رکورد abort را می خواند تراکنش رابه لیست مناسب اضافه می کند زمانیکه یک رکورد به روز رسانی مربوط به همان تراکنش Ti برای داده x می خواند مراحل زیر را اجرا می کند:
1- اگر Ti درون Cl وجود دارد به روز رسانی آن را در نظر نمی گیرد (صرفنظر می کند)
2- اگر Ti نه در Cl ونه در Al است، آنگاه Ti هنگام بروز خطا فعال بوده بنابراین آن را به Al اضافه می کند.
3- اگر Ti هم اکنون در Al است آنگاه اگر x هم اکنون درون بافر نیست آنرا می خواند و مقدار قبلی بخشی از x که در رکورد به روز رسانی ثبت شده است رابه آنباز می گرداند. همچنین اگر رکورد به روز رسانی هیچ مقدار پیشینی ندارد (اشاره گر به رکورد به روز رسانی قبلی آن Null است) آنگاه Ti از Al حذف می شود چون چیزی از Ti برای خنثی شدن وجود ندارد.
restart از رگورد Check point آخر صرفنشر کرده و Check point ماقبل آخر را می خواند و لیست تراکنشهای فعال که در آن ذخیره شده اند را بررسی می کند. آن تراکنشهای که نه در Al ونه در Cl قرار دارند را به Al اضافه می کند اینها تراکنشهایی هستند که در Check point ماقبل آخر فعال یوده و هیچگاه قطعی یا abort نشده اند بنابراین هنگام بروز خطا فعال بوده اند و باید abort شوند.
restart از Check point ماقبل آخر جستجوی خود رادرون Log با صرفنظر از تمامی رکوردها جز رکورهای به روز رسانی که مربوط به تراکنشهای درون Al هستند ادامه می دهد اینها درمرحله سوم پردازش می شوند ربرسی عقبگرد زمانی به انتها می رسد که Al خالی شود.
برای فهمیدن اثرات بررسی عقبگرد مثالی را برای یک بایت تک بررسی می کنیم. فرض کنید U آخریم رکورد به روز رسانی است که اثرات یک به روز رسانی روی b را مشخص کی کند و تراکنش مربوطه قبل از بروز خطا، قطعی شده است. با استفاده از تعریف، مقدار جدید U آخرین مقدار واقعی داده در زمان بروز خطا است. ادعا می کنیم که اگر U قبل از Check point ما قبل آخر باشدآنگاه مقدار b پس از بررسی عقبگرد شامل آخرین مقدار قطعی خود که درون U است می باشد.
از آنجا که U بر رکورد Check point ما قبل آخر مقدار بعدی آن قبل از بروز خطا درون SDB نوشته شده است حال فرض کنید که V یک رکورد به روز رسانی باشد که اثرات یک به روز رسانی روی b پس از U را نشان می دهد و تراکنش Ti تراکنشی است که باعق V شده است باتوجه به تعریف U ، V قبل از بروز خطا، قطعی نشده است. اگر رکورد مربوط به abort شدن V قبل از Check point ما قبل آخر باشد آنگاه V باید abort شده باشد درغیر اینصورت restart در بررسی عقبگرد از Log به روزرسانی V را خنثی می کند. درهر حالت بنا به دعوی، b شامل آخرین مقدار قطعی خود که درون U ذخیره شده است می باشد.
باتوجه به تقدم رکوردها، تمامی آنهایی که بعد از بررسی عقبگرد باقی می مانند. به روز رسانی هایی رانشان می دهند که رکورد آنها پس از Check point ماقبل آخر است و باید redo شوند.
این کار با بررسی پیشرو، و با شروع از رکورد Check point ماقبل آخر انجام می شود. برای هر رکوردبه روز رسانی که تراکنش آن درون Cl قرار دارد داده های متناظر خوانده می شوند (اگر هم اکنون دورن بافر نیستند) و مقدار بعدی آنها درون Slot مربوطه نوشته می شود. رکوردهای به روزرسانی مربوط به تراکنشهایی که درون Cl نیستند صرفنظر می شوند و بررسی با رسیدن به انتهای Log خاتمه می یابد و دراین لحظه DB درحالت قطعی خود نسبت به Log است (تعدادی هنور در بافر dirty هستند).
این الگوریتم idempotent است چون هیچ فرضی برای SDB ایجاد نمی کند مگر آنهایی که توسط رکورد Check point مطلبی را می رسانند. بنابراین اگر پس از اعمال کردن تعدادی Undo و redo توسط یک خطای سیستمی متوقف می شود پس از خطا دوباره می تواند از ابتدااجرا شود.
با این دو بررسی روی Log و به روز رسانی های تعداد زیادی داده restart می تواند یک پردازنده وقت گیر باشد و اگر سیستمم پس از اتمام restart و قبل از اجرای یک Check pointجدید با خطا مواجه شود. کلیه کارها پس از وقوع خطای دوم باید دوباره اجرا شوند. restart برای جلوگیری از این مورد، پس از اتمام کارهای خود دو Check point را اعمال می کند.
با استفاده از اطلاعات درون آخرین رکورد Check point که به ما می گوید کدام اقلام داده درون dirtyslot هابوده اند می توانیم روال restart را بهبود ببخشیم و از redo و Undo های غیر ضروری اجتناب کنیم. یک رکورد به روز رسانی برای x نیاز به Undo ندارد اگر:
A1 : رکورد مربوط به abort تراکنش آن بین دو رکورد Check point آخر قرار گرفته باشد و x در آخرین رکورد Check point، بین اقلام داده ای که درون dirtyslot ها هستند نباشد.
A2 : رکورد مربوط به abort تراکنش آن بین دو رکورد Check point آخر باشد و x در آخرین رکورد Check point درون یک dirtyslot باشد ولی LSN آن بزرگتر از LSN مربوط به رکورد abort تراکنش مربوطه باشد.
درمورد A1 اگر x بین dirtyslot های آخرین Check point نباشد به معنی این است که Slot مربوط به x پس از abort شدن جایگزین شده است بنابراین مقدار قبلی آن بازگردانده شده است . درمورد A2 : در اینصورت می توان نتیجه گرفت که پس از abort شدن تراکنش Ti مقدار x باید جایگزین شده باشد در غیر اینصورت LSN آن نباید بزرگتر از LSN مربوط به رکورد abort باشد بنابراین مقدار قبلی x درون SDB ذخیره شده است.
بطور مشابه فرض کنید در طول بررسی پیشرو روی Log ، restart یک رکورد به روزرسانی از تراکنش Ti (که در Cl است) برای داده x بخواند این رکورد نیاز به redo ندارد اگر:
C1 : رکورد به روز رسانی مربوط به Ti بین دو رکورد Check point آخرقرارگرفته باشد و x هنگام آخرین Check point بین داده هایی که درون dirtyslot بوده اند نباشد یا
C2 : رکورد به روزرسانی مربوط به Ti بین دو رکورد Check point آخر باشد و x هنگام آخرین Check point بین داده های درون dirtyslot باشد ولی LSN آن بزرگتر از LSN مربوط به رکورد به روز رسانی Ti باشد.
دلیل اینکه چرا این ظرطها نیاز به روز رسانی x ، به redo رابر طرف می کند مانند شرطهای A1 و A2 است. همچنین یک اختلاف بین شرطهای فوق وجود دارد. شرطهای C1 و C2 موقعیت یک رکورد به روز رسانی را نسبت به سایر رکوردها شرح می دهندولی شرطهای A1 و A2 موقعیت یک رکورد abort را نسبت به سایر رکوردها شرح می دهند.

[mzjahromi]

4-5) یادداشت برداری منطقی:
حتی با استفاده از partial data item logging مقادیر قبلی و بعدی داده ها ممکن است فضای زیادی را مصرف کند. این مورد در صورتی اتفاق می افتد که هر نوشتن روی یک داده x بیشتر محتویات آن را تحت تأثیر قرار دهد. به عنوان مثال فرض کنید هر قلم داده صفحه ای از یک فایل است. یک دستورالعمل کاربر که رکوردی جدید ® رابه ابتدای این صفحه اضافه می کند ممکن است بقیه محتویات p را به پائین منتقل می کند تا فضای کافی برای r ایجاد شود از دید RM کل P تغییرکرده است بنابراین حتی با روش partial data item logging هم باید مقادیر قبلی و بعدی P درون Log قرار گیرد.
با استفاده از logical logging می توان حجم این دوصفحه رکورد به روز رسانی را کاهش داد با جایگزینی آن توسط یک رکورد که می گوید: «یک رکورد r به صفحه p اضافه شده است» این رکورد بسیار کوچکتر از این است که بخواهد شامل مقدار بقلی و بعدی صفحه p باشد. برای تفسیر این رکورد پس از بروز خطا، restart می تواند آن را با اضافه کردن رکورد r به صفحه p دوباره انجام دهد یا با حذف کردن r از p آن را خنثی کند. (باتوجه به اینکه تراکنش مربوطه قطعی یا abort شده است)
برای پیاده ساری logical logging باید نحوه کار روال به روز رسانی را بیش از یک write ساده درنظر بگیریم. زمانی که در روش یادداشت برداری فیزیکی یک رکورد به روز رسانی را تفسیر می کنیم مقدار قبلی یا بعدی یک داده را بدون توجه به وضعیت فعلی آن بر می گردانیم اما در logical logging باید بیشتر دقت کنیم. تعدادی از Undo و redo ها ممکن است تنها روی داده هایی قابل اجرا باشند که دقیقاً وضعیتی مشابه قبل از به روز رسانی (برای redo ) یا بعد از آن (برای Undo ) داشته باشند. برای دیدن این مورد به مثالهای زیر توجه کنید:
فرض کنید که Log شامل یک رکورد LR درج رکودر r در بلاک p یاشد. فرض کنید که Slot مربوط به p قبل از بروز خطا تخلیه نشود و تراکنش Ti که باعث این به روز رسانی شده است abort شودوقتی که درون Log به عقب جستجو می کنیم restart ، LR را Undo می کند درنتیجه Undo روی کپی از x عمل می کند که r روی آن ذخیره نشده است. متأسفانه undo (LR) قادر نیست که به ما بگوید r درون p است با خیر؟ اگر او سعی کند به هر طریقی r رااز p حذف کند ممکن است مقدار دیگری از اطلاعات درونی p را پاک کند به این ترتیب p خراب می شود. این روش در صورتی مشکل نخواهد بودکه به سادگی مقدار قبلی را بازگرداندوهمچنین بازگرداندن مقدار قبلی یک داده وابسته به وضعیت فعلی آن نباشد.
یک راه برای اجتناب از این مشکل این است که روالهای redo و Undo راطوری بنویسیم که اگر بر روی داده هایی که در وضعیت مناسب خود قراردارند اعمال شود هیچ تأثیری روی آن نداشته باشد. به عنوان مثال Undo در صورتیکه p از به روز رسانی مربوط به LR استفاده نکرده باشدروی P اثری نگذارد و در صورتیکه p از به روز رسانی مربوط به LR استفاده کرده باشد redo روی آن اثری نگذارد.
یک راه برای جلوگیری از این مشکل ذخیره کردن LSN در اقلام داده است هر قلم داده شامل یک LSN از یک Log record است که آخرین عملیات به روز رسانی روی آن داده را شرح می دهد. در DB هائی که از این روش استفاده می کنند LSN یک فیلد از headep می باشد.
LSN ها در هر قلم داده x برای restart خیلی مفید است چون دقیقاً به ما می گوید که کدام به روز رسانی درون Log بر روی x اعمال شده است. کلیه رکوردهای به روز رسانی که LSN آنها کوچکتر یا مساوی LSN (x) باشند اعمال شده اند و کلیه آنهایی که دارای LSN بزرگتر از x هستند اعمال نشده اند. این اطلاعات restart را قادر می سازد که یک رکورد به روز رسانی را تنها اگر x درهمان وضعیتی که زمان تولید رکورد به روز رسانی بود باشد، Undo یا redo کند.
همچنین LSN ها را در اقلام داده restart رادر بالاترین بازده نیز کمک می کنند. از آنجا که restart با بررسی LSN ها مربوط به یک قلم داده می تواند تشخیص دهد که آیا یک به روز رسانی هم اکنون روی کپی ماندگار اعمال شده است یا نه نمی تواند از Undo یا redo های غیر ضروری نیز اجتناب کند.
برای حمایت از مقدار صحیح درون LSN برای هر قلم داده x ، RM برای هر رکورد به روز رسانی برای x با نام U ، یک فیلد جدید رادرنظر می گیرد. این فیلد شامل LSN مربوط به رکورد به روز رسانی x قبل از U است. با توجه به اینکه LSN آخرین به روز رسانی درون هر قلم داده وجود دارد فراهم کردن این اطلاعات زمان تولید U به راحتی میسر است. بنابراین کلیه به روز رسانیهای یک قلم داده با استفاده از این فیلد بصورت زنجیر به یکدیگر متصل می شوند.
در بحث بعدی توضیح خواهیم داد که چگونه RM از LSN درون اقلام داده استفاده می کند. دراین قسمت ما از روشی به نام LSN based logging استفاده می کنیم و فرض می کنیم که از Logical logging استفاده می شود جائیکه هر رکورد به روز رسانی تشریح یک به روز رسانی روی یک قلم داده تک می کند همچنین فرض می کنیم که از
fuzzy check pointing استفاده می شود.
برای پردازش یک نوشتن روی x ، RM یک رکورد به روز رسانی با نام U ایجاد
می کند و مقدار فعلی LSN(x) را درون U قرار می دهد (فیلدی که به روز رسانی قبلی اشاره می کند) و LSN(x) را به LSN(u) مرتبط می سازد (آدرس U درون Log) هنگام خنثی کردن U در پی abort مقدار LSN(x) رابه مقدار قبلی آن که در U ذخیره شده است تغییر می دهد.
روال restart دونمونه بررسی را روی Log انجام می دهد یک بررسی عقبگرد برای Undo ویک بررسی پیش رونده برای redo . فرض کنید در طول بررسی عقبگرد restart به یک رکوزد با نام U برخورد می کند که نشان دهنده یک به روز رسانی روی x توسط تراکنشی است که بلافاصله abort صادر شده است. بنابرایم x را خوانده و LSN را بررسی می کند حالتهای زیر وجود دارد.
1- اگر LSN(u) < LSN(x) آنگاه x شامل به روز رسانی U نیست. بنابراین restart نباید U را Undo کند. توجه شود که در این حالت LSN(x) برای جلوگیری از خنثی کردن U به ما کمک می کند.
2- اگر LSN(u)= LSN(x) ، آنگاه restart ، U را با قرار دادن مقدار قبلی LSN که درون U ذخیره شده است درون x ، خنثی می کند. توجه شود که LSN(u) = LSN(x) این مطلب را بیان می کند که x هم اکنون درهمان حالتی است که U اولین بار بکار برده شده بود.
3- اگر LSN(u) > LSN(x) ، آنگاه x شامل یک به روز رسانی است که توسط یک رکورد به روز رسانی با نام V پس از U انجام شده است. بنابراین V در طی بررسی عقبگرد خنثی نشده است درنتیجه تراکنشی که V را تولید کرده است باید قطعی شده باشد.
بررسی عقبگرد زمانیکه restart به رکورد Check point ماقبل آخر برسد، ورکوردهای به روزرسانی کلیه تراکنشهایی که هنگام Check point ما قبل آخر فعال بوده و پس از آن قطعی نشده اند را طی کرد به انتها می رسد.
هنگام بررسی پیشرونده restart از Check point ماقبل آخر شروع می کند و هر رکورد به روز رسانی با نام U از یک تراکنش قطعی شده را redo می کند. اگر LSN(x) > LSN(u) که دراین صورت x شامل به روز رسانی U نمی باشد. اگر LSN(x) > LSN(x) ، آنگاه restart از U صرفنظر می کند چون x هم اکنون همان وضعیتی را دارد که U تولید کرده بود (LSN(u) > LSN(x) ) در اینصورت به روز رسانی بعدی باید توسط یک تراکنش قطعی شده صورت گرفته باشد و الا در طول بررسی عقبگرد خنثی می شد با توجه به مطالب فوق restart از انجام Undo و redo های تکراری نیز خودداری می کند.

[mzjahromi]

دراین بخش الگوریتمی از RM را بررسی می کنیم که هیچگاه نیاز به redo ندارد. برای رسیدن به این حالت، الگوریتم، تمام به روز رسانیهای تراکنشها را قبل از قطعی شدن درون SDB ثبت می کند این مورد می تواند با اعمال تغییرات کمی در الگوریتم
Undo / redo حاصل شود. درحقیقت روالهای RM-write و RM-read و RM- abort دقیقاً همانها هستند ولی روالهای RM-Commit و restart به صورت زیر هستند.

RM-commit (Ti) :
1- برای هر قلم داده x که توسط Ti به روز رسانی شده است اگر x درون بافر قرار داردآنرا تخلیه کن.
2- Ti را به لیست تراکنشهای قطعی شده اضافه کن.
2- قطعی شدن Ti را به زمانبند اطلاع بده.
4- Ti را از لیست تراکنشهای فعال حذف کن.

restart :
1- کلیه Slot های بافر را دور بریز
2- redone :={ }
3- از اولین مدخل Log شروع کن تا به ابتدا برسی مراحل زیر را تا زمانیکه undone برابر مجموعه اقلام داده درون DB شود، یا اینکه هیچ مدخلی برای بررسی وجود نداشته باشد تکرار کن.
برای هر مدخل Log به صورت [Ti,x,v] اگر Ti عضو لیست تراکنشهای قطعی شده لیست و undone آنگاه:
- یک Slot را برای x در نظر بگیر
- مقدار قبلی x نسبت به اجرای Ti را درون Slot مربوط به x کپی کن و undone:=undone U{x}
4- برای هر Ti درون لیست تراکنشهای قطعی شده اگر Ti درون لیست تراکنشهای فعال قرار دارد آنرا از لیست فعال حذف کن
5- اتمام عمل restart را به زمانبند اطلاع بده

توضیحات:
(مرحله دوم از RM-commi (Ti) ): این فعالیتی سات که بیان می کند یک تراکنش قطعی شده است. اگر قبل از اینکه Ti به لیست تراکنشهای قطعی شده اضافه شود سیستم با خطا مواجه شود restart تراکنش Ti را به عنوان یک تراکنش قطعی نشده در نظرگرفته و آنرا abort می کند.
(مرحله چهارم از restart ): خطای سیستمی ممکن است پس از مرحله دوم و قبل از مرحله چهارم از RM-commit اتفاق بیافتد. بنابراین تراکنش Ti ممکن است هم در لیست تراکنشهای فعال و هم در لیست تراکنشهای قطعی باشد. دراین حالت تراکنش Ti باید قطعی در نظرگرفته شود.
این الگوریتم قانون redo را رعایت می کند. دلیل آن مانند الگوریتم Undo / redo است و همچنین چون نیازی به redo ندارد لازم نیست که قوانین redo را رعایت کند. ولی با توجه به اینکه قبل از قطعی شدن هر تراکنش کلیه به روز رسانی های آن را درون SDB ثبت می کند می توان گفت که قانون redo هم رعایت می شود. بنابراین restart همیشه می تواند SDB رابه آخرین وضعیت قطعی خود قبل از بروز خطا ببرد. همچنین restart ، idempotent نیز هست. از آنجا که restart نمی تواند مجموعه تراکنشهایی که روی آن عمل می کند را تغییر دهد اگر توسط یک خطای سیستمی متوقف شود می تواند دوباره دقیقاً همان کار را انجام دهد.

5-1) پیاده سازی:
با ایجاد تغییرات کمی در ساختار Log که برای partial data item logging توضیح داده شد می توانیم از آن برای الگوریتم undo/no-redo استفاده می کنیم. مانند قبل Log یک فایل ترتیبی روی دیسک است که شامل رکوردهای update و commit و abort و Check point است.
تنها تفاوت آن این سات که رکوردهای به روز رسانی نیازی به استفاده از نقادیر بعدی ندارند. از آنجا که در این الگوریتم هیچگاه نیازبه redo نداریم درنتیجه به مقادیر بعدی نیز نیازی نداریم.
برای اعمال تغییرات بر روی RM-commit کلیه Slot هائی که توسط یک تراکنش نوشته شده اند باید قبل از اینکه رکورد قطعی، درون Log قرار گیرد تخلیه شوند. می توانیم مانند یک حالت محدود از Check point به آن نگاه کنیم. اگر چه ما هنوز برای اطمینان از بازگشت مقادیر قبلی تراکنشهای abort شده که درون SDB ثبت شده اند نیاز به Check point داریم ولی می توان با اعمال تغییراتی در RM-abort ، Check point را از این اگلوریتم برداشت.

[mzjahromi]

6) الگوریتم no-undo/redo :
دراین بخش الگوریتم دیگری از RM را ارائه خواهیم داد که نیاز به redo دارد ولی هیچگاه نیاز به Undo ندارد. برای اجتناب از Undo ما نباید به روز رسانیهای تراکنشهای قطعی نشده را درون SDB ثبت کنیم. به همین دلیل زمانیکه یک قلم داده نوشته می شود مقدار جدید آن بلافاصله درون cache ثبت نمی شود. این کار تنها پس از قطعی شدن تراکنش انجام می شود درنتیجه زمانیکه در پی یک جایگزینی یا تخلیه Slot ها مقداری جدید درون SDB ثبت می شود این مقدار دقیقاً توسط یک تراکنش قطعی شده بوجودآمده است و هیچگاه نیازبه Undo ندارد. پنج پردازه RM به صورت زیر است:

RM- write (t1,x,v):
1) افزودن یک رکورد [Ti,x,v] به Log
2) اطلاع دادن به زمانبند در مورد پردازش RM- write (t1,x,v)

RM- read (Ti,x) :
1) اگر Ti قبلاً درون x نوشته است مقدار بعدی x سنبت به T رابه زمانبند بازگزدان
2) و الا - اگر x درون بافر نیست آنرا بخوان
- مقدار درون Slot مربوط به x را به زمانبند بازگردان

RM- commit (ti) :
1) Ti رابه لیست تراکنشهای قطعی اضافه کن
2) برای هر x که توسط Ti به روز رسانی شده است
- اگر x درون بافر نیست آنرا بخوان
- مقدار بعدی x نسبت به اجرای تراکنش Ti را درون Slot مربوط به x کپی کن
3) پردازش RM- commit رابه زمانبند اطلاع بده

RM- abort (Ti) :
1) Ti را به لیست تراکنشهای abort شده اضافه کن
2) پردازش RM-abort را به زمانبند اطلاع بده

restart :
1) کلیه محتویات بافر را دور بریز
2) redone= { }
3) از آخرین مدخل درون Log شروع کن و بررسی عقبگرد را ادامه بده تا به ابتدا برسی و مراحل زیر را تکرار کن تا زمانیکه یا redone برابر مججموعه داده های درون DB شود یا اینکه هیچ مدخلی برای بررسی درون Log وجود نداشته باشد.
برای هر مدخل Log به فرم [Ti,x,v] اگر Ti عضو تراکنشهای قطعی شده است و X=redone آنگاه:
- یک Slot برای x در نظر بگیر
- v را درون x کپی کن
readone:= readone U {x}
4) پردازش restart را به زمانبند اطلاع بده

توضیحات:
از مرحله یکم از RM-read و مرحله دوم از RM-commit : مقدار بعدی x نسبت به تراکنش Ti را می توان درون log یافت کرد که توسط RM-write وارد شده است.
(مرحله یکم RM-commit) این فعالیتی است که مشخص می کند یک تراکنش قطعی شده است
(مرحله یکم از RM-abort ): در این سطح ما مواردی را توضیح می دهیم که به لیست تراکنشهای abort شده نیازی ندارد. بنابراین اطلاعات درون آن لیست برای garbage collector است که مشخص کند کدام بخش از log مربوط به تراکنشهای abort شده است.
این الگوریتم قانون redo را رعایت می کند: هر مقداری که توسط یک تراکنش نوشته می شود RM-write آن را درون log قرار می دهد و توسط قانون garbage collection نمی تواند تا زمانیکه تراکنش قطعی نشده حذف شود. باتوجه به اینکه الگوریتم نیازی به undo ندارد نیازی به رعایت کردن قانون undo نیست. بنابراین کلیه قوانین ارضاء می شوند و restart همیشه می تواند اطلاعاتی را که برای بازگرداندن SDB به وضعیت قطعی. خود قبل از بروز خط نیاز دارد رادرون حافظه ماندگار پیدا کند و از آنجا که restart هیچ اثری روی مجموعه تراکنشهای قطعی شده ندارد اگر توسط یک خطای سیستمی متوقف شود دقیقاً می تواند همان کارها را انجام دهد بنابراین idempotent نیز است.

6-1) پیاده سازی:
این الگوریتم را می توان با استفاده از ساختارهای log مشابه آنکه برای دو الگوریتم قبلی استفاده کردیم پیاده سازی کنیم. برطرف کردن undo مطالب زیادی را ساده می کند. اول اینکه نیازی به ایجاد رکورد abort درون log نداریم. دوم از آنجا که هیچگاه نیاز به undo نداریم رکورد به روز رسانی نیازی ندارد که شامل مقدار قبلی باشد. با توجه به اینکه پیدا کردن مقدار قبلی با استفاده از رکورد به روز رسانی نیاز به دسترسی اضافی به حافظه ماندگار دارد این مطلب می تواند خیلی مهم باشد. مثل همیشه check pointing رابرای محدود کردن زمانیکه یک update می تواند قبل از تخلیه شدن درون حافظه بماند نیاز داریم و برای این مورد می توان از کلیه تکنیکهای بررسی شده در مورد redo/undo استفاده کرد.

7) الگوریتم no-undo/no-redo :
برای اجتناب از redo کلیه به روز رسانیهای تراکنش Ti باید در زمان قطعی شدن Ti درون SDB باشند وبرای اجتناب از undo هیچکدام از به روز رسانیهای Ti نمی توانند قبل از قطعی شدن Ti درون SDB قرار گیرند. بنابراین برای حذف کردن undo و redo با هم کلیه روز رسانیهای Ti باید با یک دستورالعمل atomic در زمان قطعی شدن Ti درون SDB نوشته شوند. روال RM-commity می تواند به صورت زیر باشد:

RM-commit (Ti) :
1- در یک فعالیت atomic :
- برای هر قلم داده x که توسط Ti به روز رسانی شده است مقدار بعدی x نسبت به اجرای Ti را درون SDB بنویس.
- Ti را درون لیست تراکنشهای قطعی شده قرار بده.
2- اتمام پردازش RM-commit رابه زمانبند اطلاع بده.
باور نکردنی است که چنین روالی عملی شود. برای این کار باید نوشتن به روز رسانیها درون SDB و درج Ti درون لیست تراکنشهای قطعی شده غیر قابل تقسیمی باشد. این کار را می توان با محدود کردن تعداد به روز رسانیهایی که یک تراکنش می تواند انجام دهد انجام داد.
ما میتوانیم با استفاده از نوعی Shadowing به این هدف برسیم. موقعیت آخرین مقدار قطعی برای هر قلم داده، درون یک دایرکتوری ثبت می شود که درون حافظه ماندگار است و ممکن است برای دسترسی سریعتر درون بافر باشد. همچنین دایرکتوریهای کاری وجود دارد که به نسخه های قطعی نشده بعضی از اقلام داده اشاره می کنند این دایرکتوریها با هم به مجموعه مقادیر قبلی و بعدی که معمولاً درون Log ذخیره شده اند اشاره می کند. همچنین ما log را به صورت یک فایل ترتیبی نمی سازیم.
زمانیکه یک تراکنش یک قلم داده x را می نویسد نسخه جدیدی از x درون حافظه ماندگار ایجاد می شود. دایرکتوری کاری که وضعیت DB را نشان می دهد برای به روز رسانی Ti برای اشاره به این نسخه مورد استفاده قرار می گیرد. تصور کنید این نسخه جدید بخشی از log است تا زمانیکه Ti قطعی شود. زمانیکه Ti قطعی می شود دایرکتوری که وضعیت قطعی SDB را نشان میدهد به روز رسانی می شود تا به نسخه هایی که Ti نوشته است اشاره کند که با این کار نتیجه Ti جزئی از وضعیت قطعی SDB قرار می گیرد.
با این ساختار به یک روال commit با خواص خواسته شده نیاز است که اتوماتیک مدخلهای دایرکتوری را برای اقلام داده نوشته شده توسط تراکنشی که قطعی شده است تعویض کند.
از آنجا که دایرکتوری بسیار کوچکتر از DB است می توان دو کپی از آن را درون حافظه ماندگار ذخیره کرد. یک دایرکتوری جاری که به DB است می توان دوکپی از آن را درون حافظه ماندگار ذخیره کرد. یک دایرکتوری که به DB قطعی اشاره می کند و یک کپی چرکنویس که برای Commit کردن تراکنش Ti ، RM از دایرکتوری چرکنویس برای نمایش وضعیت SDB با استفاده از به روز رسانیهای Ti استفاده می کند. برای هر قلم داده x که Ti آنرا به روز رسانی می کند RM یک مدخل دایرکتوری چرکنویس ایجاد می کند که به نسخه جدید x اشاره می کند وبرای اقلام داده ای که Ti آنها را به روز رسانی نمی کند یک مدخل دایرکتوری ایجاد می کند که به مقدار قبلی x اشاره می کند. سپس دایرکتوری جاری و چرکنویس را در یک فعالیت Atomic توسط یک رکورد اصلی درون حافظه ماندگار پیاده سازی می شود. این رکورد شامل بیتی است که نشان می دهد کدامیک از دوکپی نمونه اصلی است. برای جابجا کردن دایرکتوریها RM به سادگی بیت درون رکورد اصلی را وارون می کند. که مطمئناً یک فعالیت atomic است. تعویض آن بیت فعالیتی است که تراکنش را قطعی می کند.
شکل 3 - ساختاری که برای الگوریتم قطعی کردن تراکنش Ti که داده های x و y را بروز رسانی می کند استفاده شده است را تشریح می کند.
دایرکترویهای اصلی و کپی در shadowing

قبل از تشریح پنج پردازنده RM اجازه دهید تعریفاتی در مورد ساختمان حافظه ماندگار استفاده شده در این الگوریتم داشته باشیم. یک رکورد اصلی که تنها یک بیت را ذخیره می کند داریم و دو دایرکتوری D0 و D1 که درهر لحظه Db دایرکتوری جاری است اگر b مقدار درون رکورد اصلی باشد. Db [x] داده x درون دایرکتوری Db را مشخص می کند که شامل آدرس x درون SDB است. و از -b برای تعریف نقیض b استفاده می کنیم بنابراین Db دایرکتوری چرکنویس است. در هر لحظه ممکن است یک یا دو نسخه از یک قلم داده وجود داشته باشد. یکی در SDB (که توسط Db به آن اشاره
می شود) و احتمالاً یک نسخه جدید. کلیه این اطلاعات ( SDB و نسخه جدید و دو دایرکتوری و رکورد اصلی) باید درون حافظه ماندگار ذخیره شوند.
همچنین برای هر تراکنش فعال Ti یک دایرکتوری Di وجود دارد که شامل آدرس نسخه های جدید اقلام داده اس است که توسط Ti نوشته شده اند. این دایرکتوریها نیازی ندارند که درون حافظه ماندگار باشند. با این ساختار روالهای RM به صورت زیر است:

RM- write (ti,x,v)
1) V را درون یک موقعیت استفاده نشده از حافظه ماندگار بنویس و آدرس آن را در Di[x] قرار بده.
2) پردازش RM-write (ti,x,v) رابه زمانبند اطلاع بده.

RM-read (Ti,x) :
1) اگر Ti قبلاً یک نوشتن روی x دشاته است مقداری که درموقعیت Di[x] است را به زمانبند بازگردان
2) والا مقداری که درموقعیت D6[x] قرار دارد را به زمانبند بازگردان جائیکه b مقدار فعلی بیت رکورد اصلی است.

RM-commit (ti)
1) برای هر x که توسط Tiبه روز رسانی شده است D-b[x]:= Di[x] جائیکه b مقدار M است
2) M:=-b ( M همان رکورد اصلی است)
3) برای هر x که توسط Ti به روز رسانی شده است D-b[x]:= Di[x] جائیکه b مقدار جدید M است
4) Di را دور بریز (هرحافظه ای که برای Di استفاده شده است را آزاد کن)
5) اتمام قطعی شدن Ti را به زمانبند اطلاع بده

RM-Abort (ti) :
1) Di را دور بریز
2) اتمام abort شدن Ti را به زمانبند اطلاع بده

Restart :
1) Db را درون Db کپی کن
2) حافظه ای که برای دایرکتوریهای تراکنشهای فعال و نسخه های جدید آنها در نظرگرفته شده را آزاد کن
3) اتمام پردازش restart را به زمانبند اطلاع بده

توضیحات:
(مرحله اول از RM-write): این مرحله یک نسخه جدید از x را تولید می کند بدون اینکه نسخه قبلی آن از بین ببرد.
(مرحله دوم ازRM-read) : اگر Ti قبلاً درون x نوشته است نسخه ای از x را که هنگام نوشتن ایجاد کرده است را می خواند و در غیر اینصورت مقدار موجودر در SDB را می خواند.
(مرحله اول از RM-commit ): این مرحله دایرکتوری چرکنویس را تنظیم می کند که به روز رسانیهای Ti را منعکس می کند.
(مرحله دوم از RM-commit ): این مرحله بیت موجود در رکورد اصلی را نقیض می کند. به این وسیله دایرکتوری چرکنویس رابه دایرکتوری جاری تغییر می دهد این یک فعالیت Atomic است که Ti را قطعی می کند. خطا قبل از این مرحله باعث abort شدن Ti می شود.
(مرحله سوم از RM- commit): این مرحله تغییرات Ti را در Db نیز که هم اکنون دایرکتوری چرکنویس است ثبت می کند و این اطمینان را می دهد که زمانیکه دایرکتوری دوباره به دایرکتوری جاری تبدیل شد. اثرات بروز رسانیهای Ti هنوز در SDB وجود دارد.
الگوریتم قانون undo را رعایت می کند چون هیچگاه SDB شامل مقادیری که توسط تراکنشهای قطعی نشده نوشته شده باشند نیست و همچنین قانون redo را ارضاء می کند چون هنگام قطعی شدن تمامی به روز رسانیهای تراکنش درون SDB قرار دارد. در حقیقت تحت این الگوریتم SDB همیشه شامل آخرین مقدار قطعی DB است. درنتیجه واقعاً به هیچ عملی برای abort یک تراکنش یا restart هنگام بروز خطا نیاز نیست.
این الگوریتم سه هزینه مهم هنگام اجرای نرمال دستورالعملها نیز دارد: اول اینکه دسترسی به حافظه ماندگار غیر مستقیم است درنتیجه هزینه زیادی مصرف می شود هرچند در صورت کوچک بودن دایرکتوری با ذخیره آن درون بافر می توان این هزینه را کاهش داد. دوم اینکه پیدا کردن مقادیر قطعی نشده برای آزاد سازی فضای آنها می تواند در غیاب log کارائی خوبی نداشته باشد و سوم و مهمتر از همه اینکه انتقال داده ها به نسخه جدید ساختار فعلی SDB را خراب می کند و موقعیت اقلام داده نسبت به زمان مرتباً تغییر
میکند.
بنابراین در صورتیکه DB طوری طراحی شده باشد که اقلام داده وابسته به هم از نظر موقعیت درون حافظه ماندگار نزدیک به یکدیگر قرار گیرند. آن طراحی زمانی می تواند از این روش استفاده کند که در هر لحظه تعدادی از اقلام داده با هم به روزرسانی شوند. به عنوان مثال اگر رکوردهای یک فایل برای افزایش کارایی دستیابی ترتیبی، کنار یکدیگر ذخیره شده اند. دراین روش بالاخره رکوردها در موقعیتهای مختلف پراکنده می شوند. بنابراین سرعت دستیابی ترتیبی پائین می آید. این مشکل برای تعداد زیادی از پیاده سازیهای Shadowing مشترک است.