Ceph 的 crush 算法与一致性 hash 对比介绍

本文分享自天翼云开发者社区《Ceph的crush算法与一致性hash对比介绍》，作者:l****n

首先，我们先回顾下一致性 hash 以及其在经典存储系统中的应用。

一致性 hash 的基本原理

一致性 hash 的基本思想是，有一个 hash 函数，这个 hash 函数的值域形成了一个环(收尾相接：the largest hash value wraps around to the smallest hash value)，然后存储的节点也通过这个 hash 函数随机的分配到这个环上，然后某个 key 具体存储到哪个节点上，是由这个 key 取 hash 函数对应到环的一个位置，然后沿着这个位置顺时针找到的第一个节点负责这个 key 的存储。这样环上的每个节点负责和它前面节点之间的这个区间的数据的存储。

如上图所示，hash 函数的总区间是[A, Z]，有 3 个存储节点分别对应到 F、M 和 S 的位置上，那么 hash 值为 A 或者 Z 的 key 将会顺时针查找它遇到的第一个节点，因此会存储到节点 1 上，同理 hash 值为 K 的 key 存储到第二个节点上。咱们再观察下一致性 hash 在增删节点的时候，数据迁移的情况，在上图的场景中，如果删除节点 2 的话，节点 1 上面的不会发生变化，原来存储在节点 2 上的(F,M]区间会迁移存储到节点 3 上；在上图的场景中，如果在 U 位置增加一个节点的话，原来存储到节点 1 上的(S, F]区间会分割成两个区间其中(S, U]会存储到新的节点上，而(U, F]不发生变化还是存储到节点 1 上。从上面的例子中可以看到，一致性 hash 在增删节点的时候，只影响与其相邻的节点，并且需要迁移的数据最少。

上面这种朴素的一致性 hash 有两个问题，第一个问题是如果节点较少，节点在环上的分布可能不均匀，导致每个节点的负载不均衡，比如上图中场景，如果节点 3 故障被剔除的话，节点 1 和节点 2 的负载会非常的不均衡；第二个问题是不支持异构的机型，比如如果有的存储节点是 4TB 的，有的存储节点是 8TB 的，每个节点对应环上的一个位置，无法感知到节点的权重。为了解决这两个问题，一般都是把每个节点对应到环上的多个位置，称为 vnode，vnode 足够多的话，可以认为是均衡打散的，如果有节点故障下线的话，这个节点在环上对应的 vnode 存储的数据就可以均匀分给其他的 vnode，最终存储到对应的 node 上，因此在增删节点的时候，负载都是在所有的节点中均匀分摊。另外针对异构的机型，比如说 4TB 和 8TB 的节点，8TB 的节点的 vnode 是 4TB 节点的 2 倍就可以了。

如果 vnode 节点和环上的点一一对应的话，可以认为是一致性 hash 的一个特殊的场景，比如说上图中的例子，这个 hash 环一个有 A 到 Z 25 个点(A、Z 重合了)，如果有 25 个 vnode 和其对应的话，这样一致性 hash 只需要记录每个物理 node 节点到 vnode 的映射关系就可以了，会非常的简单。开源 swift 对象存储使用的是这种一致性 hash，参考：https://docs.openstack.org/swift/latest/ring_background.html

在分布式系统中为了保障可靠性一般都是多副本存储的，在 dynamo 存储系统中，用一致性 hash 算法查找到第一个 vnode 节点后，会顺序的向下找更多 vnode 节点，用来存储多副本(中间会跳过同台机器上的 vnode，以达到隔离故障域的要求)，并且第一个 vnode 是协调节点。在开源 swift 对象存储系统中，节点会先分组，比如 3 个一组，形成一个副本对，然后 vnode 会分配到某组机器上，一组机器上会有很多的 vnode，并且这组机器上的 vnode 的 leader 节点在 3 台机器上会打散，分摊压力。

crush 算法的核心思想

crush 算法是一个伪随机的路由选择算法，输入 pg 的 id，osdmap 等元信息，通过 crush 根据这个 pool 配置的 crush rule 规则的伪随机计算，最终输出存储这个 pd 的副本的 osd 列表。由于是伪随机的，只要 osdmap、crush rule 规则相同，在任意的机器上，针对某个 pg id，计算的最终的 osd 列表都是相同的。

crush 算法支持在 crush rule 上配置故障域，crush 会根据故障域的配置，沿着 osdmap，搜索出符合条件的 osd，然后由这些 osd 抽签来决定由哪个 osd 来存储这个 pg，crush 算法内部核心是这个称为 straw2 的 osd 的抽签算法。straw2 的名字来源于 draw straw(抽签：https://en.wikipedia.org/wiki/Drawing_straws)这个短语，针对每个 pg，符合故障域配置条件的 osd 来抽检决定谁来存储这个 pg，osd 抽签也是一个伪随机的过程，谁抽到的签最长，谁赢。并且每个 osd 的签的长度，都是 osd 独立伪随机计算的，不依赖于其他 osd，这样当增删 osd 节点时，需要迁移的数据最少。

如上图的一个示例，这是针对某个 pg 的一次抽签结果，从图中可以看到 osd.1 的签最长，所以 osd.1 赢了，最终 osd.1 会存储这个 pg，在这个时候，如果 osd.4 由于故障下线，osd.4 的故障下线并不会影响其他 osd 的抽签过程，针对这个 pg，最终的结果还是 osd.1 赢，因此这个 pg 不会发生数据的迁移；当然，在上图从场景中，如果 osd.1 下线的话，osd.1 上的 pg 会迁移到其他的 osd 上。增加 osd 节点的情况类似，比如在上图的场景中，如果新增加一个 osd.5 节点的话，每个 osd 都是独立抽签，只有 osd.5 赢的那些 pg 才会迁移到 osd.5 上，对其他的 pg 不会产生影响。因此，理论上，crush 算法也和一致性 hash 一样，在增加删除 osd 节点的时候，需要迁移的数据最少。

另外 straw2 抽签算法也是支持异构的机型的，比如有的 osd 是 4TB，有的 osd 是 8TB，straw2 的抽签算法会保证，8TB 的 osd 抽签赢的概率是 4TB 的 osd 的两倍。背后的原理是，每个 osd 有个 crush weight，crush weight 正比于 osd 的磁盘大小，比如 8TB 的 osd 的 crush weight 是 8 左右，4TB 的 osd 的 crush weight 是 4 左右。然后每个 osd 抽签的过程是，以 osd 的 crush weight 为指数分布的λ，产生一个指数分布的随机数，最后再比大小。

另外在 ceph 中，每个 osd 除了 crush weight，还有个 osd weight，osd weight 的范围是 0 到 1，表示的含义是这个 osd 故障的概率，crush 算法在伪随机选择 pg 放置的 osd 的时候，如果遇到故障的 osd，会进行重试。比如说某个 osd weight 是 0 的话，说明这个 osd 彻底故障了，通过上面 straw2 步骤计算出来的 pg 会 retry 重新分配到其他的 osd 上，如果某个 osd 的 osd weight 是 0.8 的话，这个 osd 上 20%的 pg 会被重新放置到其他的 osd 上。通过把 osd weight 置为 0，可以把某个 osd 节点从集群中临时剔除，通过调整 osd weight 也可以微调 osd 上的 pg 的分布。

总结

ceph 分布式存储系统数据分布的基石 crush 算法，是一个伪随机的路由分布算法，对比一致性 hash，它的核心的优点是元数据少，集群增删 osd 节点时，要迁移的数据少，并且 crush 算法支持异构的机型，支持各种级别的故障域的配置，它的缺点是在实际应用中发现，由于 pg 会占用一定的资源，一般每个 osd 最多 200 个 pg 左右，导致整个集群中 pg 数并不会特别的多，pg 在 osd 上分布并不是非常的均衡，经常需要微调。

参考：

https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf

https://github.com/ceph/ceph/pull/20196

https://docs.openstack.org/swif