详解Ceph的杀手级技术CRUSH

摘要：下图是的代码段，我喜欢叫它搅拌搅拌再搅拌得出一个随机数如果看到这里你已经被搅晕了，那让我再简单梳理下选择一个时做的事情给出一个，作为的输入。，，得出一个随机数重点是随机数，不是。对于所有的用他们的权重乘以每个对应的随机数，得到乘积。

前言

前文回顾：《开源社区的明星项目—Ceph谈》、《史上最全的Ceph构件及组件分析》、

关于Ceph主题，这一节将详细介绍Ceph  CRUSH。

Ceph CRUSH

CRUSH算法通过计算数据存储位置来确定如何存储和检索数据。CRUSH使Ceph客户机能够直接与OSDs通信，而不是通过集中的服务器或代理。通过算法确定的数据存储和检索方法，Ceph避免了单点故障、性能瓶颈和对其可伸缩性的物理限制。

CRUSH需要集群的映射，并使用CRUSH映射在OSDs中伪随机存储和检索数据，数据在集群中均匀分布。

CRUSH映射包含一个osd列表、一个用于将设备聚合到物理位置的“bucket”列表，以及一个规则列表，这些规则告诉CRUSH应该如何复制Ceph集群池中的数据。通过反映安装的底层物理组织，CRUSH可以建模——从而解决——相关设备故障的潜在来源。典型的资源包括物理接近性、共享电源和共享网络。通过将这些信息编码到集群映射中，CRUSH放置策略可以跨不同的故障域分离对象副本，同时仍然保持所需的分布。例如，为了解决并发故障的可能性，可能需要确保数据副本位于使用不同货架、机架、电源、控制器和／或物理位置的设备上。

当您创建一个配置文件并使用Ceph －deploy部署Ceph时，Ceph将生成一个默认的map。默认的CRUSH map 是工作的。然而，当您部署大型数据集群时，您应该考虑开发一个定制CRUSH map，因为它将帮助您管理Ceph集群，提高性能并确保数据安全。

CRUSH map可以帮助你更快地识别错误。例如，如果一个特定机架中的所有OSDs同时下降，故障可能是由网络交换机或机架的电源引起的，而不是OSDs本身。当与失败主机关联的放置组处于降级状态时，自定义CRUSH map还可以帮助您确定Ceph存储冗余数据副本的物理位置。

CRUSH WRITE

那么一个object是如何保存到磁盘上呢？

1．1．1 逻辑层

Ceph为了保存一个对象，对上构建了一个逻辑层，也就是池（pool），用于保存对象，这个池的翻译很好的解释了pool的特征，如果把pool比喻成一个中国象棋棋盘，那么保存一个对象的过程就类似于把一粒芝麻放置到棋盘上。

Pool再一次进行了细分，即将一个pool划分为若干的PG（归置组Placement Group），这类似于棋盘上的方格，所有的方格构成了整个棋盘，也就是说所有的PG构成了一个pool。

现在需要解决的问题是，对象怎么知道要保存到哪个PG上，假定这里我们的pool名叫rbd，共有256个PG，给每个PG编个号分别叫做0x0， 0x1， ．．．0xF， 0x10， 0x11．．． 0xFE， 0xFF。

要解决这个问题，我们先看看我们拥有什么，1，不同的对象名。2，不同的PG编号。这里就可以引入Ceph的计算方法了： HASH。

对于对象名分别为bar和foo的两个对象，对他们的对象名进行计算即：

HASH（‘bar’） ＝ 0x3E0A4162

HASH（‘foo’） ＝ 0x7FE391A0

HASH（‘bar’） ＝ 0x3E0A4162

对对象名进行HASH后，得到了一串十六进制输出值，也就是说通过HASH我们将一个对象名转化成了一串数字，那么上面的第一行和第三行是一样的有什么意义？意义就是对于一个同样的对象名，计算出来的结果永远都是一样的，但是HASH算法的确将对象名计算得出了一个随机数。

有了这个输出，我们使用小学就会的方法：求余数！用随机数除以PG的总数256，得到的余数一定会落在［0x0， 0xFF］之间，也就是这256个PG中的某一个：

0x3E0A4162 ％ 0xFF ＝＝＝＞ 0x62

0x7FE391A0 ％ 0xFF ＝＝＝＞ 0xA0

于是乎，对象bar保存到编号为0x62的PG中，对象foo保存到编号为0xA0的PG中。对象bar永远都会保存到PG 0x62中！对象foo永远都会保存到PG 0xA0中！

这里给出更Ceph一点的说明，实际上在Ceph中，存在着多个pool，每个pool里面存在着若干的PG，如果两个pool里面的PG编号相同，Ceph怎么区分呢？ 于是乎，Ceph对每个pool进行了编号，比如刚刚的rbd池，给予编号0，再建一个pool就给予编号1，那么在Ceph里，PG的实际编号是由pool＿id＋．＋PG＿id组成的，也就是说，刚刚的bar对象会保存在0．62这个PG里，foo这个对象会保存在0．A0这个PG里。其他池里的PG名称可能为1．12f， 2．aa1，10．aa1等。

1．1．2 物理层

理解了刚刚的逻辑层，我们再看一下Ceph里的物理层，对下，也就是我们若干的服务器上的磁盘，通常，Ceph将一个磁盘看作一个OSD（实际上，OSD是管理一个磁盘的程序），于是物理层由若干的OSD组成，我们的最终目标是将对象保存到磁盘上，在逻辑层里，对象是保存到PG里面的，那么现在的任务就是打通PG和OSD之间的隧道。PG相当于一堆余数相同的对象的组合，PG把这一部分对象打了个包，现在我们需要把很多的包平均的安放在各个OSD上，这就是CRUSH算法所要做的事情：CRUSH计算PG－＞OSD的映射关系。

加上刚刚的对象映射到PG的方法，我们将开篇的两步表示成如下的两个计算公式：

池ID ＋ HASH（‘对象名’） ％ pg＿num ＝＝＝＞ PG＿ID

CRUSH（PG＿ID） ＝＝＝＞ OSD

使用HASH代替CRUSH？

在讨论CRUSH算法之前，我们来做一点思考，可以发现，上面两个计算公式有点类似，为何我们不把

CRUSH（PG＿ID） ＝＝＝＞ OSD
改为

HASH（PG＿ID） ％OSD＿num ＝＝＝＞ OSD

我可以如下几个由此假设带来的副作用：

如果挂掉一个OSD，OSD＿num－1，于是所有的PG ％ OSD＿num的余数都会变化，也就是说这个PG保存的磁盘发生了变化，对这最简单的解释就是，这个PG上的数据要从一个磁盘全部迁移到另一个磁盘上去，一个优秀的存储架构应当在磁盘损坏时使得数据迁移量降到最低，CRUSH可以做到。

如果保存多个副本，我们希望得到多个OSD结果的输出，HASH只能获得一个，但是CRUSH可以获得任意多个。

如果增加OSD的数量，OSD＿num增大了，同样会导致PG在OSD之间的胡乱迁移，但是CRUSH可以保证数据向新增机器均匀的扩散。

所以HASH只适用于一对一的映射关系计算，并且两个映射组合（对象名和PG总数）不能变化，因此这里的假设不适用于PG－＞OSD的映射计算。因此，这里开始引入CRUSH算法。

引入CRUSH算法

千呼万唤始出来，终于开始讲CRUSH算法了，如果直接讲Sage的博士论文或者crush．c的代码的话，可能会十分苦涩难懂，所以我决定尝试大话一把CRUSH，希望能让没有接触过CRUSH的同学也能对其有所理解。

首先来看我们要做什么：

把已有的PG＿ID映射到OSD上，有了映射关系就可以把一个PG保存到一个磁盘上。

如果我们想保存三个副本，可以把一个PG映射到三个不同的OSD上，这三个OSD上保存着一模一样的PG内容。

再来看我们有了什么：

互不相同的PG＿ID。

如果给OSD也编个号，那么就有了互不相同的OSD＿ID。

每个OSD最大的不同的就是它们的容量，即4T还是800G的容量，我们将每个OSD的容量又称为OSD的权重（weight），规定4T权重为4，800G为0．8，也就是以T为单位的值。

现在问题转化为：如何将PG＿ID映射到有各自权重的OSD上。这里我直接使用CRUSH里面采取的Straw算法，翻译过来就是抽签，说白了就是挑个最长的签，这里的签指的是OSD的权重。

那么问题就来了，总不至于每次都挑容量最大的OSD吧，这不分分钟都把数据存满那个最大的OSD了吗？是的，所以在挑之前先把这些OSD搓一搓，这里直接介绍CRUSH的方法，如下图（可忽视代码直接看文字）：

CRUSH＿HASH（ PG＿ID， OSD＿ID， r ） ＝＝＝＞ draw

（ draw ＆0xffff ） ＊ osd＿weight ＝＝＝＞ osd＿straw

pick up high＿osd＿straw

第一行，我们姑且把r当做一个常数，第一行实际上就做了搓一搓的事情：将PG＿ID， OSD＿ID和r一起当做CRUSH＿HASH的输入，求出一个十六进制输出，这和HASH（对象名）完全类似，只是多了两个输入。所以需要强调的是，对于相同的三个输入，计算得出的draw的值是一定相同的。

这个draw到底有啥用？其实，CRUSH希望得到一个随机数，也就是这里的draw，然后拿这个随机数去乘以OSD的权重，这样把随机数和OSD的权重搓在一起，就得到了每个OSD的实际签长，而且每个签都不一样长（极大概率），就很容易从中挑一个最长的。

说白了，CRUSH希望随机挑一个OSD出来，但是还要满足权重越大的OSD被挑中的概率越大，为了达到随机的目的，它在挑之前让每个OSD都拿着自己的权重乘以一个随机数，再取乘积最大的那个。那么这里我们再定个小目标：挑个一亿次！从宏观来看，同样是乘以一个随机数，在样本容量足够大之后，这个随机数对挑中的结果不再有影响，起决定性影响的是OSD的权重，也就是说，OSD的权重越大，宏观来看被挑中的概率越大。

这里再说明下CRUSH造出来的随机数draw，前文可知，对于常量输入，一定会得到一样的输出，所以这并不是真正的随机，所以说，CRUSH是一个伪随机算法。下图是CRUSH＿HASH的代码段，我喜欢叫它搅拌搅拌再搅拌得出一个随机数：

如果看到这里你已经被搅晕了，那让我再简单梳理下PG选择一个OSD时做的事情：

－给出一个PG＿ID，作为CRUSH＿HASH的输入。

－CRUSH＿HASH（PG＿ID， OSD＿ID， r） 得出一个随机数（重点是随机数，不是HASH）。

－对于所有的OSD用他们的权重乘以每个OSD＿ID对应的随机数，得到乘积。

－选出乘积最大的OSD。

－这个PG就会保存到这个OSD上。

现在趁热打铁，解决一个PG映射到多个OSD的问题，还记得那个常量r吗？我们把r＋1，再求一遍随机数，再去乘以每个OSD的权重，再去选出乘积最大的OSD，如果和之前的OSD编号不一样，那么就选中它，如果和之前的OSD编号一样的话，那么再把r＋2，再次选一次，直到选出我们需要的三个不一样编号的OSD为止！

当然实际选择过程还要稍微复杂一点，我这里只是用最简单的方法来解释CRUSH在选择OSD的时候所做的事情。

下面我们来举个例子，假定我们有6个OSD，需要从中选出三个副本：

osd＿id

weight

CRUSH＿HASH

（CRUSH＿HASH ＆ 0xffff）＊ weight

osd．0

4

0xC35E90CB

0x2432C

osd．1

4

0xA67DE680

0x39A00

osd．2

4

0xF9B1B224

0x2C890

osd．3

4

0x42454470

0x111C0

osd．4

4

0xE950E2F9

0x38BE4

osd．5

4

0x8A844538

0x114E0

这是r ＝ 0的情况，这时候，我们选出（CRUSH＿HASH ＆ 0xFFFF） ＊ weight的值最大的一个，也就是osd．1的0x39A00，这就是我们选出的第一个OSD。

然后，我们再让r ＝ 1，再生成一组CRUSH＿HASH的随机值，乘以OSD的weight，再取一个最大的得到第二个OSD，依此得到第三个OSD，如果在此过程中，选中了相同的OSD，那么将r再加一，生成一组随机值，再选一次，直到选中三个OSD为止。

下面是伪代码object到osd的伪代码

locator ＝object＿name

obj＿hash ＝hash（locator）

pg ＝obj＿hash ％num＿pg

OSDs＿for＿pg ＝crush（pg）  ＃ returns a list of OSDs

primary ＝osds＿for＿pg［0］

replicas ＝osds＿for＿pg［1：］

defcrush（pg）：

all＿osds＝［＇osd．0＇，＇osd．1＇，＇osd．2＇，．．．］

result＝［］

＃ size is the number of copies； primary＋replicas

whilelen（result）＜size：

r＝hash（pg）

chosen＝all＿osds［r％len（all＿osds）］

ifchoseninresult：

＃ OSD can be picked only once

continue

result．append（chosen）

returnresult

CRUSH READ

对于Ceph 集群的一次读写操作，客户端首先联系Ceph 的momtor 并获取一个集群

map 副本。集群map 帮助客户端获取Ceph 集群的状态和配置信息。使用对象和池名IID将数据转换为对象。然后将对象和PG （ placement groups ，归置组）数一起经过散列来生成其在Ceph 池巾最终存放的那一个PG 。然后前面计算好的PG 经过CRUSH 查找来确定存储或获取数据所需的主OSO 的位置计算完准确的OSD 10 之后，客户端直接联系这个OSO 来存储数据。所有这些计算操作都由客户端来执行，因此它不会影响集群的性能。

一旦数据被写入主OSO ，主OSO 所在节点将执行CRUSH 查找操作并计算辅助归置组和lOSD 的位置来实现数据复制，进而实现高可用性。参考下面的例子来了解CRUSH 查找和对象王IJ OSO 的映射。

首先，基于池10 将对象名称和集群PG 数应用散列函数可以得到一个PG 10 。接下来，

针对这个PG lD执行CRUSH 查找得到主OSO 和辅助OSO ，最后写数据。

CRUSH 层级结构

CRUSH 是完全了解所有基础设施并支持用户自定义配置的，它维护你所有基础设施组件的一个嵌套层次结构。CRUSH 设备列表通常包括磁盘、节点、机架（ rack） 、行（ row） 、开关、电源电路、房间、数据中心等。这些组件称为故障域或CRUSH bucketo CRUSH map包含一系列可用bucket ，这些bucket 表明了设备的具体物理位置。它还包拆一系列的规则告诉CRUSH 如何为不同的Ceph 池复制数据。从下图可以看到CRUSH 是如何看待你的基础设施的。

CRUSH WEIGHTS

CRUSH算法为每个设备分配一个权重值，其目标是逼近I／O请求的均匀概率分布。作为最佳实践，我们建议使用相同类型和大小的设备创建池，并分配相同的相对权重。由于这并不总是实用的，您可以合并不同大小的设备，并使用相对权重，以便Ceph将更多的数据分配给较大的驱动器，而将更少的数据分配给较小的驱动器。

CRUSH RECOVERY

在故障域内任何组件发生故障之后，在Ceph 将该OSD 标记为down 和out 并初始化恢

复操作前，默认情况下Ceph 会等待300 秒。这个值可以在Ceph 集群的配置文件中通过参数mon osd down out interval 进行修改。在恢复操作期间，Ceph 开始重新组织发生故障的节点上受影响的数据。CRUSH 会复制数据到多个磁盘，这些复制的数据在恢复的时候使用。在恢复期间CRUSH 试图移动尽量少的数据来构建一个新的集群布局，这样即使一些组件出现故障也能确保Ceph 的容错性。

当一个新主机或磁盘添加到Ceph 集群中时，CRUSH 开始执行再平衡操作，在这个过程中，CRUSH 从现有的主机／磁盘上移动数据到新的主机／磁盘。再平衡保证所有磁盘

能闯匀使用，以此提升集群性能和保持集群健康。例如，如果一个Ceph 集群包含2000 个OSO ，这时一个新的系统添加20 个新的OSD ，这样就只有1％ 的数据会在再平衡期间移动，并且所有现有的OSD 是并行地移动数据，使其迅速完成这个操作。然而，对于利用率高的Ceph 集群，建议先将新添加的OSD的权重设为0 ，再逐渐增加权重到依据磁盘容量确定的更高的权重值。通过这种方式，新的OSD 将减少Ceph 集群再平衡时的负载并避免性能下降。

启迪云－高级开发工程师  侯玉彬

互动区

＊ 你对以上内容有什么看法？你最关注云计算哪个趋势？如果你还有想了解的技术话题，欢迎留言分享。