1、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)参数
2、input x （pg id)Hierachical Cluster map Placement rules 输出一组OSD Hierarchical Cluster map 层级化的Cluster mapdevice 基本的存储设备 OSDbucket:容器，包含device 和 子类型item：容器的组成成员，可以是基本的device，也可以是低层的bucket bucket的类型root，region，datacenter，row，rack，host，可以自己定义bucket类型和层级关系 层级化Cluster map编写host test1 id-2#weight 6.000 alg
3、straw#随机选择的算法 hash 0#rjenkins1 item osd.1 weight 1.000 item osd.2 weight 1.000 item osd.3 weight 1.000host 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.000root default id-1#bucket的id，一般为负数#weight 6.000#权重，为item的权重之和 al
4、g 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.12.00.82.02.12.01.31.01.0Placement Rules Cluster map反应了存储系统的物理结构 CRUSH placement policies（Placement rule）决定对象副本如何分布的规则 由三个基本的操作步（step）构成基
5、本操作步steptack(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-nu
6、m-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 step choose firstn 1 type row#
7、选择一个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的rulesetrule ssd-primary ruleset 5 type replicated min_size 5 max_size 10 step take ssd#选择ssd 这个root bucke
8、t为输入 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随机选择算法 目
9、标 从Bucket中随机选择一个item出来 根据Buckent的类型不同，对应同的随机选择算法 Bucket：不同的数据结构，并有不同的c(r,x)伪随机选择函数 uniform list tree strawUniform Buckets 适用于具有相同权重的item，而且bucket很少添加删除item。它的查找速度是最快的。本质上就是定长hash算法List Buckets 链表结构，所包含的item可以具有任意的权重。具体查找方法：CRUSH从表头开始查找副本的位置，它先得到表头item的权重Wh、剩余链表中所有 item的权重之和Ws，然后根据hash(x,r,item)得到一个0
10、1的值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公
11、平的竞争(不像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、出错次数、f
12、irstn参数有关)作为选择参数重新选择itemCrush 算法评价 多层确定性伪随机选择算法 优点：输入元数据较少（cluster map，placement rule)，可以应对大规模集群 数据均衡为以概率为基础的统计上的均衡，在大规模集群中可以实现数据均衡 能够灵活应对集群伸缩缺点：在小规模集群中，会有一定的数据不均衡 增加新设备时，导致旧设备之间也有数据的迁移，在规模稍大时，数据迁移随机无序，消耗资源不可控，所以在添加和删除节点是需要提天比较好的规划，否则可能对系统造成冲击 为方便学习与使用课件内容，课件可以在下载后自由调整Learning Is To Achieve A Certain Goal And Work Hard,Is A Process To Overcome Various Difficulties For A Goal
