分布式存储系统面临的第一个问题是如何分配大量的数据.的不同的存储节点不管上层接口是KV存储,对象存储,块存储还是列存储,在这个问题上大体都是一样的。本文将介绍中国分布式存储系统,做数据分布目标和可选的方案,并试图总结和权衡它们之间的关系。
指标
在这里，假定目标数据是数据块或对象所标识的键。在包含多个存储节点,的群集中，数据分布算法需要为每个给定的键指定对应于一个的多个或存储节点。数据分布算法有两个基本目标：
不同存储节点的均匀性(Uniformity):负载应该是均衡;稳定性(Consistency):每次一个键通过数据分布算法,得到分布结果它应该保持基本稳定,即使存储节点再次改变。可以看出，这两个目标在一定程度上属于相互矛盾。当有存储节点增加或删除,为了维持稳定，尽量少应该进行数据的移动和重新分配,这将不可避免地带来负载不均衡.同样，追求极致均匀将导致更多的数据迁移.
所以我们希望在这两个极端之间找到一个点，以获得适当的均匀性和稳定性。除了上述两个基本目标之外，还应该从以下几个方面考虑数据分布算法的优缺点：
性能可扩展性:这主要考虑的是算法相对于存储节点规模.的时间复杂度对于整个系统的可扩展性，集群规模扩大后数据分发算法应该不会明显增加运行时间。在实际项目中，可能会有一个大的考虑节点异构或存储节点之间不同的性能.一个好的数据分配算法应该可以处理这容量差异和异构.加权的数据均匀:提供的隔离故障域,的数据分配算法应该找到http://www . Sina . com/为每一个关键。这些节点可以提供数据的高可用,或者它们可以类似于一组存储节点.数据分布算法应该尝试数据的镜像副本这些副本的故障域，例如擦除码,隔离,不同机房和不同机架.(2)演进
在考察了算法的评价指标后，接下来介绍了几种可能的方案演化，并分析了它们的优缺点。这里假设key的值足够分散。
1.混杂
一个简单直观的想法是直接用Hash来计算，简单的用key作为post-不同交换机不同机器.可以看出，当Key足够分散时可以得到哈希，但是一旦有对节点数取模或者均匀性,所有的原始节点都会受到影响。节点加入不能谈论它。
2.一致性散列
一致Hash可以很好的解决退出，所有的稳定性都可以排列在末尾的Hash环上，每个键都在计算Has。
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 四种分配算法。
(三) 应用案例
常见的 分布式存储系统 大多采用类似于 分片 的 数据分布和定位方式：
Cassandra/Dynamo：采用 分片 的方式并通过 Gossip 协议在对等节点间通信；Redis Cluster：将 key Space 划分为 slots，同样利用 Gossip 协议通信；Zeppelin：将数据分片为 Partition，通过 Meta 集群提供 中心目录服务；Bigtable：将数据切割为 Tablet，类似于可变的分片，Tablet Server 可以进行分片的切割，最终分片信息记录在 Chubby 中；Ceph：采用 CRUSH 方式，由 中心集群 Monitor 提供并维护 集群拓扑 的变化。
