【テクニカル・上級編】 HyperLogLogコマンド群 – Redis

HyperLogLog：メモリの限界を突破する「確率的」という名の魔術

エンジニアが「ユニークユーザー数を数えろ」と命じられたとき、凡庸な者は迷わず `SET` や `HASH` を使い、数千万のキーをメモリに流し込んでシステムを破綻させる。

しかし、真のアーキテクトは知っている。データ量が指数関数的に増大するシステムにおいて、厳密な整合性を追求することが最大の悪手であることを。Redisの `HyperLogLog` は、メモリという有限の資源を極限まで削り出し、わずか12KBの固定領域で数億のカーディナリティを推定するための、まさに「計算機科学の暴力」とも呼べる実装だ。

今日は、ドキュメントの表面をなぞるような話はしない。HyperLogLogがメモリ上でどう振る舞い、どのような代償を払ってその「魔法」を実現しているのか、その深淵に迫る。

—

1. 12KBの呪文：内部構造の真実

HyperLogLogは、確率的データ構造である。具体的には、Flajolet-Martinアルゴリズムの改良版をベースにしている。

RedisにおけるHLLは、最大16,384（$2^{14}$）個の「バケット（レジスタ）」で構成される。各バケットは6ビットを消費する。
$16,384 \times 6 \text{bit} = 98,304 \text{bit} = 12,288 \text{byte} \approx 12 \text{KB}$。

これが、システムがどれほど肥大化しようとも、HLLが決して超えることのない「物理的障壁」だ。

内部エンコーディングの変遷

Redisは賢い。データが少ない段階から12KBを確保するのは無駄だ。

Sparse Encoding: 初期段階では、HLLはスパース（疎）な状態で保持される。ゼロが連続する箇所をランダムアクセス可能な形式で圧縮し、メモリ消費を劇的に抑える。
Dense Encoding: データ量が増え、閾値を超えると、Redisは即座にメモリ上のビット配列をフル展開する。ここがスイッチング・ポイントだ。この切り替え処理は、Redisの単一スレッド内でシームレスに、かつ高速に行われる。

2. なぜ「確率的」なのか：リード・ソロモンを超えた先

`PFADD` を実行すると、内部では以下のプロセスが走る。

1. 入力値を 64bit ハッシュ関数（MurmurHash64A）に通す。
2. 下位14ビットを使い、16,384個のバケットのインデックスを特定する。
3. 残りのビットの先頭から、連続するゼロの数をカウントする（$w$とする）。
4. バケット内に既に存在する値より $w$ が大きければ更新する。

この「連続するゼロの数」という指標が、実は期待値としてカーディナリティに直結している。だが、ここには0.81%の標準誤差という代償が伴う。

100万件のユニークIDを投入した後の精度確認
PFADD users:20231027 user_1 user_2 … user_1000000
PFCOUNT users:20231027
出力結果: 998432 (真値との誤差はわずか0.16%)

この誤差を許容できるか？否か？それがアーキテクトの分水嶺だ。ユーザーの正確なIDリストが必要なら `SET` や `Bloom Filter` を使うべきだが、リアルタイムのダッシュボードや、数千万規模のアクセスの「規模感」を知るだけであれば、これ以上の効率はない。

3. PFMERGE：分散アーキテクチャの要

大規模な分散システムにおいて、`PFMERGE` は強力な武器となる。複数のHLLキーをマージする際、Redisはバケットごとの最大値を比較するだけだ。

$$ \text{HLL}_{merged}[i] = \max(\text{HLL}_A[i], \text{HLL}_B[i]) $$

この処理は $O(N)$（$N=16,384$）で完了する。数百万のデータポイントをマージするのに、ミリ秒単位の時間を要することはない。この「非可逆的だが極めて高速なマージ」こそが、地理的に分散したサーバーからの集計を現実のものにする。

4. 運用上の極限知見

最後に、現場で戦う諸君へ送る運用上の鉄則を記す。

ハッシュの衝突を恐れるな: MurmurHash64Aは非常に強力だ。しかし、HLLの精度が足りないと感じた時、それはアルゴリズムの限界ではなく、データ自体の偏り（ユニーク数が極端に少ない場合の初期誤差）である場合が多い。
PFCOUNTは計算コストが高い: `PFCOUNT` は単なる読み出しではない。マージや再計算が必要な場合、内部キャッシュが効かないケースがある。頻繁に呼び出すなら、結果をアプリケーション層で数分間キャッシュすることを推奨する。
12KBは固定である: メモリが逼迫した際、`Redis` の `maxmemory-policy` によってHLLが追い出されると、推定値はゼロになる。キーを設計する際は、生存期間（TTL）を適切に設定し、不要なHLLを速やかにパージせよ。

結び

HyperLogLogは、現代のビッグデータ基盤における「妥協の美学」だ。完全な正確性を捨て、計算資源を最適化することで、本来到達できなかったスケールへ我々を導く。

君たちが設計するシステムにおいて、何を正確に数え、何を確率に委ねるか。その境界線を見極めることこそが、エンジニアとしての品格だ。

Redisのソースコードを読み、ビット演算の深淵を覗け。そこには、まだ誰も到達していない最適化の景色が広がっているはずだ。