在分布式散列中的节点连接期间优化键空间分区 table

Question

当节点加入 DHT 网络时，新节点最好将最大间隔平均划分在一致性哈希的圆上，以尽量减少重新映射。但是，这仅适用于 2ⁿ 个节点（假设以 n=1 开始）；如果键被统一访问，所有其他数字都会创建热点：

n=2, ¹/₂ ¹/₂,最优
n=3, ¹/₄ ¹/₄ ¹/₂ , 热点为 ¹/₃ 的节点服务 ¹/₂ 的流量
n=4, ¹/₄ ¹/₄¹/₄¹/ ₄，最佳
n=5, ¹/₈ ¹/₈¹/₄¹/ ₄ ¹/₄，热点有³/₅ 个节点服务 ³/₄ 个流量

一种最小化热点同时引发更多重新映射的方法是均匀地重新分配新节点：

n=2, ¹/₂ ¹/₂
n=3, ¹/₃ ¹/₃¹/₃

通过像下面这样的实现，一些相当少的元素被重新映射（不确定它是否真的被最小化），热点被消除，基本的一致性哈希算法被保留。

// 10 perfectly distributed hash keys, later referred to as a-j
var hashKeys = [0.05, 0.15, 0.25, 0.35, 0.45, 0.55, 0.65, 0.75, 0.85, 0.95];

for (var kNodeCount = 1; kNodeCount < 5; kNodeCount++) {
 var buckets = [];
 for (var k = 0; k < kNodeCount; k++) buckets[k] = [];
 // Distribute keys to buckets:
 for (var i = 0; i < hashKeys.length; i++) {
  var hashKey = hashKeys[i];
  var bucketIndex = Math.floor(hashKey * kNodeCount);
  buckets[bucketIndex].push(hashKey);
 }
 console.log(kNodeCount, buckets);
}

从那开始的过渡（字母而不是数字）是：
[abcdefghij] -> [abcde][fghij] -> [abc][defg][hij] -> [ab][cde][fg][hij]

是否有 other/better 解决方案（这是一个已解决的问题）？ 一般来说，我对 DHT 和分布式算法比较陌生，但我还没有在我读过的任何 DHT/p2p/distributed 算法中都找不到这个地址。在我的特定场景中，最小化热点至关重要，而最小化重新映射的成本更低。

Answer 1

可以注意到，随着n的增长，热点和最佳节点之间的负载差异变小，所以通常的解决方案是引入大量虚拟节点（人为地增加n value) 并让真实节点托管多个虚拟节点，以帮助更均匀地分布数据。

这是业界的普遍做法，例如 Riak 和 Cassandra 就使用它。您可以在这里阅读：

What is virtual nodes and how it is helping during partitioning in Casssandra
Vnodes and their role in Riak

在分布式散列中的节点连接期间优化键空间分区 table

Optimizing keyspace partitioning during node joins in a distributed hash table

algorithm

distributed

dht

consistent-hashing