理解Ceph CRUSH数据定位算法
Ceph的数据定位算法，CRUSH算法，这是一种用户可控的伪随机算法。理解此算法对掌握Ceph助益很大。
下面通过示例来分析CRUSH算法。我们部署一个Ceph集群，用一个节点做monitor，用两个节点（2×3=6块硬盘）做OSD数据服务器，OSD服务器的层次结构如下：
注一：层次结构在Ceph中称之为crushmap，描述了物理集群部署结构。crushmap是Ceph的核心数据之一，由Monitor集群负责维护。
注二：crushmap除了描述物理部署结构之外，还描述了数据存放采取的动作。比如本文示例中动作是step take default，step chooseleaf firstn 0 type host，...
CRUSH算法分两步：
第一步、输入要存储数据（称为object）的key，Ceph利用一个“字符串->数值”哈希算法计算object该放在哪个PG下。
（注：PG是Ceph的一个概念，将多个数据分组存放，PG就是这个“组”，分组的目的是减少元数据量。）
第二步、根据第一步计算得到的pgid，计算PG应该放在哪些osd硬盘上。——这是CRUSH算法的核心部分。
下面重点讲第二步，也就是CRUSH算法的核心。假设我们存入的object key="bigfile"，第一步映射到pgid=6b。
算法第二步目的是计算“bigfile”应该存放到哪两个osd硬盘上（因为设置备份数为2），输出6b，输出应该是[x, y]，比如[5,2]，代表bigfile存放在osd.5和osd.2上，并且是放在PG 6b下面。
1、参考上面的结构图，目前在root层，目标是从下一层选择第1个Host，选取算法是straw哈希算法（可在crushmap中配置）。
2、假设选取得到Host osd1，目前在第二层，目标是从下一层中选择一个osd硬盘，选取算法默认仍是straw哈希算法。
3、假设选取得到osd.5，获得第一个位置。返回顶层继续计算。
4、继续从root层执行，此时如果straw哈希算法输出不变，仍会得到相同结果。这自然不合要求，因此straw()还有一个输入参数是当前是第几次计算。
5.1、这次root straw()可能得到Host osd0，osd0层继续straw()可能得到osd.2，于是获得第二个位置，CRUSH计算结束，返回结果。
5.2、这次root straw()可能仍得到Host osd1，此时会被拒绝，因为根据crushmap设置的规则，数据尽量分散放，都放在一个机器上，机器一挂所有数据都访问不了。因此会递增输入参数“计算次数”并重新计算。
5.2.1、后续某次继续得到Host osd0，继续计算下一层，并最终返回正确结果。
5.2.2、如果连续尝试了>choose_total_tries（在crushmap中可配，默认50）次之后，表示第二个位置的计算失败，仅返回部分结果[5,]。
- EOF -
CRUSH算法的原理与实现
0. 前言
本文主要面向对Ceph及分布式系统有一定了解基础的同学；新入坑的读者可以先从Ceph文档官网获取基本信息。
1. 背景
在分布式存储系统中，数据的位置存放规则一直是研究的热门话题之一。一般来说，系统中所有角色（Clients、Servers）需要有一个统一的数据寻址算法Locator，满足：
Locator(ID) -> [Device_1, Device_2, Device_3, ...]其中输入ID是数据的唯一标识符，输出Device列表是一系列存储设备（多设备冗余以达到多份数据保护或切分提高并发等效果）。早期的直观方案是维护一张全局的Key-Value表，任何角色操作数据时查询该表即可。显然，随着数据量的增多和集群规模的扩大，要在整个系统中维护这么一张不断扩大的表变得越来越困难。CRUSH(Controlled Replication Under Scalable Hashing)即为解决此问题而生，她仅需要一份描述集群物理架构的信息和预定义的规则（均包含在CRUSH map中），便可实现确定数据存储位置的功能。
在Ceph的RADOS中，还引入了PG的概念用以更好地管理数据，如下图所示：
RADOS提供的是基于object的存储功能，每个object会先通过简单的Hash算法归到一个PG中，PGID再作为入参通过CRUSH计算置入到多个OSD中（这里object可以看作是文件，PG即是一个目录，OSD是一个数据根目录下仅有一级子目录的简易文件系统）。因此，CRUSH提供的功能可以描述为：
with CRUSHMap as context:
CRUSH(PGID) -> [OSD_1, OSD_2, OSD_3, ...]2. CRUSH Map
CRUSH map包含了集群正常情况下完成PG定位所需要的绝大部分信息，它可以通过以下命令获取：
$ ceph osd getcrushmap -o crushmap
$ crushtool -d crushmap -o decrushmap直接获取到的crushmap是编码过的，需要通过crushtool转换才能变成人可读的文本文件。decrushmap一般包含以下几个部分：
- Tunables: 可调整的参数列表（仅一部分，非完整列表）
- Devices: 存储设备列表，列举了集群中所有的OSD
- Types: 类型定义，一般0为OSD，其它正整数代表host、chassis、rack等
- Buckets: 容器列表，指明了每个bucket下直接包含的children项及其权重值（非OSD的items统称为bucket）
- Rules: 规则列表，每个规则定义了一种选取OSD的方式
这里是一个非常简单的版本，描述了如下图所示的物理架构：
3. CRUSH Rule
当集群系统变得复杂时，我们往往需要多种策略来存放不同类型的数据；例如，将热数据存放于SSD中，而将冷数据放在HDD中。CRUSH rule就是定义了一种选择策略，Ceph中每个逻辑池都必须对应一条合法的rule才能正常工作。还是以上面链接中的crushmap为例，分析一下rule的具体含义。
1 rule replicated_ruleset {
2 ruleset 0
3 type replicated
4 min_size 1
5 max_size 10
6 step take default
7 step chooseleaf firstn 0 type host
8 step emit
9 }- Line 1-2: rule的名称和编号
- Line 3: rule类型；replicated代表适用于副本池，erasure代表适用于EC池
- Line 4-5: rule适用的池size大小；本例表示1副本到10副本的池均可采用此条rule
- Line 6-9: 具体的选择步骤
- take: 直接选中一项item，一般用于指定选择算法的起点；本例中名为default的root类型bucket即为起点
- chooseleaf firstn 0 type host: 选择策略，这个是重点，后面细述
- emit: 返回结果
选择策略
上述rule中Line 7包含了4部分信息，可以分解为: step <1> <2> <3> type <4>
<1>: choose/chooseleaf
- choose表示选择结果类型为故障域（由<4>指定）
- chooseleaf表示在确定故障域后，还必须选出该域下面的OSD节点（即leaf）
<2>: firstn/indep
- firstn: 适用于副本池，选择结果中rep（replica，指一份副本或者EC中的一个分块，下同）位置无明显意义
- indep: 适用于EC池，选择结果中rep位置不可随意变动
举例来说，副本池中每份副本保存的是完全相同的数据，因此选择结果为[0, 1, 2]（数字代表OSD编号）与[0, 2, 1]并无大的不同。但是EC池不一样，在2+1的配比下前两份是数据块，最后一份是校验块，后两份rep位置一交换就会导致数据出错。
<3>: num_reps
这个整数值指定需要选择的rep数目，可以是正值负值或0。
- 正整数值即代表要选择的副本数，非常直观
- 0表示的是与实际逻辑池的size相等；也就是说，如果2副本池用了这个rule，0就代表了2；如果3副本池用了此rule，0就相当于3
- 负整数值代表与实际逻辑池size的差值；如果3副本池使用此rule将该值设为了-1，那边该策略只会选择出2个reps
<4>: failure domain
指定故障域类型；CRUSH确保同一故障域最多只会被选中一次。
4. Rule执行流程
接下来介绍选择策略的核心实现流程。为简单起见，以下面的rule step为例：
step take default
step choose firstn 3 type osd
step emit其基本的设计思路可以描述为：
def choose(take, num_reps, failure_domain):
result = empty_list
for rep in range(num_reps):
in_bucket = take # start item
while True:
item = random_pick_from_list(in_bucket.children)
if item.type != failure_domain: # go deeper
in_bucket = item
continue
if item in result: # collide, pick again
continue
result[rep] = item # OK, found a valid one
break
return result举例来说，某个PG在之前的物理架构中的选择过程可能如下：
rep=0, host=ceph0, go deeper -> osd=osd.0, OK
rep=1, host=ceph1, go deeper -> osd=osd.2, OK
rep=2, host=ceph0, go deeper -> osd=osd.1, OK可见，最后我们选中了同一个host ceph0下的两个OSD。在实际应用中，通常不会以OSD为故障域，而是使用高级的bucket（如host，rack）等作为故障域，那么结果会怎么样呢？以改用host为例：
# rule
step take default
step choose firstn 3 type host
step emit
# choose flow
rep=0, host=ceph0, OK
rep=1, host=ceph1, OK
rep=2, host=ceph2, OK显然，最后只选到了host而没有OSD，那么数据的最终存放位置并没有确定，这个rule的设置不合理。这里有两个解决方案：
1. 再增加一步choose
step take default
step choose firstn 3 type host
step choose firstn 1 type osd
step emit新增的一步会在上述基础上，再以每个选中的host为起点，在host下选择1个OSD。另一个更方便的方案是：
2. 使用chooseleaf
step take default
step chooseleaf firstn 3 type host
step emit这也是大部分情况下选择的方案，其流程更改为：
def choose(take, num_reps, failure_domain, chooseleaf):
result = empty_list
for rep in range(num_reps):
in_bucket = take # start item
while True:
item = random_pick_from_list(in_bucket.children)
if item.type != failure_domain: # go deeper
in_bucket = item
continue
if not is_available(item): # not available, pick again
continue
if chooseleaf and failure_domain != OSD:
result[rep] = choose(item, 1, OSD, False)[0]
else:
result[rep] = item # OK, found a valid one
break
return result这样，在选中一个failure_domain type的bucket后，会递归调用一次choose函数来选择一个该bucket下的OSD。到此，CRUSH rule实现的整体逻辑就清楚了，接下来再进一步分析里面的细节。
random_pick_from_list
这个函数是CRUSH里面非常重要的一部分，代码中一般调用的函数为crush_bucket_choose。每个bucket有一项属性alg(algorithm)，用来确定在该bucket的children列表中如何选出一个合适的item。目前的实践环境中一般使用straw或者straw2算法（早期的alg还有uniform、list、tree等，但均因各种缺陷而被逐渐遗忘；straw2是straw算法的修正改进版本，也是最新的默认选项），这里仅介绍straw2的实现思路。顾名思义，straw类算法可以看作是让bucket下的每个item随机抽一根签（本质上就是一个数值），然后互相比较选出签长最长的那个item；流程如下：
1 def bucket_choose(in_bucket, pgid, trial):
2 for index, item in enumerate(in_bucket.children):
3 draw = crush_hash(item.id, pgid, trial)
4 draw *= item.weight
5 if index == 0 or draw > high_draw:
6 high_item = item
7 high_draw = draw
8 return high_item其中crush_hash可以简单地看成是一个伪随机的hash函数：它接收3个整数作入参，返回一个固定范围内的随机值。同样的输入下其返回值是确定的，但是任何一个参数的改变都会导致其返回值发生变化。Weight是每个item的权重值（对于OSD来说，weight值与硬盘容量成正比；bucket的weight值即其下children weight值的总和），显然line 4可以使得weight值大的item被选中的几率升高。bucket_choose函数有以下几个特点：
- 对于确定的bucket，不同的pgid能返回不同的结果
- 对于确定的bucket和pgid，调整trial值可以获得不同的结果
- 对于确定的pgid和trial值，如果bucket内item增加或删除或调整weight，返回结果要么不变，要么就变更到这个发生变化的item上
这里特点1和2是比较直观的，简单讨论下第三点。假设新增了一个new_item，比对流程可以发现，只需比较原来的high_item和new_item的draw即可，因此返回结果要么仍然是原来的high_item，要么就是new_item，不会出现变为另一个旧的item的情况；同样，假设删除了一个old_item，如果原来它就是high_item，那么会有一个新的item被选择出来，如果它不是high_item，那么返回结果依然是旧的high_item，不会发生变化。
这些特性在一定程度上保证了CRUSH算法的稳定性，即我们期望集群设备的增删仅影响到必要的节点，不要在正常运行的OSD上做无意义的数据迁移。
is_available
这个函数主要是判断指定的item是否可用，如果不可用，则应将其抛弃而重新选择。此函数的判断分为两部分：
- item被选取过，则返回False；这就确保了同一故障域最多被选中一次
- 如果item是OSD且OSD状态不正常，则返回False。这里第一次考虑到了OSD的状态，其实已经超出了CRUSH map的范围，而引入了osdmap的信息，在此仅作简要说明：查看OSD的reweight值（参考命令
ceph osd tree），若其为1.0，则返回True；若其为0（即通常所说out状态）则返回False；若其为中间值，则概率性选择返回值。
while True
在一些特殊情况（如大量OSD处于out状态）下，CRUSH算法不保证一定可以选出要求的所有replicas，因此其设定了一些重试参数，而不会真正陷入死循环。当达到重试次数限制时，会放弃该replica选择。
综上所述，CRUSH rule的实现流程可以描述为：
def choose_firstn(take, num_reps, failure_domain, chooseleaf, pgid):
result, osd_result = empty_list
for rep in range(num_reps):
in_bucket = take # start item
trial = rep
while trial < MAX_TRIES + rep:
item = bucket_choose(in_bucket, pgid, trial)
if item.type != failure_domain: # go deeper
in_bucket = item
continue
if item in result: # collide, pick again
trial += 1
continue
if failure_domain == OSD:
if is_out(item): # check reweight value of item(OSD)
trial += 1
continue
elif chooseleaf:
osd = choose_firstn(item, 1, OSD, False, pgid)
if osd: # OK, found a valid osd
result.append(item)
osd_result.extend(osd)
break
else: # failed to find an available osd
trial += 1
continue
else:
result.append(item) # OK, found a valid one
break
if chooseleaf:
result = osd_result
return result备注说明
- 本节所列的所有伪代码仅用作原理说明，实际的代码流程需要更多的细节考虑，会有较大出入，具体请参考Ceph源码
- Ceph系统中PG的实际操作并不直接以CRUSH的输出为结果，还需考虑其他因素如OSD down、PG temp、primary affinity等
5. Rule流程举例
以下通过几个简化的例子阐述CRUSH算法在实际应用中遇到的一些问题及可能的解决方案。所写流程示例仅针对某个特定的PG，用r代表trial的值，使用的选择策略为：chooseleaf firstn 0 type host。
5.1 正常流程
rep=0, r=0 ---> ceph0, chooseleaf
|_ rep=0, r=0 ---> osd.0, OK
rep=1, r=1 ---> ceph1, chooseleaf
|_ rep=1, r=1 ---> osd.2, OK
rep=2, r=2 ---> ceph2, chooseleaf
|_ rep=2, r=2 ---> osd.4, OK
result = [0, 2, 4]5.2 存在冲突
rep=0, r=0 ---> ceph0, chooseleaf
|_ rep=0, r=0 ---> osd.0, OK
rep=1, r=1 ---> ceph1, chooseleaf
|_ rep=1, r=1 ---> osd.2, OK
rep=2, r=2 ---> ceph0, collide
rep=2, r=3 ---> ceph1, collide
rep=2, r=4 ---> ceph2, chooseleaf
|_ rep=2, r=2 ---> osd.4, OK
result = [0, 2, 4]本例其实也算是正常流程。
5.3 osd.4 out
rep=0, r=0 ---> ceph0, chooseleaf
|_ rep=0, r=0 ---> osd.0, OK
rep=1, r=1 ---> ceph1, chooseleaf
|_ rep=1, r=1 ---> osd.2, OK
rep=2, r=2 ---> ceph2, chooseleaf
|_ rep=2, r=2 ---> osd.4, out
rep=2, r=3 ---> ceph1, collide
rep=2, r=4 ---> ceph2, chooseleaf
|_ rep=2, r=2 ---> osd.4, out
...
result = [0, 2] # 没有选出第三个replica这里的主要原因在于每次递归调用时，r取值为2，且MAX_TRIES被设置成了1。因此，每次在ceph2下都会选中osd.4，而此osd已经out，只能退回上层重试。而上层只有3个host的情况下，没有其余选择，导致最终失败；这也警示我们在故障域个数与逻辑池size相等时，应慎重考虑。
此问题的解决方案也很多，如：
- 增加新的host
- 将
chooseleaf_vary_r参数设置成大于0，可以在递归调用中传入不同的r值，选出ceph2下的其它OSD - 设置
chooseleaf_tries或将chooseleaf_descend_once改为false等，会调整递归调用中的MAX_TRIES值，达到ceph2下多次重试的效果
5.4 osd.2 out
rep=0, r=0 ---> ceph0, chooseleaf
|_ rep=0, r=0 ---> osd.0, OK
rep=1, r=1 ---> ceph1, chooseleaf
|_ rep=1, r=1 ---> osd.2, out
rep=1, r=2 ---> ceph2, chooseleaf
|_ rep=1, r=1 ---> osd.5, OK
rep=2, r=2 ---> ceph2, collide
rep=2, r=3 ---> ceph1, chooseleaf
|_ rep=2, r=2 ---> osd.3, OK
result = [0, 5, 3] # 原来result = [0, 2, 4]，发现在4上的replica被迁移到了5上，属于额外消耗这里的主要原因在于递归调用时r取值等于rep值，在replica发生位置变化时返回了不同的结果。要想结果稳定可以将每次递归调用的r设成一个固定值，如0；这点可以通过将chooseleaf_stable参数设为true实现。
5.5 EC indep
适用于EC的indep类rule的流程大体上与firstn类似，只是需要为没选出的item留好位置，并且在每一次trial中，都遍历一轮所有的replicas。以下以chooseleaf indep 0 type host为例简要说明：
trial 0: result = [UNDEF, UNDEF, UNDEF]
trial 1: rep=0, r=0 ---> ceph0, chooseleaf
|_ rep=0, r=0 ---> osd.0, OK
rep=1, r=1 ---> ceph0, collide
rep=2, r=2 ---> ceph2, chooseleaf
|_ rep=2, r=2 ---> osd.4, OK
result = [0, UNDEF, 4]
trial 2: rep=0, r=3 ---> not UNDEF, continue
rep=1, r=4 ---> ceph1, chooseleaf
|_ rep=1, r=1 ---> osd.2, OK
rep=2, r=5 ---> not UNDEF, continue
result = [0, 2, 4], return可见，trial 1中rep 1选择失败，其位置被留了出来；osd.4直接放在了最后一个replica的位置。在trial 2中，其实仅选择了一个replica，rep=0和rep=2会直接跳过。
6. CRUSH特点
最后就笔者个人理解分析一下CRUSH算法的特点，一言以蔽之，依赖于Hash实现的纯伪随机算法。具体来说：
- 计算独立性：每次计算完全独立，不依赖于集群分配情况或已选择结果（先计算再判断冲突，而不是将冲突项从备选项中移除）；仅依靠多次重试解决选择失败问题
- 稳定性：只有OSD的增删或者weight/reweight变化才会影响到计算结果；正常运行时结果不变
- 可预测性：通过对指定的CRUSH map进行离线计算即可预测出PG的分布情形，且与集群内实际使用完全一致
虽然CRUSH算法为Ceph数据定位提供了有力的技术支持，但也依然存在一些缺陷，如：
- 假失败：因为计算的独立性CRUSH很难处理权重失衡（weight skew）的情形。例如，假设3个hosts的weight值分别为10，10，1，MAX_TRIES为50，现已经选中了前两个hosts，那么第三个replica有大约
(20/21)^50=8.72%的概率选择失败，即使低weight的那个host其实是可用的。因此，在实践中应尽量避免权重失衡的情形出现。 - 故障额外迁移：上节5.4仅解决了OSD状态由in到out的额外迁移，实际环境中还会因为OSD的增删产生一定量的数据额外迁移，对集群造成影响。
- 使用率不均衡：这也是CRUSH被诟病最多的缺陷，即完全依赖Hash的随机导致集群中OSD的容量使用率出现明显失衡（实践中遇到过差40%以上），造成空间浪费。因此，自Luminous版本起，Ceph提供了被称为
upmap的新机制（可以看成记录了一张特例表），用以手动指定PG的分布位置，来达到均衡数据的效果。
不管怎样，相信随着社区的发展和新思路的不断涌现，CRUSH算法的这些缺陷最终都能被一一解决，或是出现更优秀的算法来替代之，让我们一起参与，一起期待。
Reference
- Ceph: A Scalable, High-Performance Distributed File System, by Sage A.Weil, etc.
Notes
本文转载自：tom innetease：CRUSH算法的原理与实现
作者：网易存储团队工程师 徐桑迪。限于作者水平，难免有理解和描述上有疏漏或者错误的地方，欢迎共同交流；部分参考已经在正文和参考文献中列表注明，但仍有可能有疏漏的地方，有任何侵权或者不明确的地方，欢迎指出，必定及时更正或者删除；文章供于学习交流，转载注明出处
发布于 2019-03-15
3. CRUSH是如何工作的？
CRUSH是基于一张描述当前集群资源状态的map（Crush map）按照一定的规则（rules）得到这个OSD列表的。Ceph将系统的所有硬件资源描述成一个树状结构，然后再基于这个结构按照一定的容错规则生成一个逻辑上的树形结构作为Crush map。数的叶子节点是OSD。
3.1 Crush map
一个Crush map一般包括四个部分：
1）配置参数
# begin crush map
tunable choose_local_tries 0
tunable choose_local_fallback_tries 0
tunable choose_total_tries 50
tunable chooseleaf_descend_once 1
tunable straw_calc_version 12）设备，比如说我有一个三个osd组成的ceph环境，那么设备就有三个
# devices
device 0 osd.0
device 1 osd.1
device 2 osd.23）bucket类型。
# types
type 0 osd
type 1 host
type 2 chassis
type 3 rack
type 4 row
type 5 pdu
type 6 pod
type 7 room
type 8 datacenter
type 9 region
type 10 rootceph通过bucket这个逻辑概念来描述这个Crush map树形结构的中间节点。bucket就像是一个容器，一个中间节点就是一个bucket，它的孩子节点就是bucket里包含的items。
4）bucket的具体定义
root default {
id -1 # do not change unnecessarily
# weight 3.000
alg straw
hash 0 # rjenkins1
item rack1 weight 3.000
}id：中间节点的bucket id都是负数，这个主要是和具体的设备相区别的。
weight：bucket的权重
alg：bucket的类型
hash：bucket中使用到的hash算法
item：bucket里包含哪些元素
3.2 Rules
有了Crush map之后，如何一步一步从bucket中选出元素，这个就是有rule来定义的。一个rule就是一系列的操作，一般一个pool都会对应有一个rule。
一个rule的定义是这样的：
rule replicated_ruleset {
ruleset 0
type replicated
min_size 1
max_size 10
step take default
step choose firstn 0 type osd
step emit
}ruleset：id，表明这个rule是属于这个ruleset的。
type：表明这个rule在哪使用，storage drive (replicated) or a RAID。
min_size和max_size用来限定这个rule的使用范围，即当一个pool的副本数小于min_size或者大于max_size的时候不使用这个rule。
step开头的就是三个操作。take是选择一个bucket，然后从这个bucket开始往下遍历，找出OSD。choose是从bucket中找出若干个type类型的项，还有一个chooseleaf操作是bucket中选出若干个leaf节点。至于个数是由firstn后面的数字指定的。如果是0，就按照副本数选择，如果是正数，就按个数来，如果是负数，就按副本数＋负数得到的值来选。最后一步是emit，就是输出结果。
下面是sage论文上的一个例子：
rule和对应的结果是：
take(root) root
select(1, row) row2
select(3, cabinet) cab21, cab23, cab24
select(1, disk) disk2107, disk2313, disk2437
emit
3.3 Crush map中各个bucket权重的计算方法
Crush算法按照rule从bucket中选择item的时候，一般和bucket的权重有关系，每个bucket的权重是所有孩子的权重的和。所以权重是按照自下往上的顺序，依次计算的，也就是先算出osd的权重，然后再算出它父辈的权重。OSD的权重和它的容量有关系，现在的约定是1T容量的权重是1，OSD的权重就是它的容量/1T。
