要件:最近、BilibiliでRedis Bloomアルゴリズムの動画を見ました。キャッシュ侵入の問題を解決するためのもので、簡単に言えば、データベースにアクセスする前に論理的判断の層を加えてデータが存在するかどうかを判断し、存在する場合はデータベースにアクセスすることです。 例えば、ウェブサイトがニュースシステムであり、記事のURLは自己増分の主要キーID(URLフォーマット example:/news-1.html)によって生成され、ウェブサイトには数万件の記事やキャッシュしかない場合もあります。
もともとは：
ニュースリソースのリクエスト -> キャッシュの存在を判断 -> プレゼンス -> キャッシュはデータを返します。
ニュースリソースのリクエスト -> キャッシュが存在するかどうかを判断 -> 存在しない -> データベースからのクエリ -> 提供 -> キャッシュとデータを返す。
ニュースリソースをリクエストする -> キャッシュが存在するかどうかを判断 -> 存在しない -> データベースからのクエリ -> 存在しない -> 404エラーを返す。
今すぐ：
ニュースリソースをリクエスト -> ブルームのアルゴリズム -> 存在 -> 元の論理に従う。
ニュースリソースをリクエスト -> ブルームのアルゴリズム -> は存在しません -> 直接404エラーを返します。
ブルームフィルター
BloomFilterアルゴリズムはビッグデータのスケジューリングアルゴリズムです。 大量のデータを持つ集合では、対象がその集合に含まれていないことを正確に判定できます。 集合の中の対象を判断しても、ほとんどスペースを取らないことは可能です。 それ高精度かつ誤差ゼロが求められる状況には適していません。 部分的な精度を犠牲にすることでスペースの効率的な利用が実現されます。
ブルームのアルゴリズムは、一定の精度を犠牲にして、メモリ消費の少ないフィルタリングアルゴリズムを採用するこれは大量のデータに対してフィルタリング、重複除去、その他の操作を実現できます。
Bloomアルゴリズムは抽象的な概念であり、さまざまな方法で実装可能です。記事でRedisでBitMapを使うのは単なる実装に過ぎません。
参考：ハイパーリンクのログインが見えます。
ビットマップの紹介
ビットマップはビットマップであり、実際にはバイト配列で二進数で表現されています。数字は0と1の2つだけです、ビットマップは各2進ビットを使って要素に対応する値を保存またはマークします。 ビットマップはビット単位で保存されるため、特定のデータが存在するかどうかを判定するために通常使われます。
下図に示すように、文字列はコンピュータ内でバイナリ形式で格納されています。
Redisにおけるビットマップデータ型
Redisが提供するデータ型はBitMapで、各ビットは0と1の2つの状態に対応しています。 内部ストレージは依然としてString型ですが、RedisはBitMapを直接操作するための命令を提供しており、BitMapはビット配列と考えられます。配列の添字がオフセットです。
その利点は以下の通りです:低メモリオーバーヘッドと高効率そして、その作戦はシンプルです。
スペース節約:ビットは要素の値や状態を表すために使われ、keyは対応する要素の値です。 実際、8ビットでバイトを構成できるため、スペースの節約にもなります。
高効率:setbitとgetbitの時間計算量はO(1)であり、他のビットの効率も高いです。
セットコレクションとBitMapストレージの使い方の例を挙げます:
| データ型 | 各ユーザーIDは容量を占有します | 保存すべきユーザー数 | すべてが記憶を占める | | セット | 32ビットは4バイト(ユーザーIDが整数を使うと仮定し、多くのウェブサイトは実際には長整数を使用しています) | 50,000,000 | 32ビット * 50,000,000 = 200 MB | | ビットマップ | 1ビット | 100,000,000 | 1ビット * 100,000,000 = 12.5 MB |
時間が少し伸びている
| | 一日 | 一月 | 一年 | | セット | 200M | 6G | 72G | | ビットマップ | 12.5M | 375M | 4.5G |
計算の結果、時間が経つにつれて記録すべきデータ量が増え、コントラストがより明確になり、ビットマップの占有容量が設定より少ないことが分かりました。
RedisはBitMapの操作方法として以下の手順を提供しています:
コマンドドキュメント:ハイパーリンクのログインが見えます。
アルゴリズムとRedisのビットマップ機能、構文をざっと理解したところで、redisを使って簡単な操作を行いましょう。
SETBIT構文:SETBITキーオフセット値
記事 id:9, 10, 156 を 1 に設定すると、コマンドは以下の通りです:
GETBIT構文:GETBITキーオフセット
id: 10 または 11 の存在を判定するコマンドは以下の通りです:
.NET/C#はRedisのBitMap型を操作します
RedisでいくつかのBitMapコマンドについて学び、それらをプログラム的に操作する方法を学びました。 新しい.NET 3.1コンソールプロジェクトを作成し、StackExchange.Redisパッケージを参照して、以下のコマンドを使用します。
ソースコードは以下の通りです:
Redisには他にも多くのビットマップアプリケーションがあります。以下のように。
- ユーザーが特定の操作を行ったかどうかを判断するための簡単なブルームフィルターとして利用できます。
- ユーザーの日次活動、月間活動、定着率の統計
- ユーザーローンチ数の統計を把握しましょう
- ユーザーのオンラインプレゼンスと人物統計
(終わり)
|
掲載地 2023/01/02 17:37:01
|
|
|
|
地主|
掲載地 2023/01/02 17:41:56
|
掲載地 2023/01/02 20:42:47
|
