开辟者大年夜赛路演 | 12月16日，技巧立异，北京不见不散

分布式存储体系中面对着的重要问题就是若何将大年夜量的数据分布在不合的存储节点上，无论上层接口是KV存储、对象存储、块存储、亦或是列存储，在这个问题上大年夜体是一致的。本文将介绍在分布式存储体系中做数据分布目标及可选的筹划，测验测验着总结他们之间的关系及衡量。

指标

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

平均性(Uniformity) ：不合存储节点的负载应当均衡；

稳定性(Consistency)：每次一个key经由过程数据分布算法获得的分布结不雅应当保持根本稳定，即使再有存储节点产生变更的情况下。

可以看出，这两个目标在必定程度上是互相抵触的，当有存储节点增长或删除时，为了保持稳定应当尽量少的进行数据的移动和从新分派，而如许又势必会带来负载不均。同样寻求极致平均也会导致较多的数据迁徙。所以我们欲望在这两个极端之寄┞芬到一个点以获得合适的平均性和稳定性。除了上述两个根本目标外，工程中还须要大年夜以下几个方面推敲数据分布算法的好坏：

机能可扩大性，这个重要推敲的是算法相对于存储节点范围的时光复杂度，为了全部体系的可扩大性，数据分布算法不该该在集群范围扩大年夜后明显的增长运行时光。

推敲节点异构，实际工程中，不合存储节点之间可能会有很大年夜的机能或容量差别，好的数据分布算法应当能很好的应对这种异构，供给加权的数据平均。

上图是我们的分布式KV存储Zeppelin中的分片方法，Key Space经由过程Hash到分片，分片极其副本又经由过程一层映射到最终的存储节点Node Server。

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

演进

而也恰是因为膳绫擎提到的解耦，相当于将本来的key到节点的映射拆成两层，须要一个新的机制来进行分片到存储节点的映射，因为分片数相对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]。

　　推荐阅读

　　玩脱了，Firefox停止推送引发争议的Mr. Robot扩展

开辟者大年夜赛路演 | 12月16日，技巧立异，北京不见不散 近日，Mozilla 向 Firefox 用户推送了一个名为 Looking Glass 的浏览器扩大插件，这个插件其实是 Mozilla 和 Mr. Robot(黑客军团>>>详细阅读

本文标题：浅谈分布式存储系统数据分布方法

地址：http://www.17bianji.com/lsqh/39872.html

 1/2    1