1. 課題
ログシステムは毎日数十億件のユーザー識別子を受信し、その日のユニークユーザー数をリアルタイムで推定する必要があります。メモリ予算はわずか数KBであり、わずかな誤差は許容されます。ストリーミングアルゴリズムを設計し、その誤差、シャードのマージ方法、および厳密な重複排除を代替できない場面について説明してください。
2. 制約と明確化事項
- 入力は継続的な識別子ストリームです。1パスかつ固定メモリを使用します。
- クエリは、ある時間枠における近似カーディナリティ（異なり数）を求めます。
- ハッシュは一様分布しているとし、すべてのシャードが同じハッシュアルゴリズム、レジスタ数、およびエンコーディングを使用すると仮定します。
- 削除は不要です。スライディングウィンドウ、有効期限、強い整合性を持つ厳密な値には、追加の構造が必要です。
3. コアとなる考え方
HyperLogLog（HLL）は、ハッシュをレジスタのインデックスと残りのビットに分割します。m = 2^p 個のレジスタがある場合、最初の p ビットでレジスタを選択し、残りのビットにおいて先行するゼロの数に1を加えたものが rho となります。各レジスタは、自身が観測した最大の rho のみを保持します。
直感的には、レジスタ内で先行するゼロが非常に長く連続していることは、サンプル空間により多くの異なる要素が出現した証拠となります。カーディナリティは調和平均を用いて推定します：
E = alpha_m * m^2 / sum(2^(-M[j]))
ここで M[j] はレジスタ j であり、alpha_m はレジスタ数に基づいた補正定数です。本番の実装では、小さなカーディナリティに対するLinear Counting補正や、ハッシュ空間の限界付近に対する大規模範囲の補正も使用されます。
4. 参照実装
以下の疑似コードは、更新、推定、およびマージを示しています。実際の実装では、固定幅整数、明示的なハッシュ関数、および rho の境界を使用する必要があります。
init(p):
m = 1 << p
M = array(m, fill=0)
add(x):
h = hash64(x)
j = high_bits(h, p)
w = remaining_bits(h, p)
r = leading_zero_count(w) + 1
M[j] = max(M[j], r)
estimate():
z = sum over j of 2^(-M[j])
e = alpha(m) * m * m / z
if e <= small_range_threshold(m) and zero_registers(M) != 0:
e = m * log(m / zero_registers(M))
return large_range_correction_if_needed(e)
merge(other):
require same p, hash function, and register encoding
for j in 0..m-1:
M[j] = max(M[j], other.M[j])5. 計算量と正当性
各要素に必要な処理はハッシュ1回とレジスタ更新1回であるため、時間計算量は O(1) です。空間計算量はストリームの長さとは無関係に O(m) となります。標準的なHLLの相対標準誤差は約 1.04 / sqrt(m) です。m = 16,384 の場合、これは約 0.81% になります。これは確率的な推定誤差であり、すべてのクエリが固定された区間に収まるという保証ではありません。
更新処理は最大値を取るため、同じ要素を繰り返し追加しても状態が変化し続けることはなく、冪等性が得られます。ハッシュ関数、p、およびエンコーディングが同一であれば、レジスタごとの最大値を取ることでシャードをマージできます。そうでない場合、統計的分布の互換性が失われます。
6. フォローアップと落とし穴
- HLLは推定値を返します。プロダクトがユーザーごとの厳密なリスト、監査証跡、または課金数量を必要とする場合、厳密なセットの代替にはなりません。
- レジスタのクリアは、新しいウィンドウのみを表します。スライディングウィンドウには、タイムバケット、複数のHLL、または削除可能なバリアントに加え、境界やストレージの処理が必要です。
- ハッシュの衝突と入力の偏りは推定値に影響します。安定した64ビット以上のハッシュを選択し、サービスの境界を越えて標準化してください。
- 生の調和推定器は、小さなカーディナリティに対してバイアスが生じます。Linear Countingはゼロのレジスタ数を使用してそのバイアスを軽減します。
7. 発展資料
- RedisのPFCOUNTおよびHyperLogLogデータ型のドキュメント。
- Snowflakeの近似カーディナリティに関するドキュメント。
- PrestoにおけるHyperLogLogに関するMeta Engineeringの概要。
8. 面接の評価ポイント
状態を説明できるか
候補者は、m = 2^p 個のレジスタ、インデックス、rho の由来、および各レジスタが最大値のみを保持する理由を説明できる必要があります。
誤差と補正を導出できるか
1.04 / sqrt(m) のオーダーを示し、小規模範囲のLinear Countingと大規模範囲の補正を説明し、確率的誤差と厳密な保証を区別できる必要があります。
分散マージを扱えるか
マージがレジスタごとの最大値を取ること、およびすべてのシャードでハッシュ関数、精度、エンコーディングを共有しなければならないことを述べる必要があります。
プロダクトの境界を識別できるか
近似分析と、厳密なリスト、スライディングウィンドウ、削除、課金とを区別し、それらの要件において追加の設計が必要となる理由を説明できる必要があります。