Jump Consistent Hash

jump consistent hashというアルゴリズムがなかなかすごいアイデアな気がする。記事を解読しているが、文章として読みづらい。文章だとか見栄えだとかを気にしたり引用で泊をつけるとかせずに雑い投稿ですごいことを書いているのは、中身だけ興味がある感じでかっこいいかもしれない。理解しきれていないがメモ書きしておく。

consistent hashというのは分散ストレージによく使われるデータ構造だ。複数のノードに分散して記憶させるときには、どのノードにどのデータを記憶するのかというマッピングを行う必要がある。アロケーション情報を覚えるサーバーを置くという手段もあるが、それだとそのサーバーが単一障害点になるし、データを読み書きするのにいちいちそのサーバーに問い合わせを行わなければならない。そこでデータの名前を入力すればそのデータがあるべきノードを返す関数というのが欲しくなる。データにアクセスする人はその関数さえ知っておけば、直接データを持つノードに問い合わせることができる。当然データはノード間でなるべく均等になるように配置したい。また、データをもつノードを増やしたときに全てのデータの位置がズレてしまい、データを移動させなければならないということは避けたい。これらを満足するアルゴリズムがconsistent hashである。

例えばApache Cassandra (Amazon Dynamo) に使われている。Cassandraの設計はシンメトリックで美しい。

しかし、唯一いまいちだなと思うのはconsistent hashなのです。consistent hashを最初に考えた人は偉大だと思うけれども、欠陥が多い。メモリは食うし、計算は早くないし、データはノード間で均等にはならない。そのために他のアルゴリズムが考案されてきた。例えば、CephのCRUSHアルゴリズムである。

jump consistent hashもその一つである。発想としてはCRUSHアルゴリズムの中のList Bucketと近いように思う。しかし、List Bucketの計算量はノード数に比例(O(n))であるのに対して、jump consistent hashはノード数の対数に比例(O(log(n)))する。

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

jump consistent hashの実装はこれだけだ。謎のマジックナンバーに面食らうが、

key = key * 2862933555777941757ULL + 1;
r = double((key >> 33) + 1)) / double(1LL << 31)

としたときのrは(0, 1)の(key, j)をseedとした乱数であり他の乱数でも良い。

key(例えばデータの名前)とノードの数を入力したらデータがあるべきノードの番号を出力する。制限はノードは名前でなくて連番がついていなければならないという点だ。そのため、分散キャッシュには使いにくい。ノードをインクリメンタルに増やしていくような分散ストレージに特化している。ノードを減らすのは苦手そうだ。この点はList Bucketと同じである。計算量削減のために発想の転換があって興味深いのだが、まだまとめきれない。

参考

  1. A Fast, Minimal Memory, Consistent Hash Algorithm
  2. Dynamo: Amazon’s Highly Available Key-value Store
  3. CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data

追記 2016-03-27

List BucketとJump Consistent Hashをミックスしたアルゴリズムを発見した。

A Algorithm for Mapping Data to Storage Clusters