HyperLogLogとBloom FilterによるRedisのメモリ最適化：大規模データのカウントと重複除外 - ITFROMZERO - Share tobe shared! RedisのHyperLogLogとBloom Filterを活用してユニークビジター数のカウントや大規模データの重複除外を行い、従来のSet構造と比べてメモリ消費量を95%以上削減する方法を解説します。

システムのアクセス数が日次2,000万〜3,000万PV規模に達すると、Redisのメモリ（RAM）管理における課題が一気に顕在化します。ユニークユーザー数（UV：Unique Visitors）を計測する際、安易にユーザーIDやIPアドレスをSet型にそのまま格納していないでしょうか。その結果、わずか1週間のキャンペーン運用で数十GBものメモリが枯渇してしまうケースは珍しくありません。

その原因は極めてシンプルです。Setは100%の精度を保証するために各生データ文字列をそのまま保持するからです。しかし、トラフィック分析やスパムURLのフィルタリングといったユースケースでは、約1%の許容誤差と引き換えに数十GBのデータをわずか数MBに圧縮できるほうが遥かに価値があります。このような場面で強力な代替手段となるのが、確率的データ構造であるHyperLogLogとBloom Filterです。

Table of Contents

1. クイックスタート：5分で試す実践ハンズオン

まずはターミナルを開き、redis-cliを使って実際の動作を確認してみましょう。

HyperLogLogの検証（Redisコアに標準搭載）

HyperLogLogは追加モジュールをインストールすることなく、標準のRedis環境ですぐに利用可能です。

# redis-cliに接続
redis-cli

# 当日のアクセスIPを記録
PFADD uv:2026-10-26 "192.168.1.1" "192.168.1.2" "192.168.1.3"
# 戻り値: (integer) 1 (推定カーディナリティに変化があった場合)

# 既存のIPを再度追加
PFADD uv:2026-10-26 "192.168.1.1"
# 戻り値: (integer) 0 (カウント数は増加しない)

# ユニークIPの総数を取得
PFCOUNT uv:2026-10-26
# 戻り値: (integer) 3

Bloom Filterの検証（Redis Stackが必要）

Bloom Filterを利用するにはRedisBloomモジュールが必要です。ローカル環境で最も手軽に試すには、Redis Stackのコンテナを起動します。

docker run -d --name redis-stack -p 6379:6379 redis/redis-stack-server:latest

コンテナ起動後、重複判定の動作を確認してみましょう。

redis-cli

# フィルターの初期化: 許容誤差率1% (0.01)、想定データ数100万件
BF.RESERVE blacklisted_emails 0.01 1000000

# 不正メールアドレスをブラックリストに追加
BF.ADD blacklisted_emails "[email protected]"

# メールアドレスの存在チェック
BF.EXISTS blacklisted_emails "[email protected]"
# 戻り値: (integer) 1 (リストに存在する可能性が極めて高い)

BF.EXISTS blacklisted_emails "[email protected]"
# 戻り値: (integer) 0 (100%確実に存在しない)

2. 内部ではどのように動作しているのか？

Redis HyperLogLog：上限12KBのメモリでカーディナリティを推計

HyperLogLogは、ユニーク要素数のカウント問題（Count-Distinct問題）を解決するアルゴリズムです。最大の強みはその固定サイズにあります。記録するデータ数が1,000件であっても10億件であっても、Redisにおける1つのHyperLogLogキーのメモリ消費量は最大12KBにとどまります。その代わりに、標準誤差は約0.81%生じます。

原理としては、入力値をハッシュ関数によってランダムな64ビット列に変換します。ランダムな2進数列がk個連続する「0」で始まる確率は(1/2)^kとなります。データを16,384個のバケットに分散し、各バケットで観測された連続する「0」の最大長を記録することで、Redisは極めて高精度にユニーク要素の総数を推定します。

以下のPythonスクリプトは、複数日分のデータをマージして集計する例です。

import redis

r = redis.Redis(host='localhost', port=6379, db=0)

# 各日のアクセス数を個別に記録
r.pfadd('uv:day1', 'user_A', 'user_B', 'user_C')
r.pfadd('uv:day2', 'user_B', 'user_C', 'user_D')

# Redisのメモリ上で2つのキーを直接週次キーへマージ
r.pfmerge('uv:week_total', 'uv:day1', 'uv:day2')

total_uv = r.pfcount('uv:week_total')
print(f"週間推定UV数: {total_uv}")  # 結果: 4

Bloom Filter：O(k)の高速性で要素の存在確認を実行

Bloom Filterは、集合所属判定（Set Membership：要素Xがすでに存在するかどうか）の課題を解決する構造です。

このデータ構造は、長さmのビット配列とk個の独立したハッシュ関数で構成されています。要素を追加する際、k個のハッシュ関数を通してk個のインデックスを算出し、該当する位置のビットをすべて「1」にセットします。

判定結果が0の場合：その要素は100%確実に存在しません。対象ビットのうち1つでも「0」があれば、その要素が登録されていない証拠になります。
判定結果が1の場合：その要素はすでに存在する可能性があります。他の要素によるハッシュ衝突により、一定確率で偽陽性（False Positive）が発生します。ただし、偽陰性（False Negative：存在しているのに存在しないと判定すること）は絶対に発生しません。

注意すべき技術的制約として、標準的なBloom Filterは要素の削除をサポートしていません。特定のビットを「0」に戻してしまうと、そのビットを共有している他の多くの要素の判定結果まで狂わせてしまうためです。

3. バックエンドアーキテクチャにおける実践的なユースケース

キャッシュ侵入（Cache Penetration）の防止

よくある攻撃シナリオとして、不正なID（例：product_id = -1 や 99999999）を含んだ大量のリクエストを短時間に送りつける手法があります。これらのIDはキャッシュ上に存在しないため、すべてのリクエストがバックエンドのPostgreSQLを直撃し、コネクションプールが枯渇してデータベースがダウンしてしまいます。

キャッシュ層の手前にBloom Filterを配置することで、この問題を根本から解決できます。

import redis

r = redis.Redis(host='localhost', port=6379, decode_responses=True)

def get_product(product_id: int):
    # 1. Bloom Filterで入り口をガード
    if not r.execute_command('BF.EXISTS', 'bf:products', product_id):
        # システム内にIDが存在しないことが100%確実なため処理を中断
        return None

    # 2. 通常のRedisキャッシュを読み込み
    cache_key = f"product:{product_id}"
    data = r.get(cache_key)
    if data:
        return data

    # 3. 有効なIDが存在する場合のみDBへクエリを実行
    data = query_from_postgres(product_id)
    if data:
        r.setex(cache_key, 3600, data)
    return data

WebクローラーにおけるURLの重複除外

毎日数百万件のURLを巡回するクローラーシステムでは、クロール済みかどうかをデータベースに問い合わせているとすぐにディスクI/Oがボトルネックになります。かといって、1,000万件のURL文字列をそのままメモリ上に保持すれば数GBを消費します。許容誤差1%のBloom Filterを用いれば、ビット配列全体でわずか約11.5MBのメモリしか消費せず、1ミリ秒未満のレイテンシで毎秒50,000 opsの処理能力を容易に発揮できます。

4. 実践運用の知見と注意点

私のチームでも以前、ECサイトのクリックイベントトラッキングにおいて深刻なインシデントを経験したことがあります。当初は無難な設計としてすべてのユーザーIDをRedisのSetに格納していました。しかし、フラッシュセールの開始とともにアクセスが爆発し、わずか4日間でRedisが32GBのメモリを食い尽くしてしまったのです。

プライマリサーバーのメモリ枯渇によりRedis Sentinelが緊急フェイルオーバーを発動。チームはその夜のうちに閲覧数カウントのロジックをHyperLogLogへとリファクタリングしました。その結果、Redisクラスタ全体のメモリ消費量は30GB以上から400MB未満へと劇的に削減され、セール期間を完全に安定稼働させることができました。

この経験から得られた重要な教訓は以下の通りです。

BF.RESERVEで明示的に初期化する：未定義のキーに対して直接BF.ADDを実行してはいけません。未定義の場合、RedisBloomはデフォルトの非常に小さなキャパシティ（通常わずか100要素）でフィルターを自動作成します。データが増加するとサブフィルターが連鎖的に自動生成（stacked filters）され、余分なメモリ消費とクエリ遅延を招きます。
IDリストの一覧が必要な場合はHyperLogLogを使わない：この構造は単一のカウント数を返すためだけに特化しています。登録された元のID一覧を復元・復号する手段はありません。「最近閲覧したユーザー10人を表示」といった要件がある場合は、従来通りSetを使用するかデータベースに保存する必要があります。
偽陽性率（False Positive）のしきい値を慎重に検討する：許容誤差率を1%（0.01）から0.01%（0.0001）に下げるには、ビット配列のサイズを約2倍に拡張する必要があり、リクエストごとのハッシュ計算回数も増加してCPU負荷が高まります。一般的なWebアプリケーションにおいては、1%の誤差が精度とリソース効率の最も優れた落としどころになります。
データの削除が必要な場合はCuckoo Filterを検討する：登録済み要素の削除が必須でありながらメモリ効率も維持したい場合は、Cuckoo Filter（Redis StackのCF.ADDやCF.DELコマンド）への移行を検討してください。