标签归档:crushmap

[ceph学习-9]crush算法(5)

bucket类型
CRUSH算法的设计是为了权衡两个互斥的目标,映射算法的效率和可靠性,增删设备导致的集群变更时恢复平衡的数据迁移成本最小化。CRUSH定义了四种具有不同算法的buckets来diabetes集群层次结构中的中间节点,而非叶子节点。uniform、List、Tree、Straw。每种桶都基于一种不同的内部数据结构,并且分别使用了不同在定位过程中选择嵌套item的伪随机函数c(r,x).体现了效率和数据重组效率之间的不同权衡方法。
uniform buckets。要求所有桶内的item权值相等,而且bucket很少添加删除item。它的查找速度最快。大小如果改变,设备中的数据会被完全重组。
List buckets:他的结构是链表结构,所包含的item可以具有任意权值。CRUSH从表头开始查找副本的位置,它先得到表头的Item的权重Wh,剩余链表中所有的item的权重之和Ws,然后根据hash(x,r,item)得到一个[0-1]的值v,假如这个v在[0~Wh/Ws)之中,则副本在表头item中,并发挥表头item的标识符(id).否则机选遍历剩余的链表。这种方式来源于RUSHp
Tree buckets:链表查找的复杂度O(n),决策树的查找复杂度为O(logn).item是决策树的叶子节点,决策树中的其他节点知道它左右子树的权重,节点的权重等于左右子树的权重之和。CRUSH从root节点开始查找副本的位置,它先得到节点的左子树的权重Wl,得到节点的权重Wn,然后根据hash(x,r,node_id)得到一个[0-1]的值y,假如这个值v在[0~Wl/Wn)中,则副本在左子树,或者在右子树中。继续遍历节点,直到到达叶子节点。treebucket的关键是当添加删除叶子节点时,决策树中的其他节点的node_id不变。决策树中节点的node_id的标识是根据对二叉树的中序遍历来觉决定的(node_id不等于item的id,也不等于权重)
straw buckets:这种类型的bucket所包含的所有item公平竞争,(不像list和tree一样需要遍历)。这种算法就像抽签一样,所有的item都有机会被抽中(只有最长的签才能被抽中)。每个签的长度是有length= f(Wi)*hash(x,r,i)来决定的。f(Wi)和item的权重有关,i是item的id号。

crush.c文件中
/*用于获取指定的bucket中的item的weight*/

/*用于销毁bucket数据结构*/

/**/用于销毁cursh_map

[ceph学习-9]crush算法(4)

映射改变与数据迁移
大型文件系统中数据分布的一个关键问题是增删存储资源时的相应。CRUSH始终保持数据的均匀分布,以避免负载的不均衡,以及可用资源没有得到充分的利用情况。当某个设备发生过账时,CRUSH会位置设置标记,但仍保留在层次结构中,下次选择时被CRUSH算法拒绝,并根据位置算法,均匀的将内容分发到其他设备上。这样的Cluster map变化使得需要重新映射到新存储目标上的数据最少,这个比例是W/W(W是指所有设备的权重和),因为只有失效设备上的数据被移动了。
当集群的层次结构由于增删存储资源而发生改变时的情况要更加复杂,CRUSH的映射过程,将Cluster Map作为带权的决策树,可能导致额外的数据移动,超过理论上的最佳比例W/W.在层次结构的每一层,每一次相关子树的权重改变,都要改变数据分布,一部分数据对象就要从权重下降的子树移动到权重上升的子树中。由于层次结构中每个节点上的伪随机位置决策在统计意义上是相互独立的,移入某个子树的数据被均匀的分布在哪一点下,而且并不一定需要被重新映射到直接导致权重变化的叶节点中。只有在定位过程相对比较深的层次,才会为维持总体的数据分布而移动数据。

ceph 添加/移除osd 设备

1 删除osd设备

2 新增osd 设备

可能遇到的问题:

osd日志信息为:

mds 日志信息为:

错误的原因可能为:osd 没有在crushmap中。