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的論文：//ceph.com/assets/pdfs/weil-crush-sc06.pdf。

Crush是一個優秀的分布式存儲數據路由和均衡算法，它對存儲系統進行了抽象描述，對選取物理存儲節點的過程也進行了抽象描述，并采用經驗證的帶權重隨機采樣算法保證了在大規模場景下數據分布的均衡性。