Other Free Encyclopedias » Online Encyclopedia » Encyclopedia - Featured Articles » Contributed Topics from K-O

Multimedia Storage Organizations - Introduction, Data Placement,  

disk display block system

Seon Ho Kim
University of Denver, Denver, USA

Definition: Magnetic disk drives are typically used as multimedia storage systems due to their high data transfer, large storage capacity, and low price.


Considering the large size of multimedia files, especially streaming media (SM) such as audio and video that require real-time data retrieval, magnetic disk drives have been the choice of multimedia storage systems due to their high data transfer rate, large storage capacity, random access capability, and low price. Therefore, this article also focuses on disk based storage organization for multimedia servers.

As discussed in the article, Multimedia Servers, the objectives of multimedia servers are to support a smooth display without any jitters (continuous display), to maximize the number of simultaneous displays (high throughput), and to minimize the latency between issuing request and initiation of display (low startup latency). Thus, the design of storage organization to support such servers should also follow these objectives. Additionally, load balancing and fault tolerance issues should be considered to complete the discussion of multi-disk storage systems.

A basic approach to support continuous display is to divide an SM object into equi-sized blocks. Each block is a unit of retrieval and is contiguously stored in a disk. For example, a SM object X is divided into n equi-sized blocks: X 0 , X 1 , X 2 , X n-1. The size of blocks, the display time of a block, and the time to read a block from a disk drive can be calculated as a function of display bandwidth requirement of an object, the number of maximum simultaneous displays that a disk drive can support, and the physical disk characteristics such as the data transfer rate. Upon the request for the SM object X, the system stages the first block of X, i.e., X 0 , from the disk into main memory and initiates its display. Prior to the completion of the display of X 0 , the system stages the next block X 1 from the disk into main memory to provide for a smooth transition and a hiccup-free display. This process is repeated until all blocks of X are displayed. This process introduces the concept of a time period (T p ), or a round, which denotes the time to display a block. For example, the display time of one 0.5 MByte block of a SM object encoded with 4 Mb/s is one second (T p = 1 sec). Traditionally, double buffering has been widely used to absorb the variance of block retrieval time. The idea is as follows: while a buffer is being consumed from memory, the system fills up another buffer with data. The system can initiate display after the first buffer is filled and a request for the next one is issued.

In general, the display time of a block is longer than its retrieval time from a disk drive. Thus, the bandwidth of a disk drive can be multiplexed among multiple simultaneous displays accessing the same disk drive. For example, with 4 Mb/s of display bandwidth requirement of MPEG-2 encoded objects, a disk drive with 80 Mb/s of data transfer rate can support up to 20 simultaneous displays. This is the ideal case when there is no overhead in disk operation. However, in reality, a magnetic disk drive is a mechanical device and incurs a delay when required to retrieve data. This delay consists of: 1) seek time to reposition the disk head from the current cylinder to the target cylinder, and 2) rotational latency to wait until the data block arrives under the disk head. These are wasteful operations that prevent a disk drive from transferring data. Both their number of occurrence and duration of each occurrence must be reduced in order to maximize the number of simultaneous displays supported by a disk drive (throughput). Thus, the performance of SM servers significantly depends on the physical characteristics of magnetic disk drives (such as data transfer rate, seek times, and rotational latency), the data placement of blocks, and the block retrieval scheduling. Moreover, a single disk is not enough for most multimedia applications in both storage capacity and bandwidth. It is critical to manage multiple storage devices in a coordinated manner to support the requirement of a large-scale server, the aggregate storage capacity and bandwidth. With multiple disks, the storage system must meet the contiguous display requirements of all streams through careful data placement and retrieval scheduling. An additional issue in multi-disk system is load imbalance problem. Load to an individual device can vary over time depending on many factors such as the fluctuation of the number of user requests during a day and the popularity of objects. This may make a specific disk a bottleneck of the entire system. Thus, one may need a busy hour analysis to quantify the peak system load. Another important practical issue is the reliability of storage systems.

Data Placement

Assuming SM servers with multiple disk drives, data blocks are assigned to disks in order to distribute the load of a display evenly across the disks. Thus, data placement can affect the continuous display and performance of SM servers in conjunction with scheduling techniques. There are two well-known approaches to assign blocks of an object across multiple disk drives; constrained and unconstrained. A typical example of constrained data placement is round robin. As suggested by its name, this technique assigns the blocks of an object across disks in a round-robin manner, starting with an arbitrarily chosen disk. Assuming d disks in the system, if the first block of an object X is assigned to disk d i, j th block of X is assigned to disk d (i+j-1) mod d. An example of unconstrained data placement is random that assigns data blocks to disk drives using a random number generator. Figure 1 shows examples of both approaches.

Round-robin data placement can be generalized using the concept of clustering. The system partitions D disks (total number of disks in the system) into k clusters of disks with each cluster consisting of d disks. Then data blocks are assigned across clusters in a round-rob in manner as shown in Figure 1. Inside a cluster, a block is further divided into d fragments: X o is divided into X 0.0 X 0.d-1 and assigned to d disks in a cluster. The fragments of a block are concurrently retrieved in parallel from a cluster while blocks are periodically retrieved across clusters in a round-robin manner. Depending on the degree of striping, wide striping stripes blocks across all disks while narrow striping stripes blocks across a subset of disks. When d = 1, each disk is a cluster so it is possible to independently control individual disk. This produces a higher throughput and longer startup latency as throughput and latency scale linearly as a function of the number of disks. When d = D, all disks are accessed in a synchronized manner because all fragments of a data block should be retrieved concurrently while incurring a seek in each disk, resulting in a lower throughput. However, this approach provides shorter startup latency. Thus, it is important to determine the optimal striping size and configure the system considering the performance requirements of an application: data transfer rate of disks, display rate of objects, number of disks in the system, amount of main memory, and cost per display.

Due to the harmony of round-robin data placement and periodic cycle-based data retrieval, this approach provides a deterministic service guarantee for a hiccup-free display of a SM object once its retrieval is initiated. This approach maximizes the utilization of disk bandwidth by distributing the load of a display across disks evenly. Thus, the system throughput scales linearly as a function of the number of disk drives in the system. The drawback of this approach is that the startup latency also scales because the system might delay the initiation of data retrievals of objects. Thus, this approach is suitable to the applications that require a high throughput and can tolerate a long startup latency such as movie-on-demand systems.

With random data placement, fixed size blocks are randomly assigned across disks. Each block request is tagged with a deadline. By controlling the deadlines for block retrievals, this approach can provide shorter startup latency than the cycle-based and round-robin approach. Hence, this is more appropriate fot the applications requiring a short startup latency such as a digital editing system. However, random may suffer from statistical variation of the number of block retrievals in a disk drive. Due to the nature of random data placement, a disk might receive more than its fair share of requests. A formation of bottleneck on a disk drive may result in the violation of deadlines set forth on requested blocks, causing some displays to incur hiccups. This hiccup probability might be significant depending on the system load. To reduce the hiccup probability, a multiple buffering scheme with prefetching was proposed in.

Data placement, combined with the data retrieval scheduling, can significantly impact on the performance of the storage system for multimedia servers. The performance issues, throughput and startup latency, are discussed in the article, Scheduling, Multimedia.


Multimedia Streaming on the Internet - Compression, QoS Control/Monitor, Streaming Protocols, Media Synchronization [next] [back] Multimedia Servers - Introduction, Multimedia Server Architecture, Buffer Management, Quality of Service and Admission Control, Client Subsystem

User Comments

Your email address will be altered so spam harvesting bots can't read it easily.
Hide my email completely instead?

Cancel or