CEPHCRUSH算法源码分析
文章比较深入的写了CRUSH算法的原理和过程.通过调试深入的介绍了CRUSH计算的过程.
读本文前,你需要对ceph的基本操作,pool和CRUSH map非常熟悉.并且较深入的读过.
分析的方法
首先,我们写了个c程序调用librados向pool中写入一个对象.然后使用 GDB(CGDB is recommended)来追踪CRUSH的运行过程.同时我们将会关注CRUSH相关的几个重要变量.以便于我们完全知道CRUSH源码是如何运行.
编译CEPH 得到函数stack 追踪过程
input && PGID PGID && OSD set
1 如何追踪
1.1 编译CEPH
首先通过源码安装CEPH,然后使用./configure.如下添加编译参数/configure CFLAGS='-g3 &O0' CXXFLAGS='-g3 &O0'
-g3 意味着会产生大量的调试信息.-O0 非常重要, 它意味着关闭编译器的优化，如果没有，使用GDB追踪程序时，大多数变量被优化,无法显示。配置后，make and sudo make install。附： -O0只适合用于实验情况，在生产环境中编译器优化是必须进行的。
1.2 得到函数stack
众所周知,CRSUSH的核心函数是 crush_do_rule(位置 crush/mapper.c line 779).
* 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 ve 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计算过程分为两部分:
1. input -& PGID
2. PGID -& OSD set.
第一部分,使用GDB来得到函数过程
通过 -g 参数来编译例子程序 gdb来参看 rados_write 然后,在添加断点b crush_do_rule前,进入GDB的接口. 在函数crush_do_rule 处停留 得到函数stack,然后使用GDB log将调试信息输出到文件中 .
下面让我们来深入的研究这个过程.
函数stack和下面的相似
#11 rados_write
#10 librados::IoCtxImpl::write
#9 librados::IoCtxImpl::operate
#8 Objecter::op_submit
#7 Objecter::_op_submit_with_budget
#6 Objecter::_op_submit
#5 Objecter::_calc_target
#4 OSDMap::pg_to_up_acting_osds
#3 OSDMap::_pg_to_up_acting_osds
#2 OSDMap::_pg_to_osds
#1 CrushWrapper::do_rule
#0 crush_do_rule
CRUSH 计算过程总结如下:
INPUT(object name & pool name) && PGID && OSD set.
本文中主要关注 计算过程
2.1 input && PGID
你可以按顺序源码.最后,通过列出转换关键过程
从input 到 pgid
Ceph_hash.h (include):
extern unsigned ceph_str_hash(int type, const char *s, unsigned len);
OSDMap.h (osd):
int ret = object_locator_to_pg(oid, loc, pg);
首先从 rados_ioctx_create, 和lookup_pool 通过pool名字得到 poolid. 把poolid封装进librados::IoCtxImpl 类型变量ctx;
然后在rados_write 对象名被封装进oid; 然后在librados::IoCtxImpl::operate, oid 和oloc(comprising poolid) 被包装成Objecter::Op * 类型变量objecter_op;
通过各种类型的封装我们到到 _calc_target 这层. 我们得到不断的oid 和poolid. 然后读取目标 pool 的信息.
(in my cluster, pool &neo& id is 29, name of object to write is &neo-obj&)vcD4NCjxwPtTaPGNvZGU+b2JqZWN0X2xvY2F0b3JfdG9fcGc8L2NvZGU+LCC12tK7tM68xsvjtNM8Y29kZT5jZXBoX3N0cl9oYXNoPC9jb2RlPiC5/s+jttTP88P719azyc6q0ru49nVpbnQzMl90IMDg0M2x5MG/LNKyvs3Kx8v5zr21xCA8Y29kZT5wczwvY29kZT4gPHN0cm9uZz4ocGxhY2VtZW50IHNlZWQpPC9zdHJvbmc+PC9wPg0KPHByZSBjbGFzcz0="brush:">
unsigned int ceph_str_hash(int type, const char *s, unsigned int len)
switch (type) {
case CEPH_STR_HASH_LINUX:
return ceph_str_hash_linux(s, len);
case CEPH_STR_HASH_RJENKINS:
return ceph_str_hash_rjenkins(s, len);
return -1;
然后得到 PGID. 以前我认为pgid 是单一变量,然而不是. PGID 是个包含 poolid 和 ps 的结构体变量.
不仅仅是一个数字,还有好多信息
// placement group id
struct pg_t
uint64_t m_
uint32_t m_
int32_t m_
pg_t() : m_pool(0), m_seed(0), m_preferred(-1) {}
pg_t(ps_t seed, uint64_t pool, int pref=-1) :
还有很多信息略
crush_do_rule 的输入参数x是什么?让我们继续风雨兼程. 然后在 _pg_to_osds 有一行 ps_t pps = pool.raw_pg_to_pps(pg); //placement ps. pps 就是 x.
PPS 如何计算? 在函数crush_hash32_2(CRUSH_HASH_RJENKINS1,ceph_stable_mod(pg.ps(), pgp_num, pgp_num_mask),pg.pool());
__u32 crush_hash32_2(int type, __u32 a, __u32 b)
switch (type) {
case CRUSH_HASH_RJENKINS1:
return crush_hash32_rjenkins1_2(a, b);
ps mod pgp_num_mask 的结果(例如 a) 和poolid(例如 b) 进行哈希. 这就是pps,也就是x
我们得到第二个过程输入参数的 x.第一阶段过程图如下图
第一阶段过程图
P.S. you can find something in PG&s name and object name.
2.2 PGID && OSD set
首先需要明白几个概念
weight VS reweight
这里,&ceph osd crush reweight& 设置了OSD的权重
这个重量为任意值（通常是磁盘的TB大小,1TB设置为1），并且控制系统尝试分配到OSD的数据量。
reweight将覆盖了weight量。这个值在0到1的范围，并强制CRUSH重新分配数据。它不改变buckets 的权重,并且是CRUSH不正常的情况下的纠正措施。（例如，如果你的OSD中的一个是在90％以上，其余为50％，可以减少权重，进行补偿。）
primary-affinity
主亲和力默认为1（即，一个OSD可以作为主OSD）。primary-affinity变化范围从0到1.其中0意味着在OSD可能用作主OSD,设置为1则可以被用作主OSD.当其&1时，CRUSH将不太可能选择该OSD作为主守护进程。
pg 和 pgp的区别
- PG = Placement Group
- PGP = Placement Group for Placement purpose
- pg_num = number of placement groups mapped to an OSD
当增加每个pool的pg_num数量时,每个PG分裂成半,但他们都保持到它们的父OSD的映射。
直到这个时候，ceph不会启动平衡策略。现在，当你增加同一池中的pgp_num值，PGs启动从父OSD迁移到其他OSD,ceph开始启动平衡策略。这是PGP如何起着重要的作用的过程。
pgp-num是在CRUSH算法中使用的参数,不是 pg-num.例如pg-num = 1024 , pgp-num = 1.所有的1024个PGs都映射到同一个OSD.当您增加PG-NUM是分裂的PG，如果增加PGP-NUM将移动PGs，即改变OSD的map。PG和PGP是很重要的概念。
void do_rule(int rule, int x, vector& out, int maxout,
const vector&__u32&& weight) const {}
在了解了这些概念后开始第二部分
PGID -& OSD set. 现在我们在 do_rule: void do_rule(int rule, int x, vector& out, int maxout, const vector&__u32&& weight)
do_rule源代码
void do_rule(int rule, int x, vector& out, int maxout,
const vector&__u32&& weight) const {
Mutex::Locker l(mapper_lock);
int rawout[maxout];
int scratch[maxout * 3];
int numrep = crush_do_rule(crush, rule, x, rawout, maxout, &weight[0], weight.size(), scratch);
if (numrep & 0)
numrep = 0;
out.resize(numrep);
for (int i=0; i
让我们看下输入参数
x 就是我们已经得到的 pps rule 就是内存中的crushrule&s number(不是 ruleid, 在我的crushrule set中, this rule&s id是 3), weight 是已经讲过的 reweight
变化范围从1 到 65536. 我们定义了 rawout[maxout] 来存储 OSD set, scratch[maxout * 3] 为计算使用. 然后我们进入了crush_do_rule.
PGID -& OSDset OUTLINE
下面要仔细研究3个函数, firstn 意味着副本存储, CRUSH 需要去选择n
个osds存储副本. indep是纠删码存储过程.我们只关注副本存储方法
crush_do_rule: 反复do crushrules crush_choose_firstn: 递归选择特定类型的桶或设备 crush_bucket_choose: 直接选择bucket的子节点
crush_do_rule
首先这是我的crushrule 和集群的层次结构
@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 ve 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)
值得说的变量emit 通常用在规则的结束,同时可以被用在在形相同规则下选择不同的树。
scratch[3 * result_max]
int *b = scratch + result_
int *c = scratch + result_max*2;
a, b, c 分别指向 scratch向量的0, 1/3, 2/3的位置.
- w被用作一个先入先出队列来在CRUSH map中进行横向优先搜索(BFS traversal).
- o存储crush_choose_firstn选择的结果.
- c存储最终的OSD选择结果.
crush_choose_firstn计算后如果结果不是OSD类型, o 交给w.以便于 w成为下次crush_choose_firstn的输入参数. 如上所述, crush_do_rule 反复进行 crushrules 迭代. 你可以在内存中发现规则:
step 1 put root rgw1 in w(enqueue);
step 2 would run crush_choose_firstn to choose 1 rack-type bucket from root rgw1
下面分析crush_choose_firstn过程
crush_choose_firstn 函数
这个函数递归的选择特定bucket或者设备,并且可以处理冲突,失败的情况.
如果当前是choose过程,通过调用crush_bucket_choose来直接选择.
如果当前是chooseleaf选择叶子节点的过程,该函数将递归直到得到叶子节点.
crush_bucket_choose 函数
crush_bucket_choose是CRUSH最重要的函数.应为默认的bucket类型是straw,常见的情况下我们会使用straw类型bucket,然后就会进入bucket_straw_choose
case进行跳转
case CRUSH_BUCKET_STRAW:
return bucket_straw_choose((struct crush_bucket_straw *)in,
static int crush_bucket_choose(struct crush_bucket *in, int x, int r)
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((struct crush_bucket_uniform *)in,
case CRUSH_BUCKET_LIST:
return bucket_list_choose((struct crush_bucket_list *)in,
case CRUSH_BUCKET_TREE:
return bucket_tree_choose((struct crush_bucket_tree *)in,
case CRUSH_BUCKET_STRAW:
return bucket_straw_choose((struct crush_bucket_straw *)in,
case CRUSH_BUCKET_STRAW2:
return bucket_straw2_choose((struct crush_bucket_straw2 *)in,
dprintk(&unknown bucket %d alg %d\n&, in-&id, in-&alg);
return in-&items[0];
/* straw */
static int bucket_straw_choose(struct crush_bucket_straw *bucket,
int x, int r)
int high = 0;
__u64 high_draw = 0;
for (i = 0; i & bucket-&h. i++) {
draw = crush_hash32_3(bucket-&h.hash, x, bucket-&h.items[i], r);
draw *= bucket-&straws[i];
if (i == 0 || draw & high_draw) {
high_draw =
return bucket-&h.items[high];
bucket结构体
struct crush_bucket_straw {
struct crush_
__u32 *item_
/* 16-bit fixed point */
/* 16-bit fixed point */
可以看到 bucket root rgw1&s id是 -1, type = 10 意味着根节点 alg = 4 意味着 straw 类型. 这里 weight 是 OSD权重 we set scales up by 65536(i.e. 37 * 65536 = 2424832). 然后看下循环 T: 对每个输入的son bucket , 例如升上图rack1, crush_hash32_3 hashes x,bucket id(rack1&s id), r(current selection&s order number), 这3个变量是a uint32_t 类型变量, 结果 & 0xffff, 然后乘straw(rack1&s straw value, straw calculation seen below), 最后得到这个值, 在一次循环中, for one son bucket(rack1 here). 我们在循环中计算每个 son bucket然后选择最大的 . 然后一个son bucket 被选择 . Nice job! 下面是个计算的例子
调用层次,图表描述
我们已经研究了CRUSH计算中的重要部分,其余的部分就是迭代和递归,直到选择了所有的OSD.
关于 straw 值
详细的代码在 src/crush/builder.c crush_calc_straw.
总之,straw 值总是和OSD权重正相关.straw2正在开发.
(window.slotbydup=window.slotbydup || []).push({
id: '2467140',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467141',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467143',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467148',
container: s,
size: '1000,90',
display: 'inlay-fix'Ceph（28）
Ceph使用Bucket将系统的存储资源按照层级结构组织完成两个目标：映射算法的高效性和可扩展性，以及当集群状态发生变化时（比如设备的增加或者删除）数据的迁移量要尽可能的少。CRUSH定义了四种bucket类型（Uniform Bucket、List Bucket、Tree Bucket、Straw Bucket）来表示层级结构的中间节点，叶子节点就是对应的OSD。每一种类型的bucket使用不同的数据结构来组织它包含的内容，可以是其他Bucket或者OSD，它们是在性能和效率间的折中。接下来将详细介绍一下这四种Bucket。
1 Uniform Bucket
这种bucket有一个严格的要求，bucket中所有的item都是同构的，如有相同的性能，相同大小的容量，而其余三种bucket允许包含不同权重的设备。这个主要是考虑到设备不会一个一个添加到系统里，而是批量添加的。它根据hash函数c(r,x)=(hash(x) + rp) mod m进行映射，映射的时间复杂度是O（1），所以它的查询速度是最快的。当然它也有明显的不足，当添加或删除item时，会导致大量的数据迁移。这是因为它的计算方法和bucket大小有关系，所以当bucket发生变化时所有的计算结果都会发生变化，也就是会有数据迁移。
2 List Bucket
它的结构是链表结构，所包含的item可以具有任意的权重。CRUSH从表头开始查找副本位置，它先得到表头item的权重Wh，然后和剩余所有节点权重之和Wr做比较，然后根据hash（x, r, item）得到一个［0～1］值v，如果v在［0～Wh/Wr］，则副本在表头item中，并返回item的id，否则继续遍历剩余的链表。这个方法是从RUSHp算法中演变过来的，将数据分布问题转变为“most recently added item， or older items”。这种方法对于总是有新节点加入的情况很有好处，但当有节点从中间或者尾部删除时，就会带来一些数据迁移。这也和它的计算方法有关系，如果从尾部删除一个节点后，Wr的值回发生变化，所以ratio的值也会发生变化。使用这种bucket会使得数据要么存储在新加入的节点上，要么就还保留在原来老的地方。
List Bucket的查找复杂度为O（n），所以只适用于规模比较小的集群。
3 Tree Bucket
该方法是从RUSHt演化过来的，主要是为了解决规模比较大的环境，查找复杂度为O（logn）。Tree buckets中的元素被组织成一个加权的二叉查找树，所有的项都位于叶子节点。每一个内部节点都知道他左右子树的权重，并且按照固定的策略打上标签。
当需要从bucket众选出一项时，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，也不等于节点的权重)。
二叉树的节点的标签方法使用的是一个简单固定的方法以避免树中有节点增加或者节点减少而导致其他节点标签的变化。这个规则很简单：
1）树中最左侧的叶子节点永远是1
2）每次树增长的时候都会产生一个的新的根节点，之前的根节点会变成新根节点的左孩子。新的根节点的标签等于老的根节点的标签向左移一位（1，10，100，etc）。树的右侧的标签会复制左侧节点的标签并在最左侧在加上一个1。
tree bucket在查询性能上相比于list要好，而且数据迁移的控制也比较好。当一个节点发生变化时，只会导致节点所在子树上发生数据迁移。
4 Straw Bucket
这种类型让Bucket所包含的所有item公平的竞争(不像list和tree一样需要遍历)。这种算法就像抽签一样，所有的item都有机会被抽中(只有最长的签才能被抽中)。每个签的长度是由f(Wi)*hash(x, r, i) 决定的，Wi是item i的权重，i是item的id号。c(r, x) = MAX(f(Wi) * hash(x, r, i))。目前，这种Bucket是Ceph默认使用的Bucket，所以它也是经过大规模测试的，稳定性较好。虽然它的查询性能不如List和Tree，但它在控制数据迁移方面是最优的。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：28327次
积分：1016
积分：1016
排名：千里之外
原创：75篇
(3)(1)(4)(5)(4)(3)(3)(1)(2)(1)(15)(9)(6)(11)(3)(4)(1)(1)(4)(2)(1)ceph的crush算法究竟是怎么样的 ?
没看明白这个算法是如何计算的。。。 如果网络结构是静态的，还好办，如果是动态的，那么同样的object岂不是会映射到不同的 地方去 ？？
按投票排序
从应用的角度来看，Ceph中一个Object存储Ceph管理的磁盘的流程如下：obj --
(简单Hash算法)
(CRUSH算法)
OSD Set其中，OSD Set可以理解为是处于容错域下的一组OSD(管理进程 + 存储介质)。所以，CRUSH算法解决的最重要的问题就是给一个PG找到一个OSD set，即为同一个数据对象找到最合适的停靠点，这也是目前分布式存储系统解决的最重要的一个问题。Ceph在实现的时候因为有个中间的PG层，PG是不变的，当网络结构变化或者机器有增减的时候，用户是感知不到的， 只不过PG与OSD Set的对应关系发生了改变，这会导致在后台进行相应的数据迁移工作。
当存储节点增加后，需要对数据进行迁移，根据不同的bucket数据的迁移量也有不同。比如uniform bucket，本质上是取模，需要将数据重新分布；如果是list bucket，则数据只需要从老的机器上迁移到新新机器上，算法保证迁移的数据量是最优的。
同一个object分段后确实会尽量均匀分布到多个osd，这样带来了高可靠性和高读写性能
已有帐号？
无法登录？
社交帐号登录Ceph是一套高性能，易扩展的，无单点的分布式文件存储系统，基于Sage A. Weil的论文开发，主要提供以下三个存储服务：对象存储(Object Storage)，既可以通过使用Ceph的库，利用C, C++, Java, Python, PHP代码，也可以通过Restful网关以对象的形式访问或存储数据，兼容亚马逊的S3和OpenStack的Swift。块存储(Block Storage)，作为块设备像硬盘一样直接挂载。文件系统(File System) ，如同网络文件系统一样挂载，兼容POSIX接口。Ceph的结构，对象存储由LIBRADOS和RADOSGW提供，块存储由RBD提供，文件系统由CEPH FS提供，而RADOSGW, RBD, CEPH FS均需要调用LIBRADOS的接口，而最终都是以对象的形式存储于RADOS里。Ceph集群的节点有三种角色：Monitor，监控集群的健康状况，向客户端发送最新的CRUSH map(含有当前网络的拓扑结构)OSD，维护节点上的对象，响应客户端请求，与其他OSD节点同步MDS，提供文件的Metadata，如果不使用CephFS可以不安装Ceph是分布式的存储，它将文件分割后均匀随机地分散在各个节点上，Ceph采用了CRUSH算法来确定对象的存储位置，只要有当前集群的拓扑结构，Ceph客户端就能直接计算出文件的存储位置，直接跟OSD节点通信获取文件而不需要询问中心节点获得文件位置，这样就避免了单点风险。更多Ceph架构方面的内容可以参看官方介绍：Ceph目前已经是一套比较成熟的存储系统了，是OpenStack比较理想的存储后端，也可以作为Hadoop的存储后端，这就涉及到与Swift和HDFS的比较。Ceph与SwiftCeph用C++编写而Swift用Python编写，性能上应当是Ceph占优。但是与Ceph不同，Swift专注于对象存储，作为OpenStack组件之一经过大量生产实践的验证，与OpenStack结合很好，目前不少人使用Ceph为OpenStack提供块存储，但仍旧使用Swift提供对象存储。Swift的开发者曾写过文章对比Ceph和Swift: Ceph与HDFSCeph对比HDFS优势在于易扩展，无单点。HDFS是专门为Hadoop这样的云计算而生，在离线批量处理大数据上有先天的优势，而Ceph是一个通用的实时存储系统。虽然Hadoop可以利用Ceph作为存储后端（根据Ceph官方的教程死活整合不了，自己写了个简洁的步骤:），但执行计算任务上性能还是略逊于HDFS（时间上慢30%左右 ）。
已有帐号？
无法登录？
社交帐号登录
程序员，假装在硅谷。