Carnegie Mellon University Parallel Data Lab Ph.D. Dissertation CMU-PDL-05-111, December, 2005.
Christopher R. Lumb
Parallel Data Laboratory
Electrical and Computer Engineering
Carnegie Mellon University
Pittsburgh, PA 15213
Most current storage systems, including direct-attached disks, RAID arrays, and network filers, are centralized; they have a central point of control, with global knowledge of the system, for making data distribution and request scheduling decisions. This central control allows for good cache performance, load baliancing and scheduling efficiency. However, many now envision building storage systems out of collections of federated "bricks" connected by high-performance networks. The goal of brick-based storage is a system that has incremental scalability, parallel data transfer and low cost. However, with bricks, there is no centralized point of control to provide request distribution. This lack of central contol makes achieving good scheduling efficiency, load balancing and cache performance a challenge in decentrailized brick-based storage.
Distributed Shortest-Positioning Time First (D-SPTF) is a decentralized request distribution protocol designed to address this challenge. D-SPTF exploits high-speed interconnects to dynamically select which server, among those with a replica, should service each read request. In doing so, it simultaneoulsy balances load, exploits aggregate cache capacity, and reduces positioning times for cache misses. For network latencies of up to 0.5ms, D-SPTF performs as well as would a hypothetical centralized system with the same collection of CPU, cache, and disk resources. Compared to a popular decentralized approach, hash-based request distribution, D-SPTF achieves up to 65% higher throughput and adapts more cleanly to heterogeneous server capabilities.
KEYWORDS: decentralized storage, storage systems, array scheduling, scalability
FULL PAPER: pdf