1、题目
CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data, 翻译为"可控的，可扩展的，非中心化的多副本放置算法"。
2、abstract
引出问题：现在大型存储系统所面临的问题如何分布数据到这些成千上万的存储设备上，在面临设备的动态变化的同时，要能保证有效利用这些设备的能力，包括空间和性能。最后点题，crush是什么，并解决了什么问题。
3、introduction
基于对象的存储取代块存储：暴露的接口更简单。用户文件被存放在多个这样的对象中。
-
引出问题：如何分布这些数据到成千上万的设备中？
总写到新设备中：导致不均衡
-
简单的hash存放
- 迁移量大
- 不支持多副本，会导致丢数据
-
引出crush
伪随机、高效、确定的、支持异构
-
和对象之间的顺序无关，仅需存储结构信息以及副本策略
- 分散的，独立计算
- 元数据非常小
最大化利用资源，灵活应多设备添加和删除
确保副本的安全性
4、相关工作
- 很多存储系统会依赖中心化的目录去分配数据，而crush不会：独立计算
- 对比一致性hash，比较像crush，但是缺少权重以及故障域保护机制
- 对比crush和rush算法
5、 crush算法
- crush算法根据固定输入x，会得到固定的一组磁盘
- 因为是伪随机，相似的输入和输出之间没有任何关联性，选出的设备之间也是概率独立的
5.1、分层的集群结构
- 介绍地图的结构：bucket device
- 每一层的bucket的选择算法可以独立选择
5.2、副本放置
算法基本介绍，比较常规，不再详述
5.3 碰撞、失败、过载
- crush可能会拒绝并重新选择， 通过改变参数r来重新选择。拒绝的原因有三种：
- 碰撞：被选择过，crush结果要求唯一
- device挂了
- device过载了
3.4.1 Uniform Buckets
- 简单说就是普通的hash求余来选择，可参考公式：c(r, x) = (hash(x) + rp) mod m, 其中m为bucket的size，p是一个固定的随机且比m大的素数
- 缺点：当bucket size发生改变就会导致全部数据发生迁移，不符合最小迁移的原则
3.4.2 List Bucket
list bucket 是一个列表，包含任意权重的条目
-
选择副本所在的bucket item的时候，是从表头开始，也就是从最新添加的设备开始，比较hash(x,r,item)的值是否小于当前item权重和剩余较老的item之和(和包含当前item)。 代码里面hash是一个整形，需要转换为0～1的值。具体参考代码：
image.png
实际可以用公式总结: hash & 0xff * sum_weight[i] >> 16 < weight[i], 一眼看上去是看不懂，转换一下就比较符合论文的意思了:
**hash&0xff/2^16 < weight[i]/sum_weight[i] **
由公式可以推出：添加item的时候不会改变以前的权重和，只会导致部分数据迁移到老设备，这个符合添加设备的最小迁移原则
也由公式可推出：移除item的时候会影响在该item之后添加的设备的权重和，不仅要迁移移除设备的数据，还需要迁移发生权重变化的item上的数据，不符合最小迁移原则
3.4.3 Tree Buckets
- 源码实现：
- 原数组和权重数组对应关系为 y=2x+1, 实际通过位移来实现，让人摸不着头脑.
- 高度是通过识别最低为1所在的位置来判断，比如10就是高度为2, 110高度也是2， 有效数字就只是最后两个
- 判断左右节点：需要和父节点进行求&，判断是否为0
- 求父节点：右节点需要减n - (1 << h)， 左节点需要加n +(1 << h)
