2.2.3 Bucket随机选择算法
Ceph 的设计目标是采用通用的硬件来构建大规模、高可用性、高扩展性、高性能的分布式存储系统。Ceph 的设计目标是可以管理大型分级存储网络的分布式存储系统，在网络中不同层级具有不同的故障容忍程度，这种容忍度称为故障域。
在通常情况下一台存储服务器会包含多个磁盘，每个机架则会有多台服务器，为了实现在这些服务器上构建的存储集群具有较高的可靠性，数据通常采用多副本策略，其副本存放分布在不同机架的服务器磁盘上。Sage在 Ceph存储系统中设计了CRUSH算法，它是一种基于深度优先的遍历算法，在CRUSH最初的实现中，Sage一共设计了4种不同的基本选择算法，这些算法也是后期算法的基础。
1. 几种类型的 bucket介绍
CRUSH中定义了 4种类型的bucket来代表集群架构中的叶子节点：一般类型 bucket
（uniformbucket）、列表类型bucket（listbucket）、树结构类型bucket（treebucket）以及稻草类型bucket（strawbucket），这4种类型的bucket对应了4种CRUSH算法。
◆ Uniformbucket
Uniform类型的 bucket在选择子节点时不考虑权重，全部随机选择，因此，它要求桶内所有元素的权值相等。它的查找速度最快，但桶内元素改变时，设备中的数据会被完全重组，uniformbucket适用于 bucket 中很少添加或删除元素，即存储系统 ClusterMap相对稳定的场景。
◆ Listbucket
List类型的 bucket 采用链表数据结构，链表中的元素可拥有任意的权重配置，在查找节点元素时，只能顺序进行，性能较差，时间复杂度为 O(n)，这一特性限制了存储集群的 部署规模。但桶内新增元素时，listbucket 可以产生最优的数据移动，而桶内删除数据时，listbucket会增加额外的数据移动，即该类型bucket 更适用于小规模存储集群，且集群规模偶有扩展的场景。
◆ Treebucket
Tree类型的 bucket 采用加权二叉排序树数据结构，相较于链表数据结构，其节点元素查找效率更高，时间复杂度为 O(logn)，适用于规模更大的存储集群管理。但当集群的ClusterMap发生变化时，树状结构需要旋转调整以作适配，这决定了该类型bucket更适合于规模较大、查找频繁，但集群结构相对稳定的场景。
◆ Strawbucket
Straw类型的 bucket 通过类似抽签的方式公平“竞争”来选取节点元素。定位副本时，bucket中的每一项元素都对应一个随机长度的straw数值，拥有最长长度（最大straw数值）的元素被选中。Straw类型bucket的定位过程比 listbucket及 treebucket都要慢，但当集群结构出现变动（添加或删除元素）时，存储集群的数据移动量最优，即该类型bucket
更适用于集群规模常有变化的场景。
简要总结，当 bucket固定且集群设备规格统一时（比如 Ceph存储系统搭建在完全相同磁盘配置的服务器集群上），uniformbucket查找速度最快；如果一个bucket预计将会不断增长，则 listbucket在其列表开头插入新项时将提供最优的数据移动；而当删除bucket或 device 时，listbucket 带来额外的数据移动，strawbucket 则可以为子树之间的数据移动提供最优的解决方案。treebucket是一种适用于任何情况的 bucket，兼具性能与数据迁移效率，但其综合表现略低于 strawbucket。
Bucket 类型的选择需要基于预期的集群结构变化，权衡映射方法的元素查找运算量和存储集群数据移动之间的效率，基于此观点，对比以上4种类型bucket（如表2-1所示），straw类型的 bucket综合表现最优。
表2-1 4种类型的bucket对比
类型 |
时间复杂度 |
添加元素难度 |
删除元素难度 |
uniform |
O(1 ) |
poor |
poor |
list |
O(n ) |
optimal |
poor |
tree |
O(logn ) |
good |
good |
straw |
O(n ) |
better |
better |
考虑到呈爆炸式增长的数据存储空间需求（CRUSH添加元素），在大型分布式存储系统中某些部件故障是常态（CRUSH删除元素），以及愈发严苛的数据可靠性需求（需要将数据副本存储在更高级别的故障域中，如不同的数据中心），因此，CRUSH默认采用了性能较为均衡的straw 算法，strawbucket 也是Ceph 中默认的bucket 类型。
2. Straw算法介绍
上文介绍到 straw类型的 bucket 通过类似抽签的方式公平“竞争”来选取节点元素，这种抽签算法即为 straw算法，它的关键在于如何计算签长。
核心计算过程如下。
staticintbucket_straw_choose(structcrush_bucket_straw*bucket，intx，intr)
{
u32 i;
int high = 0;
u64 high_draw = 0;
u64draw;
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;
}
}
returnbucket->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计算会关联一个所有元素共用的 scalingfactor（比例因子），即 Ceph集群中某个元素的权重值调整，都会影响到集群内其他元素的权重值变化。
原 straw算法实现如下。
max_x = -1
max_item =-1
foreach item:
x = hash(input，r)
x = x* item_strawif x > max_x
max_x = xmax_item= item
returnmax_item
由上述算法可知，max_item的输出主要由数据输入（input）、随机值（r）和item_ straw计算得出，而 item_straw通过权重计算得到，伪代码实现如下。
reverse= rearrange all weights in reverse order
straw = -1
weight_diff_prev_total= 0
foreach item:
item_straw= straw* 0x10000
weight_diff_prev=(reverse[current_item]-reverse[prev_item])* item_remainweight_diff_prev_total+= weight_diff_prev
weight_diff_next=(reverse[next_item]-reverse[current_item])* item_remainscale= 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
foreach item:
x = hash(input，r)
x = ln(x/65536) / weight
if x >max_xmax_x=x
max_item = itemreturnmax_item
分析 straw2算法可知，straw2算法将 scalingfactor修改为 ln(x/65536) /weight的方式作为代替，针对输入和随机因子执行后，结果落在 [0～65535]，因此 x/65536必然是小于 1 的值，对其取自然对数［ln(x/655536)］后的结果为负数 1，进一步，将其除以
自身权重（weight）后，权重越大，其结果越大，从而体现了我们所期望的每个元素权重对于抽签结果的正反馈作用。这个变化使得一个元素权重值的修改不会影响到其他的元素权重，集群内某个元素的权重调整引发的集群数据迁移范围也得到了很好的控制。
简要总结，straw算法里面添加节点或者减少节点，其他服务器上的OSD之间会有PG的流动（即数据的迁移）；Straw2算法里面添加节点或者减少节点，只会有 PG从变化的节点移出或者从其他点移入，其他不相干节点不会触发数据的迁移。Ceph的 Luminous版本开始默认支持 straw2算法。
1 CRUSH算法整体是整型运算，新引入的ln()函数是一个浮点运算，为了算法整体效率，当前的实施方法是引入了一个 128KB的查找表来加速ln()函数的运算速度。
