SPREAD: an adaptive scheme for redundant and fair storage in dynamic heterogeneous storage systems

ABSTRACT

In this paper we study the problem of designing an adaptive hash table for redundant data storage in a system of storage devices with arbitrary capacities. Ideally, such a hash table should make sure that (a) a storage device with x% of the available capacity should get x% of the data, (b) the copies of each data item are distributed among the storage devices so that no two copies are stored at the same device, and (c) only a near-minimum amount of data replacements is necessary to preserve (a) and (b) under any change in the system. Hash tables satisfying (a) and (c) are already known, and it is not difficult to construct hash tables satisfying (a) and (b). However, no hash table is known so far that can satisfy all three properties as long as this is in principle possible. We present a strategy called SPREAD that solves this problem for the first time. As long as (a) and (b) can in principle be satisfied, SPREAD preserves (a) for every storage device within a (1 ± ε) factor, with high probability, where ε > 0 can be made arbitrarily small, guarantees (b) for every data item, and only needs a constant factor more data replacements than minimum possible in order to preserve (a) and (b).

REFERENCES

• 1: Witold Litwin , Thomas Schwarz, LH*RS: a high-availability scalable distributed data structure using Reed Solomon Codes, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.237-248, May 15-18, 2000, Dallas, Texas, United States
• 2: A. Brinkmann , S. Effert , F. Meyer auf der Heide, Dynamic and Redundant Data Placement, Proceedings of the 27th International Conference on Distributed Computing Systems, p.29, June 25-27, 2007 [doi>10.1109/ICDCS.2007.103]
• 3: André Brinkmann , Kay Salzwedel , Christian Scheideler, Efficient, distributed data placement strategies for storage area networks (extended abstract), Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.119-128, July 09-13, 2000, Bar Harbor, Maine, United States [doi>10.1145/341800.341815]
• 4: André Brinkmann , Kay Salzwedel , Christian Scheideler, Compact, adaptive placement schemes for non-uniform requirements, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564878]
• 5: R. J. Enbody , H. C. Du, Dynamic hashing schemes, ACM Computing Surveys (CSUR), v.20 n.2, p.850-113, June 1988 [doi>10.1145/46157.330532]
• 6: R. J. Honicky , Ethan L. Miller, A Fast Algorithm for Online Placement and Reorganization of Replicated Data, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.57.2, April 22-26, 2003
• 7: R. J. Honicky and E. L. Miller. Replication Under Scalable Hashing: A Family of Algorithms for Scalable Decentralized Data Distribution. In Proceedings of the 18th IPDPS Conference, 2004.
• 8: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 9: W. Litwin, J. Menon, and T. Risch. LH* schemes with scalable availability. Technical Report RJ 10121 (91937), IBM Research, Almaden Center, May 1998.
• 10: W. Litwin , M.-A. Neimat, High-Availability LH* Schemes with Mirroring, Proceedings of the First IFCIS International Conference on Cooperative Information Systems, p.196, June 19-21, 1996
• 11: Witold Litwin , Marie-Anna Neimat , Donovan A. Schneider, LH*—a scalable, distributed data structure, ACM Transactions on Database Systems (TODS), v.21 n.4, p.480-525, Dec. 1996 [doi>10.1145/236711.236713]
• 12: Witold Litwin , Tore Risch, LH*G: A High-Availability Scalable Distributed Data Structure By Record Grouping, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.923-927, July 2002 [doi>10.1109/TKDE.2002.1019223]
• 13: C. McDiarmid. On the method of bounded differences. In J. Siemons, editor, Surveys in Combinatorics. London Mathematical Society Lecture Note Series 141, Cambridge University Press, 1989.
• 14: C. McDiarmid. Concentration. In M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, editors, Probabilistic Methods for Algorithmic Discrete Mathematics, pages 195--247. Springer Verlag, Berlin, 1998.
• 15: Peter Sanders, Reconciling simplicity and realism in parallel disk models, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.67-76, January 07-09, 2001, Washington, D.C., United States
• 16: Christian Schindelhauer , Gunnar Schomaker, Weighted distributed hash tables, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1074008]

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies; Distributed memories

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

General Terms:
Algorithms, Design, Management, Theory