Tair (Redis® OSS-Compatible):TairBloom

概要

Redis では、ハッシュ、セット、または文字列に格納されたビットセットを使用して同様の機能を実現できます。しかし、これらのメソッドは大量のメモリを消費するか、安定した偽陽性率を維持しながら動的にスケーリングすることができません。TairBloom は、大規模なデータセットで効率的なメンバーシップテストを必要とし、わずかな偽陽性率を許容できるユースケースに最適です。カスタムラッパーやローカル実装なしで、TairBloom API を直接使用できます。

主な特徴

• 低いメモリフットプリント。

• 自動スケーリングをサポート。

• 自動スケーリング中も安定した、カスタマイズ可能な偽陽性率。

ユースケース

ベストプラクティス

void recommendedSystem(userid) {
    while (true) {
        // 候補となる記事 ID を取得します。
        docid = getDocByRandom()
        if (bf.exists(userid, docid)) {
            // 記事はすでに推薦されている可能性が高いため、スキップします。
            continue;
        } else {
            // 記事はまだ推薦されていないため、送信します。
            sendRecommendMsg(docid);
            // 推薦を記録します。
            bf.add(userid, docid);
            break;
        }
    }
}

bool crawlerSystem( ) {
    while (true) {
        // クロールする URL を取得します。
        url = getURLFromQueue()
        if (bf.exists(url_bloom, url)) {
            // URL はすでにクロールされている可能性が高いため、スキップします。
            continue;
        } else {
            // URL のコンテンツをダウンロードします。
            doDownload(url)
            // URL を TairBloom に追加します。
            bf.add(url_bloom, url);
        }
    }
}

仕組み

TairBloom は、スケーラブルブルームフィルターの実装です。自動スケーリングをサポートし、安定した偽陽性率を維持します。スケーラブルブルームフィルターは、ブルームフィルターの最適化版です。以下のセクションでは、ブルームフィルターとスケーラブルブルームフィルターの基本原則について説明します。

• ブルームフィルター

  ブルームフィルターは、1970年に Burton Bloom によって提案された、スペース効率の高い確率的データ構造です。要素がセットのメンバーであるかどうかをテストするために使用されます。

  新しいブルームフィルターは m ビットのビット配列で、すべてのビットは初期状態で 0 に設定されています。また、k 個の異なるハッシュ関数を使用します。これらのハッシュ関数は一様ランダム分布を生成し、k は m より小さい定数です。要素をブルームフィルターに追加すると、k 個のハッシュ関数が要素をビット配列内の k 個の位置にマッピングし、これらの位置のビットが 1 に設定されます。1つのビットは複数の要素で共有できます。次の図は、k が 3 の場合に要素 X1 と X2 がブルームフィルターに挿入される様子を示しています。

  要素をクエリするには、同じ k 個のハッシュ関数を使用して対応する k 個のビット位置を取得します。これらの位置のすべてのビットが 1 であれば、その要素はブルームフィルターに存在すると見なされます。いずれかのビットが 0 であれば、その要素は間違いなく存在しません。次の図は、Y1 と Y2 がブルームフィルターに存在するかどうかを確認する方法を示しています。

  図に示すように、要素 Y2 はブルームフィルターに挿入されていないにもかかわらず、フィルターは Y2 が存在すると報告します。これは誤検知です。これに基づき、ブルームフィルターの特性を次のようにまとめることができます：

  • ビット位置は異なる要素で共有されることがあります。

  • 誤検知が発生する可能性があります。ブルームフィルター内の要素が多いほど、誤検知の確率は高くなります。ただし、偽陰性は発生しません。要素が存在しないと報告された場合、それは間違いなく存在しません。

  • 要素はブルームフィルターに追加できますが、削除はできません。これは、ビット位置が共有される可能性があり、1つの要素のためにビットをクリアすると他の要素に影響を与える可能性があるためです。

• スケーラブルブルームフィルター

  ブルームフィルターに追加される要素が増えるにつれて、偽陽性率は増加します。偽陽性率を安定させるためには、ブルームフィルターのサイズを大きくする必要があります。しかし、標準のブルームフィルターはサイズ変更できません。スケーラブルブルームフィルターは、新しいブルームフィルターを作成し、それらを単一の論理フィルターにスタッキングすることでこの問題に対処します。

  次の図は、スケーラブルブルームフィルター (SBF) の基本モデルを示しています。これには BF0 と BF1 の2つのレイヤーが含まれています。初期状態では、SBF には BF0 レイヤーのみが含まれています。要素 a、b、c が挿入された後、BF0 レイヤーがユーザー定義の偽陽性率を維持できなくなったとします。この時点で、新しいレイヤー (BF1) が作成されます。その後の要素 d、e、f は BF1 レイヤーに挿入されます。同様に、BF1 レイヤーが偽陽性率を満たせなくなると、新しいレイヤー (BF2) が作成され、以下同様に続きます。詳細については、「Scalable Bloom Filter」をご参照ください。

  重要

  TairBloom が自動スケーリングすると、新しいレイヤーの容量は前のレイヤーの2倍になり、メモリ使用量は4倍になります。

  レイヤーが追加されるたびに、クエリが複数のブルームフィルターレイヤーを走査する必要があるため、クエリ時間が増加します。スケーラブルブルームフィルターは常に最新のレイヤーにデータを挿入し、クエリは最新のレイヤーから最初のレイヤー (BF0) に向かって実行されます。その結果、TairBloom の自動スケーリング操作は大きなキーを生成し、パフォーマンスを低下させる可能性があります。パフォーマンスの低下は、要素数が増えるにつれて大きくなります。

  実際には、TairBloom の自動スケーリングをトリガーすることを避け、この機能を安全策として扱うべきです。自動スケーリングイベント後に書き込みが失敗し、長時間のデータエビクションプロセスがトリガーされてインスタンスが無応答になるのを防ぐために、インスタンスに十分なメモリを確保してください。BF.INFO コマンドを使用して、キーが自動スケーリングイベントをトリガーしそうかどうかを確認できます。最新レイヤーの items の数がその capacity に達すると、自動スケーリングイベントが間近に迫っています。

  実際の容量が事前設定された容量を超えると、TairBloom は自動スケーリングして書き込み操作を継続できるようにし、本番環境でのインシデントを防ぎます。TairBloom が自動スケーリング操作を完了した後、パフォーマンスを向上させ、次の自動スケーリングイベントに関連するリスクを低減するために、できるだけ早くキーを再構築してください。

前提条件

注意事項

• このトピックのコマンドは、Tair インスタンス内の TairBloom データを操作します。

• 初期容量と偽陽性率を事前に計画してください。ターゲットキーの予想容量が 100 を大幅に超える場合は、BF.RESERVE コマンドを使用して TairBloom キーを作成してください。BF.ADD コマンドでキーを作成することは避けてください。

  以下に、BF.ADD コマンドと BF.RESERVE コマンドの実行の違いについて説明します。

  • BF.ADD (または BF.MADD)：コマンド実行時にターゲットキーが存在しない場合、Tair はデフォルト容量 100、偽陽性率 (`error_rate`) 0.01 の TairBloom インスタンスを自動的に作成します。必要な容量が 100 を大幅に超える場合、後から容量を拡張して要素を追加することしかできません。TairBloom の内部レイヤー数が増えるにつれて、クエリオペレーションは複数のブルームフィルターを走査する必要があり、パフォーマンスが著しく低下します。

  • BF.RESERVE (または BF.INSERT)：このコマンドを実行する際には、`capacity` (初期容量) を設定する必要があります。このコマンドは、TairBloom キーの最初のレイヤーで容量を初期化します。レイヤー数が少ない TairBloom キーは、より高速なクエリを提供します。

  説明

  例えば、偽陽性率 0.01 で 10,000,000 個の要素を挿入する場合、BF.ADD コマンドで TairBloom キーを作成すると 176 MB のメモリが必要になります。対照的に、BF.RESERVE コマンドでキーを作成すると、わずか 16 MB しか必要ありません。

  次の表は、BF.RESERVE コマンドを使用して、異なる初期容量と偽陽性率で作成されたキーのメモリ使用量を示しています。これらの値は参考用です。

  容量	偽陽性率：0.01	偽陽性率：0.001	偽陽性率：0.0001
  100,000	0.12 MB	0.25 MB	0.25 MB
  1,000,000	2 MB	2 MB	4 MB
  10,000,000	16 MB	32 MB	32 MB
  100,000,000	128 MB	256 MB	256 MB
  1,000,000,000	2 GB	2 GB	4 GB

  非常に大きな容量のキーを作成する場合は、`error_rate` を考慮してください。非常に大きな容量で高精度 (低い `error_rate`) のキーは、インスタンスのメモリ不足により失敗する可能性があります。

• TairBloom では新しい要素を挿入できますが、既存の要素を削除することはできません。その結果、TairBloom キーのメモリ使用量は増加する一方です。TairBloom キーが過度に大きくなり、メモリ不足 (OOM) エラーを引き起こすのを防ぐために、以下の提案を検討してください。

  • ビジネスデータの分割：ビジネスデータを分割・細分化して、単一の TairBloom キーに大量のデータを格納することを避けてください。これにより、キーが大きくなりすぎてクエリパフォーマンスに影響を与えるのを防ぐだけでなく、クエリトラフィックの大部分がキーのある Redis インスタンスに集中し、ホットキーが発生してアクセススキューが生じるのを防ぎます。

    ビジネスデータを分割し、複数の TairBloom キーにデータを分散させてください。クラスターインスタンスを使用している場合は、クラスター内のノードに TairBloom キーを分散させることで、メモリとトラフィックのバランスを取り、分散クラスターの利点を最大限に活用できます。

  • 定期的な再構築：ビジネスで許容される場合は、TairBloom キーを定期的に再構築できます。DEL コマンドを使用して TairBloom キーを削除し、バックエンドデータベースからデータをプルして再構築します。これにより、TairBloom キーのサイズを制御できます。

    また、最初に複数の TairBloom キーを作成し、それらをローテーションさせることで、個々のキーのサイズを制御することもできます。このアプローチは頻繁な再構築を避けることができますが、より多くのメモリを消費します。

コマンドリファレンス

BF.RESERVE

BF.RESERVE BFKEY 0.01 100

OK

BF.ADD

BF.ADD BFKEY item1

(integer) 1

BF.MADD

BF.MADD BFKEY item1 item2 item3

(integer) 1
(integer) 1
(integer) 1

BF.EXISTS

BF.EXISTS BFKEY item1

(integer) 1

BF.MEXISTS

BF.MEXISTS BFKEY item1 item5

(integer) 1
(integer) 0

BF.INSERT

BF.INSERT bfkey1 CAPACITY 10000 ERROR 0.001 ITEMS item1 item2 item3

(integer) 1
(integer) 1
(integer) 1

BF.INFO

BF.INFO bk1

1) "total_items:6,num_blooms:2"
2) "bytes:4 bits:32 hashes:7 hashwidth:64 capacity:3 items:3 error_ratio:0.01"
3) "bytes:16 bits:128 hashes:9 hashwidth:64 capacity:10 items:3 error_ratio:0.0025"