• 在分布式系统中，具体是如何实现数据索引或数据分布的呢？目前最常用的方法就是哈希和一致性哈希。

数据分布设计原则

• 数据分布设计原则是分布式存储系统设计的基本原则，指导了哈希和一致性哈希方法的选择和应用。数据分布，主要就是数据分片。

假设，现在有上百 G 数据需要进行分布式存储，也就是要存储到不同的节点上。提到这个问题，可能立刻就会想到很多种方法，比如随机分布、范围分布、映射分布等。那么，我们应该如何选择到底要使用哪种方法呢？

• 在分布式数据存储系统中，存储方案选型时，通常会考虑数据均匀、数据稳定和节点异构性这三个维度。
  • 从数据均匀的维度考虑，主要包括两个方面：
    • 不同存储节点中存储的数据要尽量均衡，避免让某一个或某几个节点存储压力过大，而其他节点却几乎没什么数据。比如，现在有 100G 数据，4 个同类型节点，通常希望数据存储时尽可能均衡，比如每个节点存储 25G 数据。
    • 另外，用户访问也要做到均衡，避免出现某一个或某几个节点的访问量很大，但其他节点却无人问津的情况。比如，现在有 1000 个请求，对于上述存储数据的 4 个节点，处理用户访问请求尽量均衡，比如每个节点处理 250 个请求，当然这是非常理想的情况，实际情况下，每个节点之间相差不太大即可。
  • 从数据稳定的维度考虑，当存储节点出现故障需要移除或者扩增时，数据按照分布规则得到的结果应该尽量保持稳定，不要出现大范围的数据迁移。
    • 比如，现有 100G 数据，刚开始有 4 个同类型节点（节点 1~4），每个节点存储 25G 数据，现在节点 2 故障了，也就是说每个节点需要存储 100G/3 数据。
    • 数据稳定，就是尽可能只迁移节点 2 上的数据到其他节点上，而不需要对大范围或所有数据进行迁移存储。当然，如果有扩展同类型节点，也是尽可能小范围迁移数据到扩展的节点上。
  • 从节点异构性的维度考虑，不同存储节点的硬件配置可能差别很大。比如，有的节点硬件配置很高，可以存储大量数据，也可以承受更多的请求；但，有的节点硬件配置就不怎么样，存储的数据量不能过多，用户访问也不能过多。如果这种差别很大的节点，分到的数据量、用户访问量都差不多，本质就是一种不均衡。所以，一个好的数据分布算法应该考虑节点异构性。
• 除了上面这 3 个维度外，一般还会考虑隔离故障域、性能稳定性等因素。
  • 隔离故障域，是为了保证数据的可用和可靠性。比如，我们通常通过备份来实现数据的可靠性。但如果每个数据及它的备份，被分布到了同一块硬盘或节点上，就有点违背备份的初衷了。所以，一个好的数据分布算法，应该为每个数据映射一组存储节点，这些节点应该尽量在不同的故障域，比如不同机房、不同机架等。
  • 性能稳定性是指，数据存储和查询的效率要有保证，不能因为节点的添加或者移除，造成存储或访问性能的严重下降。
    

数据分布方法

• 哈希是指，将数据按照提前规定好的函数（哈希函数）映射到相应的存储节点，即进行一个哈希计算，得到的结果就是数据应该存储的节点。
• 一致性哈希同样是采用哈希函数，进行两步哈希：
  1. 对存储节点进行哈希计算，也就是对存储节点做哈希映射；
  2. 当对数据进行存储或访问时，首先对数据进行映射得到一个结果，然后找到比该结果大的第一个存储节点，就是该数据应该存储的地方。
• 总结来讲，哈希是一步计算直接得到相应的存储节点，而一致性哈希需要两步才可以找到相应的存储节点。

哈希

• 哈希是一种非常常用的数据分布方法，其核心思想是，首先确定一个哈希函数，然后通过计算得到对应的存储节点。

具体的例子

• 假设，有三个存储节点，分别为 Node1、Node2 和 Node3；现有以下数据，ID 的范围为 [0,1000]：D0:{ id:100, name:‘a0’}、D1:{ id:200, name:‘a1’} 、D2:{ id:300, name:‘a2’}、D3:{ id:400, name:‘a3’}、D4:{ id:500, name:‘a4’}、D5:{ id:600, name:‘a5’}和 D6:{ id:700, name:‘a6’}。
• 假设，哈希函数为“id% 节点个数”，通过计算可以得到每个数据应该存入的节点。在这个例子中，哈希函数是“id%3”，结果为 0 的数据存入 Node1、结果为 1 的数据存入 Node2、结果为 2 的数据存入 Node3。
• 如图所示，Node1 将存储数据 D2（300%3=0）和 D5（600%3=0），Node2 将存储数据 D0（100%3=1）、D3（400%3=1）和 D6（700%3=1），Node3 将存储数据 D1（200%3=2）和 D4（500%3=2）。

• 可以看出，哈希算法的一个优点是，只要哈希函数设置得当，可以很好地保证数据均匀性，但有一个较为严重的缺点，就是稳定性较差。
• 比如，随着数据量的增加，三个节点的容量无法再满足存储需求了，需要再添加一个节点。这时，哈希函数变成了 id%4，原先存储在那三个节点的数据需要重新计算，然后存入相应节点，即需要大规模的数据迁移，显然会降低稳定性。
• 所以，哈希方法适用于同类型节点且节点数量比较固定的场景。目前，Redis 就使用了哈希方法。

一致性哈希

• 一致性哈希是指将存储节点和数据都映射到一个首尾相连的哈希环上，存储节点可以根据 IP 地址进行哈希，数据通常通过顺时针方向寻找的方式，来确定自己所属的存储节点，即从数据映射在环上的位置开始，顺时针方向找到的第一个存储节点。

实现上述案例的数据存储

• 如图所示，假设数据 D0～D7 按照 ID 进行等值映射，即映射值与 ID 值相等，比如数据 D0 映射到哈希环上的值为 100，数据 D1 映射到哈希环上的值为 200······；同时，假设存储节点 Node1、Node2 和 Node3 映射到哈希环上的值分别为 400、600、900。
• 按照规则，D0，D1，D2 和 D3 顺时针方向的下一个存储节点为 Node1，因此 Node1 将存储数据 D0（id = 100）、D1（id = 200）、D2（id = 300）和 D3（id = 400）；同理，Node2 将存取数据 D4（id = 500）和 D5（id = 600），Node3 将存取数据 D6（id = 700）。
  
• 一致性哈希是对哈希方法的改进，在数据存储时采用哈希方式确定存储位置的基础上，又增加了一层哈希，也就是在数据存储前，对存储节点预先进行了哈希。这种改进可以很好地解决哈希方法存在的稳定性问题。当节点加入或退出时，仅影响该节点在哈希环上顺时针相邻的后继节点。比如，当 Node2 发生故障需要移除时，由于 Node3 是 Node2 顺时针方向的后继节点，本应存储到 Node2 的数据就会存储到 Node3 中，其他节点不会受到影响，因此不会发生大规模的数据迁移。
• 所以，一致性哈希方法比较适合同类型节点、节点规模会发生变化的场景。目前，Cassandra 就使用了一致性哈希方法。
• 一致性哈希方法虽然提升了稳定性，但随之而来的均匀性问题也比较明显，即对后继节点的负载会变大。有节点退出后，该节点的后继节点需要承担该节点的所有负载，如果后继节点承受不住，便会出现节点故障，导致后继节点的后继节点也面临同样的问题。

带有限负载的一致性哈希

• 带有限负载的一致性哈希方法的核心原理是，给每个存储节点设置了一个存储上限值来控制存储节点添加或移除造成的数据不均匀。当数据按照一致性哈希算法找到相应的存储节点时，要先判断该存储节点是否达到了存储上限；如果已经达到了上限，则需要继续寻找该存储节点顺时针方向之后的节点进行存储。

上述案例的数据存储

• 如图所示，假设每个存储节点设置的上限值为 3，按照一致性哈希算法，当存储数据 D3（id = 400）时，会发现应该存储到 Node1 中，但 Node1 已经存储了三个数据 D0（id = 100）、D1（id = 200）和 D2（id = 300），达到了存储上限，因此会存储到该节点顺时针方向的下一个节点 Node2 中。当然，在存储前，也会先检查 Node2 是否达到了存储上限，如果达到了，会继续寻找其他节点。
  
• 带有限负载的一致性哈希方法比较适合同类型节点、节点规模会发生变化的场景。目前，在 Google Cloud Pub/Sub、HAProxy 中已经实现该方法，应用于 Google、Vimeo 等公司的负载均衡项目中。
• 其实，哈希、一致性哈希、带有限负载的一致性哈希，都没有考虑节点异构性的问题。如果存储节点的性能好坏不一，数据分布方案还按照这些方法的话，其实还是没做到数据的均匀分布。

带虚拟节点的一致性哈希

• 带虚拟节点的一致性哈希方法，核心思想是根据每个节点的性能，为每个节点划分不同数量的虚拟节点，并将这些虚拟节点映射到哈希环中，然后再按照一致性哈希算法进行数据映射和存储。
• 假设，Node1 性能最差，Node2 性能一般，Node3 性能最好。以 Node1 的性能作为参考基准，Node2 是 Node1 的 2 倍，Node3 是 Node1 的 3 倍。因此，Node1 对应一个虚拟节点 Node1_1，Node2 对应 2 个虚拟节点 Node2_1 和 Node2_2，Node3 对应 3 个虚拟节点 Node3_1、Node3_2 和 Node3_3。
• 假设，虚拟节点 Node1_1、Node2_1、Node2_2、Node3_1、Node3_2、Node3_3 的哈希值，分别为 100、200、300、400、500、600。
• 那么，按照带虚拟节点的哈希一致性方法， 数据 D0 和 D6 按顺时针方向的下一个虚拟存储节点为 Node 1-1，因此节点 Node1 将会存储数据 D0（id = 100）和 D6（id = 700）；同理，Node2 将会存储数据 D1（id = 200）和 D2（id = 300），Node3 将会存储数据 D3（id = 400）、D4（id = 500）和 D5（id = 600）。
  
• 带虚拟节点的一致性哈希方法比较适合异构节点、节点规模会发生变化的场景。目前 Memcached 缓存系统实现了该方法。
• 这种方法不仅解决了节点异构性问题，还提高了系统的稳定性。当节点变化时，会有多个节点共同分担系统的变化，因此稳定性更高。
• 比如，当某个节点被移除时，对应该节点的多个虚拟节点均会移除，而这些虚拟节点按顺时针方向的下一个虚拟节点，可能会对应不同的物理节点，即这些不同的物理节点共同分担了节点变化导致的压力。
• 当然，这种方法引入了虚拟节点，增加了节点规模，从而增加了节点的维护和管理的复杂度，比如新增一个节点或一个节点故障时，对应到虚拟节点构建的哈希环上需要新增和删除多个节点，数据的迁移等操作相应地也会很复杂。

四种数据分布方法对比

知识扩展：数据分片和数据分区，有何区别？
数据分区是从数据存储块的维度进行划分，不同的分区物理上归属于不同的节点。比如，现在有 2 个节点 Node1 和 Node2，2 个数据分区 Partition1 和 Partition2，Partition1 属于 Node1、Partition2 属于 Node2。数据分区，可用于存储不同的数据，也可以用来存储相同的数据实现数据备份。数据分区可以归结为是“货架”相关的关键技术，也就是为数据存储提供合适的位置。
数据分片是从数据的维度进行划分，是指将一个数据集合按照一定的方式划分为多个数据子集，不同的数据子集存在不同的存储块上，而这些存储块可以在不同的节点上，也可以在同一节点上。数据分片是实现“导购”的关键技术，目的是构建索引，为数据确定位置，包括存储数据和查询数据时确定数据位置。
由此可见，数据分片和数据分区是两个不同的概念，且属于分布式存储系统中不同角色的技术，前者是实现“导购”的关键技术，后者是“货架”相关的技术，不可直接等同。
但正因为一个是导购相关的关键技术，一个是货架相关的技术，一个提供确定数据索引的位置，一个提供合适的数据存储位置，因此这两个技术是可以共存的，比如下面这个例子。
有 3 个节点{Node1, Node2, Node3}，有 3 个分区{Partition1, Partition2, Partition3}用于存储用户信息，每个节点上 1 个分区。现在有 1000 个用户信息需要存储，用户 id 编号为 [1,1000]，为防止将所有信息存储到一个节点上，所有用户发起请求时，该节点成为瓶颈，为此需要将这 1000 个用户信息存储到 3 个节点上。
假设，我们采用最简单的哈希方法，用户 id% 节点总数 (3) 进行哈希映射，id%3 = 0 的所有用户信息存储到节点 1 的 Partition1， id%3=1 的所有用户信息存储到节点 2 的 Partition2，id%3=2 的所有用户信息存储到节点 3 的 Partition3。

你知道的越多，你不知道的越多。