Tair (Redis® OSS-Compatible):ブルーム

概要

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

特徴

• メモリの最小消費量。

• 動的スケーリング。

• スケーリング中の安定したカスタム偽陽性率。

典型的なシナリオ

ベストプラクティス

void recommendedSystem(userid) {
    while (true) {
        // Obtain a random article ID or a desired article ID. 
        docid = getDocByRandom()
        if (bf.exists(userid, docid)) {
            // If the article may have been recommended to a user, the next article is recommended. 
            continue;
        } else {
            // If the article has not been recommended to the user, the article is recommended. 
            sendRecommendMsg(docid);
            // If the article has been recommended, the article ID is recorded in a Bloom filter. 
            bf.add(userid, docid);
            break;
        }
    }
}

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

制御ポリシー機能の動作

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

• ブルームフィルター

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

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

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

  前の図は、Y2がブルームフィルタに挿入されなかったが、Y2がブルームフィルタに存在すると判定されることを示している。 このシナリオは、ブルームフィルタが偽陽性率を有することを示す。 上記の分析では、Bloomフィルターには次の機能があります。

  • ビットは、複数のデータによって共有することができる。

  • ブルームフィルタは偽陽性率を有し、この率は、ブルームフィルタ内の要素の数が増加するにつれて高くなる。 ただし、ブルームフィルターには偽陰性率はありません。 ブルームフィルタに要素が存在する場合、その要素は常に存在すると判定される。

  • 要素はブルームフィルタに追加できますが、ブルームフィルタから削除することはできません。 その理由は、ビットを共有できるからである。 ブルームフィルターから要素を削除すると、ブルームフィルター内の他の要素が影響を受けます。

• SBF

  要素の数が増加すると、偽陽性率も増加する。 安定した偽陽性率を維持したい場合は、それに応じてブルームフィルタのサイズを大きくする必要があります。 しかし、構造上の制限によりサイズを大きくすることはできない。 この問題に対応してSBFが登場しました。 SBFは、複数のブルームフィルタを1つにまとめた新しいタイプのブルームフィルタです。

  SBFの基本モデルを次の図に示します。 このSBFは、BF0およびBF1の2つの層を有する。 まず、SBFはBF0層のみを含む。 要素a、b、およびcをこのSBFに挿入し、BF0レイヤーが指定された偽陽性率を維持するのに十分な大きさでない場合、BF1レイヤーはSBFサイズを大きくするように作成されます。 次に、要素d、e、fをBF1層に挿入する。 BF1レイヤーも指定された正のレートを維持できない場合、BF2という名前の新しいレイヤーが作成されます。

  SBFは、最後の層にのみデータを挿入し、最後の層からBF0層にデータを照会する。 詳細については、「スケーラブルなブルームフィルター」をご参照ください。

前提条件

注意事項

• 管理する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とも呼ばれます): このコマンドの実行時に初期容量が指定されます。 このコマンドは、鍵の第1層における初期容量を指定する。 キーに含まれるブルームフィルターレイヤーの数が少ない場合、キーのクエリ速度は速くなります。

  説明

  たとえば、10,000,000の要素をキーに挿入し、誤検出率の0.01を許可するとします。 作成されるキーは、BF.ADDコマンドを使用する場合は176 MB、BF.RESERVEコマンドを使用する場合は16 MBです。

  キーはスケールアップできますが、安全対策としてのみキーのスケールアップを検討し、キーを頻繁にスケールアップしないことをお勧めします。 キーの実際の容量がプロビジョニングされたキーの容量を超える場合は、キーをスケールアップして、キーに対して書き込み操作を実行できるようにし、ライブ事故を防ぐことができます。

  次の表は、BF.RESERVEコマンドによってサポートされるさまざまなキーサイズと、それらの一致した初期容量と偽陽性率を示しています。

  容量 (要素数)	偽陽性: 0.01	偽陽性: 0.001	false positive: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コマンドを実行してキーからデータを削除し、バックエンドデータベースのデータをキーに挿入してキーのサイズを管理できます。

    複数のキーを作成して同じ意味で使用することもできます。 このようにして、単一のキーのサイズが適切に保たれる。 このソリューションの利点は、キーを1回だけ作成する必要があることです。 ただし、複数のキーを作成する必要があり、メモリが無駄になる場合があります。

サポートされるコマンド

BF. 予約

BF.RESERVE BFKEY 0.01 100

OK

BF.ADD

BF.ADD BFKEY item1

(integer) 1

BF. マッド

BF.MADD BFKEY itm1 item2 item3

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

BF. 出口

BF.EXISTS BFKEY item1

(integer) 1

BF. メキシコ人

BF.MEXISTS BFKEY item1 item5

(integer) 1
(integer) 0

BF. インサート

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"