关于Ceph的CRUSH算法

考虑crush map的bucket选择.

对于一个obejct o,choose的时候需要经过一个hash过程得到一个pseudo random的id x.
也就是对于任何一种bucket 类型,有
x = bucket_hash(o).

假定bucket的长度为n,x的放置位置为y的话.
bucket specific的choose policy为p.
有y=p(x)

对于uniform bucket来说,这个p为
y=p_uniform(x) = x % n

除了uniform的bucket之外,其他bucket type都是有weight权重的.
同样,记录位置w_i为位置i的用权重值,且有0<=i1的prod替换的sum.

也就是,这里的straw其实是一个权重放大倍数比list高得多的一个进阶版本.
而且跟list不同的是,它的argmax没有< w_j的条件限定.
因此它的寻址复杂度是O(n)的.
而list因为条件限定的情况,实际平均表现最差也只是跟straw一致.

在考虑现在ceph的默认policy,steaw2.
这里对hash做个额外的限定,0
这个主要是ceph的实现里有个lookup table的优化.
给定0
所以实际上starw2的hash是一个到[0,1]区间的一个mapping.
对应的log(k)取值区间大概是[-11,0].

所以这里简单重定义-11<=hash(x)<=0
则
y=p_straw2(x) = argmax(\{j; hash(x)/w_j \})

这里可以看出,只要bucket item的权重不变.节点增减的变化只由argmax的骨架部分决定.
这个跟list也有点类似,但是它是位置无关的.
不像list有对于左右有相对确定的基础cost估计.

但也因为位置无关,所以它存在一些极端情况.

对于节点减少的话,则所有argmax为这个节点的数据都会受影响.
这个是符合intuition的.

对于增加节点,argmax的max value可能都指向变动的那个节点.
这样的极端情况就是造成整体数据的挪动.

但是由于w_j的存在,这个也是可干涉/存在可控性的.

而对于节点数量不变,只是权重改变的情况.
跟节点增加类似.

所以,straw2的基本上算是忠实指向w_j的.

然后考虑hash.

由于hash会对x走一个log的重新分布.
所以实际上考虑的数据分布性质的话,只需要考虑log分布之后的就行了.

也就是在大概[-11,0]的区间内的数据分布问题.

把w_j作为一个tuning parameter/placement parameter考虑的话.
那么理论上,针对现有的实际数据分布是可以做到人工精确干涉的.

而且这么考虑的话,其实starw2的计算也并不需要搞那么复杂.

因为归根到底还是通过w_j来控制的.