Хороший алгоритм перераспределения

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 хороший алгоритм перераспределения - это алгоритм, для которого вероятность возврата a равна (или не слишком далека) от вероятности возврата b для двух разных ключей. Число серверов может измениться (хотя и редко), и если это так, допустимо, что изменяется и возвращаемый индекс для данного key.

Answer 1

Возможно, вы ищете что-то, что реализует согласованное хеширование . Самый простой способ сделать это - назначить случайный идентификатор каждому серверу memcache и назначить каждый элемент серверу memcache, который имеет ближайший идентификатор к хэшу элемента по некоторой метрике.

Общий выбор для этого - и тот, который используется распределенными системами, такими как Kademlia - - это использовать хеш-функцию SHA1 (хотя хеш-функция не важна) и сравнивать расстояния с помощью XORing хэша элемента с хэшем сервера и интерпретируя результат как величину. Все, что вам нужно, это способ информирования каждого клиента о списке серверов memcache и их идентификаторах.

Когда сервер memcache присоединяется или уходит, ему нужно только сгенерировать свой собственный случайный идентификатор, а затем попросить своих новых соседей отправить ему любые элементы, которые ближе к его хешу, чем к его собственному.

Answer 2

Я думаю, что подход хэширования - правильная идея. Существует множество упрощенных алгоритмов хеширования.

С наступающим C ++ 0x и новым стандартом unordered_map, hash строк становится стандартной операцией. Многие компиляторы уже поставляются с версией STL, которая имеет hash_map и, таким образом, уже имеет предварительно реализованную функцию hash.

Я бы начал с этих ... но было бы лучше, если бы у нас было больше информации о ваших строках: они каким-то образом ограничены ограниченным набором символов или вполне вероятно, что они будут иметь много похожих строк?

Проблема в том, что «стандартный» хеш может не дать равномерного распределения, если входные данные распределены неравномерно для начала ...

EDIT

Учитывая информацию, я думаю, что хеш-функция, уже поставляемая с большинством STL, должна работать, так как у вас, похоже, нет высококонцентрированной области. Однако я до сих пор хорошо разбираюсь в вероятностях, поэтому возьмите его с собой (и проведите эксперимент).

Answer 3

Как насчет чего-то очень простого, например

hash(key) % serverCount