• bucket-type: 类型 （磁盘、主机、机柜...）， 用来指定 该Bucket 在CRUSH分层结构中的位置 ；
• alg : Ceph提供多个bucket类型的算法选择用来寻址其下面的叶子节点；
• weight: bucket 下面所有节点的权重累积信息， 所有的磁盘无论其容量大小都要被加入到集群中被同等地利用。CRUSH给每个OSD分配一个权重。OSD的权重越高，说明它的物理存储容量越大。权重表示设备容量之间的相对差异 ；
• item: bucket 下面所有 干节点bucket 以及 叶子 节点的列表信息，包含权重 。

接下来再看CRUSH Map当中的“rules”，CRUSH map 包含了若干 CRUSH rules 来决定存储池内的数据存放方式。它们定义了存储池的属性，以及存储池中数据的存放方式。它们指定了复制（replication）和放置（placement）策略。

• step take: 获取一个 bucket 名称，开始遍历其树。
• step choose：选择某类型的若干（N）bucket，这里数字 N 通常是存储池的副本份数。
• step chooseleaf：首先选择指定 bucket 类型的一组 bucket，然后从每个bucket 的子树中选择叶子节点。该组中 bucket 的数目 N 通常是该存储池的副本份数。

3.2 CRUSH寻址算法

从上一节的介绍当中，我们基本了解了CRUSH Map的数据结构以及不同参数的重要意义。本节我们基于以上基础，来分析从PG到OSD的具体过程。这个过程就是要在CRUSH树形结构中解决“从哪里出发？途经哪几条路？到达哪些终点目标？”这几个问题；那么为了解决这几个问题需要如下输入“PG Map、CRUSH Map、Rule”。如图3.2所示：

图3.2 CRUSH 寻址流程示意图

如图，PG_OSD逻辑过程当中的PG要解决三个问题：

（1）Where：从哪里开始寻找OSD，原点在哪里？我们在上一节内容当中的CRUSH Map的定义当中看到了。其中“rules”的实例会明确定义PG寻找OSD的原点应该是哪一个Bucket实例。这个我们在做Ceph集群规划配置的时候可以输入我们相应的规则，默认为根节点。

（2）How：如何寻找OSD的路由，原点下面有很多分支，路由如何选择？同样在CRUSH Map当中的“rules”的实例当中会定义。具体为“step choose firstn {num} type {busket-type}”，只不过这里需要一些输入。

根据我们的规则确定副本数和故障隔离区类型获得了num&busket-type，可以启动计算了。在计算的过程当中还要调用CRUSH算法，而CRUSH算法就需要PG_ID、Buckets Tree等这些数据结构实例以及相应参数num的输入，才可以最终得到相应数目的Buckets。

（3）Which：如何寻找到具体的OSD？既然Bucket都定了，那么我们只需要在How的循环过程中寻找每个Bucket下面的Leaf节点。如何能定位到这个叶子节点，这就需要遍历Bucket数据结构里面定义的Item数据结构了。按照前文的解释，Item本身是一个包含了Bucket下面所有OSD及其权重Weight的集合，目标是权重最大，但是如何遍历就取决于Items的几种数据结构组织模式，也就是Bucket实例参数当中的 alg （Uniform、List、Tree、Straw），不同的数据结构在寻址复杂性以及集群变化后的受影响程度上都会有较大的差异。后面的章节我们继续这个问题。

3.3 Bucket alg

前面的章节介绍，我们基本解决了从PG到OSD这个路径当中的大部分问题，只剩下唯一的问题就是用什么样的算法去遍历Bucket下面的所有Leaf节点，以确定最终的OSD。这里就需要搞清楚Bucket下面所有节点的数据组合类型（Bucket alg）以及它相应的算法特性。Bucket alg定义的是Bucket的组织模式，主要有四种类型：Uniform、List、Tree、Straw。

（1） Uniform: 当所有存储设备的权重都统一时可以使用这种类型的bucket ， 当权重不统一时不能使用。在这种类型的bucket中添加或者删除设备将会 导致大量 数据重新放置 ， 效率 较差 。适用于所有子节点权重相同的情况，而且bucket很少添加删除 节点 ，这种情况查找速度应该是最快的 。

（2） List: 这种桶把它们的内容汇聚为链表。它基于 RUSH P 算法，一个列表就是一个自然、直观的扩张集群：对象会按一定概率被重定位到最新的设备、或者像从前一样仍保留在较老的设备上。结果是优化了新条目加入桶时的数据迁移。然而，如果从链表的中间或末尾删除了一些条目，将会导致大量没必要的挪动。所以这种桶适合永不或极少缩减的场景。

（3） Tree: 它用一种二进制搜索树， 规模效率远高于列表 。列表buckets对于少量的数据项还是高效的， 当链表达到较大规模时， 其时间复杂度就太大了。树状buckets由RUSHT发展而来，它通过将这些大量的数据项储存到一个二叉树中来解决这个问题。它将定位的时间复杂度由O(n)降低到O(logn)，这使得它们更适合管理更大规模的设备或嵌套桶。

（4） Straw: 这种类型让Bucket所包含的所有item公平的竞争 ，而不需要遍历 。这种算法就像抽签一样，所有的item都有机会被抽中 ，但是长签被抽中的概率更高 。每个签的 长度是基于OSD权重基础之上又加入了随机因子参与被计算出来的权重，可以将有限的权重序列变为散列化长度的抽签 。这种Bucket是Ceph 曾 默认使用的Bucket，所以它也是经过大规模测试的，稳定性较好。虽然它的查询性能不如List和Tree，但它在控制数据迁移方面是最优的。后续优化之后又出现了Straw2。

对比来看，从查询复杂度、添加节点以及删除节点三个维度来看各个alg类型的优略：

从以上各种数据结构类型的三个维度对比来看，Straw在各个维度都比较均衡的类型，也更适合大规模的分布式存储系统，因此通常都会采用Straw来作为Bucket的数据结构类型来使用。

Ceph数据分布本身是依靠动态计算来实现Object到OSD的映射，无论是数据的写还是后期的读操作，都是要依靠算法来实现。分布式存储系统本身对数据分布有三个基本诉求：通过PG虚拟化节点的设计、CRUSH寻址算法的输入因子（PG-ID、CRUSH-MAP）两部分的影响，数据均衡分布应该是可以满足诉求的；通过CRUSH-MAP的分层树状结构以及CRUSH算法当中的Rule输入，也可以满足关于分布式存储数据分布故障隔离的诉求；最后通过Bucket数据结构类型的选择，也可以在不同场景下实现数据迁移的最小化。因此Ceph的数据分布算法机制满足了分布式存储所要求的所有基本诉求。

但是，并不是说Ceph本身是一个放之四海皆准的分布式存储系统，我们仍然需要根据具体的业务场景以及系统规模因素，对故障隔离规则、Bucket数据结构类型等关键因素提前进行规划，这样才能更好的适应企业分布式存储业务的具体场景，发挥出其应有的效应。

作者：赵海
来源：twt社区