共計 6229 個字符，預計需要花費 16 分鐘才能閱讀完成。
這篇文章主要介紹 Ceph 中 CRUSH 算法的示例分析，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！
一、bucket 數據結構介紹。
struct crush_bucket {
__s32 id; //bucket 的 ID 號，crushmap 中所有 bucket 的編號都是負數
__u16 type; //bucket 的類型(uniform/list/tree/straw/straw2)
__u8 alg; //bucket 使用的算法
__u8 hash; //bucket 使用哪種 hash 算法
__u32 weight; //bucket 權重值
__u32 size; //bucket 中包含的 items 的數量
__s32 *items; //bucket 中包含的 items 內容
__u32 perm_x; // 緩存進行隨機排列的輸入值
__u32 perm_n; // 緩存隨機排列結果 perm 中可用的個數
__u32 *perm; // 對 bucket 中 items 的緩存隨機排列結果
};
二、uniform 類型。
1、uniform 類型 bucket 的數據結構。
struct crush_bucket_uniform {
struct crush_bucket h; // 通用 bucket 定義
__u32 item_weight; //uniform bucket 中所有 items 的權重值(uniform 類型的 bucket，其所有 items 的權重值是一樣的)
};
2、uniform 類型 bucket 算法分析。
輸入參數：
1）crush_bucket_uniform 結構；
2）待執行運算的輸入值 x；
3）輸入值 x 的副本位置 r；
輸出參數：
1）經過 uniform 算法計算后的 bucket 中的 item；
算法分析：
1）對于第一次執行 uniform 算法來說，經過 hash()函數計算出來一個隨機數后對 bucket.h.size 取模，得到一個隨機的 item 位置，之后將這個隨機位置寫入到 bucket.h.perm[0]中且返回該隨機數指定的 bucket.h.item；
2）對于后續執行 uniform 算法來說，由于 bucket.h.perm[]中已經有隨機數且 bucket.h.perm_n 中保存 bucket.h.perm[]中可用的隨機數的個數，因此，對于副本位置 r 來說，若 r%bucket.h.size bucket.h.perm_n，則直接從 bucket.h.perm[r%bucket.h.size]獲取隨機數，之后返回該隨機數指定的 bucket.h.item。若 r%bucket.h.size =bucket.h.perm_n，則需要執行 hash()函數計算出來一個隨機數后對 (bucket.h.size-bucket.h.perm_n) 取模，得到 i，之后將 bucket.h.perm[]中 bucket.h.perm_n+ i 與 bucket.h.perm_n 位置的內容互換，之后 bucket.h.perm_n++，反復執行，直到 r%bucket.h.size bucket.h.perm_n。最后從 bucket.h.perm[r%bucket.h.size]獲取隨機數，之后返回該隨機數指定的 bucket.h.item；
uniform 類型算法流程圖
3、uniform 算法適用條件。
1）bucket 中所有的 items 的權重是一樣的，也就是說 uniform 算法不考慮權重；
2）uniform 算法適合 bucket 中的 item 不經常變更的情況，若經常變更則 bucket.h.size 會變化，從而導致 bucket.h.perm_n 需要重新計算，數據會大面積的遷移；
三、list 類型。
1、list 類型 bucket 的數據結構。
struct crush_bucket_list {
struct crush_bucket h; // 通用 bucket 定義
__u32 *item_weight; //bucket 中每個 item 的權重值
__u32 *sum_weight; //bucket 中從第一個 item 開始到第 i 個 item 的權重值之和
};
2、list 類型 bucket 算法分析。
輸入參數：
1）crush_bucket_list 結構；
2）待執行運算的輸入值 x；
3）輸入值 x 的副本位置 r；
輸出參數：
1）經過 list 算法計算后的 bucket 中的 item；
算法分析：
1）從 bucket 中最后一個 item 開始反向遍歷整個 items，執行 hash()函數計算出一個隨機數 w；
2）將該隨機數 w 乘以 bucket.sum_weight[i]，之后將結果右移 16 位；
3）判斷右移 16 位后的結果和 bucket.item_weight[i]，若結果小于 bucket.item_weight[i]則直接返回 bucket.h.items[i]，否則反向遍歷 bucket 中下一個 item；
4）若所有右移 16 位后的結果都大雨 bucket.sum_weight[i]，則最終返回 bucket.h.items[0]；
list 類型算法原理圖
list 類型算法流程圖
3、list 算法適用條件。
1）適用于集群拓展類型。當增加 item 時，會產生最優的數據移動。因為在 list bucket 中增加一個 item 節點時，都會增加到 head 部，這時其他節點的 sum_weight 都不會發生變化，只需要將 old_head 上的 sum_weight 和 weight 之和添加到 new_head 的 sum_weight 就好了。這樣時其他 item 之間不需要進行數據移動，其他的 item 上的數據 只需要和 head 上比較就好，如果算的 w 值小于 head 的 weight，則需要移動到 head 上，否則還保存在原來的 item 上。這樣就獲得了最優最少的數據移動；
2）list bucket 存在一個缺點，就是在查找 item 節點時，只能順序查找 時間復雜度為 O(n)；
四、tree 類型。
1、tree 類型 bucket 的數據結構。
struct crush_bucket_tree {
struct crush_bucket h; // 通用 bucket 定義
__u8 num_nodes; // 記錄 node_weights 中的所有節點個數(包括二叉樹中間節點和葉子節點)
__u32 *node_weights; // 除了 bucket 中 item 的權重值外，node_weights 中還包含一個二叉樹結構的權重值，其中 bucket 中的 item 是樹的葉子節點，二叉樹的中間節點的權重值是左右兩個字節點權重值之和
};
2、tree 類型 bucket 算法分析。
輸入參數：
1）crush_bucket_tree 結構；
2）待執行運算的輸入值 x；
3）輸入值 x 的副本位置 r；
輸出參數：
1）經過 tree 算法計算后的 bucket 中的 item；
算法分析：
1）找到二叉樹的根節點，即：n=bucket.num_nodes 1；
2）判斷當前節點是否是葉子節點，若不是則從 bucket.node_weights[n]中得到二叉樹上對應中間節點的權重值，之后執行 hash()函數的到一個隨機數，之后將這個隨機數乘以中間節點的權重值，再右移 32 位。將經過調整后的權重值與該中間節點左子樹的權重值進行比較，若小于左子樹的權重值則從左子樹開始遍歷，否則從柚子樹開始遍歷；
3）當前節點到達葉子節點，則返回該葉子節點指定的 item，即：bucket.h.items[n 1]；
tree 類型算法原理圖
tree 類型算法流程圖
3、tree 算法適用條件。
1）使用 tree 算法時定位數據的時間復雜度為 O(logn)，這使其適用于管理大得多設備數量或嵌套 buckets；
2）樹狀 buckets 是一種適用于任何情況的 buckets，兼具高性能與出色的重組效率；
五、straw 類型。
1、straw 類型 bucket 的數據結構。
struct crush_bucket_straw {
struct crush_bucket h; // 通用 bucket 定義
__u32 *item_weights; // 保存 bucket 中所有 item 的權重值
__u32 *straws; // 保存根據 item 權重值計算出來的權重值
2、straw 類型 bucket 算法分析。
輸入參數：
1）crush_bucket_straw 結構；
2）待執行運算的輸入值 x；
3）輸入值 x 的副本位置 r；
輸出參數：
1）經過 straw 算法計算后的 bucket 中的 item；
算法分析：
1）順序遍歷 backet 中所有的 items，對于 bucket 中每一個 item 執行 hash()算法計算出一個隨機數，之后將該隨機數與 bucket.staws[i]相乘，得到一個修正后的隨機值；
2）比較 bucket 中所有 items 經過 hash()算法算出的修正后的隨機值且找到最大的修正后的隨機值；
3）返回最大的修正后的隨機值位置所在的 item，即：bucket.h.item[high]；
straw 算法原理圖
3、straw 數組的生成過程分析。
1）根據 bucket.item_weights[bucket.h.size]數組，生成一個按照 items 權重值從小到大排序的數組 reverse[bucket.h.size]且 reverse[bucket.h.size]中保存的是按序排列的 item 權重值的下標；
2）初始化計算 straw 算法所使用的變量。
numleft=bucket.h.size;
straw=1.0;
lastw=0;
wbelow=0;
3）遍歷整個 items，按照如下算法計算 items 對應的 straw 值。
A）對于 bucket.item_weights[reverse[i]]==0，則 straw[reverse[i]]=0；
B）設置 straw 值。bucket.straw[reverse[i]]=straw*0x1000；
C）變量 i+1；
D）計算 wbelow 值。wbelow=(bucket.item_weights[reverser[i-1])-lastw)*numleft；
E）變量 numleft-1；
F）計算 wnext 值。wnext=numleft*(bucket.item_weights[reverse[i]-bucket.item_weight[revese[i-1])；
G）計算 pbelow 值。pbelow=wbelow/(wbelow+wnext)；
H）計算 straw 值。straw=pow(1/pbelow,1/numleft)；
I）計算 lastw 值。lastw=bucket.item_weights[reverse[i-1]]；
對于 bucket 中所有的 items 來說，權重越大，計算出來的 straw 值就越大；
從算法來看，計算 item 的 straw 值與 item 的權重值以及 item 之前的權重值有關，因此在修改 bucket 中某一個 item 的權重值時會影響該 item 及其前后 items 的 straw 值；
4、straw 算法適用條件。
1）考慮權重對數據分布的影響，即：權重值高的 item 來說，被選中的概率就大，落在權重值高的 item 的數據越多；
2）straw 類型的 buckets 可以為子樹之間的數據移動提供最優的解決方案；
六、straw2 類型。
1、straw2 類型 bucket 的數據結構。
struct crush_bucket_straw2 {
struct crush_bucket h; // 通用 bucket 定義
__u32 *item_weights; // 保存 bucket 中所有 item 的權重值
};
2、straw2 類型 bucket 算法分析。
輸入參數：
1）crush_bucket_straw2 結構；
2）待執行運算的輸入值 x；
3）輸入值 x 的副本位置 r；
輸出參數：
1）經過 straw2 算法計算后的 bucket 中的 item；
算法分析：
1）遍歷整個 bucket 的所有 items，得到 items 對應的權重值；
2）對于非零權重值來說，首先執行 hash()函數計算出一個隨機數，之后將該隨機數作為參數調用最小指數隨機變量分布算法得到的結果再減去 0x1000000000000，最后將該結果除以 item 權重值得到 item 對應的最終值 (draw)。對于權重值為零來說，最終值(draw) 為最小值；
3）比較整個 bucket 中所有 items 計算出來的最終值(draw)，取最終值最大的 item，即：bucket.h.items[high]；
從算法來看，計算 item 的 straw 值只與 item 的權重值有關，與 bucket 中其它 items 的權重值無關。因此在修改 bucket 中某一個 item 的權重值時不會影響該 bucket 中其它 items 的 straw 值；
3、straw2 算法適用條件。
1）考慮權重對數據分布的影響，即：權重值高的 item 來說，被選中的概率就大，落在權重值高的 item 的數據越多；
2）straw 類型的 buckets 可以為子樹之間的數據移動提供最優的解決方案；
3）適合 bucket 中的 items 權重動態變化的場景；
以上是“Ceph 中 CRUSH 算法的示例分析”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注丸趣 TV 行業資訊頻道！
