Ceph源码解析:CRUSH算法(2)

数据写入时,文件被切分成object,object先映射到PG,再由PG映射到OSD set。每个pool有多个PG,每个object通过计算hash值并取模得到它所对应的PG。PG再映射到一组OSD(OSD个数由pool的副本数决定),第一个OSD是Primary,剩下的都是Replicas。

Ceph分布数据的过程:首先计算数据x的Hash值并将结果和PG数目取余,以得到数据x对应的PG编号。然后,通过CRUSH算法将PG映射到一组OSD中。最后把数据x存放到PG对应的OSD中。这个过程中包含了两次映射,第一次是数据x到PG的映射。PG是抽象的存储节点,它不会随着物理节点的加入或则离开而增加或减少,因此数据到PG的映射是稳定的。

(1)创建 Pool 和它的 PG。根据上述的计算过程,PG 在 Pool 被创建后就会被 MON 在根据 CRUSH 算法计算出来的 PG 应该所在若干的 OSD 上被创建出来了。也就是说,在客户端写入对象的时候,PG 已经被创建好了,PG 和 OSD 的映射关系已经是确定了的。

(2)Ceph 客户端通过哈希算法计算出存放 object 的 PG 的 ID:

客户端输入 pool ID 和 object ID (比如 pool = “liverpool” and object-id = “john”)

ceph 对 object ID 做哈希

ceph 对该 hash 值取 PG 总数的模,得到 PG 编号 (比如 58)(第2和第3步基本保证了一个 pool 的所有 PG 将会被均匀地使用)

ceph 对 pool ID 取 hash (比如 “liverpool” = 4)

ceph 将  pool ID 和 PG ID 组合在一起(比如 4.58)得到 PG 的完整ID。

也就是:PG-id = hash(pool-id). hash(objet-id) % PG-number

Ceph源码解析:CRUSH算法

(3)客户端通过 CRUSH 算法计算出(或者说查找出) object 应该会被保存到 PG 中哪个 OSD 上。(注意:这里是说”应该“,而不是”将会“,这是因为 PG 和 OSD 之间的关系是已经确定了的,那客户端需要做的就是需要知道它所选中的这个 PG 到底将会在哪些 OSD 上创建对象。)。这步骤也叫做 CRUSH 查找。 

对 Ceph 客户端来说,只要它获得了 Cluster map,就可以使用 CRUSH 算法计算出某个 object 将要所在的 OSD 的 ID,然后直接与它通信。

Ceph client 从 MON 获取最新的 cluster map。

Ceph client 根据上面的第(2)步计算出该 object 将要在的 PG 的 ID。

Ceph client 再根据 CRUSH 算法计算出 PG 中目标主和次 OSD 的 ID。

也就是:OSD-ids = CURSH(PG-id, cluster-map, cursh-rules)。

Ceph源码解析:CRUSH算法

具体数据读写流程下次整理分析。

3 CRUSH 算法

CRUSH算法根据种每个设备的权重尽可能概率平均地分配数据。分布算法是由集群可用存储资源以及其逻辑单元的map控制的。这个map的描述类似于一个大型服务器的描述:服务器由一系列的机柜组成,机柜装满服务器,服务器装满磁盘。数据分配的策略是由定位规则来定义的,定位规则指定了集群中将保存多少个副本,以及数据副本的放置有什么限制。例如,可以指定数据有三个副本,这三个副本必须放置在不同的机柜中,使得三个数据副本不公用一个物理电路。

给定一个输入x,CRUSH 算法将输出一个确定的有序的储存目标向量 ⃗R 。当输入x,CRUSH利用强大的多重整数hash函数根据集群map、定位规则、以及x计算出独立的完全确定可靠的映射关系。CRUSH分配算法是伪随机算法,并且输入的内容和输出的储存位置之间是没有显式相关的。我们可以说CRUSH 算法在集群设备中生成了“伪集群”的数据副本。集群的设备对一个数据项目共享数据副本,对其他数据项目又是独立的。

CRUSH算法通过每个设备的权重来计算数据对象的分布。对象分布是由cluster map和data distribution policy决定的。cluster map描述了可用存储资源和层级结构(比如有多少个机架,每个机架上有多少个服务器,每个服务器上有多少个磁盘)。data distribution policy由 placement rules组成。rule决定了每个数据对象有多少个副本,这些副本存储的限制条件(比如3个副本放在不同的机架中)。

CRUSH算出x到一组OSD集合(OSD是对象存储设备):

(osd0, osd1, osd2 … osdn) = CRUSH(x) 

CRUSH利用多参数HASH函数,HASH函数中的参数包括x,使得从x到OSD集合是确定性的和独立的。CRUSH只使用了cluster map、placement rules、x。CRUSH是伪随机算法,相似输入的结果之间没有相关性。

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

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