Crush（Controlled Replication Under Scalable Hashing）全称为受控的可扩展副本Hash算法，它是Ceph分布式存储系统的基石之一。Crush算法的目标是为PB级别的分布式存储系统实现数据路由，数据及副本按照故障域均衡分布。

Crush算法有三个核心要素，1. 集群拓扑结构描述（Hierarchical Cluster Map）2. 自定义数据及副本放置规则（Replica Placement）3. 支持按存储硬件设置的权重随机数据分布，且在不同级别硬件故障时保证高可用且数据迁移较少。

Crush采用map数据结构描述了一个树状结构的集群拓扑，树的根节点称为root节点，依次往下可以有数据中心（datacenter），机房（room），机柜（rack）,主机（host），物理磁盘（osd）等构成，树中的叶子节点是实际负责数据存储的最小硬件单元。叶子节点按其物理存储能力等配置有权重，后续将根据该权重能够分配对应大小的数据量到该叶子节点。一个典型的集群拓扑结构如下图所示：

Crush支持自定义数据及副本放置规则，支持副本池策略（副本数可配置）和EC池策略（m+n可配置）。数据及副本放置规则描述了从集群拓扑中选取OSD的过程，允许从集群拓扑树中的某个节点开始，按照运维人员配置的Crush Rule规则（主要是指定副本策略，故障域级别等），选取特定数量的OSD来存储应用数据。一个典型的副本池Crush Rule如下图所示：

Crush算法选取OSD节点的过程是一个从根节点深度遍历或广度遍历的过程。从根节点开始，通过Hash算法计算得到当前节点所有孩子节点的签长（签长描述了这些孩子节点被抽签选中的概率，签长越长该孩子节点被选中的概率越大）。Crush算法中使用straw2 Hash算法来计算孩子节点的签长，这是一种能够实现按权重随机采样的稳定Hash算法，算是Crush算法实现数据随机均衡的关键，如需深入了解straw2的随机均衡采样，可以参考Crush的论文：https://ceph.com/assets/pdfs/weil-crush-sc06.pdf。

Crush是一个优秀的分布式存储数据路由和均衡算法，它对存储系统进行了抽象描述，对选取物理存储节点的过程也进行了抽象描述，并采用经验证的带权重随机采样算法保证了在大规模场景下数据分布的均衡性。