问题描述

数据分布是分布式存储系统的一个重要部分，数据分布算法至少要考虑以下 3 个因素：
1）故障域隔离。同份数据的不同副本分布在不同的故障域，降低数据损坏的风险；
2）负载均衡。数据能够均匀地分布在磁盘容量不等的存储节点，避免部分节点空闲，部分节点超载，从而影响系统性能；
3）控制节点加入离开时引起的数据迁移量。当节点离开时，最优的数据迁移是只有离线节点上的数据被迁移到其他节点，而正常工作的节点的数据不会发生迁移；

解决方案

CRUSH Algorithm，是为解决以上问题而设计的，是 Ceph 的设计精髓。

The CRUSH algorithm enables the Ceph Storage Cluster to scale, rebalance, and recover dynamically.

Using the CRUSH algorithm：Ceph calculates which placement group should contain the object, and further calculates which Ceph OSD Daemon should store the placement group.

原理简述

CRUSH Map，是个结构，该结构描述整个存储集群的结构（诸如 地域、数据中心、区域、机架、主机 等等），是人为定义的。借助于 CRUSH Map 结构，CRUSH 伪随机地存储和检索 OSD 中的数据，并使数据在整个存储集群中均匀分布。

层次结构

在 Ceph Cluster 中，CRUSH 通过简洁而层次清晰的设备描述（CRUSH Map），包括存储集群和副本放置策略，就可以有效地把数据对象映射到存储设备上，且这个过程是完全分布式的，在集群系统中的任何一方都可以独立计算任何对象的位置；

动态变化

另外，大型系统存储结构是动态变化的（存储节点的扩展或者缩容、硬件故障等），CRUSH 能够处理存储设备的变更（添加或删除），并最小化由于存储设备的变更而导致的数据迁移；

特性特征

通过 CRUSH Algorithm 计算来确定数据的存储位置，不需要像以往要查询元数据服务器才能知道数据的位置。这也是 Ceph 不需要元数据服务器的原因。

CRUSH是受控复制的分布式hash算法。
CRUSH算法可以避免单点故障、性能瓶颈以及对Ceph可扩展性的物理限制。
CRUSH 是一种基于伪随机控制数据分布、复制的算法；

数据条带化

存储系统通常都支持 Stripe（条带化）以增加存储系统的吞吐量并提升性能，数据条带化最常见的方式是做 RAID 0 或 “带区卷”，这种数据的分配方式可以弥补单个磁盘读写性能不足的问题。Ceph 条带化提供了类似于 RAID 0 的吞吐量；

决定 Ceph 条带化数据的 3 个因素：
1）对象大小：处于分布式集群中的对象拥有一个最大可配置的尺寸（例如 2MB 、4MB 等），对象大小应该足够大以适应大量的条带单元；
2）条带宽度：条带有一个可以配置的单元大小，Ceph Client 端将数据写入对象分成相同大小的条带单元，除了最后一个条带之外；每个条带宽度，应该是对象大小的一小部分，这样使得一个对象可以包含多个条带单元；
3）条带总量： Ceph 客户端写入一系列的条带单元到一系列的对象，这就决定了条带的总量，这些对象被称为对象集，当 Ceph 客户端端写入的对象集合中的最后一个对象之后，它将会返回到对象集合中的第一个对象处；

Object and PG

Ceph 条带化之后，将获得 N 个带有唯一 Object ID。Object id 是进行线性映射生成的，即由 file 的元数据、 Ceph 条带化产生的 Object 的序号连缀而成；

此时 Object 需要映射到 PG 中，该映射包括两部分：
1）由 Ceph 集群指定的静态 Hash 函数计算 Object 的 oid，获取到其 Hash 值；
2）将该 Hash 值与 mask 进行与操作，从而获得 PG ID。根据 RADOS 的设计，假定集群中设定的 PG 总数为 M（M 一般为 2 的整数幂），则 mask 的值为 M–1。由此，Hash 值计算之后，进行按位与操作是想从所有 PG 中近似均匀地随机选择。基于该原理以及概率论的相关原理，当用于数量庞大的 Object 以及 PG 时，获得到的 PG ID 是近似均匀的；

PG and OSD

由 PG 映射到数据存储的实际单元 OSD 中，该映射是由 CRUSH 算法来确定的，将 PG ID 作为该算法的输入，获得到包含 N 个 OSD 的集合，集合中第一个 OSD 被作为主 OSD，其他的 OSD 则依次作为从 OSD。N 为该 PG 所在 POOL 下的副本数目，在生产环境中 N 一般为 3；OSD 集合中的 OSD 将共同存储和维护该 PG 下的 Object。需要注意的是，CRUSH 算法的结果不是绝对不变的，而是受到其他因素的影响；

其影响因素主要有以下两个：
1）当前系统状态。也就是上文逻辑结构中曾经提及的 Cluster Map （集群映射）。当系统中的 OSD 状态、数量发生变化时，Cluster Map 可能发生变化，而这种变化将会影响到 PG 与 OSD 之间的映射。2）存储策略配置。这里的策略主要与安全相关。利用策略配置，系统管理员可以指定承载同一个 PG 的 3 个 OSD 分别位于数据中心的不同服务器乃至机架上，从而进一步改善存储的可靠性；

因此，只有在 Cluster Map 和存储策略都不发生变化的时候，PG 和 OSD 之间的映射关系才是固定不变的。在实际使用中，策略一经配置通常不会改变。而系统状态的改变或者是因为设备损坏，或者是因为存储集群规模扩大。好在 Ceph 本身提供了对于这种变化的自动化支持，因而，即便 PG 与 OSD 之间的映射关系发生了变化，并不会对应用造成困扰。事实上，Ceph 正是需要有目的的利用这种动态映射关系。正是利用了 CRUSH 的动态特性，Ceph 才可以将一个 PG 根据需要动态迁移到不同的 OSD 组合上，从而自动化地实现高可靠性、数据分布 re-blancing 等特性；

之所以在此次映射中使用 CRUSH 算法，而不是其他 Hash 算法，原因是：
1）CRUSH 具有上述可配置特性，可以根据管理员的配置参数决定 OSD 的物理位置映射策略；
2）CRUSH 具有特殊的 “稳定性 ”，也就是当系统中加入新的 OSD 导致系统规模增大时，大部分 PG 与 OSD 之间的映射关系不会发生改变，只有少部分 PG 的映射关系会发生变化并引发数据迁移；

这种可配置性和稳定性都不是普通 Hash 算法所能提供的；

PG and Pool

Ceph 存储系统支持 “池”（Pool ）的概念，这是存储对象的逻辑分区；
Ceph Client 端从 Ceph mon 端检索 Cluster Map，写入对象到 Pool。Pool 的副本数目，Crush 规则和 PG 数目决定了 Ceph 将数据存储的位置，如图所示；

Pool 至少需要设定以下参数；
·对象的所有权 / 访问权；
·PG 数目；
·该 pool 使用的 crush 规则；
·对象副本的数目；

CRUSH 关系分析

从本质上讲，CRUSH 算法是通过存储设备的权重来计算数据对象的分布的。在计算过程中，通过 Cluster Map （集群映射）、 Data Distribution Policy （数据分布策略）和给出的一个随机数共同决定数据对象的最终位置；

Cluster Map

Cluster Map 记录所有可用的存储资源及相互之间的空间层次结构（集群中有多少个机架、机架上有多少服务器、每个机器上有多少磁盘等信息）。所谓的 Map，顾名思义，就是类似于我们生活中的地图。在 Ceph 存储里，数据的索引都是通过各种不同的 Map 来实现的。另一方面，Map 使得 Ceph 集群存储设备在物理层作了一层防护。例如，在多副本（常见的三副本）的结构上，通过设置合理的 Map （故障域设置为 Host 级），可以保证在某一服务器死机的情况下，有其他副本保留在正常的存储节点上，能够继续提供服务，实现存储的高可用。设置更高的故障域级别（如 Rack 、Row 等）能保证整机柜或同一排机柜在掉电情况下数据的可用性和完整性；

（1）Cluster Map 的分层结构：

Data Distribution Policy

Data Distribution Policy 由 Placement Rules 组成。Rule 决定了每个数据对象有多少个副本，这些副本存储的限制条件（比如 3 个副本放在不同的机架中）；

根据实际的设备环境，可以定制出符合自己需求的 Rule；

CRUSH 中的伪随机

先来看一下数据映射到具体 OSD 的函数表达形式：CRUSH(x) -> (osd1, osd2, osd3…..osdn)
CRUSH 使用了多参数的 Hash 函数在 Hash 之后，映射都是按既定规则选择的，这使得从 x 到 OSD 的集合是确定的和独立的。CRUSH 只使用 Cluster Map 、Placement Rules 、X。CRUSH 是伪随机算法，相似输入的结果之间没有相关性。关于伪随机的确认性和独立性，以下我们以一个实例来展示；

以下是某个 Ceph 集群的存储的 CRUSH 结构；

[root@host-192-168-0-16 ~]# ceph osd tree
ID WEIGHT TYPE NAME UP/DOWN REWEIGHT PRIMARY-AFFINITY
-1 0.35999 root default
-3 0.09000 host host-192-168-0-17
 2 0.09000 osd.2 up 1.00000 1.00000
-4 0.09000 host host-192-168-0-18
 3 0.09000 osd.3 up 1.00000 1.00000
-2 0.17999 host host-192-168-0-16
 0 0.09000 osd.0 up 1.00000 1.00000
 1 0.09000 osd.1 up 1.00000

在此集群里我们手动创建一个 pool，并指定为 8 个 PG 和 PGP：

# ceph osd pool create crush 8 8
pool 'crush' created

可以查看 PG 映射 OSD 的集合，即 PG 具体分配到 OSD 的归属；

# ceph pg dump | grep ^22\. | awk '{print $1 "\t" $17}' ## 22
 Pool id ##
dumped all in format plain
22.1 [1,2,3]
22.0 [1,2,3]
22.3 [3,1,2]
22.2 [3,2,0]
22.5 [1,3,2]
22.4 [3,1,2]
22.7 [2,1,3]
22.6 [3,0,2]

上面示例中，第一列是 PG 的编号（其中 22 表示的 Pool 的 ID ），共计 8 个，第二列是 PG 映射到了具体的 OSD 集合。如 “22.1[1,2,3]” 表示 PG 22.1 分别在 OSD1 、OSD2 和 OSD3 分别存储副本；

在 Ceph 集群里，当有数据对象要写入集群时，需要进行两次映射。第一次从 object→PG，第二次是 PG→OSD set。每一次的映射都是与其他对象无相关的。以上充分体现了 CRUSH 的独立性（充分分散）和确定性（可确定的存储位置）；