存储系统的核心功能是数据的存取，实现这一目标的前提是正确，高效的数据寻址策略。数据寻址的方式主要有两大类：

• 查表型寻址（有中心的非对称式架构）
  典型的比如GFS等分布式文件系统。
• 计算型寻址（无中心的对称式架构）
  比如采用一致性hash的swift 和 Dynamo，以及采用CRUSH算法的ceph。

为什么采用计算型寻址？

TODO

CEPH 的数据寻址

在PB级数据存储和上千台存储服务器纳管的需求背景下，大规模分布式存储必须做到数据和负载的均衡分布，以此来提高资源利用率，最大化的系统性能输出，同时处理好系统的扩展和硬件失效的问题。
对此 ceph 自己设计了一套CRUSH 算法，用在分布式对象存储系统（RADOS）上，可以有效的将数据对象映射到存储设备（OSD）上。同时CRUSH 算法能够处理存储设备的添加和移除，并最小化由于存储设备和添加和移动而导致的数据迁移。

CRUSH 算法有两个优点：

• 客户端可以独立计算出Object所在的位置，运算过程只需要很少的集群元数据（Cluster Map）
• 同时上面的元数据只有当存储集群添加或删除设备时，才会发生改变

讲清这个算法前，先介绍ceph中的几个基本概念。

• File
  File 是要存储和访问的文件，在不同的服务下，定义是不一样的。在块存储的场景下，File 指的是挂载出去使用的RBD设备，在对象存储的场景下，File 指的一个对象，在文件存储使用的场景下，File 指文件系统中存储的用户数据

• Object
  Object 是 Ceph 底层RADOS所看到的对象，也是在Ceph中数据存储的基本单位，当File过大时，需要将File切分成统一大小的Object（通常为4MB）进行存储。

• PG
  PG 是一个逻辑的概念，它的用途是对RADOS层Object的存储进行组织和位置的映射，通过PG概念的引入，Ceph 存储系统可以更好的分配数据和定位数据。PG 是Ceph存储系统数据均衡和恢复的最小单位。

• Pool
  Pool 规定了数据冗余的类型，比如副本模式，纠删码模式，对于不同冗余类型的数据存储，需要单独的Pool划分，每个Pool 可包含多个PG。

• OSD
  OSD 负责完成数据的存取，并处理数据的复制，恢复，再均衡等任务。

1. PG 和 Object 是一对多的关系，1个PG里面组织若干个Object，但是1个Object 只能被映射到1个PG中。
2. PG 和 OSD 是多对多的关系，1个PG会映射到多个OSD 上（按照副本或者纠删码规则），每个OSD也会承载多个PG
3. PG 和 Pool 是多对一的关系。1个Pool内包含多个PG，Pool创建时可指定其中PG的数量。

image.png

Ceph 的数据寻址需要3次映射：

1. 将File 切分成多个Object，每个Object 将有一个OID标识。
2. 将每个Object 映射到一个PG中去。
3. 将Object所在的PG映射到实际的存储位置OSD上。

总结起来：Ceph 存储系统的数据寻址过程只需要输入文件的名称以及文件的大小等信息，所有计算过程都可以直接再客户端本地完成。Ceph 客户端只要获得了Cluster Map，就可以使用 算法计算出某个Object 所在的OSD 的ID，然后直接与它通信。Ceph 客户端在初始化时会从Mon服务获取最新的Cluster Map，后续如果有变化，Mon服务会将其推送给客户端。

CRUSH 算法包括两个关键输入因子：

1. 层次化的 Cluster Map
2. 数据分布策略 Placement Rules

CRUSH 算法输入因子：Cluster Map

层次化的 Cluster Map 反映了存储系统层级的物理拓扑结构。Cluster Map 由 device 和 bucket 组成，device 是最基本的存储设备，也就是OSD，通常一个OSD 对应一个磁盘存储设备。bucket 表示存放设备的容器，可以包含多个 device 和 子 bucket。device 和 bucket 的可以由如下组成：

比如一个典型的为例：

image.png

在上面的Cluster Map 中，有一个 root 类型的 bucket，名字为 default。root 下面有两个host 类型的 bucket，名字分别为 test1 和 test2，其下分别各有3个OSD 设备。

CRUSH 算法输入因子：数据分布策略 Placement Rules

Placement Rules 决定了一个PG的对象如何选择OSD。定义格式如下：

take (a)
choose 
    choose firstn {num} type {bucket-type}
    chooseleaf firstn {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. choose leaf 先选择出 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. 定位副本搜索模式（广度或者深度优先）

举例如下：
1、3个副本分布式在1个row下的3个cabinet中。

自顶而下来看，顶层是一个 root bucket，每个 root 下有4个row 类型 bucket，每个row 下面有4个cabinet，每个 cabinet 下有若干个OSD设备，该场景下，placement rules 定义如下：

step take root
step choose firstn 1 type row
step choose firstn 3 type cabinet
step choose firstn 1 type osd
step emit

2、主副本分布在SSD上，其他副本分布在HDD上。

image.png

Placement Rules 定义如下：

rule ssd-primary {
    ...
    step take ssd
    setp chooseleaf firstn 1 type host
    step emit

    step take hdd
    step chooseleaf firstn -1 type host
    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），并分别递归选择一个OSD设备，最终选出2个HDD设备。
6. 输出最终结果。

Bucket 随机选择算法

Sage 在Ceph存储系统中设计了CRUSH算法，它是一种基于深度优先的遍历算法。在CRUSH最初的实现中，设计了4种不同的基本选择算法，这些算法也是后期算法的基础。

CRUSH种定义了4种类型的bucket来代表集群架构种的叶子节点，这4种类型bucket对应了4种CRUSH算法。

• uniform bucket
• list bucket
• tree bucket
• straw bucket

4种算法对比：

straw 抽签算法

TODO