TL;DR
This paper tackles the challenge of efficiently storing and retrieving continuous media (like video and audio) from disks, which have inherent latency issues. The authors propose a novel "matrix-based allocation" scheme that eliminates disk latency for retrieval, drastically reducing buffer requirements and enabling concurrent stream servicing.
What Problem Does This Paper Address?
Modern applications increasingly rely on continuous media data – think streaming video, interactive TV, or multimedia emails. Unlike traditional data (text, code), continuous media has strict timing requirements; data must be delivered at a guaranteed rate to avoid glitches or interruptions. Conventional file systems, designed for bursty, non-time-sensitive data, fail to provide these rate guarantees. Storing large amounts of continuous media data (like a movie) in RAM is prohibitively expensive, making secondary storage (disks) the only viable option. However, disks introduce significant latency (seek and rotational delays) and have limited bandwidth, making it difficult to serve multiple continuous media streams concurrently while meeting their strict timing demands. This paper aims to bridge this gap by designing storage and retrieval mechanisms that overcome disk limitations for continuous media.
Methods
The paper presents two main approaches:
- Simple Concurrent Retrieval Scheme: This initial scheme focuses on retrieving multiple continuous media streams from disks. It involves managing critical storage resources like memory and disks to provide rate guarantees. The core idea is to retrieve data in rounds, ensuring that for each stream, enough data is fetched to cover the consumption rate between retrieval cycles. This method, however, leads to high buffer requirements due to disk latency.
- Matrix-Based Allocation Scheme: This is the paper's key contribution. It proposes a clever way to organize continuous media data on disk. Instead of storing clips contiguously, the data is viewed as a matrix where rows represent time segments and columns represent portions of data. This matrix is then stored on disk in a column-major order. By strategically retrieving data column by column, the scheme effectively eliminates the need for random disk seeks. This allows for concurrent retrieval of multiple streams at a guaranteed rate, drastically reducing the buffer size needed per stream and making it independent of disk latency. The paper also details how VCR-like operations (pause, fast-forward, rewind) can be implemented with this scheme.
Datasets
Not discussed in the paper. The paper uses theoretical disk characteristics (e.g., Seagate Barracuda 2 disk) and hypothetical data rates for video (MPEG-I) and image (JPEG) compression.
Key Insights and Ideas
- Disk Latency is the Bottleneck: The paper clearly identifies disk latency (seek + rotational) as the primary challenge for continuous media retrieval, leading to substantial buffering needs in traditional approaches.
- Matrix-Based Allocation Eliminates Latency: The "aha moment" is realizing that by restructuring data storage into a matrix and retrieving it column-wise, random seeks can be avoided. This is a clever way to "hide" disk latency by ensuring data is always accessed sequentially.
- Buffer Requirements Drastically Reduced: The matrix-based scheme's ability to eliminate disk latency directly translates to significantly lower buffer requirements compared to traditional methods, making it more cost-effective.
- VCR Operations Feasible: The paper demonstrates that even complex operations like fast-forward and rewind can be implemented efficiently within this new storage paradigm.
- Trade-off Between Response Time and Buffer Size: The paper highlights a common trade-off: the simple scheme offers low response times but high buffer needs, while the matrix-based scheme reduces buffers but can increase initial response times for stream initiation.
Key Results
- The paper provides an example (Example 1) showing that for a single disk serving MPEG-I video at 1.5 Mb/s, the simple scheme requires 10 GB of total buffer to support 45 concurrent streams.
- The matrix-based allocation scheme, by eliminating disk latency, drastically reduces these buffer requirements.
- The matrix-based scheme allows for the concurrent retrieval of
pstreams, wherep = floor(T_disk / T_med), and the buffer size per stream becomes independent of disk latency. - For VCR operations, the worst-case delay for initiating a stream (or resuming after pause) is
t_c, the time to read one row of the super-clip matrix. For the example disk, this was initially 133 seconds, but could be reduced to 26 seconds by using an array of 5 disks.
Limitations and Future Work
Limitations:
- Initial Response Time: The matrix-based scheme can lead to higher initial response times for stream initiation compared to simpler schemes, especially when resuming from a pause or starting a new stream.
- Data Modification: The matrix-based scheme is rigid and not well-suited for scenarios with frequent additions, deletions, or modifications of data, potentially leading to fragmentation.
- Single Disk Assumption: Much of the initial analysis assumes data resides on a single disk.
- Disk Imperfections: The paper acknowledges that real-world disks have issues like bad sectors and thermal expansion that are not fully accounted for.
- Continuous Media Only: The current schemes primarily focus on continuous media requests, not mixed workloads with non-continuous data.
Future Work:
- Load Balancing and Fault Tolerance: Developing schemes for distributing continuous media clips across multiple disks (striping) and ensuring fault tolerance (replication, parity disks) without excessive overhead.
- Storage Schemes for Dynamic Data: Investigating storage methods that handle frequent data changes and avoid fragmentation, possibly by using page-based storage.
- Tertiary Storage: Exploring techniques for storing and retrieving continuous media from cheaper, slower media like tapes and CD-ROMs.
- Reducing Disk Latency: Further research into disk scheduling algorithms to reduce seek and rotational latency for stream servicing.
- Variable Transfer Rates: Developing schemes to handle streams with different transfer rates (e.g., MPEG-I vs. JPEG).
- Accounting for Disk Imperfections: Incorporating real-world disk behaviors like bad sectors and thermal recalibration into storage and retrieval schemes.
- Mixed Workloads: Designing systems that can efficiently service both continuous and non-continuous media requests, prioritizing continuous media while utilizing slack time for other requests.
Summary updated