Recovery Alternatif - Shadow Paging

Back to IF3140 Sistem Basis Data

Metode Alternatif Recovery: Shadow Paging

Questions/Cues

• Apa itu Shadow Paging?

• Apa perbedaan Current Page Table vs Shadow Page Table?

• Mana yang disimpan di nonvolatile?

• Bagaimana proses update data di Shadow Paging?

• Apa itu Copy-on-Write?

• Bagaimana proses Commit transaksi?

• Bagaimana proses Recovery dari crash?

• Apa Keuntungan (Advantages) Shadow Paging?

• Apa Kerugian (Disadvantages) Shadow Paging?

• Mengapa concurrency sulit diimplementasikan?

Reference Points

• Slides “12 - Recovery System - 2.pdf” (Slide 36-40)

Apa itu Shadow Paging?

Shadow Paging adalah sebuah teknik recovery alternatif yang tidak menggunakan log. Ide utamanya adalah tidak pernah menimpa (overwrite) data yang konsisten di disk, melainkan menulis versi baru dari data di lokasi lain.

Teknik ini bergantung pada Page Table (seperti di OS) yang memetakan alamat virtual database ke alamat fisik di disk.

Shadow Paging memelihara dua page table selama transaksi berjalan:

1. Shadow Page Table: Ini adalah salinan page table yang “valid” dan konsisten. Isinya menunjuk ke blok-blok data di disk dari commit terakhir. Page table ini tidak pernah dimodifikasi dan disimpan di nonvolatile storage.

2. Current Page Table: Ini adalah salinan dari shadow page table yang digunakan oleh transaksi saat ini. Page table inilah yang dimodifikasi saat transaksi berjalan.

Proses Update Data (Copy-on-Write)

Saat sebuah transaksi Ti ingin menulis/mengubah page (blok) X untuk pertama kalinya:

1. Sistem tidak langsung mengubah page X yang asli.

2. Sistem menemukan page kosong di disk, lalu menyalin (copy) isi page X ke page baru tersebut (ini disebut Copy-on-Write).

3. Current Page Table diperbarui: entry untuk page X sekarang menunjuk ke copy yang baru.

4. Shadow Page Table tetap tidak berubah (masih menunjuk ke page X yang lama/asli).

5. Transaksi melakukan operasi write pada copy yang baru tersebut.

(Lihat slide 38: Page 4 akan di-update. Shadow tetap menunjuk ke page 4 lama, Current menunjuk ke page 4 baru yang disalin di lokasi lain di disk).

Proses Commit Transaksi

Proses commit adalah operasi “ajaib” yang membuat semua perubahan transaksi menjadi permanen secara atomik.

6. Ada satu pointer khusus di nonvolatile storage yang selalu menunjuk ke shadow page table yang aktif.

7. Saat transaksi Ti ingin commit:

   a. Sistem menulis semua page yang dimodifikasi (yang ditunjuk current) ke disk.

   b. Sistem menulis current page table ke disk.

   c. Sistem secara atomik (satu operasi tak terpisahkan) memindahkan pointer khusus tadi agar menunjuk ke current page table.

8. Pada titik ini, current page table telah resmi menjadi shadow page table yang baru. Transaksi telah commit. Page lama yang ditunjuk oleh shadow page table sebelumnya kini menjadi garbage (sampah).

Proses Recovery dari Crash

Recovery di shadow paging sangat sederhana dan cepat:

• Skenario Crash: Sistem crash di tengah transaksi (sebelum pointer dipindah).

• Proses Recovery:

  1. Semua yang ada di memory (termasuk current page table) hilang.

  2. Sistem restart dan melihat pointer khusus di disk.

  3. Pointer tersebut masih menunjuk ke shadow page table yang lama (karena commit belum terjadi).

  4. Sistem menggunakan shadow page table tersebut. Semua copy page baru yang dibuat transaksi (namun tidak pernah di-commit) otomatis terabaikan.

• Hasil: Database kembali ke state konsisten terakhir. Tidak perlu UNDO atau REDO.

Keuntungan dan Kerugian

Keuntungan (Advantages):

1. Tidak ada overhead penulisan log.

2. Recovery trivial dan sangat cepat (hampir instan), karena tidak perlu memindai log.

Kerugian (Disadvantages):

1. Commit Overhead Tinggi: Saat commit, semua page yang diubah dan page table itu sendiri harus di-flush ke disk.

2. Fragmentasi Data: Page yang secara logis berurutan (misal: page 4 dan 5) bisa jadi terletak berjauhan secara fisik di disk, memperlambat scan data.

3. Garbage Collection: Sistem memerlukan proses latar belakang untuk mengumpulkan page-page lama yang sudah tidak terpakai (setelah commit).

4. Sulit untuk Concurrency: Sangat sulit untuk mengizinkan banyak transaksi berjalan bersamaan. Jika Transaksi A dan B berjalan, lalu A commit, B akan “dipaksa” ikut commit padahal belum selesai.

Summary

Shadow Paging adalah teknik recovery non-log yang menjaga dua page table: Shadow (state konsisten terakhir di disk) dan Current (yang dimodifikasi transaksi). Perubahan data dilakukan dengan Copy-on-Write, di mana page baru disalin dan current table diubah untuk menunjuk ke salinan. Commit adalah operasi atomik memindahkan pointer disk agar menunjuk ke current table, menjadikannya shadow table baru. Recovery-nya instan (cukup gunakan shadow table lama) sehingga tidak perlu undo/redo, namun teknik ini memiliki commit overhead tinggi, menyebabkan fragmentasi, dan sangat sulit mendukung concurrency.

Additional Information

Pendalaman Teknis: Shadow Paging dan File System Modern

Meskipun Shadow Paging (dalam bentuk murninya) jarang digunakan di database relasional modern karena masalah concurrency dan fragmentasi, ide intinya (yaitu Copy-on-Write / CoW) sangat sukses dan menjadi dasar dari banyak teknologi lain:

1. File Systems: ZFS (Zettabyte File System) dan Btrfs (B-tree File System) menggunakan CoW secara ekstensif. Mereka tidak pernah menimpa data. Saat Anda mengubah file, mereka menulis blok baru di lokasi lain dan memperbarui metadata (setara page table) untuk menunjuk ke sana. Ini membuat fitur seperti snapshot (yang pada dasarnya adalah “membekukan” shadow page table) menjadi sangat murah dan instan.

2. Virtual Machine (VM) Snapshots: Saat Anda mengambil snapshot dari VM, hypervisor berhenti menulis ke disk virtual utama (file VDI/VMDK) dan mulai menulis semua perubahan ke file disk diferensial baru. Disk utama bertindak sebagai shadow, dan disk diferensial bertindak sebagai current.

3. Git (Version Control): Meskipun tidak di level blok disk, Git bekerja dengan konsep serupa. Commit adalah snapshot (mirip shadow) yang tidak bisa diubah. Perubahan Anda terjadi di working directory (mirip current).

Pendalaman Teknis: Mengapa Concurrency Sangat Sulit?

Bayangkan Transaksi T1 mengubah page A dan Transaksi T2 mengubah page B, keduanya berjalan bersamaan.

4. T1 membuat A_copy dan Current_Table menunjuk ke A_copy.

5. T2 membuat B_copy dan Current_Table menunjuk ke B_copy.

6. Sekarang, T1 ingin commit.

7. T1 akan memaksa pointer disk menunjuk ke Current_Table.

8. Masalah: Current_Table ini juga berisi perubahan dari T2 (yaitu pointer ke B_copy) yang padahal belum selesai!

9. Commit dari T1 secara tidak sengaja ikut meng-commit perubahan T2 yang belum selesai. Ini adalah pelanggaran berat Isolation (huruf ‘I’ dalam ACID).

Log-based recovery jauh lebih unggul dalam menangani concurrency karena setiap transaksi memiliki record-nya sendiri di log.

Sumber & Referensi Lanjutan:

• Buku: Silberschatz, Korth, Sudarshan, “Database System Concepts”, 7th Ed, Chapter 19.8.

• Konsep: “Copy-on-Write (CoW)”