プロンプトと適用範囲
これはデータエンジニアリングおよびストリーム処理の面接質問です。プラットフォームは数十億件のイベントを取り込み、時間、テナント、リージョン別にクエリを実行し、ダッシュボード用に約1%の相対誤差を許容します。請求、クォータ適用、監査レポートには依然として厳密な値が必要です。誤差バジェット、ウィンドウの種類、遅延許容限界（lateness bound）、集合演算の必要性、および識別子が個人データに該当するかどうかを明確にしてください。
質問バンクはすでにストリーミング、ホットパーティション、バッチ対ストリームアーキテクチャをカバーしています。このプロンプトは、特定のデータベース製品ではなく、マージ可能なカーディナリティスケッチが分散個別カウントのコストをどのように変化させるかに焦点を当てています。
面接官が評価するポイント
- HLLをBloomフィルタやCount-Min Sketchのように扱うのではなく、カーディナリティ、メンバーシップ、頻度を明確に区別しているか。
- ローカルな推計値を合算するのではなく、シャードごとの固定サイズスケッチとレジスタごとの最大値マージを説明しているか。
- 誤差、遅延、リセット、プライバシー、ビジネス上の厳密性をテスト可能な契約に落とし込んでいるか。
不十分な回答は「Redis HLLはサイズが小さいためそれを使用する」とだけ答えます。優れた回答は厳密なベースラインを提示し、近似の失敗モードを挙げ、リプレイ、サンプリング、ドリフト監視を定義します。
回答前の明確化事項
- どの程度の誤差が許容されるか？ ダッシュボードであれば約1%を許容できる場合がありますが、請求やコンプライアンスレポートには厳密なパスまたは校正された照合パスが必要です。
- クエリは固定ウィンドウか、それとも任意の範囲か？ 1時間単位のスケッチは固定バケットに適しています。任意の範囲の場合は、明確な境界と保持期間を持つマージ可能なバケットが必要です。
- イベントはどの程度遅れて到着する可能性があるか？ 遅延限界によって、バケットを再オープンするか、元イベントを保持するか、確定ウォーターマークを受け入れるかが決まります。
- 積集合、差集合、またはメンバー一覧が必要か？ HLLは和集合のカーディナリティに優れています。メンバーシップ、積集合、または削除には、別の構造または厳密な再計算が必要です。
30秒での回答
「私は正確性のベースラインとして厳密なセットを保持しますが、ユニークユーザー数の増加に伴いメモリ、ネットワークシャッフル、クロスシャードマージのコストが増大します。ダッシュボードが約1%の誤差を許容する場合、各シャードは時間、テナント、リージョンをキーとする固定精度のHyperLogLogを保持します。クエリ時にはスケッチ全体でレジスタごとの最大値を取り、1つの推定器を実行します。ローカルの推計値を合算することは決してしません。HLLは近似的な和集合カーディナリティに答えるものであり、メンバーシップ、削除、識別子一覧には対応しません。イベント時間とウォーターマークを使用してバケットをクローズし、有界な遅延を受け入れ、より古い修正は厳密なリプレイに送ります。最後に、サンプリングしたクローズ済みバケットを厳密なカウントと照合し、相対誤差、空バケット、重複、スケッチマージ、プライバシーリスクを監視します。」
ステップごとの詳細な回答
ステップ1：厳密なベースラインを構築する。
各(hour, tenant, region)に対してユーザーIDセットを保存します。これは厳密ですが、シャードが多数のIDを送信するか、グローバルシャッフルを実行する必要があります。ローカルのCOUNT(DISTINCT)値を合算すると、複数のシャードに存在するユーザーが二重カウントされます。
ステップ2：HLLの状態を記述する。
安定したハッシュをレジスタインデックスと先行ゼロのランクに分割します。各入力は、最大ランクを用いて自身のレジスタのみを更新します。推定器はすべてのレジスタからカーディナリティを導出し、小範囲の補正を適用します。精度、ハッシュの挙動、推定器の範囲を指定せずに汎用的な誤差を約束してはなりません。
ステップ3：分散マージを説明する。
1つのディメンションに対するスケッチは、同じレジスタ数、ハッシュ規約、エンコーディングを使用する必要があります。推計値を加算するのではなく、各レジスタの最大値を取ることでマージします。これにより、元のIDをシャッフルすることなく、分単位のスケッチを時間単位の回答にロールアップできます。
for each event(user_id, bucket, tenant, region):
i, rank = hash_and_rank(user_id, precision)
sketch[bucket, tenant, region][i] = max(sketch[...][i], rank)
merged[i] = max(sketch_a[i], sketch_b[i])
estimate = hll_estimator(merged)ステップ4：遅延とウィンドウを処理する。
イベント時間でバケット化し、ウォーターマークを使用してバケットを確定状態にします。最大遅延限界内の更新のみを受け入れ、それ以前のイベントは未加工ログのリプレイまたは厳密な修正テーブルに送ります。HLLは1人のユーザーを削除できないため、イベントを取り消すには影響を受けるバケットを再構築する必要があります。
ステップ5：近似結果とビジネス上の正確性を分離する。
照合ジョブがクローズ済みバケットをサンプリングし、厳密なセットまたはオフラインSQLを用いて正解値を計算します。相対誤差、バイアスの方向、異常のあるディメンションを記録します。請求、クォータ、プライバシー削除用には厳密な台帳を保持し、低コストの観測や推定にはスケッチを使用します。
ステップ6：コストとプライバシーを管理する。
ディメンションの組み合わせ、バケットの保持期間、テナントごとのスケッチを制限し、高カーディナリティのラベルが無制限の状態を作成しないようにします。ハッシュ入力を一貫して正規化し、鍵のローテーションを管理して、スケッチへのアクセスを認可します。集計サイズからグループが判明する可能性があるため、スケッチは匿名化の保証にはなりません。
高品質な回答例
「まず、結果が近似値でよいかを確認します。厳密なセットは請求や監査に適していますが、複数シャードにわたる数十億件のイベントと長いウィンドウでは、メモリとシャッフルのコストが非常に高くなります。約1%の許容誤差を持つダッシュボードの場合、各シャードは時間バケットおよびディメンションごとに同一設定のHLLを保持します。安定したハッシュが1つのレジスタを更新し、クエリは推定器を実行する前にレジスタごとの最大値を取ります。ローカルな推計値を足し合わせるとユーザーが二重カウントされてしまいます。
私はイベント時間バケットをウォーターマークでクローズし、有界な遅延ウィンドウを保持します。HLLは単一要素を削除できないため、そのウィンドウ外の修正は未加工ログのリプレイを経由します。スケッチのマージ可能性を維持するため、メタデータには精度、ハッシュ規約、バケット境界を記録します。スケッチサイズ、マージレイテンシ、重複率、相対誤差を監視し、サンプリングしたバケットを厳密なセットと照合します。請求やコンプライアンス上の削除は厳密なまま維持し、HLLは分析の高速化レイヤーとして位置付けます。」
よくある間違い
- シャードの推計値を合算する → 同じユーザーが複数のシャードに現れる可能性がある → レジスタをマージしてから1回だけ推定する。
- HLLがユーザーが存在したかどうかを判定できると主張する → 統計的サマリーを保存しているだけである → メンバーシップにはセットまたはBloomフィルタを使用し、偽陽性を明記する。
- 遅延または削除されたイベントをスケッチから減算する → レジスタの最大値には可逆的な寄与者が存在しない → バケットを再構築するか、厳密な修正テーブルを使用する。
- 任意の精度やハッシュ形式をマージする → レジスタの意味が異なる → 精度、ハッシュ、エンコーディング、バージョンのメタデータを保存する。
- スケッチをプライバシー保護として扱う → 集約サイズからグループ情報が漏洩する可能性がある → 認可、最小限のディメンション、保持期間、プライバシーレビューを組み合わせる。
フォローアップと回答
フォローアップ1：ビジネス側から任意の37日間の範囲を求められました。どのようにバケット化しますか？
分単位のスケッチはより多くの状態を生成しますが、クエリは連続する分をマージできます。時間単位および日単位のスケッチは、長期間の読み取り量を削減します。マルチレベルのバケットには、重複のない明確な境界が必要です。プランナーは重複しない最も粗い組み合わせを選択し、レベル間の端数をより細かいバケットで埋めます。
フォローアップ2：ユーザー削除を24時間以内に反映する必要があります。HLLを維持できますか？
HLLはユーザーごとの削除を実行できません。消去可能な厳密イベントインデックスまたは暗号化マッピングを保持し、影響を受けるバケットを再構築して、ダッシュボード層で古いバージョンを非表示にします。スケッチは非公式なものとして扱います。規制により削除の証跡が求められる場合は、厳密な削除台帳とリプレイ検証を使用します。
フォローアップ3：マージ後に誤差が1%から8%に跳ね上がりました。最初に何を調査しますか？
スケッチのメタデータ（精度、ハッシュシード、レジスタエンコーディング、バージョン）を比較します。あるシャードがレジスタではなく推計値をシリアライズしていないか、同じ入力を2回マージしていないか、ハッシュ分布に異常がないかを確認します。推定器またはシリアライゼーションの不具合を特定するために、1シャード、2シャード、そしてマージの順で小さなセットを段階的に再現します。