School of Information Systems

Database Recovery Techniques

23 Aug 2021

Database systems dapat mengalami failures (contoh: data loss, hacked, dll), tetapi data yang disimpan di dalamnya harus tetap bisa diakses (selalu available) saat dibutuhkan. Ketika database mengalami failure, perlu dilakukan database recovery, yaitu proses restorasi database dan data (terhapus, hacked, atau rusak) ke consistent state (state sebelum terjadi system crash). Dalam proses database recovery, atomicity of transactions perlu dipertahankan agar proses recovery dapat dilakukan dengan cepat dan efisien. Atomicity berarti transaksi yang telah dilakukan harus berhasil memberikan efek pada database secara permanen atau tidak memberikan efek sama sekali pada database.

Teknik-teknik yang digunakan untuk memulihkan (recover) data loss akibat system crash, transaction errors, virus, dll, disebut Database Recovery Techniques. Recovery Techniques bergantung pada file system log yang mengandung informasi tentang awal dan akhir setiap transaksi dan updates yang terjadi pada transaksi tersebut. System log merekam semua proses transaksi yang mempengaruhi database. Informasi dari system log ini dibutuhkan untuk melakukan recover saat terjadi kegagalan transaksi.

Ada beberapa teknik untuk memulihkan database dan mempertahankan atomicity transaksi, yaitu Manual Reprocessing dan Automated Recovery:

1. Manual Reprocessing

  • Database di backup (database save) secara berkala dan semua transaksi yang dilakukan sejak save terakhir di-record dan disimpan di log.
  • Jika system crash, backup yang paling terakhir di restore dan reapply updates semua transaksi (menggunakan log file) pada backup sampai ke kondisi sebelum crash terjadi.
  • Kekurangan dari teknik Manual Reprocessing:
    • Butuh waktu untuk reapply semua transaksi
    • Transaksi dapat mengandung potential failures lainnya
    • Proses reapplying concurrent transactions sesuai urutan aslinya sulit dilakukan

2. Automated Recovery

  • Teknik Automated Recovery menggunakan log file (terpisah dari data) yang mencatat semua perubahan yang dibuat oleh transaksi pada database. Log file disebut juga sebagai Journal.
  • Transaction log mengandung informasi yang berguna untuk proses recovery, seperti: transaction identifier, date, time, user yang menjalankan transaksi, before images dan after images
  • Jika database inconsistent, transaction changes yang menyebabkan inconsistency dapat di undo / redo transactions untuk memastikan updates mencapai secondary storage. Backup tidak dibutuhkan, karena database dapat di restore menggunakan before dan after image di dalam log file
  • Before Image: Copy dari table record (data item) sebelum dirubah oleh transaksi
  • After Image: Copy dari table record (data item) sesudah diubah oleh transaksi
  • Rollback: Undo semua partially completed transactions (transaksi yang masih in progress ketika terjadi crash) dengan cara menerapkan before images ke database
  • Rollforward: Redo transactions dengan cara menerapkan after images ke database (ini dilakukan untuk transaksi yang telah di commit sebelum terjadi crash)
  • Proses Automated Recovery menggunakan rollback dan rollforward untuk me-restore database
  • Checkpoints juga dapat dilakukan di antara database saves:
  • DBMS menghapus semua pending transactions dan menulis semua data ke disk dan transaction log
  • Database dapat di recover dari last checkpoint dalam waktu yang lebih singkat

Beberapa tipe teknik Automated Recovery yaitu: Deferred Update dan Immediate Update, dan Shadow Paging.

  1. Deferred Update (No-undo/redo algorithm)

Teknik ini menunda write updates pada database di disk secara physical sampai transaction mencapai commit point. Selama transaction berlangsung (belum mencapai commit), semua transaction updates di catat di log dan local transaction workspace. Setelah transaction di commit dan log di write ke disk, update data items pada database. Jika transaction gagal sebelum mencapai commit, tidak perlu melakukan UNDO, karena transaction belum mempengaruhi database sama sekali. Namun REDO updates pada commited transactions dapat diperlukan karena effect nya mungkin belum mencapai database.

Aturan pada Deffered Update adalah:

  • transaction tidak dapat merubah items apapun pada database sampai transaction di commit
  • transaction dapat tidak di commit sampai semua write operations berhasil di record pada log (perlu mengecek bahwa log sudah di write pada disk)

 Tahap dalam deffered update adalah sebagai berikut:

  1. Saat transaction dimulai (start), tulis entry start_transaction(T) pada log untuk memulai execution
  2. Saat operation yang dilakukan akan merubah value database, tulis log entry write_item(T, x, old_value, new_value). transaction T akan merubah value item X dari old_value menjadi new_value.
  3. Saat transaction akan di commit, tulis log record commit(T) untuk menulis semua log records ke disk
  4. Commit transaction menggunakan log untuk menuliskan updates pada database.
  5. Jika transaction berhenti (abort), hapus log records dan jangan tuliskan perubahan pada disk

Database tidak pernah di update sampai setelah transaction di commit, dan tidak perlu melakukan undo operations. Deffered Update dikenal sebagai NO-UNDO/REDO algorithm. REDO dibutuhkan jika system fails setelah transaction di commit namun sebelum semua perubahannya di record dalam database (transaction operations di redo dari log entries)

Kelebihan Deferred Updates:

  • Recovery lebih mudah: transaction yang sudah mencapai commit (dari log) di apply pada database, transaction yang belum mencapai commit diabaikan
  • Cascading rollback tidak terjadi karena tidak ada transaction yang melihat transaction lain sampai transaction tersebut di commit

Kekurangan Deffered Updates: limited concurrency

  1. Immediate Update (Undo/redo algorithm)

Pada immediate update, database dapat langsung di update oleh transaction operations sebelum transaction tersebut mencapai commit point. Namun, operations tersebut direcord dalam log di disk sebelum di apply pada database (write-ahead log protocol), sehingga recovery masih dapat dilakukan. Jika transaction gagal mencapai commit point, transaction harus di rollback dengan cara undo effects dari write operation tersebut, maka dibutuhkan undo dan redo. Undo operations dilakukan secara reverse order sesuai penulisan pada log. Tahap pada Immediate Update adalah:

  1. Saat transaction dimulai (start), tulis entry start_transaction(T) pada log untuk memulai execution
  2. Saat operation yang dilakukan akan merubah value database, tulis log entry write_item(T, x, old_value, new_value). transaction T akan merubah value item X dari old_value menjadi new_value.
  3. Write log pada disk
  4. Setelah log record di write, write update pada database buffers
  5. Write database buffers pada disk
  6. Saat transaction akan di commit, tulis log record commit(T) untuk menulis semua log records ke disk
  7. Write log pada disk

Kelebihan Immediate Updates: higher concurrency karena transactions write secara continuously ke database (tidak perlu menunggu commit point)

Kekurangan Immediate Updates: cascading rollbacks, time consuming

  1. Shadow Paging

Database tidak dimodifikasi secara langsung, namun copy yang disimpan di permanent storage (disk) dibuat dan semua modifikasi dilakukan pada copy. Sementara, database versi lama tetap utuh. Setelah transaction di commit, copy yang sudah dimodifikasi me-replace database original secara atomic (replacement dilakukan secara keseluruhan atau tidak sama sekali). Jika terjadi system crash pada saat ini, database versi lama masih available untuk melakukan recovery.

Cara kerja shadow paging adalah sebagai berikut:

Selama proses transaction berlangsung, maintain 2 page tables, yaitu: current page dan shadow page table. Ketika transaction dimulai, kedua page tables identik. Selama proses transaction, Shadow page table tidak pernah diubah dan digunakan untuk restore database jika terjadi failure. Current page table me-record semua updates pada database. Semua input dan output operations menggunakan current page table untuk me-locate database pages pada disk.Setelah transaction selesai, current page table menjadi shadow page table.

Kelebihan: tidak ada overhead untuk writing log records, recovery lebih cepat

Kekurangan: data jadi terpencar, setelah setiap transaction selesai old pages harus dibuang, complex storage management strategies

Referensi:

https://www.ques10.com/p/29171/describe-the-shadow-paging-recovery-technique/

https://www.geeksforgeeks.org/database-recovery-techniques-in-dbms/

https://dbms-ii.blogspot.com/2010/03/defferred-update-method.html

https://whatisdbms.com/database-recovery-in-dbms-and-its-techniques/

Evaristus Didik M