我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:白小姐 > 分布式算法 >

浅谈分布式存储系统的数据分布算法来了解一下吧!

归档日期:04-26       文本归类:分布式算法      文章编辑:爱尚语录

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

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

  稳定性(Consistency):每次一个 key 通过 数据分布算法 得到的 分布结果 应该保持 基本稳定,即使再有存储节点发生变化的情况下。

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

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

  性能可扩展性:这个主要考虑的是算法相对于 存储节点规模 的 时间复杂度。为了整个系统的可扩展性,数据分布算法不应该在集群规模扩大后显著的增加运行时间。

  考虑节点异构:实际工程中,不同 存储节点 之间可能会有很大的 性能 或 容量差异,好的数据分布算法应该能很好的应对这种 异构,提供 加权的数据均匀。

  隔离故障域:为了 数据的高可用,数据分布算法应该为每个 key 找到 一组存储节点,这些节点可能提供的是 数据的镜像副本,也可能是类似 擦除码 的副本方式。数据分布算法应该尽量 隔离 这些副本的故障域,如 不同机房、不同机架、不同交换机、不同机器。

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

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

  一致性 Hash 可以很好的解决 稳定性问题,可以将所有的 存储节点 排列在收尾相接的 Hash 环上,每个 key 在计算 Hash 后会 顺时针 找到先遇到的 存储节点 存放。而当有节点 加入 或 退出 时,仅影响该节点在 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,都无法解决 节点异构 的问题。

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

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

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

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

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

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

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

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

  分片映射信息量:避免 中心目录服务 和 存储节点 及 客户端之间 交互大量的 分片映射信息,而改由 存储节点 或 客户端 自己根据 少量 且 稳定 的集群节点拓扑和确定的规则自己计算分片映射。

  完善的故障域划分:支持 层级 的 故障域控制,将 同一分片 的 不同副本 按照配置划分到 不同层级 的 故障域中。

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

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

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

  Ceph:采用 CRUSH 方式,由 中心集群 Monitor 提供并维护 集群拓扑 的变化。

  本网站依据国家相关规定准备了相应的稿酬,但由于客观原因无法支付。如您是这篇文章或图片的著作权人或其他权利人,请与本网站联系。本网站在确认您的身份后将予以支付。

本文链接:http://frankstella.net/fenbushisuanfa/230.html