浅谈分布式存储系统的数据分布算法

待我称王封你为后i 2022-05-12 20:56 179阅读 0赞

# 前言 #

**分布式存储系统** 面临着的首要问题，就是如何将 **大量的数据** 分布在 **不同的存储节点** 上。无论上层接口是 `KV` **存储**、**对象存储**、**块存储**、亦或是 **列存储**，在这个问题上大体是一致的。本文将介绍如何 **分布式存储系统** 中 **做数据分布目标** 及可选的 **方案**，并试着总结和权衡他们之间的关系及。

# 正文 #

## (一) 指标 ##

这里假设 **目标数据** 是以 `key` 标识的 **数据块** 或 **对象**。在一个包含 **多个存储节点** 的集群中，**数据分布算法** 需要为每一个给定的 `key` 指定 **一个** 或 **多个** 对应的 **存储节点** 负责，**数据分布算法** 有两个基本目标：

*  **均匀性(Uniformity)**：不同存储节点的 **负载** 应该 **均衡**；
 *  **稳定性(Consistency)**：每次一个 `key` 通过 **数据分布算法** 得到的 **分布结果** 应该保持 **基本稳定**，即使再有存储节点发生变化的情况下。

可以看出，这两个目标在一定程度上是 **相互矛盾** 的。当有 **存储节点增加或删除** 时，为了保持稳定应该 **尽量少** 的进行 **数据的移动** 和 **重新分配**，而这样又势必会带来 **负载不均衡**。同样追求 **极致均匀** 也会导致较多的 **数据迁移**。

所以我们希望在这两个极端之间，找到一个点以获得合适的均匀性和稳定性。除了上述两个基本目标外，工程中还需要从以下几个方面考虑数据分布算法的优劣：

1.  **性能可扩展性**：这个主要考虑的是算法相对于 **存储节点规模** 的 **时间复杂度**。为了整个系统的可扩展性，数据分布算法不应该在集群规模扩大后显著的增加运行时间。
2.  **考虑节点异构**：实际工程中，不同 **存储节点** 之间可能会有很大的 **性能** 或 **容量差异**，好的数据分布算法应该能很好的应对这种 **异构**，提供 **加权的数据均匀**。
3.  **隔离故障域**：为了 **数据的高可用**，数据分布算法应该为每个 `key` 找到 **一组存储节点**，这些节点可能提供的是 **数据的镜像副本**，也可能是类似 **擦除码** 的副本方式。数据分布算法应该尽量 **隔离** 这些副本的故障域，如 **不同机房**、**不同机架**、**不同交换机**、**不同机器**。

## (二) 演进 ##

看完算法的评价指标后，接下来介绍一些可能的方案演进，并分析他们的优劣。这里假设 `key` 的值足够分散。

### 1. Hash ###

一个简单直观的想法是直接用 `Hash` 来计算，简单的以 `Key` 做 **哈希** 后 **对节点数取模**。可以看出，在 `key` 足够分散的情况下，**均匀性** 可以获得，但一旦有 **节点加入** 或 **退出** 时，所有的原有节点都会受到影响。**稳定性** 无从谈起。

### 2. 一致性Hash ###

![16455ec5b670a4be_w_576_h_412_f_png_s_38351][]

一致性 `Hash` 可以很好的解决 **稳定性问题**，可以将所有的 **存储节点** 排列在收尾相接的 `Hash` 环上，每个 `key` 在计算 `Hash` 后会 **顺时针** 找到先遇到的 **存储节点** 存放。而当有节点 **加入** 或 **退出** 时，仅影响该节点在 `Hash` 环上 **顺时针相邻** 的 **后续节点**。但这有带来 **均匀性** 的问题，即使可以将存储节点等距排列，也会在 **存储节点个数** 变化时带来 **数据的不均匀**。而这种可能 **成倍数的不均匀** 在实际工程中是不可接受的。

### 3. 带负载上限的一致性Hash ###

一致性 `Hash` 有 **节点变化时不均匀**的问题。`Google` 在 `2017` 年提出了 Consistent Hashing with Bounded Loads 来控制这种 **不均匀的程度**。简单的说，该算法给 `Hash` 环上的每个节点一个 **负载上限** 为 `1 + e` 倍的 **平均负载**，这个 `e`可以自定义。当 `key` 在 `Hash` 环上 **顺时针** 找到合适的节点后，会判断这个节点的 **负载** 是否已经 **到达上限**，如果 **已达上限**，则需要继续找 **之后的节点** 进行分配。

![16455ec5b6ac1b85_w_431_h_397_f_png_s_46890][]

如上图所示，假设每个桶 **当前上限** 是 `2`，红色的小球按序号访问，当编号为 `6` 的红色小球到达时，发现顺时针首先遇到的 `B（3，4）`，`C（1，5）`都已经 **达到上限**，因此最终放置在桶 `A` 里。

这个算法最吸引人的地方在于 **当有节点变化** 时，需要迁移的数据量是 `1/e^2` 相关，而与 **节点数** 或 **数据数量** 均无关。

也就是说当 **集群规模扩大** 时，**数据迁移量** 并不会随着显著增加。另外，使用者可以通过调整 `e` 的值来控制 **均匀性** 和 **稳定性** 之间的权衡，就是一种 **以时间换空间** 的算法。总体来说，无论是 **一致性** `Hash` 还是 **带负载限制** 的 **一致性** `Hash`，都无法解决 **节点异构** 的问题。

### 4. 带虚拟节点的一致性Hash ###

为了解决 **负载不均匀** 和 **异构** 的问题，可以在 **一致性** `Hash` 的基础上引入 **虚拟节点**。即 `hash` 环上的 **每个节点** 并不是 **实际** 的 **存储节点**，而是一个 **虚拟节点**。实际的 **存储节点** 根据其 **不同的权重**，对应 **一个** 或 **多个虚拟节点**，所有落到相应虚拟节点上的 `key` 都由该 **存储节点负责**。

如下图所示，存储节点 `A` 负责 `(1,3]`，`(4,8]`，`(10, 14]`，存储节点 `B` 负责 `(14,1]`，`(8,10]`。

![16455ec5b6940588_w_700_h_338_f_png_s_64488][]

这个算法的问题在于，一个 **实际存储节点** 的 **加入** 或 **退出**，会影响 **多个虚拟节点**的重新分配，进而引起 **很多节点** 参与到 **数据迁移** 中来。

另外，实践中将一个 **虚拟节点** 重新分配给 **新的实际节点** 时，需要将这部分数据 **遍历** 出来 **发送给新节点**。我们需要一个更合适的 **虚拟节点切分** 和 **分配方式**，那就是 **分片**。

### 5. 分片 ###

**分片** 将 **哈希环** 切割为 **相同大小的分片**，然后将这些 **分片** 交给 **不同的节点** 负责。

注意这里跟上面提到的 **虚拟节点** 有着很 **本质的区别**：**分片的划分和分片的分配被解耦**。

一个 **节点退出** 时，其所负责的 **分片** 并不需要 **顺时针合并** 给之后节点，而是可以更灵活的 **将整个分片** 作为一个 **整体** 交给 **任意节点**。在实践中，一个 **分片** 多作为 **最小的数据迁移** 和 **备份单位**。

![16455ec5b68eee2d_w_546_h_462_f_png_s_34445][]

而也正是由于上面提到的 **解耦**，相当于将原先的 `key` 到 **节点** 的 **映射** 拆成了两层。需要一个 **新的机制** 来进行 **分片** 到 **存储节点** 的 **映射**。由于 **分片数** 相对 `key` 空间已经很小并且 **数量确定**，可以更精确地初始设置，并引入 **中心目录服务** 来根据 **节点存活** 修改 **分片的映射关系**。同时将这个 **映射信息** 通知给所有的 **存储节点** 和 **客户端**。

![16455ec5b9a03c5b_w_700_h_388_f_png_s_49049][]

上图是 **分布式KV存储** `Zeppelin`中的 **分片方式**，`Key Space` 通过 `Hash` 到 **分片**，**分片及其副本** 又通过一层映射到 **最终的存储节点** `Node Server`。

### 6. CRUSH算法 ###

`CRUSH` 算法本质上也是一种 **基于分片** 的数据分布方式，其试图在以下几个方面进行优化：

*  **分片映射信息量**：避免 **中心目录服务** 和 **存储节点** 及 **客户端之间** 交互大量的 **分片映射信息**，而改由 **存储节点** 或 **客户端** 自己根据 **少量** 且 **稳定** 的集群节点拓扑和确定的规则自己计算分片映射。
 *  **完善的故障域划分**：支持 **层级** 的 **故障域控制**，将 **同一分片** 的 **不同副本** 按照配置划分到 **不同层级** 的 **故障域中**。

**客户端** 或 **存储节点** 利用 `key`、**存储节点** 的 **拓扑结构** 和 **分配算法**，独立的进行 **分片位置** 的计算，得到一组负责对应 **分片** 及 **副本** 的 **存储位置**。

如图所示是 **一次定位** 的过程，最终选择了一个 `row` 下的 `cab21`，`cab23`，`cab24` 三个机柜下的三个存储节点。

![16455ec5b6abde68_w_700_h_254_f_png_s_72421][]

当 **节点变化** 时，由于 **节点拓扑** 的变化，会影响 **少量分片** 数据进行迁移，如下图是加入 **新节点** 引起的 **数据迁移**。通过良好的 **分配算法**，可以得到很好的 **负载均衡** 和 **稳定性**，`CRUSH` 提供了 `Uniform`、`List`、`Tree`、`Straw` 四种分配算法。

## (三) 应用案例 ##

常见的 **分布式存储系统** 大多采用类似于 **分片** 的 **数据分布和定位方式**：

1.  **Cassandra/Dynamo**：采用 **分片** 的方式并通过 `Gossip` 协议在对等节点间通信；
2.  **Redis Cluster**：将 `key Space` 划分为 `slots`，同样利用 `Gossip` 协议通信；
3.  **Zeppelin**：将数据分片为 `Partition`，通过 `Meta` 集群提供 **中心目录服务**；
4.  **Bigtable**：将数据切割为 `Tablet`，类似于可变的分片，`Tablet Server` 可以进行分片的切割，最终分片信息记录在 `Chubby` 中；
5.  **Ceph**：采用 `CRUSH` 方式，由 **中心集群** `Monitor` 提供并维护 **集群拓扑** 的变化。

--------------------

欢迎关注技术公众号： 零壹技术栈

![零壹技术栈][16455ec5dcc40392_w_258_h_258_f_jpeg_s_16109]

本帐号将持续分享后端技术干货，包括虚拟机基础，多线程编程，高性能框架，异步、缓存和消息中间件，分布式和微服务，架构学习和进阶等学习资料和文章。

[16455ec5b670a4be_w_576_h_412_f_png_s_38351]: https://user-gold-cdn.xitu.io/2018/7/1/16455ec5b670a4be?w=576&h=412&f=png&s=38351
[16455ec5b6ac1b85_w_431_h_397_f_png_s_46890]: https://user-gold-cdn.xitu.io/2018/7/1/16455ec5b6ac1b85?w=431&h=397&f=png&s=46890
[16455ec5b6940588_w_700_h_338_f_png_s_64488]: https://user-gold-cdn.xitu.io/2018/7/1/16455ec5b6940588?w=700&h=338&f=png&s=64488
[16455ec5b68eee2d_w_546_h_462_f_png_s_34445]: https://user-gold-cdn.xitu.io/2018/7/1/16455ec5b68eee2d?w=546&h=462&f=png&s=34445
[16455ec5b9a03c5b_w_700_h_388_f_png_s_49049]: https://user-gold-cdn.xitu.io/2018/7/1/16455ec5b9a03c5b?w=700&h=388&f=png&s=49049
[16455ec5b6abde68_w_700_h_254_f_png_s_72421]: https://user-gold-cdn.xitu.io/2018/7/1/16455ec5b6abde68?w=700&h=254&f=png&s=72421
[16455ec5dcc40392_w_258_h_258_f_jpeg_s_16109]: https://user-gold-cdn.xitu.io/2018/7/1/16455ec5dcc40392?w=258&h=258&f=jpeg&s=16109