Redis: HyperLogLog の実装について その2
前回、Redis の HyperLogLog に 対して "A", "B", "C" という 3つの文字列を与えると
registers に 0x51, 0x7c, 0x88, 0x5e, 0xc1, 0x80, 0x42, 0x62, 0x88, 0x4d, 0x5a というバイト配列が格納された。
今回は、sparse 表現の実装をより詳しく見ていくことにする。
ハッシュ関数とレジスタ
そもそも Redis におけるレジスタとは何なのか。
ソースコードのコメントには、HyperLogLog型のキーは 16,384個の 6ビットレジスタで表現されるとある。
従って、キー 1個あたり
6 bit x 16,384 = 98,304 bit = 12,288 Byte = 12 KB
でカーディナリティが表現されることになる。
レジスタ値の求め方
任意のバイト配列から、記録すべきレジスタのインデックスと 6ビットの値を求める手順は以下のとおり。
- 入力に対して 64ビット版の MurmurHash2 アルゴリズムを適用し、
ハッシュ値 (64ビット符号無し整数値) を得る
- MurmurHash とは、衝突困難性と一様性に優れ、MD5 よりも高速なハッシュ関数
- 実際の実装ではエンディアン・ニュートラル (ビッグエンディアンにもリトルエンディアンにも対応可能) に改変されている
- ハッシュ値の下位 14ビットの値をレジスタ・インデックスとして使う
- 0 〜 16383 の値が得られ、何番目の箱にレジスタをセットするかが決まる。
- ハッシュ値の 下位から数えて 15ビット目から上位へ向かってビットを走査し、初めて「1」が登場する位置を調べる(=「0」のビットが何個連続しているかを数え、1を足す)
- ただし、最上位のビットにはあらかじめ「1」をセットしておく
- 1 〜 50 の値が得られ、これがレジスタの値となる
- この値が 33 以上だった場合、sparse 表現ができないので自動的に dense 表現に変換される。
ランレングス圧縮
sparse 表現とは、すなわち上記のレジスタ情報をランレングス圧縮したバイト列である。
それは、Redis 独自の以下3種類のオペコードで構成される。
ZERO
00xxxxxx という 1バイトの表現。
xxxxxx を 6ビットの符号無し整数として解釈し、1 を足す。(1 <= x <= 64 とする)
「x」の個数ぶん、値が「0」のレジスタが連続していることを示す。
XZERO
01xxxxxx yyyyyyyy という 2バイトの表現。
xxxxxxyyyyyyyy を 14ビットの符号無し整数として解釈し、1 を足す。(1 <= x <= 16384 とする)
「x」の個数ぶん、値が「0」のレジスタが連続していることを示す。
VAL
1vvvvvxx という 1バイトの表現。
vvvvv を 5ビットの符号無し整数、xx を 2ビットの符号無し整数として解釈し、それぞれ 1 を足す。
(1 <= v <=32, 1 <= x <= 4 とする)
「x」の個数ぶん、値が「v」のレジスタが連続していることを示す。
読み解いてみる
冒頭の例をランレングス圧縮のオペコードに読み替えてみると、以下のようになる。
- 0x51, 0x7c => 0b01010001, 0b01111100 => XZERO:4477
- 0x88 => 0b10001000 => VAL:3,1
- 0x5e, 0xc1 => 0b01011110, 0b11000001 => XZERO:7874
- 0x80 => 0b10000000 => VAL:1,1
- 0x42, 0x62 => 0b01000010, 0b01100010 => XZERO:611
- 0x88 => 0b10001000 => VAL:3,1
- 0x4d, 0x5a => 0b01001101, 0b01011010 => XZERO:3419
従って、レジスタの状態は index:4477 -> 3、index:12352 -> 1、index:12964 -> 3 がセットされており
他は全てゼロであることがわかった。
レジスタの個数も、4477 + 1 + 7874 + 1 + 611 + 1 + 3419 = 12964 とピッタリ合っている。
実際、入力した 3個の文字列は
- A: index:12352 -> 1
- B: index:12964 -> 3
- C: index:4477 -> 3
に対応している。
0 件のコメント:
コメントを投稿