c++ - 一个好的重新分区算法

Question

我正在实现 memcached客户端库。我希望它支持多个服务器，因此我希望添加一些负载平衡系统。

基本上，您可以在服务器上执行两个操作:

• 存储 value鉴于其 key .
• 获取value鉴于其 key .

假设我有 N服务器(从 0 到 N - 1 )，我想要一个重新分区函数，从给定的 key和服务器编号 N , 会给我一个 index在[0, N[范围。

unsigned int getServerIndex(const std::string& key, unsigned int serverCount);

该函数应尽可能快速和简单，并且必须遵守以下约束:

getServerIndex(key, N) == getServerIndex(key, N); //aka. No random return.

我希望我可以不使用外部库(例如OpenSSL 及其散列函数)来做到这一点。我在这里有哪些选择？

---

旁注:

显然，基本实现:

unsigned int getServerIndex(const std::string& key, unsigned int serverCount)
{
  return 0;
}

这不是一个有效的答案，因为这不是一个很好的重新分区函数:D

---

附加信息:

键通常是 ANSI 字符集中的任何可能的字符串(主要是 [a-zA-Z0-9_-] )。大小可以是从单字符键到您想要的任何大小的任何值。

一个好的重新分区算法是一种返回概率为a的算法。与返回概率相等(或不太远)b , 对于两个不同的键。服务器的数量可能会发生变化(尽管很少发生)，如果发生变化，则给定 key 的返回索引是可以接受的也有变化。

Answer 1

您可能正在寻找实现 consistent hashing 的东西.最简单的方法是为每个内存缓存服务器分配一个随机 ID，并根据某种指标将每个项目分配给 ID 最接近该项目哈希值的内存缓存服务器。

这是一个常见的选择 - 也是分布式系统所采用的选择，例如 Kademlia - 将使用 SHA1 哈希函数(尽管哈希并不重要)，并通过对项目的哈希与服务器的哈希进行异或并将结果解释为大小来比较距离。那么，您所需要的只是一种让每个客户端都知道内存缓存服务器列表及其 ID 的方法。

当一个 memcache 服务器加入或离开时，它只需要生成自己的随机 ID，然后要求它的新邻居向它发送任何比自己的哈希值更接近它的哈希值的项目。