标签归档:crush

[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学习-8]crush算法(3)

冲突、故障、和超载
select(n,t)操作可能为了定位n个不相同的t类型的item,而从起点开始向下遍历而经过许多层,递归过程的次数有r=1,..n确定,n是选择副本的个数。在处理过程中,CRUSH可能会有下面三个不同的原因而用于修改过的输入r’来拒绝并重选项,某个item已经在当前的集合中(发生冲突,select(n,t)的结果必须是各不相同的);有一个设备失效了,有一个设备超载。失效或超载的设备都会在Cluster Map中进行相应的标记,但为了避免不必要的数据迁移,不同从层次结构中移除它们。CRUSH通过根据Cluster Map中指定的概率伪随机的拒绝超载的设备,来选择性的转移此超载device上的少部分数据。这个概率则是与报告的超载情况有关的。对于失效或超载的设备、CRUSH通过重新启动select(n,t)开始部分递归过程,均匀的在存储集群中重新分布这些item。而对应冲突的青睐,则在递归内层使用r’替换r来进行局部搜索。不至于在那些很可能发生冲突的子树中(bucket容量小于n)改变总体数据分布。

冲突:这个item已经在向量i中,已被选择,使用r’(r’和r、出错次数,firstn参数)做为新的参数选择item(局部选择)
故障:设备故障,不能被选择。
超载:设备使用容量超过警戒线、没有剩余空间保存数据。
其中故障和超载设备会在clustermap上标记,为了不必要的数据迁移,不会从层次结构中移除它们。

副本排序
在主拷贝副本模式中,发生故障时,让之前的副本目标成为新的主拷贝,在这种情况下,CRUSH可以通过r’=r+f进行重选,来使用”前n个“合适的目标,f是当前select(n,t)操作中确定放置位置失败的次数。而对于奇偶校验码或擦除码模式,CRUSH算法输出的存储设备的顺序至关重要,因为每个目标都存放了数据对象的不同比特位,特别的,当某个存储设备发生故障时,它需要在CRUSH的输出列表R(向量R)的对应位置上被替换,其他列表中的设备要维持位置不变(位置是指向量R对应的位置)这种情况下,CRUSH通过r’=r+fn进行重选,其中f是第r次迭代时失败的次数。这样就是为每一个向量位置上的item定义了一系列的候选item。每个候选item与其他位置上的候选item是无关的。相比,RUSH对应发生故障的设备没有特殊处理,就像其他现有的散列分布式函数,它隐式的假设使用”前n个”的策略在结果中跳过失效的设备。

[ceph学习-6]crush算法(1)

crush算法类似一致性算法,一致性算法使用了一个散列到服务器平台的散列表,crush可以存在层级结构的服务器上(shelves,racks,rows),并允许用户制定。例如将复制到不同的货架上而不是仅在primary上。

crush(Controoled Replication Under Scalable Hashing)是一种伪随机数据分布算法,它能够在层级结构的存储集群中有效的分布对象的副本。它的参数为object id或object group。id,并返回一组存储设备(用于保存object副本)。Crush需要cluster map(描述存储集群的层级结构)、和副本分布策略(rule).
CRUSH的优点:任何组件都可以独立计算出每个object所在的位置(去中心化).只需要少量的元数据(cluster map),只要当删除添加设备时,这些元数据才需要改变

crush算法是通过对每个设备的权重在存储设备间分发数据,大致是均匀分布的。数据分发是有一个层次化的cluster map 控制的,Cluster Map描述了可用的存储资源,由建立集群映射的一些逻辑元素组成。例如,某个Cluster Map可能描述了一个大型的装置,包含了一排机柜,每个机柜有许多磁盘架,每个磁盘架上有许多存储设备。数据分配策略是有placement Rules定义的。 Placement Rules 指定了从及群众中选中的副本目标的数量,以及放置这些副本的限制条件。例如,某个Placement Rule也许会指定三个镜像副本要被放置在不同的物理机柜上,以免这些副本共享同一条供电线路。

CRUSH算出x到一组OSD集合:
给出一个整型输入x,CRUSH会输出一个有序的、包含n个不相同的存储目标的R向量。

CRUSH使用一个多参数的整形hash函数,参数列表包含x,使得从x到osd集合是完全独立且确定性的,仅仅依赖Cluster Map、Placement RUles和输入参数x。数据分发是伪随机的,输出结果与输入结果或者设备中现象有的对象之间没有明显的相关性。
CRUSH提供了一个去集中化(集群化)的副本发布方案,包含某对象的共享副本的这些设备也是相对其他对象也是独立的。