Последовательное хеширование против хребта (HRW) - каковы компромиссы?

В Сети много доступных о последовательном хэшировании и реализациях на нескольких языках. Запись в Wikipedia для этой темы ссылается на другой алгоритм с теми же целями:

Rendezvous Hashing

Этот алгоритм кажется более простым и не требует добавления реплик/виртуальных элементов вокруг кольца для решения проблем с неравномерной загрузкой. Как упоминается в статье, она, похоже, работает в O (n), которая будет проблемой для больших n, но ссылается на документ, в котором говорится, что он может быть структурирован для работы в O (log n).

Мой вопрос для людей, имеющих опыт работы в этой области, заключается в том, почему нужно выбирать согласованное хеширование по HRW или наоборот? Существуют ли случаи, когда одним из этих решений является лучший выбор?

Большое спасибо.

Ответ 1

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

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

Большим преимуществом для HRW является добавление или удаление узлов, в которых вы поддерживаете равномерное распределение по всему. С помощью последовательных хэшей они разрешают это, предоставляя каждому виртуальному узлу node 200 или около того, что также затрудняет управление диапазонами вручную.

Ответ 2

Говоря как кто-то, кто просто должен был выбирать между двумя подходами и кто в конечном итоге набросился на хэш-настройку HRW: мой прецедент был простой балансировкой нагрузки, абсолютно без необходимости переназначения - если node умерла вполне нормально, просто выберите новый и начните снова. Не требуется повторная балансировка существующих данных.

1) Согласованное Хеширование требует постоянной хэш-карты узлов и vnodes (или, по крайней мере, разумной реализации, вы можете построить все объекты по каждому запросу.... но вы действительно не хотите!). HWR не является (он не имеет значения). Ничто не нуждается в изменении, когда машины соединяются или покидают кластер - нет проблем с concurrency (за исключением того, что ваши клиенты имеют хорошее представление о состоянии кластера, которое в обоих случаях одинаково)

2) HRW легче объяснить и понять (и код короче). Например, это полный алгоритм HRW, реализованный в Riverbed Stingray TrafficScript. (Обратите внимание, что лучше выбрать алгоритмы хеширования, чем MD5 - это излишнее для этого задания)

$nodes = pool.listActiveNodes("stingray_test");

# Get the key
$key = http.getFormParam("param");

$biggest_hash = "";
$node_selected = "";

foreach ($node in $nodes) {
   $hash_comparator = string.hashMD5($node . '-' . $key);

   # If the combined hash is the biggest we've seen, we have a candidate
   if ( $hash_comparator > $biggest_hash ) {
      $biggest_hash = $hash_comparator;
      $node_selected = $node;
   }
}

connection.setPersistenceNode( $node_selected );

3) HRW обеспечивает равномерное распределение, когда вы теряете или получаете узлы (если вы выбрали разумную хеш-функцию). Согласованное Хеширование не гарантирует этого, но с достаточным количеством vnodes это, вероятно, не будет проблемой.

4) Согласованная маршрутизация может быть более быстрой - при нормальной работе это должен быть порядок Log (N), где N - количество узлов * коэффициент реплики для vnodes. Однако, если у вас нет большого количества узлов (я этого не сделал), HRW будет, вероятно, достаточно быстрым для вас.

4.1) Как вы уже упоминали, википедия упоминает, что существует способ сделать HWR в log (N) времени. Я не знаю, как это сделать! Я доволен своим O (N) временем на 5 узлах.....

В конце концов, простота и безгражданность HRW сделали выбор для меня....