Ceph源码解析:CRUSH算法

随着大规模分布式存储系统(PB级的数据和成百上千台存储设备)的出现。这些系统必须平衡的分布数据和负载(提高资源利用率),最大化系统的性能,并要处理系统的扩展和硬件失效。ceph设计了CRUSH(一个可扩展的伪随机数据分布算法),用在分布式对象存储系统上,可以有效映射数据对象到存储设备上(不需要中心设备)。因为大型系统的结构式动态变化的,CRUSH能够处理存储设备的添加和移除,并最小化由于存储设备的的添加和移动而导致的数据迁移。

为了保证负载均衡,保证新旧数据混合在一起。但是简单HASH分布不能有效处理设备数量的变化,导致大量数据迁移。ceph开发了CRUSH(Controoled Replication Under Scalable Hashing),一种伪随机数据分布算法,它能够在层级结构的存储集群中有效的分布对象的副本。CRUSH实现了一种伪随机(确定性)的函数,它的参数是object id或object group id,并返回一组存储设备(用于保存object副本OSD)。CRUSH需要cluster map(描述存储集群的层级结构)、和副本分布策略(rule)。

CRUSH有两个关键优点:

任何组件都可以独立计算出每个object所在的位置(去中心化)。

只需要很少的元数据(cluster map),只要当删除添加设备时,这些元数据才需要改变。

CRUSH的目的是利用可用资源优化分配数据,当存储设备添加或删除时高效地重组数据,以及灵活地约束对象副本放置,当数据同步或者相关硬件故障的时候最大化保证数据安全。支持各种各样的数据安全机制,包括多方复制(镜像),RAID奇偶校验方案或者其他形式的校验码,以及混合方法(比如RAID-10)。这些特性使得CRUSH适合管理对象分布非常大的(PB级别)、要求可伸缩性,性能和可靠性非常高的存储系统。简而言之就是PG到OSD的映射过程。

2.映射过程

2.1 概念

ceph中Pool的属性有:1.object的副本数  2.Placement Groups的数量    3.所使用的CRUSH Ruleset

数据映射(Data Placement)的方式决定了存储系统的性能和扩展性。(Pool,PG)→ OSD set的映射由四个因素决定:

(1)CRUSH算法

(2)OSD MAP:包含当前所有pool的状态和OSD的状态。OSDMap管理当前ceph中所有的OSD,OSDMap规定了crush算法的一个范围,在这个范围中选择OSD结合。OSDMap其实就是一个树形的结构,叶子节点是device(也就是osd),其他的节点称为bucket节点,这些bucket都是虚构的节点,可以根据物理结构进行抽象,当然树形结构只有一个最终的根节点称之为root节点,中间虚拟的bucket节点可以是数据中心抽象、机房抽象、机架抽象、主机抽象等如下图。

191305_azzU_2460844

osd组成的逻辑树形结构

struct crush_bucket
{
    __s32 id;        /* this'll be negative */
    __u16 type;      /* non-zero; type=0 is reserved for devices */
    __u8 alg;        /* one of CRUSH_BUCKET_* */
    __u8 hash;      /* which hash function to use, CRUSH_HASH_* */
    __u32 weight;    /* 16-bit fixed point *///权重一般有两种设法。一种按容量,一般是1T为1,500G就是0.5。另外一种按性能。具体按实际设置。
    __u32 size;      /* num items */
    __s32 *items;

/*
    * cached random permutation: used for uniform bucket and for
    * the linear search fallback for the other bucket types.
    */
    __u32 perm_x;  /* @x for which *perm is defined */
    __u32 perm_n;  /* num elements of *perm that are permuted/defined */
    __u32 *perm;
};

(3)CRUSH MAP:包含当前磁盘、服务器、机架的层级结构。

(4)CRUSH Rules:数据映射的策略。这些策略可以灵活的设置object存放的区域。比如可以指定 pool1中所有objects放置在机架1上,所有objects的第1个副本放置在机架1上的服务器A上,第2个副本分布在机架1上的服务器B上。 pool2中所有的object分布在机架2、3、4上,所有Object的第1个副本分布在机架2的服务器上,第2个副本分布在机架3的服器上,第3个副本分布在机架4的服务器上。

2.2 流程

Ceph 架构中,Ceph 客户端是直接读或者写存放在 OSD上的 RADOS 对象存储中的对象(data object)的,因此,Ceph 需要走完 (Pool, Object) → (Pool, PG) → OSD set → OSD/Disk 完整的链路,才能让 ceph client 知道目标数据 object的具体位置在哪里。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/af34d2648b0f6bf7050bbadff830e5bf.html