Ceph►CRUSH

CRUSH算法实现原理详细分析

CRUSH算法实现原理详细分析

目录

  1. CRUSH算法概述
  2. 核心数据结构
  3. 哈希函数
  4. Bucket算法
  5. 映射规则（Rule）
  6. 映射执行流程
  7. 代码实现分析
  8. 性能优化

CRUSH算法概述

1.1 什么是CRUSH

CRUSH (Controlled Replication Under Scalable Hashing) 是Ceph中用于数据分布的核心算法。它是一个伪随机数据分布算法，能够高效地将输入值（通常是数据对象）分布到异构的、结构化的存储集群中。

1.2 核心特点

  • 确定性：给定相同的输入，总是产生相同的输出
  • 伪随机性：分布看起来是随机的，但实际上是确定性的
  • 可扩展性：支持大规模集群
  • 容错性：能够处理节点故障和恢复
  • 权重支持：根据设备权重进行负载均衡

1.3 算法原理

CRUSH算法通过以下步骤将对象映射到OSD：

1
2
3
4
5
6
7
8
9
对象名 (object_name) 
    ↓
PG ID (pgid = hash(object_name) % num_pgs)
    ↓
CRUSH输入 (x = hash(pgid, pool_id))
    ↓
CRUSH规则 (rule)
    ↓
OSD列表 (osd_list)

1.4 关键概念

  • Item：CRUSH层次结构中的节点，可以是设备（OSD）或桶（Bucket）
  • Bucket：包含其他Item的容器，形成层次结构
  • Rule：定义如何从层次结构中选择Item的规则序列
  • Weight：Item的权重，用于负载均衡
  • Type：Item的类型，用于故障域隔离

核心数据结构

2.1 crush_map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct crush_map {
    struct crush_bucket **buckets;      // 桶数组
    struct crush_rule **rules;          // 规则数组
    __s32 max_buckets;                  // 最大桶数量
    __u32 max_rules;                    // 最大规则数量
    __s32 max_devices;                  // 最大设备数量
    
    // 可调参数
    __u32 choose_total_tries;           // 总重试次数
    __u32 choose_local_tries;           // 本地重试次数
    __u32 choose_local_fallback_tries;  // 本地回退重试次数
    __u32 chooseleaf_descend_once;      // chooseleaf是否只下降一次
    __u8 chooseleaf_vary_r;              // chooseleaf是否变化r值
    __u8 chooseleaf_stable;              // chooseleaf稳定模式
    
    size_t working_size;                 // 工作空间大小
};

说明：

  • buckets：存储所有桶的指针数组，桶ID为负数（-1, -2, …）
  • rules：存储所有规则的指针数组
  • max_devices：最大设备ID + 1
  • 可调参数用于控制映射行为和稳定性

2.2 crush_bucket

1
2
3
4
5
6
7
8
9
struct crush_bucket {
    __s32 id;        // 桶ID，< 0且唯一
    __u16 type;      // 桶类型，> 0，由调用者定义
    __u8 alg;        // 项目选择算法
    __u8 hash;       // 哈希函数类型
    __u32 weight;    // 16.16定点累积子项权重
    __u32 size;      // items数组大小
    __s32 *items;    // 子项数组：< 0是桶，>= 0是设备
};

说明：

  • id：桶的唯一标识符，必须为负数
  • type：桶的类型，用于规则匹配（如rack、host等）
  • alg：选择算法（uniform、list、straw2等）
  • weight：所有子项的累积权重
  • items：子项数组，负数表示桶，非负数表示设备

2.3 桶类型结构

2.3.1 Uniform Bucket

1
2
3
4
struct crush_bucket_uniform {
    struct crush_bucket h;
    __u32 item_weight;  // 每个项目的权重（所有项目相同）
};

特点：

  • 所有项目权重相同
  • 选择速度最快 O(1)
  • 添加/删除项目时数据移动较大

2.3.2 List Bucket

1
2
3
4
5
struct crush_bucket_list {
    struct crush_bucket h;
    __u32 *item_weights;  // 每个项目的权重
    __u32 *sum_weights;   // 累积权重
};

特点：

  • 支持不同权重
  • 选择速度 O(n)
  • 添加项目时数据移动最优
  • 删除项目时数据移动较大

2.3.3 Straw2 Bucket

1
2
3
4
struct crush_bucket_straw2 {
    struct crush_bucket h;
    __u32 *item_weights;  // 每个项目的权重
};

特点：

  • 支持不同权重
  • 选择速度 O(n)
  • 添加/删除/重权重时数据移动最优
  • 推荐使用的算法

2.4 crush_rule

1
2
3
4
5
6
7
8
9
10
11
struct crush_rule {
    __u32 len;                           // 步骤数量
    __u8 type;                           // 规则类型
    struct crush_rule_step steps[0];      // 步骤数组
};

struct crush_rule_step {
    __u32 op;    // 操作码
    __s32 arg1; // 参数1
    __s32 arg2; // 参数2
};

操作码类型：

  • CRUSH_RULE_TAKE：选择起始桶
  • CRUSH_RULE_CHOOSE_FIRSTN：选择N个项目（深度优先）
  • CRUSH_RULE_CHOOSE_INDEP：选择N个项目（广度优先）
  • CRUSH_RULE_CHOOSELEAF_FIRSTN：选择N个叶子（深度优先）
  • CRUSH_RULE_CHOOSELEAF_INDEP：选择N个叶子（广度优先）
  • CRUSH_RULE_EMIT：输出结果

哈希函数

3.1 哈希函数实现

CRUSH使用Robert Jenkins的哈希函数（rjenkins1），位于hash.c：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 哈希混合函数
#define crush_hashmix(a, b, c) do {			\
    a = a-b;  a = a-c;  a = a^(c>>13);	\
    b = b-c;  b = b-a;  b = b^(a<<8);	\
    c = c-a;  c = c-b;  c = c^(b>>13);	\
    a = a-b;  a = a-c;  a = a^(c>>12);	\
    b = b-c;  b = b-a;  b = b^(a<<16);	\
    c = c-a;  c = c-b;  c = c^(b>>5);	\
    a = a-b;  a = a-c;  a = a^(c>>3);	\
    b = b-c;  b = b-a;  b = b^(a<<10);	\
    c = c-a;  c = c-b;  c = c^(b>>15);	\
} while (0)

// 单参数哈希
__u32 crush_hash32_rjenkins1(__u32 a) {
    __u32 hash = crush_hash_seed ^ a;
    __u32 b = a;
    __u32 x = 231232;
    __u32 y = 1232;
    crush_hashmix(b, x, hash);
    crush_hashmix(y, a, hash);
    return hash;
}

// 多参数哈希
__u32 crush_hash32_3(int type, __u32 a, __u32 b, __u32 c);
__u32 crush_hash32_4(int type, __u32 a, __u32 b, __u32 c, __u32 d);

特点：

  • 使用混合函数确保良好的分布
  • 支持多个输入参数
  • 确定性：相同输入产生相同输出

3.2 哈希函数使用

在CRUSH映射中，哈希函数用于：

  1. 桶内项目选择：hash(x, bucket_id, r) 选择桶内项目
  2. 排列生成：hash(x, bucket_id, position) 生成排列
  3. 权重检查：hash(x, item) 检查项目是否”out”

Bucket算法

4.1 Uniform Bucket算法

实现位置：mapper.c:115-119

1
2
3
4
5
6
7
static int bucket_uniform_choose(
    const struct crush_bucket_uniform *bucket,
    struct crush_work_bucket *work, 
    int x, int r)
{
    return bucket_perm_choose(&bucket->h, work, x, r);
}

算法原理：

  1. 所有项目权重相同
  2. 使用排列选择算法
  3. 时间复杂度：O(1)（优化后）

排列选择算法（bucket_perm_choose）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
static int bucket_perm_choose(const struct crush_bucket *bucket,
                              struct crush_work_bucket *work,
                              int x, int r)
{
    unsigned int pr = r % bucket->size;
    
    // 优化：r=0的情况
    if (pr == 0) {
        s = crush_hash32_3(bucket->hash, x, bucket->id, 0) % bucket->size;
        work->perm[0] = s;
        return bucket->items[s];
    }
    
    // 生成排列
    for (i = 0; i < bucket->size; i++)
        work->perm[i] = i;
    
    // 计算排列到位置pr
    for (p = 0; p <= pr; p++) {
        i = crush_hash32_3(bucket->hash, x, bucket->id, p) % (bucket->size - p);
        if (i) {
            // 交换
            swap(work->perm[p], work->perm[p + i]);
        }
    }
    
    return bucket->items[work->perm[pr]];
}

特点：

  • 快速：O(1)平均情况
  • 均匀分布
  • 添加/删除项目时数据移动大

4.2 List Bucket算法

实现位置：mapper.c:122-145

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static int bucket_list_choose(const struct crush_bucket_list *bucket,
                             int x, int r)
{
    for (i = bucket->h.size-1; i >= 0; i--) {
        // 计算哈希值
        w = crush_hash32_4(bucket->h.hash, x, bucket->h.items[i], r, bucket->h.id);
        w &= 0xffff;
        
        // 缩放权重
        w *= bucket->sum_weights[i];
        w = w >> 16;
        
        // 检查是否选择
        if (w < bucket->item_weights[i]) {
            return bucket->h.items[i];
        }
    }
    return bucket->h.items[0];
}

算法原理：

  1. 从列表尾部（最新添加的项目）开始
  2. 对每个项目计算哈希值
  3. 根据累积权重决定是否选择该项目
  4. 如果选择，返回该项目；否则继续

特点：

  • 时间复杂度：O(n)
  • 添加项目时数据移动最优
  • 删除项目时数据移动较大

4.3 Straw2 Bucket算法

实现位置：mapper.c:342-365

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
static int bucket_straw2_choose(
    const struct crush_bucket_straw2 *bucket,
    int x, int r, 
    const struct crush_choose_arg *arg,
    int position)
{
    unsigned int i, high = 0;
    __s64 draw, high_draw = 0;
    __u32 *weights = get_choose_arg_weights(bucket, arg, position);
    __s32 *ids = get_choose_arg_ids(bucket, arg);
    
    for (i = 0; i < bucket->h.size; i++) {
        if (weights[i]) {
            // 生成指数分布随机变量
            draw = generate_exponential_distribution(
                bucket->h.hash, x, ids[i], r, weights[i]);
        } else {
            draw = S64_MIN;  // 权重为0，不选择
        }
        
        // 选择最大的draw值
        if (i == 0 || draw > high_draw) {
            high = i;
            high_draw = draw;
        }
    }
    
    return bucket->h.items[high];
}

指数分布生成（generate_exponential_distribution）：

1
2
3
4
5
6
7
8
9
10
11
12
13
static inline __s64 generate_exponential_distribution(
    int type, int x, int y, int z, int weight)
{
    // 生成随机数
    unsigned int u = crush_hash32_3(type, x, y, z);
    u &= 0xffff;
    
    // 计算自然对数（使用查找表）
    __s64 ln = crush_ln(u) - 0x1000000000000ll;
    
    // 除以权重（16.16定点）
    return div64_s64(ln, weight);
}

算法原理：

  1. 为每个项目生成一个指数分布的随机变量（”straw”长度）
  2. 权重越大，straw长度期望越大
  3. 选择straw长度最大的项目

数学原理：

  • 使用指数分布的逆变换采样
  • 如果每个OSD的请求间隔服从指数分布，则PG分布与权重成正比
  • 参考：指数分布最小值的分布

特点：

  • 时间复杂度：O(n)
  • 添加/删除/重权重时数据移动最优
  • 推荐使用

映射规则（Rule）

5.1 规则结构

规则由一系列步骤组成，每个步骤执行一个操作：

1
2
3
4
5
6
7
8
// 示例规则：三副本规则
rule replicated_rule {
    id 0
    type replicated
    step take root          // 从root桶开始
    step chooseleaf firstn 0 type host  // 从每个host选择1个OSD
    step emit              // 输出结果
}

5.2 规则步骤类型

5.2.1 TAKE

1
2
3
4
case CRUSH_RULE_TAKE:
    w[0] = curstep->arg1;  // 选择起始桶
    wsize = 1;
    break;

功能：选择规则执行的起始桶

5.2.2 CHOOSE_FIRSTN / CHOOSELEAF_FIRSTN

深度优先选择：

  • CHOOSE_FIRSTN：选择N个桶
  • CHOOSELEAF_FIRSTN：选择N个叶子（OSD）

特点：

  • 深度优先：先选择一个桶，再递归选择
  • 副本间有依赖关系
  • 适合副本存储

5.2.3 CHOOSE_INDEP / CHOOSELEAF_INDEP

广度优先选择：

  • CHOOSE_INDEP：选择N个桶
  • CHOOSELEAF_INDEP：选择N个叶子（OSD）

特点：

  • 广度优先：同时选择所有副本
  • 副本间独立
  • 适合纠删码

5.3 规则执行流程

规则执行在crush_do_rule_no_retry中实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
static int crush_do_rule_no_retry(...)
{
    // 初始化工作空间
    w[0] = ...;  // 起始桶
    wsize = 1;
    
    // 遍历规则步骤
    for (step = 0; step < rule->len; step++) {
        switch (curstep->op) {
        case CRUSH_RULE_TAKE:
            // 选择起始桶
            break;
            
        case CRUSH_RULE_CHOOSELEAF_FIRSTN:
        case CRUSH_RULE_CHOOSE_FIRSTN:
            // 深度优先选择
            osize += crush_choose_firstn(...);
            break;
            
        case CRUSH_RULE_CHOOSELEAF_INDEP:
        case CRUSH_RULE_CHOOSE_INDEP:
            // 广度优先选择
            crush_choose_indep(...);
            break;
            
        case CRUSH_RULE_EMIT:
            // 输出结果
            break;
        }
    }
    
    return result_len;
}

映射执行流程

6.1 整体流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
crush_do_rule()
    ↓
crush_do_rule_no_retry()
    ↓
遍历规则步骤
    ↓
TAKE: 选择起始桶
    ↓
CHOOSE/CHOOSELEAF: 选择项目
    ↓
    ├─► crush_choose_firstn()  (深度优先)
    │       ↓
    │   遍历每个副本位置
    │       ↓
    │   选择桶内项目
    │       ↓
    │   crush_bucket_choose()
    │       ↓
    │   根据桶类型选择算法
    │       ├─► bucket_uniform_choose()
    │       ├─► bucket_list_choose()
    │       └─► bucket_straw2_choose()
    │
    └─► crush_choose_indep()  (广度优先)
            ↓
        同时选择所有副本
            ↓
        crush_bucket_choose()
            ↓
        根据桶类型选择算法

6.2 crush_choose_firstn（深度优先）

实现位置：mapper.c:441-629

核心逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
static int crush_choose_firstn(...)
{
    // 对每个副本位置
    for (rep = stable ? 0 : outpos; rep < numrep && count > 0; rep++) {
        ftotal = 0;
        do {
            retry_descent = 0;
            in = bucket;  // 从起始桶开始
            
            do {
                retry_bucket = 0;
                r = rep + parent_r + ftotal;  // 计算r值
                
                // 选择桶内项目
                item = crush_bucket_choose(in, work, x, r, ...);
                
                // 检查类型
                if (itemtype != type) {
                    // 继续下降
                    in = map->buckets[-1-item];
                    retry_bucket = 1;
                    continue;
                }
                
                // 检查冲突
                if (collide) {
                    // 重试
                    retry_bucket = 1;
                }
                
                // 如果是chooseleaf，递归选择叶子
                if (recurse_to_leaf && item < 0) {
                    if (crush_choose_firstn(...) <= outpos) {
                        reject = 1;
                    }
                }
                
                // 检查是否out
                if (is_out(...)) {
                    reject = 1;
                }
                
            } while (retry_bucket);
        } while (retry_descent);
        
        // 保存结果
        out[outpos] = item;
        outpos++;
    }
    
    return outpos;
}

关键点：

  1. r值计算：r = rep + parent_r + ftotal
    • rep：副本位置
    • parent_r：父级r值
    • ftotal：总失败次数
  2. 冲突检测：检查是否与已选择的项目冲突
  3. 重试机制：
    • retry_bucket：桶内重试
    • retry_descent：下降重试
  4. out检测：检查项目是否可用（基于权重）

6.3 crush_choose_indep（广度优先）

实现位置：mapper.c:636-824

核心逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
static void crush_choose_indep(...)
{
    // 初始化所有位置为未定义
    for (rep = outpos; rep < endpos; rep++) {
        out[rep] = CRUSH_ITEM_UNDEF;
    }
    
    // 尝试选择
    for (ftotal = 0; left > 0 && ftotal < tries; ftotal++) {
        // 对每个未定义的位置
        for (rep = outpos; rep < endpos; rep++) {
            if (out[rep] != CRUSH_ITEM_UNDEF)
                continue;
            
            in = bucket;
            for (;;) {
                // 计算r值（独立于其他副本）
                r = rep + parent_r;
                if (in->alg == CRUSH_BUCKET_UNIFORM && 
                    in->size % numrep == 0) {
                    r += (numrep+1) * ftotal;
                } else {
                    r += numrep * ftotal;
                }
                
                // 选择项目
                item = crush_bucket_choose(in, work, x, r, ...);
                
                // 检查类型、冲突、out等
                // ...
                
                // 保存结果
                out[rep] = item;
                left--;
                break;
            }
        }
    }
}

关键点：

  1. 独立选择：每个副本位置独立选择
  2. r值计算：考虑副本数量和失败次数
  3. 广度优先：同时处理所有副本位置

6.4 is_out函数

实现位置：mapper.c:405-419

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static int is_out(const struct crush_map *map,
                 const __u32 *weight, int weight_max,
                 int item, int x)
{
    if (item >= weight_max)
        return 1;  // 超出范围，out
    if (weight[item] >= 0x10000)
        return 0;  // 权重>=1.0，in
    if (weight[item] == 0)
        return 1;  // 权重=0，out
    
    // 基于哈希的概率检查
    if ((crush_hash32_2(CRUSH_HASH_RJENKINS1, x, item) & 0xffff)
        < weight[item])
        return 0;  // 在概率范围内，in
    return 1;      // 超出概率范围，out
}

功能：检查项目是否”out”（不可用）

原理：

  • 权重=0：总是out
  • 权重>=1.0：总是in
  • 0<权重<1.0：基于哈希的概率检查

代码实现分析

7.1 文件结构

1
2
3
4
5
6
7
8
9
10
11
crush/
├── crush.h          # 核心数据结构定义
├── crush.c          # 数据结构管理
├── mapper.h         # 映射函数声明
├── mapper.c         # 映射算法实现（核心）
├── builder.h         # 构建函数声明
├── builder.c         # CRUSH map构建
├── hash.h            # 哈希函数声明
├── hash.c             # 哈希函数实现
├── CrushWrapper.h      # C++包装类
└── CrushWrapper.cc     # C++包装实现

7.2 关键函数调用链

7.2.1 映射调用链

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
crush_do_rule()
    ↓
crush_do_rule_no_retry()
    ↓
遍历规则步骤
    ↓
crush_choose_firstn() / crush_choose_indep()
    ↓
crush_bucket_choose()
    ↓
bucket_uniform_choose() / bucket_list_choose() / bucket_straw2_choose()
    ↓
bucket_perm_choose() / generate_exponential_distribution()
    ↓
crush_hash32_*()

7.2.2 桶选择函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// mapper.c:368-399
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)
{
    switch (in->alg) {
    case CRUSH_BUCKET_UNIFORM:
        return bucket_uniform_choose(...);
    case CRUSH_BUCKET_LIST:
        return bucket_list_choose(...);
    case CRUSH_BUCKET_STRAW2:
        return bucket_straw2_choose(...);
    default:
        return in->items[0];
    }
}

7.3 工作空间管理

工作空间结构：

1
2
3
4
5
6
7
8
9
struct crush_work {
    struct crush_work_bucket **work;  // 每个桶的工作空间
};

struct crush_work_bucket {
    __u32 perm_x;    // 排列对应的x值
    __u32 perm_n;    // 已计算的排列元素数
    __u32 *perm;     // 排列数组
};

初始化：

1
2
3
4
5
6
7
8
9
10
11
size_t crush_work_size(const struct crush_map *map, int result_max)
{
    // 计算所需工作空间大小
    // 包括：work结构 + 桶指针数组 + 每个桶的工作空间
}

void crush_init_workspace(const struct crush_map *m, void *v)
{
    // 初始化工作空间
    // 分配每个桶的工作空间
}

7.4 重试机制

重试层次：

  1. 本地重试（local_retries）：桶内重试，避免冲突
  2. 本地回退重试（local_fallback_retries）：桶内穷举搜索
  3. 下降重试（retry_descent）：重新开始下降过程
  4. 总重试（choose_total_tries）：总重试次数限制

重试逻辑（crush_choose_firstn）：

1
2
3
4
5
6
7
8
9
if (collide && flocal <= local_retries)
    retry_bucket = 1;  // 本地重试
else if (local_fallback_retries > 0 && 
         flocal <= in->size + local_fallback_retries)
    retry_bucket = 1;  // 本地回退重试
else if (ftotal < tries)
    retry_descent = 1;  // 下降重试
else
    skip_rep = 1;      // 放弃

性能优化

8.1 Uniform Bucket优化

优化点：

  1. r=0优化：直接计算第一个元素，避免完整排列
  2. 延迟排列：只在需要时计算排列元素
1
2
3
4
5
6
7
// 优化：r=0的情况
if (pr == 0) {
    s = crush_hash32_3(bucket->hash, x, bucket->id, 0) % bucket->size;
    work->perm[0] = s;
    work->perm_n = 0xffff;  // 标记
    return bucket->items[s];
}

8.2 工作空间重用

优化：

  • 工作空间可以在多次调用间重用
  • 只要CRUSH map不变，工作空间就有效
  • 减少内存分配开销

8.3 哈希函数优化

优化：

  • 使用查找表加速自然对数计算（crush_ln）
  • 内联函数减少函数调用开销
  • 位运算优化

8.4 选择算法选择

性能对比：

算法 选择速度 添加项目 删除项目 重权重
Uniform O(1) 差 差 差
List O(n) 优 差 差
Straw2 O(n) 优 优 优

建议：

  • 小规模、权重相同的桶：使用Uniform
  • 大规模、频繁变化的桶：使用Straw2
  • 只添加、不删除的场景：使用List

8.5 规则优化

优化建议：

  1. 减少规则步骤：步骤越少，执行越快
  2. 合理使用类型：利用类型快速过滤
  3. 避免过深层次：层次越深，递归开销越大

总结

核心要点

  1. CRUSH是确定性伪随机算法：相同输入总是产生相同输出
  2. 支持多种桶算法：Uniform、List、Straw2，各有优缺点
  3. 规则驱动：通过规则定义映射行为
  4. 权重支持：根据权重进行负载均衡
  5. 容错机制：通过重试处理冲突和故障

算法优势

  • 可扩展性：支持大规模集群
  • 灵活性：通过规则和权重灵活控制
  • 稳定性：Straw2算法在变化时数据移动最小
  • 性能：Uniform算法选择速度最快

应用场景

  • 副本存储：使用FIRSTN模式
  • 纠删码：使用INDEP模式
  • 故障域隔离：通过类型和规则实现
  • 负载均衡：通过权重实现

参考资料

  1. CRUSH论文：http://www.ssrc.ucsc.edu/Papers/weil-sc06.pdf
  2. Ceph源码：cephMain/src/crush/
  3. CRUSH算法文档：Ceph官方文档

文章互动

阅读 --

留言

0 条留言

正在加载留言…