前言分布式存储系统面临的首要问题是如何将大量数据分布在不同的存储节点上。不管上层接口是KV存储、对象存储、块存储还是列存储，在这个问题上大体上是一致的。本文将介绍如何在分布式存储系统中制定数据分布目标和备选方案，并尝试总结和权衡它们之间的关系。Text(1)这里的索引假定目标数据是一个数据块或由一个键标识的对象。在包含多个存储节点的集群中，数据分发算法需要为每个给定的键指定一个或多个对应的存储节点。数据分布算法有两个基本目标：均匀性：不同存储节点的负载应该是平衡的；一致性：每个key的数据分发算法得到的分发结果应该保持基本稳定，即使存储节点发生变化。可见，这两个目标有些矛盾。在添加或删除存储节点时，为了保持稳定性，应尽可能少地进行数据移动和重新分配，这将不可避免地导致负载不平衡。同样追求极致的统一性，也会导致更多的数据迁移。所以我们希望在这两个极端之间找到一个点，以获得合适的均匀性和稳定性。除了以上两个基本目标，数据分布算法的优劣在工程上还需要考虑以下几个方面：性能可扩展性：这里主要考虑算法的时间复杂度相对于存储节点的大小.为了整个系统的可扩展性，数据分布算法在集群规模增加后不应显着增加运行时间。考虑节点异构性：在实际工程中，不同存储节点之间可能存在较大的性能或容量差异。一个好的数据分布算法应该能够应对这种异构性，均匀地提供加权数据。隔离故障域：为了数据的高可用性，数据分发算法应该为每个键找到一组存储节点。这些节点可能会提供数据的镜像副本，或类似于纠删码的副本。数据分布算法应该尽量隔离这些副本的故障域，比如不同的机房、不同的机架、不同的交换机、不同的机器。(2)演化看完算法的评价指标，我们将介绍一些可能的解演化，并分析其优缺点。这假设键的值足够分散。1、Hash一个简单直观的思路就是直接用Hash来计算，简单的用Key做hash然后对节点个数取模。可见，当key充分分散时可以获得均匀性，但一旦有节点加入或退出，所有原有节点都会受到影响。稳定性无从谈起。2.ConsistentHashConsistentHash可以很好的解决稳定性问题。所有的存储节点都可以安排在末端相连的哈希环上。计算完Hash后，每个key会顺时针找到第一个遇到的存储节点存放。并且当一个节点加入或退出时，只会影响该节点在哈希环上顺时针相邻的后续节点。但这有统一性的问题。即使存储节点可以等距排列，当存储节点数量变化时，数据也会不均匀。而这种可能的倍增不均匀度在实际工程中是不能接受的。3.ConsistencyHashwithloadcapConsistencyHash存在节点变化时不均匀的问题。谷歌在2017年提出了ConsistentHashingwithBoundedLoads来控制这种不均匀性。简单的说，这个算法给Hash环上的每个节点一个平均负载，负载上限为1+e倍，这个e是可以自定义的。当key在Hash环上顺时针方向找到一个合适的节点时，会判断这个节点的负载是否已经达到上限。如果已经达到上限，则需要继续寻找下一个节点进行分发。如上图所示，假设当前每个桶的上限为2，按照序号访问红球。当编号为6的红球到达时，发现最先遇到的顺时针方向的B(3,4),C(1,5)已经达到了上限，所以最后都放到了A桶中。最吸引人的东西关于这个算法的是，当有节点变化时，需要迁移的数据量与1/e^2有关，与节点数或数据量无关。也就是说，当集群规模扩大时，数据迁移量不会有明显的增加。此外，用户可以通过调整e的值来控制均匀性和稳定性之间的权衡，这是一种以时间换空间的算法。一般来说，一致性Hash和带负载限制的一致性Hash都不能解决节点异构的问题。4.ConsistentHashwithvirtualnodes为了解决负载不均匀和异构的问题，可以在consistentHash的基础上引入虚拟节点。也就是说，哈希环上的每个节点都不是一个实际的存储节点，而是一个虚拟节点。实际存储节点根据其不同的权值对应一个或多个虚拟节点，所有落在对应虚拟节点上的key都由存储节点负责。如下图所示，存储节点A负责(1,3],(4,8],(10,14]，存储节点B负责(14,1],(8,10]。该算法的问题在于，一个实际存储节点的添加或退出会影响多个虚拟节点的重新分配，这会导致很多节点参与数据迁移。另外，当将一个虚拟节点重新分配给一个新的实际节点时实践中，这部分需要将数据遍历并发送到新的节点，我们需要一种更合适的虚拟节点切分和分配方式，即分片。然后把这些分片交给不同的节点，注意和上面说的虚拟节点有一个本质区别：分片的划分和分片的分配是解耦的，当一个节点退出的时候，它负责的分片不需要要按顺序而不是顺时针合并到subsequent节点，整个shard可以更灵活的整体交给任意一个节点。在实践中，分片主要用作最小的数据迁移和备份单元。而也正是因为上面提到的Decoupling，相当于把原来的key-to-node映射拆分成了两层。需要一种新的机制来将分片映射到存储节点。由于分片的数量相对于键空间较小，数量是确定的，因此可以更改精确的初始设置，引入中心目录服务，根据节点的存活情况修改分片的映射关系。同时，将该映射信息通知给所有存储节点和客户端。上图是分布式KV存储Zeppelin中的sharding方式，KeySpace通过Hash传递给shard，shard及其副本通过一层映射到最终的存储节点NodeServer。6.CRUSH算法CRUSH算法本质上是一种基于分片的数据分发方法。两方面优化：分片映射信息量：避免中心目录服务、存储节点、客户端之间交换大量的分片映射信息，而让存储节点或客户端自己根据少量稳定的集群节点来决定topology和rules自己计算shardmap。完善的故障域划分：支持分级故障域控制，将同一个shard的不同副本根据配置划分为不同级别的故障域。客户端或存储节点使用密钥、存储节点的拓扑结构和分配算法独立计算分片位置，得到一组负责相应分片和复制的存储位置。如图所示，是一次性定位的过程，最终选中一排下cab21、cab23、cab24三个机柜下的三个存储节点。当节点发生变化时，由于节点拓扑发生变化，会影响少量零散数据的迁移。下图是新增节点引起的数据迁移。通过一个好的分配算法，可以获得很好的负载均衡和稳定性。CRUSH提供了四种分配算法：Uniform、List、Tree和Straw。(3)应用案例常见的分布式存储系统大多采用类似sharding的数据分布和定位方式：Cassandra/Dynamo：使用sharding，peer节点之间通过Gossip协议进行通信；RedisCluster：使用keySpace划分槽，也使用Gossip协议进行通信；Zeppelin：将数据划分为Partitions，通过Meta集群提供中央目录服务；Bigtable：将数据分成Tablets，类似于变量分片，TabletServer可以进行分片Cutting，最终的分片信息记录在Chubby中；Ceph：采用CRUSH方式，中央集群监视器提供和维护集群拓扑的变化。
