0. 学会使用解析ceph的cluster map工具：
ceph osd getcrushmap -o crush.map crushtool -d crush.map >> crush.txt
这时将一个ceph集群的 cluster map导入到crush.txt的文件中，这时可以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\
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。
ceph的数据存储之路(3) ----- pg选择osd的过程(crush 算法)
原文：http://my.oschina.net/u/2460844/blog/531722