CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data

Appeared in Proceedings of SC '06.

Abstract

Emerging large-scale distributed storage systems are faced with the task of distributing petabytes of data among tens or hundreds of thousands of storage devices. Such systems must evenly distribute data and workload to efficiently utilize available resources and maximize system performance, while facilitating system growth and managing hardware failures. We have developed CRUSH, a scalable pseudo-random data distribution function designed for distributed object-based storage systems that efficiently maps data objects to storage devices without relying on a central directory. Because large systems are inherently dynamic, CRUSH is designed to facilitate the addition and removal of storage while minimizing unnecessary data movement. The algorithm accommodates a wide variety of data replication and reliability mechanisms and distributes data in terms of user-defined policies that enforce separation of replicas across failure domains.

Publication date:
November 2006

Authors:
Sage Weil
Scott A. Brandt
Ethan L. Miller
Carlos Maltzahn

Projects:
Ultra-Large Scale Storage

Available media

Full paper text: PDF

Bibtex entry

@inproceedings{weil-sc06,
  author       = {Sage Weil and Scott A. Brandt and Ethan L. Miller and Carlos Maltzahn},
  title        = {{CRUSH}: Controlled, Scalable, Decentralized Placement of Replicated Data},
  booktitle    = {Proceedings of SC '06},
  month        = nov,
  year         = {2006},
}