Guava'nın Hashing # consistentHash'ı nasıl kullanmalıyım?

Question

Bazı java kodlarında consistent hash algoritmasını arıyorum. Guava Hashing kitaplığı consistentHash(HashCode, int) yöntemine sahiptir, ancak the documentation eksiktir. İlk umudum, bir dizi arka uç sunucusunda yükü verimli bir şekilde dağıtmak için consistentHash()'u basit oturum yakınlığı olarak kullanabilmemdi.

Bu yöntemin nasıl kullanılacağına dair gerçek bir dünya örneği var mı? Özellikle de hedef alandan bir kepçenin kaldırılmasını yönetmekle ilgileniyorum.

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

çıkışına İlanlar: Örneğin:

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

İstediğim bir sunucu daha önce kaldırılmasından sonra aynı sunucuya eşlemek için bu tanımlayıcı ("SomeID") içindir listede. Yukarıdaki örnekte, kaldırma işleminden sonra, "server1" 'e eşlemek için "bucket", "server3"' e eşlemek için bucket 1, "server4" 'e eşlemek için bucket 2 ve "server5"' e eşlemek içinse bucket 3 'ün olmasını istiyorum.

Kova çıkarma ve ekleme işlemlerini yönetmek için ayrı bir (bir listeden daha karmaşık) veri yapısını korumalı mıyım? Sanırım özellikle benim için özel kovalar ekledikten ve çıkardıktan sonra yeniden işlemeyi yönetecek daha karmaşık bir Hashing API'sini tahmin ettim.

Not: Örnek kodun küçük bir giriş ve kova seti kullandığını biliyorum. Bunu 100 kova üzerinden 1000'lerce girdi ile denedim ve sonuç aynı. buckets - 99'u değiştirdiğimde 0-98 no'lu kovalara eşlenen girişler aynı kalır ve kova 99, kalan 99 kovaya dağıtılır.

Answer 1

Hiçbir veri yapısının, geçerli consistentHash ile gerçekten doğru yapamayacağından korkuyorum. Yöntem yalnızca liste boyutunu kabul ettiğinden, sondan ekleme ve çıkarma işlemlerinden hiçbiri desteklenemez. Şu anda, en iyi çözüm

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

sıralamak başarısız takas Bu şekilde ve en son sunucu tarafından

servers.remove(n) 

değiştirme muhtemelen oluşur. Bu, iki takaslı sunucuya atamaları yanlış yaptığı için kötü görünüyor. Bu sorun, bir tanesi başarısız olduğu kadar sadece yarısı kadar kötü. Ancak, son liste elemanının kaldırılmasından sonra, başarısız sunucuya ve önceki son sunucuya yapılan atamalar haricinde her şey yolundadır.

Gerekli değişiklik olarak iki kat fazla ödev.Optimal değil, ama umarım kullanılabilir mi?

Answer 2

Şu anda bunu yapmanın iyi bir yolu olduğunu sanmıyorum. Mevcut haliyle consistentHash sadece basit durumlarda yararlıdır - temelde, sunucu sayısını artırmak veya azaltmak için bir düğme var ... ama her zaman sonunda ekleyerek ve kaldırarak.

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

Ve aynı her seferinde sunucuyu almalısınız:

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

Sonra yazardı:

Orada böyle bir sınıf eklenmesi için çalışmalar bazı iş. Bu API uygun görünüyor mu?

Answer 3

guava API'sı sunucu listeniz hakkında herhangi bir bilgiye sahip değildir. can,

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 

Eğer sunucu listesinden kendinize Sen dikkat