PARALLEL DATA LABORATORYCarnegie Mellon UniversityAdvanced disk scheduling“Freeblock scheduling”Eno Thereska(slide contributions by Chris Lumb and Brandon Salmon)Eno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 2Outline• Freeblock scheduling: some theory• Freeblock scheduling: applied• Some details• Q & AEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 3Some theory: preview• Next few slides will review & show that:• disks are slow• mechanical delays (seek + rotational latencies)• there is nothing we can do during a seek• there is a lot we can do during a rotation• rotational latencies are very large• while rotation is happening go to nearby tracks and do useful work• “freeblock scheduling” = utilization of rotational latency gaps (+ any idle time)Eno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 4Are disks slow?• Are the xfer speeds that slow?• no, xfer speeds of 200MB/s are pretty good• So what is slow?• workload often not sequential• disk head has to move from place to place• seek (~ 4ms) + rotation (~ 3ms)• Effective bandwidth can be very low• ~ 10-30MB/s• even when SPTF is usedEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 5Surface organized into tracksEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 6Tracks broken up into sectorsEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 7Disk head positionEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 8Rotation is counter-clockwiseEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 9About to read blue sectorEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 10After reading blue sectorAfter BLUE readEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 11Red request scheduled nextAfter BLUE readEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 12Seek to Red’s trackAfter BLUE read Seek for REDSEEKEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 13Wait for Red sector to reach headAfter BLUE read Seek for RED Rotational latencyROTATESEEKEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 14Read Red sectorAfter BLUE read Seek for RED Rotational latency After RED readROTATESEEKEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 15Scheduling algorithm Impact0%20%40%60%80%100% FCFS C-LOOK SSTF SPTF Disk Head Usage Latency Transfer Seek Eno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 16Impact of Request Sizes0%20%40%60%80%100%1 2 4 8 16 32 64 128 256 512 1024 2048 4096Request Size (KB)Disk Head Usage Latency Transfer SeekEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 17What can we do?• Nothing we can do during a seek• disk head has to move to the right track• Rotational latency is fully wasted• let’s use this latency• During a rotational latency• go to nearby tracks and do useful work• then, just-in-time, seek back to the original requestEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 18A quick glance ahead…• What kind of “useful work” are we doing?• work that belongs to a “background” app• things like backup, defrag, virus scanning• What do we really gain?• background apps don’t interfere with fore. apps• background apps still complete• What’s in it for me?• can run defrag + virus scanner + backup in the background while working on your homework and you won’t notice they are running JEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 19Rotational latency gap utilizationAfter BLUE readEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 20Seek to Third trackAfter BLUE read Seek to ThirdSEEKEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 21Free transferAfter BLUE read Seek to Third Free transferSEEK FREE TRANSFEREno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 22Seek to Red’s trackAfter BLUE read Seek to Third Seek to REDFree transferSEEKSEEK FREE TRANSFEREno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 23Read Red sectorAfter BLUE read Seek to Third Seek to RED After RED readFree transferSEEKSEEK FREE TRANSFEREno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 24Final theory details• Scheduler also uses disk idle time• high end servers have little idle time• Idle time + rotational latency usage = “freeblock scheduling”(it means we are getting things for free)Eno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 25Steady background I/O progress05101520253035400 10 20 30 40 50 60 70 80 90 100% disk utilization by foreground reads/writes“Free” MB/sfrom idle timefrom rotational gapsEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 26Applied freeblocks: preview• Next few slides will show that:• we can build background apps• that do not interfere with foreground apps• that complete eventually• things like backup, defrag, virus scanners, etc• imagine the possibilities…Eno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 27App 1: Backup• Frequent backup improves data reliability and availability• companies take very frequent backups• a backup every 30 mins is not uncommon• Our experiment:• disk used is 18GB• we want to back up 12GB of data• goal: back it up for freeEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 28Backup completed for free0102030405060708090Idle system Synthetic TPC-C PostmarkBackup time (mins)< 2% impact on foreground workloadEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 29App 2: Layout reorganization• Layout reorganization improves access latencies• defragmentation is a type of reorganization• typical example of background activity• Our experiment:• disk used is 18GB• we want to defrag up to 20% of it• goal: defrag for freeEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 30Disk Layout Reorganized for Free!RandomCircularTrack Shuffle01002003004005006001% 10% 20% 1% 10% 20%8MB 64MBReorganizer buffer size (MB)Reorganization time (mins)Eno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 31Other maintenance applications• Virus scanner• LFS cleaner• Disk scrubber• Data mining• Data migrationEno Thereska 15-410 Lecture April 2004http://www.pdl.cmu.edu/ 32Summary• Disks are slow• but we can squeeze extra bw
View Full Document
Unlocking...