CRUSH 论文伪代码整理
procedure SELECT(n,t) // Select n items of type t
{
~o←0 //输出结果o,开始为空
for i ∈~i do //遍历每个i
{
f←0 //没有错误
for r←1,n do
{ //遍历n个副本
f[r] ←0 //这个副本没有错误P
retry descent ←false
do//repeat 对于故障或过载设备
{/*
对于故障或过载设备，CRUSH通过在select(n,t)
开始时重启递归来达到项在存储集群中的均匀分布
*/
b←bucket(i) //开始选择bucket i
retry bucket ←false
do //repeat 冲突情况
{/*
对于冲突情况，替代参数r′首先在迭代的内部级别使用以进行本地查找
这样可以远离比较容易出现冲突的子树以避免全部数据的分布不均
（比如桶（数量）比n小的时候）。
*/
if “first n” //看3.2.2节
{/*复制和纠删码
在配置要求上都有些许不同
奇偶检验方案很难处理
*/
r′ ←r+ f //f表示执行当前操作select(n,t)过程中定位失败的次数
}
else
{
r′ ←r+ f[r]n
}
o ←(r′,x) //看3.4节 Bucket类型
if(type(o) != t) then //如果选的bucket不是要的t类型
{
b ← bucket(o) //继续下降寻找
retry bucket←true
}
else if (o ∈ ~o or failed(o) or overload(o,x) )
{//then
f[r] ← f[r] +1, f ← f +1
if (o ∈~o and f[r] < 3 then)
{
retry bucket←true //Retry
collisions locally (see Section 3.2.1)//冲突，失败和过载
}
else
{
retry descent ←true //Otherwise
retry descent from i
}
}
}while(retry bucket) //until retry bucket
}while(retry descent) //until retry descent
~o←[~o,o] //添加到输出结果o
}//end for
}//end for
~i←~o // Copy output back into~i
}//end procedure