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

快来打我* 2022-01-12 02:51 246阅读 0赞

### 前言 ###

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

### **正文** ###

## (一) 指标 ##

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

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

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

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

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

## (二) 演进 ##

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

### 1. Hash ###

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

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

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

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

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

如上图所示，假设每个桶 **当前上限** 是 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\]。

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

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

### 5. 分片 ###

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

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

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

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

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

### 6. CRUSH算法 ###

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

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

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

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

当 **节点变化** 时，由于 **节点拓扑** 的变化，会影响 **少量分片** 数据进行迁移，如下图是加入 **新节点** 引起的 **数据迁移**。通过良好的 **分配算法**，可以得到很好的 **负载均衡** 和 **稳定性**，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 提供并维护 **集群拓扑** 的变化。

转载于:https://juejin.im/post/5d00bb8f6fb9a07ef63fd611