0

当一个节点加入 DHT 网络时，新节点似乎最优的做法是平均划分一致哈希圆上的最大间隔，以最小化重新映射。然而，这仅对 2 n 个节点是最优的（假设从n =1 开始）；如果键被统一访问，所有其他数字都会创建热点：

  • n =2, 1 / 2 1 / 2 , 最优
  • n =3, 1 / 4 1 / 4 1 / 2，1 / 3个节点服务1 / 2流量的热点
  • n =4, 1 / 4 1 / 4 1 / 4 1 / 4 , 最优
  • n = 5, 1 / 8 1 / 8 1 / 4 1 / 4 1 / 4，热点有3 / 5个节点服务3 / 4的流量

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

  • n =2, 1 / 2 1 / 2
  • n =3, 1 / 3 1 / 3 1 / 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]

是否有其他/更好的解决方案（这是一个已解决的问题）？一般来说，我对 DHT 和分布式算法相对较新，但我没有发现在我读过的任何 DHT/p2p/分布式算法中都解决了这个问题。在我的特定场景中，最小化热点至关重要，而最小化重新映射成本更低。

4

1 回答 1

1

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

这是工业界的常见做法，例如 Riak 和 Cassandra 使用它。你可以在这里读到它：

于 2016-08-05T22:50:59.007 回答