ARIES

ARIES merupakan salah satu algoritma recovery yang menggunakan beberapa teknik untuk mengurangi waktu yang harus digunakan untuk recovery dan mengurangi overhead checkpointing. ARIES dapat mencegah redo yang dilakukan berulang-ulang untuk mengurangi informasi yang harus dimasukkan kedalam log. 

Tiga prinsip utama yang dimiliki oleh ARIES adalah :

• Write Ahead Logging : menjamin semua record pada log dituliskan ke stable storage.

• Repeating history during Redo : saat restart setelah crash, ARIES menampilkan kembali semua aksi yang terjadi sebelum crash. Selanjutnya aksi-aksi yang aktif saat crash akan di undo.

• Logging change during Undo : mencatat perubahan basisdata saat melakukan undo suatu transaksi, agar aksi tersebut tidak dilakukan lagi apabila terjadi pengulangan restart.

ARIES menjamin sifat atomicity dan durability transaksi dalam sebuah proses, transaksi, sistem dan media failure. Untuk itu ARIES menyimpan setiap perubahan pada basisdata dengan menggunakan sebuah log yang disebut WAL. Disamping adanya log, pada setiap page yang terpengaruh, juga dilakukan update untuk proses selanjutnya menggunakan Compensation Log Record (CLRs), updateselalu dilakukan baik itu saat transaksi berjalan secara normal ataupun pada saat dilakukan restart.

Gambar diatas merupakan salah satu contoh partial rollback. Setelah melakukan tiga update, terjadirollback terhadap dua aksi dan kemudian update dilanjutkan. Karena adanya undo terhadap dua updatemaka akan dicatat pada CLR. Pada ARIES, CLR merupakan redo-only record. Pada algoritma lainnya dapat terjadi kemungkinan undo terhadap non-CLR berulang-ulang.

ARIES, seperti yang digambarkan pada ilustrasi diatas, pada saat undo sebuah log record maka akan ditulis CLR untuk log record tersebut. Selain berisi deskripsi aksi kompensasi untuk kepentingan redo, CLR dibuat untuk menghasilkan pointer UndoNxtLSN yang menunjukkan predecessor dari log recordyang baru saja dilakukan. Informasi predecessor akan tersedia semenjak setiap record, termasuk CLR, mengandung pointer PrevLSN yang menunjukkan log record yang sebelumnya yang baru saja ditulis dengan transaksi yang sama. Dengan pointer UndoNxtLSN dapat dengan tepat ditentukan berapa banyak transaksi yang telah selesai di undo sampai saat itu.

a. Normal Processing

Dalam algoritma recovery ARIES normal processing dalam transaksi termasuk yang di-manage di dalamnya.

Update

Selama pemrosesan berjalan normal, terdapat tiga hal yang mungkin dilakukan untuk transaksi yaitu transaksi mungkin akan diteruskan, terjadi partial rollback, atau total rollback. Rollback terjadi karena adanya inisialisasi kesalahan oleh sistem atau aplikasi itu sendiri. Biasanya yang menyebabkan terjadinya rollback adalah terjadinya deadlock, error condition, integrity constraint violation,unexpected database state dan lain-lain. Jika granularity of locking adalah record, ketika akan dilakukanupdate sebuah record pada suatu page, setelah record di lock, page akan di masukkan (fixed) kedalambuffer dan di latch pada mode X. selanjutnya update dapat dilakukan. Selanjutnya log recordditambahkan pada log. LSN dari log record tersebut ditempatkan pada field page_LSN pada page dan dimasukkan ke dalam transaction table. Setelah itu maka page tersebut akan di unlatched dan unfixed, dengan kata lain page dikeluarkan dari buffer dan lock dilepaskan. Latch suatu page akan ditahan selama pemanggilan logger. Ini dilakukan untuk menjamin update pada log sama dengan update yang diterapkan pada page yang bersangkutan. Ini sangat penting jika beberapa informasi redo di log secara fisik (seperti jumlah free space pada page) dan pengulangan history dijamin berjalan sesuai dengan yang seharusnya untuk physical redo. Reader untuk page di-latch dengan mode S dan modifier untuk pageyang sama di-latch dengan mode X. Jika terdapat latch dengan mode yang sama ditahan secara bersamaan, itu menandakan adanya beberapa transaksi yang mengakses data yang berbeda.

Total or Partial Rollback

Untuk membatasi rollback transaksi maka digunakan dukungan savepoint. Pada setiap pointpengeksekusian transaksi maka akan ada savepoint. Seperti yang terjadi pada sistem DB2, savepointakan ada sebelum perintah manipulasi data SQL melakukan update pada data. Ini dibutuhkan untuk mendukung SQL statement-level atomicity. Setelah dieksekusi, transaksi atau sistem bisa meminta untuk melakukan undo untuk seluruh update yang telah dilakukan setelah adanya kehadiran outstanding savepoint. Setelah melakukan partial rollback, transaksi bisa dilanjutkan kembali. Sebuah particular savepoint tidak lagi bernilai outstanding jika rollback telah dilakukan pada savepoint itu atau sebelumsavepoint tersebut. Jika savepoint tercipta, LSN untuk log record terakhir yang dituliskan oleh transaksi, disebut saveLSN, akan disimpan pada virtual storage.

Jika savepoint muncul pada awal transaksi, dimana belum ada log record yang dituliskan, maka saveLSN diset menjadi nol. Dan jika transaksi ingin di-rollback sampai savepoint, maka akan disediakan saveLSN yang tadi telah disimpan pada virtual storage. Jika konsep savepoint diterapkan pada level user, maka diharapkan sistem tidak mengeluarkan saveLSN untuk user, tetapi dengan menggunakan nilai secara simbolis atau sequence number dan melakukan mapping untuk LSN secara internal.

Transaction termination

Transaksi dikatakan berakhir jika ada perintah commit atau abort. Dengan demikian transaksi tersebut telah selesai.

b. Restart Processing

Dalam ARIES terdapat tiga tahapan yang dilakukan selama proses recover yaitu analisis, redo dan undo.

Tahapan Analisis

Fase analisis memiliki tiga tugas yang akan dilakukan yaitu :

1. Menentukan posisi pada log yang akan digunakan untuk memulai tahapan redo.

2. Menentukan dirty page pada buffer pool pada saat terjadinya crash.

3. Mengidentifikasi transaksi yang aktif pada saat crash dan transaksi yang harus di undo.

Analisis dimulai dengan menentukan begin_checkpoint log record yang terbaru dan menginisialisasidirty page table dan transaction table dengan salinan dari strukturnya pada end_checkpointberikutnya. Dengan demikian tabel-tabel ini diinisialisasi pada kumpulan dirty page table dan transaksi yang aktif pada saat dilakukan checkpoint. Kemudian memeriksa log pada tujuan berikutnya sampai akhir log.

- Jika akhir log record untuk transaksi T ditemukan maka T akan dibuang dari transaction table karena transaksi tersebut sudah tidak aktif atau sudah selesai.

- Jika log record lain dengan end record untuk transaksi T ditemukan, maka masukan untuk T ditambahkan pada transaction table jika transaksi tersebut belum termasuk didalamnya. Selanjutnya masukan untuk T dimodifikasi sebagai berikut :

1. Field lastLSN di set dengan LSN record tersebut.

2. Jika log record merupakan commit record, status di set C, sebaliknya akan diset jadi U (undo).

- Jika log record yang dapat di redo yang mempengaruhi page P ditemukan, dan P tidak ada pada dirty page table, entry dimasukkan pada tabel dengan page id P dan recLSN sama dengan LSN log recordtersebut. LSN ini akan mengidentifikasi perubahan terlama yang mempengaruhi page P yang mungkin belum dituliskan pada disk.

Pada akhir dari tahapan analisis transaction table berisi daftar dari seluruh transaksi yang sebenarnya yang aktif pada saat terjadinya crash, transaksi tersebut merupakan transaksi-transaksi dengan status U. Dan dirty page table mengandung seluruh page yang dirty pada saat terjadinya crash, tetapi juga berisi beberapa page yang telah ditulis pada disk. Jika end_write log record yang tertulis pada penyelesaian setiap operasi, dirty page table yang dibangun selama fase analisis bisa dibuat lebih akurat, tetapi pada ARIES cost tambahan untuk penulisan end_write log record tidak dipertimbangkan untuk mendapatkan keuntungan atau kelebihan.

Tahapan Redo

Selama tahapan redo, ARIES melakukan kembali seluruh update transaksi, commit ataupun abort. Selanjutnya, jika sebuah transaksi digagalkan sebelum crash dan update telah di undo, seperti yang diindikasikan pada CLR, maka aksi yang dijelaskan pada CLR akan dilakukan kembali. Pengulangan urutan ini membedakan ARIES dengan algoritma

lainnya yang juga menggunakan WAL dan menyebabkan basisdata kembali kepada state yang sama pada saat terjadi crash.

Tahapan redo dimulai dengan log record yang mempunyai recLSN terkecil dari seluruh page yang ada pada dirty page table yang dibuat pada tahapan analisis karena log record ini mengidentifikasikanupdate terlama yang mungkin belum ditulis pada disk yang seharusnya pada saat crash. Dimulai dari log record ini, redo membaca sampai pada akhir log. Untuk setiap log record yang redoable yang ditemui,redo akan memeriksa apakah aksi yang ada di log harus dilakukan lagi atau tidak. Aksi yang akan di redosetidaknya harus memenuhi satu dari kondisi berikut ini:

• LSN log yang diperiksa >= RecLSN untuk pageID untuk log tersebut

• pageLSN untuk page tersebut < LSN log yang sedang diperiksa

Kondisi pertama dengan jelas menyatakan bahwa seluruh perubahan pada page harus sudah ditulis pada disk. Karena recLSN adalah update pertama untuk page ini yang mungkin belum ditulis ke disk, kondisi kedua berarti bahwa update yang diperiksa sudah dipropagasikan ke disk. Kondisi ketiga, diperiksa terakhir karena adanya kebutuhan untuk memanggil page, juga memastikan bahwa update yang diperiksa sudah ditulis pada disk, karena baik update ini ataupun update berikutnya sudah ditulis.

Jika aksi yang telah ada pada log harus di-redo maka:

1. aksi tersebut akan dilakukan ulang

2. pageLSN pada page di-set dengan LSN pada log record yang di-redo. Tidak ada log record tambahan yang dituliskan pada saat itu.

Pada akhir dari tahapan redo, tipe record untuk seluruh transaksi adalah dengan status C, dan di keluarkan dari transaction table.

Tahapan Undo

Tahapan undo, berbeda dengan dua tahapan sebelumnya, membaca terbalik dari akhir log. Tujuan dari tahapan ini adalah untuk membatalkan aksi yang sudah dilakukan untuk seluruh transaksi yang aktif pada saat adanya crash, oleh karena itu akan lebih efektif untuk menggagalkan (abort) transaksi tersebut. Kumpulan dari transaksi ini diidentifikasi pada transaction table yang dibuat pada saat tahapan analisis. Undo dimulai dengan transaction table yang dibangun pada saat analisis, yang mengidentifikasi seluruh transaksi yang aktif pada saat adanya crash, termasuk LSN dari log recordyang terbaru (field lastLSN) untuk setiap transaksi. Transaksi tersebut disebut dengan loser transaction. Seluruh aksi dari loser transaction harus di-undo, dan selanjutnya, aksi-aksi ini harus di-undo dengan kebalikannya seperti yang tertera pada log. Kumpulan nilai lastLSN untuk seluruh loser transactiondisebut ToUndo. Secara berulang-ulang undo memilih nilai LSN yang terbesar pada kumpulan dan proses ini, sampai ToUndo habis. Untuk memproses sebuah log record :

1. Jika itu adalah CLR, dan nilai undoNextLSN bukan null, nilai undoNextLSN ditambahkan padaToUndo; jika undoNextLSN null dan end record ditulis untuk transaksi karena telah selesai di-undo, dan CLR sudah di-discard.

2. Jika itu adalah update record, CLR ditulis dan aksi yang berhubungan akan di undo. Dan nilai prevLSN pada update log record akan ditambahkan pada ToUndo.

Pada saat ToUndo sudah kosong, maka tahapan undo telah selesai dilakukan. Restart selesai dan sistem bisa berjalan dengan operasi yang normal.