HyperLogLog Implementation in Redis, pt.4

Redis: HyperLogLog の実装について その4

 

その他のトピック。

 

要素の追加

追加する要素のハッシュを求め、インデックスと base-2 rank を求める。
各インデックスごとにより大きい値をレジスタに保存するだけ。

 

データのマージ

$2^{14}$ 個の全てのレジスタを走査し、各位置に対して値の大きいほうを保持する。
非常に高速なマージ処理も HyperLogLog の特長である。

 

dense 表現について

dense 表現では、sparse 表現と異なり、全部のインデックスの値が配列的に保持されている。

Redis では以下のような構造のバイト配列を定義することで、メモリ使用量を圧縮している。
(各レジスタの値は 0〜50 の範囲内であるため、それぞれ 6 ビットで表現可能)

 * +--------+--------+--------+------//
 * |11000000|22221111|33333322|55444444
 * +--------+--------+--------+------//

sparse から dense へ変換が行われるタイミングは以下。

• PFADD
  • 追加する要素の base-2 rank が 33 以上だった場合 (sparse では表現不可)
  • sparse 表現の使用サイズが サーバ変数 server.hll_sparse_max_bytes を超えた場合
    (デフォルトは 3000)

• PFMERGE: マージ実行後は必ず dense 表現になる
• PFDEBUG TODENSE key: デバッグ用のコマンド

 

 

Related Posts

• mog project: HyperLogLog Implementation in Redis, pt.1
• mog project: HyperLogLog Implementation in Redis, pt.2
• mog project: HyperLogLog Implementation in Redis, pt.3

HyperLogLog Implementation in Redis, pt.3

Redis: HyperLogLog の実装について その3

 

前回は sparse 表現のバイナリについて中身をざっと見た。

今回は HyperLogLog の目的である、カーディナリティを求める処理 pfcount についてその実装を確かめてみる。

 

カウントのコア部分の処理は hllCount 関数に記述されている。

 

カウントの求め方

論文によれば、カーディナリティの期待値 $E$ は以下のように求められる。

• レジスタの個数を $m$ とする。Redis の場合 $$m = 2^{14} = 16384$$
• このとき $$E = \frac{\alpha_{m}m^2}{\sum_{j=1}^{m} 2^{-M^{(j)}}}$$
• ここで $$\alpha_{m} = \left(m \int_{0}^{\infty} \left(\text{log}_2 \left(\frac{2+u}{1+u}\right)\right)^m du\right)^{-1}$$
  Redis の場合、これは $\alpha_{m} \approx 0.7213 \cdot \left({1 + \frac{1.079}{m}}\right)^{-1} \approx 0.7213$ で近似される。
• また、$M^{(j)}$ は $j$番目のレジスタの値である。

 

具体的な例

これまで見てきたように、Redis の HyperLogLog 型に "A", "B", "C" という 3つの値を追加すると、レジスタの状態は以下のようになる。

• index:4477 -> 3 (C)
• index:12352 -> 1 (A)
• index:12964 -> 3 (B)
• 上記以外の index -> 0

この例で実際に $E$ を求めてみる。

• $2^0 = 1, \qquad 2^{-1} = 0.5, \qquad 2^{-3} = 0.125$ であるから $$\sum_{j=1}^{m} 2^{-M^{(j)}} = 1 \cdot (m-3) + 0.5 \cdot 1 + 0.125 \cdot 2 = 16381.75$$
• したがって $$E = \frac{\alpha_{m}m^2}{\sum_{j=1}^{m} 2^{-M^{(j)}}} \approx \frac{0.7213 \cdot 16384^2}{16381.75} \approx 11819.40$$

実際のカーディナリティは 3 なので、大きなズレがあるように見える。




期待値の補正

このように、HyperLogLog は小さいカーディナリティに対して大きな誤差が出るという性質がある。
この問題を解決するため、Redis では一旦期待値を算出した後で、以下のルールに従ってその値を補正している。

• i) $E \lt 2.5 \cdot m = 40960$ かつ 値が 0 であるレジスタが存在する場合

  以下の式 (Redis のコメントには「LINEARCOUNTING アルゴリズム」と書かれている) によって期待値を計算し直す。値が 0 であるレジスタの個数を $z$ として $$E := m \cdot \text{log} \left( \frac{m}{z} \right)$$

  上記の具体例では、$z = 16384 - 3 = 16381$ なので $$E := m \cdot \text{log} \left( \frac{m}{z} \right) = 16384 \cdot \text{log} \left( \frac{16384}{16381} \right) \approx 3.0003$$
  正しいカーディナリティ 3 を得ることができた。

• ii) i)に該当せず $E \lt 72000$ の場合
  以下の多項式バイアスを適用して期待値を調整している。これは $m = 2^{14}$ の場合に限り適用可能。 $$ \begin{align} bias &= 5.9119 \cdot 10^{-18}E^4 - 1.4253 \cdot 10^{-12}E^3 + 1.2940 \cdot 10^{-7}E^2-5.2921 \cdot 10^{-3}E + 83.3216 \\ E :&= E - E \cdot \frac{bias}{100} \end{align}$$
• iii) その他の場合は補正なし

こうして得られた値 $E$ を 64ビット非負整数に変換したものが、HyperLogLog型のカウントとして得られる値である。

 

Related Posts

• mog project: HyperLogLog Implementation in Redis, pt.1
• mog project: HyperLogLog Implementation in Redis, pt.2

HyperLogLog Implementation in Redis, pt.2

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

に対応している。

 

 

Related Posts

• mog project: HyperLogLog Implementation in Redis, pt.1

HyperLogLog Implementation in Redis, pt.1

Redis: HyperLogLog の実装について その1

だいぶ古い話だが、Redis 2.8.9 で新しいデータ構造 HyperLogLog が登場した。
その実装コードを読む。

• redis/hyperloglog.c at unstable · antirez/redis

（そして、モック作り に活かしたい）

2種類のデータ構造

Redis では、dense(密) と sparse(疎) の 2種類のデータ構造をシームレスに切り替えることで、最小限に近い空間計算量での高精度カーディナリティ推定を可能としている。

また、これらはいずれも STRING 型とよく似たデータ構造 (つまりバイト配列) をなしており、get コマンドを利用することでその実体を窺い知ることができる。

ヘッダの読み方

まずは実際に動かしてみる。

127.0.0.1:6379> get hll
(nil)
127.0.0.1:6379> pfadd hll A B C
(integer) 1
127.0.0.1:6379> pfcount hll
(integer) 3
127.0.0.1:6379> strlen hll
(integer) 27
127.0.0.1:6379> get hll
"HYLL\x01\x00\x00\x00\x03\x00\x00\x00\x00\x00\x00\x00Q|\x88^\xc1\x80Bb\x88MZ"




get で表示されたデータの先頭 16 bytes がヘッダとして定義されているもの。

struct hllhdr {
    char magic[4];      /* "HYLL" */
    uint8_t encoding;   /* HLL_DENSE or HLL_SPARSE. */
    uint8_t notused[3]; /* Reserved for future use, must be zero. */
    uint8_t card[8];    /* Cached cardinality, little endian. */
    uint8_t registers[]; /* Data bytes. */
};

• magic: 最初の4文字は、データが HyperLogLog であることを示す固定値「HYLL」が入る。
• encoding: 次の1バイトは、データ構造を示すフラグ。
  上記のように「\x01」であれば sparse(疎)、「\0x00」なら dense(密) を表す。
• notused: 将来のために確保されている、未使用の領域が3バイトほど続く。
• card: カーディナリティの値が64bitぶん、リトルエンディアンで保存されている。
  今回の場合は「0x03」「0x00」「0x00」「0x00」「0x00」「0x00」「0x00」「0x00」なので、
  カーディナリティ 3 を表す。

そして、registers の部分が HyperLogLog のデータそのもの。

今回の例では、「Q|\x88^\xc1\x80Bb\x88MZ」の部分 (11 bytes) がそれに該当する。

16進数表記をすれば、順に
「51, 7c, 88, 5e, c1, 80, 42, 62, 88, 4d, 5a」
である。

References

• HyperLogLog - Wikipedia, the free encyclopedia
• 元の論文

• 乱択データ構造の最新事情 －MinHash と HyperLogLog の最近の進歩－
• RedisのHyperLogLogを使ってユニークユーザー数を推定する « Rest Term

How to Detect Stack Overflow with GCC

GCCでスタックオーバーフローを検知する方法

GCC でコンパイルしたC/C++プログラムがスタックオーバーフローを引き起こした時、
何も起こっていないかのようにプログラムが静かに終了することがある。

コンパイル時に「-fstack-check」 オプションを付けておくと、スタックオーバーフローの際に
強制的にプログラムを停止させてくれるので、何らかのメッセージを拾うことができる。

また、マルチスレッド環境ではこのフラグを指定すべきである。

Get the current system time in microseconds/nanoseconds

マイクロ秒/ナノ秒単位の時刻の取得

1. [UNIX/Windows] マイクロ秒の表示 – gettimeofday() – <sys/time.h>

・print_time1.c

#include <stdio.h>
#include <sys/time.h>

int main() {
  struct timeval now;
  struct tm *t;
  gettimeofday(&now, NULL);
  t = localtime(&now.tv_sec);

  printf("%04d/%02d/%02d %02d:%02d:%02d.%06ld\n",
      t->tm_year + 1900, t->tm_mon + 1, t->tm_mday,
      t->tm_hour, t->tm_min, t->tm_sec,
      now.tv_usec);
  return 0;
}

$ ./print_time1

2011/07/18 02:50:40.333827

gettimeofday() は廃止予定らしい。

http://archive.linux.or.jp/JM/html/LDP_man-pages/man2/gettimeofday.2.html
>> POSIX.1-2008 では gettimeofday() は廃止予定とされており、代わりに clock_gettime(2) の使用が推奨されている。

 

2. [UNIX] ナノ秒の表示 – clock_gettime() – <time.h>

・print_time2.c

#include <stdio.h>
#include <time.h>

int main() {
  struct timespec now;
  struct tm *t;
  clock_gettime(CLOCK_REALTIME, &now);
  t = localtime(&now.tv_sec);

  printf("%04d/%02d/%02d %02d:%02d:%02d.%09ld\n",
      t->tm_year + 1900, t->tm_mon + 1, t->tm_mday,
      t->tm_hour, t->tm_min, t->tm_sec,
      now.tv_nsec);
  return 0;
}

$ ./print_time2

2011/07/18 02:50:43.268259848

コンパイルに失敗した場合は、「-lrt」オプションを付け、librt とリンクさせる。

 

3. [Windows] ミリ秒の表示 – GetLocalTime() – <windows.h>

・print_time3.c

#include <stdio.h>
#include <windows.h>

int main() {
  SYSTEMTIME now;
  GetLocalTime(&now);

  printf("%04d/%02d/%02d %02d:%02d:%02d.%03d\n",
      now.wYear, now.wMonth, now.wDay,
      now.wHour, now.wMinute, now.wSecond,
      now.wMilliseconds);
  return 0;
}

>.\print_time3.exe

2011/07/18 03:31:53.722

参考：
http://www.bugbearr.jp/?C%E8%A8%80%E8%AA%9E%2F%E6%97%A5%E6%99%82
http://archive.linux.or.jp/JM/html/LDP_man-pages/man2/clock_gettime.2.html