select(n, t):迭代操作每个item(向量i中的item),对于每个item(向量i中的item)向下遍历(遍历这个item所包含的item),都返回n个不同的item(type为t的item),并把这些item都放到向量i中。select函数会调用c(r, x)函数,这个函数会在每个bucket中伪随机选择一个item。
emit:把向量i放到result中
存储设备有一个确定的类型。每个bucket都有type属性值,用于区分不同的bucket类型(比如”row”、”rack”、”host”等,type可以自定义)。rules可以包含多个take和emit语句块,这样就允许从不同的存储池中选择副本的storage target。
如表1中示例所示,该法则是从图1架构中的root节点开始,第一个select(1.row)操作选择了一个row类型的单例bucket。随后的select(3,cabinet)操作选择了3个嵌套在下面row2(cab21, cab23, cab24)行中不重复的值,同时,最后的select(1,disk)操作迭代了输入向量中的三个buckets,也选择了嵌套在它们其中的人一个单例磁盘。最后的结果集是三个磁盘空间分配给了三个块,但是所有的结果集都在同一行中。因此,这种方法允许复制品在容器中被同时分割和合并,这些容器包括rows、cabinets、shelves。这种方法对于可靠性和优异的性能要求是非常有利的。这些法则包含了多次take和emit模块,它们允许从不同的存储池中获取不同的存储对象,正如在远程复制脚本或者层叠式设备那样。
3.2.1 冲突,失败和过载
select(n,t) 操作可能会在多种层次的存储体系中查找以定位位于其起始点下的n个不同的t类型项,这是一个由选择的复制数 r =1,..., n部分决定的迭代过程。在此过程中,CRUSH可能会由于以下三个不同原因而丢弃(定位)项并使用修改后的输入参数 r′来重新选择(定位)项:如果某一项已经位于当前集合中(冲突——select(n,t) 的结果必须互不相同),如果设备出现故障,或者过载。虽然故障或过载设备在集群map中尽可能地被标记出来,但他们还是被保留在体系中以避免不必要的数据迁移。CRUSH利用集群map中的可能性,特别是与过度利用相关的可能性,通过伪随机拒绝有选择的转移过载设备中的一小部分数据。对于故障或过载设备,CRUSH通过在select(n,t) 开始时重启递归来达到项在存储集群中的均匀分布(见算法1第11行)。对于冲突情况,替代参数r′首先在迭代的内部级别使用以进行本地查找(见算法1的第14行),这样可以远离比较容易出现冲突的子树以避免全部数据的分布不均(比如桶(数量)比n小的时候)。
冲突:这个item已经在向量i中,已被选择。
故障:设备发生故障,不能被选择。
超载:设备使用容量超过警戒线,没有剩余空间保存数据对象。
3.2.2 复制排名
奇偶检验和纠删码方案相比复制在配置要求上都有些许不同。在原本复制方案中,出现故障后,原先副本(已经拥有该数据的副本)成为新的原本常常是需要的。在这种情况下,CRUSH可以使用r′ = r + f 重新进行选择并使用前n个合适项,其中 f表示执行当前操作select(n,t)过程中定位失败的次数(见算法1第16行)。然而,在奇偶检验和纠删码方案中,CRUSH输出中的存储设备排名或位置是特定的,因为每个目标保存了数据对象中的不同数据。特别是,如果存储设备出现故障,它应在CRUSH输出列表⃗R 的特定位置被替换掉,以保证列表中的其他设备排名保持不变(即查看图2中 ⃗R的位置)。在这种情况下,CRUSH使用r′=r+frn进行重新选择,其中fr是r中的失败尝试次数,这样就可以为每一个复制排名确定一系列在统计上与其他故障独立的候选项。相反的是,RUSH同其他存在的哈希分布函数一样,对于故障设备没有特殊的处理机制,它想当然地假设在使用前n个选项时已经跳过了故障设备,这使得它对于奇偶检验方案很难处理。