当前位置: 代码迷 >> 综合 >> Ceph学习之Crush算法—— Bucket
  详细解决方案

Ceph学习之Crush算法—— Bucket

热度:77   发布时间:2024-01-09 03:28:52.0

Ceph使用Bucket将系统的存储资源按照层级结构组织完成两个目标:映射算法的高效性和可扩展性,以及当集群状态发生变化时(比如设备的增加或者删除)数据的迁移量要尽可能的少。CRUSH定义了四种bucket类型(Uniform Bucket、List Bucket、Tree Bucket、Straw Bucket)来表示层级结构的中间节点,叶子节点就是对应的OSD。每一种类型的bucket使用不同的数据结构来组织它包含的内容,可以是其他Bucket或者OSD,它们是在性能和效率间的折中。接下来将详细介绍一下这四种Bucket。

1 Uniform Bucket

这种bucket有一个严格的要求,bucket中所有的item都是同构的,如有相同的性能,相同大小的容量,而其余三种bucket允许包含不同权重的设备。这个主要是考虑到设备不会一个一个添加到系统里,而是批量添加的。它根据hash函数c(r,x)=(hash(x) + rp) mod m进行映射,映射的时间复杂度是O(1),所以它的查询速度是最快的。当然它也有明显的不足,当添加或删除item时,会导致大量的数据迁移。这是因为它的计算方法和bucket大小有关系,所以当bucket发生变化时所有的计算结果都会发生变化,也就是会有数据迁移。

2 List Bucket

它的结构是链表结构,所包含的item可以具有任意的权重。CRUSH从表头开始查找副本位置,它先得到表头item的权重Wh,然后和剩余所有节点权重之和Wr做比较,然后根据hash(x, r, item)得到一个[0