Redisのデータ構造を詳しく解説

実際の開発では、Redis が頻繁に使用されることになりますが、使用時にデータ型を正しく選択するにはどうすればよいでしょうか?どのデータ型がどのシナリオに適しているか。そして面接では、面接官が Redis のデータ構造についてよく質問します:

• なぜ Redis は速いのですか?
• クエリ操作が遅くなるのはなぜですか?
• Redis ハッシュの再ハッシュ プロセス
• Redis のインデックスとしてハッシュ テーブルを使用する理由

Redis データ構造を分析して理解したとき。これは、使用するデータ型を正しく選択し、Redis を使用する際のシステム パフォーマンスを向上させるのに役立ちます。 [関連する推奨事項: Redis ビデオ チュートリアル ]

Redis基礎となるデータ構造

Redis はいmemorykey-valuekey-value データベース。キーと値のペアのデータは memory に保存されるため、Redis メモリ-ベースのデータ操作は、高効率かつ高速です;

このうち、Key は String 型で、Redis は ## をサポートします。 #value タイプ String、List、Hash、Set、Sorted Set、## を含む#BitMap お待ちください。 Redis これが多くのビジネス シナリオに広く適用できる理由は、その多様な種類の value に基づいています。

Redis

の Value のデータ型は、RedisredisObject 用にカスタマイズされたオブジェクト システムに基づいています。実装済み、<pre class="brush:php;toolbar:false">typedef struct redisObject{     //类型     unsigned type:4;     //编码     unsigned encoding:4;     //指向底层实现数据结构的指针     void *ptr;     …..  }</pre>

redisObject

実際のデータの記録に加えて、データ長、スペース使用量などのメタデータ情報を記録するために追加のメモリ領域も必要です。これには 8 バイトのメタデータが含まれます。および 8 バイトのポインター。ポインターは、特定のデータ型の実際のデータの場所を指します。

このうち、

ポインター

に基づく場所を指します Redis の基礎となるデータ構造には、データの場所が格納されます。Redis の基礎となるデータ構造は次のとおりです: SDS、二重リンクによって実装されますリスト、ジャンプ テーブル、ハッシュ テーブル、圧縮リスト、整数セット。 では、Redis の基礎となるデータ構造はどのように実装されているのでしょうか?

Redis の基礎となるデータ構造の実装

Redis

比較的単純なSDS を見てみましょう。2 つ目は、リンクされたリスト、整数のセット。

SDS、二重リンク リストと整数セット

SDS

、len フィールドを使用使用されるバイト数により、文字列の長さを取得する複雑さが O(1) に軽減されます。また、SDS は 遅延解放スペース であるため、free を解放します。スペースにある場合、システムはデータを記録し、次回使用するときにそれを直接使用できます。新たにスペースを申請する必要はありません。
整数コレクション
、メモリ内に連続したアドレスを持つスペースを割り当てると、データ要素は並べて保存されます。スペースのオーバーヘッドをもたらす追加ポインタ。その特徴は、メモリがコンパクトでメモリ領域を節約し、クエリの複雑さが O(1) で効率が高く、その他の演算の複雑さが O(N) であることです。

二重リンク リスト

。これはメモリ内で非連続かつ非順次の空間にすることができ、要素間のシーケンスは追加のポインタ オーバーヘッドを通じて直列に接続されます。フロントエンド/バックエンドポインタ。 その特徴は、セクション内のデータの挿入/更新の複雑さは O(1)、高効率、クエリの複雑さは O(N) であることです。 #Hash

ha ハッシュ テーブル

ハッシュ テーブルは実際には配列に似ています。配列の各要素はハッシュ バケットと呼ばれます。各ハッシュ バケットにはキーと値のペアのデータが格納され、ハッシュbucket 要素は dictEntry 構造、

を使用します。 したがって、ハッシュ バケット要素はキーと値のペア自体を保存しませんが、を指します 特定の値
へのポインターです。そのため、各キーと値のペアを保存するときにスペースのオーバーヘッドが追加されます。少なくとも 24 バイトが追加されます。特に Value は

です。 String

キーと値のペア。各キーと値のペアには追加の 24 バイトのスペースが必要です。保存されるデータが小さく、追加のオーバーヘッドがデータよりも大きい場合、スペースを節約するために、データ構造の変更を検討してください。

グローバル ハッシュ テーブルの全体像を見てみましょう:

ハッシュ テーブルの操作は非常に高速ですが、Redisデータが大きくなると、潜在的なリスクが発生します: ハッシュ テーブルの競合問題と rehash オーバーヘッドの問題 、これで、ハッシュ テーブルの操作が遅くなる理由が説明できますか?

より多くのデータをハッシュ テーブルに書き込む場合、ハッシュの競合は避けられない問題です。Redis がハッシュの競合を解決する方法は Chained Hash であり、同じハッシュ バケットに複数の要素が保存されます。

ハッシュの競合が増えると、これにより、一部のハッシュ競合チェーンが長くなり、このチェーン上の要素の検索に時間がかかり、効率が低下します。

ハッシュの競合によって引き起こされる長すぎるチェーンの問題を解決するには、rehash 操作を実行して既存のハッシュ バケットの数を増やし、ハッシュ バケットを分散させます。 single バケット要素の数。では、rehash

プロセスはどのように実行されるのでしょうか?

Rehash

• rehash
• 操作をより効率的にするために、ハッシュ テーブル 1 とハッシュ テーブル 2 の 2 つのグローバル ハッシュ テーブルが使用されます。ハッシュ テーブル 2 を次のようにします:

より大きなスペースをハッシュ テーブル 2 に割り当てます。ハッシュ テーブル 1 のデータを再マップし、それをテーブル 2 のハッシュにコピーします。

ハッシュ テーブル 1 の領域を解放します。 ただし、リマップやコピーの際、テーブル 1 とテーブル 2 のデータ サイズが大きいため、ハッシュ テーブル 1 を一度に配置すると、すべてのデータが終わった後にが移行された場合、Redis スレッドはブロックされ、他のリクエストを処理できなくなります。 この問題を回避し、Redi

がクライアント リクエストを正常に処理できるようにするために、

Redis

は

プログレッシブ rehash

## を採用しています。 ＃。

リクエストが処理されるたびに、インデックス位置にあるすべてのエントリがハッシュテーブル 1 からハッシュテーブル 2 にコピーされ、一度に大量にコピーされるオーバーヘッドは複数の処理の処理に割り当てられます。 、時間のかかる操作を回避し、データへの高速アクセスを確保します。

Hash

ハッシュ テーブルに関連する知識ポイントを理解した後、一般的ではない圧縮リストとスキップ テーブルを見てみましょう。
圧縮リストとスキップ テーブル

圧縮リスト

、配列に基づいて、圧縮リストのヘッダーには zlbytes、zltail の 3 つのフィールドがあります。 zllen と zllen は、それぞれリストの長さ、リストの終わりのオフセット、リスト内のエントリの数を表します。圧縮されたリストのテーブルの終わりには、リストの終わりを示す zlend もあります。

利点:

メモリがコンパクトでメモリ空間を節約 メモリ上に連続したアドレスの空間を確保し、データ要素を格納しますスペースのオーバーヘッドを削減するため、最初の要素と最後の要素の検索と特定は、3 つのヘッダー フィールドの長さを通じて直接見つけることができ、複雑さは O(1) です。

ジャンプ リスト

は、リンク リストに基づいてマルチレベル インデックスを追加し、次に示すようにインデックス位置での複数のジャンプを通じてデータの迅速な配置を実現します。図：

例：クエリ33

特徴：データ量が多い場合、スキップテーブルの検索複雑さはO(logN) 。 要約すると、基礎となるデータ構造の時間計算量を知ることができます: データ構造タイプ

時間計算量
ハッシュ テーブル	O(1)
整数配列	O( N)
二重リンクリスト	O(N)
圧縮リスト	O( N )

ジャンプ リスト######O(logN)############

Redisカスタム オブジェクト システム タイプは、Redis の Value データ型です。Redis のデータ型は、基礎となるデータ構造が実装されている場合、データ型は何ですか?

Redis データ型

String、List、Hash、Sorted Set 、Set は比較的一般的な型であり、基礎となるデータ構造との対応関係は次のとおりです。

##ハッシュ圧縮リスト
ハッシュ テーブル # ソートされたセット圧縮リスト
スキップリストセットハッシュテーブル
整数配列#

データ型の対応する特性は、その実装の基礎となるデータ構造に似ており、プロパティも同じです。また、

String は SDS に基づいて実装されており、適切です。単純な key-valueストレージ、setnx key valueの場合は、分散ロック、カウンター (アトミック性)、および分散グローバル一意 ID を実装します。

List は、FIFO (先入れ先出し) ルールに従い、要素が List に入る順序に従って並べ替えられ、通常は次の中で使用されます。統計のソートと単純なメッセージキュー。

Hash は、文字列 key と文字列 value の間のマッピングです。オブジェクト情報を表すのに非常に適しています。機能が追加されています。また、削除操作の複雑さは O(1) です。

Set は、String 型要素の順序付けされていないコレクションです。コレクションのメンバーは一意であるため、コレクション内に重複したデータが存在することはできません。ハッシュ テーブルに基づいて実装されるため、追加、削除、検索の複雑さは O(1) です。

Sorted Set は Set タイプのアップグレードです。違いは、各要素が double タイプのスコアに関連付けられていることです。スコアをソートすることで、範囲クエリは次のようになります。可能。

それでは、これらのデータ型、Redis Geo、HyperLogLog、BitMap を見てみましょう。

Redis Geo は、地球を近似的な球として扱い、GeoHash に基づいて 2 次元の経度と緯度を文字列に変換し、位置の分割と指定された距離のクエリを実装します。機能は通常、位置情報関連のアプリケーションで使用されます。

HyperLogLog は、確率的アルゴリズムを使用してセットのおおよそのカーディナリティを約 0.81% のエラー率でカウントする probabilistic データ構造です。セット要素の数が非常に多い場合、カーディナリティの計算に必要なスペースは常に固定され、非常に小さいため、UV 統計に適しています。

BitMap は 1 ビットを使用して要素の状態をマップします。状態は 0 と 1 の 2 つだけです。これは非常に典型的なバイナリ状態であり、文字列型を基礎となる層. データ構造によって実装される統計的なバイナリ状態のデータ タイプ。多くのメモリ スペースを節約できるという利点があり、バイナリ統計のシナリオで使用できます。

上記の知識を理解した後、対応するアプリケーション シナリオで Redis データ型を選択するためにどのような戦略が使用されるかについて説明します。

適切な Redisデータ型戦略

実際の開発アプリケーションでは、Redis は多くのビジネス シナリオに適用できますが、必要なものは何ですか? ? データ型ストレージの選択についてはどうですか?

主な基礎は時間/空間の複雑さですが、実際の開発では次の点が考慮されます:

#データ量、データ自体のサイズ
• コレクション タイプ 統計モード
• シングル ポイント クエリ/範囲クエリをサポート
• 特別な使用シナリオ

データ量、データ自体のサイズ

データ量が比較的多く、データ自体が比較的小さい場合、

String を使用すると、余分なスペースの使用量が大幅に増加します。 table はキーと値のペアを保存するために使用され、dictEntry は使用されます 構造体を保存すると、各キーと値のペアを保存するときに dictEntry の 3 つの追加ポインターを保存するオーバーヘッドが発生します。データ自体が追加のスペース オーバーヘッドよりも小さくなり、最終的には元のデータ ストレージ サイズよりもはるかに大きなストレージ スペースのデータ サイズにつながります。

整数配列

と圧縮リスト##に基づいて、List、Hash、Sorted Set#を使用して実装できます。 、整数配列と圧縮リストは、メモリ上に連続したアドレスを持つ空間を確保し、その空間にセット内の要素を1つずつ配置するため、非常に便利です。コンパクトであり、要素を接続するために追加のポインタを使用する必要がないため、追加のポインタによって引き起こされるスペースのオーバーヘッドが回避されます。さらに、コレクション型を使用する場合、1 つのキーがコレクションのデータに対応し、より多くのデータを保存できますが、使用される dictEntry は 1 つだけであるため、メモリが節約されます。 コレクション タイプの統計モード

Redis

一般的なコレクション タイプの統計モードには次のものがあります:

• 集計統計 (交差、差分セット、和集合統計): 複数のセットで集計計算を実行する場合、Set;
• 統計の並べ替え (セット タイプが必要です)要素の順序は保持できます): Redis の List と Sorted Set は順序付けられたコレクションであり、List は要素に従って入力されます List は順序でソートされ、Sorted Set は要素の重みに従ってソートできます;
• バイナリ状態統計 (セット要素の値は0 と 1 のみ) : Bitmap 自体は、基盤となるデータ構造として String 型を使用して実装された統計バイナリ状態データ型です。ビットマップは、BITOP のビットごとの AND、OR、および XOR の後に使用されます。 BITCOUNT は 1 の数をカウントします。
• カーディナリティ統計 (セット内の固有の要素の数をカウントする): HyperLogLog は、カーディナリティをカウントするために使用されるデータ収集タイプです。統計結果には、一定の誤差があります。標準エラー率は次のとおりです。 0.81%。正確な統計結果が必要な場合は、Set または Hash タイプを使用します。

#Set タイプ。# などの統計的なユーザー/友達/フォロー/ファン/関心のある人々のコレクション集計操作に適しています。

## 毎日のモバイル APP の新規ユーザー数の統計

• 2 人のユーザーの共通の友人

Redis

中リスト と Sorted Set は順序付きセットで、

最新のコメント リスト

• Ranking
などのセット要素の並べ替え要件を処理するために使用されます。

ビットマップ

バイナリ ステータス統計は、大量のデータを含む統計に適しており、次のようなバイナリ ステータスで表すことができます。クロックイン、その日のユーザー チェックイン数User Weekly Active

User Online Status
• HyperLogLog
• は、カーディナリティをカウントし、コレクション内の非繰り返し要素をカウントするために使用されるデータ コレクション タイプ 数値 (例:

は、Web ページの UV をカウントします。カウントできるのは、1 日にユーザーが複数回訪問した場合のみ)

シングルポイント クエリ/範囲クエリをサポート

RedisList

および

Sorted Set は範囲クエリをサポートする順序付きコレクションですが、Hash は 範囲クエリをサポートしない特別な使用シナリオです

メッセージ キュー 、メッセージ キューの実装として Redis

を使用、メッセージの基本要件

メッセージの順序を保持する 、 重複するメッセージ および を処理するメッセージの信頼性を確保する 、ソリューションは次のとおりです。 List のメッセージ キュー ソリューションに基づく #ストリーム ベースのメッセージ キュー ソリューション

データ型	データ構造
文字列	SDS (単純な動的文字列)
リスト	二重リンク リスト 圧縮リスト

#リストに基づくStrems に基づく##メッセージ順序の保存#LPUSH/RPOP を使用するXADD/XREAD を使用する使用 XREAD ブロック プロデューサはグローバル一意の ID を実装しますメッセージの信頼性使用 使用 保留 メッセージを自動的に保持するリスト ロケーションベースの LBS サービスは、特定の RedisGEO概要

	##読み取りのブロック	BRPOP
	重複メッセージ処理	#ストリームは自動的にグローバルに一意の ID を生成します
	BRPOPLPUSH
	#適用可能なシナリオ##メッセージの総量は少ないです##メッセージの総量はサイズが大きく、データはコンシューマ グループの形式で読み取る必要があります
GEO## を使用して実装されています	の # データ型	は地理的な位置情報を経度と緯度の形式で記録でき、LBS で広く使用されています。たとえば、タクシー配車ソフトウェアが位置に基づいてサービスを提供する方法などです。

Redis は、メモリベースのデータ操作と HashHash As の使用により非常に高速です。インデックスに基づいてテーブルは非常に効率的かつ高速であり、基になるデータが多様化しているため、多くのシナリオに適用できます。さまざまなシナリオで適切なデータ型を選択すると、クエリのパフォーマンスを向上させることができます。 プログラミング関連の知識について詳しくは、プログラミング ビデオ

をご覧ください。 ！

以上がRedisのデータ構造を詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。