java - 一致性哈希是如何工作的？

Question

我试图了解一致的哈希是如何工作的。这是我试图关注但无法关注的文章，首先我的问题是：

我理解，服务器被映射到哈希码的范围内，数据分布更加固定，看起来也很容易。但这如何处理集群中添加新节点的问题呢？
示例 java 代码不起作用，任何基于简单java的一致哈希的建议。

更新

一致散列的任何替代方案？

score 5 · Accepted Answer

对于 python 实现参考我的github repo

最简单的解释什么是普通散列？

假设我们必须将以下键值对存储在像 redis 这样的分布式内存存储中。

假设我们有一个散列函数 f(id) ，它接受上面的 ids 并从中创建散列。假设我们有 3 台服务器——（s1、s2 和 s3）

我们可以通过服务器的数量（即 3 ）对散列进行模运算，以将每个键映射到一个服务器，然后我们就剩下以下内容了。

我们可以使用 f() 通过简单的查找来检索键的值。说关键 Jackson ， f("Jackson")%(no of servers) => 1211*3 = 2 (node-2)。

这看起来很完美，是的，但不是雪茄！

但是如果服务器说 node-1 宕机了怎么办？对用户 Jackson 应用相同的公式，即 f(id)%(no of servers)，1211%2 = 1 即当实际密钥从上表散列到节点 2 时，我们得到节点 1。

我们可以在这里重新映射，如果我们有十亿个键怎么办，在这种情况下，我们必须重新映射大量的键，这很乏味:(

这是传统散列技术的主要流程。

什么是一致性哈希？

在 Consistent hashing 中，我们可视化圆环中所有节点的列表。（基本上是一个排序数组）

start func
For each node:
 Find f(node) where f is the hash function
 Append each f(node) to a sorted array
For any key
  Compute the hash f(key)
  Find the first f(node)>f(key)
  map it
end func

例如，如果我们必须对密钥 smith 进行哈希处理，我们计算哈希值 1123 ，找到哈希值 > 1123 的直接节点，即哈希值为 1500 的节点 3

现在，如果我们丢失了一个服务器，比如说我们丢失了 node-2，所有的键都可以映射到下一个服务器 node-3 :) 是的，我们只需要重新映射 node-2 的键

score 4 · Accepted Answer

我将回答你问题的第一部分。首先，该代码中有一些错误，所以我会寻找一个更好的例子。

这里以缓存服务器为例。

当您考虑一致性哈希时，您应该将其视为一个圆环，就像您链接到的文章一样。添加新服务器时，它上面将没有数据开始。当客户端获取应该在该服务器上的数据但没有找到它时，将发生缓存未命中。然后程序应该在新节点上填充数据，这样以后的请求就会被缓存命中。从缓存的角度来看，就是这样。

score 1 · Accepted Answer

概述

我写了一篇关于一致性哈希如何工作的博客，在这里回答这些原始问题，下面是快速总结。

一致性哈希更常用于数据分区目的，我们通常在组件中看到它

负载均衡器
API网关
...

为了回答这些问题，下面将涵盖

这个怎么运作
如何添加/查找/删除服务器节点
如何实施
一致散列的任何替代方案？

让我们在这里使用一个简单的示例负载均衡器，负载均衡器映射 2 个源节点（负载均衡器后面的服务器）和同一个哈希环圈中的传入请求（假设哈希环范围为 [0,255]）。

初始状态

对于服务器节点，我们有一个表：

查找节点

对于任何传入的请求，我们应用相同的哈希函数，然后我们假设我们得到一个hashcode = 120的请求的哈希码，现在从表中，我们以顺时针顺序找到下一个最近的节点，所以节点 2是本例中的目标节点。

同样，如果我们收到一个 hashcode = 220 的请求怎么办？因为哈希环范围是一个圆，所以我们返回第一个节点。

添加节点

现在让我们在集群中再添加一个节点：节点 3（哈希码 150），然后我们的表将更新为：

然后我们在Find Node部分使用相同的算法来查找下一个最近的节点。比如说，hashcode = 120 的请求，现在它将被路由到 node-3。

删除节点

删除也很简单，只需从表中删除条目 <node, hashcode> ，假设我们删除 node-1，那么表将更新为：

然后所有请求：

[201, 255] 和 [0, 150] 中的哈希码将被路由到 node-3
[151, 200] 中的哈希码将被路由到 node-2

执行

下面是一个简单的 c++ 版本（启用了虚拟节点），它与 Java 非常相似。

#define HASH_RING_SZ 256

struct Node {
  int id_;
  int repl_;
  int hashCode_;
  Node(int id, int replica) : id_(id), repl_(replica) {
    hashCode_ =
      hash<string>{} (to_string(id_) + "_" + to_string(repl_)) % HASH_RING_SZ;
  }
};

class ConsistentHashing {
private:
  unordered_map<int/*nodeId*/, vector<Node*>> id2node;
  map<int/*hash code*/, Node*> ring;

public:
  ConsistentHashing() {}

  // Allow dynamically assign the node replicas
  // O(Rlog(RN)) time
  void addNode(int id, int replica) {
    for (int i = 0; i < replica; i++) {
      Node* repl = new Node(id, replica);

      id2node[id].push_back(repl);
      ring.insert({node->hashCode_, repl});
    }
  }

  // O(Rlog(RN)) time
  void removeNode(int id) {
    auto repls = id2node[id];
    if (repls.empty()) return;

    for (auto* repl : repls) {
      ring.erase(repl->hashCode_);
    }

    id2node.erase(id);
  }

  // Return the nodeId
  // O(log(RN)) time
  int findNode(const string& key) {
    int h = hash<string>{}(key) % HASH_RING_SZ;

    auto it = ring.lower_bound(h);
    if (it == ring.end()) it == ring.begin();

    return it->second->id;
  }
};

备择方案

如果我正确理解了这个问题，那么问题就是为数据分区目的询问一致散列的任何替代方案。实际上有很多，取决于实际用例我们可以选择不同的方法，例如：

随机的
循环赛
加权循环
模散列
一致哈希
加权（动态）一致散列
基于范围
基于列表
基于字典
...

特别是在负载均衡领域，还有一些方法，例如：

最少连接
最短响应时间
最小带宽
...

上述所有方法各有利弊，没有最好的解决方案，我们必须做出相应的取舍。

最后的

以上只是对原始问题的快速总结，供进一步阅读，例如：

一致性哈希不平衡问题
雪崩问题
虚拟节点概念
如何调整副本号

我已经在博客中介绍了它们，以下是快捷方式：

玩得开心：）

score 1 · Accepted Answer

我会回答你问题的第一部分。出现的问题是一致性散列实际上是如何工作的？正如我们所知，在客户端-服务器模型中，负载均衡器将根据网络请求到服务器的流量将请求路由到不同的服务器。

因此，散列的目的是将数字分配给所有请求的客户端，并通过我们拥有的许多服务器对其进行模式（数学）。我们将在模式之后获得的其余部分，我们将请求分配给该特定服务器。

在一致散列策略中，它使用散列函数将客户端和服务器定位在循环路径上。如果客户端是顺时针方向，它将路由请求，客户端的请求将被路径中最先到达的服务器接受。

如果我们的一台服务器死了怎么办？

之前，在一个简单的哈希策略中，我们需要重新计算并根据我们将得到的余数路由请求，我们将面临缓存命中的问题。

在这种一致的散列策略中，如果任何一个服务器死亡，客户端的请求将按照顺时针方向的路径移动到下一个服务器。这意味着它不会影响其他服务器，并且将保持缓存命中和一致性。

java - 一致性哈希是如何工作的？

4 回答 4

概述

初始状态

查找节点

添加节点

删除节点

执行

备择方案

最后的

Related

Reference