ceph的数据存储之路（3）-----pg选择osd的过程（crush算
法）
0. 学会使⽤解析ceph的cluster map⼯具：
ceph osd getcrushmap -o crush.map
crushtool -d crush.map >>
这时将⼀个ceph集的 cluster map导⼊到的⽂件中，这时可以cat这个⽂件看⼀下⽂件中保存了哪些内容，帮助理解下⾯的内容
1. 说明：这⾥⾸先要说明的是  ⼀个object要保存三个副本，也就是要保存到三个osd上，当前的ceph集可以存在N个osd节点，那么怎么来记录这个object保存到哪⾥了？ 这⾥就要讲述这个伪随机的选择osd过程-----crush。
pg 到OSD的映射的过程算法叫做crush 算法，这个算法是⼀个伪随机的过程，他可以从所有的OSD中，随机性选择⼀个OSD集合，但是同⼀个PG每次随机选择的结果是不变的，也就是映射的OSD集合是固定的。
2. crush 因⼦：
OSDMap管理当前ceph中所有的OSD，OSDMap规定了crush算法的⼀个范围，在这个范围中选择OSD结合。那么影响crush算法结果的有两种因素，⼀个就是OSDMap的结构，另外⼀个就是crush rule。
OSDMap其实就是⼀个树形的结构，叶⼦节点是device（也就是osd），其他的节点称为bucket节点，这些bucket都是虚构的节点，可以根据物理结构进⾏抽象，当然树形结构只有⼀个最终的根节点称之为root节点，中间虚拟的bucket节点可以是数据中⼼抽象、机房抽象、机架抽象、主机抽象等如图。
图1-4  osd组成的逻辑树形结构
上图中红⾊框内的节点都是bucket节点，这些节点都是根据实际情况进⾏抽象得来的。其实也就是实际中整个物理拓扑结构。这个拓扑⾥的每个节点都有⼀个权重值，这个权重值等于所有⼦节点的权重之和，叶⼦节点的重量由osd的容量决定，⼀般设定1T的权重为1。这个权重值在crush算法中也有很重要的地位。
3.bucket类型解释：
对于bucket节点不只是虚设的节点，bucket同样有type。bucket的type有四种类型结构，uniform、list、tree、straw。这四种bucket有着不同的特
性，bucket的type设定同样也影响着crush算法。
3.1 uniform 类型：先来介绍下uniform bucket如何来定位数据在哪个⼦节点的过程。
图1-5 uniform 定位⼦节点过程
先来说明⼀下uniform的要素。bucket的所有⼦节点都保存在item[]数组之中。perm_x 是记录这次随机排布时 x的值，perm[]是在perm_x时候对item随机排列后的结果。r则是选择第⼏个副本。
定位⼦节点过程。这时我们重新来看uniform定位⼦节点的过程。根据输⼊的x值判断是否为perm_x，如果不是，则需要重新排列perm[]数组，并且记
录perm_x=x。如果x==perm_x时，这时算R = r%size，算后得到R，最后返回 perm[R]。
uniform bucket 适⽤的情况：
a.适⽤于所有⼦节点权重相同的情况。因为uniform的bucket在选择⼦节点时是不考虑权重的问题，全部随机选择。所以在权重上不会进⾏特别的照顾，为了公平起见最好是相同的权重节点。
b.适⽤于⼦节点变化概率⼩的情况。当⼦节点的数量进⾏变化时，size发⽣改变，在随机组合perm数组时，即使x相同，则perm数组需要完全重新排列，也就意味着已经保存在⼦节点的数据要全部发⽣重排，造成很多数据的迁移。所以uniform不适合⼦节点变化的bucket，否则会产⽣⼤量已经保存的数据发⽣移动，所有的item上的数据都可能会发⽣相互之间的移动。
3.2 list 类型：list bucket的形成过程。list  bucket 不是真的将所有的item都穿成⼀个链表，bucket的item仍然保存在item数组之中。这时的list bucket 每
个item 不仅要保存的权重（根据容量换算⽽来）weight，还要记录前所有节点的重量之和sum_weight如图，list bucket的每个item的权重可以不相同，也不需要按顺序排列。
图1-6 list bucket 形成过程
list bucket定位数据在⼦节点的⽅法。从head开始，会逐个的查⼦节点是否保存数据。
如何判断当前⼦节点是否保存了数据呢？⾸先取了⼀个节点之后，根据x，r 和item的id 进⾏crush_hash得到⼀个w值。这个值与sum_weight之积，最后这个w再向右移16位，最后判断这个值与weight的⼤⼩，如果⼩于weight时，则选择当前的这个item，否则进⾏查下⼀个item。
图1-7 list bucket 定位数据过程
list bucket使⽤的情况：
a.适⽤于集拓展类型。当增加item时，会产⽣最优的数据移动。因为在list bucket中增加⼀个item节点时，都会增加到head部，这时其他节点
的sum_weight都不会发⽣变化，只需要将old_head 上的sum_weight和weight之和添加到new_head的sum_weight就好了。这样时其他item之间不需要进⾏数据移动，其他的item上的数据 只需要和 head上⽐较就好，如果算的w值⼩于head的weight，则需要移动到head上，否则还保存在原来的item上。这样就获得了最优最少的数据移动。
b.list bucket存在⼀个缺点，就是在查item节点时，只能顺序查 时间复杂度为O(n)。
3.3 tree 类型：tree bucket 会借助⼀个叫做node_weight[ ]的数组来进⾏帮助搜索定位item。⾸先是node_weight[ ]的形成，nodeweight[ ]中不仅包含
了item，⽽且增加了很多中间节点，item都作为叶⼦节点。⽗节点的重量等于左右⼦节点的重量之和，递归到根节点如下图。
图1-8 tree bucket的形成过程
tree bucket的搜索过程，通过⼀定的⽅法形成node tree。这tree的查从根节点开始直到到叶⼦节点。当前节点的重量weight使⽤crush_hash(x,r）修正后，与左节点的重量left_weight⽐较，如果⽐左节点轻 则继续遍历左节点，否则遍历右节点如下图。所以该类型的bucket适合于查的，对于变动的集就没那么合适了。
图1-9 tree bucket选择过程
3.4 straw类型：这种类型是⼀种抽签类型的bucket，他选择⼦节点是公平的，straw和uniform的区别在于，straw算法考虑了⼦节点的权重，所以是最公平的bucket类型。
图 1-10 straw bucket的形成过程
straw bucket⾸先根据每个节点的重量⽣成的straw，最后组成straw[] 数组。在straw定位副本的过程中，每⼀个定位都需要遍历所有的item，长度draw = crush(x,r,item_id)*straw[i]。出那个最长的，最后选择这个最长，定位到副本。
4. crush rule介绍：
crush rule主要有3个重点：a.从OSDMap中的哪个节点开始查，b.使⽤那个节点作为故障隔离域，c.定位副本的搜索模式（⼴度优先 or 深度优先）。
# rules
rule replicated_ruleset                            #规则集的命名，创建pool时可以指定rule集
{
ruleset 0                                      #rules集的编号，顺序编即可
type replicated                                #定义pool类型为replicated(还有esurecode模式)
min_size 1                                    #pool中最⼩指定的副本数量不能⼩1\
weight的所有形式
max_size 10                                    #pool中最⼤指定的副本数量不能⼤于10
step take default                              #定义pg查副本的⼊⼝点
step chooseleaf  firstn  0  type  host        #选叶⼦节点、深度优先、隔离host
step emit        #结束
}
5. 总结：
pg 选择osd的过程，⾸先要知道在rules中 指明从osdmap中哪个节点开始查，⼊⼝点默认为default也就是root节点，然后隔离域为host节点(也就是同⼀个host下⾯不能选择两个⼦节点)。由default到3个host的选择过程，这⾥由default根据节点的bucket类型选择下⼀个⼦节点，由⼦节点再根据本⾝的类型继续选择，知道选择到host，然后在host下选择⼀个osd。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。