CRUSH in Ceph

聊聊Ceph中的核心数据分布选择算法——CRUSH

概述

CRUSH算法构建了Ceph存储体系的核心,解决了计算效率和计算性能的同步优化,解放了元数据节点,让ceph的客户端侧完成数据目标位置的计算任务,保障了系统的可扩展性和鲁棒性。具备计算寻址、高并发能力、动态数据再平衡、可定制的副本策略等优秀特性。

CRUSH:Controlled Replication Under Scalable Hashing ,基于可扩展哈希的受控副本分布策略。CRUSH本质上是一种基于hash的数据分布式算法,主要解决两个问题:

  1. 当系统发生变化时,如何最小化数据的迁移量并尽快恢复平衡;

  2. 如何保证数据的多个副本合理分布,保证数据的可靠性;

CRUSH中的5种设备选择算法

对比项/算法 unique list tree straw staw2
时间复杂度 O(1) O(N) O(log(N)) O(N) O(N)
添加元素 最好 最好 最好
删除元素 最好 最好

以上对比可以看出,straw虽然时间复杂度高,但应对环境变化能力强,所以作为ceph的默认配置算法。

straw算法的本质是一个抽签算法,选取抽取签长最长的作为结果,同时考虑不同设备的权重,来补偿签长权重,让容量大的设备更容易被抽中。

straw抽签算法可以保证,每个设备的签长计算只与该设备的权重有关,这样当添加或删除设备时,不会导致数据在除添加/删除之外的两个元素之间迁移。

但straw算法并非完美,在算法设计的权重排序中,由于需要和其它元素的权重进行比较,从而导致每次有元素加入当前集合或从当前集合删除时,都会引起不相关的数据迁移。为此,straw2提出了改良算法。

CRUSH算法

输入:x,cluster map,placement rule

目的: 为输入PG寻找合适的OSD set

Cluster Map

cluster map也成为CRUSH map是集群拓扑结构的逻辑描述形式,采用树这种数据结构实现,比如“数据中心——机架——主机——磁盘”的树状层级关系。其中叶子节点为device,中间节点统称bucket,根节点为root,每个节点通过ID和类型描述。

cluster map中包含CRUSH MAP Devices表,用于统计所有的设备资源

1
2
#devices
device {num} {osd.name}

Bucket类型表,描述了不同的设备类型信息:

1
2
3
4
5
6
7
8
9
10
11
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 region
type 10 root
1
2
3
4
5
6
7
[bucket-type] [bucket-name] {
id [a unique negative numeric ID]
weight [the relative capacity/capability of the item(s)]
alg [the bucket type: uniform | list | tree | straw | straw2]
hash [the hash type: 0 by default]
item [item-name] weight [weight]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
host ceph-node3 {
id -4 # do not change unnecessarily
# weight 0.053
alg straw
hash 0 # rjenkins1
item osd.4 weight 0.018
item osd.5 weight 0.018
item osd.8 weight 0.018
}
root default {
id -1 # do not change unnecessarily
# weight 0.158
alg straw
hash 0 # rjenkins1
item ceph-node1 weight 0.053
item ceph-node2 weight 0.053
item ceph-node3 weight 0.053
}

Placement Rule

数据分布策略:Placement Rule,用于利用cluster map完成数据映射,包括take,select和emit三种操作。

核心是select算法,将根据需求返回指定数量的叶子设备,并保证这些叶子设备位于不同的指定类型的容灾域之下。

1
2
3
4
5
6
7
8
9
10
rule <rulename> {

ruleset <ruleset>
type [ replicated | erasure ]
min_size <min-size>
max_size <max-size>
step take <bucket-name>
step [choose|chooseleaf] [firstn|indep] <N> <bucket-type>
step emit
}

CRUSH算法的缺陷

CRUSH算法本身仍然存在缺陷,从基本选择算法上看,每次选择都是计算单个条目被选中的独立概率,但是CRUSH所要求的副本策略使得针对同一输入、多个副本之间的选择变成了计算条件概率,所以CRUSH无法处理好多副本模式下的副本均匀分布问题;

这导致了在Ceph集群中,特别是异构集群中,出现大量磁盘数据分布悬殊的情况,因此需要对其计算结果进行人工干预。除了本身的weight,人工设置一个reweight值,叫做过载测试。

CRUSH规则修改常用命令

CRUSH修改满足如下流程:

  1. Get the CRUSH map.
  2. Decompile the CRUSH map.
  3. Edit at least one of Devices, Buckets and Rules.
  4. Recompile the CRUSH map.
  5. Test it.
  6. Set the CRUSH map.
1
2
3
4
5
6
7
8
9
10
11
12
# 1.
ceph osd getcrushmap -o {compiled crush map file}
# 2.
crushtool -d {compiled crush map file} -o {decompiled crush map file}
# 3.
#4.
crushtool -c {decompiled crush map file} -o {compiled crush map file}
# 5. 模拟测试
crushtool -i mycrushmap --test --min-x - --max-x 9 --num-rep 3 --ruleset 0 --show_mappings
crushtool -i mycrushmap --test --min-x - --max-x 9 --num-rep 3 --ruleset 0 --show_utilization
# 6.
ceph osd setcrushmap -i {compiled crush map file}

定制CRUSH规则

  1. 修改容灾域(如下为以rack作为容灾域)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    # rules
    rule replicated_ruleset {
    ruleset 0
    type replicated
    min_size 1
    max_size 10
    step take default
    step chooseleaf firstn 0 type rack
    step emit
    }

2.限制只选择特定范围的OSD,比如下面只选择rack2的OSD

1
2
3
4
5
6
7
8
9
10
# rules
rule replicated_ruleset {
ruleset 0
type replicated
min_size 1
max_size 10
step take rack2
step chooseleaf firstn 0 type host
step emit
}
  1. 构建虚拟隔离池

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    host virtualhost {
    id -10 # do not change unnecessarily
    # weight 0.053
    alg straw2
    hash 0 # rjenkins1
    item osd.3 weight 0.018
    item osd.6 weight 0.018
    item osd.7 weight 0.018
    }
    # rules
    rule replicated_ruleset {
    ruleset 0
    type replicated
    min_size 1
    max_size 10
    step take virtualhost
    step chooseleaf firstn 0 type osd
    step emit
    }

数据重平衡

人为干预可以通过reweight来调节数据分布:

1
ceph osd reweight {osd_numeric_id} {reweight}

也可以批量调整,比如按照reweight-by-utilizaitonreweight-by-pg,可以调整前通过如下命令测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ceph osd test-reweight-by-utilization {overload} {max_change} {max_osds} {--no-incresing}
[root@ceph-node1 ~]# ceph osd test-reweight-by-utilization 105 .2 4 --no-increasing
no change
moved 6 / 384 (1.5625%)
avg 42.6667
stddev 5.4365 -> 4.49691 (expected baseline 6.1584)
min osd.7 with 33 -> 37 pgs (0.773438 -> 0.867188 * mean)
max osd.6 with 52 -> 48 pgs (1.21875 -> 1.125 * mean)

oload 105
max_change 0.2
max_change_osds 4
average 0.007894
overload 0.008289
osd.6 weight 1.000000 -> 0.843857
osd.4 weight 1.000000 -> 0.940109
参数 含义
overload 可选,默认值为120,为大于100的数,当且仅当OSD的空间利用与大于等于集群平均利用率的overload/100时,调整reweight
max_change [0,1],每次调整reweight的最大幅度,默认0.05
max_osds 整型,默认 4;每次至多调整的OSD数目
–no-incresing 可选,不将reweight进行上调

其它可配置信息

主OSD的选择

可以通过给OSD一个[0,1]之间的权重,来选择该OSD是否适合作为主OSD,0代表不作为主OSD,1作为可以被选为主OSD。

1
ceph osd primary-affinity <osd-id> <weight>

Tunable

1
ceph osd crush tunables optimal
  • legacy: the legacy behavior from argonaut and earlier.
  • argonaut: the legacy values supported by the original argonaut release
  • bobtail: the values supported by the bobtail release
  • firefly: the values supported by the firefly release
  • optimal: the current best values
  • default: the current default values for a new cluster

参考

  1. 《Ceph设计与实现原理》
  2. 《CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data》
  3. http://docs.ceph.com/docs/jewel/rados/operations/crush-map/

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×