1 Lecture 9-10: Recovery Friday, April 16 and Monday, April 19, 2010 Dan Suciu -- 444 Spring 20102 Outline • Disks 13.2 • Undo logging 17.2 • Redo logging 17.3 • Redo/undo 17.4 Dan Suciu -- 444 Spring 2010Project 2 What you will learn: • Connect to db and call SQL from java (read 9.6) • Dependent joins • Integrate two databases • Transactions Amount of work: • 20 SQL queries + 180 lines Java ≈ 12 hours (?) 3Project 2 • Database 1 = IMDB on SQL Server • Database 2 = you create a CUSTOMER db on postgres – Customers – Rentals – Plans 4 Dan Suciu -- 444 Spring 20105 The Mechanics of Disk Mechanical characteristics: • Rotation speed (5400RPM) • Number of platters (1-30) • Number of tracks (<=10000) • Number of bytes/track(105) Platters Spindle Disk head Arm movement Arm assembly Tracks Sector Cylinder Unit of read or write: disk block Once in memory: page Typically: 4k or 8k or 16k6 RAID Several disks that work in parallel • Redundancy: use parity to recover from disk failure • Speed: read from several disks at once Various configurations (called levels): • RAID 1 = mirror • RAID 4 = n disks + 1 parity disk • RAID 5 = n+1 disks, assign parity blocks round robin • RAID 6 = “Hamming codes” Dan Suciu -- 444 Spring 2010 Not required for exam, but interesting reading in the book7 Disk Access Characteristics • Disk latency = time between when command is issued and when data is in memory • Disk latency = seek time + rotational latency – Seek time = time for the head to reach cylinder • 10ms – 40ms – Rotational latency = time for the sector to rotate • Rotation time = 10ms • Average latency = 10ms/2 • Transfer time = typically 40MB/s • Disks read/write one block at a time Dan Suciu -- 444 Spring 2010 Large gap between disk I/O and memory Buffer pool8 Buffer Management in a DBMS • Data must be in RAM for DBMS to operate on it! • Table of <frame#, pageid> pairs is maintained DB MAIN MEMORY DISK disk page free frame Page Requests from Higher Levels BUFFER POOL choice of frame dictated by replacement policy READ WRITE INPUT OUTUPT Dan Suciu -- 444 Spring 20109 Buffer Manager Page replacement policies • LRU = expensive • Clock algorithm = cheaper alternative Both work well in OS, but not always in DB Dan Suciu -- 444 Spring 2010Least Recently Used (LRU) Dan Suciu -- 444 Spring 2010 10 P5, P2, P8, P4, P1, P9, P6, P3, P7 Read(P6) P6, P5, P2, P8, P4, P1, P9, P3, P7 Input(P10) P10, P6, P5, P2, P8, P4, P1, P9, P3 Read(P10)Buffer Manager DBMS build their own buffer manager and don’t rely on the OS • Better control for transactions – Force pages to disk – Pin pages in the buffer • Tweaks to LRU/clock algorithms for specialized accesses, s.a. sequential scan Dan Suciu -- 444 Spring 2010 1112 Transaction Management and the Buffer Manager The transaction manager operates on the buffer pool • Recovery: ‘log-file write-ahead’, then careful policy about which pages to force to disk • Concurrency control: locks at the page level, multiversion concurrency control13 Transaction Management Two parts: • Recovery from crashes: ACID • Concurrency control: ACID Both operate on the buffer pool Dan Suciu -- 444 Spring 201014 Recovery Type of Crash Prevention Wrong data entry Constraints and Data cleaning Disk crashes Redundancy: e.g. RAID, archive Fire, theft, bankruptcy… Remote backups System failures: e.g. power DATABASE RECOVERY15 Main Idea for Recovery • Write-ahead log = – A file that records every single action of all running transactions – After a crash, transaction manager reads the log and finds out exactly what the transactions did or did not Dan Suciu -- 444 Spring 201016 Transactions • Assumption: the database is composed of elements – Usually 1 element = 1 block – Can be smaller (=1 record) or larger (=1 relation) • Assumption: each transaction reads/writes some elements Dan Suciu -- 444 Spring 201017 Primitive Operations of Transactions • READ(X,t) – copy element X to transaction local variable t • WRITE(X,t) – copy transaction local variable t to element X • INPUT(X) – read element X to memory buffer • OUTPUT(X) – write element X to disk Dan Suciu -- 444 Spring 201018 Example Atomicity: BOTH A and B are multiplied by 2 Dan Suciu -- 444 Spring 2010 START TRANSACTION READ(A,t); t := t*2; WRITE(A,t); READ(B,t); t := t*2; WRITE(B,t) COMMIT;19 Action t Mem A Mem B Disk A Disk B INPUT(A) 8 8 8 READ(A,t) 8 8 8 8 t:=t*2 16 8 8 8 WRITE(A,t) 16 16 8 8 INPUT(B) 16 16 8 8 8 READ(B,t) 8 16 8 8 8 t:=t*2 16 16 8 8 8 WRITE(B,t) 16 16 16 8 8 OUTPUT(A) 16 16 16 16 8 OUTPUT(B) 16 16 16 16 16 Buffer pool Disk Transaction READ(A,t); t := t*2; WRITE(A,t); READ(B,t); t := t*2; WRITE(B,t)20 Action t Mem A Mem B Disk A Disk B INPUT(A) 8 8 8 READ(A,t) 8 8 8 8 t:=t*2 16 8 8 8 WRITE(A,t) 16 16 8 8 INPUT(B) 16 16 8 8 8 READ(B,t) 8 16 8 8 8 t:=t*2 16 16 8 8 8 WRITE(B,t) 16 16 16 8 8 OUTPUT(A) 16 16 16 16 8 OUTPUT(B) 16 16 16 16 16 Crash ! Crash occurs after OUTPUT(A), before OUTPUT(B) We lose atomicity21 The Log • An append-only file containing log records • Multiple transactions run concurrently, log records are interleaved • After a system crash, use log to: – Redo some transaction that didn’t commit – Undo other transactions that didn’t commit • Three kinds of logs: undo, redo, undo/redo Dan Suciu -- 444 Spring 201022 Undo Logging Log records • <START T> – transaction T has begun • <COMMIT T> – T has committed • <ABORT T> – T has aborted • <T,X,v> – T has updated element X, and its old value was v Dan Suciu -- 444 Spring 201023 Action T Mem A Mem B Disk A Disk B Log <START T> INPUT(A) 8 8 8 READ(A,t) 8 8 8 8 t:=t*2 16 8 8 8 WRITE(A,t) 16 16 8 8 <T,A,8> INPUT(B) 16 16 8 8 8 READ(B,t) 8 16 8 8 8 t:=t*2 16 16 8 8 8 WRITE(B,t) 16 16 16 8 8 <T,B,8> OUTPUT(A) 16 16 16 16 8 OUTPUT(B) 16 16 16 16 16 COMMIT <COMMIT T>24 Action T Mem A Mem B Disk A Disk B Log <START T> INPUT(A) 8 8 8 READ(A,t) 8 8 8 8 t:=t*2 16 8 8 8 WRITE(A,t) 16 16 8 8 <T,A,8> INPUT(B)
View Full Document
Unlocking...