2.2.3 Bucket 随机选择算法
Ceph 的设计目标是采用通用的硬件来构建大规模、高可用性、高扩展性、高性能的分布式存储系统。Ceph 的设计目标是可以管理大型分级存储网络的分布式存储系统，在网络中不同层级具有不同的故障容忍程度，这种容忍度称为故障域。
在通常情况下一台存储服务器会包含多个磁盘，每个机架则会有多台服务器，为了实现在这些服务器上构建的存储集群具有较高的可靠性，数据通常采用多副本策略，其副本存放分布在不同机架的服务器磁盘上。Sage 在 Ceph 存储系统中设计了 CRUSH 算法，它是一种基于深度优先的遍历算法，在 CRUSH 最初的实现中，Sage 一共设计了 4 种不同的基本选择算法，这些算法也是后期算法的基础。
1. 几种类型的 bucket 介绍
CRUSH 中定义了 4 种类型的 bucket 来代表集群架构中的叶子节点：一般类型 bucket（uniform bucket）、列表类型 bucket（list bucket）、树结构类型 bucket（tree bucket）以及稻草类型 bucket（straw bucket），这 4 种类型的 bucket 对应了 4 种 CRUSH 算法。
◆ Uniform bucket
Uniform 类型的 bucket 在选择子节点时不考虑权重，全部随机选择，因此，它要求桶内所有元素的权值相等。它的查找速度最快，但桶内元素改变时，设备中的数据会被完全重组，uniform bucket 适用于 bucket 中很少添加或删除元素，即存储系统 Cluster Map相对稳定的场景。
◆ List bucket
List 类型的 bucket 采用链表数据结构，链表中的元素可拥有任意的权重配置，在查找节点元素时，只能顺序进行，性能较差，时间复杂度为 O(n)，这一特性限制了存储集群的部署规模。但桶内新增元素时，list bucket 可以产生最优的数据移动，而桶内删除数据时，list bucket 会增加额外的数据移动，即该类型 bucket 更适用于小规模存储集群，且集群规模偶有扩展的场景。
◆ Tree bucket
Tree 类型的 bucket 采用加权二叉排序树数据结构，相较于链表数据结构，其节点元素查找效率更高，时间复杂度为 O(logn)，适用于规模更大的存储集群管理。但当集群的Cluster Map 发生变化时，树状结构需要旋转调整以作适配，这决定了该类型 bucket 更适合于规模较大、查找频繁，但集群结构相对稳定的场景。
◆ Straw bucket
Straw 类型的 bucket 通过类似抽签的方式公平“竞争”来选取节点元素。定位副本时，bucket 中的每一项元素都对应一个随机长度的 straw 数值，拥有最长长度（最大 straw 数值）的元素被选中。Straw 类型 bucket 的定位过程比 list bucket 及 tree bucket 都要慢，但当集群结构出现变动（添加或删除元素）时，存储集群的数据移动量最优，即该类型 bucket更适用于集群规模常有变化的场景。
简要总结，当 bucket 固定且集群设备规格统一时（比如 Ceph 存储系统搭建在完全相同磁盘配置的服务器集群上），uniform bucket 查找速度最快；如果一个 bucket 预计将会不断增长，则 list bucket 在其列表开头插入新项时将提供最优的数据移动；而当删除bucket 或 device 时，list bucket 带来额外的数据移动，straw bucket 则可以为子树之间的数据移动提供最优的解决方案。tree bucket 是一种适用于任何情况的 bucket，兼具性能与数据迁移效率，但其综合表现略低于 straw bucket。
Bucket 类型的选择需要基于预期的集群结构变化，权衡映射方法的元素查找运算量和存储集群数据移动之间的效率，基于此观点，对比以上 4 种类型 bucket（如表 2-1 所示），straw 类型的 bucket 综合表现最优。
考虑到呈爆炸式增长的数据存储空间需求（CRUSH 添加元素），在大型分布式存储系统中某些部件故障是常态（CRUSH 删除元素），以及愈发严苛的数据可靠性需求（需要将数据副本存储在更高级别的故障域中，如不同的数据中心），因此，CRUSH 默认采用了性能较为均衡的 straw 算法，straw bucket 也是 Ceph 中默认的 bucket 类型。
2. Straw 算法介绍
上文介绍到 straw 类型的 bucket 通过类似抽签的方式公平“竞争”来选取节点元素，这种抽签算法即为 straw 算法，它的关键在于如何计算签长。
核心计算过程如下。
static int bucket_straw_choose(struct crush_bucket_straw *bucket， int x， int r) { __u32 i; int high = 0; __u64 high_draw = 0; __u64 draw; for (i = 0; i < bucket->h.size; i++) { draw = crush_hash32_3(bucket->h.hash， x， bucket->h.items[i]， r); draw &= 0xffff; draw *= bucket->straws[i]; if (i == 0 || draw > high_draw) { high = i; high_draw = draw; } } return bucket->h.items[high]; }
算法核心流程如下。
（1）给出一个 PG_ID，作为 CRUSH_HASH 方法的输入；
（2）CRUSH_HASH（PG_ID，OSD_ID，r）方法调用之后，得出一个随机数；
（3）对于所有的 OSD，用它们的权重乘以每个 OSD_ID 对应的随机数，得到乘积；
（4）选出乘积最大的 OSD ；
（5）这个 PG 就会保存到这个 OSD 上。
如果两次选出的 OSD 一样，Ceph 会递增 r 再选一次，直到选出 3 个编号不一样的OSD 为止。
通过概率分布可知，只要样本容量足够大，那么最后选出的元素概率就会是相同的，从而使数据可以得到均匀分布。但是在实际使用过程中，很多因素都会使得集群不够均衡，如磁盘容量不尽相同等，这就需要额外添加其他因子来控制差异。straw 算法就是通过使用权重对签长的计算过程进行调整来实现的，即让权重大的元素有较大的概率获取更大的签长，从而更容易被抽中。
Straw 算法选出一个元素的计算过程，其时间复杂度是 O(n)。
3. Straw2 算法介绍
理论上，在样本足够多的情况下，OSD 被选中的概率只与权重相关，下面以添加元素为例。
（1）假定当前集合中一共有n 个元素：（e1，e2，…，en）。
（2）向集合中添加一个新元素 en+1 ：（e1，e2，…，en，en+1）。
（3）针对任意的输入 x，在加入 en+1 之前，分别计算每一个元素的签长并假定其中最大值为 dmax ：（d1，d2，…，dn）。
（4）因为新元素 en+1 的签长计算只与自身编号和自身权重相关，所以可以使用 x 独立计算其签长（同时其他元素无须重新计算），假定签长为 dn+1。
（5）因为 straw 算法需要选出最大签长作为输出，所以：若 dn+1>dmax，那么 x 将被重新映射至 en+1 上，反之，对 x 的已有映射不会产生影响。
由上可见，添加一个元素，straw 算法会随机地将一些原有元素中的数据重新映射至新加的元素之中。同理，删除一个元素，straw 算法会将该元素中的数据全部重新随机映射至其他元素之中。因此无论添加或者删除元素，都不会导致数据在除被添加或者删除之外的两个元素（即不相干的元素）之间进行迁移。这也是 straw 算法的设计初衷，即一个元素的 weight 调高或者调低，效果作用于该调整了 weight 的元素以及另外一个特定的相关元素，数据会从另一个元素向它迁入或者从它向另一个元素迁出，而不会影响到集群内其他不相关的元素。
理论上，straw 算法是完美的，但随着 Ceph 存储系统应用日益广泛，不断有用户向Ceph 社区反馈，每次集群有新的 OSD 加入、旧的 OSD 删除，或用户仅在一个元素上做很小的权重调节后，就会触发存储集群上很大的数据迁移。这迫使 Sage 对 straw 算法重新进行审视。
经代码分析，straw 算法的 weight 计算会关联一个所有元素共用的 scaling factor（比例因子），即 Ceph 集群中某个元素的权重值调整，都会影响到集群内其他元素的权重值变化。
原 straw 算法实现如下。
max_x = -1 max_item = -1 for each item: x = hash(input，r) x = x * item_straw if x > max_x max_x = x max_item = item return max_item
由上述算法可知，max_item 的输出主要由数据输入（input）、随机值（r）和 item_straw 计算得出，而 item_straw 通过权重计算得到，伪代码实现如下。
reverse = rearrange all weights in reverse order straw = -1 weight_diff_prev_total = 0 for each item: item_straw = straw * 0x10000 weight_diff_prev = (reverse[current_item] - reverse[prev_item]) * item_remain weight_diff_prev_total += weight_diff_prev weight_diff_next = (reverse[next_item] - reverse[current_item]) * item_remain scale = weigth_diff_prev_total / (weight_diff_next + weight_diff_prev) straw *= pow(1/scale， 1/item_remain)
原 straw 算法中，将所有元素按其权重进行逆序排列后逐个计算每个元素的 item_straw，计算过程中不断累积当前元素与前后元素的权重差值，以此作为计算下一个元素item_straw 的基准。因此 straw 算法的最终结果不但取决于每一个元素自身权重，而且也与集合中所有其他元素的权重强相关，从而导致每次加入新的元素或者从集群中剔除元素时都会引起不相干的数据迁移。
Sage 及社区对该问题进行了修复，出于兼容性的考虑，Sage 重新设计了一种对原有straw 算法进行修正的新算法，称为 straw2。straw2 在计算每个元素的签长时仅使用自身权重，因此代码可以完美反应 Sage 的初衷（也因此可以避免不相干的数据迁移），同时计算也变得更加简单，其伪代码如下。
max_x = -1 max_item = -1 for each item: x = hash(input，r) x = ln(x/65536) / weight if x > max_x max_x = x max_item = item return max_item
分析 straw2 算法可知，straw2 算法将 scaling factor 修改为 ln(x / 65536) / weight的方式作为代替，针对输入和随机因子执行后，结果落在 [0 ～ 65535]，因此 x/65536 必然是小于 1 的值，对其取自然对数［ln(x/655536)］后的结果为负数 1，进一步，将其除以自身权重（weight）后，权重越大，其结果越大，从而体现了我们所期望的每个元素权重对于抽签结果的正反馈作用。这个变化使得一个元素权重值的修改不会影响到其他的元素权重，集群内某个元素的权重调整引发的集群数据迁移范围也得到了很好的控制。
1 CRUSH 算法整体是整型运算，新引入的 ln() 函数是一个浮点运算，为了算法整体效率，当前的实施方法是引入了一个 128KB 的查找表来加速 ln() 函数的运算速度。
简要总结，straw 算法里面添加节点或者减少节点，其他服务器上的 OSD 之间会有PG 的流动（即数据的迁移）；Straw2 算法里面添加节点或者减少节点，只会有 PG 从变化的节点移出或者从其他点移入，其他不相干节点不会触发数据的迁移。Ceph 的 Luminous版本开始默认支持 straw2 算法。
