CephのStraw2について

Cephについて調べております。

CRUSHの中のstraw bucketというアルゴリズムに驚嘆したのですが、改良の余地がありそうだと思えたので、もっといい方法はないかと考えてしました。しかし、Cephの作者はおそろしく頭がよく、私の発想の2段階先に行っていました。straw2と呼ばれるものがすでに実装されておりました。

従来のstraw bucket

従来のstraw bucketのコードは以下のようになっています。

/* straw */

static int bucket_straw_choose(struct crush_bucket_straw *bucket,
                               int x, int r)
{
        __u32 i;
        int high = 0;
        __u64 high_draw = 0;
        __u64 draw;

        for (i = 0; i < bucket->h.size; i++) {
                draw = crush_hash32_3(bucket->h.hash, x, bucket->h.items[i], r);
                draw &= 0xffff;
                draw *= bucket->straws[i];
                if (i == 0 || draw > high_draw) {
                        high = i;
                        high_draw = draw;
                }
        }
        return bucket->h.items[high];
}

ランダムにstrawの長さを決定したあと、strawが選ばれる可能性を調整するための係数bucket->straws[i]を掛けあわせています。bucketのアイテムを追加・削除したり、重みを変更すると、すべてのアイテムについてこの係数を変更する必要があります。

新しいstraw bucket

新しいstraw bucketのコードは以下のようになっています。

/*
 * straw2
 *
 * for reference, see:
 *
 * http://en.wikipedia.org/wiki/Exponential_distribution#Distribution_of_the_minimum_of_exponential_random_variables
 *
 */

static int bucket_straw2_choose(struct crush_bucket_straw2 *bucket,
                                int x, int r)
{
        unsigned int i, high = 0;
        unsigned int u;
        unsigned int w;
        __s64 ln, draw, high_draw = 0;

        for (i = 0; i < bucket->h.size; i++) {
                w = bucket->item_weights[i];
                if (w) {
                        u = crush_hash32_3(bucket->h.hash, x,
                                           bucket->h.items[i], r);
                        u &= 0xffff;

                        /*
                         * for some reason slightly less than 0x10000 produces
                         * a slightly more accurate distribution... probably a
                         * rounding effect.
                         *
                         * the natural log lookup table maps [0,0xffff]
                         * (corresponding to real numbers [1/0x10000, 1] to
                         * [0, 0xffffffffffff] (corresponding to real numbers
                         * [-11.090355,0]).
                         */
                        ln = crush_ln(u) - 0x1000000000000ll;

                        /*
                         * divide by 16.16 fixed-point weight.  note
                         * that the ln value is negative, so a larger
                         * weight means a larger (less negative) value
                         * for draw.
                         */
                        draw = div64_s64(ln, w);
                } else {
                        draw = S64_MIN;
                }

                if (i == 0 || draw > high_draw) {
                        high = i;
                        high_draw = draw;
                }
        }
        return bucket->h.items[high];
}

ランダムに決定した0~1の値の自然対数をとって、アイテムの重みで割った値を比較しています。

- ln(hash)/ w

は指数分布の確率分布を取ります。wは変数です。

X1, X2, … Xnがそれぞれ、w1, w2, … wnの変数の指数分布に従っているとき、 X1, X2, … Xnの最小値がXkである確率は、なんと

wk / (w1 + w2 + … + wn)

になります!!もはや、確率を調整するための係数は必要ありません。また、重みを変更したり、アイテムを追加しても、他の重みに影響はありません。

従来のstraw bucketの欠点を完全に克服しています。もう改良の余地は見当たらなくなってしまいました。

Cephの作者は、やはり天才のようです。

参考

crush: straw is dead, long live straw2 — CEPH Filesystem Development