本篇文章是对论文CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data的翻译和提炼，探究它是什么、解决了什么问题、怎么实现的三个方面。
CRUSH是什么
CRUSH，全称是 Controlled Scalable Decentralized Placement of Replicated Data，可控的、可扩展的、分布式的副本数据放置算法。
分布式系统中数据分布算法挑战：
- 数据分布和负载均衡：
- a. 数据分布均衡，使数据能均匀的分布到各个节点上。
- b. 负载均衡，使数据访问读写操作的负载在各个节点和磁盘的负载均衡。
- 灵活应对集群伸缩
- a. 系统可以方便的增加或者删除节点设备，并且对节点失效进行处理。
- b. 增加或者删除节点设备后，能自动实现数据的均衡，并且尽可能少的迁移数据。
- 支持大规模集群
- a. 要求数据分布算法维护的元数据相对较小，并且计算量不能太大。随着集群规模的增 加，数据分布算法开销相对比较小。
CRUSH解决了什么问题
CRUSH解决了对象数据在分布式系统中的寻址和分布不均衡的问题，通过此算法可以在任意地方能找寻到数据，并且数据会随着节点的增加或者减少重新动态平衡。
大部分分布书存储系统简单地将新数据写入到未被充分利用的设备上。这种方法的根本问题是，当数据被写入后，它很少甚至不会被移动。即使是完美的分布也会在存储系统被扩展后变得不均衡，因为新的磁盘或者是空的或者仅含有新的数据。旧的磁盘和新的磁盘可能都是繁忙的，这取决于系统负载，但是这很少能够平等地利用二者并得到所有可用资源的优势。
一种健壮的解决方案是将所有数据随机分布到系统中可用的存储设备上。这样可以使分布在概率上是均衡的，且新数据和旧数据会均匀地混合在一起。当添加新的存储时，已有数据的中的一份随机采样会被迁移到新的存储设备上以保持平衡。这种方法最重要的优势是平均，所有设备将会有相似的负载，让系统在任何潜在负载下表现良好。
CRUSH（Controlled Replication Under Scalable Hashing，基于可伸缩哈希的受控多副本策略），它是一个伪随机数据分布算法，它能够高效、健壮地将对象副本在异构、结构化存储集群上分布。CRUSH的实现是一个伪随机、确定性的函数，它将输入值（通常是一个对象或对象组的标识符）映射到一系列存储对象副本的设备上。它与传统方法的不同点在于，它的数据分配不依赖每个文件或每个对象的任何类型的目录——CRUSH仅需要对构成存储集群的设备的紧凑的层次结构的描述和副本分配策略的知识。这种方法有两个关键的好处：第一，它完全是分布式的，大型系统中的任意一方都能单独计算任何对象的位置；第二，所需的元数据很少且几乎是静态的，它仅在有设备加入或移除时变化。
分布式存储系统如GFS这些都面临着数据分布问题，这些系统使用半随机（semi-random）或基于启发式（heuristic-based）的方法来将数据分配到可用容量的存储设备上，但是很少将数据重新放置以随着时间维护均衡的分布，并且这些系统都通过某种元数据的方式来定位数据（简单说就是有一个Metadata Server来记录了对象数据所在位置，通过hash的形式来定位数据）。
CRUSH基于RUSH算法族[Honicky and Miller 2004]。RUSH是已有的文献中唯一的一个利用映射函数替代显式元数据，并支持设备添加或移除的算法。尽管RUSH算法有这些特性，但是大量的问题使其无法实际应用。CRUSH完整地包括了RUSHP和RUSHT中好用的元素，同时解决了之前未解决的可靠性和副本问题，并优化了性能和灵活性。