con - java crud

¿Cómo debo usar Guava''s Hashing#consistente Hash?

Question

Estoy estudiando el uso de un algoritmo hash consistente en algún código Java que estoy escribiendo. La biblioteca de guash Hashing tiene un método de hash consistentHash(HashCode, int) , pero la documentación es bastante deficiente. Mi esperanza inicial era poder usar el consistentHash() para una afinidad de sesión simple para distribuir eficientemente la carga en un conjunto de servidores de back-end.

¿Alguien tiene un ejemplo del mundo real de cómo usar este método? En particular, me preocupa la gestión de la eliminación de un cubo del rango objetivo.

Por ejemplo:

@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));
}

Conduce a la salida:

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

Lo que quiero es que ese identificador ("someId") se asigne al mismo servidor después de eliminar un servidor anteriormente en la lista. Así que en el ejemplo anterior, después de la eliminación supongo que querría que el grupo 0 se asigne a "server1", el grupo 1 a "server3", el grupo 2 a "server4" y el grupo 3 a "server5".

¿Se supone que debo mantener una estructura de datos separada (más complicada que una lista) para administrar la eliminación y adición del grupo? Supongo que había imaginado tal vez una API de Hashing más complicada que administraría la reasignación después de agregar y eliminar determinados cubos para mí.

Nota: Sé que el código de ejemplo está utilizando una pequeña entrada y un conjunto de cubetas. Intenté esto con miles de entradas en 100 cubos y el resultado es el mismo. Las entradas que se asignan a los grupos 0-98 permanecen iguales cuando cambio los buckets a 99 y el grupo 99 se distribuye en los 99 grupos restantes.

Answer 1

La API de guayaba no tiene ningún conocimiento de su lista de servidores. Solo puede garantizar esto:

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 

Usted necesita administrar el cubo a su lista de servidores usted mismo

Answer 2

La respuesta propuesta en la pregunta es la correcta:

¿Se supone que debo mantener una estructura de datos separada (más complicada que una lista) para administrar la eliminación y adición del grupo?

La guayaba se mezcla en un anillo con números ordinales. La asignación de esos números ordinales a los ID de servidor debe mantenerse externamente:

• Dados los servidores N inicialmente: se puede elegir una asignación arbitraria para cada número ordinal 0..N-1 a los ID de servidor A..K ( 0 -> A , 1 -> B , .., N-1 -> K ) . También se requiere una asignación inversa del ID del servidor a su número ordinal ( A -> 0 , B -> 1 , ..).

• En la eliminación de un servidor, el espacio numérico ordinal se reduce en uno. Todos los números ordinales que comienzan con el del servidor eliminado deben volver a asignarse al siguiente servidor (cambiar en uno).

  Entonces, por ejemplo, después de la asignación inicial, digamos que el servidor C (correspondiente al número ordinal 2) se eliminó. Ahora las nuevas asignaciones se convierten en: ( 0 -> A , 1 -> B , 2-> D , 3 -> E , .., N-2 -> K )

• Al agregar un servidor L (es decir, pasar de N a N + 1 servidores), se puede agregar una nueva asignación de N-> L.

Lo que estamos haciendo aquí es imitar cómo se moverían los nodos en un anillo a medida que se agregan y eliminan. Mientras que el orden de los nodos sigue siendo el mismo, sus números ordinales (en los que opera Guava) pueden cambiar a medida que los nodos van y vienen.

Answer 3

Me temo que ninguna estructura de datos puede hacerlo realmente bien con el hash consistentHash actual. Como el método solo acepta el tamaño de la lista, no se puede admitir nada más que agregar y eliminar del final. Actualmente, la mejor solución consiste probablemente en reemplazar

servers.remove(n)

por

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

De esta manera, de alguna forma intercambiarás el último y el último servidor. Esto se ve mal ya que hace que las asignaciones a los dos servidores intercambiados sean incorrectas. Este problema es tan malo como la mitad de uno de ellos. Pero tiene sentido, ya que después de la siguiente eliminación del último elemento de la lista, todo está bien, excepto las asignaciones al servidor fallido y al último servidor anterior.

Por lo tanto, el doble de las tareas que se necesiten cambian. ¿No es óptimo, pero con suerte utilizable?

Answer 4

No creo que haya una buena manera de hacer esto en este momento. consistentHash en su forma actual es útil solo en casos simples, básicamente, donde tiene un botón para aumentar o disminuir el número de servidores ... pero siempre agregando y eliminando al final.

Hay algunos trabajos en curso para agregar una clase como esta:

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);
}

Entonces escribirías:

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"));

Y deberías tener el mismo servidor cada vez. ¿Esa API parece adecuada?