# 6-2. CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data
:::info
**CRUSH( Controlled Replication Under Scalable Hashing)**，一個**可伸縮的偽隨機資料分佈演算法**，為了分散式物件儲存系統設計，能**高效地將輸入值（通常是物件或物件群組的識別碼）對應到一系列儲存物件副本的裝置上**，且**不依賴中央目錄**。
CRUSH 被設計來便利存儲設備的添加與移除，同時最大限度地減少不必要的數據移動，適用於許多種類的資料副本和可靠性機制，同時根據使用者定義的策略分佈數據，可以強制將不同的副本分散到不同的failure domain中。
簡而言之就是**一種在分散式儲存系統中用來決定數據如何儲存和分配的算法，特別適合用於大規模儲存系統，如Ceph。**
:::

## Introduction
**object-based storage device(OSD) :** 在內部管理磁碟區塊的分配， 將數據存儲為物件，每個物件包括數據本身、可變長度的元數據以及一個全局唯一的ID，透過以較小的物件列表取代較大的區塊列表，以簡化資料layout並分攤下層的區塊分配問題。

雖然透過減少文件配置的metadata和複雜性大大提高可擴展性，但是將資料分佈到數千個儲存設備上（通常其容量和效能都不同）的問題仍然存在。

CRUSH（Controlled Replication Under Scalable Hashing)是一個偽隨機資料分佈演算法，能夠高效、健壯地將物件副本在異質、結構化儲存集群上分佈，CRUSH的實作是一個偽隨機、確定性的函數，將輸入值（通常是物件或物件群組的識別碼）對應到一系列儲存物件副本的裝置上，只需要一個簡潔的、層次化的描述，涵蓋存儲集群中的設備，以及對副本放置策略的了解。優點如下:
1. 完全是分散式的，大型系統中的任意一方都能單獨計算任何物件的位置。
2. 所需的metadata很少且幾乎是靜態的，它僅在有設備加入或移除時變化。

## The CRUSH algorithm
CRUSH 算法根據每個設備的**權重值**(大致都會符合均勻概率分布)分配數據對象。
>CRASH輸入是一個整數x（例如物件名字的hash值），輸出是n個device的列表。

***hierarchical cluster map*:** 一種表示儲存資源（如服務器、硬碟架等）如何組織的map，例如，一個大型數據中心可能被描述成由多個rows組成，每row包含多個cabinets，每個cabinet裝有多個disk shelves，每個disk shelves裝有多個儲存設備。
數據分布政策是根據*placement rules*定義的，這些規則指定了從集群中選擇多少個副本目標，以及對副本放置施加了哪些限制，例如，可以指定三個鏡像副本應該放置在不同物理櫃中的設備上，以便它們不共享同一電路。
>**確定性映射:** CRUSH通過使用特定的雜湊函數，確保相同的輸入總是產生相同的輸出（數據儲存位置），代表每次查詢都會返回相同的儲存位置。
>**偽隨機分布：** CRUSH生成的數據存放位置看似隨機，但實際上是通過算法確定的，不同數據的存放位置之間看起來沒有明顯的關聯，有助於平均分散風險。

### Hierarchical Cluster Map
>**用來組織和管理分散式儲存系統中的所有儲存資源的一種工具，按照層次結構將儲存設備和其他元素（如bucket）進行分類和組織，以便更有效地控制數據如何在這些設備上分佈和複製。**

Cluster Map由*device*和*bucket*組成，他們都有numerical identifiers和相關的權重值，*bucket*可以包含任意數量的*device*或其他*bucket*，使它們能夠在storage hierarchy中形成內部節點，其中*device*始終位於leave。
*bucket*可以任意組合以構建代表可用存儲的層次結構，如將device組成shelf buckets，再將shelf buckets組成cabinet bucket，依此類推。
* weight設定: *device*的權重由管理員設定，以控制其存儲的數據量，*bucket*的權重則是其內含項目的權重總和。

>**和傳統hash哪裡不同?**
>傳統技術中target bins (devices) results數量的任何變化都會導致bin內容大規模重新洗牌，CRUSH 基於四種不同的bucket類型，每種都有不同的選擇演算法來解決設備增加或移除及整體計算複雜性所產生的data movement resulting。

### Replica Placement
CRUSH放置策略可以在維護所需的分佈同時將物件的副本分散到不同的故障域中。無論是在數據複製策略還是在底層硬體配置，CRUSH 定義了每個複製策略或分佈政策使用的放置規則(*placement rules*)，允許存儲系統或管理員準確指定物件副本的放置方式，每條規則由一系列被應用於hierarchy的操作組成。

*Table 1*中定義的規則從*Figure 1* hierarchy的root開始，第一個$select(1,row)$選取了一個類型為「row」的bucket（row2），之後的$select(3,cabinet)$在先前選取的row2內選擇了3個不同的cabinet（cab21、cab23、cab24），最後，每個$select(1,disk)$遍歷其輸入向量中的3個cabinet bucket之一，並選擇其下的1個disk。最後結果是分散在3個cabinet中的3個disk，但是都在同一個row中。

上圖的*take*表示選擇一個節點加到目前清單中，*select*會在清單中每個節點上套用，選擇n個符合條件的節點出來。

這種方法讓副本能跨副本分佈且對容器類型（例如，row、cabinet、shelf）進行約束，兼顧了可靠性和性能。

#### Collisions, Failure, and Overload
$select(n, t)$操作可能從它的起始點開始穿過多個儲存層級以找到其下的$n$個不同的類型為$t$的item，是一個以$r$（$r=1,…n$，n是所選的副本編號）作為部分參數的遞歸過程。
可能因為下列三種情況CRASH reject並reselect item並修改輸入$r'$：
1. item已經被選取到目前的集合中 (collision, $select(n,t)$的結果必須是不重複的)
>solution: 會首先使用改變後的$r'$，避免整體資料分佈偏離更可能發生衝突的子樹（例如，bucket數小於n的子樹），也就是在在下一層重試
2. device failed or overload
>solution: CRUSH會重新開始從$select(n,t)$開始處的遞歸，均勻地將它們的item分佈到存儲集群中。也就是在在目前層級重試。

#### Replica Ranks
同層重試的兩種不同方法
* **primary copy replication scheme:** **適用於不同設備儲存相同replica的情況**，副本常常希望在先前的目標副本（已經有一份資料拷貝的副本）故障後成為新的主副本，CRUSH可以用$r ' = r + f$ 來重新選取前n個合適的目標，其中$f$是當前的$select(n,t)$的失敗的放置嘗試次數。
* **Parity and erasure coding schemes:** **適用於不同設備儲存不同內容的情況**，CRUSH輸出中的device的排名或位置十分重要，CRUSH會使用$r ' = r + f_{r} n$重新選取，其中$f_{r}$是在item $r$上的失敗嘗試的次數。

### Map Changes and Data Movement
failed和overloaded兩種裝置都會留在cluster map中，只是有不同的標記。
* failed裝置上的已有物件會被移轉到其它正常裝置上，預期遷移比例為$W_{failed} /W$。
* overloaded設備只是不再接受新對象，已有對像不需要遷移

當有設備加入或移除時，需要遷移的資料量也與權重有關：權重被降低的子樹會有資料遷移到權重被升高的子樹上。資料遷移量的下界是$\frac{ \Delta w}{W}$，上界是$h \frac{ \Delta w}{W}$，其中h是樹的高度，但達到上界的機率非常小，因為需要每層資料都對應到一個權重非常小的item上。

### Bucket Types
CRUSH支援4種bucket，每種不同的bucket類型都基於不同的內部資料結構，分別有不同的選擇演算法。
* **Uniform Buckets:**
所包含的item必須全都有相同的權重。
給定CRUSH的輸入$x$和一個副本編號$r$，$c(r,x)=(hash(x)+rp) \mod m$從大小為$m$的uniform bucket中選擇一個item，其中p是某個大於m的質數。
選擇的時間複雜度為O(1)，但如果uniform bucket的大小改變，會發生device間的完整的資料重調配，適合設備不怎麼變動的場景。

* **List Buckets:**
item的權重可以不同，選擇時比較head的權重與剩餘權重和來決定選擇head還是繼續(選擇最近被加入的item還是之前的item)。
當item被加入bucket時，資料遷移最優(（與權重比例相同)，但當移除非head節點時會造成大量資料遷移（越接近tail越多），因此最適合bucket幾乎不移除的情況。
list bucket對於較小的item的集合效率很高，但是可能不適用於較大的集合，因為其$O(n)$的運轉時間可能太大。
能在新item被加入到head時提供最優的資料移動。

* **Tree Buckets:** (TODO???)
item的權重可以不同，根據左右子樹的權重和選擇插入路徑。為了避免樹擴張或收縮過程中節點的label發生變化，tree bucket使用了一種路徑標記的方式（左子樹1，右子樹0）來產生label。

* **Straw Buckets:**
item的權重可以不同，根據item和節點的權重，每個節點產生一個hash值，然後選擇其中最大的一個。
$c(r,x)= \max _i ( f( w_i ) hash(x,r,i) )$
雖然這個過程幾乎比list bucket慢兩倍甚至比tree bucket還要慢，但是能在變更時得到最優的內部item間的資料移動。
能在子樹間提供最優的遷移行為。

Table 2總結了上述四個bucket的差異

## Evaluation
### Data Distribution
CRUSH的資料分佈應該是隨機分佈的，與物件識別碼x和儲存裝置都是不相關的，並以相同的權重均勻分佈在設備中。
發現對於由相同device組成的集群和不同權重的device組成的集群中，CRUSH的分佈的平均值與標準差與二項分佈的相匹配。

#### Overload Protection
CRUSH有一個過載修正機制，能夠重新分配資料。這使得當一個設備有過載危險時，可以按照過度使用的情況成比例地縮減設備的分配量，有選擇地穩定過載設備。

#### Variance and Partial Failure
CRUSH使用現有的負載校正機制將效能下降的設備當作「局部異常」設備處理，並轉移特定的資料和工作負載以避免效能瓶頸的出現，同時即時校正負載平衡。

### Reorganization and Data Movement
### Algorithm Performance
### Reliability

## Future Work
CRUSH 是作為 Ceph 分散式檔案系統的一部分(正在開發)，目前研究聚焦於開發基於CRUSH 特色的分散式物件存儲。
設計 CRUSH 的主要動機是解決因故障重疊導致的數據安全問題，需要進一步研究更快的hash技術來確定故障的性質和頻率。

## Conclusions
CRUSH通過將數據放置定義為偽隨機映射函數，來解決分散式儲存系統中數據放置的可擴展性挑戰，省去了傳統所需的配置元數據，而是基於描述可用存儲的加權層次結構來分配數據，將對象副本分隔到不同的用戶定義故障域中（例如，具有獨立的電力和網絡基礎設施），減少現有偽隨機系統中因declustered replication而導致的設備故障的問題。
映射計算運行時間為O(logn)，執行迅速，可靠性強，適合大規模分散式儲存系統。

## Reference
[翻譯] https://blog.mrcroxx.com/posts/paper-reading/weil-crush-sc06/#321-%E7%A2%B0%E6%92%9E%E6%95%85%E9%9A%9C%E4%B8%8E%E8%BF%87%E8%BD%BD
[翻譯] https://www.cnblogs.com/pcxie/p/7718452.html
[筆記] https://fuzhe1989.github.io/2021/04/26/crush-controlled-scalable-decentralized-placement-of-replicated-data/