google jump consistent hash / Maglev hash

consistent hash는 bucket이 추가되더라도, 추가된 버킷으로 이동한 엘리먼트를 뺀 나머지 엘리먼트는 버킷의 변화가 없는 해시를 말한다. 

가장 대표적인 게 링에 버킷 구역을 끼워 넣는 karger hash... 

근데 대부분의 해시는 버킷 밸런스가 매우 안 좋은 편이다.  

jump consistent hash

google에서 jump consistent hash를 만들었다.

버킷이 n개일 때 1개가 추가되면 1(n+1)의 확률로 새로 추가 된 버킷으로 옮겨간다. 

이 아이디어를 그대로 옮기면 다음이 된다. 

----------------------------------------------------------------------
int ch(int key, int num_buckets) {
   random.seed(key);
   int b = 0;  // This will track ch(key, j+1).
   for (int j = 1; j < num_buckets; j++) {   //기존 상황에서 버킷이 하나씩 추가된다. 
      if (random.next() < 1.0 / (j + 1)) b = j;  // 다음의 확률로 새로운 버킷으로 바꾼다.
   }
   return b;
}
----------------------------------------------------------------------

suppose that b was the destination of the last jump, that is, ch(k, b) ≠ ch(k, b+1), and ch(k,
b+1) = b. 

  버킷을 추가해서 b+1개의 버킷이 있다. k는 마지막 버킷으로 옮겨간다. 

Now, we want to find the largest j such that ch(k, j) = ch(k, b+1). 

We will make a pseudo­random variable whose value is that j.

 k는 최대 j 개의 버킷이 추가 될 때 까지 움직이지 않는다. 이 확률적 j를 구해 보자.

To get a probabilistic constraint on j, note that for any bucket number, i, we
have j ≥ i if and only if the consistent hash hasn’t changed by i, that is, if and only if ch(k, i) =
ch(k, b+1). Hence, the distribution of j must satisfy

이를 위해 i를 두자. i 는 k의 버킷이 b가 되는 버킷 수이고, i의 최대값이 j이다. 

 그런 i의 존재 확률은

 P(j ≥ i > b+1) = P( ch(k, i) = ch(k, b+1) ) = (b+1) / i = P (r ≤ (b+1) / i ) (r은  0-1 사이 균등랜덤)

  P(j ≥ i > b+1) =   P(j ≥ i )  - P(i <= b+1) =    P(j ≥ i )   = P (r ≤ (b+1) / i ) 

P(i <= b+1)  = 0 <- 버킷이 B가 없는데, b+1 보다 더 작은 i는 b로 배정될 수 없다.

i ≤ (b+1) / r 를 얻을 수 있다.

P(j ≥ i), thus the largest i satisfying i ≤ (b+1) / r.

----------------------------------------------------------------------

 j = floor((b+1) / r)

int ch(int key, int num_buckets) {

   random.seed(key);

   int b = ­1;  // bucket number before the previous jump

   int j = 0; // bucket number before the current jump

   while (j < num_buckets) {

      b = j;

      r = random.next();

      j = floor((b + 1) / r);

   }

   return = b;

}

----------------------------------------------------------------------최종

 int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
  int64_t b = ­1, j = 0;
  while (j < num_buckets) {
    b  =  j;
    key = key * 2862933555777941757ULL + 1;
    j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
  }
  return  b;
}
----------------------------------------------------------------------

Maglev consistent hash

 근데 그래도 밸런스가 완벽하지 않다. 확률적인 거니깐.. 

밸런스가 중요한 로드밸런서 Maglev에는 또 다른 해시를 만들었다.

google consistent hash가 밸런스가 맞지 않는 문제를 (강제로?) 해결한 것이다. 

알고리즘은

엘리먼트가 N개, 버킷(엔트리)이 M개 있다.  (M >> N)

각 엘리먼트(i)에 대해 M개의 엔트리를 랜덤하게 방문하도록 하는 permutation 함수를 만든다. 

각 엘리먼트 순서대로, permutation으로 만든 방문 순서대로 엔트리를 조회하고,

해당 엔트리가 비었으면 엘리먼트를 넣는다. 

비어있지 않으면 비어있는 엔트리가 나올 때 까지 다음 순서의 엔트리를 조회한다. 

엔트리를 하나 채우면 다음 엘리먼트로 넘어 간다. 

엔트리를 모두 채울 때 까지 반복한다.

maglev 논문.

http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf