3.3 Map的变化和数据移动
在大型文件系统中一个比较典型的部分就是数据在存储资源中的增加和移动。为了避免非对称造成的系统压力和资源的不充分利用，CRUSH主张均衡的数据分布和系统负载。当存储系统中个别设备宕机后，CRUSH会对这些宕机设备做相应标记，并且会将其从存储架构中移除，这样这些设备就不会参与后面的存储，同时也会将其上面的数据复制一份到其它机器进程存储。
当集群架构发生变化后情况就比较复杂了，例如在集群中添加节点或者删除节点。在添加的数据进行移动时，CRUSH的mapping过程所使用的按决策树中层次权重算法比理论上的优化算法∆w /w更有效。在每个层次中，当一个香港子树的权重改变分布后，一些数据对象也必须跟着从下降的权重移动到上升的权重。由于集群架构中每个节点上伪随机位置决策是相互独立的，所以数据会统一重新分布在该点下面，并且无须获取重新map后的叶子节点在权重上的改变。仅仅更高层次的位置发送变化时，相关数据才会重新分布。这样的影响在图3的二进制层次结构中展示了出来。
架构中数据移动的总量有一个最低限度∆w/w，这部分数据将会根据∆w权重重新分布在新的存储节点上。移动数据的增量会根据权重h以及平滑上升的界限h ∆w决定。当∆w非常小以至于几乎接近W时移动数据的总量会通过这个上升界限进行变化，因为在每个递归过程中数据对象移动到一个子树上会有一个最低值和最小相关权重。
代码流程图：
bucket: take操作指定的bucket；
type: select操作指定的Bucket的类型；
repnum: select操作指定的副本数目；
rep：当前选择的副本编号；
x: 当前选择的PG编号；
item: 代表当前被选中的Bucket；
c(r, x, in): 代表从Bucket in中为PG x选取第r个副本；
collide: 代表当前选中的副本位置item已经被选中，即出现了冲突；
reject: 代表当前选中的副本位置item被拒绝，例如，在item已经处于out状态的情况下；
ftotal: 在Descent域中选择的失败次数，即选择一个副本位置的总共的失败次数；
flocal: 在Local域中选择的失败次数；
local_retries: 在Local域选择冲突时的尝试次数；
local_fallback_retries: 允许在Local域的总共尝试次数为bucket.size + local_fallback_retires次，以保证遍历完Buckt的所有子节点；
tries: 在Descent的最大尝试次数，超过这个次数则放弃这个副本。
当Take操作指定的Bucket和Select操作指定的Bucket类型之间隔着几层Bucket时，算法直接深度优先地进入到目的Bucket的直接父母节点。例如，从根节点开始选择N个Host时，它会深度优先地查找到Rack类型的节点，并在这个节点下选取Host节点。为了方便表述，将Rack的所有子节点标记为Local域，将Take指定的Bucket的子节点标记为Descent域，如上图所示。
选取过程中出现冲突、过载或者故障时，算法先在Local域内重新选择，尝试有限次数后，如果仍然找不到满足条件的Bucket，那就回到Descent域重新选择。每次重新选择时，修改副本数目为r += ftotal。因此每次选择失败都会递增ftotal，所以可以尽量避免选择时再次选到冲突的节点。