Introduction to Database SystemsCSE 444Lectures 9-10 Transactions: recoveryCSE 444 - Summer 2010 1Outline• We are starting to look at DBMS internals• Next pair of lectures: transactions & recovery– Disks 13.2– Undo logging 17.2 – Redo logging 17.3–Redo/undo 17.4CSE 444 - Summer 2010 2The Mechanics of DiskMhilh titiCylinderMechanical characteristics:• Rotation speed (5400 RPM)•Numberofplatters (130)SpindleDisk headTracks•Number of platters (1-30)• Number of tracks (<=10000)•Number of bytes/track(105)SectorNumber of bytes/track(10)Pl ttUnit of read or write:disk blockPlattersArm movementdisk blockOnce in memory:pageTypically: 4k or 8k or 16kArm assemblyTypically: 4k or 8k or 16k3RAIDSeveral disks that work in parallel• Redundancy: use parity to recover from disk failureSpeed: read from several disks at once•Speed: read from several disks at onceVarious configurations (called levels):• RAID 1 = mirror• RAID 4 = n disks + 1 parity disk•RAID 5 = n+1 disks assign parity blocks round robin•RAID 5 = n+1 disks, assign parity blocks round robin• RAID 6 = “Hamming codes”CSE 444 - Summer 2010 4Disk 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 cylinder1040•10ms –40ms– Rotational latency = time for the sector to rotate• Rotation time = 10msAverage latency 10ms/2•Average latency = 10ms/2• Transfer time = typically 40MB/s• Disks read/write one block at a timeCSE 444 - Summer 2010 5Storage Latency: How Far Away is the Data?How Far Away is the Data?AndromedaTape /Optical Robot1092,000 YearsDisk1062 YearsPlutoMemory100Olympia1.5 hrOn Chip CacheOn Board CacheMemory 210100This BuildingThis Room10 min7/8/2010 © 2007 Gribble, Lazowska, Levy, Zahorjan62Registers1 My Head 1 min© 2004 Jim Gray, Microsoft CorporationBuffer Management in a DBMSPage Requests from Higher LevelsBUFFER POOLREADWRITEdisk pageBUFFER POOLWRITEMAIN MEMORYfree frameINPUTOUTUPTDBMAIN MEMORYDISKchoice of frame dictatedby replacement policyOUTUPT• Data must be in RAM for DBMS to operate on it!Table of <frame#pageid> pairs ismaintainedyppy7•Table of <frame#, pageid> pairs ismaintainedCSE 444 Summer 2010Buffer Manager• Enables higher layers of the DBMS to assume that needed data is in main memory• Needs to decide on page replacement policy– LRU, clock algorithm, or other• Both work well in OS, but not always in DBCSE 444 - Summer 2010 8Least Recently Used (LRU)• Order pages by the time of last accessed•Always replace the least recently accessedyp yP5, P2, P8, P4, P1, P9, P6, P3, P7,,,,,,,,Access P6Access P6P6, P5, P2, P8, P4, P1, P9, P3, P7LRU is expensive (why ?); the clock algorithm is good approxBuffer Manager• Why not use the OS for the task??• Reason 1: Correctness– DBMS needs fine grained control for transactions– Needs to force pages to disk for recovery purposes• Reason 2: Performance– DBMS may be able to anticipate access patterns–Hence, may also be able to perform prefetching– May select better page replacement policyMttiithbff–May want to pin pages in the bufferCSE 444 - Summer 2010 10Transaction Management andTransaction Management and the Buffer ManagerTransaction manager operates on buffer pool• Recovery: ‘log-file write-ahead’, then careful ygpolicy about which pages to force to disk• Concurrency control: locks at the page level, multiversion concurrency controlCSE 444 - Summer 2010 11Transaction ManagementTwo parts:• Recovery from crashes: ACID• Concurrency control: ACIDyBoth operate on the bufferpoolBoth operate on the buffer poolCSE 444 - Summer 2010 12Problem IllustrationClient 1:Client 1:START TRANSACTIONINSERT INTO SmallProduct(name, price)SELECT pname, priceFROM ProductWHEREprice<=0.99WHEREprice 0.99DELETE ProductWHEREprice <=0 99Crash !WHEREprice <=0.99COMMITWhat do we do now?CSE 444 - Summer 2010What do we do now?13RecoveryType of Crash PreventionConstraints andWrong data entryConstraints andData cleaningRedundancy:Disk crashesRedundancy: e.g. RAID, archiveFire, theft,Buy insurance,Fire, theft, bankruptcy…Buy insurance, Change jobs…SystemfailuresDATABASESystem failuresRECOVERY14Main Idea for Recovery• Each transaction has internal state• When system crashes, internal state is lost– Don’t know which parts executed and which didn’t– Need ability to undo and redo• Remedy: use a log– File that records every single action of all running transactionstransactions– After a crash, transaction manager reads the log to find out exactly what each transaction did or did not doyCSE 444 - Summer 2010 15Transactions• Assumption: db composed of elements– Usually 1 element = 1 blockCb ll(1 d)l (1lti)–Can be smaller (=1 record) or larger (=1 relation)•Assumption: each transaction reads/writes•Assumption: each transaction reads/writes some elementsCSE 444 - Summer 2010 16Primitive Operations ofPrimitive 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 buffery• OUTPUT(X)– write element X to diskCSE 444 - Summer 2010 17ExampleSTART TRANSACTIONSTART TRANSACTIONREAD(A,t); tt*2t:= t*2;WRITE(A,t); Atomicity:BOTH A and BREAD(B,t); t := t*2;are multiplied by 2WRITE(B,t);COMMIT;CSE 444 - Summer 2010 18READ(A,t); t := t*2; WRITE(A,t); READ(B,t); t := t*2; WRITE(B,t);ActiontMem AMem BDisk ADisk BBuffer pool DiskTransactionActiontMem AMem BDisk ADisk BINPUT(A) 8 8READ(A,t)READ(A,t)t:=t*2WRITE(A,t)INPUT(B)READ(B,t)t:=t*2WRITE(B,t)OUTPUT(A)OUTPUT(B)READ(A,t); t := t*2; WRITE(A,t); READ(B,t); t := t*2; WRITE(B,t);ActiontMem AMem BDisk ADisk BBuffer pool DiskTransactionActiontMem AMem BDisk ADisk BINPUT(A) 8 8 8READ(A,t)READ(A,t)t:=t*2WRITE(A,t)INPUT(B)READ(B,t)t:=t*2WRITE(B,t)OUTPUT(A)OUTPUT(B)READ(A,t); t := t*2; WRITE(A,t); READ(B,t); t := t*2; WRITE(B,t);ActiontMem AMem BDisk ADisk BBuffer pool DiskTransactionActiontMem AMem BDisk ADisk BINPUT(A) 8 8 8READ(A,t)8888READ(A,t)8888t:=t*2 16 8 8 8WRITE(A,t)INPUT(B)READ(B,t)t:=t*2WRITE(B,t)OUTPUT(A)OUTPUT(B)READ(A,t); t := t*2; WRITE(A,t); READ(B,t); t := t*2; WRITE(B,t);ActiontMem AMem BDisk ADisk BBuffer pool DiskTransactionActiontMem AMem BDisk ADisk BINPUT(A) 8 8 8READ(A,t)8888READ(A,t)8888t:=t*2 16 8 8 8WRITE(A,t) 16 16 8
View Full Document
Unlocking...