注意
本文档适用于 Ceph 的开发版本。
CRUSH MSR（多步重试）
动机
传统的 CRUSH 有一个重要的限制：包含多个 choose 步骤的规则，如果遇到一个 out OSD，则无法重试先前的步骤。例如，对于像下面这样的规则
rule replicated_rule_1 {
...
step take default class hdd
step chooseleaf firstn 3 type host
step emit
}
人们可能会期望，如果特定主机上的所有 OSD 都被标记为 out，包含这些 OSD 的映射最终会落在另一台主机上（前提是有足够的主机）。事实上，情况就是如此。此外，如果一台主机上 1/8 的 OSD 被标记为 out，则映射到该主机的大约 1/8 的 PG 将被重新映射到其他主机，从而保持每个 OSD 的总体利用率均衡。
相反，假设规则是这样编写的
rule replicated_rule_1 {
...
step take default class hdd
step choose firstn 3 type host
step choose firstn 1 type osd
step emit
}
只要没有 OSD 被标记为 out，行为就会非常相似。但是，如果一个 OSD 被标记为 out，映射到该 OSD 的任何 PG 将被重新映射到同一主机上的其他 OSD，导致这些 OSD 相对于其他主机上的 OSD 过度利用。此外，如果一台主机上的所有 OSD 都被标记为 out，碰巧映射到该主机的映射将失败，导致 PG 不足。
只要目标是将 N 个 OSD 分布到 N 个故障域中，解决方案就是使用上面的 chooseleaf 变体。然而，考虑一个用例，我们想要将一个 8+6 EC 编码分布到 4 台主机上，以容忍一台主机的丢失和另一台主机上一个 OSD 的丢失，同时存储开销为 1.75 倍。规则必须看起来像这样
rule ecpool-86 {
...
step take default class hdd
step choose indep 4 type host
step choose indep 4 type osd
step emit
}
这确实将多达 16 个 OSD 分布到 4 台主机上（对于 8+6 代码，它会将 4 个 OSD 放在前 3 台上，最后 2 个 OSD 放在最后一台），并且满足了我们的故障要求。但是，出于上面概述的原因，如果还有其他主机可以重新平衡，当 OSD 被标记为 out 时，它的表现会很差。chooseleaf 在这里不是一个解决方案，因为它不支持在指定的类型下映射多个叶子。
MSR
CRUSH MSR（多步重试）规则通过使用不同的下降算法来解决上述问题，该算法在遇到 out OSD 时会重试所有步骤。经典的 CRUSH 是广度优先的（对于每个步骤，它在进入下一步之前完全填充向量），而 MSR 规则是深度优先的——对于每个选择，我们在继续下一个选择之前递归地下降所有步骤。上面的用例可以通过以下规则满足
rule ecpool-86 {
type msr_indep
...
step take default class hdd
step choosemsr 4 type host
step choosemsr 4 type osd
step emit
}
正如顶部的 chooseleaf 示例一样，当 OSD 被标记为 out 时，只要有额外的 OSD 可用，这些 OSD 就会按比例重新映射到其他主机。有关这如何在仍保持故障域隔离的情况下工作的详细信息，请参阅 mapper.c:crush_msr_choose 中的注释。
规则结构
CRUSH MSR 规则是类型为 CRUSH_RULE_TYPE_MSR_FIRSTN 或 CRUSH_RULE_TYPE_MSR_INDEP 的 crush 规则（参见 mapper.c: rule_type_is_msr）。与经典的 crush 规则不同，单个步骤不指定 firstn 或 indep。相反，输出顺序由整个规则的规则类型定义。
MSR 规则与传统规则有一些结构差异
规则类型决定了映射是 FIRSTN 还是 INDEP。因为下降可以重试步骤，所以步骤单独指定输出顺序并没有真正意义，而且我不太清楚有什么用例会从中受益。
MSR 规则*必须*构造为配置步骤（CRUSH_RULE_SET_CHOOSE_MSR*）的（可能为空的）前缀，后跟一系列 EMIT 块，每个块由一个 TAKE 步骤、一系列 CHOOSE_MSR 步骤组成，并以一个 EMIT 步骤结束。
MSR 步骤必须是 choosemsr。choose 和 chooseleaf 不允许。
工作空间
MSR 规则对工作空间也有不同的要求。传统的 CRUSH 需要 3 个大小为 result_max 的向量用于工作空间——两个用于在处理每个规则时交替使用，一个用于 chooseleaf。MSR 规则需要 N 个向量，其中 N 是最长的 EMIT 块中 choosemsr 步骤的数量，因为它需要保留作为每次下降的一部分所做的所有选择。
有关详细信息，请参阅 mapper.h/c:crush_work_size, crush_msr_scan_rule。
实施
对于类型为 CRUSH_RULE_TYPE_MSR_* 的规则（参见 mapper.c:rule_type_is_msr），mapper.h/c:crush_do_rule 内部会分支到 mapper.c:crush_msr_do_rule。
mapper.c 中与 MSR 相关的功能会使用有关算法的更多详细信息进行注释。