【数据分布方式】

    1、普通哈希

        它的另一种叫法是取模。将它想象为一个大哈希表，每类机器就是一个桶，把数据哈希值分散到各个桶。

        哈希函数散列性决定了数据分布的均匀性。不记录元数据信息，只需知道计算方式和模的机器总数。

        扩展性低，集群规模变动全部数据都要迁移并重新分布。

        集群规模成倍扩容按照数据重新哈希，原数据只迁移一半到另外一台机器上。

        应用：Mola(https://developer.baidu.com/platform/s60)、Armor(分布式Key-Value系统)、Big Pipe(百度的消息传输系统)

    2、按数据范围

        从全局看数据类似一个B树，每个具体的服务器都是叶子节点，元数据服务器是中间节点。将数据按特征值的值域范围划分为不同的区间，使得集群中每台(组)服务器处理不同区间的数据，比如按照ID的值域范围分。

        利用动态划分区间技术，每个区间数据量尽量一样多。相比哈希方式非常灵活，集群扩容时，随意添加机器，不限为倍增方式，只需将原机器上的部分数据分区迁移到新加入的机器上就可以完成机器扩容。

        需要专门的元信息服务器来维护数据分布信息大规模集群，元信息会很大，元数据服务器较为容易成为瓶颈。还会存在某个区间的数据很大出现倾斜问题。

        某区间数据量较大将该区间分裂拆为两个区间，保证每个区间的数据在一个固定阈值下。

        应用：Big Table(https://cloud.google.com/bigtable/)、Hbase(https://hbase.apache.org/)、PNUTS(https://timyang.net/architecture/yahoo-pnuts/)

    3、按数据量

        它与哈希方式和按数据范围方式不同，按数据量分布数据与具体的数据特征无关，将数据视为一个顺序增长的文件，将这个文件按照某个较为固定的大小划分为若干数据库(chunk)，不同的数据分布到不同的服务器。也是需要记录数据块的具体分布情况，将分布信息作为元数据使用元数据服务器管理。

        一般是没有数据倾斜的问题，数据总数被均匀的切分并分布到集群中，当集群需要重新负载均衡时，只需要迁移数据块就可以。集群扩容扩容也没有太大的限制，只需将部分数据块迁移到新加入的机器上就可以完成扩容。

        缺点是需要管理复杂的元信息，高效的管理元信息会成为新的问题。

        应用：GFS(https://pdos.csail.mit.edu/6.824/papers/gfs.pdf)、HDFS(https://hadoop.apache.org/docs/r1.0.4/cn/hdfs_design.html)

    4、一致性哈希

        最初在P2P网络中作为分布式哈希表(DHT)的常用数据分布算法。使用一个哈希函数计算数据或数据特征的哈希值，令哈希函数的输出值域为一个封闭的环，将节点随机分布在这个环上，每个节点负责处理从自己开始顺时针到下一个节点的全部哈希值域上的数据。

        普通哈希分布式数据集群扩容时很复杂，往往需要倍增节点个数，一致性哈希可以任意动态添加、删除节点，每一个节点仅影响一致性哈希环上相邻的节点。节点的位置信息只和集群中机器规模相关，它的元信息的量通常比按照数据范围和按数据量分布的元信息量要小很多。

        缺点是很难均匀的分布哈希值域，即使原先的分布均匀也很难保证后续的继续均匀，会出现某个节点异常时，该节点的全部压力转移到相邻的一个节点，出现多米诺骨牌效应。

        引入虚拟节点的概念改进算法，系统初始时就创建许多虚拟节点，虚拟节点的个数一般远大于未来集群中机器的个数，将虚拟节点均匀分布到一致性哈希值域环上。为每个节点分片若干虚拟节点。操作数据时，首先通过数据的哈希值在环上找到对应的虚节点，进而查找元数据找到对应的真实节点。一旦某个节点不可用，该节点的多个虚拟节点不可用。

        应用：Dynamo(https://aws.amazon.com/cn/dynamodb/)、Cassandra(http://cassandra.apache.org/)

    除了上面讲到的四种数据分布方式，还有哈希槽方式，还有组合的方式：比如应用Doris(http://doris.incubator.apache.org/)是普通哈希方式与按数据量分布组合。

【副本中数据分布方式】

    分布式系统的容错、提高可用性的基本手段就是使用副本。对于数据副本的分布方式主要影响系统的可扩展性。下面我们讲两种基本的数据副本的分布方式。

    一种基本的数据副本策略是以机器为单位，若干机器互为副本，副本机器之间的数据完全相同。这种策略适用于上述各种数据分布方式。优点是简单，缺点是恢复副本数据时效率不高、可扩展性也不高。

    场景：假设有3个副本机器，某时刻其中某台机器磁盘损坏，丢失了全部数据，此时使用新的机器替代故障机器，为了是让新的机器也可以提供服务，怎么从正常的两台机器上拷贝数据？

    方案一：将一台可用的副本机器下线，专门作为数据源拷贝数据，缺点是造成实际正常工作的副本只有一个，对数据安全性造成巨大隐患，如果服务由于分布式协议设计或压力的要求必须2个副本才能正常工作，则该做法完全不可行。

    方案二：以较低的资源使用限速的方式从两个正常副本上拷贝数据，此方法不停服务，但是可以选择服务压力较小的时间段进行。缺点就是速度很慢，如果数据量巨大(数T)，限速较小(1MB/s)，往往需要数天才能够完成恢复。

    小结：副本策略是以机器为单位，这种方式不利于提高系统扩展性。不利于系统容错，理想情况下，有N台机器，宕机一台后，该台机器的压力可以均匀分散到剩下的N-1台机器上，每台机器的压力仅增加1/N-1，但是有可能直接超过单台的处理能力。

    更合适的做法不是以机器作为副本单位，而是将数据拆分为较合理的数据段，以数据段位为单位做副本。控制每个数据段的大小尽量相等且控制在一定大小以内。数据段有很多称谓，segment、fragment、chunk、partition。使得副本与机器不再硬相关，每台机器都可以负责一定的数据段副本(o、p、q为数据段)。

    一旦副本分布与机器无关，数据丢失后恢复效率会非常高。一旦某台机器的数据丢失，其上数据段的副本将分布在整个集群的所有机器中，而不仅仅在几个副本机器中，从而整个集群同步拷贝恢复数据，集群中每台数据源机器都可以非常低的资源做拷贝，比如作为恢复数据源的机器都限速1MB/s，有100台机器参与恢复，恢复速度达到100MB/s。也利于集群容错、集群扩展。假设集群规模为N台机器，当加入一台新机器时，只需要从各台机器上迁移1/N - 1/1/N +1比例的数据段到新机器即实现了新的负载均衡，是从机器中各机器迁移数据，与数据恢复同理，效率也很高。

    工程中，完全按照数据段建立副本会引起需要管理的元数据的开销增大，副本维护的难度也增大。一种折中的做法是将某些数据段组成一个数据段分组，将数据段分组为粒度进行副本管理。这样做刻意将副本粒度控制在一个合适的范围内。

【本地化计算】

    上面提到的都是数据分布方式，容易被理解为分布方式仅仅作用于数据存储。分布式除了解决大规模存储问题更需要解决大规模计算问题。计算离不开数据，计算的规模往往与输入的数据量或计算产生的中间结果的数据量正相关。分布式架构中，数据的分布方式也可以作用于计算中。

    分布式架构中的计算节点和保存计算数据的存储节点可以在同一台物理机器上，也可以位于不同的物理机器。如果计算节点和存储节点位于不同的物理机器则计算的数据需要通过网络传输，这种方式的开销很大，网络带宽会成为架构中的总体瓶颈。

    ”移动数据不如移动计算”，这种思路就是：把计算尽量调度到与存储节点在同一台物理机器上的计算节点上进行，这种称为本地化计算。本地化计算是计算调度的一种重要优化，这是一种重要的分布式调度思想。

【数据分布方式的选择】

    在实际的工程实践中，可以根据需求以及实施复杂度合理选择数据分布方式。上述的数据分布方式如果可以灵活组合使用，往往可以兼备各种方式的优点，收到较好的综合效果。

    场景：怎么解决分布式中数据倾斜问题？

    假设初始的策略使用的是普通哈希，它不需要维护元数据信息。但是可能存在数据倾斜，在此策略基础之上引入按数据量分布数据的方式，解决数据倾斜问题。按照用户ID的哈希值分数据，如果某个用户ID的数据量特别大时，统计用户的数据量，并按某一阈值将用户的数据切分为多个均匀的数据段，将这些数据段分布到集群中去。大部分用户的数据量不会超过阈值，元数据中仅仅保存超过阈值的用户的数据段分布信息。这种普通哈希分布数据方式与按数据量分布式数据方式组合使用的方案，在某真实系统中取得了较好的效果。