考虑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<=i<n .
对于list bucket.
y=p_list(x) = argmax({j; (hash(x,w_j)) * \sum_{0}^{j}w_j) < w_j })
即x用位置j的权重共同计算一个hash,然后用从[0,j]的权重累加值作为一个scale factor,从右往左寻找一个最先满足<w_j条件的.
对于tree bucket.
y=p_tree(x) = binary_search(hash(x,i,n)*w_i)
即常规的用节点的位置信息以及当前树的节点数信息做hash之后,用该节点的权重scale后的值作为search branch condition.
对于tree和uniform模式来说,有个比较明显的问题就是寻址的过程有节点数n参与.
也即是说,数据的分布策略是跟放置时候的节点数状态绑定的.
当crush map的bucket数量变化的时候,就必然会引发整体的数据迁移/挪动.
而list bucket的寻址主体框架是跟左侧节点有关.
只要左侧节点的数量和权重不变,框架内的选取集合就不会变.
会受影响的只是argmax部分.
而argmax会变化的则之后是命中集合s中maximum值变化的部分.
虽然这个很难说就一定比uniform/list的挪动少就是了.
但是对于在右侧新增节点的情况来说,会被挪动的部分一定是都落到这个新增节点上的.
因为有变更的s的max value只可能是这个最右值.
而且通过调小权重还可以进一步push back一些挪动.
或者通过暂时调小临时delay一些挪动.
实际上,对于list bucket的挪动估计,假设bucket item的预计变动位置为j.
那么基础的比变动影响就是[j,n-1]范围的节点的所有数据,加上[0,j)节点的argmax受影响了的部分.
也就是说对于位置j的变动是包括部分数据的push/shift left,加上右侧数据的reshuffle.
所以,对于list bucket来说,较优的操作是在右侧节点动手脚.
然后是剩下的straw和straw2的bucket type.
对于straw,增加表征w的array是ascending sorted的.
即对于有0<=i<j<n,有w_i<w_j.
则
y=p_straw(x) = argmax({j; hash(x,w_j) * \prod_{0}^{j} straw_j })
这里先不考虑straw_j的定义.
可以看到其实跟list是大同小异的.
所以抛开starw_j的话,list有的问题和适用的地方,straw也大概类似.
然后考虑straw_j的定义.
首先有predicated(w_j) = (w_j-w_{j-1}) * (n-j)
即对于位置j之后的权重预估影响因子,由当前位置的权重和前一位置的权重差值作为基准,用甚于的n-j做scale加成.
类似地有
predicated(w_j-1) = (w_{j+1}-w_j(j)) * (n-j).
用同样的算法预估的下一位置的影响因子.
然后一个动力学因子.
velocity(j) = predicated(w_j) / ( predicated(w_j) + predicated(w_{j+1})).
则
straw(j) = velocity(j) ^ -(1/(n-j))
由于0<velocity(j)<1, -(1/(n-j)<-1.
也就是这是一个基数<1的指数曲线的(-infinite,-1)部分.
对于统一velocity值的话,j越往bucket右侧,则实际的权重scale影响就增加越少.
而velocity本身的话,如果大于0.5,则说明w的往右侧的梯度变小,变平缓.
所以这个starw的intuition是,如果权重设定的波动变化趋于平缓的话,straw的值就会愈趋近于1.
如果把starw的prod替换成sum的话,也就是愈趋近于list的w是均等的情况.
反之的话,就是继续放大w的波动率.
尤其考虑到这里实际是用value>1的prod替换的sum.
也就是,这里的straw其实是一个权重放大倍数比list高得多的一个进阶版本.
而且跟list不同的是,它的argmax没有< w_j的条件限定.
因此它的寻址复杂度是O(n)的.
而list因为条件限定的情况,实际平均表现最差也只是跟straw一致.
在考虑现在ceph的默认policy,steaw2.
这里对hash做个额外的限定,0<hash(x)<=65535.
这个主要是ceph的实现里有个lookup table的优化.
给定0<k<=1,log(k)的取值做个个65536大小的lookup table.
所以实际上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来控制的.
网友评论