cephcrush算法介绍课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,Ceph CRUSH算法介绍,Agenda,数据分布算法的解决的问题,CRUSH算法介绍,Ceph数据寻址,Clush map,Placement Rule,Bucket随机选择算法,CRUSH算法的评价,数据分布算法解决的问题,数据如何分布到存储设备上,数据均衡,灵活应对集群伸缩,存储设备的增加删除导致数据迁移量小,支持大规模集群,较少的元数据维护,合适的计算量,CRUSH算法的核心：多层迭代伪随机选择算法,Ceph 数据的寻址,两层映射,Object-PG,PG-(OSD1,OSD2,OSD3),CRUSH做什么用？,PG如何分布到osd上,CRHUSH(X)-(OSD1,OSD2,OSD3),参数,input x （pg id),Hierachical Cluster map,Placement rules,输出一组OSD,Hierarchical Cluster map,层级化的Cluster map,device 基本的存储设备 OSD,bucket:容器，包含device 和 子类型,item：容器的组成成员，可以是基本的device，也可以是低层的bucket,bucket的类型,root，region，datacenter，row，rack，host，,可以自己定义bucket类型和层级关系,层级化Cluster map编写,host test1,id-2#,#weight 6.000,alg straw,#随机选择的算法,hash 0#rjenkins1,item osd.1 weight 1.000,item osd.2 weight 1.000,item osd.3 weight 1.000,host test2,id-3#,#weight 6.000,alg straw,#随机选择的算法,hash 0#rjenkins1,item osd.4 weight 1.000,item osd.5 weight 1.000,item osd.6 weight 1.000,root default,id-1,#bucket的id，一般为负数,#weight 6.000,#权重，为item的权重之和,alg straw,#bucket类型，决定随机选择的算法,hash 0#rjenkins1,#hash函数的类型,item test1 weight 3.000,#item,item test2 weight 3.000,Cluster map 示例,缺省提供了,root,，,datacenter,，,room,，,row,，,rack,，,host,。,8.1,2.0,0.8,2.0,2.1,2.0,1.3,1.0,1.0,Placement Rules,Cluster map,反应了存储系统的物理结构,CRUSH placement policies（Placement rule）,决定对象副本,如何,分布,的规则,由三个基本的操作步（step）构成,基本操作步step,tack(a)：选择一个bucket（一般是root bucket）做为后续step操作的输入,choose：对于上一个操作的每个item，都要做相应的操作,choose firstn num type bucket-type,选择一个bucket-type类型的item,chooseleaf firstn num type bucket-type,先选择bucket-type类型的item，再递归选择叶子节点的OSD,NUM参数的意义,If num=0,choose pool-num-replicas buckets(all available).,If num 0&pool-num-replicas,choose that many buckets.,If num 0,it means pool-num-replicas-num.,firstn 和 indepn的分别是一个是深度优先和广度优先选择,emit,示例1 ruleset编写,rule replicated_ruleset,ruleset 0,#ruleset的 编号id,type replicated,#类型 repliated 或者erasure code,min_size 1,#副本数最小值,max_size 10,#副本数最大值,step take root,#选择一个root bucket，做下一步的输入,step choose firstn 1 type row,#选择一个row，同一排,step choose firstn 3 type cabinet,#选择三个cabinet,三副本分别在不同的cabinet,step choose firstn 1 type osd,#在上一步输出的三个cabinet中，分别选择一个osd,step emit,示例1 图,示例1的ruleset对于的图,ruleset示例2,pg主osd为ssd，从osd为hdd的ruleset,rule ssd-primary,ruleset 5,type replicated,min_size 5,max_size 10,step take ssd,#选择ssd 这个root bucket为输入,step chooseleaf firstn 1 type host,#选择一个host，并递归选择叶子节点osd,step emit,#输出结果,step take hdd,#选择hdd 这个root bucket为输入,step chooseleaf firstn-1 type host,#选择总副本数减一个host，并递归选择一个叶子节点osd,step emit,#输出结果,Agenda,数据分布算法的解决的问题,CRUSH算法介绍,Ceph数据寻址,Clush map,Placement Rule,Bucket类型和对应的随机选择算法,CRUSH算法的评价,Bucket随机选择算法,目标,从Bucket中随机选择一个item出来,根据Buckent的类型不同，对应同的随机选择算法,Bucket：,不同的数据结构，并有不同的,c(r,x),伪随机选择函数,uniform,list,tree,straw,Uniform Buckets,适用于具有相同权重的item，而且bucket很少添加删除item。,它的查找速度是最快的。,本质上就是定长hash算法,List Buckets,链表结构，,所包含的item可以具有任意的权重。,具体查找方法：,CRUSH从表头开始查找副本的位置，它先得到表头item的权重Wh、剩余链表中所有 item的权重之和Ws，,然后根据hash(x,r,item)得到一个01的值v，假如这个值v在0Wh/Ws)之中，则副本在表头item中，并返回表头item的id。,否者继续遍历剩余的链 表。,链表的查找复杂度是O(n),Tree Buckets,item,是决策树的叶子节点，节点的权重等于左右子树的权重之和。,CRUSH,从,root,节点开始查找副本 的位置，它先得到节点的左子树的权重,Wl,，得到节点的权重,Wn,，然后根据,hash(x,r,node_id),得到一个,01,的值,v,，假如这个值,v,在,0Wl/Wn),中，则副本在左子树中，否者在右子树中。继续遍历节点，直到到达叶子节点。,决策树的查找复杂度是,O(log n),Straw Buckets,这种类型让,bucket,所包含的所有,item,公平的竞争,(,不像,list,和,tree,一样需要遍历,),。这种算法就像抽签一样，所有的,item,都有机会被抽中,(,只有最长的签才能被抽中,),。,每个签的长度是由,length=f(Wi)*hash(x,r,i),决定的，,f(Wi),和,item,的权重有关，,i,是,item,的,id,号。,c(r,x)=MAXi(f(Wi)*hash(x,r,i),。,冲突、故障、超载处理,冲突、故障、超载,冲突：这个,item,已经在向量,i,中，已被选择。,故障：设备发生故障，不能被选择。,超载：设备使用容量超过警戒线，没有剩余空间保存数据对象,选择到的,item,遇到三种情况,(,冲突，故障，超载,),时，,CRUSH,会拒绝选择这个,item,，并使用,r(r,和,r,、出错次数、,firstn,参数有关,),作为选择参数重新选择,item,Crush 算法评价,多层确定性伪随机选择算法,优点：,输入元数据较少（cluster map，placement rule)，可以应对大规模集群,数据均衡为以概率为基础的统计上的均衡，在大规模集群中可以实现数据均衡,能够灵活应对集群伸缩,缺点：,在小规模集群中，会有一定的数据不均衡,增加新设备时，导致旧设备之间也有数据的迁移，在规模稍大时，数据迁移随机无序，消耗资源不可控，所以在添加和删除节点是需要提天比较好的规划，否则可能对系统造成冲击,为方便学习与使用课件内容，课件可以在下载后自由调整,Learning Is To Achieve A Certain Goal And Work Hard,Is A Process To Overcome Various Difficulties For A Goal,