Ceph源码解析：CRUSH算法

共计 30254 个字符，预计需要花费 76 分钟才能阅读完成。

1、简介

    随着大规模分布式存储系统 (PB 级的数据和成百上千台存储设备) 的出现。这些系统必须平衡的分布数据和负载(提高资源利用率)，最大化系统的性能，并要处理系统的扩展和硬件失效。ceph 设计了 CRUSH(一个可扩展的伪随机数据分布算法)，用在分布式对象存储系统上，可以有效映射数据对象到存储设备上(不需要中心设备)。因为大型系统的结构式动态变化的，CRUSH 能够处理存储设备的添加和移除，并最小化由于存储设备的的添加和移动而导致的数据迁移。

    为了保证负载均衡，保证新旧数据混合在一起。但是简单 HASH 分布不能有效处理设备数量的变化，导致大量数据迁移。ceph 开发了 CRUSH（Controoled Replication Under Scalable Hashing），一种伪随机数据分布算法，它能够在层级结构的存储集群中有效的分布对象的副本。CRUSH 实现了一种伪随机 (确定性) 的函数，它的参数是 object id 或 object group id，并返回一组存储设备(用于保存 object 副本 OSD)。CRUSH 需要 cluster map(描述存储集群的层级结构)、和副本分布策略(rule)。

    CRUSH 有两个关键优点：

• 任何组件都可以独立计算出每个 object 所在的位置(去中心化)。
• 只需要很少的元数据(cluster map)，只要当删除添加设备时，这些元数据才需要改变。

    CRUSH 的目的是利用可用资源优化分配数据, 当存储设备添加或删除时高效地重组数据, 以及灵活地约束对象副本放置, 当数据同步或者相关硬件故障的时候最大化保证数据安全。支持各种各样的数据安全机制, 包括多方复制(镜像),RAID 奇偶校验方案或者其他形式的校验码, 以及混合方法(比如 RAID-10)。这些特性使得 CRUSH 适合管理对象分布非常大的(PB 级别)、要求可伸缩性, 性能和可靠性非常高的存储系统。简而言之就是 PG 到 OSD 的映射过程。

2. 映射过程

2.1 概念

    ceph 中 Pool 的属性有：1.object 的副本数  2.Placement Groups 的数量    3. 所使用的 CRUSH Ruleset

    数据映射（Data Placement）的方式决定了存储系统的性能和扩展性。（Pool，PG）→ OSD set 的映射由四个因素决定：

（1）CRUSH 算法

（2）OSD MAP：包含当前所有 pool 的状态和 OSD 的状态。OSDMap 管理当前 ceph 中所有的 OSD，OSDMap 规定了 crush 算法的一个范围，在这个范围中选择 OSD 结合。OSDMap 其实就是一个树形的结构，叶子节点是 device（也就是 osd），其他的节点称为 bucket 节点，这些 bucket 都是虚构的节点，可以根据物理结构进行抽象，当然树形结构只有一个最终的根节点称之为 root 节点，中间虚拟的 bucket 节点可以是数据中心抽象、机房抽象、机架抽象、主机抽象等如下图。

                                                                      osd 组成的逻辑树形结构

struct crush_bucket
{
    __s32 id;        /* this’ll be negative */
    __u16 type;      /* non-zero; type=0 is reserved for devices */
    __u8 alg;        /* one of CRUSH_BUCKET_* */
    __u8 hash;      /* which hash function to use, CRUSH_HASH_* */
    __u32 weight;    /* 16-bit fixed point */// 权重一般有两种设法。一种按容量，一般是 1T 为 1，500G 就是 0.5。另外一种按性能。具体按实际设置。
    __u32 size;      /* num items */
    __s32 *items;

    /*
    * cached random permutation: used for uniform bucket and for
    * the linear search fallback for the other bucket types.
    */
    __u32 perm_x;  /* @x for which *perm is defined */
    __u32 perm_n;  /* num elements of *perm that are permuted/defined */
    __u32 *perm;
};

（3）CRUSH MAP：包含当前磁盘、服务器、机架的层级结构。

（4）CRUSH Rules：数据映射的策略。这些策略可以灵活的设置 object 存放的区域。比如可以指定 pool1 中所有 objects 放置在机架 1 上，所有 objects 的第 1 个副本放置在机架 1 上的服务器 A 上，第 2 个副本分布在机架 1 上的服务器 B 上。pool2 中所有的 object 分布在机架 2、3、4 上，所有 Object 的第 1 个副本分布在机架 2 的服务器上，第 2 个副本分布在机架 3 的服器上，第 3 个副本分布在机架 4 的服务器上。

2.2 流程

    Ceph 架构中，Ceph 客户端是直接读或者写存放在 OSD 上的 RADOS 对象存储中的对象（data object）的，因此，Ceph 需要走完 (Pool, Object) → (Pool, PG) → OSD set → OSD/Disk 完整的链路，才能让 ceph client 知道目标数据 object 的具体位置在哪里。

    数据写入时，文件被切分成 object，object 先映射到 PG，再由 PG 映射到 OSD set。每个 pool 有多个 PG，每个 object 通过计算 hash 值并取模得到它所对应的 PG。PG 再映射到一组 OSD（OSD 个数由 pool 的副本数决定），第一个 OSD 是 Primary，剩下的都是 Replicas。

    Ceph 分布数据的过程：首先计算数据 x 的 Hash 值并将结果和 PG 数目取余，以得到数据 x 对应的 PG 编号。然后，通过 CRUSH 算法将 PG 映射到一组 OSD 中。最后把数据 x 存放到 PG 对应的 OSD 中。这个过程中包含了两次映射，第一次是数据 x 到 PG 的映射。PG 是抽象的存储节点，它不会随着物理节点的加入或则离开而增加或减少，因此数据到 PG 的映射是稳定的。

（1）创建 Pool 和它的 PG。根据上述的计算过程，PG 在 Pool 被创建后就会被 MON 在根据 CRUSH 算法计算出来的 PG 应该所在若干的 OSD 上被创建出来了。也就是说，在客户端写入对象的时候，PG 已经被创建好了，PG 和 OSD 的映射关系已经是确定了的。

（2）Ceph 客户端通过哈希算法计算出存放 object 的 PG 的 ID：

1. 客户端输入 pool ID 和 object ID（比如 pool =“liverpool”and object-id =“john”）
2. ceph 对 object ID 做哈希
3. ceph 对该 hash 值取 PG 总数的模，得到 PG 编号（比如 58）（第 2 和第 3 步基本保证了一个 pool 的所有 PG 将会被均匀地使用）
4. ceph 对 pool ID 取 hash（比如“liverpool”= 4）
5. ceph 将  pool ID 和 PG ID 组合在一起（比如 4.58）得到 PG 的完整 ID。

  也就是：PG-id = hash(pool-id). hash(objet-id) % PG-number

（3）客户端通过 CRUSH 算法计算出（或者说查找出）object 应该会被保存到 PG 中哪个 OSD 上。（注意：这里是说”应该“，而不是”将会“，这是因为 PG 和 OSD 之间的关系是已经确定了的，那客户端需要做的就是需要知道它所选中的这个 PG 到底将会在哪些 OSD 上创建对象。）。这步骤也叫做 CRUSH 查找。

  对 Ceph 客户端来说，只要它获得了 Cluster map，就可以使用 CRUSH 算法计算出某个 object 将要所在的 OSD 的 ID，然后直接与它通信。

1. Ceph client 从 MON 获取最新的 cluster map。
2. Ceph client 根据上面的第（2）步计算出该 object 将要在的 PG 的 ID。
3. Ceph client 再根据 CRUSH 算法计算出 PG 中目标主和次 OSD 的 ID。

也就是：OSD-ids = CURSH(PG-id, cluster-map, cursh-rules)。

    具体数据读写流程下次整理分析。

3 CRUSH 算法

    CRUSH 算法根据种每个设备的权重尽可能概率平均地分配数据。分布算法是由集群可用存储资源以及其逻辑单元的 map 控制的。这个 map 的描述类似于一个大型服务器的描述：服务器由一系列的机柜组成，机柜装满服务器，服务器装满磁盘。数据分配的策略是由定位规则来定义的，定位规则指定了集群中将保存多少个副本，以及数据副本的放置有什么限制。例如，可以指定数据有三个副本，这三个副本必须放置在不同的机柜中，使得三个数据副本不公用一个物理电路。

    给定一个输入 x，CRUSH 算法将输出一个确定的有序的储存目标向量 ⃗R。当输入 x，CRUSH 利用强大的多重整数 hash 函数根据 集群 map、定位规则、以及 x 计算出独立的完全确定可靠的映射关系。CRUSH 分配算法是伪随机算法，并且输入的内容和输出的储存位置之间是没有显式相关的。我们可以说 CRUSH 算法在集群设备中生成了“伪集群”的数据副本。集群的设备对一个数据项目共享数据副本，对其他数据项目又是独立的。

    CRUSH 算法通过每个设备的权重来计算数据对象的分布。对象分布是由 cluster map 和 data distribution policy 决定的。cluster map 描述了可用存储资源和层级结构(比如有多少个机架，每个机架上有多少个服务器，每个服务器上有多少个磁盘)。data distribution policy 由 placement rules 组成。rule 决定了每个数据对象有多少个副本，这些副本存储的限制条件(比如 3 个副本放在不同的机架中)。

    CRUSH 算出 x 到一组 OSD 集合(OSD 是对象存储设备)：

(osd0, osd1, osd2 … osdn) = CRUSH(x) 

    CRUSH 利用多参数 HASH 函数，HASH 函数中的参数包括 x，使得从 x 到 OSD 集合是确定性的和独立的。CRUSH 只使用了 cluster map、placement rules、x。CRUSH 是伪随机算法，相似输入的结果之间没有相关性。

    Cluster map 由 device 和 bucket 组成，它们都有 id 和权重���。Bucket 可以包含任意数量 item。item 可以都是的 devices 或者都是 buckets。管理员控制存储设备的权重。权重和存储设备的容量有关。Bucket 的权重被定义为它所包含所有 item 的权重之和。CRUSH 基于 4 种不同的 bucket type，每种有不同的选择算法。

3.1 分层集群映射（cluster map）

    集群映射由设备和桶（buckets）组成，设备和桶都有数值的描述和权重值。桶可以包含任意多的设备或者其他的桶，使他们形成内部节点的存储层次结构, 设备总是在叶节点。存储设备的权重由管理员设置以控制相设备负责存储的相对数据量。尽管大型系统的设备含不同的容量大小和性能特点, 随机数据分布算法可以根据设备的利用率和负载来分布数据。

    这样设备的平均负载与存储的数据量成正比。这导致一维位置指标、权重、应来源于设备的能力。桶的权重是它所包含的元素的权重的总和。

    桶可由任意可用存储的层次结构组成。例如, 可以创建这样一个集群映射，用名为“shelf”的桶代表最低层的一个主机来包含主机上的磁盘设备, 然后用名为“cabinet”的桶来包含安装在同一个机架上的主机。在一个大的系统中，代表机架的“cabinet”桶可能还会包含在“row”桶或者“room”桶里。数据被通过一个伪随机类 hash 函数递归地分配到层级分明的桶元素中。传统的散列分布技术，一旦存储目标数量有变，就会导致大量的数据迁移；而 CRUSH 算法是基于桶四个不同的类型, 每一个都有不同的选择算法, 以解决添加或删除设备造成的数据移动和整体的计算复杂度。

3.2 副本放置（Replica Placement）

      CRUSH 算法的设置目的是使数据能够根据设备的存储能力和宽带资源加权平均地分布，并保持一个相对的概率平衡。副本放置在具有层次结构的存储设备中，这对数据安全也有重要影响。通过反射系统的物理安装组织，CRUSH 算法可以将系统模块化，从而定位潜在的设备故障。这些潜在故障的资源包括物理的，比如共用电源，共用的网络。通过向集群映射编码信息,CRUSH 副本放置策略可以将数据对象独立在不同故障域, 同时仍然保持所需的分布。例如, 为了定位可能存在的并发故障, 应该确保设备上的数据副本放置在不同的机架、主机、电源、控制器、或其他的物理位置。

    CRUSH 算法为了适应千篇一律的脚本，像数据复制策略和底层的硬件配置，CRUSH 对于每份数据的复制策略或者分布式策略的部署方式，它允许存储系统或 者管理员精确地指定对象副本如何放置。例如，有的会选择两个镜像来存储一对数据对象，有的会选择 3 个镜像来存储 2 个不同的数据对象，还有的会选择 6 个甚至更多的便宜廉价 RAID- 4 硬盘设备来存储等等。

函数入口：

/**
* crush_do_rule – calculate a mapping with the given input and rule
* @map: the crush_map
* @ruleno: the rule id
* @x: hash input
* @result: pointer to result vector
* @result_max: maximum result size
* @weight: weight vector (for map leaves)
* @weight_max: size of weight vector
* @scratch: scratch vector for private use; must be >= 3 * result_max
*/
int crush_do_rule(const struct crush_map *map,
int ruleno, int x, int *result, int result_max,
const __u32 *weight, int weight_max,
int *scratch)                  // 对照此函数与算法伪代码基本可以看出 crush 在做什么事情。部分数值计算我也看不懂为什么他这么做，水平有限。

 

CRUSH_RULE_TAKE    /* arg1 = value to start with */

CRUSH_RULE_CHOOSE_FIRSTN = 2, /* arg1 = num items to pick */  crush_choose_firstn()
/* arg2 = type */
CRUSH_RULE_CHOOSE_INDEP = 3, /* same */ crush_choose_indep()

CRUSH_RULE_EMIT = 4,          /* no args */   return results

 

      在算法 1 的伪代码中，每个规则都包含了一系列应用在一个简单运行环境的操作。CRUSH 函数的整型输入参数就是一个典型的对象名或者标示符，这个参数就像一堆可以被复制在相同机器上的对象复制品。操作 take(a)选择了一个在存储层次的 bucket 并把这个 bucket 分配给向量 i，这是为后面的操作做准备。操作 select(n,t)迭代每个元素 i，并且在这个点中的子树中选择了 n 个 t 类型的项。存储设备有一个绑定类型，并且每个 bucket 在系统中拥有一个用于分辨 buckets 中 classes 的类型区域（例如哪些代表 rows，哪些代表 cabinets 等）。对于每个 i，select(n,t)都会从 1 到 n 迭代调用，同时通过任何中间 buckets 降序递归，它伪随机地选择一个通过函数 c(r,x)嵌套的项，直到它找到请求 t 中的一个项。去重后的结果项 n |i| 会返回给输入变量 i，同时也会作为随后被调用的 select(n,t)操作的输入参数，或者被移动到用于触发操作的结果向量中。

• tack(a)：选择一个 item，一般是 bucket，并返回 bucket 所包含的所有 item。这些 item 是后续操作的参数，这些 item 组成向量 i。
• select(n, t)：迭代操作每个 item(向量 i 中的 item)，对于每个 item(向量 i 中的 item)向下遍历 (遍历这个 item 所包含的 item)，都返回 n 个不同的 item(type 为 t 的 item)，并把这些 item 都放到向量 i 中。select 函数会调用 c(r, x) 函数，这个函数会在每个 bucket 中伪随机选择一个 item。
• emit：把向量 i 放到 result 中

    存储设备有一个确定的类型。每个 bucket 都有 type 属性值，用于区分不同的 bucket 类型(比如”row”、”rack”、”host”等，type 可以自定义)。rules 可以包含多个 take 和 emit 语句块，这样就允许从不同的存储池中选择副本的 storage target。

      如表 1 中示例所示，该法则是从图 1 架构中的 root 节点开始，第一个 select(1.row)操作选择了一个 row 类型的单例 bucket。随后的 select(3,cabinet)操作选择了 3 个嵌套在下面 row2(cab21, cab23, cab24)行中不重复的值，同时，最后的 select(1,disk)操作迭代了输入向量中的三个 buckets，也选择了嵌套在它们其中的人一个单例磁盘。最后的结果集是三个磁盘空间分配给了三个块，但是所有的结果集都在同一行中。因此，这种方法允许复制品在容器中被同时分割和合并，这些容器包括 rows、cabinets、shelves。这种方法对于可靠性和优异的性能要求是非常有利的。这些法则包含了多次 take 和 emit 模块，它们允许从不同的存储池中获取不同的存储对象，正如在远程复制脚本或者层叠式设备那样。

3.2.1 冲突，失败和过载

      select(n,t) 操作可能会在多种层次的存储体系中查找以定位位于其起始点下的 n 个不同的 t 类型项，这是一个由选择的复制数 r =1,…, n 部分决定的迭代过程。在此过程中，CRUSH 可能会由于以下三个不同原因而丢弃（定位）项并使用修改后的输入参数 r′来重新选择（定位）项：如果某一项已经位于当前集合中（冲突——select(n,t) 的结果必须互不相同），如果设备出现故障，或者过载。虽然故障或过载设备在集群 map 中尽可能地被标记出来，但他们还是被保留在体系中以避免不必要的数据迁移。CRUSH 利用集群 map 中的可能性，特别是与过度利用相关的可能性，通过伪随机拒绝有选择的转移过载设备中的一小部分数据。对于故障或过载设备，CRUSH 通过在 select(n,t) 开始时重启递归来达到项在存储集群中的均匀分布（见算法 1 第 11 行）。对于冲突情况，替代参数 r′首先在迭代的内部级别使用以进行本地查找（见算法 1 的第 14 行），这样可以远离比较容易出现冲突的子树以避免全部数据的分布不均（比如桶（数量）比 n 小的时候）。

• 冲突：这个 item 已经在向量 i 中，已被选择。
• 故障：设备发生故障，不能被选择。
• 超载：设备使用容量超过警戒线，没有剩余空间保存数据对象。

3.2.2 复制排名

    奇偶检验和纠删码方案相比复制在配置要求上都有些许不同。在原本复制方案中，出现故障后，原先副本（已经拥有该数据的副本）成为新的原本常常是需要的。在这种情况下，CRUSH 可以使用 r′ = r + f 重新进行选择并使用前 n 个合适项，其中 f 表示执行当前操作 select(n,t)过程中定位失败的次数（见算法 1 第 16 行）。然而，在奇偶检验和纠删码方案中，CRUSH 输出中的存储设备排名或位置是特定的，因为每个目标保存了数据对象中的不同数据。特别是，如果存储设备出现故障，它应在 CRUSH 输出列表⃗R 的特定位置被替换掉，以保证列表中的其他设备排名保持不变（即查看图 2 中 ⃗R 的位置）。在这种情况下，CRUSH 使用 r′=r+frn 进行重新选择，其中 fr 是 r 中的失败尝试次数，这样就可以为每一个复制排名确定一系列在统计上与其他故障独立的候选项。相反的是，RUSH 同其他存在的哈希分布函数一样，对于故障设备没有特殊的处理机制，它想当然地假设在使用前 n 个选项时已经跳过了故障设备，这使得它对于奇偶检验方案很难处理。

3.3 Map 的变化和数据移动

    在大型文件系统中一个比较典型的部分就是数据在存储资源中的增加和移动。为了避免非对称造成的系统压力和资源的不充分利用，CRUSH 主张均衡的数据分布和系统负载。当存储系统中个别设备宕机后，CRUSH 会对这些宕机设备做相应标记，并且会将其从存储架构中移除，这样这些设备就不会参与后面的存储，同时也会将其上面的数据复制一份到其它机器进程存储。

    当集群架构发生变化后情况就比较复杂了，例如在集群中添加节点或者删除节点。在添加的数据进行移动时，CRUSH 的 mapping 过程所使用的按决策树中层次权重算法比理论上的优化算法∆w / w 更有效。在每个层次中，当一个香港子树的权重改变分布后，一些数据对象也必须跟着从下降的权重移动到上升的权重。由于集群架构中每个节点上伪随机位置决策是相互独立的，所以数据会统一重新分布在该点下面，并且无须获取重新 map 后的叶子节点在权重上的改变。仅仅更高层次的位置发送变化时，相关数据才会重新分布。这样的影响在图 3 的二进制层次结构中展示了出来。

架构中数据移动的总量有一个最低限度∆w/w，这部分数据将会根据∆w 权重重新分布在新的存储节点上。移动数据的增量会根据权重 h 以及平滑上升的界限 h ∆w 决定。当∆w 非常小以至于几乎接近 W 时移动数据的总量会通过这个上升界限进行变化，因为在每个递归过程中数据对象移动到一个子树上会有一个最低值和最小相关权重。

代码流程图：

bucket: take 操作指定的 bucket；
type: select 操作指定的 Bucket 的类型；
repnum: select 操作指定的副本数目；

rep：当前选择的副本编号；
x: 当前选择的 PG 编号；
item: 代表当前被选中的 Bucket；
c(r, x, in): 代表从 Bucket in 中为 PG x 选取第 r 个副本；
collide: 代表当前选中的副本位置 item 已经被选中，即出现了冲突；
reject: 代表当前选中的副本位置 item 被拒绝，例如，在 item 已经处于 out 状态的情况下；

ftotal: 在 Descent 域中选择的失败次数，即选择一个副本位置的总共的失败次数；
flocal: 在 Local 域中选择的失败次数；
local_retries: 在 Local 域选择冲突时的尝试次数；
local_fallback_retries: 允许在 Local 域的总共尝试次数为 bucket.size + local_fallback_retires 次，以保证遍历完 Buckt 的所有子节点；
tries: 在 Descent 的最大尝试次数，超过这个次数则放弃这个副本。

    当 Take 操作指定的 Bucket 和 Select 操作指定的 Bucket 类型之间隔着几层 Bucket 时，算法直接深度优先地进入到目的 Bucket 的直接父母节点。例如，从根节点开始选择 N 个 Host 时，它会深度优先地查找到 Rack 类型的节点，并在这个节点下选取 Host 节点。为了方便表述，将 Rack 的所有子节点标记为 Local 域，将 Take 指定的 Bucket 的子节点标记为 Descent 域，如上图所示。

    选取过程中出现冲突、过载或者故障时，算法先在 Local 域内重新选择，尝试有限次数后，如果仍然找不到满足条件的 Bucket，那就回到 Descent 域重新选择。每次重新选择时，修改副本数目为r += ftotal。因此每次选择失败都会递增 ftotal，所以可以尽量避免选择时再次选到冲突的节点。

更多详情见请继续阅读下一页的精彩内容：http://www.linuxidc.com/Linux/2017-03/141872p2.htm

3.4 Bucket 类型

    一般而言，CRUSH 的开发是为了协调两个计算目标：map 计算的高效性和可伸缩性，以及当添加或者移除存储设备后的数据均衡。在最后，CRUSH 定义了 4 种类型的 buckets 来代表集群架构中的叶子节点：一般的 buckets、列表式 buckets、树结构 buckets 以及稻草类型 buckets。对于在数据副本存储的进程中的伪随机选择嵌套项，每个类型的 bucket 都是建立在不同的内部数据结构和充分利用不同 c(r,x)函数的基础上，这些 buckets 在计算和重构效率上发挥着不同的权衡性。一般的 bucket 会被所以具有相同权重的项限制，然而其它类型的 bucket 可以在任何组合权重中包含混合项。这些 bucket 的差异总结如下表所示：

3.4.1 一般的 Bucket

    这些存储设备纯粹按个体添加进一个大型存储系统。取而代之的是，新型存储系统上存储的都是文件块，就像将机器添加进机架或者整个机柜一样。这些设备在退役后会被分拆成各个零件。在这样的环境下 CRUSH 中的一般类型 Bucket 会被当成一个设备集合一样进行使用，例如多个内存组成的计算集合和多个硬盘组成的存储集合。这样做的最大好处在于，CRUSH 可以一直 map 复制品到一般的 Bucket 中。在这种情况下，正常使用的 Bucket 就可以和不能正常使用的 Bucket 直接互不影响。

    当我们使用 c(r,x)=（hash(x)+rp）函数从 m 大小的 Bucket 中选择一个项时，CRUSH 会给一个输入值 x 和一个复制品 r，其中，p 是从大于 m 的素数中随机产生。当 r <= m 时，我们可以使用一些简单的理论数据来选择一个不重复的项。当 r >m 时，两个不同的 r 和一个 x 会被分解成相同的项。实际上，通过这个存储算法，这将意味着出现一个非零数冲突和回退的概率非常小。

    如果这个一般类型的 Bucket 大小发生改变后，数据将会在这些机器上出现完全重组。

    bucket 的所有子节点都保存在 item[]数组之中。perm_x 是记录这次随机排布时 x 的值，perm[]是在 perm_x 时候对 item 随机排列后的结果。r 则是选择第几个副本。

定位子节点过程。这时我们重新来看 uniform 定位子节点的过程。根据输入的 x 值判断是否为 perm_x，如果不是，则需要重新排列 perm[]数组，并且记录 perm_x=x。如果 x ==perm_x 时，这时算 R = r%size，算后得到 R，最后返回 perm[R]。

/*
* Choose based on a random permutation of the bucket.
*
* We used to use some prime number arithmetic to do this, but it
* wasn’t very random, and had some other bad behaviors.  Instead, we
* calculate an actual random permutation of the bucket members.
* Since this is expensive, we optimize for the r=0 case, which
* captures the vast majority of calls.
*/
static int bucket_perm_choose(struct crush_bucket *bucket,
                              int x, int r)
{
    unsigned int pr = r % bucket->size;
    unsigned int i, s;

    /* start a new permutation if @x has changed */
    if (bucket->perm_x != (__u32)x || bucket->perm_n == 0)
    {
        dprintk(“bucket %d new x=%d\n”, bucket->id, x);
        bucket->perm_x = x;

        /* optimize common r=0 case */
        if (pr == 0)
        {
            s = crush_hash32_3(bucket->hash, x, bucket->id, 0) %
                bucket->size;
            bucket->perm[0] = s;
            bucket->perm_n = 0xffff;  /* magic value, see below */
            goto out;
        }

        for (i = 0; i < bucket->size; i++)
            bucket->perm[i] = i;
        bucket->perm_n = 0;
    }
    else if (bucket->perm_n == 0xffff)
    {
        /* clean up after the r=0 case above */
        for (i = 1; i < bucket->size; i++)
            bucket->perm[i] = i;
        bucket->perm[bucket->perm[0]] = 0;
        bucket->perm_n = 1;
    }

    /* calculate permutation up to pr */
    for (i = 0; i < bucket->perm_n; i++)
        dprintk(” perm_choose have %d: %d\n”, i, bucket->perm[i]);
    while (bucket->perm_n <= pr)
    {
        unsigned int p = bucket->perm_n;
        /* no point in swapping the final entry */
        if (p < bucket->size – 1)
        {
            i = crush_hash32_3(bucket->hash, x, bucket->id, p) %
                (bucket->size – p);
            if (i)
            {
                unsigned int t = bucket->perm[p + i];
                bucket->perm[p + i] = bucket->perm[p];
                bucket->perm[p] = t;
            }
            dprintk(” perm_choose swap %d with %d\n”, p, p + i);
        }
        bucket->perm_n++;
    }
    for (i = 0; i < bucket->size; i++)
        dprintk(” perm_choose  %d: %d\n”, i, bucket->perm[i]);

    s = bucket->perm[pr];
out:
    dprintk(” perm_choose %d sz=%d x=%d r=%d (%d) s=%d\n”, bucket->id,
            bucket->size, x, r, pr, s);
    return bucket->items[s];
}

uniform bucket 适用的情况：

a. 适用于所有子节点权重相同的情况，而且 bucket 很少添加删除 item，这种情况查找速度应该是最快的。因为 uniform 的 bucket 在选择子节点时是不考虑权重的问题，全部随机选择。所以在权重上不会进行特别的照顾，为了公平起见最好是相同的权重节点。

b. 适用于子节点变化概率小的情况。当子节点的数量进行变化时，size 发生改变，在随机组合 perm 数组时，即使 x 相同，则 perm 数组需要完全重新排列，也就意味着已经保存在子节点的数据要全部发生重排，造成很多数据的迁移。所以 uniform 不适合子节点变化的 bucket，否则会产生大量已经保存的数据发生移动，所有的 item 上的数据都可能会发生相互之间的移动。

3.4.2 List 类型 buckets

    List 类型的 buckets 组织其内部的内容会像 list 的方式一样，并且里面的项都有随机的权重。为了放置一个数据副本，CRUSH 在 list 的头部开始添加项并且和除这些项外其它项的权重进行比较。根据 hash(x,r,item)函数的值，每个当前项会根据适合的概率被选择，或者出现继续递归查找该 list。这种方法重申了数据存储所存在的问题“是大部分新加项还是旧项？”这对于一个扩展中的集群是一个根本且直观的选择：一方面每个数据对象会根性相应的概率重新分配到新的存储设备上，或者依然像以前一样被存储在旧的存储设备上。这样当新的项添加进到 bucket 中时这些项会获得最优的移动方式。当这些项从 list 的中间或者末尾进行移动时，list 类型的 bucket 将比较适合这种环境。

    它的结构是链表结构，所包含的 item 可以具有任意的权重。CRUSH 从表头开始查找副本的位置，它先得到表头 item 的权重 Wh、剩余链表中所有 item 的权重之和 Ws，然后根据 hash(x, r, i)得到一个 [0~1] 的值 v，假如这个值 v 在 [0~Wh/Ws) 之中，则副本在表头 item 中，并返回表头 item 的 id，i 是 item 的 id 号。否者继续遍历剩余的链表。

    list bucket 的形成过程。list  bucket 不是真的将所有的 item 都穿成一个链表，bucket 的 item 仍然保存在 item 数组之中。这时的 list bucket 每个 item 不仅要保存的权重（根据容量换算而来）weight，还要记录前所有节点的重量之和 sum_weight 如图，list bucket 的每个 item 的权重可以不相同，也不需要按顺序排列。

list bucket 定位数据在子节点的方法。从 head 开始，会逐个的查找子节点是否保存数据。

如何判断当前子节点是否保存了数据呢？首先取了一个节点之后，根据 x，r 和 item 的 id 进行 crush_hash 得到一个 w 值。这个值与 sum_weight 之积，最后这个 w 再向右移 16 位，最后判断这个值与 weight 的大小，如果小于 weight 时，则选择当前的这个 item，否则进行查找下一个 item。

static int bucket_list_choose(struct crush_bucket_list *bucket,
                              int x, int r)
{
    int i;

    for (i = bucket->h.size – 1; i >= 0; i–)
    {
        __u64 w = crush_hash32_4(bucket->h.hash, x, bucket->h.items[i],
                                r, bucket->h.id);
        w &= 0xffff;
        dprintk(“list_choose i=%d x=%d r=%d item %d weight %x ”
                “sw %x rand %llx”,
                i, x, r, bucket->h.items[i], bucket->item_weights[i],
                bucket->sum_weights[i], w);
        w *= bucket->sum_weights[i];
        w = w >> 16;
        /*dprintk(” scaled %llx\n”, w);*/
        if (w < bucket->item_weights[i])
            return bucket->h.items[i];
    }

    dprintk(“bad list sums for bucket %d\n”, bucket->h.id);
    return bucket->h.items[0];
}

list bucket 使用的情况：

a. 适用于集群拓展类型。当增加 item 时，会产生最优的数据移动。因为在 list bucket 中增加一个 item 节点时，都会增加到 head 部，这时其他节点的 sum_weight 都不会发生变化，只需要将 old_head 上的 sum_weight 和 weight 之和添加到 new_head 的 sum_weight 就好了。这样时其他 item 之间不需要进行数据移动，其他的 item 上的数据 只需要和 head 上比较就好，如果算的 w 值小于 head 的 weight，则需要移动到 head 上，否则还保存在原来的 item 上。这样就获得了最优最少的数据移动。

b.list bucket 存在一个缺点，就是在查找 item 节点时，只能顺序查找 时间复杂度为 O(n)。

3.4.3 树状 Buckets

    像任何链表结构一样，列表 buckets 对于少量的数据项还是高效的，而遇到大量的数据就不合适了，其时间复杂度就太大了。树状 buckets 由 RUSHT 发展而来，它通过将这些大量的数据项储存到一个二叉树中来解决这个问题（时间复杂度过大）。它将定位的时间复杂度由 O(n)降低到 O(logn)，这使其适用于管理大得多设备数量或嵌套 buckets。RUSHT i 等价于一个由单一树状 bucket 组成的二级 CRUSH 结构，该树状 bucket 包含了许多一般 buckets.

    树状 buckets 是一种加权二叉排序树，数据项位于树的叶子节点。每个递归节点有其左子树和右子树的总权重，并根据一种固定的算法（下面会讲述）进行标记。为了从 bucket 中选择一个数据项，CRUSH 由树的根节点开始（计算），计算输入主键 x，副本数量 r,bucket 标识以及当前节点（初始值是根节点）标志的哈希值，计算的结果会跟（当前节点）左子树和右子树的权重比进行比较，仪确定下次访问的节点。重复这一过程直至到达（存储)相应数据项的叶子节点。定位该数据项最多只需要进行 logn 次哈希值计算和比较。

    该 buckett 二叉树结点使用一种简单固定的策略来得到二进制数进行标记，以避免当树增长或收缩时标记更改。该树最左侧的叶子节点通常标记为“1”，每次树扩展时，原来的根节点成为新根节点的左子树，新根节点的标记由原根节点的标记左移一位得到（比如 1 变成 10，10 变成 100 等）。右子树的标记在左子树标记的基础上增加了“1”，拥有 6 个叶子节点的标记二叉树如图 4 所示。这一策略保证了当 bucket 增加（或删除）新数据项并且树结构增长（或收缩）时，二叉树中现有项的路径通过在根节点处增加（或删除）额外节点即可实现，决策树的初始位置随之发生变化。一旦某个对象放入特定的子树中，其最终的 mapping 将仅由该子树中的权重和节点标记来决定，只要该子树中的数据项不发生变化 mapping 就不会发生变化。虽然层次化的决策树在嵌套数据项项之间会增加额外的数据迁移，但是这一（标记）策略可以保证移动在可接受范围内，同时还能为非常巨大的 bucket 提供有效的 mapping。

    链表的查找复杂度是 O(n)，决策树的查找复杂度是 O(log n)。item 是决策树的叶子节点，决策树中的其他节点知道它左右子树的权重，节点的权重等于左右子树的权重之和。CRUSH 从 root 节点开始查找副本的位置，它先得到节点的左子树的权重 Wl，得到节点的权重 Wn，然后根据 hash(x, r, node_id)得到一个 [0~1] 的值 v，假如这个值 v 在 [0~Wl/Wn) 中，则副本在左子树中，否者在右子树中。继续遍历节点，直到到达叶子节点。Tree Bucket 的关键是当添加删除叶子节点时，决策树中的其他节点的 node_id 不变。决策树中节点的 node_id 的标识是根据对二叉树的中序遍历来决定的(node_id 不等于 item 的 id，也不等于节点的权重)

    tree bucket 会借助一个叫做 node_weight[]的数组来进行帮助搜索定位 item。首先是 node_weight[]的形成，nodeweight[]中不仅包含了 item，而且增加了很多中间节点，item 都作为叶子节点。父节点的重量等于左右子节点的重量之和，递归到根节点如下图。

    tree bucket 的搜索过程，通过一定的方法形成 node tree。这 tree 的查找从根节点开始直到找到叶子节点。当前节点的重量 weight 使用 crush_hash(x,r）修正后，与左节点的重量 left_weight 比较，如果比左节点轻 则继续遍历左节点，否则遍历右节点如下图。所以该类型的 bucket 适合于查找的，对于变动的集群就没那么合适了。

static int bucket_tree_choose(struct crush_bucket_tree *bucket,
                              int x, int r)
{
    int n;
    __u32 w;
    __u64 t;

    /* start at root */
    n = bucket->num_nodes >> 1;

    while (!terminal(n))
    {
        int l;
        /* pick point in [0, w) */
        w = bucket->node_weights[n];
        t = (__u64)crush_hash32_4(bucket->h.hash, x, n, r,
                                  bucket->h.id) * (__u64)w;
        t = t >> 32;

        /* descend to the left or right? */
        l = left(n);
        if (t < bucket->node_weights[l])
            n = l;
        else
            n = right(n);
    }

    return bucket->h.items[n >> 1];
}

3.4.4 Straw 类型 Buckets

    列表 buckets 和树状 buckets 的结构决定了只有有限的哈希值需要计算并与权重进行比较以确定 bucket 中的项。这样做的话，他们采用了分而治之的方式，要么给特定项以优先权（比如那些在列表开头的项），要么消除完全考虑整个子树的必要。尽管这样提高了副本定位过程的效率，但当向 buckets 中增加项、删除项或重新计算某一项的权重以改变其内容时，其重组的过程是次最优的。

    Straw 类型 bucket 允许所有项通过类似抽签的方式来与其他项公平“竞争”。定位副本时，bucket 中的每一项都对应一个随机长度的 straw，且拥有最长长度的 straw 会获得胜利（被选中）。每一个 straw 的长度都是由固定区间内基于 CRUSH 输入 x, 副本数目 r, 以及 bucket 项 i. 的哈希值计算得到的一个值。每一个 straw 长度都乘以根据该项权重的立方获得的一个系数 f(wi)，这样拥有最大权重的项更容易被选中。比如 c(r,x)=maxi(f(wi)hash(x,r,i)). 尽管 straw 类型 bucket 定位过程要比列表 bucket（平均）慢一倍，甚至比树状 bucket 都要慢（树状 bucket 的时间复杂度是 log(n)），但是 straw 类型的 bucket 在修改时最近邻项之间数据的移动是最优的。

    Bucket 类型的选择是基于预期的集群增长类型，以权衡映射方法的运算量和数据移动之间的效率，这样的权衡是非常值得的。当 buckets 是固定时（比如一个存放完全相同磁盘的机柜），一般类型的 buckets 是最快的。如果一个 bucket 预计将会不断增长，则列表类型的 buckets 在其列表开头插入新项时将提供最优的数据移动。这允许 CRUSH 准确恰当地转移足够的数据到新添加的设备中，而不影响其他 bucket 项。其缺点是映射速度的时间复杂度为 O(n) 且当旧项移除或重新计算权重时会增加额外的数据移动。当删除和重新计算权重的效率特别重要时（比如存储结构的根节点附近（项）），straw 类型的 buckets 可以为子树之间的数据移动提供最优的解决方案。树状 buckets 是一种适用于任何情况的 buckets，兼具高性能与出色的重组效率。

    这种类型让 bucket 所包含的所有 item 公平的竞争 (不像 list 和 tree 一样需要遍历)。这种算法就像抽签一样，所有的 item 都有机会被抽中(只有最长的签才能被抽中)。每个签的长度是由 length = f(Wi)*hash(x, r, i) 决定的，f(Wi) 和 item 的权重有关，i 是 item 的 id 号。c(r, x) = MAX(f(Wi) * hash(x, r, i))。

    这种类型是一种抽签类型的 bucket，他选择子节点是公平的，straw 和 uniform 的区别在于，straw 算法考虑了子节点的权重，所以是最公平的 bucket 类型。

    straw bucket 首先根据每个节点的重量生成的 straw，最后组成 straw[] 数组。在 straw 定位副本的过程中，每一个定位都需要遍历所有的 item，长度 draw = crush(x,r,item_id)*straw[i]。找出那个最长的，最后选择这个最长，定位到副本。

static int bucket_straw_choose(struct crush_bucket_straw *bucket,
                              int x, int r)
{
    __u32 i;
    int high = 0;
    __u64 high_draw = 0;
    __u64 draw;

    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;
        }
    }
    return bucket->h.items[high];
}

3.5 CRUSH RULE

crush rule 主要有 3 个重点：a. 从 OSDMap 中的哪个节点开始查找，b. 使用那个节点作为故障隔离域，c. 定位副本的搜索模式（广度优先 or 深度优先）。

# rules

rule replicated_ruleset                            #规则集的命名，创建 pool 时可以指定 rule 集
{
    ruleset 0                                      #rules 集的编号，顺序编即可
    type replicated                                #定义 pool 类型为 replicated(还有 esurecode 模式)
    min_size 1                                    #pool 中最小指定的副本数量不能小 1\

    max_size 10                                    #pool 中最大指定的副本数量不能大于 10   

    step take default                              #定义 pg 查找副本的入口点

    step chooseleaf  firstn  0  type  host        #选叶子节点、深度优先、隔离 host
    step emit        #结束
}

pg 选择 osd 的过程，首先要知道在 rules 中 指明从 osdmap 中哪个节点开始查找，入口点默认为 default 也就是 root 节点，然后隔离域为 host 节点(也就是同一个 host 下面不能选择两个子节点)。由 default 到 3 个 host 的选择过程，这里由 default 根据节点的 bucket 类型选择下一个子节点，由子节点再根据本身的类型继续选择，知道选择到 host，然后在 host 下选择一个 osd。

还在学习阶段，整理了一些资料，自己也看了看 crush 的代码实现，后续有新理解再增加内容，有错误恳请指教。

在 CentOS 7.1 上安装分布式存储系统 Ceph  http://www.linuxidc.com/Linux/2015-08/120990.htm

Ceph 环境配置文档 PDF http://www.linuxidc.com/Linux/2013-05/85212.htm 

CentOS7 下部署 Ceph 集群（版本 10.2.2）http://www.linuxidc.com/Linux/2017-02/140728.htm

Ceph 的安装过程 http://www.linuxidc.com/Linux/2013-05/85210.htm 

如何升级 Ceph 版本及注意事项  http://www.linuxidc.com/Linux/2017-02/140631.htm

HOWTO Install Ceph On FC12, FC 上安装 Ceph 分布式文件系统 http://www.linuxidc.com/Linux/2013-05/85209.htm 

实验环境 Ceph 9.2.1 部署笔记 http://www.linuxidc.com/Linux/2016-11/137094.htm

Ubuntu 16.04 快速安装 Ceph 集群  http://www.linuxidc.com/Linux/2016-09/135261.htm

Ceph 的详细介绍：请点这里
Ceph 的下载地址：请点这里

本文永久更新链接地址：http://www.linuxidc.com/Linux/2017-03/141872.htm

1、简介

    随着大规模分布式存储系统 (PB 级的数据和成百上千台存储设备) 的出现。这些系统必须平衡的分布数据和负载(提高资源利用率)，最大化系统的性能，并要处理系统的扩展和硬件失效。ceph 设计了 CRUSH(一个可扩展的伪随机数据分布算法)，用在分布式对象存储系统上，可以有效映射数据对象到存储设备上(不需要中心设备)。因为大型系统的结构式动态变化的，CRUSH 能够处理存储设备的添加和移除，并最小化由于存储设备的的添加和移动而导致的数据迁移。

    为了保证负载均衡，保证新旧数据混合在一起。但是简单 HASH 分布不能有效处理设备数量的变化，导致大量数据迁移。ceph 开发了 CRUSH（Controoled Replication Under Scalable Hashing），一种伪随机数据分布算法，它能够在层级结构的存储集群中有效的分布对象的副本。CRUSH 实现了一种伪随机 (确定性) 的函数，它的参数是 object id 或 object group id，并返回一组存储设备(用于保存 object 副本 OSD)。CRUSH 需要 cluster map(描述存储集群的层级结构)、和副本分布策略(rule)。

    CRUSH 有两个关键优点：

• 任何组件都可以独立计算出每个 object 所在的位置(去中心化)。
• 只需要很少的元数据(cluster map)，只要当删除添加设备时，这些元数据才需要改变。

    CRUSH 的目的是利用可用资源优化分配数据, 当存储设备添加或删除时高效地重组数据, 以及灵活地约束对象副本放置, 当数据同步或者相关硬件故障的时候最大化保证数据安全。支持各种各样的数据安全机制, 包括多方复制(镜像),RAID 奇偶校验方案或者其他形式的校验码, 以及混合方法(比如 RAID-10)。这些特性使得 CRUSH 适合管理对象分布非常大的(PB 级别)、要求可伸缩性, 性能和可靠性非常高的存储系统。简而言之就是 PG 到 OSD 的映射过程。

2. 映射过程

2.1 概念

    ceph 中 Pool 的属性有：1.object 的副本数  2.Placement Groups 的数量    3. 所使用的 CRUSH Ruleset

    数据映射（Data Placement）的方式决定了存储系统的性能和扩展性。（Pool，PG）→ OSD set 的映射由四个因素决定：

（1）CRUSH 算法

（2）OSD MAP：包含当前所有 pool 的状态和 OSD 的状态。OSDMap 管理当前 ceph 中所有的 OSD，OSDMap 规定了 crush 算法的一个范围，在这个范围中选择 OSD 结合。OSDMap 其实就是一个树形的结构，叶子节点是 device（也就是 osd），其他的节点称为 bucket 节点，这些 bucket 都是虚构的节点，可以根据物理结构进行抽象，当然树形结构只有一个最终的根节点称之为 root 节点，中间虚拟的 bucket 节点可以是数据中心抽象、机房抽象、机架抽象、主机抽象等如下图。

                                                                      osd 组成的逻辑树形结构

struct crush_bucket
{
    __s32 id;        /* this’ll be negative */
    __u16 type;      /* non-zero; type=0 is reserved for devices */
    __u8 alg;        /* one of CRUSH_BUCKET_* */
    __u8 hash;      /* which hash function to use, CRUSH_HASH_* */
    __u32 weight;    /* 16-bit fixed point */// 权重一般有两种设法。一种按容量，一般是 1T 为 1，500G 就是 0.5。另外一种按性能。具体按实际设置。
    __u32 size;      /* num items */
    __s32 *items;

    /*
    * cached random permutation: used for uniform bucket and for
    * the linear search fallback for the other bucket types.
    */
    __u32 perm_x;  /* @x for which *perm is defined */
    __u32 perm_n;  /* num elements of *perm that are permuted/defined */
    __u32 *perm;
};

（3）CRUSH MAP：包含当前磁盘、服务器、机架的层级结构。

（4）CRUSH Rules：数据映射的策略。这些策略可以灵活的设置 object 存放的区域。比如可以指定 pool1 中所有 objects 放置在机架 1 上，所有 objects 的第 1 个副本放置在机架 1 上的服务器 A 上，第 2 个副本分布在机架 1 上的服务器 B 上。pool2 中所有的 object 分布在机架 2、3、4 上，所有 Object 的第 1 个副本分布在机架 2 的服务器上，第 2 个副本分布在机架 3 的服器上，第 3 个副本分布在机架 4 的服务器上。

2.2 流程

    Ceph 架构中，Ceph 客户端是直接读或者写存放在 OSD 上的 RADOS 对象存储中的对象（data object）的，因此，Ceph 需要走完 (Pool, Object) → (Pool, PG) → OSD set → OSD/Disk 完整的链路，才能让 ceph client 知道目标数据 object 的具体位置在哪里。

    数据写入时，文件被切分成 object，object 先映射到 PG，再由 PG 映射到 OSD set。每个 pool 有多个 PG，每个 object 通过计算 hash 值并取模得到它所对应的 PG。PG 再映射到一组 OSD（OSD 个数由 pool 的副本数决定），第一个 OSD 是 Primary，剩下的都是 Replicas。

    Ceph 分布数据的过程：首先计算数据 x 的 Hash 值并将结果和 PG 数目取余，以得到数据 x 对应的 PG 编号。然后，通过 CRUSH 算法将 PG 映射到一组 OSD 中。最后把数据 x 存放到 PG 对应的 OSD 中。这个过程中包含了两次映射，第一次是数据 x 到 PG 的映射。PG 是抽象的存储节点，它不会随着物理节点的加入或则离开而增加或减少，因此数据到 PG 的映射是稳定的。

（1）创建 Pool 和它的 PG。根据上述的计算过程，PG 在 Pool 被创建后就会被 MON 在根据 CRUSH 算法计算出来的 PG 应该所在若干的 OSD 上被创建出来了。也就是说，在客户端写入对象的时候，PG 已经被创建好了，PG 和 OSD 的映射关系已经是确定了的。

（2）Ceph 客户端通过哈希算法计算出存放 object 的 PG 的 ID：

1. 客户端输入 pool ID 和 object ID（比如 pool =“liverpool”and object-id =“john”）
2. ceph 对 object ID 做哈希
3. ceph 对该 hash 值取 PG 总数的模，得到 PG 编号（比如 58）（第 2 和第 3 步基本保证了一个 pool 的所有 PG 将会被均匀地使用）
4. ceph 对 pool ID 取 hash（比如“liverpool”= 4）
5. ceph 将  pool ID 和 PG ID 组合在一起（比如 4.58）得到 PG 的完整 ID。

  也就是：PG-id = hash(pool-id). hash(objet-id) % PG-number

（3）客户端通过 CRUSH 算法计算出（或者说查找出）object 应该会被保存到 PG 中哪个 OSD 上。（注意：这里是说”应该“，而不是”将会“，这是因为 PG 和 OSD 之间的关系是已经确定了的，那客户端需要做的就是需要知道它所选中的这个 PG 到底将会在哪些 OSD 上创建对象。）。这步骤也叫做 CRUSH 查找。

  对 Ceph 客户端来说，只要它获得了 Cluster map，就可以使用 CRUSH 算法计算出某个 object 将要所在的 OSD 的 ID，然后直接与它通信。

1. Ceph client 从 MON 获取最新的 cluster map。
2. Ceph client 根据上面的第（2）步计算出该 object 将要在的 PG 的 ID。
3. Ceph client 再根据 CRUSH 算法计算出 PG 中目标主和次 OSD 的 ID。

也就是：OSD-ids = CURSH(PG-id, cluster-map, cursh-rules)。

    具体数据读写流程下次整理分析。

3 CRUSH 算法

    CRUSH 算法根据种每个设备的权重尽可能概率平均地分配数据。分布算法是由集群可用存储资源以及其逻辑单元的 map 控制的。这个 map 的描述类似于一个大型服务器的描述：服务器由一系列的机柜组成，机柜装满服务器，服务器装满磁盘。数据分配的策略是由定位规则来定义的，定位规则指定了集群中将保存多少个副本，以及数据副本的放置有什么限制。例如，可以指定数据有三个副本，这三个副本必须放置在不同的机柜中，使得三个数据副本不公用一个物理电路。

    给定一个输入 x，CRUSH 算法将输出一个确定的有序的储存目标向量 ⃗R。当输入 x，CRUSH 利用强大的多重整数 hash 函数根据 集群 map、定位规则、以及 x 计算出独立的完全确定可靠的映射关系。CRUSH 分配算法是伪随机算法，并且输入的内容和输出的储存位置之间是没有显式相关的。我们可以说 CRUSH 算法在集群设备中生成了“伪集群”的数据副本。集群的设备对一个数据项目共享数据副本，对其他数据项目又是独立的。

    CRUSH 算法通过每个设备的权重来计算数据对象的分布。对象分布是由 cluster map 和 data distribution policy 决定的。cluster map 描述了可用存储资源和层级结构(比如有多少个机架，每个机架上有多少个服务器，每个服务器上有多少个磁盘)。data distribution policy 由 placement rules 组成。rule 决定了每个数据对象有多少个副本，这些副本存储的限制条件(比如 3 个副本放在不同的机架中)。

    CRUSH 算出 x 到一组 OSD 集合(OSD 是对象存储设备)：

(osd0, osd1, osd2 … osdn) = CRUSH(x) 

    CRUSH 利用多参数 HASH 函数，HASH 函数中的参数包括 x，使得从 x 到 OSD 集合是确定性的和独立的。CRUSH 只使用了 cluster map、placement rules、x。CRUSH 是伪随机算法，相似输入的结果之间没有相关性。

    Cluster map 由 device 和 bucket 组成，它们都有 id 和权重���。Bucket 可以包含任意数量 item。item 可以都是的 devices 或者都是 buckets。管理员控制存储设备的权重。权重和存储设备的容量有关。Bucket 的权重被定义为它所包含所有 item 的权重之和。CRUSH 基于 4 种不同的 bucket type，每种有不同的选择算法。

3.1 分层集群映射（cluster map）

    集群映射由设备和桶（buckets）组成，设备和桶都有数值的描述和权重值。桶可以包含任意多的设备或者其他的桶，使他们形成内部节点的存储层次结构, 设备总是在叶节点。存储设备的权重由管理员设置以控制相设备负责存储的相对数据量。尽管大型系统的设备含不同的容量大小和性能特点, 随机数据分布算法可以根据设备的利用率和负载来分布数据。

    这样设备的平均负载与存储的数据量成正比。这导致一维位置指标、权重、应来源于设备的能力。桶的权重是它所包含的元素的权重的总和。

    桶可由任意可用存储的层次结构组成。例如, 可以创建这样一个集群映射，用名为“shelf”的桶代表最低层的一个主机来包含主机上的磁盘设备, 然后用名为“cabinet”的桶来包含安装在同一个机架上的主机。在一个大的系统中，代表机架的“cabinet”桶可能还会包含在“row”桶或者“room”桶里。数据被通过一个伪随机类 hash 函数递归地分配到层级分明的桶元素中。传统的散列分布技术，一旦存储目标数量有变，就会导致大量的数据迁移；而 CRUSH 算法是基于桶四个不同的类型, 每一个都有不同的选择算法, 以解决添加或删除设备造成的数据移动和整体的计算复杂度。

3.2 副本放置（Replica Placement）

      CRUSH 算法的设置目的是使数据能够根据设备的存储能力和宽带资源加权平均地分布，并保持一个相对的概率平衡。副本放置在具有层次结构的存储设备中，这对数据安全也有重要影响。通过反射系统的物理安装组织，CRUSH 算法可以将系统模块化，从而定位潜在的设备故障。这些潜在故障的资源包括物理的，比如共用电源，共用的网络。通过向集群映射编码信息,CRUSH 副本放置策略可以将数据对象独立在不同故障域, 同时仍然保持所需的分布。例如, 为了定位可能存在的并发故障, 应该确保设备上的数据副本放置在不同的机架、主机、电源、控制器、或其他的物理位置。

    CRUSH 算法为了适应千篇一律的脚本，像数据复制策略和底层的硬件配置，CRUSH 对于每份数据的复制策略或者分布式策略的部署方式，它允许存储系统或 者管理员精确地指定对象副本如何放置。例如，有的会选择两个镜像来存储一对数据对象，有的会选择 3 个镜像来存储 2 个不同的数据对象，还有的会选择 6 个甚至更多的便宜廉价 RAID- 4 硬盘设备来存储等等。

函数入口：

/**
* crush_do_rule – calculate a mapping with the given input and rule
* @map: the crush_map
* @ruleno: the rule id
* @x: hash input
* @result: pointer to result vector
* @result_max: maximum result size
* @weight: weight vector (for map leaves)
* @weight_max: size of weight vector
* @scratch: scratch vector for private use; must be >= 3 * result_max
*/
int crush_do_rule(const struct crush_map *map,
int ruleno, int x, int *result, int result_max,
const __u32 *weight, int weight_max,
int *scratch)                  // 对照此函数与算法伪代码基本可以看出 crush 在做什么事情。部分数值计算我也看不懂为什么他这么做，水平有限。

 

CRUSH_RULE_TAKE    /* arg1 = value to start with */

CRUSH_RULE_CHOOSE_FIRSTN = 2, /* arg1 = num items to pick */  crush_choose_firstn()
/* arg2 = type */
CRUSH_RULE_CHOOSE_INDEP = 3, /* same */ crush_choose_indep()

CRUSH_RULE_EMIT = 4,          /* no args */   return results

 

      在算法 1 的伪代码中，每个规则都包含了一系列应用在一个简单运行环境的操作。CRUSH 函数的整型输入参数就是一个典型的对象名或者标示符，这个参数就像一堆可以被复制在相同机器上的对象复制品。操作 take(a)选择了一个在存储层次的 bucket 并把这个 bucket 分配给向量 i，这是为后面的操作做准备。操作 select(n,t)迭代每个元素 i，并且在这个点中的子树中选择了 n 个 t 类型的项。存储设备有一个绑定类型，并且每个 bucket 在系统中拥有一个用于分辨 buckets 中 classes 的类型区域（例如哪些代表 rows，哪些代表 cabinets 等）。对于每个 i，select(n,t)都会从 1 到 n 迭代调用，同时通过任何中间 buckets 降序递归，它伪随机地选择一个通过函数 c(r,x)嵌套的项，直到它找到请求 t 中的一个项。去重后的结果项 n |i| 会返回给输入变量 i，同时也会作为随后被调用的 select(n,t)操作的输入参数，或者被移动到用于触发操作的结果向量中。

• tack(a)：选择一个 item，一般是 bucket，并返回 bucket 所包含的所有 item。这些 item 是后续操作的参数，这些 item 组成向量 i。
• select(n, t)：迭代操作每个 item(向量 i 中的 item)，对于每个 item(向量 i 中的 item)向下遍历 (遍历这个 item 所包含的 item)，都返回 n 个不同的 item(type 为 t 的 item)，并把这些 item 都放到向量 i 中。select 函数会调用 c(r, x) 函数，这个函数会在每个 bucket 中伪随机选择一个 item。
• emit：把向量 i 放到 result 中

    存储设备有一个确定的类型。每个 bucket 都有 type 属性值，用于区分不同的 bucket 类型(比如”row”、”rack”、”host”等，type 可以自定义)。rules 可以包含多个 take 和 emit 语句块，这样就允许从不同的存储池中选择副本的 storage target。

      如表 1 中示例所示，该法则是从图 1 架构中的 root 节点开始，第一个 select(1.row)操作选择了一个 row 类型的单例 bucket。随后的 select(3,cabinet)操作选择了 3 个嵌套在下面 row2(cab21, cab23, cab24)行中不重复的值，同时，最后的 select(1,disk)操作迭代了输入向量中的三个 buckets，也选择了嵌套在它们其中的人一个单例磁盘。最后的结果集是三个磁盘空间分配给了三个块，但是所有的结果集都在同一行中。因此，这种方法允许复制品在容器中被同时分割和合并，这些容器包括 rows、cabinets、shelves。这种方法对于可靠性和优异的性能要求是非常有利的。这些法则包含了多次 take 和 emit 模块，它们允许从不同的存储池中获取不同的存储对象，正如在远程复制脚本或者层叠式设备那样。

3.2.1 冲突，失败和过载

      select(n,t) 操作可能会在多种层次的存储体系中查找以定位位于其起始点下的 n 个不同的 t 类型项，这是一个由选择的复制数 r =1,…, n 部分决定的迭代过程。在此过程中，CRUSH 可能会由于以下三个不同原因而丢弃（定位）项并使用修改后的输入参数 r′来重新选择（定位）项：如果某一项已经位于当前集合中（冲突——select(n,t) 的结果必须互不相同），如果设备出现故障，或者过载。虽然故障或过载设备在集群 map 中尽可能地被标记出来，但他们还是被保留在体系中以避免不必要的数据迁移。CRUSH 利用集群 map 中的可能性，特别是与过度利用相关的可能性，通过伪随机拒绝有选择的转移过载设备中的一小部分数据。对于故障或过载设备，CRUSH 通过在 select(n,t) 开始时重启递归来达到项在存储集群中的均匀分布（见算法 1 第 11 行）。对于冲突情况，替代参数 r′首先在迭代的内部级别使用以进行本地查找（见算法 1 的第 14 行），这样可以远离比较容易出现冲突的子树以避免全部数据的分布不均（比如桶（数量）比 n 小的时候）。

• 冲突：这个 item 已经在向量 i 中，已被选择。
• 故障：设备发生故障，不能被选择。
• 超载：设备使用容量超过警戒线，没有剩余空间保存数据对象。

3.2.2 复制排名

    奇偶检验和纠删码方案相比复制在配置要求上都有些许不同。在原本复制方案中，出现故障后，原先副本（已经拥有该数据的副本）成为新的原本常常是需要的。在这种情况下，CRUSH 可以使用 r′ = r + f 重新进行选择并使用前 n 个合适项，其中 f 表示执行当前操作 select(n,t)过程中定位失败的次数（见算法 1 第 16 行）。然而，在奇偶检验和纠删码方案中，CRUSH 输出中的存储设备排名或位置是特定的，因为每个目标保存了数据对象中的不同数据。特别是，如果存储设备出现故障，它应在 CRUSH 输出列表⃗R 的特定位置被替换掉，以保证列表中的其他设备排名保持不变（即查看图 2 中 ⃗R 的位置）。在这种情况下，CRUSH 使用 r′=r+frn 进行重新选择，其中 fr 是 r 中的失败尝试次数，这样就可以为每一个复制排名确定一系列在统计上与其他故障独立的候选项。相反的是，RUSH 同其他存在的哈希分布函数一样，对于故障设备没有特殊的处理机制，它想当然地假设在使用前 n 个选项时已经跳过了故障设备，这使得它对于奇偶检验方案很难处理。

3.3 Map 的变化和数据移动

    在大型文件系统中一个比较典型的部分就是数据在存储资源中的增加和移动。为了避免非对称造成的系统压力和资源的不充分利用，CRUSH 主张均衡的数据分布和系统负载。当存储系统中个别设备宕机后，CRUSH 会对这些宕机设备做相应标记，并且会将其从存储架构中移除，这样这些设备就不会参与后面的存储，同时也会将其上面的数据复制一份到其它机器进程存储。

    当集群架构发生变化后情况就比较复杂了，例如在集群中添加节点或者删除节点。在添加的数据进行移动时，CRUSH 的 mapping 过程所使用的按决策树中层次权重算法比理论上的优化算法∆w / w 更有效。在每个层次中，当一个香港子树的权重改变分布后，一些数据对象也必须跟着从下降的权重移动到上升的权重。由于集群架构中每个节点上伪随机位置决策是相互独立的，所以数据会统一重新分布在该点下面，并且无须获取重新 map 后的叶子节点在权重上的改变。仅仅更高层次的位置发送变化时，相关数据才会重新分布。这样的影响在图 3 的二进制层次结构中展示了出来。

架构中数据移动的总量有一个最低限度∆w/w，这部分数据将会根据∆w 权重重新分布在新的存储节点上。移动数据的增量会根据权重 h 以及平滑上升的界限 h ∆w 决定。当∆w 非常小以至于几乎接近 W 时移动数据的总量会通过这个上升界限进行变化，因为在每个递归过程中数据对象移动到一个子树上会有一个最低值和最小相关权重。

代码流程图：

bucket: take 操作指定的 bucket；
type: select 操作指定的 Bucket 的类型；
repnum: select 操作指定的副本数目；

rep：当前选择的副本编号；
x: 当前选择的 PG 编号；
item: 代表当前被选中的 Bucket；
c(r, x, in): 代表从 Bucket in 中为 PG x 选取第 r 个副本；
collide: 代表当前选中的副本位置 item 已经被选中，即出现了冲突；
reject: 代表当前选中的副本位置 item 被拒绝，例如，在 item 已经处于 out 状态的情况下；

ftotal: 在 Descent 域中选择的失败次数，即选择一个副本位置的总共的失败次数；
flocal: 在 Local 域中选择的失败次数；
local_retries: 在 Local 域选择冲突时的尝试次数；
local_fallback_retries: 允许在 Local 域的总共尝试次数为 bucket.size + local_fallback_retires 次，以保证遍历完 Buckt 的所有子节点；
tries: 在 Descent 的最大尝试次数，超过这个次数则放弃这个副本。

    当 Take 操作指定的 Bucket 和 Select 操作指定的 Bucket 类型之间隔着几层 Bucket 时，算法直接深度优先地进入到目的 Bucket 的直接父母节点。例如，从根节点开始选择 N 个 Host 时，它会深度优先地查找到 Rack 类型的节点，并在这个节点下选取 Host 节点。为了方便表述，将 Rack 的所有子节点标记为 Local 域，将 Take 指定的 Bucket 的子节点标记为 Descent 域，如上图所示。

    选取过程中出现冲突、过载或者故障时，算法先在 Local 域内重新选择，尝试有限次数后，如果仍然找不到满足条件的 Bucket，那就回到 Descent 域重新选择。每次重新选择时，修改副本数目为r += ftotal。因此每次选择失败都会递增 ftotal，所以可以尽量避免选择时再次选到冲突的节点。

更多详情见请继续阅读下一页的精彩内容：http://www.linuxidc.com/Linux/2017-03/141872p2.htm