1Chapter 11 1Chapter 11: Hardware(Slides by Hector Garcia-Molina,http://www-db.stanford.edu/~hector/cs245/notes.htm)Chapter 11 2Outline• Hardware: Disks• Access Times• Optimizations• Other Topics:– Storage costs– Using secondary storage– Disk failuresChapter 11 3The Big Picture:DBMSData Storage2Chapter 11 4PMTypicalComputerSecondaryStorage...Chapter 11 5ProcessorFast, slow, reduced instruction set,with cache, pipelined…Speed: 100 → 500 → 1000 MIPSMemoryFast, slow, non-volatile, read-only,…Access time: 10-6 → 10-9 sec.1 µs → 1 nsChapter 11 6Secondary storageMany flavors:- Disk: Floppy (hard, soft)Removable PacksWinchesterRam disksOptical, CD-ROM…Arrays- Tape Reel, cartridgeRobots3Chapter 11 7Focus on: “Typical Disk”Terms: Platter, Head, Cylinder, TrackSector (physical),Block (logical), Gap…Chapter 11 8Top ViewChapter 11 9“Typical” NumbersDiameter: 1 inch → 15 inchesCylinders: 100 → 2000Surfaces: 1 (CDs) →(Tracks/cyl) 2 (floppies) → 30Sector Size: 512B → 50KCapacity: 360 KB (old floppy)→ 30 GB (I use)4Chapter 11 10Disk Access Timeblock xin memory?I wantblock XChapter 11 11Time = Seek Time +Rotational Delay +Transfer Time +OtherChapter 11 12Rotational DelayHead HereBlock I Want5Chapter 11 13Average Rotational DelayR = 1/2 revolution“typical” R = 8.33 ms (3600 RPM)Chapter 11 14Transfer Rate: t• “typical” t: 1 → 3 MB/second• transfer time: block sizetChapter 11 15Other Delays• CPU time to issue I/O• Contention for controller• Contention for bus, memory“Typical” Value: 06Chapter 11 16• So far: Random Block Access• What about: Reading “Next” block?Chapter 11 17If we do things right (e.g., Double Buffer, Stagger Blocks…)Time to get = Block Size + Negligible block t- skip gap- switch track- once in a while, next cylinderChapter 11 18Rule of Random I/O: ExpensiveThumb Sequential I/O: Much less• Ex: 1 KB Block» Random I/O: ∼ 20 ms.» Sequential I/O: ∼ 1 ms.7Chapter 11 19Cost for Writing similar to Reading…. unless we want to verify! need to add (full) rotation + Block size tChapter 11 20• To Modify a Block?To Modify Block:(a) Read Block(b) Modify in Memory(c) Write Block[(d) Verify?]Chapter 11 21Block Address:• Physical Device• Cylinder #• Surface #• Sector8Chapter 11 22Outline• Hardware: Disks• Access Times• Optimizations• Other Topics– Storage Costs– Using Secondary Storage– Disk FailureshereChapter 11 23Optimizations (in controller or O.S.)• Double Buffering• Disk Scheduling Algorithms: sec. 11.5.4– e.g., elevator algorithmChapter 11 24Double BufferingProblem: Have a File» Sequence of Blocks B1, B2 Have a Program» Process B1» Process B2» Process B3...9Chapter 11 25Single Buffer Solution(1) Read B1 → Buffer(2) Process Data in Buffer(3) Read B2 → Buffer(4) Process Data in Buffer ...Chapter 11 26Say P = time to process/blockR = time to read in 1 blockn = # blocksSingle buffer time = n(P+R)Chapter 11 27Double BufferingMemory:Disk:A B C D GE FABdoneprocessACprocessBdone10Chapter 11 28Say P ≥ RWhat is processing time?P = Processing time/blockR = IO time/blockn = # blocks• Double buffering time = R + nP• Single buffering time = n(R+P)Chapter 11 29Block Size Selection?• Big Block → Amortize I/O Cost• Big Block ⇒ Read in more useless stuff! and takes longer to readUnfortunately...Chapter 11 30Trend• As memory prices drop,blocks get bigger ...Trend11Chapter 11 31Storage Cost10-910-610-310-0103access time (sec)101510131011109107105103cacheelectronicmainelectronicsecondarymagneticopticaldiskstapeopticaldiskstapetypical capacity (bytes)from Gray & ReuterChapter 11 32Storage Cost10-910-610-310-0103access time (sec)10410210010-210-4cacheelectronicmainelectronicsecondarymagneticopticaldiskstapeopticaldiskstapedollars/MBfrom Gray & ReuterChapter 11 33Using secondary storage effectively• Example: Sorting data on disk• Conclusion:– I/O costs dominate– Design algorithms to reduce I/O• Also: How big should blocks be?12Chapter 11 34Disk Failures (Sec 11.6)• Partial → Total• Intermittent → PermanentChapter 11 35Coping with Disk Failures• Detection– e.g. Checksum• Correction ⇒ RedundancyChapter 11 36At what level do we cope?• Single Disk– e.g., Error Correcting Codes• Disk ArrayLogicalPhysical13Chapter 11 37 Operating System e.g., Stable StorageLogical Block Copy A Copy BChapter 11 38Database System• e.g., LogCurrent DB Last week’s DBChapter 11 39Summary• Secondary storage, mainly disks• I/O times• I/Os should be avoided,especially random ones…..Summary14Chapter 11 40Outline• Hardware: Disks• Access Times• Optimizations• Other Topics– Storage Costs– Using Secondary Storage– Disk