Consistent Hashingを計算してみる

libmemcachedを流用して，こんなコマンドラインプログラムを書いてみました．

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(int argc, char *argv[])
{
  if(argc<2)
  {
    printf("usage: %s string\n",argv[0]);
    exit(0);
  }
  if(sizeof(unsigned int)!=4)
  {
    printf("please replace unsigned int for 32bit type\n");
    exit(0);
  }
  int key_len = strlen(argv[1]);
  char *key = (char *)malloc(key_len+1); /* for CR */
  strcpy(key, argv[1]);
  unsigned int value= 0;

  while (key_len--)
  {
    unsigned int val= (unsigned int) *key++;
    value += val;
    value += (value << 10);  // value += value *= 2^10
    value ^= (value >> 6);
  }
  value += (value << 3);
  value ^= (value >> 11);
  value += (value << 15);

  unsigned int hash_value = value == 0 ? 1 : (unsigned int) value;
  printf("hash = %u\n",hash_value);
  return(0);
}

コンパイルして実行します．

> cc generate_default_consistent_hashing.c

まず，3つのmemcachedサーバがあるとします．そのホスト名でハッシュを計算します．

> ./a.out localhost01
hash = 2484904651
> ./a.out localhost02
hash = 378546096
> ./a.out localhost03
hash = 266803806

これをハッシュ値で並べてみると，ホストは次のように並べられていることに相当します．

[0] <-(A)-> localhost03[266803806] <-(B)-> localhost02[378546096] <-(C)-> localhost01[2484904651] <-(D)-> [4294967295]

(A)はlocalhost03に，(B)はlocalhost02に，(C)はlocalhost01に，(D)は，コンシステント・ハッシングはトーラス状に並ぶと考えるそうなので[0]と繋がっていると考え，やはりlocalhost03にストアされます．

適当なキーでハッシュを計算してみます．

> ./a.out key1
hash = 3203718188 --> (D)=(A)=localhost03
> ./a.out key2
hash = 2905880747 --> (D)=(A)=localhost03
> ./a.out key3
hash = 3682768199 --> (D)=(A)=localhost03
> ./a.out key4
hash = 3386175980 --> (D)=(A)=localhost03
> ./a.out key5
hash = 4101556019 --> (D)=(A)=localhost03

なんと全てのキーがlocalhost03にストアされることになりました．localhost03の負荷が高そうですね．
でも，localhost01やlocalhost02が落ちても，バリューは消えずにすむようです．localhost03が落ちると，キャッシュは全部構築し直しです．

もう少し複雑なキーでハッシュを計算してみます．

> ./a.out yahoo.co.jp
hash = 1591825169 --> (C)=localhost01
> ./a.out rakuten.co.jp
hash = 2584871479 --> (D)=(A)=localhost03
> ./a.out amazon.co.jp
hash = 3280703220 --> (D)=(A)=localhost03
> ./a.out msn.co.jp
hash = 2112415372 --> (C)=localhost01
> ./a.out google.co.jp
hash = 1868171465 --> (C)=localhost01

この場合，localhost01が落ちると3/5のキャッシュが構築し直し，localhost02が落ちても影響なし，localhost03が落ちると2/5のキャッシュが構築し直しになるようです．

その他のパターンは，また次回に．