共计 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 行业资讯频道！
