bucket类型
CRUSH算法的设计是为了权衡两个互斥的目标，映射算法的效率和可靠性，增删设备导致的集群变更时恢复平衡的数据迁移成本最小化。CRUSH定义了四种具有不同算法的buckets来diabetes集群层次结构中的中间节点，而非叶子节点。uniform、List、Tree、Straw。每种桶都基于一种不同的内部数据结构，并且分别使用了不同在定位过程中选择嵌套item的伪随机函数c(r,x).体现了效率和数据重组效率之间的不同权衡方法。
uniform buckets。要求所有桶内的item权值相等，而且bucket很少添加删除item。它的查找速度最快。大小如果改变，设备中的数据会被完全重组。
List buckets：他的结构是链表结构，所包含的item可以具有任意权值。CRUSH从表头开始查找副本的位置，它先得到表头的Item的权重Wh，剩余链表中所有的item的权重之和Ws，然后根据hash(x,r,item)得到一个[0-1]的值v，假如这个v在[0~Wh/Ws)之中，则副本在表头item中，并发挥表头item的标识符(id).否则机选遍历剩余的链表。这种方式来源于RUSHp
Tree buckets:链表查找的复杂度O(n)，决策树的查找复杂度为O(logn).item是决策树的叶子节点，决策树中的其他节点知道它左右子树的权重，节点的权重等于左右子树的权重之和。CRUSH从root节点开始查找副本的位置，它先得到节点的左子树的权重Wl，得到节点的权重Wn，然后根据hash（x，r,node_id)得到一个[0-1]的值y，假如这个值v在[0~Wl/Wn)中，则副本在左子树，或者在右子树中。继续遍历节点，直到到达叶子节点。treebucket的关键是当添加删除叶子节点时，决策树中的其他节点的node_id不变。决策树中节点的node_id的标识是根据对二叉树的中序遍历来觉决定的(node_id不等于item的id，也不等于权重)
straw buckets：这种类型的bucket所包含的所有item公平竞争，（不像list和tree一样需要遍历）。这种算法就像抽签一样，所有的item都有机会被抽中（只有最长的签才能被抽中）。每个签的长度是有length= f(Wi)*hash(x,r,i）来决定的。f(Wi)和item的权重有关，i是item的id号。
c(r,x)= max<i>(f(W<i>)hash(x,r,i))。
struct crush_bucket {
__s32 id; // this'll be negative
__u16 type; //non-zero; type=0 is reserved for devices
__u8 alg; // one of CRUSH_BUCKET_*
__u8 hash; // which hash function to use, CRUSH_HASH_*
__u32 weight; // 16-bit fixed point
__u32 size; // num items 假如size为0，不包含item
__s32 *items; // 数组，它包含item的id。这些id可能是负数，也可能都是自然数。如果是负数，表示它包含的都是bucket，如果是自然数，表示item都是device（叶节点）
//
// cached random permutation: used for uniform bucket and for
// the linear search fallback for the other bucket types.
//
__u32 perm_x; /* @x for which *perm is defined //
__u32 perm_n; /* num elements of *perm that are permuted/defined //
__u32 *perm;
};
crush.c文件中
/*用于获取指定的bucket中的item的weight*/
int crush_get_bucket_item_weight(const struct crush_bucket *b, int p)
/*用于销毁bucket数据结构*/
void crush_destroy_bucket(struct crush_bucket *b)
/**/用于销毁cursh_map
void crush_destroy(struct crush_map *map)
