前语
假定让你为淘宝这种数据量非常大的公司的设计一个可扩展的数据存储体系，你该怎么存储和办理数据呢？总不能放在单个服务器上吧，肯定放不下，必然需求水平扩展。那么这样就带来一个问题，这个数据要存储在哪个服务器上呢？这就引入了本文的主题一致性哈希算法，可能你没听过，那么本文就经过一个简略的比如带你一步一步认识它。
欢迎重视个人大众号【JAVA旭阳】
数据线性散布
假定咱们现在有一组服务器，咱们想提出一个在这组服务器之间进行数据存储和查找的战略。让咱们从一个最最简略的计划开始。假定咱们一个接一个地填满服务器，即仅当当时服务器已满时，咱们才开始将数据写入下一个服务器。
在下图中，咱们有一个简略的服务器，一次只能存储 4 条记载。当服务器变满时，咱们增加一个新服务器并向其增加新数据。
好吧，这种方法在任何服务器上写入数据时都非常有用。当您被要求读取特定数据时会发生什么？您需求识别存储给定数据的服务器，然后获取它。你怎么识别服务器？您会遍历一切服务器并线性扫描每个服务器吗？这会影响读取性能。
例如：在上面的比如中，假如你被要求查找“New York”，因为键和服务器之间没有直接映射，你将不得不线性扫描一切服务器并查找这个键。
这样的效率是不是很糟糕，那么有没有更好的解决计划呢。
数据哈希散布
哈希算法想必大家都知道，Java中的HashMap就是采用的哈希算法。那么依据这个思路，咱们提出了一个新的解决计划，数据依据哈希进行存储办理。
咱们看到假如咱们有 N 个服务器，则获取记载的时刻复杂度将为 O(N)。咱们期望在 O(1) 中高效地读写数据。咱们首要想到的是供给 O(1) 查找和写入的 HashMap 数据结构。
让咱们看看 Hashing 是否能够解决咱们的问题。假定咱们有 N 个存储数据的服务器和一个具有分发数据战略的应用程序。该方法类似于 HashMap 运用的方法。首要，对键进行哈希处理，然后确定数据将寄存的存储桶。应用程序将首要对密钥进行哈希处理，然后经过核算hash(data) % N来确定哪个服务器。
上述算法将给出写入数据的服务器编号。此外，在检索数据时，它将运用相同的逻辑，获取服务器编号并获取数据。读取和写入都在 O(1) 中完成。
让咱们来看一个比如。假定咱们有三个名为 S0、S1 和 S2 的服务器。咱们的钥匙是国际城市称号。运用哈希，咱们核算需求将密钥分配到的存储桶或服务器。
密钥的哈希和核算桶
密钥分配
但这在散布式体系中总是有用的吗？咱们会遇到以下问题：
- 假如咱们增加更多服务器，则
hash(data) % N会有所不同。这意味着咱们将不得不在增加新服务器时从头分配一切数据。 - 假如删去其间一台服务器，咱们将遇到同样的问题。由于此处服务器的数量 N 是可变的，因而一切密钥都会受到影响。
以下是增加新服务器时发生的状况的阐明。跟着服务器数量从 3 台增长到 4 台，桶的核算逻辑将变为Hash % 4。
新旧密钥分配
在增加新服务器时，咱们观察到三个键中的两个受到了影响。假如咱们增加一个新服务器，键Madrid的桶将是 0 (S0) 而不是 1(S1)。咱们有必要将此密钥移动到服务器 S1 以保证咱们的应用程序找到它。因而，咱们有必要从头散列一切现有密钥并将它们分配给不同的服务器。在最坏的状况下，这可能会影响体系中的一切密钥。
看来经过哈希算法将数据分发到不同服务器中还是不大行，那还有什么更好的方法呢？这边就要盛大介绍一致性哈希。
什么是一致性哈希？
当咱们想要动态增加或删去服务器时，一致性哈希解决了咱们的问题。在简略散列的状况下，增加或删去服务器将影响存储在体系中的一切 M 密钥。但是，一致性哈希保证只有 M/N 键受到影响，其间 N 是服务器的数量。
一致性哈希使密钥的散布与体系运用的服务器数量无关。因而，咱们能够在不影响整个体系的状况下扩展或缩小规模。
从根本上说，一致性哈希运用哈希环。该算法将每个服务器映射到圆上的一个点。它首要运用服务器的 IP 地址，核算其散列值并为其分配圆上的一个点（角度）。以下是怎么为 3 个服务器 S1、S2、S3 核算角度的简略阐明：
将服务器分配给哈希环上的点
此外，每个密钥都运用相同的哈希算法进行哈希处理并在服务器上分配一个点。关于每个散列键，咱们按顺时针方向移动并找到最近的服务器并分配给它。
将密钥分配给哈希环上的点
咱们得到以上密钥集的以下分配：
将密钥分配给服务器
以下是上述密钥分配到哈希环上不同服务器的图形表明：
在哈希环大将密钥分配给服务器
从上图能够看出，咱们从每个键顺时针方向移动，找到它的服务器。
扩展和增加新服务器
如前一节所述，咱们首要核算服务器IP地址的哈希值并找到它在圆上的方位。例如：假如咱们增加一个服务器S4，发现它坐落圆上的S2和S0之间。此外，咱们从头分配 S0 的键，其角度小于 S3，或许换句话说，在圆上出现在 S3 之前。
下图阐明晰此进程，其间增加了一个新服务器 S3，它坐落 S2 和 S0 之间。开始，键Mumbai被分配给服务器 S0。在增加 S3 时，咱们看到从键Mumbai顺时针方向遇到的第一个服务器是 S3，因而咱们将此键分配给 S3。
增加新服务器 S3
从上面能够看出，增加新服务器不会影响一切密钥。只有散列环上两个服务器之间出现的密钥需求从头分配。
删去现有服务器
当删去现有服务器时，只需求从头分配归于该服务器的密钥。关于归于被移除服务器的key，按顺时针方向找到哈希环上的下一个服务器。此外，然后将密钥分配给新服务器。
下图阐明晰删去现有服务器的进程：
删去服务器 S1
在上图中，删去了服务器 S1。键New York被分配给服务器 S1。删去 S1 后，咱们从键New York中找到第一个服务器并找到服务器 S2。因而，键New York被从头分配给服务器 S2。
与普通散列不同，删去服务器不需求从头散列一切密钥。只需从头分配已移除服务器的密钥。
虚拟节点
咱们看到，当一个节点被移除时，分配给这个节点的一切键都会被移动到哈希环中的下一个节点。通常，在删去一个节点时，数据散布会变得不均匀，而且其间一个节点的负载会增加。
在上述状况下，假如咱们从体系中删去 S0，则键London将映射到服务器 S2。最终，咱们会发现 S2 处理三个密钥，而 S1 只办理一个密钥。因而，数据散布不均匀。
删去 S0 会给 S2 带来更多负载
在抱负状况下，当有M个密钥和N个服务器时，每个服务器有必要有挨近 M/N 个密钥。因而，增加或删去节点会影响体系中的最大 M/N 键。为了保证挨近抱负的散布，咱们在体系中引入了虚拟节点。每个物理节点在哈希环上都有多个虚拟节点。
咱们运用多个哈希函数来查找虚拟节点在哈希环上的方位。每个服务器都用 Sij 表明，其间 i 表明实际服务器编号，j 代表其虚拟副本。例如：关于第一台服务器，虚拟副本将是 S00、S01、S02、S03 等。咱们运用不同的哈希函数来核算每个虚拟副本的哈希值。
在上面的示例中，咱们得到以下虚拟服务器分配：
哈希环上的虚拟服务器
从上图能够看出，服务器S1的虚拟副本是S10、S12和S13。这同样适用于服务器 S0。这导致节点之间的数据散布挨近均匀。
关于给定的密钥，假如哈希环中的下一个服务器是 S12，则它将分配给第一个物理服务器。一般来说，分配给虚拟服务器 Sij 的密钥将存储在物理服务器 Si 上。
总结
本文带大家认识了一致性哈希算法，一致性哈希于 1997 年推出，它已经在许多散布式体系中的得到了应用。 Amazon 的 Dynamo DB 中运用它作分区组件。此外，Apache Cassandra 和 Voldermort 等开源应用程序运用它进行数据分区。
欢迎重视个人大众号【JAVA旭阳】
