mog project: 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つの値を追加すると、レジスタの状態は以下のようになる。

この例で実際に $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型のカウントとして得られる値である。

mog project