2012-09-07 10 views
19

Ich bin in der Suche nach einem consistent hash Algorithmus in einigen Java-Code, den ich schreibe. Die Guava-Hashing-Bibliothek hat eine consistentHash(HashCode, int) Methode, aber the documentation fehlt eher. Meine anfängliche Hoffnung war, dass ich einfach consistentHash() für einfache Sitzungsaffinität verwenden konnte, um die Last effizient auf eine Reihe von Backend-Servern zu verteilen.Wie sollte ich Guavas Hashing # consequentHash verwenden?

Hat jemand ein Beispiel aus der Praxis, wie man diese Methode benutzt? Insbesondere gehe es mir darum, das Entfernen eines Eimers aus dem Zielbereich zu verwalten.

Zum Beispiel:

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

führt zur Ausgabe:

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

Was ich will, ist für diese Kennung ("someId") auf den gleichen Server nach dem Entfernen eines Server früher zur Karte In der Liste. Also im obigen Beispiel würde ich nach dem Entfernen wahrscheinlich Bucket 0 auf "Server1", Bucket 1 auf "Server3", Bucket 2 auf "Server4" und Bucket 3 auf "Server5" mappen.

Soll ich eine separate (komplizierter als eine Liste) Datenstruktur verwalten, um Bucket-Entfernung und -Einfügung zu verwalten? Ich denke, ich hatte mir vielleicht eine kompliziertere Hashing-API vorgestellt, die die Neuzuordnung nach dem Hinzufügen und Entfernen bestimmter Buckets für mich verwalten würde.

Hinweis: Ich weiß, dass der Beispielcode eine kleine Eingabe und einen Bucket-Satz verwendet. Ich habe dies mit 1000 Eingaben pro 100 Buckets versucht und das Ergebnis ist das gleiche. Eingaben, die den Buckets 0 bis 98 zugeordnet sind, bleiben gleich, wenn ich den Wert buckets zu 99 ändere und der Bucket 99 über die restlichen 99 Buckets verteilt wird.

+0

Sie beachten ist richtig ... aber man kann sehen, dass Guava nichts über Ihre Liste außer seiner Größe kennt, kann Bist du? So kann es nichts anderes tun. – maaartinus

+0

Ich denke, das ist der Dokument-Link, den Sie wirklich möchten: http://docs.guava-libraries.googlecode.com/git-history/release13/javadoc/com/google/common/hash/Hashing.html#consistentHash%28com. google.common.hash.HashCode,% 20int% 29 - obwohl es wahr ist, gibt es dort nicht viel, was soll es sonst noch sagen? –

+0

@Kevin - Die Dokumentation ist wahrscheinlich O.K. Wenn überhaupt ein paar Worte mehr über die Anforderung auf Ergänzungen/Entfernungen am Ende sein. Ich habe meine Frage gestellt, weil ich gehofft hatte, dass meine Interpretation falsch ist, und es gab einen offensichtlichen Weg, die Bucket-Manipulation zu verwalten, an die ich nicht gedacht hatte. Ich kam zur Guava-Methode, nachdem ich mit dem Wikipedia-Eintrag begonnen hatte und die dort erwähnte Java-Implementierung gelesen hatte, also erwartete ich etwas näher zu sehen, was diese beiden Artikel beschreiben (mehr wie Chris Beschreibung, was in einer Antwort unten steht). – GamingBuck

Antwort

3

Ich habe Angst, dass keine Datenstruktur es wirklich richtig mit dem aktuellen consistentHash tun kann. Da die Methode nur die Listengröße akzeptiert, kann nur das Anhängen und Entfernen am Ende unterstützt werden. Derzeit besteht die beste Lösung wahrscheinlich

ersetzen
servers.remove(n) 

von

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

diese Weise können Sie eine Art des gescheiterten und der allerletzte Server tauschen. Das sieht schlecht aus, da es die Zuweisungen zu den zwei ausgelagerten Servern falsch macht. Dieses Problem ist nur halb so schlimm, wie einer von ihnen fehlgeschlagen ist. Aber es macht Sinn, denn nach dem folgenden Entfernen des letzten Listenelements ist alles in Ordnung, außer den Zuordnungen zum ausgefallenen Server und zum letzten Server.

Also doppelt so viele Zuweisungen wie nötig ändern.Nicht optimal, aber hoffentlich nutzbar?

+0

Danke für die schnelle Antwort. Es scheint eine vernünftige Lösung zu sein, bis eine reichere API verfügbar ist. Ich werde wahrscheinlich entweder mit diesem gehen oder mein eigenes basierend auf anderen Sprachimplementierungen rollen. – GamingBuck

+0

@GamingBuck: Ich habe gerade [eine bessere (vielleicht sogar optimale) Lösung] (https://dl.dropbox.com/u/4971686/published/maaartin/guava/consistenthash/index.html) erstellt. – maaartinus

3

Ich glaube nicht, dass es im Moment einen guten Weg gibt, dies zu tun. consistentHash in seiner aktuellen Form ist nur in einfachen Fällen nützlich - im Grunde, wo Sie einen Knopf haben, um die Anzahl der Server zu erhöhen oder zu verringern ... aber immer durch Hinzufügen und Entfernen am Ende.

Es gibt einige Arbeiten im Gange eine Klasse wie folgt hinzuzufügen:

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

Dann würden Sie schreiben:

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

Und Sie sollten die gleichen Server jedes Mal bekommen. Ist diese API geeignet?

+0

Ich muss zugeben, dass ich die Funnel API noch nicht genau angeschaut habe, aber auf den ersten Blick scheint das praktikabel zu sein. Ich freue mich auf die Verfügbarkeit. – GamingBuck

+0

Irgendwelche Neuigkeiten dazu? Ich kann eine 'weightedConsistentHash'-Referenz in [v14] sehen (http://docs.guava-libraries.googlecode.com/git-history/v14.0.1/javadoc/com/google/common/hash/Hashing.html). , aber nicht in [v16] (http://docs.guava-libraries.googlecode.com/git-history/v16.0.1/javadoc/com/google/common/hash/Hashing.html). Referenz entfernt von Colin in Commit 9acc76ba4. – maaartinus

2

Die Guava API hat keine Kenntnis Ihrer Serverliste. Es kann nur garantieren:

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 

Sie den Eimer auf Ihre Serverliste manange brauchen, um sich