[ceph学习-8]crush算法(3)

冲突、故障、和超载
select(n,t)操作可能为了定位n个不相同的t类型的item,而从起点开始向下遍历而经过许多层,递归过程的次数有r=1,..n确定,n是选择副本的个数。在处理过程中,CRUSH可能会有下面三个不同的原因而用于修改过的输入r’来拒绝并重选项,某个item已经在当前的集合中(发生冲突,select(n,t)的结果必须是各不相同的);有一个设备失效了,有一个设备超载。失效或超载的设备都会在Cluster Map中进行相应的标记,但为了避免不必要的数据迁移,不同从层次结构中移除它们。CRUSH通过根据Cluster Map中指定的概率伪随机的拒绝超载的设备,来选择性的转移此超载device上的少部分数据。这个概率则是与报告的超载情况有关的。对于失效或超载的设备、CRUSH通过重新启动select(n,t)开始部分递归过程,均匀的在存储集群中重新分布这些item。而对应冲突的青睐,则在递归内层使用r’替换r来进行局部搜索。不至于在那些很可能发生冲突的子树中(bucket容量小于n)改变总体数据分布。

冲突:这个item已经在向量i中,已被选择,使用r'(r’和r、出错次数,firstn参数)做为新的参数选择item(局部选择)
故障:设备故障,不能被选择。
超载:设备使用容量超过警戒线、没有剩余空间保存数据。
其中故障和超载设备会在clustermap上标记,为了不必要的数据迁移,不会从层次结构中移除它们。

副本排序
在主拷贝副本模式中,发生故障时,让之前的副本目标成为新的主拷贝,在这种情况下,CRUSH可以通过r’=r+f进行重选,来使用”前n个“合适的目标,f是当前select(n,t)操作中确定放置位置失败的次数。而对于奇偶校验码或擦除码模式,CRUSH算法输出的存储设备的顺序至关重要,因为每个目标都存放了数据对象的不同比特位,特别的,当某个存储设备发生故障时,它需要在CRUSH的输出列表R(向量R)的对应位置上被替换,其他列表中的设备要维持位置不变(位置是指向量R对应的位置)这种情况下,CRUSH通过r’=r+fn进行重选,其中f是第r次迭代时失败的次数。这样就是为每一个向量位置上的item定义了一系列的候选item。每个候选item与其他位置上的候选item是无关的。相比,RUSH对应发生故障的设备没有特殊处理,就像其他现有的散列分布式函数,它隐式的假设使用”前n个”的策略在结果中跳过失效的设备。

发表评论

您的电子邮箱地址不会被公开。