数据分布方式

所谓分布式系统顾名思义就是利用多台计算机协同解决单台计算机所不能解决的计算、存储等问题。

单机系统与分布式系统的最大的区别在于问题的规模，即计算、存储的数据量的区别。

将一个单机问题使用分布式解决，首先要解决的就是如何将问题拆解为可以使用多机分布式解决，使得分布式系统中的每台机器负责原问题的一个子集。

由于无论是计算还是存储，其问题输入对象都是数据，所以如何拆解分布式系统的输入数据成为分布式系统的基本问题，本文称这样的数据拆解为数据分布方式，在本节中介绍几种常见的数据分布方式，最后对这几种方式加以对比讨论。

哈希方式

哈希方式是最常见的数据分布方式，其方法是按照数据的某一特征计算哈希值，并将哈希值与机器中的机器建立映射关系，从而将不同哈希值的数据分布到不同的机器上。

所谓数据特征可以是key value 系统中的 key ，也可以是其他与应用业务逻辑相关的值。

只要哈希函数的散列特性较好，哈希方式可以较为均匀的将数据分布到集群中去。

哈希分布数据的缺点同样明显，突出表现为可扩展性不高，一旦集群规模需要扩展，则几乎所有的数据需要被迁移并重新分布。

工程中，扩展哈希分布数据的系统时，往往使得集群规模成倍扩展，按照数据重新计算哈希，这样原本一台机器上的数据只需迁移一半到另一台对应的机器上即可完成扩 展。

ps: 所以才有了一次性哈希算法。

哈希分布数据的另一个缺点是，一旦某数据特征值的数据严重不均，容易出现“数据倾斜”（dataskew ）问题。

ps: 这个应该在选择 hash key 的时候就避免掉。

按数据范围分布

按数据范围分布是另一个常见的数据分布式，将数据按特征值的值域范围划分为不同的区间，使得集群中每台（组）服务器处理不同区间的数据。

与哈希分布数据的方式只需要记录哈希函数及分桶个数（机器数）不同，按数据范围分布数据需要记录所有的数据分布情况。

一般的，往往需要使用专门的服务器在内存中维护数据分布信息，称这种数据的分布信息为一种元信息。

甚至对于大规模的集群，由于元信息的规模非常庞大，单台计算机无法独立维护，需要使用多台机器作为元信息服务器。

使用范围分布数据的方式的最大优点就是可以灵活的根据数据量的具体情况拆分原有数据区间，拆分后的数据区间可以迁移到其他机器，一旦需要集群完成负载均衡时，与哈希方式相比非常灵活。

另外，当集群需要扩容时，可以随意添加机器，而不限为倍增的方式，只需将原机器上的部分数据分区迁移到新加入的机器上就可以完成集群扩容。

按范围分布数据方式的缺点是需要维护较为复杂的元信息。

随着集群规模的增长，元数据服务器较为容易成为瓶颈，从而需要较为负责的多元数据服务器机制解决这个问题。

ps: 实际工作中，冷热分表可能会使用一下。将不常用的数据进行备份，保证热点数据的性能。

按数据量分布

另一类常用的数据分布方式则是按照数据量分布数据。

与哈希方式和按数据范围方式不同，数据量分布数据与具体的数据特征无关，而是将数据视为一个顺序增长的文件，并将这个文件按照某一较为固定的大小划分为若干数据块（ chunk ），不同的数据块分布到不同的服务器上。

与按数据范围分布数据的方式类似的是，按数据量分布数据也需要记录数据块的具体分布情况，并将该分布信息作为元数据使用元数据服务器管理。

由于与具体的数据内容无关，按数据量分布数据的方式一般没有数据倾斜的问题，数据总是被均匀切分并分布到集群中。

当集群需要重新负载均衡时，只需通过迁移数据块即可完成。

集群扩容也没有太大的限制，只需将部分数据库迁移到新加入的机器上即可以完成扩容。

按数据量划分数据的缺点是需要管理较为复杂的元信息，与按范围分布数据的方式类似，当集群规模较大时，元信息的数据量也变得很大，高效的管理元信息成为新的课题。

一致性哈希

一致性哈希（consistent hashing ）是另一个种在工程中使用较为广泛的数据分布方式。

一致性哈希最初在 P2P 网络中作为分布式哈希表（ DHT ）的常用数据分布算法。

一致性哈希的基本方式是使用一个哈希函数计算数据或数据特征的哈希值，令该哈希函数的输出值域为一个封闭的环，即哈希函数输出的最大值是最小值的前序。

将节点随机分布到这个环上，每个节点负责处理从自己开始顺时针至下一个节点的全部哈希值域上的数据。

哈希分布数据的方式在集群扩容时非常复杂，往往需要倍增节点个数，与此相比，一致性哈希的优点在于可以任意动态添加、删除节点，每次添加、删除一个节点仅影响一致性哈希环上相邻的节点。

使用一致性哈希的方式需要将节点在一致性哈希环上的位置作为元信息加以管理，这点比直接使用哈希分布数据的方式要复杂。

然而，节点的位置信息只于集群中的机器规模相关，其元信息的量通常比按数据范围分布数据和按数据量分布数据的元信息量要小很多。

上述最基本的一致性哈希算法有很明显的缺点，随机分布节点的方式使得很难均匀的分布哈希值域，尤其在动态增加节点后，即使原先的分布均匀也很难保证继续均匀，由此带来的另一个较为严重的缺点是，当一个节点异常时，该节点的压力全部转移到相邻的一个节点，当加入一个新节点时只能为一个相邻节点分摊压力。

为此一种常见的改进算法是引入虚节点（virtual node ）的概念，系统初始时就创建许多虚节点虚节点的个数一般 远大于未来集群中机器的个数，将虚节点均匀分布到一致性哈希值域环上，其功能与基本一致性哈希算法中的节点相同。为每个节点分配若干虚节点。

操作数据时，首先通过数据的哈希值在环上找到对应的虚节点，进而查找元数据找到对应的真实节点。

使用虚节点改进有多个优点。

首先，一旦某个节点不可用，该节点将使得多个虚节点不可用，从而使得多个相邻的真实节点负载失效节点的压力。

同理，一旦加入一个新节点，可以分配多个虚节点，从而使得新节点可以负载多个原有节点的压力，从全局看，较容易实现扩容时的负载均衡。

副本与数据分布

上述几节讨论了几种常见的数据分布方式，这些讨论中没有考虑数据副本的问题。

分布式系统容错、提高可用性的基本手段就是使用副本。

对于数据副本的分布方式主要影响系统的可扩展性。

一种基本的数据副本策略是以机器为单位，若干机器互为副本，副本机器之间的数据完全相同。

这种策略适用于上述各种数据分布方式。其优点是非常简单，其缺点是恢复数据的效率不高、可扩展性也不高。

（1）首先、使用该方式时，一旦出现副本数据丢失，需要恢复副本数据时效率不高。

（2）再者、该种方式不利于提高系统扩展性。一个极端的例子是，假设系统原有

（3）最后、这种方式不利于系统容错。

当出现一台机器宕机时，该机器上的原有压力只能被剩下的副本机器承担，假设有 3 个副本，宕机一台后，剩下两台的压力将增加 50%，有可能直接超过单台 的处理能力。

数据分段

更合适的做法不是以机器作为副本单位，而是将数据拆为较合理的数据段，以数据段为单位作为副本。

实践中，常常使得每个数据段的大小尽量相等且控制在一定的大小以内。

数据段有很多不同的称谓， segment fragment chunk partition 等等。数据段的选择与数据分布方式直接相关。

对于哈希分数据的方式，每个哈希分桶后的余数可以作为一个数据段，为了控制数据 段的大小，常常使得分桶个数大于集群规模。

一旦将数据分为数据段，则可以以数据段为单位管理副本，从而副本与机器不再硬相关，每台机器都可以负责一定数据段的副本。

一旦副本分布与机器无关，数据丢失后的恢复效率将非常高。

这是因为，一旦某台机器的数据丢失，其上数据段的副本将分布在整个集群的所有机器中，而不是仅在几个副本机器中，从而可以从整个集群同时拷贝恢复数据，而集群中每台数据源机器都可以以非常低的资源做拷贝。

工程中，完全按照数据段建立副本会引起需要管理的元数据的开销增大，副本维护的难度也相应增大。

一种折中的做法是将某些数据段组成一个数据段分组，按数据段分组为粒度进行副本管理。

这样做可以将副本粒度控制在一个较为合适的范围内。

本地化计算

本节到此为止都是讨论的数据分布的方式，容易被理解为仅仅是对数据存储分布方式的讨论。

对于分布式系统而言，除了解决大规模存储问题更需要解决大规模的计算问题。

然而计算离不开数据，计算的规模往往与输入的数据量或者计算产生的中间结果的数据量正相关。

在分布式系统中，数据的分布方式也深深影响着计算的分布方式。

在分布式系统中计算节点和保存计算数据的存储节点可以在同一台物理机器上，也可以位于不同的物理机器。

如果计算节点和存储节点位于不同的物理机器则计算的数据需要通过网络传输，此种方式的开销很大，甚至网络带宽会成为系统的总体瓶颈。

另一种思路是，将计算尽量调度到与存储节点在同一台物理机器上的计算节点上进行，这称之为本地化计算。

本地化计算是计算调度的一种重要优化，其体现了一种重要的分布式调度思想：“移动数据不如移动计算”。

参考资料

《分布式系统原理》