Redisデータ構造の概要：ビットマップ

ビットマップ（ビット配列、ビットベクトルなどとも呼ばれます）は、巨大なドメインのブール情報をコンパクトにマッピングする必要がある場合にすぐに頭に浮かぶデータ構造です。表現。 OSカーネル（メモリページ、iノードなど）、デジタルイメージングなど、メモリスペースが限られている場合は常に、非常に人気のあるデータ構造です。

メモリ内のデータ構造サーバーであるRedisは、ビット操作操作のサポートを提供します。ただし、Redisのビットマップには特別なデータ構造はありません。むしろ、ビットレベルの操作は基本的なRedis構造である文字列でサポートされています。現在、Redis文字列の最大長は512MBです。したがって、Redisがビットマップとしてマップできる最大のドメインは2（512 MB =2バイト=2ビット）です。

Redisのビット関連の操作には、次の2種類があります。定数時間（O（1））例：特定のビットを取得/設定する操作と、基本的にビットのグループを操作するO（N）の操作。これらの場合のNは、操作が処理する必要のあるビットの長さです。いくつかの例を見てみましょう。

コマンド

# SETBIT key offset value: Store bit value 'value' at offset 'offset' for 'key'. O(1)
# Returns the original bit value stored at that offset.
127.0.0.1:6379> setbit k 10 1
(integer) 0
# GETBIT key offset: Fetch value of 'offset' in 'key'. O(1)
127.0.0.1:6379> getbit k 10
(integer) 1
127.0.0.1:6379> getbit k 11
(integer) 0
127.0.0.1:6379> getbit k 0
(integer) 0
127.0.0.1:6379> setbit k 9 1
(integer) 0
127.0.0.1:6379> setbit k 8 1
(integer) 0
# And since it is still a generic String, here's a get.
127.0.0.1:6379> get k
"\x00\xe0"
# "\x00\xe0" -> "0000 0000 111"
# BITCOUNT key [start end]: Number of set bits in the range. O(N)
# IMPORTANT: start & end are bytes not bits
127.0.0.1:6379> bitcount k
(integer) 3
127.0.0.1:6379> set m "meow"
OK
# meow -> 01101101 01100101 01101111 01110111 
127.0.0.1:6379> bitcount m
(integer) 21
# BITPOS key bit [start] [end]: 1st position of 1 or 0 in the key in range. O(N)
127.0.0.1:6379> SET mykey "\xff\xf0\x00"
OK
127.0.0.1:6379> BITPOS mykey 0
(integer) 12

キー自体を操作する演算子のほかに、 BITOP 演算子は、複数のキー間のビット単位の論理演算に使用されます。

# BITOP operation destkey key [key ...]. O(N)
# operation can be  AND, OR, XOR and NOT
127.0.0.1:6379> set a "\xff\xff"
OK
127.0.0.1:6379> bitop not nota a
(integer) 2
127.0.0.1:6379> get nota
"\x00\x00"
127.0.0.1:6379> set b "\x0f\x0f"
OK
127.0.0.1:6379> set c "\xf0\xf0"
OK
127.0.0.1:6379> BITOP OR orbc b c
(integer) 2
127.0.0.1:6379> get orbc
"\xff\xff"
127.0.0.1:6379> BITOP AND andbc b c
(integer) 2
127.0.0.1:6379> get andbc
"\x00\x00"
127.0.0.1:6379> BITOP XOR xorbc b c
(integer) 2
127.0.0.1:6379> get xorbc
"\xff\xff"

内部

ビットマップ操作には独自のデータ構造がないため、説明する特別なデータ構造はありません。 Redis文字列自体は、バイナリセーフ文字列として実装されています。 Redis文字列データ構造は、内部的にSimple Dynamic String（SDS）と呼ばれます。本質的にはネイティブのchar[] いくつかの追加の簿記情報があります。実装の詳細はここにあります。

ビットマップ関数の実装は、ファイル bitops.cにあります。。

追記：重要なOSおよびグラフィックス機能のビット操作アルゴリズムの重要性を考えると、ほとんどのアーキテクチャはそのような操作のための特別な命令を提供します。さまざまな興味深いコンピューター算術アルゴリズムを読むのに適した場所は、時代を超えた古典的なHacker’sDelightです。

アプリケーション

この人気のあるGetSpoolブログは、大規模なデータセットのリアルタイム分析にビットマップを使用する優れた例です。これは、ビットマップの典型的な使用例でもあります。まともなパフォーマンスを維持しながら、非常に大きなドメインのブール情報を（比較的）小さなスペースに格納することです。

サイズは通常、非常に大きなビットマップの懸念事項です。これに対する最も有用な操作はO（N）であるためです。巨大なキーでの作業を避けるために、Redisのドキュメントでは、巨大なキーを複数の小さなキーに分割することを推奨しています。キーが大きくなるまで、BITCOUNTのパフォーマンスは許容範囲内です。その時点で、キーを分割するか、範囲引数を使用して増分クエリを実行することをお勧めします。低速のBITOP操作に対処するための推奨事項は、スレーブで実行することです。したがって、一般に、適度なサイズのキーを処理し、キーを複数のキーに分割することで将来の潜在的な成長を計画することは理にかなっています。

RedisセットとRedisビットマップ

Redisセットとビットマップ操作によって提供される機能の性質は似ています。そのため、2つのアプローチのどちらが優れているか混乱することがよくあります。まあ、それは本当にユースケースの正確な性質に依存します。明らかに、この説明は、セットとビットマップの両方が実行できる種類の操作に対してのみ有効です。

Redisセットは一般に効率的で拡張性が高く、サイズが使用できなくなるまでデータ構造を選択する必要があります。 Redisセットは管理も簡単で、プログラムとデバッグはほとんどのアプリケーションでうまく機能します。セットの使いやすさを過小評価してはなりません。ビットマップを操作するコードは、通常、読み取り、理解、デバッグ、および保守が困難です。ドメインが非常に大きい場合でも、セットが適切な場合があります。たとえばアプリケーションが人気のあるeコマースサイトへの毎日の訪問を追跡することを目的としている場合、通常、ユーザーベース全体のわずか5〜10％が毎日サイトにアクセスするため、結果はセットにうまく収まる可能性があります。これは、ユーザーベース全体の60％が毎日ログインすると予想されるサイトでは明らかに変化します。次に、多数のキーに対する論理ビット単位の操作のサイズとパフォーマンスを考えると、ビットマップの関連性が高くなります。 Redisセットには、IDをビットオフセットにマップする必要がないという明確な利点もあります。同様に、値が2より大きいドメインからのものである場合、ビットマップ用にドメインを分割するメカニズムを理解するよりも、Redisセットを使用する方が簡単である必要があります。

MOOCの分析

これは、Redisビットマップ操作を適用できる場所の例です（ただし、十分に現実的です！）。たとえば、数十万人の学生が登録している非常に人気のあるオンラインMOOCを実行しているとします。コースを促進するアカデミックチームは、学生の進捗状況と登録済みの学生の一般的な背景をリアルタイムで確認できるダッシュボードを必要としています。これは、Redisビットマップ操作を介して実装することにしました。これが段階的なアプローチです。

学生IDとビットマップオフセットの間をマッピングする計画を作成します。 IDがビットマップのオフセットであるのと同じくらい簡単かもしれません。
コースの開始後に、人口統計に関連するさまざまなビットマップを作成して入力します。たとえば同じ大学、教育レベル、性別などの他のMOOCに登録している学生
これで、コースの進行に合わせて、コースの進行状況を記録するための新しいビットマップを作成できます。たとえば第1週のすべての講義の視聴を完了した学生、第1週のすべての課題を完了した学生など。
これで、これらのキーに基づいてリアルタイム分析を作成することは非常に簡単な演習であり、ドラッグアンドドロップUIで実行できます。例：

第1週（A）の講義を視聴したが、第1週（B）の課題を完了しなかった学生の数を確認したい教授：オペレーター：BITOP。操作：A AND（Bではありません）。
第1週（A）、第2週（B）、第3週（C）、第4週（D）のすべての課題を完了した生徒：オペレーター：BITOP。オペレーションAANDB AND C AND D.言ってやるが、これらはコースに合格した人々だ。
コースに合格したすべての男子生徒（M）（上記で計算したように、たとえばP）：オペレーター：BITOP。操作：MおよびP。
コースに合格した学生の数：BITCOUNT P.

同様に、ビットマップとして任意の数の興味深いコホートを設定でき、そのような順列が実行されます。

脚注

Redisデータ構造シリーズの他の投稿：

セット
ハッシュ
ソートされたセット