Как использовать Guava Hashing # consHash?

Я изучаю алгоритм согласованный хеш-алгоритм в некотором java-коде, который я пишу. Хватая библиотека guava имеет метод 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));
}

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

First time routed to: server4
Second time routed to: server5

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

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

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

Ответ 1

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

servers.remove(n)

по

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

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

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

Ответ 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?

Ответ 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

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