CS 414 – Multimedia Systems Design Lecture 26 – Media Server (Part 2) Outline Client/Server Video-on-Demand System Video-on-Demand Systems must be designed with goals: Some Facts on YouTube Video Service (from 2009)YouTube Video Server (2010)Media Server Architecture Storage Management Placement of MM Data Blocks on Single Disk Intra-file Seek Time Scattered Non-continuous Placement Constrained Placement Log-Structure Placement Placement of Multiple MM Files on Single Disk ExamplePlacement Algorithm for Multiple Files on Single Disk Need for Multiple Disks Solutions for Media ServerApproach: Data Striping Data Striping – Group Creation Storage/Disk Management Data Interleaving Disk Scheduling PoliciesDisk Scheduling Framework EDF (Earliest Deadline First) Disk SchedulingEDF ExampleConclusionCS 414 - Spring 2011CS 414 – Multimedia Systems DesignLecture 26 –Media Server (Part 2) Klara NahrstedtSpring 2011Outline Storage Management Multimedia Data Placement Strategies on Disk Multiple Disks and Multimedia RAID Data Striping Group Creation Disk Management Data Interleaving Disk Scheduling EDF ; SCAN-EDFCS 414 - Spring 2011Client/Server Video-on-Demand System CS 414 - Spring 2011Video-on-Demand Systems must be designed with goals: Avoid starvation Minimize buffer space requirement Minimize initiation latency (video startup time) Optimize costCS 414 - Spring 2011Some Facts on YouTube Video Service (from 2009) Checked with http://www.wired.com/epicenter/2009/10/youtube-over-one-billion-videos-served-per-day/ Over 1 billion videos per day Bandwidth accounts for about 51% of expenses -- with a run rate of $1 million per day -- with content licensing accounting for 36% http://www.multichannel.com/article/191223-YouTube_May_Lose_470_Million_In_2009_Analysts.phpCS 414 - Spring 2011YouTube Video Server (2010) http://tech.fortune.cnn.com/2010/05/17/youtube-at-5-years-old-2-billion-served-per-day/ May 2010, 2 Billion videos served per day More than 24 hours of video uploaded every minute Videos usually less than 10 minutes longCS 414 - Spring 2011Media Server Architecture CS 414 - Spring 2011Storage device Disk controller (Disk Management)Storage management File SystemMemory Management Content DirectoryNetwork Attachment Incoming requestDelivered dataStorage Management Storage access time to read/write disk block is determined by 3 components Seek Time Time required for the movement of read/write head Rotational Time (Latency Time) Time during which transfer cannot proceed until the right block or sector rotates under read/write head Data Transfer Time Time needed for data to copy from disk into main memory CS 414 - Spring 2011Placement of MM Data Blocks on Single Disk CS 414 - Spring 2011Continuous Placement Scattered PlacementSimple to implement, but subject to fragmentationAvoids fragmentationEnormous copying overhead during insert/delete to maintain continuityAvoid copying overheadWhen reading file, only one seek required to position the disk head at the start of dataWhen reading file, seek operation incurs for each block , hence intrafileseekIntra-file Seek Time Intra-file seek – can be avoided in scattered layout if the amount read from a stream always evenly divides block Solution: select sufficient large block and read one block in each round If more than one block is required to prevent starvation prior to next read, deal with intra-file seek Solution: constrained placement or log-structure placement CS 414 - Spring 2011Scattered Non-continuous Placement CS 414 - Spring 2011Constrained Placement Approach: separation between successive file blocks is bounded Bound on separation – not enforced for each pair of successive blocks, but only on average over finite sequence of blocks Attractive for small block sizes Implementation – expensive For constrained latency to yield full benefit, scheduling algorithm must retrieve immediately all blocks for a given stream before switching to another stream CS 414 - Spring 2011Log-Structure Placement This approach writes modified blocks sequentially in a large contiguous space, instead of requiring seek for each block in stream when writing (recording) Reduction of disk seeks Large performance improvements during recording, editing video and audio Problem: bad performance during playback Implementation: complexCS 414 - Spring 2011Placement of Multiple MM Files on Single Disk Popularity concept among multimedia content -very important Take popularity into account when placing movies on disk Model of popularity distribution – Zipf’s Law Movies are kthranked if their probability of customer usage is C/k, C = normalization factor Condition holds: C/1 + C/2 + … C/N = 1, N is number of customersCS 414 - Spring 2011Example Assume N = 5 movies Problem: what is the probability that the next customer picks 3rdranked movie? Solution: Solve C from the equation C/1 + C/2 + C/3 + C/4 + C/5 = 1 C = 0.437 Probability to pick 3rdranked movie is C/3 = 0.437/3 = 0.1456CS 414 - Spring 2011Placement Algorithm for Multiple Files on Single Disk Organ-Pipe Algorithms (Grossman and Silverman 1973)CS 414 - Spring 2011Middle of disk (in case of traditional disk layout)1strank (most popular movie)2ndranked movie3rd4th5th6th7th8th9thNote: In case of ZBR disk layout , place most popular disks at the outer tracksNeed for Multiple Disks Solutions for Media Server Limitation of Single Disk: Disk Throughput Approach: 1 Maintain multiple copies of the same file on different disks Very expensive Approach 2: Scatter multimedia file across multiple disksCS 414 - Spring 2011Approach: Data Striping RAID (Redundant Arrays of Inexpensive Disks) Addresses both performance and security (0-6) RAID levels – different approach at combining performance enhancements with security/fault-tolerance enhancements Disks spindle synchronously Operate in lock-step parallel mode Striping improves BW, but does not improve seek or rotational delayCS 414 - Spring 2011Data Striping – Group Creation CS 414 - Spring 2011Multiple RAID: Creation of Subgroups of disks into independent logical disk arrays; limits # of disks per fileDeclustering: Groups are not made up of complete disks ; # of disks for any stripe is fixed and of same
View Full Document
Unlocking...