Redis(五)——ブロンフィルター
9441 ワード
前節では、HyperLogLogデータ構造を使用して評価することを学びました.これは非常に価値があり、多くの精度の低い統計的ニーズを解決することができます.
しかし、ある値がHyperLogLog構造の中にあるかどうかを知りたい場合は、pfaddとpfcountメソッドしか提供されず、pfcontainsというメソッドは提供されていません.
例えば、ニュースクライアントを使ってニュースを見ると、新しいコンテンツを絶えず推薦してくれます.推薦するたびに、見たことのあるコンテンツを削除しなければなりません.問題が来て、ニュースクライアントの推薦システムはどのようにプッシュを実現しますか?
サーバは、ユーザーが見たすべての履歴を記録し、システムがニュースを推薦すると、各ユーザーの履歴からフィルタリングし、既存のレコードをフィルタリングします.問題は、ユーザーの量が多く、ユーザー一人一人が見たニュースが多い場合、このような方法では、システムの再稼働を性能に追随させることをお勧めしますか?
実際には、履歴がリレーショナル・データベースに格納されている場合、重さを落とすには頻繁にデータベースをexistsクエリする必要があり、システムの同時量が高い場合、データベースは圧力を担ぐことができません.
キャッシュを思い出すかもしれませんが、こんなに多くの履歴をすべてキャッシュすると、どれだけのストレージスペースが無駄になりますか?そして、このストレージスペースは時間とともに線形に増加しています.あなたは1ヶ月も耐えられます.何年も耐えられますか.しかし、キャッシュしないと性能が追いつかないので、どうすればいいですか?
この時、ブロンフィルタ(Bloom Filter)が登場し、このような重い問題を解決するために使われた.重さを落とすと同時に、空間的に90%以上節約できますが、少し不正確なだけで、一定の誤審確率があります.
ブロンフィルターは何ですか?
ブロンフィルタは、あまり正確ではないset構造と理解でき、containsメソッドを使用してオブジェクトが存在するかどうかを判断すると、誤審する可能性があります.しかし、ブロンフィルタも特に不正確ではなく、パラメータの設定が合理であれば、その精度は相対的に十分に正確に制御でき、小さな誤判確率しかありません.
ブロンフィルタが値が存在すると言った場合、この値は存在しない可能性があります.存在しないと言ったら、存在しないに違いない.例えば、あなたを知らないと言ったら、きっと知らないに違いない.あなたに会ったことがあると言ったとき、全然会ったことがないかもしれませんが、あなたの顔は知っている人の中のある顔に似ている(いくつかの熟した顔の係数の組み合わせ)ので、前に会ったことがあると誤審しました.
上の使用シーンでは、ブロンフィルタはすでに見た内容を正確にフィルタリングすることができ、見たことのない新しい内容もごく一部(誤審)をフィルタリングすることができますが、ほとんどの新しい内容は正確に識別することができます.これにより,ユーザに推奨されるコンテンツが重複しないことを完全に保証できる.
Redisのブロンフィルタ
Redisが公式に提供したブロンフィルターは、Redis 4.0がプラグイン機能を提供してから正式に登場した.ブロンフィルタは、プラグインとしてRedis Serverにロードされ、Redisに強力なブロンデリバリー機能を提供します.
次はRedis 4.0のブロンフィルターを体験してみましょう.煩雑な取り付けを省くためにDockerを直接使いましょう.
上の3つの命令の実行に問題がなければ、ブロンフィルタを体験することができます.
ブロンフィルター基本使用
ブロンフィルタには2つの基本命令があり、bf.add追加要素、bf.existsクエリー要素が存在するかどうか、その使い方とsetセットのsaddとsismemberの差は多くありません.注意bf.addは一度に1つの要素しか追加できません.一度に複数を追加するには、bf.maddコマンドが必要です.同様に、複数の要素が存在するかどうかを一度にクエリする必要がある場合は、bf.mexistsコマンドを使用する必要があります.
私たちが上で使用したブロンフィルタは、デフォルトのパラメータのブロンフィルタにすぎず、私たちが初めてaddしたときに自動的に作成されます.Redisは、addの前にbf.reserveコマンドを使用して明示的に作成する必要があるカスタムパラメータのブロンフィルタも提供しています.対応するkeyがすでに存在する場合、bf.reserveはエラーを報告します.bf.reserveにはkey,error_の3つのパラメータがありますrateとinitial_size.エラー率が低いほど、必要なスペースが大きくなります.initial_sizeパラメータは、予想される要素の数を表し、実際の数がこの数値を超えると誤判率が上昇します.
そのため、誤審率の上昇を招くことを避けるために、大きな数値を事前に設定する必要があります.bf.reserveを使用しない場合、デフォルトのerror_rateは0.01で、デフォルトのinitial_sizeは100です.
注意事項
ブロンフィルターのinitial_size推定が大きすぎると、ストレージスペースが浪費され、推定が小さすぎると、精度に影響し、ユーザーは使用する前にできるだけ要素の数を正確に推定しなければならない.また、実際の要素が予想外に推定値を高くしないように、一定の冗長空間を加える必要がある.
ブロンフィルターのerror_rateが小さいほど、必要なストレージスペースが大きくなり、正確すぎる必要がない場合、error_rateの設定は少し大きくても上品ではありません.例えば、ニュースを重んじると、誤審率が高いのは、一部の文章が適切な人に見られないだけで、文章の全体的な読書量がこのような誤審率で大きな変化をもたらすことはありません.
ブロンフィルタの原理
ブロンフィルタの使用を学んだので、以下に原理を説明する必要があります.そうしないと、読者はドラムに覆われ続けます.各ブロンフィルタがRedisに対応するデータ構造の中には、大きなビット数グループといくつかの異なる偏りのないhash関数があります.無偏とは元素のhash値を比較的均一に計算できることである.
ブロンフィルタにkeyを追加すると、複数のhash関数を使用してkeyをhashして整数インデックス値を算出し、ビット配列長をモデリングして位置を算出し、各hash関数は異なる位置を算出します.さらにビット数グループのこれらの位置を1にするとadd操作が完了します.
ブロンフィルタにkeyが存在するかどうかを尋ねるとaddと同様にhashのいくつかの位置も算出され、ビット配列のいくつかの位置が1であるかどうかを見て、1つのビットが0であれば、ブロンフィルタにこのkeyが存在しないことを示します.いずれも1であれば、このkeyが必ず存在するとは限らないが、これらのビットが1に設定されているのは、他のkeyの存在による可能性があるため、極めて存在する可能性が高い.このビット数グループがまばらであれば,正しいと判断する確率が大きく,このビット数グループが混雑していれば,正しいと判断する確率が低下する.具体的な確率計算の公式は比較的に複雑で、興味を持って読むことができて拡張して読むことができて、とても頭を焼いて、読者に詳しく見ることを提案しません.
実際の要素を初期化サイズよりはるかに大きくしないでください.実際の要素が初期化サイズを超え始めた場合、ブロンフィルタを再構築し、sizeより大きなフィルタを再割り当てし、すべての履歴要素を一括addします(これは、他のメモリにすべての履歴要素を記録する必要があります).error_rateは数が超過したために急激に増加することはなく,フィルタの再構築に比較的ゆとりのある時間を提供した.
ブロンフィルタの他の応用
爬虫類システムでは、URLを重くする必要があります.すでに登ったページは登らなくてもいいです.しかし、URLが多すぎて、数千万何億もあります.これらのURLアドレスを1つの集合で詰めると、スペースがもったいないです.この場合、ブロンフィルタの使用を考えることができます.再ストレージの消費量を大幅に削減できますが、爬虫類システムが少量のページを逃すこともあります.
ベロンフィルタはNoSQLデータベースの分野で非常に広く使用されており、私たちが普段使っているHBAse、Cassandra、さらにLevelDB、RocksDBの内部にはベロンフィルタ構造があり、ベロンフィルタはデータベースのIO要求数を著しく低減することができます.ユーザーがrowをクエリーする場合は、メモリ内のブロンフィルタで存在しないrowリクエストを大量にフィルタリングしてから、ディスクにクエリーすることができます.
メールボックスシステムの迷惑メールフィルタ機能も一般的にブロンフィルタが使われていますが、このフィルタを使っているので、普段も正常なメールが迷惑メールディレクトリに入れられていることに遭遇します.これは誤審によるもので、確率が低いです.
しかし、ある値がHyperLogLog構造の中にあるかどうかを知りたい場合は、pfaddとpfcountメソッドしか提供されず、pfcontainsというメソッドは提供されていません.
例えば、ニュースクライアントを使ってニュースを見ると、新しいコンテンツを絶えず推薦してくれます.推薦するたびに、見たことのあるコンテンツを削除しなければなりません.問題が来て、ニュースクライアントの推薦システムはどのようにプッシュを実現しますか?
サーバは、ユーザーが見たすべての履歴を記録し、システムがニュースを推薦すると、各ユーザーの履歴からフィルタリングし、既存のレコードをフィルタリングします.問題は、ユーザーの量が多く、ユーザー一人一人が見たニュースが多い場合、このような方法では、システムの再稼働を性能に追随させることをお勧めしますか?
実際には、履歴がリレーショナル・データベースに格納されている場合、重さを落とすには頻繁にデータベースをexistsクエリする必要があり、システムの同時量が高い場合、データベースは圧力を担ぐことができません.
キャッシュを思い出すかもしれませんが、こんなに多くの履歴をすべてキャッシュすると、どれだけのストレージスペースが無駄になりますか?そして、このストレージスペースは時間とともに線形に増加しています.あなたは1ヶ月も耐えられます.何年も耐えられますか.しかし、キャッシュしないと性能が追いつかないので、どうすればいいですか?
この時、ブロンフィルタ(Bloom Filter)が登場し、このような重い問題を解決するために使われた.重さを落とすと同時に、空間的に90%以上節約できますが、少し不正確なだけで、一定の誤審確率があります.
ブロンフィルターは何ですか?
ブロンフィルタは、あまり正確ではないset構造と理解でき、containsメソッドを使用してオブジェクトが存在するかどうかを判断すると、誤審する可能性があります.しかし、ブロンフィルタも特に不正確ではなく、パラメータの設定が合理であれば、その精度は相対的に十分に正確に制御でき、小さな誤判確率しかありません.
ブロンフィルタが値が存在すると言った場合、この値は存在しない可能性があります.存在しないと言ったら、存在しないに違いない.例えば、あなたを知らないと言ったら、きっと知らないに違いない.あなたに会ったことがあると言ったとき、全然会ったことがないかもしれませんが、あなたの顔は知っている人の中のある顔に似ている(いくつかの熟した顔の係数の組み合わせ)ので、前に会ったことがあると誤審しました.
上の使用シーンでは、ブロンフィルタはすでに見た内容を正確にフィルタリングすることができ、見たことのない新しい内容もごく一部(誤審)をフィルタリングすることができますが、ほとんどの新しい内容は正確に識別することができます.これにより,ユーザに推奨されるコンテンツが重複しないことを完全に保証できる.
Redisのブロンフィルタ
Redisが公式に提供したブロンフィルターは、Redis 4.0がプラグイン機能を提供してから正式に登場した.ブロンフィルタは、プラグインとしてRedis Serverにロードされ、Redisに強力なブロンデリバリー機能を提供します.
次はRedis 4.0のブロンフィルターを体験してみましょう.煩雑な取り付けを省くためにDockerを直接使いましょう.
> docker pull redislabs/rebloom #
> docker run -p6379:6379 redislabs/rebloom #
> redis-cli # redis
上の3つの命令の実行に問題がなければ、ブロンフィルタを体験することができます.
ブロンフィルター基本使用
ブロンフィルタには2つの基本命令があり、bf.add追加要素、bf.existsクエリー要素が存在するかどうか、その使い方とsetセットのsaddとsismemberの差は多くありません.注意bf.addは一度に1つの要素しか追加できません.一度に複数を追加するには、bf.maddコマンドが必要です.同様に、複数の要素が存在するかどうかを一度にクエリする必要がある場合は、bf.mexistsコマンドを使用する必要があります.
127.0.0.1:6379> bf.add codehole user1
(integer) 1
127.0.0.1:6379> bf.add codehole user2
(integer) 1
127.0.0.1:6379> bf.add codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehole user1
(integer) 1
127.0.0.1:6379> bf.exists codehole user2
(integer) 1
127.0.0.1:6379> bf.exists codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehole user4
(integer) 0
127.0.0.1:6379> bf.madd codehole user4 user5 user6
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists codehole user4 user5 user6 user7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0
私たちが上で使用したブロンフィルタは、デフォルトのパラメータのブロンフィルタにすぎず、私たちが初めてaddしたときに自動的に作成されます.Redisは、addの前にbf.reserveコマンドを使用して明示的に作成する必要があるカスタムパラメータのブロンフィルタも提供しています.対応するkeyがすでに存在する場合、bf.reserveはエラーを報告します.bf.reserveにはkey,error_の3つのパラメータがありますrateとinitial_size.エラー率が低いほど、必要なスペースが大きくなります.initial_sizeパラメータは、予想される要素の数を表し、実際の数がこの数値を超えると誤判率が上昇します.
そのため、誤審率の上昇を招くことを避けるために、大きな数値を事前に設定する必要があります.bf.reserveを使用しない場合、デフォルトのerror_rateは0.01で、デフォルトのinitial_sizeは100です.
注意事項
ブロンフィルターのinitial_size推定が大きすぎると、ストレージスペースが浪費され、推定が小さすぎると、精度に影響し、ユーザーは使用する前にできるだけ要素の数を正確に推定しなければならない.また、実際の要素が予想外に推定値を高くしないように、一定の冗長空間を加える必要がある.
ブロンフィルターのerror_rateが小さいほど、必要なストレージスペースが大きくなり、正確すぎる必要がない場合、error_rateの設定は少し大きくても上品ではありません.例えば、ニュースを重んじると、誤審率が高いのは、一部の文章が適切な人に見られないだけで、文章の全体的な読書量がこのような誤審率で大きな変化をもたらすことはありません.
ブロンフィルタの原理
ブロンフィルタの使用を学んだので、以下に原理を説明する必要があります.そうしないと、読者はドラムに覆われ続けます.各ブロンフィルタがRedisに対応するデータ構造の中には、大きなビット数グループといくつかの異なる偏りのないhash関数があります.無偏とは元素のhash値を比較的均一に計算できることである.
ブロンフィルタにkeyを追加すると、複数のhash関数を使用してkeyをhashして整数インデックス値を算出し、ビット配列長をモデリングして位置を算出し、各hash関数は異なる位置を算出します.さらにビット数グループのこれらの位置を1にするとadd操作が完了します.
ブロンフィルタにkeyが存在するかどうかを尋ねるとaddと同様にhashのいくつかの位置も算出され、ビット配列のいくつかの位置が1であるかどうかを見て、1つのビットが0であれば、ブロンフィルタにこのkeyが存在しないことを示します.いずれも1であれば、このkeyが必ず存在するとは限らないが、これらのビットが1に設定されているのは、他のkeyの存在による可能性があるため、極めて存在する可能性が高い.このビット数グループがまばらであれば,正しいと判断する確率が大きく,このビット数グループが混雑していれば,正しいと判断する確率が低下する.具体的な確率計算の公式は比較的に複雑で、興味を持って読むことができて拡張して読むことができて、とても頭を焼いて、読者に詳しく見ることを提案しません.
実際の要素を初期化サイズよりはるかに大きくしないでください.実際の要素が初期化サイズを超え始めた場合、ブロンフィルタを再構築し、sizeより大きなフィルタを再割り当てし、すべての履歴要素を一括addします(これは、他のメモリにすべての履歴要素を記録する必要があります).error_rateは数が超過したために急激に増加することはなく,フィルタの再構築に比較的ゆとりのある時間を提供した.
ブロンフィルタの他の応用
爬虫類システムでは、URLを重くする必要があります.すでに登ったページは登らなくてもいいです.しかし、URLが多すぎて、数千万何億もあります.これらのURLアドレスを1つの集合で詰めると、スペースがもったいないです.この場合、ブロンフィルタの使用を考えることができます.再ストレージの消費量を大幅に削減できますが、爬虫類システムが少量のページを逃すこともあります.
ベロンフィルタはNoSQLデータベースの分野で非常に広く使用されており、私たちが普段使っているHBAse、Cassandra、さらにLevelDB、RocksDBの内部にはベロンフィルタ構造があり、ベロンフィルタはデータベースのIO要求数を著しく低減することができます.ユーザーがrowをクエリーする場合は、メモリ内のブロンフィルタで存在しないrowリクエストを大量にフィルタリングしてから、ディスクにクエリーすることができます.
メールボックスシステムの迷惑メールフィルタ機能も一般的にブロンフィルタが使われていますが、このフィルタを使っているので、普段も正常なメールが迷惑メールディレクトリに入れられていることに遭遇します.これは誤審によるもので、確率が低いです.