2.2.2 CRUSH 算法因子
上述介绍可以看出，CRUSH 算法在 Ceph 存储系统的数据寻址中占有核心地位，Ceph 存储系统通过 CRUSH 算法规则来控制数据的分布策略，Ceph 存储系统的 CRUSH算法能够控制对象文件在存储集群中随机均匀地分布。
CRUSH 算法包含两个关键输入因子：层次化的 Cluster Map 以及数据分布策略Placement Rules。
1. 层次化的 Cluster Map
层次化的 Cluster Map 反映了存储系统层级的物理拓扑结构。
Ceph 存储集群通过 Cluster Map 定义了 OSD 守护进程的静态拓扑关系（层级信息），使得 CRUSH 算法在选择 OSD 时具备了主机、机架、机房等信息的感知能力。通过Cluster Map 规则定义，Ceph 存储系统允许数据副本可以分布在不同的主机、不同的机架，甚至不同的机房中，提高了数据存储的安全性。
Cluster Map 由设备（device）和桶（bucket）组成，device 是最基本的存储设备，也就是 OSD，通常 1 个 OSD 对应 1 个磁盘存储设备，bucket 表示存放设备的容器，可以包含多个设备或子类型的 bucket。
存储设备（device）的权重由管理员设置，以控制设备负责存储的相对数据量，device的权重值越高，对应的磁盘就会被分配写入更多的数据。大型存储系统中的存储设备（磁盘）通常存在容量大小不等或者性能高低不一的情况，系统管理员可以依据存储设备的利用率和负载来设定权重，随机数据分布算法，以此控制数据的最终分布，实现存储系统设备的数据量均衡，进而平衡存储系统的 I/O 负载，最终提高存储集群整体的性能和可靠性。
桶的权重是它所包含的所有元素（device 及 bucket）权重的总和。Bucket 可以包含很多种类型，例如，Host 就代表一个主机节点，可以包含多个 device ；Rack 代表机架，包含多个 host 节点。Ceph 中默认有 OSD、host、Chassis、Rack、row、PDU、Pod、Room、Datacenter、Region、root，共计 11 个层级（同时也允许用户定义自己新的类型），它们含义如下。
OSD 磁盘设备，对应 OSD 守护进程
host 包含若干个 OSD 的主机
Chassis 包含若干个刀片服务器的机箱
Rack 包含若干个主机的机架
row 包含若干个主机的一排机柜
PDU 为机柜分配的电源插排
Pod 一个数据中心中的机房单间
Room 含若干个机柜和主机的机房
Datacenter 包含若干机房的数据中心
Region 包含若干数据中心的区域
root bucket 分层结构的根
通常 OSD、host、Rack 层级较为常用。
下面举例说明 bucket 的用法。
host test1{ // 类型 host，名字为 test1 id -2 //bucket 的 ID，一般为负值 # weight 3.000 // 权重，默认为子 item 的权重之和 alg straw //bucket 随机选择的算法 hash 0 //bucket 随机选择的算法使用的 hash 函数 // 这里 0 代表使用 hash 函数 jenkins1 item osd.1 weight 1.000 //item1: osd.1 和权重 item osd.2 weight 1.000 item osd.3 weight 1.000 } host test2{ id -3 # weight 3.00 alg straw hash 0 item osd.3 weight 1.000 item osd.4 weight 1.000 item osd.5 weight 1.000 } root default{ //root 的类型为 bucket，名字为 default id -1 //ID 号 # weight 6.000 alg straw hash 0 item test1 weight 3.000 item test2 weight 3.000 }
根据上面 Cluster Map 的语法定义，图 2-2 给出了比较直观的层级化的树形结构。
如图 2-2 所示，Ceph 的 Cluster Map 是一个由 bucket 和 device 共同组成的树形存储层次结构，叶子节点是 device（也就是 OSD），其他的节点称为 bucket 节点，这些 bucket都是逻辑上的概念，是对物理结构的抽象（如对数据中心的抽象、机房的抽象、机架的抽象、主机的抽象等），树形结构只有一个最终的根节点，称为 root 节点，root 也是一个抽象的逻辑概念。
图 2-2 Ceph 的 Cluster Map 层级结构
在上面的 Cluster Map 中，有一个 root 类型的 bucket，名字为 default ；root 下面有两个 host 类型的 bucket，名字分别为 test1 和 test2，其下分别各有 3 个 OSD 设备，每个 device 的权重都为 1.000，说明它们的容量大小都相同。host 的权重为子设备之和，即test1 与 test2 的权重均为 3.000，它是自动计算的，不需要设置；同理，root 的权重为 6.000。
2. 数据分布策略 Placement Rules
Placement Rules 决定了一个 PG 的对象（副本或纠删码策略）如何选择 OSD，通过这些自定义的规则，用户可以设置副本在集群中的分布。
Ceph 存储系统的 Placement Rules 定义格式如下。
take(a) choose choose fifirstn {num} type {bucket-type} chooseleaf fifirstn {num} type {bucket-type} If {num} == 0， choose pool-num-replicas buckets (all-available). If {num} > 0 && < pool-num-replicas， choose that many buckets. If {num} < 0， it means pool-num-replicas - |{num}|. Emit
Placement Rules 的执行流程如下。
（1）take 操作选择一个 bucket，一般是 root 类型的 bucket。
（2）choose 操作有不同的选择方式，其输入都是上一步的输出。
a）choose firstn 深度优先选择出 num 个类型为 bucket-type 的子 bucket。
b）chooseleaf 先选择出 num 个类型为 bucket-type 的子 bucket，然后递归到叶子节点，选择一个 OSD 设备。
i. 如果 num 为 0，num 就为 Pool 设置的副本数；
ii. 如果 num 大于 0，小于 Pool 的副本数，那么就选出 num 个；
iii. 如果 num 小于 0， 就选出 Pool 的副本数减去 num 的绝对值。
（3）emit 输出结果。
由上述流程可以看出，Placement Rules 主要定义以下 3 个关键操作。
（1）从 CRUSH Map 中的哪个节点开始查找；
（2）使用哪个节点作为故障隔离域；
（3）定位副本的搜索模式（广度优先或深度优先）。
3. 示例
（1）3 个副本分布在 1 个 row 下的 3 个 cabinet 中。
在图 2-3 中，最下面的长方形图例代表一台主机，里面的圆柱形图例代表 OSD，cabinet 图例代表一个机柜，row 图例代表一排机柜，顶端的 root 是根节点，可以把它理解成一个数据中心。
图 2-3 Ceph 数据分布示意（Cluster Map）
自顶而下来看，顶层是一个 root bucket，每个 root 下有 4 个 row 类型 bucket，每个 row 下面有 4 个 cabinet，每个 cabinet 下有若干个 OSD 设备（图中有 4 个 host，每个host 有若干个 OSD 设备，但是在本 CRUSH Map 中并没有设置 host 这一级别的 bucket，而是直接把 4 个 host 上的所有 OSD 设备定义为一个 cabinet）。
该场景下，Placement Rules 定义如下。
rule replicated_ruleset { ruleset 0 //ruleset 的编号 ID type replicated // 类型 replicated 或者 erasure code min_size 1 // 副本数最小值 max_size 10 // 副本数最大值 step take root // 选择一个 root bucket，做下一步的输入 step choose fifirstn 1 type row // 选择一个 row，同一排 step choose fifirstn 3 type cabinet // 选择 3 个 cabinet，3 副本分别在不同的 cabinet step choose fifirstn 1 type osd // 在上一步输出的3个cabinet中，分别选择一个OSD step emit }
根据上面的 Cluster Map 和 Placement Rules 定义，选择算法的执行过程如下。
1）选中 root bucket 作为下一个步骤的输入；
2）从 root 类型的 bucket 中选择 1 个 row 类的子 bucket，其选择的算法在 root 的定义中设置，一般设置为 straw 算法；
3）从上一步的输出 row 中，选择 3 个 cabinet，其选择的算法在 row 中定义；
4）从上一步输出的 3 个 cabinet 中，分别选出一个 OSD，并输出。最终实现效果为可选择出 3 个 OSD 设备，分布在 1 个 row 上的 3 个 cabinet 中。
（2）主副本分布在 SSD 上，其他副本分布在 HDD 上。
如图 2-4 所示的 Cluster Map 定义了 2 个 root 类型的 bucket，一个是名为 SSD 的root 类型的 bucket，其 OSD 存储介质都是 SSD 固态硬盘，它包含 2 个 host，每个 host上的存储设备都是 SSD 固态硬盘；另一个是名为 HDD 的 root 类型的 bucket，其 OSD 存储介质都是 HDD 硬盘，它有 2 个 host，每个 host 上的设备都是 HDD 硬盘。
图 2-4 Ceph 数据分布示意（Cluster Map）
该场景下，Placement Rules 定义如下。
rule ssd-primary { ruleset 0 type replicated min_size 1 max_size 10 step take ssd // 选择 SSD 这个 root bucket 为输入 step chooseleaf fifirstn 1 type host // 选择一个 host， 并递归选择叶子节点 OSD step emit // 输出结果 step take hdd // 选择 HDD 这个 root bucket 为输入 step chooseleaf fifirstn -1 type host // 选择总副本数减一个 host // 并分别递归选择一个叶子节点 OSD step emit // 输出结果 }
根据上面的 Cluster Map 和 Placement Rules 定义，选择算法的执行过程如下。
1）首先 take 操作选择 ssd 为 root 类型的 bucket ；
2）在 SSD 的 root 中先选择一个 host，然后以该 host 为输入，递归至叶子节点，选择一个 OSD 设备；
3）输出选择的设备，也就是 SSD 设备；
4）选择 HDD 作为 root 的输入；
5）选择 2 个 host（副本数减 1，默认 3 副本），并分别递归选择一个 OSD 设备，最终选出 2 个 HDD 设备；
6）输出最终结果。
最终实现效果为输出 3 个设备，一个是 SSD 类型的磁盘，另外两个是 HDD 磁盘。通过上述规则，就可以把 PG 的主副本存储在 SSD 类型的 OSD 上，其他副本分布在 HDD 类型的磁盘上。
