cephcrush算法介绍课件

CephCRUSH算法介绍CephCRUSH算法介绍1Agenda数据分布算法的解决的问题CRUSH算法介绍Ceph数据寻址ClushmapPlacementRuleBucket随机选择算法CRUSH算法的评价Agenda数据分布算法的解决的问题2数据分布算法解决的问题数据如何分布到存储设备上数据均衡灵活应对集群伸缩存储设备的增加删除导致数据迁移量小支持大规模集群较少的元数据维护合适的计算量CRUSH算法的核心：多层迭代伪随机选择算法数据分布算法解决的问题数据如何分布到存储设备上3Ceph数据的寻址两层映射Object-->PGPG-->(OSD1,OSD2,OSD3)Ceph数据的寻址两层映射4CRUSH做什么用？PG如何分布到osd上CRHUSH(X)-->(OSD1,OSD2,OSD3)参数inputx（pgid)HierachicalClustermapPlacementrules输出一组OSDCRUSH做什么用？PG如何分布到osd上5HierarchicalClustermap层级化的Clustermapdevice基本的存储设备OSDbucket:容器，包含device和子类型item：容器的组成成员，可以是基本的device，也可以是低层的bucketbucket的类型root，region，datacenter，row，rack，host，可以自己定义bucket类型和层级关系HierarchicalClustermap层级化的C6层级化Clustermap编写hosttest1{id-2##weight6.000algstraw#随机选择的算法hash0#rjenkins1itemosd.1weight1.000itemosd.2weight1.000itemosd.3weight1.000}hosttest2{id-3##weight6.000algstraw#随机选择的算法hash0#rjenkins1itemosd.4weight1.000itemosd.5weight1.000itemosd.6weight1.000}rootdefault{id-1#bucket的id，一般为负数#weight6.000#权重，为item的权重之和algstraw#bucket类型，决定随机选择的算法hash0#rjenkins1#hash函数的类型itemtest1weight3.000#itemitemtest2weight3.000}层级化Clustermap编写hosttest1{ho7Clustermap示例缺省提供了root，datacenter，room，row，rack，host。8.12.00.82.02.12.01.31.01.0Clustermap示例缺省提供了root，datace8PlacementRulesClustermap反应了存储系统的物理结构CRUSHplacementpolicies（Placementrule）决定对象副本如何分布的规则由三个基本的操作步（step）构成PlacementRulesClustermap反应了存9基本操作步steptack(a)：选择一个bucket（一般是rootbucket）做为后续step操作的输入choose：对于上一个操作的每个item，都要做相应的操作choosefirstn{num}type{bucket-type}选择一个bucket-type类型的itemchooseleaffirstn{num}type{bucket-type}先选择bucket-type类型的item，再递归选择叶子节点的OSDNUM参数的意义If{num}==0,choosepool-num-replicasbuckets(allavailable).If{num}>0&&<pool-num-replicas,choosethatmanybuckets.If{num}<0,itmeanspool-num-replicas-{num}.firstn和indepn的分别是一个是深度优先和广度优先选择emit基本操作步steptack(a)：选择一个bucket10示例1ruleset编写rulereplicated_ruleset{ruleset0#ruleset的编号idtypereplicated#类型repliated或者erasurecodemin_size1#副本数最小值max_size10#副本数最大值steptakeroot#选择一个rootbucket，做下一步的输入stepchoosefirstn1typerow#选择一个row，同一排stepchoosefirstn3typecabinet#选择三个cabinet,三副本分别在不同的cabinetstepchoosefirstn1typeosd#在上一步输出的三个cabinet中，分别选择一个osdstepemit}示例1ruleset编写11示例1图示例1的ruleset对于的图示例1图示例1的ruleset对于的图12ruleset示例2pg主osd为ssd，从osd为hdd的rulesetrulessd-primary{ruleset5typereplicatedmin_size5max_size10steptakessd#选择ssd这个rootbucket为输入stepchooseleaffirstn1typehost#选择一个host，并递归选择叶子节点osdstepemit#输出结果steptakehdd#选择hdd这个rootbucket为输入stepchooseleaffirstn-1typehost#选择总副本数减一个host，并递归选择一个叶子节点osdstepemit#输出结果}ruleset示例2pg主osd为ssd，从osd为hdd的13Agenda数据分布算法的解决的问题CRUSH算法介绍Ceph数据寻址ClushmapPlacementRuleBucket类型和对应的随机选择算法CRUSH算法的评价Agenda数据分布算法的解决的问题14Bucket随机选择算法目标从Bucket中随机选择一个item出来根据Buckent的类型不同，对应同的随机选择算法Bucket：不同的数据结构，并有不同的c(r,x)伪随机选择函数uniformlisttreestrawBucket随机选择算法目标15UniformBuckets适用于具有相同权重的item，而且bucket很少添加删除item。它的查找速度是最快的。本质上就是定长hash算法UniformBuckets适用于具有相同权重的item，16ListBuckets链表结构，所包含的item可以具有任意的权重。具体查找方法：CRUSH从表头开始查找副本的位置，它先得到表头item的权重Wh、剩余链表中所有item的权重之和Ws，然后根据hash(x,r,item)得到一个[0~1]的值v，假如这个值v在[0~Wh/Ws)之中，则副本在表头item中，并返回表头item的id。否者继续遍历剩余的链表。链表的查找复杂度是O(n)ListBuckets链表结构，17TreeBucketsitem是决策树的叶子节点，节点的权重等于左右子树的权重之和。CRUSH从root节点开始查找副本的位置，它先得到节点的左子树的权重Wl，得到节点的权重Wn，然后根据hash(x,r,node_id)得到一个[0~1]的值v，假如这个值v在[0~Wl/Wn)中，则副本在左子树中，否者在右子树中。继续遍历节点，直到到达叶子节点。决策树的查找复杂度是O(logn)TreeBucketsitem是决策树的叶子节点，节点的权18StrawBuckets这种类型让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))。StrawBuckets这种类型让bucket所包含的所有19冲突、故障、超载处理冲突、故障、超载冲突：这个item已经在向量i中，已被选择。故障：设备发生故障，不能被选择。超载：设备使用容量超过警戒线，没有剩余空间保存数据对象选择到的item遇到三种情况(冲突，故障，超载)时，CRUSH会拒绝选择这个item，并使用r’(r’和r、出错次数、firstn参数有关)作为选择参数重新选择item冲突、故障、超载处理冲突、故障、超载20Crush算法评价多层确定性伪随机选择算法优点：输入元数据较少（clustermap，placementrule)，可以应对大规模集群数据均衡为以概率为基础的统计上的均衡，在大规模集群中可以实现数据均衡能够灵活应对集群伸缩缺点：在小规模集群中，会有一定的数据不均衡增加新设备时，导致旧设备之间也有数据的迁移，在规模稍大时，数据迁移随机无序，消耗资源不可控，所以在添加和删除节点是需要提天比较好的规划，否则可能对系统造成冲击

Crush算法评价多层确定性伪随机选择算法21为方便学习与使用课件内容，课件可以在下载后自由调整LearningIsToAchieveACertainGoalAndWorkHard,IsAProcessToOvercomeVariousDifficultiesForAGoal为方便学习与使用课件内容，课件可以在下载后自由调整22CephCRUSH算法介绍CephCRUSH算法介绍23Agenda数据分布算法的解决的问题CRUSH算法介绍Ceph数据寻址ClushmapPlacementRuleBucket随机选择算法CRUSH算法的评价Agenda数据分布算法的解决的问题24数据分布算法解决的问题数据如何分布到存储设备上数据均衡灵活应对集群伸缩存储设备的增加删除导致数据迁移量小支持大规模集群较少的元数据维护合适的计算量CRUSH算法的核心：多层迭代伪随机选择算法数据分布算法解决的问题数据如何分布到存储设备上25Ceph数据的寻址两层映射Object-->PGPG-->(OSD1,OSD2,OSD3)Ceph数据的寻址两层映射26CRUSH做什么用？PG如何分布到osd上CRHUSH(X)-->(OSD1,OSD2,OSD3)参数inputx（pgid)HierachicalClustermapPlacementrules输出一组OSDCRUSH做什么用？PG如何分布到osd上27HierarchicalClustermap层级化的Clustermapdevice基本的存储设备OSDbucket:容器，包含device和子类型item：容器的组成成员，可以是基本的device，也可以是低层的bucketbucket的类型root，region，datacenter，row，rack，host，可以自己定义bucket类型和层级关系HierarchicalClustermap层级化的C28层级化Clustermap编写hosttest1{id-2##weight6.000algstraw#随机选择的算法hash0#rjenkins1itemosd.1weight1.000itemosd.2weight1.000itemosd.3weight1.000}hosttest2{id-3##weight6.000algstraw#随机选择的算法hash0#rjenkins1itemosd.4weight1.000itemosd.5weight1.000itemosd.6weight1.000}rootdefault{id-1#bucket的id，一般为负数#weight6.000#权重，为item的权重之和algstraw#bucket类型，决定随机选择的算法hash0#rjenkins1#hash函数的类型itemtest1weight3.000#itemitemtest2weight3.000}层级化Clustermap编写hosttest1{ho29Clustermap示例缺省提供了root，datacenter，room，row，rack，host。8.12.00.82.02.12.01.31.01.0Clustermap示例缺省提供了root，datace30PlacementRulesClustermap反应了存储系统的物理结构CRUSHplacementpolicies（Placementrule）决定对象副本如何分布的规则由三个基本的操作步（step）构成PlacementRulesClustermap反应了存31基本操作步steptack(a)：选择一个bucket（一般是rootbucket）做为后续step操作的输入choose：对于上一个操作的每个item，都要做相应的操作choosefirstn{num}type{bucket-type}选择一个bucket-type类型的itemchooseleaffirstn{num}type{bucket-type}先选择bucket-type类型的item，再递归选择叶子节点的OSDNUM参数的意义If{num}==0,choosepool-num-replicasbuckets(allavailable).If{num}>0&&<pool-num-replicas,choosethatmanybuckets.If{num}<0,itmeanspool-num-replicas-{num}.firstn和indepn的分别是一个是深度优先和广度优先选择emit基本操作步steptack(a)：选择一个bucket32示例1ruleset编写rulereplicated_ruleset{ruleset0#ruleset的编号idtypereplicated#类型repliated或者erasurecodemin_size1#副本数最小值max_size10#副本数最大值steptakeroot#选择一个rootbucket，做下一步的输入stepchoosefirstn1typerow#选择一个row，同一排stepchoosefirstn3typecabinet#选择三个cabinet,三副本分别在不同的cabinetstepchoosefirstn1typeosd#在上一步输出的三个cabinet中，分别选择一个osdstepemit}示例1ruleset编写33示例1图示例1的ruleset对于的图示例1图示例1的ruleset对于的图34ruleset示例2pg主osd为ssd，从osd为hdd的rulesetrulessd-primary{ruleset5typereplicatedmin_size5max_size10steptakessd#选择ssd这个rootbucket为输入stepchooseleaffirstn1typehost#选择一个host，并递归选择叶子节点osdstepemit#输出结果steptakehdd#选择hdd这个rootbucket为输入stepchooseleaffirstn-1typehost#选择总副本数减一个host，并递归选择一个叶子节点osdstepemit#输出结果}ruleset示例2pg主osd为ssd，从osd为hdd的35Agenda数据分布算法的解决的问题CRUSH算法介绍Ceph数据寻址ClushmapPlacementRuleBucket类型和对应的随机选择算法CRUSH算法的评价Agenda数据分布算法的解决的问题36Bucket随机选择算法目标从Bucket中随机选择一个item出来根据Buckent的类型不同，对应同的随机选择算法Bucket：不同的数据结构，并有不同的c(r,x)伪随机选择函数uniformlisttreestrawBucket随机选择算法目标37UniformBuckets适用于具有相同权重的item，而且bucket很少添加删除item。它的查找速度是最快的。本质上就是定长hash算法UniformBuckets适用于具有相同权重的item，38ListBuckets链表结构，所包含的item可以具有任意的权重。具体查找方法：CRUSH从表头开始查找副本的位置，它先得到表头item的权重Wh、剩余链表中所有item的权重之和Ws，然后根据hash(x,r,item)得到一个[0~1]的值v，假如这个值v在[0~Wh/Ws)之中，则副本在表头item中，并返回表头item的id。否者继续遍历剩余的链表。链表的查找复杂度是O(n)ListBuckets链表结构，39TreeBucketsitem是决策树的叶子节点，节点的权重等于左右子树的权重之和。CRUSH从root节点开始查找副本的位置，它先得到节点的左子树的权重Wl，得到节点的权重Wn，然后根据hash(x,r