D-SPTF: decentralized request distribution in brick-based storage systems

ABSTRACT

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 expected in storage clusters (e.g., 10--200μs), D-SPTF performs as well as would a hypothetical centralized system with the same collection of CPU, cache, and disk resources. Compared to popular decentralized approaches, D-SPTF achieves up to 65% higher throughput and adapts more cleanly to heterogenous server capabilities.

REFERENCES

• 1: Khalil Amiri , Garth A. Gibson , Richard Golding, Highly Concurrent Shared Storage, Proceedings of the The 20th International Conference on Distributed Computing Systems ( ICDCS 2000), p.298, April 10-13, 2000
• 2: Remzi H. Arpaci-Dusseau , Eric Anderson , Noah Treuhaft , David E. Culler , Joseph M. Hellerstein , David Patterson , Kathy Yelick, Cluster I/O with River: making the fast case common, Proceedings of the sixth workshop on I/O in parallel and distributed systems, p.10-22, May 05-05, 1999, Atlanta, Georgia, United States [doi>10.1145/301816.301823]
• 3: John S. Bucy and Gregory R. Ganger. The DiskSim simulation environment version 3.0 reference manual. Technical Report CMU--CS--03--102. Department of Computer Science Carnegie-Mellon University, Pittsburgh, PA, January 2003.
• 4: M. D. Dahlin, R. Y. Wang, T. E. Anderson, and D. A. Patterson. Cooperative caching: using remote client memory to improve file system performance. Symposium on Operating Systems Design and Implementation (Monterey, CA, 14--17 November 1994), pages 267--280. IEEE, 1994.
• 5: Zoran Dimitrijevic , Raju Rangaswami , Edward Chang, Design and Implementation of Semi-preemptible IO, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 6: The DiskSim Simulation Environment (Version 3.0). http://www.pdl.cmu.edu/DiskSim/index.html.
• 7: EqualLogic Inc. PeerStorage Overview, 2003. http://www.equallogic.com/pages/products_technology.htm.
• 8: Svend Frolund, Arif Merchant, Yasushi Saito, Susan Spence, and Alistair Veitch. FAB: enterprise storage systems on a shoestring. Hot Topics in Operating Systems (Lihue, HI, 18--21 May 2003), pages 133--138. USENIX Association, 2003.
• 9: Gregory R. Ganger, John D. Strunk, and Andrew J. Klosterman. Self-* Storage: brick-based storage with automated administration. Technical Report CMU-CS-03-178. Carnegie Mellon University, August 2003.
• 10: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 11: HP Labs SSP traces. http://www.hpl.hp.com/research/ssp.
• 12: Hui-I Hsiao , David J. DeWitt, A performance study of three high availability data replication strategies, Proceedings of the first international conference on Parallel and distributed information systems, p.18-29, December 1991, Miami, Florida, United States
• 13: Hui-I Hsiao , David J. DeWitt, Chained Declustering: A New Availability Strategy for Multiprocessor Database Machines, Proceedings of the Sixth International Conference on Data Engineering, p.456-465, February 05-09, 1990
• 14: IBM Almaden Research Center. Collective Intelligent Bricks, August, 2003. http://www.almaden.ibm.com/StorageSystems/autonomic_storage/CIB/index.shtml.
• 15: David M. Jacobson and John Wilkes. Disk scheduling algorithms based on rotational position. Technical report HPL--CSP--91--7. Hewlett-Packard Laboratories, Palo Alto, CA, 24 February 1991, revised 1 March 1991.
• 16: Edward K. Lee , Chandramohan A. Thekkath, Petal: distributed virtual disks, ACM SIGPLAN Notices, v.31 n.9, p.84-92, Sept. 1996
• 17: Sai-Lai Lo. Ivy: a study on replicating data for performance improvment. TR HPL-CSP-90-48. Hewlett Packard, December 1990.
• 18: Christopher R. Lumb , Jiri Schindler , Gregory R. Ganger, Freeblock Scheduling Outside of Disk Firmware, Proceedings of the Conference on File and Storage Technologies, p.275-288, January 28-30, 2002
• 19: Vivek S. Pai , Mohit Aron , Gaurov Banga , Michael Svendsen , Peter Druschel , Willy Zwaenepoel , Erich Nahum, Locality-aware request distribution in cluster-based network servers, ACM SIGPLAN Notices, v.33 n.11, p.205-216, Nov. 1998
• 20: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States
• 21: Steven Schuchart. High on Fibre. Network Computing, 1 December 2002.
• 22: Margo Seltzer, Peter Chen, and John Ousterhout. Disk scheduling revisited. Winter USENIX Technical Conference (Washington, DC, 22--26 January 1990), pages 313--323, 1990.
• 23: Storage Performance Council traces. http://traces.cs.umass.edu/storage/.
• 24: Geoffrey M. Voelker , Eric J. Anderson , Tracy Kimbrel , Michael J. Feeley , Jeffrey S. Chase , Anna R. Karlin , Henry M. Levy, Implementing cooperative prefetching and caching in a globally-managed memory system, ACM SIGMETRICS Performance Evaluation Review, v.26 n.1, p.33-43, June 1998
• 25: John Wilkes , Richard Golding , Carl Staelin , Tim Sullivan, The HP AutoRAID hierarchical storage system, ACM Transactions on Computer Systems (TOCS), v.14 n.1, p.108-136, Feb. 1996 [doi>10.1145/225535.225539]
• 26: Xiang Yu, Benjamin Gum, Yuqun Chen, Randolph Y. Wang, Kai Li, Arvind Krishnamurthy, and Thomas E. Anderson. Trading capacity for performance in a disk array. Symposium on Operating Systems Design and Implementation (San Diego, CA, 23--25 October 2000), pages 243--258. USENIX Association, 2000.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Management, Performance

Keywords:
brick based storage, decentralized systems, disk scheduling, distributed systems, storage systems