การกู้คืนและการบันทึกข้อมูล

กลไกการกู้คืนและการบันทึกข้อมูลรับประกันความเป็นอะตอมมิค (atomicity) และความคงทน (durability) ของธุรกรรมโดยการบันทึกการเปลี่ยนแปลงลงในล็อก (log) เพื่อให้หลังจากระบบล่ม งานที่ทำเสร็จแล้วสามารถทำซ้ำได้ และงานที่ยังไม่เสร็จสามารถยกเลิกได้

Definition

การกู้คืนฐานข้อมูลคือกระบวนการกู้คืนฐานข้อมูลให้อยู่ในสถานะที่สอดคล้องกันหลังจากความล้มเหลว เพื่อให้มั่นใจว่าผลกระทบของธุรกรรมที่คอมมิตแล้วมีความคงทน และธุรกรรมที่ถูกยกเลิกหรืออยู่ระหว่างดำเนินการจะไม่ทิ้งร่องรอยใดๆ; การบันทึกข้อมูลคือเทคนิคการบันทึกการกระทำของธุรกรรมลงในล็อกที่คงทนเพื่อให้สามารถดำเนินการนี้ได้

Scope

หัวข้อนี้ครอบคลุมถึงวิธีการที่ฐานข้อมูลรอดพ้นจากความล้มเหลว: โปรโตคอลการบันทึกข้อมูลล่วงหน้า (write-ahead logging - WAL), ข้อมูลการยกเลิก (undo) และการทำซ้ำ (redo), จุดตรวจสอบ (checkpoints) เพื่อจำกัดขอบเขตงานการกู้คืน, และอัลกอริทึมการกู้คืนมาตรฐาน (โดยเฉพาะ ARIES) พร้อมกับการวิเคราะห์, การทำซ้ำ, และการยกเลิก. นอกจากนี้ยังกล่าวถึงนโยบายการจัดการบัฟเฟอร์ (steal/no-steal, force/no-force) ที่กำหนดว่าต้องมีการบันทึกข้อมูลประเภทใด. หัวข้อนี้ไม่รวมถึงโปรโตคอลการควบคุมการทำงานพร้อมกัน (concurrency-control protocols) ที่ทำงานระหว่างการทำงานปกติและการคอมมิตแบบกระจาย (distributed commit) ซึ่งเป็นหัวข้อที่เกี่ยวข้องแต่แยกกัน.

Core questions

• เหตุใดบันทึกข้อมูล (log record) จึงต้องไปถึงที่เก็บข้อมูลถาวรก่อนข้อมูลที่บันทึกอธิบาย (write-ahead logging)?
• การยกเลิก (undo) และการทำซ้ำ (redo) กู้คืนสถานะที่สอดคล้องกันหลังจากระบบล่มได้อย่างไร?
• นโยบายการจัดการบัฟเฟอร์ (steal/force) กำหนดข้อกำหนดการบันทึกข้อมูลอย่างไร?
• จุดตรวจสอบ (checkpoints) มีบทบาทอย่างไรในการจำกัดเวลาการกู้คืน?
• อัลกอริทึม ARIES จัดโครงสร้างการกู้คืนออกเป็นการวิเคราะห์ (analysis), การทำซ้ำ (redo), และการยกเลิก (undo) อย่างไร?

Key concepts

• การบันทึกข้อมูลล่วงหน้า (WAL)
• การบันทึกข้อมูลการยกเลิกและการทำซ้ำ
• หมายเลขลำดับล็อก
• จุดตรวจสอบ
• นโยบาย steal/no-steal และ force/no-force
• บันทึกการชดเชย
• ขั้นตอนการวิเคราะห์, การทำซ้ำ, การยกเลิก
• ARIES

Key theories

การบันทึกข้อมูลล่วงหน้า

โปรโตคอล WAL กำหนดให้บันทึกข้อมูลที่อธิบายการเปลี่ยนแปลงต้องถูกบังคับให้จัดเก็บในที่เก็บข้อมูลที่เสถียรก่อนหน้าหน้าข้อมูลที่เกี่ยวข้อง เพื่อให้มั่นใจว่าหลังจากระบบล่ม ระบบมีข้อมูลเพียงพอที่จะยกเลิกการเปลี่ยนแปลงที่ยังไม่คอมมิตและทำซ้ำการเปลี่ยนแปลงที่คอมมิตแล้ว

การกู้คืนแบบ Undo/redo และนโยบายบัฟเฟอร์

ระบบต้องการการยกเลิก (undo), การทำซ้ำ (redo) หรือทั้งสองอย่าง ขึ้นอยู่กับนโยบายบัฟเฟอร์: นโยบาย steal (การเขียนหน้าข้อมูลที่ยังไม่คอมมิตลงดิสก์) ต้องการการยกเลิก, และนโยบาย no-force (การไม่บังคับหน้าข้อมูลที่คอมมิตแล้วลงดิสก์เมื่อคอมมิต) ต้องการการทำซ้ำ; การรวมกันของ steal/no-force ที่พบบ่อยต้องการทั้งสองอย่าง

ARIES

ARIES เป็นวิธีการกู้คืนที่ได้รับการยอมรับอย่างกว้างขวาง ซึ่งใช้การบันทึกข้อมูลล่วงหน้า, หมายเลขลำดับล็อก, และอัลกอริทึมสามขั้นตอน (การวิเคราะห์, การทำซ้ำ, การยกเลิก) พร้อมกับบันทึกการชดเชย เพื่อรองรับการล็อกแบบละเอียดและการย้อนกลับบางส่วน

Clinical relevance

การกู้คืนและการบันทึกข้อมูลคือสิ่งที่ทำให้ความคงทนเป็นจริง: พวกมันรับประกันว่าเมื่อระบบยืนยันธุรกรรม เช่น การชำระเงินหรือคำสั่งซื้อ ข้อเท็จจริงนั้นจะยังคงอยู่รอดได้แม้ไฟฟ้าดับและระบบล่ม และการที่ระบบล่มกลางคันระหว่างธุรกรรมจะไม่ทำให้ฐานข้อมูลอยู่ในสถานะที่อัปเดตไม่สมบูรณ์และไม่สอดคล้องกัน

History

การสำรวจของ Härder และ Reuter ในปี 1983 ได้วางหลักการของการกู้คืนที่เน้นธุรกรรมและอนุกรมวิธานของนโยบายบัฟเฟอร์. ARIES ซึ่งพัฒนาโดย C. Mohan และเพื่อนร่วมงานที่ IBM และตีพิมพ์ในปี 1992 ได้กลายเป็นอัลกอริทึมการกู้คืนมาตรฐานโดยพฤตินัย โดยรวมการบันทึกข้อมูลล่วงหน้าเข้ากับหมายเลขลำดับล็อก (log sequence numbers) และบันทึกการชดเชย (compensation records) เพื่อรองรับการล็อกแบบละเอียด (fine-granularity locking).

Key figures

• C. Mohan
• Jim Gray
• Theo Härder
• Andreas Reuter

Seminal works

• mohan1992
• haerder1983
• gray1992

Frequently asked questions

เหตุใดการบันทึกข้อมูลล่วงหน้าจึงจำเป็น?

เนื่องจากฐานข้อมูลอาจเขียนหน้าข้อมูลที่แก้ไขแล้วลงดิสก์ก่อนที่ธุรกรรมจะคอมมิต หรือเก็บหน้าข้อมูลที่คอมมิตแล้วไว้ในหน่วยความจำในขณะที่ระบบล่ม การบังคับให้บันทึกข้อมูลก่อนหน้าหน้าข้อมูลรับประกันว่าไม่ว่าตัวจัดการบัฟเฟอร์จะทำอะไร การกู้คืนจะมีข้อมูลเพียงพอที่จะยกเลิกการเปลี่ยนแปลงที่ยังไม่คอมมิตและทำซ้ำการเปลี่ยนแปลงที่คอมมิตแล้วเพื่อเข้าสู่สถานะที่สอดคล้องกัน

จุดตรวจสอบ (checkpoints) ทำอะไรได้บ้าง?

จุดตรวจสอบจะบันทึกธุรกรรมที่กำลังทำงานอยู่เป็นระยะๆ และล้างข้อมูลการบัญชีลงในล็อก ซึ่งเป็นจุดเริ่มต้นที่ทราบว่าดีและเป็นปัจจุบันสำหรับการกู้คืน หากไม่มีจุดตรวจสอบ การกู้คืนอาจต้องสแกนล็อกทั้งหมดตั้งแต่ต้น; จุดตรวจสอบจะจำกัดว่าการกู้คืนต้องประมวลผลย้อนหลังไปไกลแค่ไหน ทำให้เวลาในการเริ่มต้นใหม่สามารถจัดการได้