Guava의 Hashing # consistentHash는 어떻게 사용해야합니까?

Question

내가 쓰고있는 일부 Java 코드에서 consistent hash 알고리즘을 사용하려고합니다. 구아바 해싱 라이브러리는 consistentHash(HashCode, int) 메소드를 가지고 있지만, the documentation은 다소 부족합니다. 나의 초기 희망은 간단 세션 친 화성을 위해 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")입니다 목록에. 그래서 위의 예제에서 제거 후 "server1", 버킷 1에 매핑 할 버킷 0을 "server3"에 매핑하고 버킷 2를 "server4"에 매핑하고 버킷 3을 "server5"에 매핑 할 것입니다.

버킷 제거 및 추가를 관리하기 위해 별도의 (목록보다 복잡한) 데이터 구조를 유지해야합니까? 아마도 나에게는 특정 버킷을 추가하고 제거한 후에 다시 매핑을 관리하는 좀 더 복잡한 해싱 API를 구상했을 것입니다.

참고 : 예제 코드는 작은 입력 및 양동이 세트를 사용하고 있습니다. 나는 100 개의 버킷에 걸쳐서 1000 초의 입력으로 이것을 시도했고 그 결과는 같습니다. buckets을 99로 변경하고 버킷 99를 나머지 99 개 버킷에 분산 시키면 버킷 0-98에 매핑되는 입력이 동일하게 유지됩니다.

Answer 1

데이터 구조가 현재 consistentHash에서 실제로 제대로 작동하지 않을까 걱정됩니다. 메서드가 목록 크기 만 허용하므로 끝에 추가 및 제거가 지원 될 수 있습니다. 현재, 가장 좋은 방법은

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

당신이 종류의 실패한으로 스왑이 방법과 매우 마지막 서버에서

servers.remove(n) 

을 대체하는 아마로 구성되어 있습니다. 두 개의 스왑 된 서버에 대한 할당이 잘못되어 나쁘다. 이 문제는 그 중 하나가 실패한 것만 큼 나쁜 것입니다. 그러나 마지막 목록 요소를 다음과 같이 제거한 후에는 실패한 서버 및 이전 서버에 대한 할당을 제외하고는 모든 것이 정상입니다.

필요에 따라 두 배의 할당이 변경됩니다.최적은 아니지만 잘하면 사용할 수 있습니까?

Answer 2

나는 지금이 일을하는 좋은 방법이 없다고 생각합니다. 현재 형태의 consistentHash은 단순한 경우에만 유용합니다. 기본적으로 서버 수를 늘리거나 줄이려는 노브가있는 곳이지만, 끝에 추가하거나 제거하면됩니다.

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

그리고 당신은 동일한 서버마다 얻을해야합니다

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

이 그럼 당신은 작성합니다

이 같은 클래스를 추가 진행 중 몇 가지 작업입니다. 해당 API가 적합합니까?

Answer 3

guava API에는 서버 목록에 대한 지식이 없습니다. 수,

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 

당신이 당신의 서버 목록 자신에게 당신은주의