ceph 的crush算法 straw

很多年以前,Sage 在写CRUSH的原始算法的时候,写了不同的Bucket类型,可以选择不同的伪随机选择算法,大部分的模型是基于RJ Honicky写的RUSH algorithms 这个算法,这个在网上可以找到资料,这里面有一个新的特性是sage很引以为豪的,straw算法,也就是我们现在常用的一些算法,这个算法有下面的特性:

  • items 可以有任意的weight
  • 选择一个项目的算法复杂度是O(n)
  • 如果一个item的weight调高或者调低,只会在调整了的item直接变动,而没有调整的item是不会变动的

O(n)找到一个数组里面最大的一个数,你要把n个变量都扫描一遍,操作次数为n,那么算法复杂度是O(n) 冒泡法的算法复杂度是O(n²)

这个过程的算法基本动机看起来像画画的颜料吸管,最长的一个将会获胜,每个item 基于weight有自己的随机straw长度

这些看上去都很好,但是第三个属性实际上是不成立的,这个straw 长度是基于bucket中的其他的weights来进行的一个复杂的算法的,虽然iteam的PG的计算方法是很独立的,但是一个iteam的权重变化实际上影响了其他的iteam的比例因子,这意味着一个iteam的变化可能会影响其他的iteam

这个看起来是显而易见的,但是事实上证明,8年都没有人去仔细研究底层的代码或者算法,这个影响就是用户做了一个很小的权重变化,但是看到了一个很大的数据变动过程,sage 在做的时候写过一个很好的测试,来验证了第三个属性是真的,但是当时的测试只用了几个比较少的组合,如果大量测试是会发现这个问题的

sage注意到这个问题也是很多人抱怨在迁移的数据超过了预期的数据,但是这个很难量化和验证,所以被忽视了很久

无论如何,这是个坏消息

好消息是,sage找到了如何解决分布算法来的实现这三个属性,新的算法被称为 ‘straw2’,下面是不同的算法 straw的算法

max_x = -1
max_item = -1
for each item:
    x = random value from 0..65535
    x *= scaling factor
    if x > max_x:
       max_x = x
       max_item = item
return item

这个就有问题了scaling factor(比例因子) 是其他iteam的权重所有的,这个就意味着改变A的权重,可能会影响到B和C的权重了

新的straw2的算法是这样的

max_x = -1
max_item = -1
for each item:
   x = random value from 0..65535
   x = ln(x / 65536) / weight
   if x > max_x:
      max_x = x
      max_item = item
return item

可以看到这个是一个weight的简单的函数,这个意味着改变一个item的权重不会影响到其他的项目

sage发现问题的一半,然后 sam根据这个算法解决了问题

计算ln()函数有点讨厌,因为这个是一个浮点功能,CRUSH是定点运算(整数型),当前的实施方法是128KB的查找表,在做一个小的单元测试的时候比straw慢了25%,单这个可能跟一些缓存和输入也有关系

以上是2014年sage在开发者邮件列表里面提出来的,相信到现在为止straw2的算法已经改进了很多,目前默认的还是straw算法,内核在kernel4.1以后才支持的这个属性的

那么我们在0.9x中来看下这个属性,来从实际环境中看下具体有什么区别

实践过程

基础的环境为这个,我的机器为8个osd的单机节点,通过修改crush模拟成如上图所示的环境,设置的pg数目为800,保证每个osd上的pg为100左右,这个增加pg的数目,来扩大测试的样本

straw2和straw的区别在于,straw算法改变一个bucket的权重的时候,因为内部算法的问题,造成了其他机器的item的计算因子也会变化,就会出现其他没修改权重的bucket也会出现pg的相互间的流动,这个跟设计之初的想法是不一致的,造成的后果就是,在增加或者减少存储节点的时候,如果集群比较大,数据比较多,就会造成很大的无关数据的迁移,这个就是上面提到的问题

为了解决这个问题就新加入了算法straw2,这个算法保证在bucket的crush权重发生变化的时候,只会在变化的bucket有数据流入或者流出,不会出现其他bucket间的数据流动,减少数据的迁移量,下面的测试将会直观的看到这种变化

一、环境配置

调整tunables 为 hammer,这个里面才支持crush v4(straw2)属性

root@lab8107:~/ceph/crush# ceph osd crush tunables hammer
adjusted tunables profile to hammer
root@lab8107:~/ceph/crush# ceph osd crush set-tunable straw_calc_version 1
adjusted tunable straw_calc_version to 1

设置完了检查这两个个属性,如果是straw_calc_version 0的时候profile会显示unknow

root@lab8107:~/ceph/crush# ceph osd crush dump|egrep "allowed_bucket_algs|profile"
        "allowed_bucket_algs": 54,
        "profile": "hammer",
root@lab8107:~/ceph/crush# ceph osd crush dump|grep alg
            "alg": "straw",
            "alg": "straw",
            "alg": "straw",
            "alg": "straw",
            "alg": "straw",
            "alg": "straw",

设置完了后并不能马上生效的,这个是为了防止集群大的变动,可以用这个触发,或者等待下次crush发生变动的时候会自动触发

ceph osd crush reweight-all

二、先来测试straw

开始第一步测试,将osd.7从集群中crush改为0,那么变动的就是host4的crush,那么我们来看下数据的变化 首先需要记录原始的pg分布

root@lab8107:~ ceph pg dump pgs|awk '{print $1,$15}' > oringin
root@lab8107:~/ceph/crush# ceph osd crush reweight osd.7 0
reweighted item id 7 name 'osd.7' to 0 in crush map
root@lab8107:~ceph pg dump pgs|awk '{print $1,$15}' > rewei70

现在比较oringin 和rewei70 的变化

diff oringin rewei70 -y -W 30 --suppress-common-lines

查看非调整节点的数据流动

0.3d [2]      | 0.3d [5]
0.316 [2]     | 0.316 [5]
0.26c [5]     | 0.26c [1]
0.241 [2]     | 0.241 [0]
0.235 [5]     | 0.235 [2]
0.128 [0]     | 0.128 [3]

再来一次将osd.6的crush weight弄成0

ceph osd crush reweight osd.6 0

再次查看变化

0.cb [4]      | 0.cb [2]
0.30b [4]     | 0.30b [2]
0.2e9 [1]     | 0.2e9 [4]
0.2d8 [3]     | 0.2d8 [1]
0.28e [3]     | 0.28e [4]
0.286 [1]     | 0.286 [4]
0.1f7 [3]     | 0.1f7 [1]
0.1b6 [1]     | 0.1b6 [4]
0.163 [0]     | 0.163 [3]
0.14f [2]     | 0.14f [4]
0.10a [0]     | 0.10a [3]

上面的两组就是在一个bucket的里面的出现单点和整个bucket的crush weight减少的时候触发的其他节点的数据变动

三、现在把环境恢复后再来测试straw2

修改crush map 里面的bucket的alg

root@lab8107:~/ceph/crush# ceph osd getcrushmap -o crushmap.txt
got crush map from osdmap epoch 390
root@lab8107:~/ceph/crush# crushtool -d crushmap.txt -o crushmap-decompile
root@lab8107:~/ceph/crush# vim crushmap-decompile
将文件里面的所有straw修改成straw2
root@lab8107:~/ceph/crush# crushtool -c crushmap-decompile  -o crushmap-compile
root@lab8107:~/ceph/crush# ceph osd setcrushmap -i crushmap-compile

如果出现报错就把crushmap里面的straw2_calc_version改成straw_calc_version

并且设置算法(最关键的一步,否则即使设置straw2也不生效)

ceph osd crush set-tunable straw_calc_version 2

查询当前的crush算法

root@lab8107:~/ceph/crush# ceph osd crush dump|grep alg
            "alg": "straw2",
            "alg": "straw2",
            "alg": "straw2",
            "alg": "straw2",
            "alg": "straw2",
            "alg": "straw2",
        "allowed_bucket_algs": 54,

做一次重新内部算法

ceph osd crush reweight-all

可以重复上面的测试了

获取当前的pg分布

[root@lab8106 pgf]# ceph pg dump pgs|awk '{print $1,$15}' > oringin
root@lab8107:~/ceph/crush# ceph osd crush reweight osd.7 0
[root@lab8106 pgf]# ceph pg dump pgs|awk '{print $1,$15}' > rewei70

比较调整前后

diff oringin rewei70  -y -W 30 --suppress-common-lines|less

再次调整osd.6

ceph osd crush reweight osd.6 0
ceph pg dump pgs|awk '{print $1,$15}' > rewei60

已经没有非调整bucket的pg在节点间的变化了

四、简短的做个总结就是

straw算法里面添加节点或者减少节点,其他服务器上的osd之间会有pg的流动 straw2算法里面添加节点或者减少节点,只会pg从变化的节点移出或者从其他点移入,其他节点间没有数据流动

设置方法

ceph osd crush tunables hammer
ceph osd crush set-tunable straw_calc_version 2

开始设置好了 新创建的默认就是会straw2就会省去修改crushmap的操作

注意librados是服务端支持,客户端就支持,涉及到内核客户端的,就需要内核版本的支持,内核从4.1开始支持,也就是cephfs和rbd的块设备方式需要内核4.1及以上支持,openstack对接的是librados可以默认支持,其他的也都默认可以支持的

相关链接

https://en.wikipedia.org/wiki/Exponential_distribution#Distribution_of_the_minimum_of_exponential_random_variables

原文发布于微信公众号 - 磨磨谈(momotan1987)

原文发表时间:2017-01-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏书山有路勤为径

Tensorflow训练网络出现了loss = NAN解决方案

注:内容来源与网络 最近用Tensorflow训练网络,在增加层数和节点之后,出现loss = NAN的情况,在网上搜寻了很多答案,最终解决了问题,在这里汇总...

20610
来自专栏机器之心

教程 | TensorFlow 官方解读:如何在多系统和网络拓扑中构建高性能模型

选自Tensorflow 机器之心编译 参与:黄玉胜、黄小天 这个文档和附带的脚本详细介绍了如何构建针对各种系统和网络拓扑的高性能可拓展模型。这个技术在本文档中...

393110
来自专栏AIUAI

GPU 显存 - Caffe 内存优化

58060
来自专栏深度学习思考者

Caffe for windows 训练minst和cifar-10

前言 今天刚看了看Theano,本来打算试着改改,再深入学习学习(这就是所谓的深度学习啊,亲们!哈哈)。由于扣扣好友在训练CIFAR-10数据集,所以就在昨天配...

27560
来自专栏专知

【干货】快速上手图像识别:用TensorFlow API实现图像分类实例

【导读】1月17日,Arduino社区的编辑SAGAR SHARMA发布一篇基于TensorFlow API的图像识别实例教程。作者通过TensorFlow A...

94570
来自专栏机器之心

资源 | TensorFlow极简教程:创建、保存和恢复机器学习模型

选自Github 机器之心编译 参与:Jane W、李泽南 TensorFlow 是一个由谷歌发布的机器学习框架,在这篇文章中,我们将阐述 TensorFlow...

28470
来自专栏人工智能LeadAI

逻辑回归 | TensorFlow深度学习笔记

课程目标:学习简单的数据展示,训练一个Logistics Classifier,熟悉以后要使用的数据 Install Ipython NoteBook 可以参考...

33170
来自专栏人工智能LeadAI

TensorFlow分布式全套(原理,部署,实例)

TF的实现分为了单机实现和分布式实现,在分布式实现中,需要实现的是对client,master,worker process不在同一台机器上时的支持。数据量很大...

1.1K60
来自专栏机器学习算法工程师

应用TF-Slim快速实现迁移学习

作者:张旭 编辑:张欢 这是一篇以实践为主的入门文章,目的在于用尽量少的成本组织起来一套可以训练和测试自己的分类任务的代码,其中就会用到迁移学习,TF-Sli...

61360
来自专栏PPV课数据科学社区

手把手教你用1行代码实现人脸识别 -- Python Face_recognition

环境要求: Ubuntu17.10 Python 2.7.14 环境搭建: 1. 安装 Ubuntu17.10 > 安装步骤在这里 2. 安装 Python2....

45280

扫码关注云+社区

领取腾讯云代金券