Ceph中CRUSH算法的示例分析

這篇文章主要介紹Ceph中CRUSH算法的示例分析，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

一、bucket數(shù)據(jù)結(jié)構(gòu)介紹。

     struct crush_bucket {

          __s32      id;          //bucket的ID號(hào)，crushmap中所有bucket的編號(hào)都是負(fù)數(shù)

          __u16      type;     //bucket的類型(uniform/list/tree/straw/straw2)

          __u8        alg;       //bucket使用的算法

          __u8        hash;      //bucket使用哪種hash算法

          __u32      weight;     //bucket權(quán)重值

          __u32      size;          //bucket中包含的items的數(shù)量

          __s32      *items;      //bucket中包含的items內(nèi)容

          __u32      perm_x;     //緩存進(jìn)行隨機(jī)排列的輸入值

          __u32      perm_n;     //緩存隨機(jī)排列結(jié)果perm中可用的個(gè)數(shù)

          __u32      *perm;       //對(duì)bucket中items的緩存隨機(jī)排列結(jié)果

     };

二、uniform類型。

     1、uniform類型bucket的數(shù)據(jù)結(jié)構(gòu)。

          struct crush_bucket_uniform {

               struct crush_bucket h;          //通用bucket定義

               __u32      item_weight;          //uniform bucket中所有items的權(quán)重值(uniform類型的bucket，其所有items的權(quán)重值是一樣的)

          };

     2、uniform類型bucket算法分析。

          輸入?yún)?shù)：

               1）crush_bucket_uniform結(jié)構(gòu)；

               2）待執(zhí)行運(yùn)算的輸入值x；

               3）輸入值x的副本位置r；

          輸出參數(shù)：

               1）經(jīng)過uniform算法計(jì)算后的bucket中的item；

          算法分析：

               1）對(duì)于第一次執(zhí)行uniform算法來說，經(jīng)過hash()函數(shù)計(jì)算出來一個(gè)隨機(jī)數(shù)后對(duì)bucket.h.size取模，得到一個(gè)隨機(jī)的item位置，之后將這個(gè)隨機(jī)位置寫入到bucket.h.perm[0]中且返回該隨機(jī)數(shù)指定的bucket.h.item；

               2）對(duì)于后續(xù)執(zhí)行uniform算法來說，由于bucket.h.perm[]中已經(jīng)有隨機(jī)數(shù)且bucket.h.perm_n中保存bucket.h.perm[]中可用的隨機(jī)數(shù)的個(gè)數(shù)，因此，對(duì)于副本位置r來說，若r%bucket.h.size<bucket.h.perm_n，則直接從bucket.h.perm[r%bucket.h.size]獲取隨機(jī)數(shù)，之后返回該隨機(jī)數(shù)指定的bucket.h.item。若r%bucket.h.size>=bucket.h.perm_n，則需要執(zhí)行hash()函數(shù)計(jì)算出來一個(gè)隨機(jī)數(shù)后對(duì)(bucket.h.size-bucket.h.perm_n)取模，得到i，之后將bucket.h.perm[]中bucket.h.perm_n+i與bucket.h.perm_n位置的內(nèi)容互換，之后bucket.h.perm_n++，反復(fù)執(zhí)行，直到r%bucket.h.size < bucket.h.perm_n。最后從bucket.h.perm[r%bucket.h.size]獲取隨機(jī)數(shù)，之后返回該隨機(jī)數(shù)指定的bucket.h.item；

uniform類型算法流程圖

     3、uniform算法適用條件。

          1）bucket中所有的items的權(quán)重是一樣的，也就是說uniform算法不考慮權(quán)重；

          2）uniform算法適合bucket中的item不經(jīng)常變更的情況，若經(jīng)常變更則bucket.h.size會(huì)變化，從而導(dǎo)致bucket.h.perm_n需要重新計(jì)算，數(shù)據(jù)會(huì)大面積的遷移；

三、list類型。

     1、list類型bucket的數(shù)據(jù)結(jié)構(gòu)。

          struct crush_bucket_list {

               struct crush_bucket h;          //通用bucket定義

               __u32     *item_weight;          //bucket中每個(gè)item的權(quán)重值

               __u32     *sum_weight;          //bucket中從第一個(gè)item開始到第i個(gè)item的權(quán)重值之和

          };

     2、list類型bucket算法分析。

          輸入?yún)?shù)：

               1）crush_bucket_list結(jié)構(gòu)；

               2）待執(zhí)行運(yùn)算的輸入值x；

               3）輸入值x的副本位置r；

          輸出參數(shù)：

               1）經(jīng)過list算法計(jì)算后的bucket中的item；

          算法分析：

               1）從bucket中最后一個(gè)item開始反向遍歷整個(gè)items，執(zhí)行hash()函數(shù)計(jì)算出一個(gè)隨機(jī)數(shù)w；

               2）將該隨機(jī)數(shù)w乘以bucket.sum_weight[i]，之后將結(jié)果右移16位；

               3）判斷右移16位后的結(jié)果和bucket.item_weight[i]，若結(jié)果小于bucket.item_weight[i]則直接返回bucket.h.items[i]，否則反向遍歷bucket中下一個(gè)item；

               4）若所有右移16位后的結(jié)果都大雨bucket.sum_weight[i]，則最終返回bucket.h.items[0]；

list類型算法原理圖

list類型算法流程圖

     3、list算法適用條件。

          1）適用于集群拓展類型。當(dāng)增加item時(shí)，會(huì)產(chǎn)生最優(yōu)的數(shù)據(jù)移動(dòng)。因?yàn)樵趌ist bucket中增加一個(gè)item節(jié)點(diǎn)時(shí)，都會(huì)增加到head部，這時(shí)其他節(jié)點(diǎn)的sum_weight都不會(huì)發(fā)生變化，只需要將old_head 上的sum_weight和weight之和添加到new_head的sum_weight就好了。這樣時(shí)其他item之間不需要進(jìn)行數(shù)據(jù)移動(dòng)，其他的item上的數(shù)據(jù) 只需要和 head上比較就好，如果算的w值小于head的weight，則需要移動(dòng)到head上，否則還保存在原來的item上。這樣就獲得了最優(yōu)最少的數(shù)據(jù)移動(dòng)；

          2）list bucket存在一個(gè)缺點(diǎn)，就是在查找item節(jié)點(diǎn)時(shí)，只能順序查找 時(shí)間復(fù)雜度為O(n)；

四、tree類型。

     1、tree類型bucket的數(shù)據(jù)結(jié)構(gòu)。

          struct crush_bucket_tree {

               struct crush_bucket h;          //通用bucket定義

               __u8      num_nodes;             //記錄node_weights中的所有節(jié)點(diǎn)個(gè)數(shù)(包括二叉樹中間節(jié)點(diǎn)和葉子節(jié)點(diǎn))

               __u32      *node_weights;      //除了bucket中item的權(quán)重值外，node_weights中還包含一個(gè)二叉樹結(jié)構(gòu)的權(quán)重值，其中bucket中的item是樹的葉子節(jié)點(diǎn)，二叉樹的中間節(jié)點(diǎn)的權(quán)重值是左右兩個(gè)字節(jié)點(diǎn)權(quán)重值之和

          };

     2、tree類型bucket算法分析。

          輸入?yún)?shù)：

               1）crush_bucket_tree結(jié)構(gòu)；

               2）待執(zhí)行運(yùn)算的輸入值x；

               3）輸入值x的副本位置r；

          輸出參數(shù)：

               1）經(jīng)過tree算法計(jì)算后的bucket中的item；

          算法分析：

               1）找到二叉樹的根節(jié)點(diǎn)，即：n=bucket.num_nodes >> 1；

               2）判斷當(dāng)前節(jié)點(diǎn)是否是葉子節(jié)點(diǎn)，若不是則從bucket.node_weights[n]中得到二叉樹上對(duì)應(yīng)中間節(jié)點(diǎn)的權(quán)重值，之后執(zhí)行hash()函數(shù)的到一個(gè)隨機(jī)數(shù)，之后將這個(gè)隨機(jī)數(shù)乘以中間節(jié)點(diǎn)的權(quán)重值，再右移32位。將經(jīng)過調(diào)整后的權(quán)重值與該中間節(jié)點(diǎn)左子樹的權(quán)重值進(jìn)行比較，若小于左子樹的權(quán)重值則從左子樹開始遍歷，否則從柚子樹開始遍歷；

               3）當(dāng)前節(jié)點(diǎn)到達(dá)葉子節(jié)點(diǎn)，則返回該葉子節(jié)點(diǎn)指定的item，即：bucket.h.items[n>>1]；

tree類型算法原理圖

tree類型算法流程圖

     3、tree算法適用條件。

          1）使用tree算法時(shí)定位數(shù)據(jù)的時(shí)間復(fù)雜度為O(logn)，這使其適用于管理大得多設(shè)備數(shù)量或嵌套buckets；

        2）樹狀buckets是一種適用于任何情況的buckets，兼具高性能與出色的重組效率；

五、straw類型。

     1、straw類型bucket的數(shù)據(jù)結(jié)構(gòu)。

          struct crush_bucket_straw {

               struct crush_bucket h;          //通用bucket定義

               __u32      *item_weights;       //保存bucket中所有item的權(quán)重值

               __u32      *straws;                 //保存根據(jù)item權(quán)重值計(jì)算出來的權(quán)重值

     2、straw類型bucket算法分析。

          輸入?yún)?shù)：

               1）crush_bucket_straw結(jié)構(gòu)；

               2）待執(zhí)行運(yùn)算的輸入值x；

               3）輸入值x的副本位置r；

          輸出參數(shù)：

               1）經(jīng)過straw算法計(jì)算后的bucket中的item；

          算法分析：

               1）順序遍歷backet中所有的items，對(duì)于bucket中每一個(gè)item執(zhí)行hash()算法計(jì)算出一個(gè)隨機(jī)數(shù)，之后將該隨機(jī)數(shù)與bucket.staws[i]相乘，得到一個(gè)修正后的隨機(jī)值；

               2）比較bucket中所有items經(jīng)過hash()算法算出的修正后的隨機(jī)值且找到最大的修正后的隨機(jī)值；

               3）返回最大的修正后的隨機(jī)值位置所在的item，即：bucket.h.item[high]；

straw算法原理圖

     3、straw數(shù)組的生成過程分析。

          1）根據(jù)bucket.item_weights[bucket.h.size]數(shù)組，生成一個(gè)按照items權(quán)重值從小到大排序的數(shù)組reverse[bucket.h.size]且reverse[bucket.h.size]中保存的是按序排列的item權(quán)重值的下標(biāo)；

          2）初始化計(jì)算straw算法所使用的變量。

               numleft=bucket.h.size;

               straw=1.0;

               lastw=0;

               wbelow=0;

          3）遍歷整個(gè)items，按照如下算法計(jì)算items對(duì)應(yīng)的straw值。

               A）對(duì)于bucket.item_weights[reverse[i]]==0，則straw[reverse[i]]=0；

               B）設(shè)置straw值。bucket.straw[reverse[i]]=straw*0x1000；

               C）變量i＋1；

               D）計(jì)算wbelow值。wbelow=(bucket.item_weights[reverser[i-1])-lastw)*numleft；

               E）變量numleft-1；

               F）計(jì)算wnext值。wnext=numleft*(bucket.item_weights[reverse[i]-bucket.item_weight[revese[i-1])；

               G）計(jì)算pbelow值。pbelow=wbelow/(wbelow+wnext)；

               H）計(jì)算straw值。straw=pow(1/pbelow,1/numleft)；

               I）計(jì)算lastw值。lastw=bucket.item_weights[reverse[i-1]]；

          對(duì)于bucket中所有的items來說，權(quán)重越大，計(jì)算出來的straw值就越大；

          從算法來看，計(jì)算item的straw值與item的權(quán)重值以及item之前的權(quán)重值有關(guān)，因此在修改bucket中某一個(gè)item的權(quán)重值時(shí)會(huì)影響該item及其前后items的straw值；

     4、straw算法適用條件。

          1）考慮權(quán)重對(duì)數(shù)據(jù)分布的影響，即：權(quán)重值高的item來說，被選中的概率就大，落在權(quán)重值高的item的數(shù)據(jù)越多；

          2）straw類型的buckets可以為子樹之間的數(shù)據(jù)移動(dòng)提供最優(yōu)的解決方案；

六、straw2類型。

     1、straw2類型bucket的數(shù)據(jù)結(jié)構(gòu)。

          struct crush_bucket_straw2 {

               struct crush_bucket h;           //通用bucket定義

               __u32      *item_weights;       //保存bucket中所有item的權(quán)重值

          };

     2、straw2類型bucket算法分析。

          輸入?yún)?shù)：

               1）crush_bucket_straw2結(jié)構(gòu)；

               2）待執(zhí)行運(yùn)算的輸入值x；

               3）輸入值x的副本位置r；

          輸出參數(shù)：

               1）經(jīng)過straw2算法計(jì)算后的bucket中的item；

          算法分析：

               1）遍歷整個(gè)bucket的所有items，得到items對(duì)應(yīng)的權(quán)重值；

               2）對(duì)于非零權(quán)重值來說，首先執(zhí)行hash()函數(shù)計(jì)算出一個(gè)隨機(jī)數(shù)，之后將該隨機(jī)數(shù)作為參數(shù)調(diào)用最小指數(shù)隨機(jī)變量分布算法得到的結(jié)果再減去0x1000000000000，最后將該結(jié)果除以item權(quán)重值得到item對(duì)應(yīng)的最終值(draw)。對(duì)于權(quán)重值為零來說，最終值(draw)為最小值；

               3）比較整個(gè)bucket中所有items計(jì)算出來的最終值(draw)，取最終值最大的item，即：bucket.h.items[high]；

               從算法來看，計(jì)算item的straw值只與item的權(quán)重值有關(guān)，與bucket中其它items的權(quán)重值無關(guān)。因此在修改bucket中某一個(gè)item的權(quán)重值時(shí)不會(huì)影響該bucket中其它items的straw值；

     3、straw2算法適用條件。          

          1）考慮權(quán)重對(duì)數(shù)據(jù)分布的影響，即：權(quán)重值高的item來說，被選中的概率就大，落在權(quán)重值高的item的數(shù)據(jù)越多；

          2）straw類型的buckets可以為子樹之間的數(shù)據(jù)移動(dòng)提供最優(yōu)的解決方案；

        3）適合bucket中的items權(quán)重動(dòng)態(tài)變化的場(chǎng)景；

以上是“Ceph中CRUSH算法的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！