02月21, 2017

ceph分片算法crush简单介绍

ceph做为Openstack后端的共享存储,可以让虚拟机实现“热迁移”,“快速扩容”等功能,下面简单说下ceph的分片算法crush。

一个典型的ceph集群如下: alt

  • client从monitor拉取集群的拓扑信息(clustermap)及相应的分片规则(crush_rule)。请求过程中,客户端哈希计算出对象的所在的分片,并可直接算出该分片所对应的几个设备副本(replica set)。
  • 从 (集群拓扑,分片规则,对象所在分片) -> (设备i1,设备i2,设备i3) 的这个转换就叫做crush算法(controlled replica using scalable hash).
  • 有了crush算法,客户端根据crush算法,只需要考虑设备情况,无需考虑各个分片所对应设备的位置,大大减少了元信息。

算法特性

crush算法有这么几个特点:

  1. 设备分布模型是有层次的树状结构。如机房-机架-机器-osd。可以灵活的配置crush_rule,使replicaset分配在不同的故障域。这些机房,机架等抽象出的索引,又叫bucket
  2. 每个设备可以配权重,crush 算法可以做到使每个设备上分配的pg数依分布收敛到其权重

crush 算法涉及到这几个参数:

  • 将分片映射到设备的时间复杂度(对设备数),这决定算法是否是scalable的
  • 集群状态更改(添加或删除设备)后数据的迁移量。这个迁移量最优情况是 delta(w)/ W,即更改设备占全设备的权重比例。真正迁移的数据比例除以这个权重比例,大于等于1,用来衡量算法对设备更改的容忍性。

算法内容

映射过程

用户通过指定crush_rule递归的从设备树中寻找出对应的设备权重。过程类似于宽度优先搜索,维护一个fifo队列.主要包含三个操作

  1. take(a): 将bucket a 加入队列i
  2. select(x,n,type): 对i中的每个bucket,根据要映射的数据x, 选取n个type为t的元素并放入队列。
  3. emit:返回队列中的元素

举例

假设root为设备树的根,其下包含10个类型为rac的bucket,每个rac下面包含10个类型为host的bucket,每个host下面包含10个osd。从中选取3个机器作为repicaset,要求处于同一rac,不同host,则过程如下:

                                        take(root)
                                        select(1, rac)
                                        select(3, host)
                                        select(1,osd)
                                        emit()

那么用户set一条(key,object)数据的过程如下

  1. hash算出pg分片x,取出对应pool的crush规则
  2. 执行crush规则,通过不断的select(x,n,type) ,依次映射rac-->host–>osd,
  3. 最后emit退出,返回pg分片x对应的几个设备副本(repilicaset)

select过程

select过程其实做了这样的事情:

给定一个输入,x(pg分片),和一个集合(bucket),依次选出集合中的若干元素(子bucket/设备副本)。

假设第r次选取,则函数为: select(x,r,bucket) -> i(子bucket序号)。

这个select函数需要有这样的性质

  1. 输入不同的r,结果不同
  2. 分片x在子bucket的分布应依照子bucket的weight权重收敛。

select函数同时兼顾 扩展性(子bucket增多时,每次映射的计算量在增长) 和子bucket改变后的数据迁移量。也即上文所说的crush算法所关心的两点。通过select函数,我们可以在不同的故障域配置不同的select函数策略。

select策略

select有4种策略,不同的bucket可以配置不同的策略

uniform策略
  • 适用于所有bucket权重一致的情形。o(1)的计算复杂度,但在设备改变时会带来大量的数据迁移
  • 做法:select(x,r) ---> x+r * P mod m ,m 指 子bucket总数,P是一个比m大的素数。这相当于简单的取模哈希uniform策略
list策略
  • 适用于bucket只增不减的情况,o(n)的计算复杂度,设备减少时会带来的数据迁移
  • 做法:将子bucket按照加入顺序来组织成一个list,最后加入的子bucket放在最前。对每个子bucket,比较其权重占全部的比例与hash结果决定是否选择该子bucket
tree策略
straw策略

四种策略的表现如下表所示:

alt

本文链接:https://www.opsdev.cn/post/ceph-crush-simple-info.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。