IF Notes

Algoritma Recovery dan Buffering

5 min read

Back to IF3140 Sistem Basis Data

Algoritma Log-Based Recovery & Optimasi Buffering

Questions/Cues

  • Apa itu Transaction Rollback (saat normal)?

  • Apa itu Compensation Log Record (CLR)?

  • Apa 2 fase algoritma recovery dari failure?

  • Bagaimana cara kerja Redo Phase?

  • Apa itu undo-list?

  • Bagaimana cara kerja Undo Phase?

  • Apa itu Log Record Buffering?

  • Apa itu Log Force?

  • Apa aturan Write-Ahead Logging (WAL)?

  • Apa itu Database Buffering?

  • Apa kebijakan steal vs no-force?

  • Apa itu latch?

Reference Points

  • Slides “12 - Recovery System - 1.pdf” (Slide 22-27)

  • Slides “12 - Recovery System - 2.pdf” (Slide 28-31)

Algoritma Recovery (Detail)

Algoritma recovery dasar (seperti yang digunakan di ARIES) terdiri dari 3 fase, namun slide ini menyederhanakannya menjadi 2 fase utama setelah crash: Redo Phase dan Undo Phase. Algoritma ini juga bergantung pada prosedur rollback standar.

Transaction Rollback (Saat Operasi Normal):

Ini adalah proses abort yang diminta oleh transaksi itu sendiri (bukan karena crash).

  1. Memindai log secara mundur dari akhir.

  2. Untuk setiap log record <Ti, X, V1, V2> milik transaksi Ti:

    • Menulis nilai lama (V1) kembali ke item data X.

    • Menulis Compensation Log Record (CLR), misal <Ti, X, V1>, ke log. (CLR tidak akan di-undo).

  3. Setelah menemukan <Ti start>, tulis <Ti abort> ke log.

Recovery from Failure: Dua Fase

Setelah system crash, sistem melakukan recovery saat restart.

1. Redo Phase (Fase Mengulangi)

  • Tujuan: Mengembalikan state database ke kondisi tepat seperti saat crash (termasuk data “kotor” dari transaksi yang belum commit) dan mengidentifikasi transaksi mana yang gagal.

  • Proses:

    1. Cari record <checkpoint L> terakhir. Inisialisasi undo-list dengan daftar L dari checkpoint.

    2. Pindai log secara MAJU (dari checkpoint ke akhir).

    3. Jika menemukan record <Ti, X, V1, V2>, selalu lakukan REDO: tulis nilai baru (V2) ke data item X.

    4. Jika menemukan <Ti start>, tambahkan Ti ke undo-list.

    5. Jika menemukan <Ti commit> atau <Ti abort>, hapus Ti dari undo-list.

  • Hasil: Database di disk kini konsisten dengan state di log. undo-list berisi semua transaksi yang dimulai tapi tidak pernah commit/abort.

2. Undo Phase (Fase Membatalkan)

  • Tujuan: Membersihkan data “kotor” yang ditulis oleh transaksi di undo-list.

  • Proses:

    1. Pindai log secara MUNDUR (dari akhir ke awal).

    2. Cek setiap log record. Jika record itu milik transaksi Ti yang ada di undo-list:

      • Lakukan UNDO (tulis nilai lama V1) dan tulis CLR ke log (seperti rollback normal).

    3. Jika menemukan <Ti start> untuk transaksi Ti yang ada di undo-list:

      • Tulis <Ti abort> ke log.

      • Hapus Ti dari undo-list.

    4. Berhenti ketika undo-list kosong.

Optimasi: Log Record Buffering

Menulis log ke stable storage (disk) adalah operasi yang lambat. Untuk efisiensi, log record ditampung dulu di buffer (memory/volatile).

  • Output: Buffer log ditulis ke disk saat buffer penuh, atau saat terjadi Log Force.

  • Log Force: Operasi yang memaksa buffer log untuk segera ditulis ke stable storage. Ini wajib dilakukan saat transaksi commit untuk menjamin Durability (karena transaksi baru dianggap commit saat record <Ti commit>-nya ada di stable storage).

Aturan Kunci: Write-Ahead Logging (WAL)

Ini adalah aturan paling fundamental dalam recovery:

Informasi UNDO (yaitu log record <Ti, X, V1, V2>) harus ditulis ke stable storage SEBELUM blok data X yang dimodifikasi oleh Ti (di buffer) diizinkan untuk ditulis ke disk.

Alasan: Jika sistem mengizinkan data X yang baru (kotor) ditulis ke disk, lalu crash sebelum log-nya ditulis, sistem tidak akan punya informasi (nilai V1) untuk melakukan UNDO. Aturan WAL memastikan sistem selalu bisa membatalkan perubahan jika diperlukan.

Optimasi: Database Buffering

Sama seperti log, blok data juga ditampung di buffer (memory). Ini melahirkan dua kebijakan:

  1. steal Policy: Blok data di buffer yang diubah oleh transaksi uncommitted (belum commit) diizinkan (“dicuri” / steal) untuk ditulis ke disk.

    • Implikasi: Membutuhkan UNDO (karena data kotor ada di disk).

  2. no-force Policy: Blok data tidak wajib “dipaksa” (force) ditulis ke disk saat transaksi commit.

    • Implikasi: Membutuhkan REDO (karena saat commit, datanya mungkin masih di buffer dan bisa hilang jika crash).

Algoritma recovery yang kita bahas (slide 23-26) adalah untuk kebijakan steal / no-force, yang paling fleksibel dan umum digunakan.

Latching: Saat blok data di buffer akan ditulis ke disk, blok itu harus di-latch. Latch adalah mekanisme proteksi internal (bukan lock transaksi) yang sangat singkat, memastikan tidak ada update lain yang terjadi pada blok itu selama proses I/O penulisan ke disk.

Summary

Algoritma recovery modern (berbasis steal/no-force) bekerja dalam dua fase: Redo Phase (memindai log maju untuk mengulang semua perubahan dan membangun undo-list) dan Undo Phase (memindai log mundur untuk membatalkan transaksi di undo-list menggunakan Compensation Log Records/CLR). Agar ini aman, sistem wajib mengikuti aturan Write-Ahead Logging (WAL), yaitu log (info undo) harus ada di stable storage sebelum data yang diubahnya boleh ditulis ke disk.

Graph View

Backlinks