分布式存储中的数据分布策略

本文提出一种分层的数据放置策略 DPRD。DPRD 主要应用于分布式存储系统中，目前 DPRD 应用于 Zeppelin 中。DPRD 策略的想法脱胎于 CRUSH 算法，吸取了 CRUSH 算法中最显著的故障域分离的特性，同时对扩容和缩容场景做出了效果显著的优化。

CRUSH 简介

CRUSH 是应用于 CEPH 的数据分布算法，它是一个分层的，区分故障域的分布式算法。在 CRUSH 算法中，对于不同的物理设备统一抽象成了 bucket，每个结点都是一个 bucket，其对应的物理结构各不相同。例如下图中的 root，row（机架）， cabinet（机柜）， disk 都是 bucket 的一种。

以下是对应的 CRUSH 算法分层部分的介绍，

• 从root bucket开始, 对应Rule take(root)。

• 在下一层选择一个row 对应Rule select(1, row)。这一层选出的是row2。

• 下一层将上一层的输出当作这一层的输入，遵循Rule select(3, cabinet), row2中选三个cabinet。最终的这一层输出是cab21, cab23, cab24。

• 下一层对应Rule select(1, disk)。在cab21, cab23, cab24 中分别选一个disk。最终emit输出是disk2107, disk2313, disk2437。

CRUSH 如何实现 Rule 中的 select N 这个操作的呢？

对于每一个 bucket，CRUSH 的 paper 提供了几种不同的选择策略（Uniform, List, Tree, Straw）。如果有兴趣的同学可以读下论文。

这里简单介绍一下他的默认策略 Straw：

Straw 翻译过来是抽签，每个桶会计算其每个子节点的”参数值”，然后抽取一个最大的作为选中 bucket，其”参数值”为的 weight * hash。由于 hash 计算本身的随机特性，哈希值的变化会导致本来应该移动到 A 节点的 PG，移动到了 B 节点。造成了额外的移动。

CRUSH 迁移策略

CEPH 的迁移是一个非常复杂的过程，涉及到其内部许多其它的机制，这里只简要说明与 CRUSH 算法相关的步骤。CEPH 的迁移步骤概述如下：

1.收到 map 的更新信息。

2.重新计算 pg 对应的 osd 信息。

3.对比之前的 pg 和 osd 的对应关系，得知如何迁移。

例如 ：

由老的 map 信息计算得知 pg 101 对应的 osd[1,2,3], 新的 map 信息计算得知 pg 101 对应 osd[1,2,4], 所以迁移方向应该是从 osd3 到 osd4

上图是 CRUSH 论文中提到的数据迁移现象。由于新 bucket 的加入，新加入节点的上层 bucket 权重都会改变，在做 select N 操作的时候，由于 hash 值的存在，同样权重的情况下选择到了其它的分支，这样就带来了额外的迁移。如图所示，流向新添加节点的 pg 是必要的移动，流向其他节点的 pg 是额外的迁移。

以上就是 CRUSH 的数据迁移策略。

Is CRUSH Perfect? Em……NO!

这部分主要提出 CRUSH 的两个问题，引出 DPRD 策略。

1、CRUSH 默认使用的 straw bucket 会造成 2 到 3 倍于理论迁移率的移动。

2、对于 pg 分布是否平衡文中没有详细的讨论。

在调研阶段对 CRUSH 进行了测试：

4(rack) * 10(host) * 10(node) 拓扑下 1024 * 3 副本

对于每个结点分配的 pg 比较少的情况，分布不均匀的现象比较明显。

2 * 10 * 2 拓扑下 1024 * 3 副本

对于每个结点分配 pg 比较多的情况下，分布不均匀的现象会有一定的缓解, 但是依旧离理论值很远。

具体测试数据位于测试数据中 PG 分布平衡性测试部分。

DPRD 来了！

DPRD Target：

(在分层拓扑，故障域分离情形下)

1, 副本的移动率应该尽可能的贴近理论值

2, 副本的分布应该尽可能的贴近均匀分布

Service：

1, 副本分布的初始化过程

2, 扩容时副本的重新分布

3, 缩容时副本的重新分布

DPRD 策略

pg 和 osd 是 CEPH 中的概念, 对应到 Zeppelin 中分别为 partition 和 node

定义：

Factor：partition / weight

代表单位 weight 上所分布的 partition 数量，这个数量来衡量 bucket 负担是否过于重或者过于轻。partition 倾向于在同一层中选择负担比较轻的 bucket。

Base Factor: 1/ weight

partition 为 1 的情况。代表移动一个 partition 对于 Factor 的影响。

Average Factor：sum of partition / sum of weight

平均的 Factor 参数，扩容或缩容过程中，衡量 bucket 是否均衡的参数。

1, 副本分布的初始化过程

DPRD 策略借鉴了 CRUSH 中的分层结构，从上层到下层遵循 Rule 依次进行 partition 选择。但是，对于 Select N 策略，DPRD 跟 CRUSH 有很大的区别。Select N 策略中，parent bucket 计算子节点当前的“参数”值，然后选择前 N 个子节点作为这次 select N 的输出。所谓的参数值，在 DPRD 策略中是 Factor（partition/weight） 代表了每个子节点的重量负担，每一次的 partition 选择都应该选择当前负担小的 N 个子节点。这样，每一次 partition 都会放置到本层相对于轻的 bucket 中，以此来保证这一层的 bucket 都不会过重或者过轻。

具体的数据见 测试数据 Partition 初始化。

2, 扩容时副本的重新分布

在添加 bucket 的时候会造成“不均衡”。

在 rack2 下面添加 bucket 会导致 rack 层 weight 增加，以至于 average factor 变小。最终进行迁移之前，rack5 由于本身的 Factor 值没变，average factor 变小，rack5 有可能高于 average factor“很多”。rack2 由于 Factor 变小幅度更大，有可能低于 average factor“很多”。 这样，由于新添加的 bucket 会有可能造成本层的不平衡（rack5 超出 average factor，rack2 低于 acerage factor）。下面定义 DPRD 中的“不平衡”概念，以及 DPRD 是如何实现平衡的。

定义“不均衡”

• 所谓不均衡是bucket的Factor超出average factor太多或者小于average factor太多

• 超出均值情况: factor - average_factor > base_factor

• 低于均值情况: average_factor - factor > base_factor

如下图所示, 每一层经过均衡的过程之后，parent bucket 的所有的 children bucket 都应该落在平衡区域内。

整体上来看, DPRD 策略是从上层到下层做均衡，确保每一层都是均衡的。从 root 层开始，其 children 为 rack，由于 rack5 高于 average factor， rack2 低于 average factor。DPRD 策略会在 rack5 子树的 node 中选择一个 partition 移动到 rack2 中。直到 rack 层的每一个 bucket 都均衡之后，DPRD 策略会再均衡下一层(host 层)，直到遍历整棵树。

问题来了，我们应该选择 rack5 种哪一个 node 中的哪一个 partition 呢？

DPRD 选择策略

Target：从 rack5 子树选出一个 bucket 的 partition 移动到 rack2 中

Step1: 从 rack5 children 中选择出正向偏离 average factor 最远的 host（host52）如下图所示。

Step2: 遵循 step1 的原则向下递归选择 bucket，直到选择一个 node bucket。

Step3: 在 node bucket 中选择一个 rack2 中没有的 partition 移动到 rack2。

如果没有能够在 Step3 中选择出一个 partition 那么重新回到 Step1 选择 host53，继续流程。

至此，上文中说明了 DPRD 扩容的 partition 迁移策略。具体的测试结果位于测试数据中扩容测试部分。

3, 缩容时副本的重新分布

最直观的实现就是把要去除的 bucket 里边的 partition 从拓扑里面全都移除掉，包括该 partition 在其他 node 上的副本。然后再从 root 进行副本的初始化过程。这样会带来 3 倍于理论移动率的迁移。

DPRD 的实现：

只去除需要删除的 bucket 中的 partition 副本，同时为保障 choose_n 的故障域策略，需要在 choose_n 的那一层，在从没有该 partition 副本的 bucket 中选择出一个新的副本放置位置。

Step 1.记录 partition 10 在 choose_n 层的位置(rack3, rack4, rack5)

Step 2. 移除要删除的 bucket （bucket100）

Step 3. 在 choose_n 层选择一个目前没有 partition 10 的 bucket（rack1 或者 rack2）

Step 4. 从选出的 bucket 开始做副本的初始化过程。

至此，上文中介绍了 DPRD 缩容的 partition 迁移策略。具体的测试结果位于测试数据中缩容测试部分。

总结

本文提出了一种 DPRD 的数据分布策略，在保证故障域分离的情况下，尽量保证数据的均匀分布。同时本文讨论了在扩容和缩容时，DPRD 如何保证尽量贴近理论极限的数据迁移。

本文转载自公众号 360 云计算（ID：hulktalk）。

原文链接：

https://mp.weixin.qq.com/s/4KZYtmM01xjI2ROBAas_fA