PDL Abstract

D-SPTF: Decentralized Request Distribution in Brick-based Storage

Carnegie Mellon University School of Computer Science Technical Report CMU-CS-03-202, November, 2003.

Christopher R. Lumb, Gregory R. Ganger, Richard Golding*

Electrical and Computer Engineering
Carnegie Mellon University
Pittsburgh, PA 15213

*IBM Almaden Research


Distributed Shortest-Positioning Time First (D-SPTF) is a request distribution protocol for decentralized systems of storage servers. 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 simultaneously balances load, exploits the 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 existing decentralized approaches, such as hash-based request distribution, D-SPTF achieves up to 65% higher throughput and adapts more cleanly to heterogenous server capabilities.

KEYWORDS: decentralized storage, storage systems, array scheduling, scalability