Ceph中CRUSH算法的示例分析

这篇文章主要介绍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算法的示例分析”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注亿速云行业资讯频道！