3

给定一组静态目标，循环散列算法提供一致性。例如：

  1. 我有一组初始目标，我们称它们A为B和C。
  2. 我有钥匙，我们就叫它吧x
  3. 我有一个循环哈希函数，我们称之为hash(key, targets)
  4. 当我打电话时hash(x, [A,B,C])，x总是哈希到A

似乎足够明显。A我总是得到的事实x代表了我在使用循环哈希时所期望的一致性。但是，现在让我们考虑如果我添加一个新节点会发生什么D：

  1. 我的目标集重新平衡以包括A、B、C和D
  2. 我重新申请我的x钥匙hash(x, [A,B,C,D])
  3. 因为圈子重新平衡了，我不能保证再A得到

我错过了什么还是我只是运气不好？当您开始重新排序节点（例如hash(x, [B,A,D,C])）或在现有节点列表的中间插入新节点（例如 ）时，问题会进一步恶化hash(x, [A,AA,B,C,D])。我对循环散列的学术方面进行了一些研究，这种类型的“缩放一致性”似乎并不是它的主要关注点之一。也许我只是使用了错误类型的哈希算法？

4

4 回答 4

1

您的问题有一个非常简单的解决方案。这是它如何工作的示例。

假设您有 3 个真实目标（即物理机）：A、B、C。然后引入 9 个虚拟目标：1、2、3、4、5、6、7、8、9 并从虚拟目标建立静态映射像这样的真正目标：

1, 2, 3 -> A
4, 5, 6 -> B
7, 8, 9 -> C

当您需要读取/写入某个键的值时，您首先使用哈希函数将键映射到虚拟目标，然后使用上面显示的静态映射将虚拟目标映射到真实目标。一旦某个真实目标为多个虚拟目标提供服务，它应该将它们存储在单独的哈希映射中，因此真实目标 B 为其服务的三个虚拟目标具有三个单独的哈希映射。

现在我们要添加新的真实目标： D. 我们首先重新平衡我们的静态映射，例如：

1, 2, 3 -> A
4, 5 -> B
7, 8 -> C
6, 9 -> D

然后我们将服务于虚拟目标的哈希映射6从真实目标B转移到新的真实目标D。我们还将地图服务虚拟目标9从转移C到D。此操作具有复杂性O(n)，其中n传输的值的数量是多少，因为每个真实目标都在单独的哈希映射中为每个虚拟目标服务。

为了获得良好的负载平衡，虚拟目标的数量应该比实际目标的最大可能数量估计值大几倍（例如 10 倍）。

换句话说，该解决方案的主要思想是使用哈希函数将键映射到虚拟目标的数量不变的虚拟目标。然后使用静态映射将虚拟目标映射到真实目标，并且当添加或删除真实目标时，此静态映射会发生变化。

于 2013-03-08T18:40:36.517 回答
0

I couldn't interpret your entire question in a consistent way, so I will guess what you really wanted to ask and answer based on that.

Assumed problem: You have a bunch of objects (e.g. strings) and you have a bunch of machines, and you want to assign each object to a machine in order to spread the workload among the machines. When a machine joins or leaves the pool of machines, you don't want to reshuffle too many of the object-to-machine assignments ("scaling consistency").

I think you have a misunderstanding where you said you hash the object x to map a machine in the pool [A,B,C]. My understanding is that there are three intermediate steps involved.

  1. Calculate a hash value for each object. Suppose that the hash output space is something large like all integers from 0 to 232 − 1.

  2. Assign a value (in the same number space) to each machine, which it keeps constant for its lifetime. You would want to spread these numbers out randomly.

  3. Now, we assign each object to belong to the closest upward machine. That means if the object's hash is x, then it belongs to the machine M such that M's value is the smallest number greater than x.

Example:

  1. We have 4 string objects with their respective hash in the range 0 to 999: abc=314, def=125, ghi=802, jkl=001.

  2. We have 3 machines, with these numbers: X=010, Y=357, Z=768.

  3. Which machine does object abc=314 belong to? Counting upwards, the closest machine is Y=357.
    Which machine does object ghi=802 belong to? Counting upwards, the closest machine is X=010.

于 2013-03-08T03:55:25.240 回答
0

好的，我想我明白了。

我最终使散列算法保持简单，并使用“校验和”（排序）来确保 x 始终键为同一个目标。当添加新目标并且系统重新平衡时，我只需通知所有现有目标有关重新平衡的信息。这样，如果 x 散列到不应再散列到的目标，则目标可以委托给正确的目标。

感谢您的所有回复，如果不是因为你们都提供了清晰的信息，我可能不会想到这个解决方案。

干杯，

乔恩

于 2013-03-09T05:06:16.367 回答
0

当您扩展散列函数的允许输出范围时，理所当然的一些输入将散列到不同的输出（否则扩展范围没有意义）。唯一的方法是哈希函数存储所有以前的结果（或压缩的，可能有损的相同形式，如布隆过滤器），以便它可以记住将“旧”结果用于它的输入以前见过。

于 2013-03-08T03:19:28.573 回答