CRUSH数据分布算法的全称是:Controlled, Scalable, Decentralized Placement of Replicated Data. 开源的分布式存储Ceph采用CRUSH数据分布算法以达到以下几个要求: 2. 负载均衡
在Ceph存储中,数据都是以object为基本单位进行存储的,每个object默认为4MB大小;若干个object属于一个PG(Placement Group,归置组);而若干个PG又属于一个OSD;一般来说,一个OSD对应于一块磁盘。Ceph采用层级化的集群结构(Hierarchical Cluster Map),并且用户可自定义该集群结构,而OSD正是这个层级化集群结构的叶子节点。用户可定义整个集群分为3层,也可定义为5层,具体还可以定义每层的名字。举个栗子,一个Ceph集群,最顶层叫做root,root下面分为2个data center,每个data center有3个room,每个room有4个机架,每个机架上有5台机器,每台机器有6块硬盘(即6个OSD)。这些都是可自定义的,并且还可在线修改(见此篇)。整个层次结构中,除了叶子节点OSD之外,其他的都称之为bucket. 而上面提到的PG,不属于该层级结构。因为层级结构反映的是物理情况,相当于设定故障域,方便定位问题,而PG则是一个逻辑概念(在实际中,PG相当于磁盘上的一个目录,而属于这个PG的诸多object则是这个目录下的文件)。在一个Ceph集群上,可建立若干个Pool,每个Pool在创建的时候,就需要指明该Pool的PG数目。因此,Pool也是一个逻辑的概念。而PG,其实还相当于一致性Hash中的虚拟节点 -- PG的数目不会改变就如同虚拟节点的数目不会改变。而OSD相当于是一致性Hash中的物理节点。一旦一块磁盘损坏,其对应的OSD上的数据会迁移到其他的OSD上,这就相当于一致性Hash中的物理节点损坏后,其所管辖的虚拟节点被划分给了其他的物理节点。 那么,CRUSH算法如何定位存储数据的位置,并且满足以上四大要求呢? CRUSH算法主要用于在Ceph中定位存储数据的位置,分为2个步骤: 1. 根据数据对象(object)的对象名,计算得到PG_ID: PG_ID = Pool_ID Hash(<object name>) % PG_NUM 2. 根据PG_ID,计算得到一组OSD 因为在Ceph中,Pool分为2种。第一种是Replicated Pool,比如每个object都有N个副本,就是属于这种;第二种是EC Pool,运用的是纠删码技术,每个object只有一个副本,但有一些用于校验和还原的数据块。因此无论对于哪种Pool,一个object都需要多个OSD来保存其副本或者是保存其纠删码,因此输出是一组OSD. 那么,如何根据PG_ID,计算得到一组OSD呢?
效果如下图所示: 这三步(take、select(n,t), emit),是真正的原CRUSH论文中CRUSH算法的架构内容。而在涉及到select的时候,也需要介绍下是如何select的 -- 即bucket选择算法。详情如下。 第一步take(root), 代表的是选中了这个root. 注意,在一个Ceph集群中,是有可能有多个root的,因为层次结构是用户可自己设定的。比如,用户把所有SSD的设备设置成属于一个root,而把所有HDD的设备设置成属于另一个root. 第二步,select(n, t). 这一步是关键,意思是,选择n个类型为t的bucket. 首先,select有2种操作方式:
其次,就是如何去选择bucket了,即bucket随机选择算法。 一共有4种类型的bucket,对于每种类型的bucket,如何“选出”的方法是不一样的。而在设置Placement Rule时,可以指定采用哪种bucket随机选择算法,即属于哪种bucket. hash(PG_ID, r, bucket_id) 这个Hash函数的输入有3个:PG_ID,r为 [1-n] 中的一个值(n为副本数),bucket_id 1. Uniform Bucket 每个bucket的权重都相同(这里应该指的是同层级的节点的weight都相同),并且基本没有硬件设备添加和删除的情况 2. List Bucket 其子item在内存中使用数据结构中的链表来保存,其所包含的item可以具有任意权重。(注:此处item和bucket是一个意思) 具体查找bucket的方法是: 这种Bucket在实际中一般也不太会用,因为其删除硬件时,效率也较差。 这种Bucket在实际中可以考虑使用。其选择速度是很快的,而在添加和删除硬件设备时,速度也还可以。
然后选择length最大的item.
当选出一个OSD后,可能出现冲突(重复选择)、失效(磁盘损坏)、过载的情况,那么此时就重新选择一次。对于Replicated Pool和EC Pool,重新选择的算法是略有不同的。Replicated Pool是直接再选一个即可(r' = r f,f为总失败的次数),而EC Pool则需令r值增加n的倍数后(r' = fr*n, fr为在这个副本上失败的次数),再运用hash(PG_ID, r', bucket_id)来进行重新选择。 下图显示了两种Pool在失败的情况下是如何决定r'的值:
1. 《Ceph源码分析》第四章 CRUSH数据分布算法 2. CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data |
|