【一致性hash】负载均衡器分发请求

1. 水平扩容和垂直扩容

    在单体架构中，客户端通常向单个服务器发出请求。随着请求数量开始增加，单个服务器没有足够的容量来处理所有传入的请求。

    垂直扩展可能是一种选择，将更多的 CPU/RAM 添加到服务器。在遇到硬件限制之前，此选项能工作很长时间。

 在大多数情况下，添加更多服务器的水平扩展通常是一种更具可扩展性的替代方案。

2. 使用负载均衡器重定向请求

       当我们水平扩展时，请求被定向到负载均衡器而不是直接到服务器上。负载均衡器：它的目的是通过尽可能均匀地分布请求来平衡每台服务器上的负载。

        2.1 Hash function and modulo (%)

            所有具有唯一标识符（例如 IPV6 地址）的传入请求都被假定为统一随机的。 使用散列函数，我们可以获得一个输出值，之后我们应用模函数来获得与负载均衡器应该将请求定向到的服务器相对应的数字。

• hash(ipv6Address) → output
• Output % number of servers -1 → server ID  // 取模函数

        使用良好的散列函数以确保输出值分布在一系列值以提高随机性非常重要。然后，模函数保证服务器 ID 在 0 范围内。（服务器数量 -1）

        2.2 可视化映射

           让我们退后一步，想象一下我们如何使用数组作为数据结构来将每个请求映射到服务器。 在下面这个简单的示例中，

数组的索引直接映射到服务器 ID，但在生产中可能不一定如此。因此，使用像数组这样的数据结构可以让我们更灵活地将输出映射到我们喜欢的任何服务器。

        2.3 当我们添加额外的服务器时会发生什么？

         到目前为止，我们假设了固定数量的服务器。但是，由于我们选择了水平扩展，我们应该能够根据需要添加或删除服务器。 不幸的是，简单地使用散列函数和取模会影响其他请求的处理和重定向方式。

         让我们通过以下示例来了解不利影响。 假设我们有五台服务器，在对用户的 IP 地址进行哈希处理后，我们得到哈希值 88。如果我们取 (88 % 5) 的值，我们得到 3。在这种情况下，负载均衡器将请求重定向到服务器 3。但是，如果我们决定添加一个额外的服务器，我们将得到一个值 (88 % 6)，这反过来将请求重定向到服务器 4。

        2.4 变更的代价

        这种重定向可能看似微不足道，但当服务器不是无状态时会涉及成本（比如服务器有根据用户特征来做的本地缓存）。虽然 HTTP 是一种无状态协议，但一些服务器可能会选择将一些与用户相关的数据存储在其缓存中以进行优化。 例如，服务器可以选择存储会话日志以记住用户以减少身份验证频率。

       因此，如果具有特定 IP 地址的用户将被路由到不同的服务器，则需要使之前服务器上的缓存失效。由于此更改同样会影响所有其他传入请求，因此服务器上的所有缓存都需要失效。 这里的更改成本过高，尤其是在同时处理数万台服务器时。那么，我们如何在添加或删除服务器的同时减少对其他服务器的影响呢？

3. Consistent Hashing 一致性hash

        解决方案：使用一致的散列。

        3.1 第 1 步：将请求映射到环上的位置

            现在，让我们想象一个圆形数组，而不是常规数组。与数组类似，每个请求现在都将映射到哈希环上的一个位置。

        3.2 第 2 步：将服务器映射到环上的位置

         由于每个服务器都有一个 ID，我们可以将应用于 IP 地址的相同哈希和模函数应用于服务器 ID。假设选择的哈希函数是最优的，并且 IP 地址和服务器 ID 之间没有冲突。 （注意：这里server和节点一一映射）

        3.3 第3步：顺时针移动

        现在我们已经在环上映射了请求和服务器，最后一步很简单。对于每个请求，我们只需按顺时针方向找到其右侧最近的服务器。例如，映射到索引 7 的传入请求由映射到索引 9 的服务器提供服务。

4. 一致性哈希如何最小化对其他服务器的影响？

      由于请求由最右边的服务器提供服务，因此最多有一台其他服务器会受到服务器数量变化的影响。

    在上面的示例中，添加了一个新服务器并映射到索引 95。映射到索引 88 的请求现在由映射到索引 95 的新服务器提供服务，而不是之前映射到索引 99 的服务器。

    在这种情况下，只有映射到索引 99 的服务器需要使其缓存失效。类似地，如果一个服务器被移除，下一个服务器的邻居将接管负载，其他服务器不会受到影响。

    在寻找最近邻居时，一致性哈希的概念避免了强加于其他服务器的昂贵更改成本，并将成本降低到一个常数。

5. Virtual Nodes 虚拟节点

        5.1 请求不是完全随机的

        在理想世界中，请求是均匀随机的，并且每个服务器都有一个均匀的负载。 然而，现实中很少出现这种情况。例如，来自特定区域的请求数量可能更多，这意味着与其他服务器相比，服务器的负载会更高。 为了减轻负载，我们需要在映射到请求的索引和最近服务器的索引之间放置更多服务器。给定固定数量的服务器，能做到吗？--- 虚拟节点

        5.2 使用多个哈希函数

       答案是肯定的。回想一下，每个散列函数都是不同的，并返回不同的输出。 如果我们获取服务器 ID 并使用三个不同的哈希函数对其进行哈希处理，我们最终会得到三个不同的输出。如果我们将这三个不同的值映射到哈希环上，它们将位于不同的位置。

      在服务器 ID 上使用多个哈希函数的想法在哈希环上创建了虚拟位置，或者我们称之为虚拟节点。因此，我们在环上的服务器位置更加分散，这有助于减少每台服务器的负载。这样环上的每一一个区域每一个server都有3个虚拟节点对应；当然3---->500（500个随机函数？？或者使用500个个特定参数如：hash(ipv6(1-500))%N） N可以设置为65535甚至int32的最大值，效果更好；