Semester Ganjil 2014 Fak. Teknik Jurusan Teknik Informatika Universitas Pasundan Caca E. Supriana, S.Si.,MT.
[email protected]
Materi 1. Pengantar 2. Recovery Manager 3. Log‐based Recovery 4. Media Failure 5. Shadow Paging
2
1 Pengantar 1. Pengantar y Semua database yang membaca / menulis berada dalam y y y y y y y y
sebuah transaksi b h k Transaksi memiliki properti"ACID“ (S) A Atomicity – i i seluruh instruksi atau tidak l h i k i id k Konsistensi ‐ menjaga integritas basis data I l i mengeksekusi seolah‐olah mereka berjalan Isolasi ‐ k k i l h l h k b j l sendiri Durability ‐ hasilnya tidak akan kalah oleh kegagalan Pemulihan subsistem menjamin Atomicity & Durability Kontrol konkurensi menjamin Isolasi Program aplikasi menjamin Konsistensi 3
Tujuan Recovery y Sebuah database dapat menjadi tidak konsisten karena
kegagalan transaksi (abort) y kegagalan sistem database (mungkin disebabkan oleh kerusakan OS) y Media crash (disk data rusak) ( ) y Sistem pemulihan memastikan database berisi persis update tersebut dan dihasilkan oleh transaksi yang dilakukan yaitu atomicity dan daya tahan meskipun dilakukan yaitu atomicity dan daya tahan, meskipun kegagalan
4
Storage Model y Database Stabil – dapat bertahan dari kegagalan sistem
p y Cache (volatile) ‐ berisi salinan dari beberapa halaman yang hilang oleh kegagalan sistem
Fetch, Flush Pin, Unpin, Deallocate Read, Write
Cache Manager
Stable Database Log
Read, Write Cache 5
Cache y Cache adalah komponen yang menyimpan data secara
transparan sehingga permintaan selanjutnya untuk data yang dapat dilayani lebih cepat. y Data yang disimpan dalam cache mungkin nilai‐nilai yang d d l h k l l telah dihitung sebelumnya atau duplikat dari nilai‐nilai asli yang disimpan di tempat lain. Jika data yang diminta terkandung dalam cache (cache hit) permintaan ini dapat terkandung dalam cache (cache hit), permintaan ini dapat dilayani dengan hanya membaca cache, yang relatif lebih cepat. Jika tidak (cache miss), data harus menghitung ulang atau diambil dari lokasi penyimpanan aslinya, yang relatif lebih lambat. y Oleh karena itu, semakin besar jumlah permintaan yang p y , p j dapat dilayani dari cache, semakin cepat kinerja sistem secara keseluruhan menjadi. 6
Cache (lanjutan) y Hardware mengimplementasikan cache blok memori
untuk penyimpanan sementara data yang mungkin akan digunakan lagi CPU dan hard drive sering akan digunakan lagi. CPU dan hard drive sering menggunakan cache, seperti halnya web browser dan server web. y Cache terdiri dari pool (kumpulan) entri. Setiap entri memiliki datum (sepotong data) ‐ salinan datum yang sama di beberapa tempat penyimpanan. Setiap entri juga memiliki tag, yang menentukan identitas datum di tempat penyimpanany ang masuk adalah salinan. di tempat penyimpanany ang masuk adalah salinan 7
Stable Storage Stab e Sto age y Write (P) akan menimpa seluruh isi P pada disk y Jika Write tidak berhasil, kesalahan mungkin terdeteksi
pada Read berikutnya ... , misalnya Page checksum error Æ halaman rusak ... atau mungkin tidak halaman rusak atau mungkin tidak y Write dengan benar, write ke lokasi yang salah y Write merupakan operasi yang atomik sehubungan dengan kegagalan dan keberhasilan pelaksanaan yang dapat ditentukan dengan prosedur pemulihan.
8
y Cache dibagi menjadi slot berukuran page. g j p g y Setiap slot akan mengatakan jika page itu diperbarui
j sejak terakhir ditulis ke disk. y Jumlah pin memberitahu jumlah pin ops tanpa unpins Page g Dirtyy Bit Cache Address Pin Count P2 1 91976 1 P47 0 812 2 P21 1 10101 0 • Fetch(P) - read P ke dalam cache slot. Mengembalikan alamat slot. • Flush(P) - Jika P’s slot dirty dan unpinned, tulis ke disk • Pin(P) – membuat pin tidak bisa di Flush. 9 • Deallocate – P dapat digunakan kembali
M j R d d l h d i h j y Manajer Record adalah pengguna utama dari cache manajer. y Setelah memanggil Fetch (P) dan Pin (P), ia mengendalikan
akses ke catatan pada halaman. akses ke catatan pada halaman
Query Optimizer Query Executor Database Access Method System ((record-oriented files)) Page-oriented Files Database
Fetch, Flush Pin, Unpin, Deallocate Recovery manager Cache manager P Page fil file manager 10
Log y Sebuah catatan file sekuensial menggambarkan update : alamat halaman diperbarui id transaksi yang melakukan update id k i l k k d sebelum‐gambar dan setelah‐gambar halaman y Setiap kali memperbarui cache, juga update log Setiap kali memperbarui cache juga update log y Log catatan untuk Commit (Ti) dan Abort (Ti) y Beberapa sistem lama berpisah sebelum‐gambar dan
setelah‐gambar ke dalam file log yang terpisah. y Jika konflik op i dengan dan mengeksekusi sebelum op k , J p g g p , maka catatan log op i yang harus mendahului catatan log op k ini y pemulihan akan memutar ulang operasi dalam rangka log record 11
Log D i l i k i j k y Dengan catatan operasi granularity, kunci jangka pendek, yang disebut kait, mengontrol update record bersamaan ke halaman yang sama: ‐ Fetch(P) read P into cache y Pin(P) y write lock (P) y latch P y update P y log the update to P y unlatch P y Unpin(P)
ensure P isn t flushed ensure P isn’t flushed for two‐phase locking g get exclusive access to P update P in cache append it to the log release exclusive access allow P to be flushed
y Tidak ada deadlock untuk kait. 12
2. Recovery Manager y Processes Commit, Abort and Restart y Commit(T) y Menulis page T yang diperbarui untuk penyimpanan atomik stabil, bahkan jika sistem crash. y Abort(T) b ( ) y Undo penulisan T y Restart = recover dari system failure R t t d i t f il y Abort semua transaksi yang tidak dilakukan pada saat kegagalan sebelumnya y Perbaiki penyimpanan stabil sehingga mencakup semua transasksi berkomitmen menulis dan tidak ada yang tidak mengikat (sehingga dapat dibaca oleh transaksi baru) ik ( hi d dib l h k i b ) 13
Recovery Manager Model Transaction 1
Transaction 2
Transaction N
Commit, Abort, Restart Recovery Manager Pin, Unpin Fetch Read, Write
Flush Deallocate
Cache Manager
Stable Database Log
Read, Write
Read, Write
Cache Fetch, dealloc for normal operat’n Restart uses Fetch, Pin, Unpin 14
Implementasi Abort(T) y Misalkan T menulis page P. y Jika P tidak ditransfer ke penyimpanan yang stabil,?
Kemudian DEALLOCATE Slot cache K di DEALLOCATE Sl t h y Jika dipindahkan, maka before‐image P harus dalam penyimpanan stabil (tidak bisa membatalkan setelah kegagalan sistem) y Undo Rule ‐ Jangan flush update mengikat P hingga P J g p g gg before‐image stabil. (Memastikan membatalkan adalah mungkin.) y Write‐Ahead Log Protocol ‐ Jangan ... sampai P before‐image di log
15
Menghindari Undo M hi d i l h i l h U d R l d id k y Menghindari masalah tersirat oleh Undo Rule dengan tidak y y y y
pernah flush update uncommitted. Menghindari logging stabil before‐image Menghindari logging stabil before image Tidak perlu membatalkan update setelah kegagalan sistem Sebuah algoritma pemulihan membutuhkan pembatalan jika pembaruan dari transaksi uncommitted dapat memerah. Biasanya disebut mencuri algoritma, karena memungkinkan y g , g halaman cache yang kotor akan "dicuri."
16
Implementasi Commit(T) C i h ik J di h dil k k l h i y Commit harus atomik. Jadi harus dilaksanakan oleh write disk. y Misalkan T menulis P, T berkomitmen, dan kemudian sistem Misalkan T menulis P T berkomitmen dan kemudian sistem gagal. P harus dalam penyimpanan yang stabil. y Redo Redo aturan ‐ atu a Ja Jangan melakukan transaksi sampai after‐ ga e a u a t a sa s sa pa a te image dari semua page yang terdapat pada penyimpanan yang stabil (dalam database atau log). (Memastikan Redo adalah mungkin.) d l h ki ) y Sering disebut aturan Force‐At‐Commit
17
Menghindari Redo y Untuk menghindari redo, flush semua update T ke database
stabil. (Mereka harus dalam penyimpanan stabil.) y Biasanya disebut algoritma Force, karena update dipaksa untuk disk sebelum Commit. y Sangat mudah, karena tidak perlu pembukuan stabil after‐ Sangat mudah karena tidak perlu pembukuan stabil after image y Sebaliknya, algoritma pemulihan membutuhkan mengulang Sebaliknya algoritma pemulihan membutuhkan mengulang jika transaksi dapat melakukan sebelum semua pembaruan yang berada dalam database yang stabil.
18
Menghindari Undo dan Redo y Untuk menghindari undo dan redo yang pernah flush update
uncommitted (untuk menghindari pembatalan), dan flush semua update T ke database stabil sebelum dilakukan (untuk menghindari redo). y Oleh karena itu perlu menginstal semua update transaksi ke dalam database yang stabil dalam menulis ke sebuah disk y Hal ini dapat dilakukan, tetapi tidak efisien untuk transaksi pendek dan update record‐level.
19
Implementasi Restart y Untuk pulih dari kegagalan sistem Abort transaksi yang gagal Untuk setiap transaksi berkomitmen, ulangi update yang ada di log bukan database stabil g y Melanjutkan proses transaksi normal y Operasi idempotent ‐ p p banyak eksekusi operasi memiliki efek y p
yang sama sebagai salah satu eksekusi y Restart harus idempotent. Jika itu terganggu oleh kegagalan, maka kembali mengeksekusi dari awal. k k b li k k i d i l y Restart kontribusi untuk ketersediaannya.
20
3. Log‐based Recovery y Logging adalah mekanisme yang paling populer untuk
menerapkan algoritma pemulihan. y Manajer pemulihan mengimplementasikan : y Commit ‐ by writing a commit record to the log and flushing
the log (satisfies the Redo Rule) y Abort ‐ by using the transaction’s log records to restore before‐ images y Restart ‐ by scanning the log and undoing and redoing operations as necessary
y Algoritma yang cepat karena mereka menggunakan logika g y g p gg g
sekuensial I/O di tempat database acak I/O. Algoritma sangat mempengaruhi TP dan Restart kinerja.
21
4. Media Failures 4. Media Failures y Kegagalan Media adalah hilangnya beberapa penyimpanan stabil. y Kebanyakan disk telah MTBF (mean time between failure)lebih dari 10 K b k di k t l h MTBF ( ti b t f il )l bih d i y y y y y y y y
tahun Namun, jika Anda memiliki 10 disk ... Jadi shadow disk menjadi penting Menulis ke kedua salinan. Handshake antara penulisan ke disk untuk menghindari mode kegagalan umum (misalnya listrik mati) Layanan setiap membaca dari satu salinan Untuk memunculkan bayangan baru Menyalin trek dari disk yang baik ke disk baru, satu per satu Sebuah Write pergi ke kedua disk jika lagu tersebut telah disalin Read yang pergi ke disk yang baik, sampai trek disalin
22
RAID y RAID (redundant array of independent disks) adalah
teknologi virtualisasi penyimpanan data yang menggabungkan beberapa komponen disk drive ke dalam sebuah unit logis untuk tujuan redundansi data atau peningkatan y Menggunakan array dari N disk secara paralel y Sebuah stripe adalah array dari blok ke‐i dari setiap disk y Sebuah stripe dipartisi sebagai berikut: ... M data blocks
... N-M error correction blocks 23
Dimana Menggunakan Disk redundansi? y Lebih baik untuk kedua DB dan log y Tapi setidaknya untuk log y dalam algoritma undo, itu satu‐satunya tempat yang
memiliki tertentu sebelum image y dalam algoritma redo, itu satu‐satunya tempat yang d l l i d i memiliki tertentu setelah image y Jika tidak memiliki shadow log, itu adalah titik Jika tidak memiliki shadow log itu adalah titik tunggal kegagalan
24
5. Shadow Paging y Shadow paging adalah teknik untuk memberikan atomicity
dan durability (dua dari sifat ACID) dalam sistem database. Halaman dalam konteks ini mengacu pada unit penyimpanan fisik (mungkin pada hard disk) biasanya dari urutan (order) ke fisik (mungkin pada hard disk), biasanya dari urutan (order) ke byte. y Shadow paging adalah teknik copy‐on‐write untuk menghindari p penempatan update page. Sebaliknya, saat halaman harus p p p g y dimodifikasi, shadow paging dialokasikan. Karena halaman bayangan tidak memiliki referensi (dari halaman lain pada disk), dapat dimodifikasi secara bebas, tanpa memperhatikan kendala konsistensi dll konsistensi, dll. y Ketika page siap menjadi durable, semua halaman asli diperbarui untuk merujuk halaman pengganti yang baru sebagai gantinya. Karena halaman tersebut "diaktifkan" hanya bila sudah siap, itu b berarti menjadi atomik. d k 25
Shadow Paging (lanjutan) y Setiap file F dikelola melalui tabel halaman p y Setiap transaksi T update F melalui tabel halaman pribadi y Commit T dengan mengganti tabel halaman publik oleh salah
satu private
D I S K
Initial State
Master a b
Pt[a,1] 1 2 3 ...
P1a old
Pt[b,1] 1 2 3 ...
P1b old
P2a old
P2b old
P1a new P2a P2 new
P2b new
Pt[a,2] [ , ] 1 2 Main 3 Memory ... Pt[b,2] Pt[b 2] 1 2 3 ... 26
Shadow Paging (lanjutan)
D I S K
Initial State
Master a b
P1a old
Pt[a,1] 1 2 3 ...
P2a old
Pt[b,1] 1 2 3 ...
P1a new P2a new
P1b old P2b old
P2b new
Pt[a,2] 1 2 Master´ 3 a ... b Pt[b,2] 1 2 3 ...
Master Pointer To commit, replace this pointer by this one
27
Shadow Paging (lanjutan) y Untuk mengunci halaman, harus mengunci setiap tabel
halaman sementara memperbarui pointer dan mentransfer ke disk. y Mempertimbangkan diperbaruinya dua transaksi dari halaman yang berbeda dari file yang sama dan melakukan secara bersamaan. y menghitung update disk per transaksi
28
