Ceph CRUSH 实现细节分析

CRUSH（Controlled Replication Under Scalable Hashing）是 Ceph 存储系统中用于数据分布和复制的算法。关于 CRUSH 的论文解析参考: 译 - CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data 。CRUSH map 是 Ceph 集群中一个关键的配置组件，它定义了数据如何在集群的物理硬件上分布。 CRUSH 算法使得 Ceph 能够在无需中心化或者分布式元数据管理器的情况下，高效、可靠地进行数据复制和恢复。

一、CRUSH map 解析

CRUSH map 包含了集群的层次结构和各种规则，这些规则定义了数据应该如何在集群中分布。 CRUSH map 主要包含以下几个部分：

• Tunables : 一组可用于调整 CRUSH 算法行为的参数。
• Devices : 定义集群中所有可用的存储设备的列表。
• Types : 定义存储层次结构中的不同层级类型。
• Buckets : 组织和管理存储设备（如 OSDs ）的逻辑容器。
• Rules : 定义了数据的复制方式。

新建 crush map 相关代码:

struct crush_map* crush_create()
{
    struct crush_map* m;
    m = malloc(sizeof(*m));
    if (!m) return NULL;
    memset(m, 0, sizeof(*m));

    // 初始化配置
    set_optimal_crush_map(m);
    return m;
}

void set_optimal_crush_map(struct crush_map* map)
{
    map->choose_local_tries = 0;
    map->choose_local_fallback_tries = 0;
    map->choose_total_tries = 50;
    map->chooseleaf_descend_once = 1;
    map->chooseleaf_vary_r = 1;
    map->chooseleaf_stable = 1;
    map->allowed_bucket_algs = ((1 << CRUSH_BUCKET_UNIFORM) | 
                                (1 << CRUSH_BUCKET_LIST) | 
                                (1 << CRUSH_BUCKET_STRAW) | 
                                (1 << CRUSH_BUCKET_STRAW2));
}

相关命令:

# 查看 crush map
rm -rf crushmap.file crushmap-human.file
ceph osd getcrushmap -o crushmap.file
crushtool -d crushmap.file -o crushmap-human.file
cat crushmap-human.file

CRUSH map 示例:

# begin crush map
tunable choose_local_tries 0
tunable choose_local_fallback_tries 0
tunable choose_total_tries 50
tunable chooseleaf_descend_once 1
tunable chooseleaf_vary_r 1
tunable chooseleaf_stable 1
tunable straw_calc_version 1
tunable allowed_bucket_algs 54

# devices
device 0 osd.0 class hdd
device 1 osd.1 class hdd
device 2 osd.2 class hdd
device 3 osd.3 class hdd
device 4 osd.4 class hdd
device 5 osd.5 class hdd

# types
type 0 osd
type 1 host
type 2 chassis
type 3 rack
type 4 row
type 5 pdu
type 6 pod
type 7 room
type 8 datacenter
type 9 zone
type 10 region
type 11 root

# buckets
host node01 {
        id -3            # do not change unnecessarily
        id -4 class hdd  # do not change unnecessarily
        # weight 0.19537
        alg straw2
        hash 0  # rjenkins1
        item osd.0 weight 0.09769
        item osd.1 weight 0.09769
}
host node02 {
        id -5            # do not change unnecessarily
        id -6 class hdd  # do not change unnecessarily
        # weight 0.19537
        alg straw2
        hash 0  # rjenkins1
        item osd.2 weight 0.09769
        item osd.3 weight 0.09769
}
host node03 {
        id -7            # do not change unnecessarily
        id -8 class hdd  # do not change unnecessarily
        # weight 0.19537
        alg straw2
        hash 0  # rjenkins1
        item osd.4 weight 0.09769
        item osd.5 weight 0.09769
}
root default {
        id -1            # do not change unnecessarily
        id -2 class hdd  # do not change unnecessarily
        # weight 0.58612
        alg straw2
        hash 0  # rjenkins1
        item node01 weight 0.19537
        item node02 weight 0.19537
        item node03 weight 0.19537
}

# rules
rule replicated_rule {
        id 0
        type replicated
        step take default
        step chooseleaf firstn 0 type host
        step emit
}
# end crush map

1.1、Tunables

一组可用于调整 CRUSH 算法行为的参数。通过调整这些参数，管理员可以优化数据的分布和复制策略，以适应特定的性能需求或硬件配置。

# begin crush map
tunable choose_local_tries 0
tunable choose_local_fallback_tries 0
tunable choose_total_tries 50
tunable chooseleaf_descend_once 1
tunable chooseleaf_vary_r 1
tunable chooseleaf_stable 1
tunable straw_calc_version 1
tunable allowed_bucket_algs 54

字段解析:

• choose_local_tries: 控制 CRUSH 算法在尝试找到一个本地副本（即在同一物理位置，如同一机架或同一数据中心）时的尝试次数。如果设置为 0 ，表示 CRUSH 算法不会尝试在本地找到副本。增加这个值会使算法更倾向于在本地找到副本，可能提高访问速度但减少数据分散度。
• choose_local_fallback_tries: 定义了在 choose_local_tries 未能找到本地副本后， CRUSH 算法尝试找到非本地副本之前的额外本地尝试次数。如果设置为 0 ，表示没有额外的本地回退尝试。增加这个值可以增加在本地找到副本的机会，同样可能影响数据的分散度和容错性。
• choose_total_tries: 定义了 CRUSH 算法在放弃之前尝试选择不同项的总次数。较低的值可能导致数据分布不均，而较高的值增加了计算复杂性，但可以改善数据的均匀分布。
• chooseleaf_descend_once: 控制 CRUSH 算法在选择叶节点（通常是存储设备）时是否只遍历树结构一次。设置为 1 时，算法只遍历一次，减少了计算量并提高了效率，但可能影响在复杂拓扑中的数据分布精度。
• chooseleaf_vary_r: 控制每次选择叶节点时种子是否有所变化，以增加随机性。设置为 1 时，每次选择过程的随机性增加，有助于数据的均匀分布。
• chooseleaf_stable: 确保相同的输入在 CRUSH 算法的不同版本中给出相同的输出。设置为 1 时，可以保持数据分布的一致性，特别是在升级或修改集群配置时。
• straw_calc_version: 指定使用 Straw 算法的版本， Straw 算法用于决定数据在不同存储桶之间的分配。版本 1 是较旧的版本，可能不如版本 2 在数据分布上有效和均匀。
• allowed_bucket_algs: 指定允许使用的 bucket 算法的位掩码。通过限制或启用特定的 bucket 算法，管理员可以根据具体的数据分布需求调整算法的使用，影响数据的分布和性能。

1.2、Devices

定义集群中所有可用的存储设备的列表。每个设备通常对应一个 OSD（Object Storage Daemon）。每个条目通常包含: 设备ID，OSD编号，类别。device 的 id 都是大于等于零的非负数。

# devices
device 0 osd.0 class hdd
device 1 osd.1 class hdd
device 2 osd.2 class hdd
device 3 osd.3 class hdd
device 4 osd.4 class hdd
device 5 osd.5 class hdd

1.3、Types

定义存储层次结构中的不同层级类型。

字段解析:

# types
type 0 osd         # 基本存储单元，通常对应一个物理存储设备
type 1 host        # 一台物理服务器或虚拟机，它可以包含一个或多个 osd
type 2 chassis     # 机箱或机柜，可以包含一组服务器或多个设备
type 3 rack        # 数据中心中的一个机架，通常包含多个服务器或机柜
type 4 row         # 数据中心中的一行机架
type 5 pdu         # 电源分配单元。不常见，可以用来表示依赖于同一电源单元的设备组
type 6 pod         # 表示包含多个机架或行的更大物理单元
type 7 room        # 数据中心中的一个房间，可能包含多个 pod 或行
type 8 datacenter  # 整个数据中心，是物理存储资源的大集合
type 9 zone        # 一个区域或集群的一部分
type 10 region     # 一个更大的地理区域，可能包含多个数据中心或区域
type 11 root       # CRUSH 层次结构中的最顶层，代表整个存储集群

1.4、Buckets

用来组织和管理存储设备（如 OSDs ）的逻辑容器。每个 bucket 可以包含 OSDs 或其他 buckets ，形成一个层次化的结构，这有助于定义数据在集群中的分布方式。 bucket 的设计允许 CRUSH 算法模拟物理存储的层次结构，如机架、行、数据中心等，以及在这些层次上实施数据复制和负载均衡策略。bucket 的 id 都是小于零的负数。

# buckets
host node01 {
        id -3            # do not change unnecessarily
        id -4 class hdd  # do not change unnecessarily
        # weight 0.19537
        alg straw2
        hash 0  # rjenkins1
        item osd.0 weight 0.09769
        item osd.1 weight 0.09769
}

......

root default {
        id -1            # do not change unnecessarily
        id -2 class hdd  # do not change unnecessarily
        # weight 0.58612
        alg straw2
        hash 0  # rjenkins1
        item node01 weight 0.19537
        item node02 weight 0.19537
        item node03 weight 0.19537
}

字段解析:

• host/root: bucket 类型。对应于 CRUSH 层次结构中的一个层级，如 host、rack、datacenter 等。
• node01/default: bucket 名称。通常反映其在物理或逻辑结构中的角色，如 node01、default 等。
• id: bucket id。这个 id 在 CRUSH map 中是唯一的，用于区分不同的 buckets。
• alg: bucket 算法。bucket 使用特定的算法来决定如何在其包含的项（ OSDs 或其他 buckets ）之间分配数据。常见的算法包括 uniform/list/tree/straw/straw2 。
  • uniform: 对应 CRUSH_BUCKET_UNIFORM 。一种简单的分配策略，其中所有子项都具有相同的权重，适用于所有子项具有均等的存储容量和性能的情况。
  • list: 对应 CRUSH_BUCKET_LIST 。按照列表中的顺序和指定的权重来分配数据，允许管理员精确控制数据分配的顺序，适用于需要按特定顺序优先分配数据的场景。
  • tree: 对应 CRUSH_BUCKET_TREE 。基于树形结构的数据分配方法，其中数据是按层次结构递归分配的。适用于复杂的层次结构，如多层数据中心的环境，它可以有效地在多个层级上平衡数据分布。
  • straw: 对应 CRUSH_BUCKET_STRAW 。使用一种称为 straw 算法的方法来分配数据。每个子项被赋予一个 straw ，其长度与子项的权重成比例。选择子项的概率与其 straw 的长度成正比。适用于子项之间权重差异较大的情况。
  • straw2: 对应 CRUSH_BUCKET_STRAW2 。straw 算法的改进版本，它修正了原始 straw 算法中的一些不平衡问题，提供了更加均匀和公平的数据分配。在各种场景下都能提供更好的负载均衡和数据分散性。
• hash: hash 函数。用于决定如何在 bucket 的子项之间选择。常见的哈希函数包括 rjenkins1（对应配置参数为 0 ） 。
• item: bucket 子项。这些子项可以是 OSDs（Object Storage Daemons）或者是其他的 buckets 。每个条目定义了子项的 ID 、权重以及其他可能的属性。

部分桶算法的比较:

桶算法	时间复杂度	添加	移除
uniform	O(1)	差	差
list	O(n)	优	差
straw2	O(n)	优	优

1.5、Rules

定义了数据的复制方式。例如，一个规则可能指定一个数据块应该被复制三次，并存储在不同的机架上以确保容错。

# rules
rule replicated_rule {
        id 0
        type replicated
        step take default
        step chooseleaf firstn 0 type host
        step emit
}
# end crush map

字段解析:

• rule: rule 标记。
• replicated_rule: rule name。自定义的 rule 。
• id: rule id。规则的唯一标识符。
• type: rule type。可选值为 replicated/erasure/msr_firstn/msr_indep 。
  • replicated: 最常用的规则类型，用于创建数据的多个副本。每个数据对象会在多个物理位置存储相同的副本，以提高数据的可用性和耐久性。适用于需要高数据可靠性和快速恢复能力的场景。如果一个存储节点失败，其他节点上的副本可以立即提供数据，无需复杂的恢复过程。
  • erasure: 使用纠删码技术，将数据分割成多个数据块和校验块。这种方法可以在保持相似的容错能力的同时，比简单复制更有效地使用存储空间。适用于大规模数据存储，特别是当存储成本是一个重要考虑因素时。虽然纠删码提供了高存储效率，但其恢复过程可能比复制更复杂，对性能的影响也较大。
  • msr_firstn: MSR (Multi-Site Replication) 是一种多站点复制策略，其中 FirstN 指的是在多个站点中选择前 N 个站点进行数据复制。适用于需要跨地理位置进行数据复制的场景，以实现灾难恢复和数据本地化。FirstN策略确保数据被复制到指定数量的最优站点，通常基于位置或其他标准选择。
  • msr_indep: MSR (Multi-Site Replication) 是一种多站点复制策略，其中 IndeP 指数据在每个站点独立地被复制和管理，而不是选择固定数量的站点。这种模式适用于那些需要在每个站点独立管理数据的场景，允许每个站点根据本地需求和策略来优化数据存储和访问。这种类型的复制可以提高灵活性和数据自治。
• step:
  • take: 指定了 CRUSH 算法开始选择的起点。通常，这个起点是一个 bucket ，例如一个数据中心、机架或服务器组。
  • chooseleaf: 选择方式。选择存储数据的叶子节点。叶子节点通常是指实际存储数据的设备，如硬盘或SSD。
  • choose: 选择方式。类似于 chooseleaf ，但不限于选择叶子节点。 choose 可以用于在任何级别的 bucket 中进行选择。该操作允许在非叶子级别进行更复杂的数据分布决策，例如在不同的数据中心或机架之间进行选择。
  • firstn: 选择模式。指定选择的叶子节点的数量。这个数字可以是具体的数量，也可以是 0 （表示根据复制因子自动确定数量）。常用于需要固定数量副本的场景，如在多个数据中心或机架中复制数据，确保数据的高可用性和冗余。
  • indep: 选择模式。表示每次选择都是独立的，不受之前选择的影响。这意味着即使多次执行相同的选择操作，也可能得到不同的结果。适用于需要增强随机性和分布均匀性的场景。它有助于避免因选择过程中的依赖关系而导致的数据局部化和热点问题。
  • type: 指定叶子节点的类型，如 host、rack 等，这决定了数据复制的物理分隔程度。
  • emit: 标志着选择过程的结束，输出最终确定的存储目标。

二、对象映射规则

数据对象到 OSD 的映射主要包含两个阶段:

• 对象映射到 PG：简单的哈希。
• PG 映射到 OSD 列表：CRUSH 伪随机算法。

2.1、对象映射到 PG

概要代码:

// 创建对象的定位信息
object_locator_t oloc(pool, namespacestr);

// 创建对象信息
object_t oid(objstr);

// 计算对象的原始 pg id 信息
pg_t pgid = osdmap.object_locator_to_pg(oid, oloc);

// 将对象的原始 pg id 信息转换为实际可存储的 pg 信息
// 其实是将原始 pg id 映射到 pg_num 的有效范围内
pg_t mpgid = osdmap.raw_pg_to_pg(pgid);

计算 pgid 的规则如下: （注意这里的 hashfunc 为特定 pool 的 hash 类型，目前支持 linux 和 rjenkins 这两种类型，默认为 rjenkins）

• 如果 oloc.hash >= 0 : 则 pgid = pg_t(oloc.hash, oloc.pool)
• 如果 oloc.hash < 0 && oloc.key 非空 && oloc.nspace 非空 : 则 pgid = pg_t(hashfunc(oloc.nspace + '\037' + oloc.key), oloc.pool)
• 如果 oloc.hash < 0 && oloc.key 非空 && oloc.nspace 为空 : 则 pgid = pg_t(hashfunc(oloc.key), oloc.pool)
• 如果 oloc.hash < 0 && oloc.key 为空 && oloc.nspace 非空 : 则 pgid = pg_t(hashfunc(oloc.nspace + '\037' + oid.name), oloc.pool)
• 如果 oloc.hash < 0 && oloc.key 为空 && oloc.nspace 为空 : 则 pgid = pg_t(hashfunc(oid.name), oloc.pool)

计算 mpgid 的规则如下:

• 规则前提: pg_num_mask 是将 pg_num 向上取到最近的二次幂数值，然后减一得到的（pgp_num 和 pgp_num_mask 关系亦如此）。比如 pg_num=16，则 pg_num_mask=15； pg_num=10，则 pg_num_mask=15；
• 计算规则:
  • 如果 (pgid.m_seed & pg_num_mask) < pg_num ， 则 mpgid.m_seed = pgid.m_seed & pg_num_mask
  • 如果 (pgid.m_seed & pg_num_mask) >= pg_num ， 则 mpgid.m_seed = pgid.m_seed & (pg_num_mask >> 1)
• 参考数值计算示例:

pgid.m_seed	pg_num	pg_num_mask	(pgid.m_seed & pg_num_mask) < pg_num	mpgid.m_seed
7	10	15	Yes	7 & 15 = 7
12	10	15	No	12 & (15 >> 1) = 4
133	16	15	Yes	133 & 15 = 5

对象映射到 PG 的相关代码实现:

struct object_t
{
    std::string name;
}

struct object_locator_t
{
    // You specify either the hash or the key -- not both
    std::int64_t pool;    // pool id
    std::string key;      // key string (if non-empty)
    std::string nspace;   // namespace
    std::int64_t hash;    // hash position (if >= 0)
}

struct pg_t
{
    uint64_t m_pool;
    uint32_t m_seed;
}

pg_t OSDMap::object_locator_to_pg(const object_t& oid, const object_locator_t& loc) const
{
    pg_t pg;
    int ret = object_locator_to_pg(oid, loc, pg);
    ceph_assert(ret == 0);
    return pg;
}

int OSDMap::object_locator_to_pg(const object_t& oid, const object_locator_t& loc, pg_t& pg) const
{
    if (loc.hash >= 0) {
        if (!get_pg_pool(loc.get_pool())) {
            return -ENOENT;
        }
        pg = pg_t(loc.hash, loc.get_pool());
        return 0;
    }
    return map_to_pg(loc.get_pool(), oid.name, loc.key, loc.nspace, &pg);
}

// mapping
int OSDMap::map_to_pg(int64_t poolid, const string& name, const string& key, const string& nspace, pg_t* pg) const
{
    // calculate ps (placement seed)
    const pg_pool_t* pool = get_pg_pool(poolid);
    if (!pool) return -ENOENT;
    ps_t ps;
    if (!key.empty())
        ps = pool->hash_key(key, nspace);
    else
        ps = pool->hash_key(name, nspace);
    *pg = pg_t(ps, poolid);
    return 0;
}

pg_t pg_pool_t::raw_pg_to_pg(pg_t pg) const
{
    pg.set_ps(ceph_stable_mod(pg.ps(), pg_num, pg_num_mask));
    return pg;
}

static inline int ceph_stable_mod(int x, int b, int bmask)
{
    if ((x & bmask) < b)
        return x & bmask;
    else
        return x & (bmask >> 1);
}

void pg_pool_t::calc_pg_masks()
{
    pg_num_mask = (1 << cbits(pg_num - 1)) - 1;
    pgp_num_mask = (1 << cbits(pgp_num - 1)) - 1;
}

2.2、PG 映射到 OSD 列表

概要代码:

vector<int> up, acting;
int up_p, acting_p;

// 获取指定 PG 映射的 OSD 列表
osdmap.pg_to_up_acting_osds(mpgid, &up, &up_p, &acting, &acting_p);

// 重点函数
static int crush_do_rule_no_retry(const struct crush_map* map, int ruleno, int x, int* result, int result_max, const __u32* weight, int weight_max, void* cwin, const struct crush_choose_arg* choose_args)

在处理 crush rule 的时候，内部会针对不同的操作类型执行不同的操作，相关的操作类型如下:

• CRUSH_RULE_SET_CHOOSE_TRIES: 对应操作为 step set_choose_tries ；
• CRUSH_RULE_SET_CHOOSELEAF_TRIES: 对应操作为 step set_choose_local_tries ， 会覆盖 chooseleaf_descend_once 参数， 相关的参数还有 choose_total_tries ；
• CRUSH_RULE_SET_CHOOSE_LOCAL_TRIES: 对应操作为 step set_choose_local_tries ；
• CRUSH_RULE_SET_CHOOSE_LOCAL_FALLBACK_TRIES: 对应操作为 step set_choose_local_fallback_tries ；
• CRUSH_RULE_SET_CHOOSELEAF_VARY_R: 对应操作为 step set_chooseleaf_vary_r，对应配置为 chooseleaf_vary_r ；
• CRUSH_RULE_SET_CHOOSELEAF_STABLE: 对应操作为 step set_chooseleaf_stable， 对应配置为 chooseleaf_stable ；
• CRUSH_RULE_TAKE: 对应操作为 step take ；
• CRUSH_RULE_CHOOSELEAF_FIRSTN: 对应操作为 step chooseleaf firstn ；
• CRUSH_RULE_CHOOSE_FIRSTN: 对应操作为 step choose firstn ；
• CRUSH_RULE_CHOOSELEAF_INDEP: 对应操作为 step chooseleaf indep ；
• CRUSH_RULE_CHOOSE_INDEP: 对应操作为 step choose indep ；
• CRUSH_RULE_EMIT: 对应操作为 step emit ；

PG 映射到 OSD 列表的相关代码实现:

void OSDMap::_pg_to_raw_osds(const pg_pool_t& pool, pg_t pg, vector<int>* osds, ps_t* ppps) const
{
    // placement ps
    ps_t pps = pool.raw_pg_to_pps(pg);

    // size: pool 副本数量
    unsigned size = pool.get_size();

    // 获取对应 crush role id
    int ruleno = pool.get_crush_rule();

    // 
    if (ruleno >= 0) crush->do_rule(ruleno, pps, *osds, size, osd_weight, pg.pool());

    // 移除不存在的 OSDs
    _remove_nonexistent_osds(pool, *osds);

    if (ppps) *ppps = pps;
}

template<typename WeightVector>
void do_rule(int rule, int x, std::vector<int>& out, int maxout, const WeightVector& weight, uint64_t choose_args_index) const
{
    int rawout[maxout];
    char work[crush_work_size(crush, maxout)];
    crush_init_workspace(crush, work);
    crush_choose_arg_map arg_map = choose_args_get_with_fallback(choose_args_index);
    int numrep = crush_do_rule(crush, rule, x, rawout, maxout, std::data(weight), std::size(weight), work, arg_map.args);
    if (numrep < 0) numrep = 0;
    out.resize(numrep);
    for (int i = 0; i < numrep; i++) out[i] = rawout[i];
}

int crush_do_rule(const struct crush_map* map, int ruleno, int x, int* result, int result_max, const __u32* weight, int weight_max, void* cwin, const struct crush_choose_arg* choose_args)
{
    const struct crush_rule* rule;

    if ((__u32)ruleno >= map->max_rules) {
        dprintk(" bad ruleno %d\n", ruleno);
        return 0;
    }

    rule = map->rules[ruleno];
    if (rule_type_is_msr(rule->type)) {
        // 处理 CRUSH_RULE_TYPE_MSR_FIRSTN 和 CRUSH_RULE_TYPE_MSR_INDEP 类型的 rule
        return crush_msr_do_rule(map, ruleno, x, result, result_max, weight, weight_max, cwin, choose_args);
    }
    else {
        // 处理 CRUSH_RULE_TYPE_REPLICATED 和 CRUSH_RULE_TYPE_ERASURE 类型的 rule
        return crush_do_rule_no_retry(map, ruleno, x, result, result_max, weight, weight_max, cwin, choose_args);
    }
}

static int crush_bucket_choose(const struct crush_bucket* in, struct crush_work_bucket* work, int x, int r, const struct crush_choose_arg* arg, int position)
{
    dprintk(" crush_bucket_choose %d x=%d r=%d\n", in->id, x, r);
    BUG_ON(in->size == 0);
    switch (in->alg) {
    case CRUSH_BUCKET_UNIFORM: return bucket_uniform_choose((const struct crush_bucket_uniform*)in, work, x, r);
    case CRUSH_BUCKET_LIST: return bucket_list_choose((const struct crush_bucket_list*)in, x, r);
    case CRUSH_BUCKET_TREE: return bucket_tree_choose((const struct crush_bucket_tree*)in, x, r);
    case CRUSH_BUCKET_STRAW: return bucket_straw_choose((const struct crush_bucket_straw*)in, x, r);
    case CRUSH_BUCKET_STRAW2: return bucket_straw2_choose((const struct crush_bucket_straw2*)in, x, r, arg, position);
    default: dprintk("unknown bucket %d alg %d\n", in->id, in->alg); return in->items[0];
    }
}

......