Как я должен использовать хеширование в Guava #istentHash?

Question

Я пытаюсь использовать согласованный алгоритм хеширования в некотором Java-коде, который пишу. Библиотека хеширования гуавы имеет consistentHash(HashCode, int) метод, но документации довольно не хватает. Моя первоначальная надежда заключалась в том, что я мог просто использовать consistentHash() для простого соответствия сеанса для эффективного распределения нагрузки по набору внутренних серверов.

У кого-нибудь есть реальный пример того, как использовать этот метод? В частности, я занимаюсь удалением ведра из целевого диапазона.

Например:

@Test
public void testConsistentHash() {
    List<String> servers = Lists.newArrayList("server1", "server2", "server3", "server4", "server5");

    int bucket = Hashing.consistentHash(Hashing.md5().hashString("someId"), servers.size());
    System.out.println("First time routed to: " + servers.get(bucket));

    // one of the back end servers is removed from the (middle of the) pool
    servers.remove(1);

    bucket = Hashing.consistentHash(Hashing.md5().hashString("blah"), servers.size());
    System.out.println("Second time routed to: " + servers.get(bucket));
}

Приводит к выходу:

Впервые направлено на: server4
Второй раз направляется на: server5

Я хочу, чтобы этот идентификатор ("someId") отображался на тот же сервер после удаления сервера, ранее указанного в списке. Таким образом, в приведенном выше примере, после удаления, я бы хотел, чтобы сегмент 0 отображался на "server1", сегмент 1 - на "server3", контейнер 2 - на "server4", а сегмент 3 - на "server5".

Должен ли я поддерживать отдельную (более сложную, чем список) структуру данных для управления удалением и добавлением сегментов? Наверное, я предполагал, возможно, более сложный Hashing API, который бы управлял переназначением после добавления и удаления определенных сегментов для меня.

Примечание. Я знаю, что в примере кода используется небольшой набор входных данных и набор блоков. Я пробовал это с 1000 входами через 100 сегментов, и результат тот же. Входы, которые отображаются на сегменты 0-98, остаются теми же, когда я меняю buckets до 99 и сегмент 99 распределяется по оставшимся 99 сегментам.

Answer 1

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

servers.remove(n)

от

server.set(n, servers.get(servers.size() - 1);
servers.remove(servers.size() - 1);

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

Таким образом, в два раза больше заданий, чем необходимо изменить. Не оптимально, но, надеюсь, пригодно для использования?

Answer 2

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

Идет работа над добавлением такого класса:

public final class WeightedConsistentHash<B, I> {
  /** Initially, all buckets have weight zero. */
  public static <B, I> WeightedConsistentHash<B, I> create(
      Funnel<B> bucketFunnel, Funnel<I> inputFunnel);

  /**
   * Sets the weight of bucket "bucketId" to "weight".
   * Requires "weight" >= 0.0.
   */
  public void setBucketWeight(B bucketId, double weight);

  /**
   * Returns the bucket id that "input" maps to.
   * Requires that at least one bucket has a non-zero weight.
   */
  public B hash(I input);
}

Тогда вы бы написали:

WeightedConsistentHash<String, String> serverChooser =
    WeightedConsistentHash.create(stringFunnel(), stringFunnel());
serverChooser.setBucketWeight("server1", 1);
serverChooser.setBucketWeight("server2", 1);
// etc.

System.out.println("First time routed to: " + serverChooser.hash("someId"));

// one of the back end servers is removed from the (middle of the) pool
serverChooser.setBucketWeight("server2", 0);

System.out.println("Second time routed to: " + serverChooser.hash("someId"));

И вы должны получать один и тот же сервер каждый раз. Этот API выглядит подходящим?

Answer 3

API guava не знает о вашем списке серверов. Это может гарантировать только это:

int bucket1 = Hashing.consistentHash(Hashing.md5().hashString("server1"),N);    
int bucket2 = Hashing.consistentHash(Hashing.md5().hashString("server1"),N-1);

assertThat(bucket1,is(equalTo(bucket2))); iff bucket1==bucket2!=N-1 

вам нужно самим управлять списком серверов

Answer 4

Ответ, предложенный в вопросе, является правильным:

Должен ли я поддерживать отдельную (более сложную, чем список) структуру данных для управления удалением и добавлением сегментов?

Гуава перемешивает в кольцо с порядковыми номерами. Сопоставление этих порядковых номеров с идентификаторами сервера должно поддерживаться извне:

• Исходно для N серверов - можно выбрать произвольное отображение для каждого порядкового номера 0..N-1 на идентификаторы серверов A..K (0->A, 1->B,.., N-1->K), Также требуется обратное отображение идентификатора сервера на его порядковый номер (A->0, B->1,..).

• При удалении сервера - порядковый номер пространства уменьшается на единицу. Все порядковые номера, начинающиеся с номера для удаленного сервера, необходимо переназначить на следующий сервер (смещение на единицу).

  Так, например, после начального отображения, скажем, сервер C (соответствующий порядковому номеру 2) был удален. Теперь новые отображения становятся: (0->A, 1->B, 2-> D, 3->E,.., N-2->K)

• При добавлении сервера L (скажем, от N до N+1 серверов) - новое отображение может быть добавлено из N->L.

То, что мы делаем здесь, это имитация того, как узлы будут двигаться в кольце, когда они добавляются и удаляются. Хотя порядок узлов остается неизменным - их порядковые номера (по которым работает Guava) могут меняться по мере того, как узлы приходят и уходят.