Tair (Redis® OSS-Compatible):Bloom

概要

ハッシュ、セット、文字列などの Redis データ構造でビットマップを使用して、TairBloom と同様の機能を実装できます。ただし、これらのデータ構造は、大量のメモリを消費したり、動的スケーリング中に安定した誤検知率を維持できない場合があります。このため、TairBloom は、一定の誤検知率を許容しながら、大規模なデータセットのメンバーシップチェックに最適です。 TairBloom の組み込み Bloom フィルターは、さらにカプセル化したり、オンプレミスデバイスに Bloom フィルターを追加で作成したりする必要なく使用できます。

特徴

• 低メモリ使用量。

• 動的スケーリング。

• スケーリング中も安定したカスタム誤検知率。

一般的なシナリオ

ベストプラクティス

void recommendedSystem(userid) {
    while (true) {
        // ランダムな記事 ID または目的の記事 ID を取得します。
        docid = getDocByRandom()
        if (bf.exists(userid, docid)) {
            // 記事がユーザーに推奨されている可能性がある場合は、次の記事が推奨されます。
            continue;
        } else {
            // 記事がユーザーに推奨されていない場合は、記事が推奨されます。
            sendRecommendMsg(docid);
            // 記事が推奨されている場合は、記事 ID が Bloom フィルターに記録されます。
            bf.add(userid, docid);
            break;
        }
    }
}

bool crawlerSystem( ) {
    while (true) {
        // クロールする URL を取得します。
        url = getURLFromQueue()
        if (bf.exists(url_bloom, url)) {
            // URL が既にクロールされている可能性がある場合は、URL はスキップされます。
            continue;
        } else {
            // この URL をクロールします。
            doDownload(url)
            // この URL を Bloom フィルターに追加します。
            bf.add(url_bloom, url);
        }
    }
}

仕組み

TairBloom は、SBF の実装です。安定した誤検知率を維持しながら、動的スケーラビリティを特長としています。SBF は最適化された Bloom フィルターです。次のセクションでは、Bloom フィルターと SBF の基本原則について説明します。

• Bloom フィルター

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

  新しい Bloom フィルターは、すべて 0 に設定された m ビットのビット配列です。Bloom フィルターには、均一なランダム分布を生成するための一連の k 個の異なるハッシュ関数も含まれています。k は m より小さい定数です。Bloom フィルターに要素を追加すると、k 個のハッシュ関数はこれらの要素をビット配列内の k ビットにマッピングし、k ビットを値 1 に設定します。この場合、ビットは複数のデータで共有できます。次の図は、3 つのハッシュ関数を含む Bloom フィルターに X1 と X2 を挿入する方法を示しています。

  

  Bloom フィルターで要素をクエリする場合、k 個のハッシュ関数を使用して k ビットを取得できます。k ビットのすべてが値 1 である場合、その要素は Bloom フィルターに存在します。それ以外の場合、要素は存在しません。次の図は、Bloom フィルターで Y1 と Y2 をクエリする方法を示しています。

  

  前の図は、Y2 が Bloom フィルターに挿入されたことがないにもかかわらず、Y2 が Bloom フィルターに存在すると判断されていることを示しています。このシナリオは、Bloom フィルターに誤検知率があることを示しています。上記の分析は、Bloom フィルターに次の特徴があることを示しています。

  • ビットは複数のデータで共有できます。

  • Bloom フィルターには誤検知率があり、その率は Bloom フィルター内の要素の数が増えるにつれて高くなります。ただし、Bloom フィルターには偽陰性率はありません。要素が Bloom フィルターに存在する場合、その要素は常に存在すると判断されます。

  • 要素は Bloom フィルターに追加できますが、Bloom フィルターから削除することはできません。その理由は、ビットが共有される可能性があるためです。Bloom フィルターから要素を削除すると、Bloom フィルター内の他の要素に影響します。

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

  要素の数が増加すると、誤検知率も増加します。安定した誤検知率を維持するには、それに応じて Bloom フィルターのサイズを増やす必要があります。ただし、構造上の制限により、サイズを増やすことはできません。SBF は、この問題に対応するために登場しました。SBF は、複数の Bloom フィルターを 1 つに組み合わせた新しいタイプの Bloom フィルターです。

  次の図は、SBF の基本モデルを示しています。この SBF には、BF0 と BF1 の 2 つのレイヤーがあります。最初は、SBF には BF0 レイヤーのみが含まれています。この SBF に要素 a、b、c を挿入し、BF0 レイヤーが指定された誤検知率を維持するのに十分な大きさでない場合、SBF サイズを増やすために BF1 レイヤーが作成されます。次に、要素 d、e、f が BF1 レイヤーに挿入されます。BF1 レイヤーも指定された誤検知率を維持できない場合は、BF2 という名前の新しいレイヤーが作成されます。詳細については、「スケーラブル Bloom フィルター」をご参照ください。

  
  重要

  TairBloom の動的スケーリング中、新しいレイヤーの容量は前のレイヤーの 2 倍になり、占有されるメモリ空間は前のレイヤーの 4 倍になります。

  レイヤーが追加されるたびに、クエリ中に複数の Bloom フィルターをトラバースする必要がある場合があります。SBF は最後のレイヤーにのみデータを挿入し、最後のレイヤーから BF0 レイヤーまでデータをクエリします。したがって、TairBloom のスケールアップにより、大きなキーが作成される可能性があり、パフォーマンスが低下する可能性があり、その低下の程度は要素の数が増えるにつれて大きくなります。

  実際に使用する場合、TairBloom のスケールアップは安全対策としてのみ考慮し、TairBloom を頻繁にスケールアップしないことをお勧めします。TairBloom のスケールアップ後に書き込みエラーが発生しないように、インスタンスに十分なメモリが予約されていることを確認してください。書き込みエラーが発生すると、データエビクション操作が長くなり、リクエスト処理が妨げられる可能性があります。

  BF.INFO コマンドを実行して、キーがスケールアップをトリガーしようとしているかどうかを確認できます。最新のレイヤーのアイテム数が容量と等しい場合、スケールアップが差し迫っていることを示します。

  実際の容量がプリセット制限を超える場合は、TairBloom をスケールアップして、ビジネスの書き込み操作を TairBloom で実行できるようにし、ライブインシデントを防ぐことができます。TairBloom をスケールアップした後、パフォーマンスを向上させ、将来のスケールアップに伴うリスクを軽減するために、速やかに再構築することをお勧めします。

前提条件

注意事項

• 管理する TairBloom データは、Tair インスタンスに保存されます。

• 要件を満たす初期容量と誤検知率を事前に計算する必要があります。100 要素をはるかに超える容量を持つ TairBloom キーを作成するには、BF.ADD コマンドではなく、BF.RESERVE コマンドを実行します。

  次のセクションでは、BF.ADD コマンドと BF.RESERVE コマンドの違いについて説明します。

  • BF.ADD（BF.MADD とも呼ばれます）：このコマンドの実行時に TairBloom キーが存在しない場合、キーは自動的に作成されます。キーのデフォルト容量は 100 で、キーのデフォルト誤検知率は 0.01 です。100 をはるかに超えるキー容量が必要な場合は、より多くの要素をサポートするようにキーをスケールアップすることしかできません。

  • BF.RESERVE（BF.INSERT とも呼ばれます）：このコマンドの実行時に初期容量が指定されます。このコマンドは、キーの最初のレイヤーで初期容量を指定します。キーに含まれる Bloom フィルターレイヤーの数が少ないほど、キーのクエリ速度は速くなります。

  説明

  たとえば、10,000,000 個の要素をキーに挿入し、0.01 の誤検知率を許容するとします。BF.ADD コマンドを使用すると、作成されたキーのサイズは 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

  超高容量キーを作成する場合、エラー率の精度に注意する必要があります。超高容量で超高精度のキーは、インスタンスのメモリ不足により作成に失敗する可能性があります。

• キーのサイズは、要素をキーに追加することしかできず、キーから削除できないため、小さくすることはできません。メモリ不足 (OOM) エラーなどの容量の問題を防ぐために、次のソリューションを実装することをお勧めします。

  • ビジネスデータを分割する。ビジネスデータを分割して、クエリのパフォーマンスに影響を与える大きなキーを防ぐことができます。大きなキーが存在する場合、ほとんどのリクエストはこれらのキーを含むインスタンスに対して行われます。これにより、ホットキー、さらにはリクエストの偏りが発生する可能性があります。

    分割されたデータを複数のキーに分散できます。ビジネスデータが Tair クラスターインスタンスに保存されている場合は、分割されたデータをインスタンス内の複数のノードに分散して、大きなキーとホットキーが発生しないようにすることができます。

  • キーを定期的に再構築する。可能であれば、DEL コマンドを実行してキーからデータを削除し、バックエンドデータベースからキーにデータを挿入してキーサイズを管理できます。

    複数のキーを作成して交互に使用することもできます。こうすることで、単一キーのサイズを適切に保つことができます。このソリューションの利点は、キーを一度だけ作成すればよいことです。ただし、複数のキーを作成する必要があり、メモリがいくらか無駄になる可能性があります。

サポートされているコマンド

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"