Redis データ構造の String 型について話しましょう-Redis-php.cn

Redis データ構造の String 型について話しましょう

青灯夜游

リリース： 2021-12-08 09:53:51

転載

1899 人が閲覧しました

この記事では、Redis データ構造の String 型を理解し、Redis の KV ストレージ構造について説明します。お役に立てば幸いです。

Redis データ構造の String 型について話しましょう

Redis は分散 KV キャッシュとしてよく使用されますが、多くの人は単にそれを使用していますが、その下に多くの未知の秘密があることを知りません。 [関連する推奨事項: Redis ビデオチュートリアル ]

String 型

String は、Redis でサポートされる最も基本的なデータ型です。文字列、そのデータ構造とストレージはどのようなものですか。

SDS を再定義して String を保存する

ご存知のとおり、redis は C 言語で書かれており、C 言語には String 型はなく、char[] のみがあります。初期化中にサイズを指定する必要があり、タイプを変更することはできません。 incrコマンドやappendコマンドなどの動的追加・拡張などの機能を実現するために、redisではこれらの機能を実現するSDS(Simple Dynamic String)を定義・保守しています。

まず、Redis ソースコードで定義されているデータ構造を見てみましょう。スペースを節約するために、ここでは 5 つのタイプがあります。

Redis データ構造の String 型について話しましょう

1. len: char[] の長さを取得するには、配列を走査する必要があります。len(char[]) の時間計算量は O(n) です。 ;
2. alloc : C 言語には String 型はなく、char[] だけがあり、char[] は最初にスペースの長さを割り当てる必要があります。char[] には事前に割り当てられた長さがあり、データが大きくなった後に拡張する必要があります;

3. falgs: 常に 1 バイトを占有します。最下位の 3 ビットはヘッダーのタイプを示すために使用されます。ヘッダーは5種類あり、sds.hに定数定義があります。
4. buf[]: C 言語の char 配列。'\0' が終わりを表します。これは、バイナリデータの保存に '\0' を含めることはできないことを意味します。画像、音声などのバイナリストレージには問題が発生します。 . - これが、Redis が実装した SDS がバイナリセーフな文字列であると述べた理由です。

C のオリジナル char 配列に対する SDS の改善

1. Redis によって実装された SDS は拡張をサポートしています
2. 長さ len が含まれており、長さを取得する複雑さは次のとおりです。 O(1 )
3. スペースの事前割り当て
4. 遅延スペースの解放 (後述)

SDS の利点と欠点

利点

拡張をサポートできます
長さ len を含み、長さの複雑さ O(1) を取得します
スペースの事前割り当て

欠点

追加のメモリを割り当てる必要がある
頻繁な割り当てとリサイクルによって生じる効率の問題

Redis で使用されるメモリ割り当てライブラリ jemalloc

jemalloc がメモリを割り当てるときは、割り当てられたスペースとして N に適用するバイト数に基づいて、N より大きいが N に最も近い 2 のべき乗を見つけます。これにより、頻繁な割り当ての数を減らすことができます。例えば。 6 バイトのスペースを申請した場合、jemalloc は実際に 8 バイトのスペースを割り当てます。24 バイトのスペースを申請した場合、jemalloc は 32 バイトを割り当てます。したがって、先ほど述べたシナリオでは、dictEntry 構造体は 32 バイトを占有します。

スペースの事前割り当て

スペースの事前割り当ては、SDS の文字列拡張操作を最適化するために使用されます。SDS API が SDS を変更し、スペースを変更する必要がある場合に使用されます。 SDS への割り当て拡張時に、プログラムは変更に必要な領域を SDS に割り当てるだけでなく、追加の未使用領域も SDS に割り当てます。

このうち、追加で割り当てられる未使用領域の量は、次の式で決定されます。

SDS が変更された場合、SDS の長さ (つまり、 len 属性) が 1 MB 未満の場合、プログラムは len 属性と同じサイズの未使用領域を割り当てます。このとき、SDS の len 属性の値は free 属性の値と同じになります。たとえば、変更後に SDS の len が 13 バイトになる場合、プログラムは未使用スペースも 13 バイト割り当て、SDS の buf 配列の実際の長さは 13 13 1 = 27 バイトになります (追加のバイトnull 文字を保持するために使用されます)。
SDS を変更した後、SDS の長さが 1 MB 以上になる場合、プログラムは 1 MB の未使用スペースを割り当てます。たとえば、変更後に SDS の len が 30 MB になる場合、プログラムは 1 MB の未使用スペースを割り当て、SDS の buf 配列の実際の長さは 30 MB 1 MB 1 バイトになります。

Redis は、スペースの事前割り当て戦略を通じて、文字列拡張操作を継続的に実行するために必要なメモリの再割り当ての数を減らすことができます。

レイジーリリース

レイジースペースリリースは、SDS の文字列短縮操作を最適化するために使用されます。SDS API が SDS によって保存された文字列を短縮する必要がある場合、プログラムはそれを実行します。すぐにはではありません。メモリの再割り当てを使用して短縮後の余分なバイトをリサイクルしますが、free 属性を使用してこれらのバイト数を記録し、将来の使用を待ちます。

Redis の KV ストレージ構造

Redis では、すべてのストレージは KV キーと値のペアの形式で保存されます。K は文字列型で、これは SDS です。V はそれを可能にしますは文字列、リスト、ハッシュなどです (Redis によってサポートされるデータ構造)。V は特定の型に直接設定されませんが、redisObject の層でカプセル化されます。実際に格納されたデータ構造は、具体的には ptr ポインタによって指されます。。

さらに、領域を節約するために、redis は ptr ポインターをさまざまな方法で保存しますが、一方で Long 型の整数を保存する場合、RedisObject 内のポインターは整数データに直接割り当てられるため、整数を指すために追加のポインターが必要ないため、ポインターのスペースオーバーヘッドが節約されます。一方、文字列データが保存され、その文字列が 44 バイト以下の場合、RedisObject 内のメタデータ、ポインター、SDS は連続したメモリ領域となるため、メモリの断片化が回避されます。このレイアウト方式はembstr符号化方式とも呼ばれます。もちろん、文字列が 44 バイトを超えると、SDS 内のデータ量が増加し始め、Redis は SDS と RedisObject を一緒にレイアウトしなくなり、代わりに SDS に独立した領域を割り当て、SDS 構造を指すポインターを使用します。。このレイアウト方法は raw エンコードモードと呼ばれます。図に示すように、

Redis データ構造の String 型について話しましょう

embstr エンコーディング
短い文字列、メモリ割り当てを保存します。
コンテンツが次の場合、読み取り専用です。変更後は、(44 バイトを超えない場合でも) raw エンコードになります。
raw エンコード
は、44 バイトを超える長い文字列を格納するためにメモリ領域を複数回割り当てることができます。

raw raw SDS の文字長が 44 未満に短縮された場合、embstr エンコーディングに逆変換されますか?
いいえ、Redis の基礎となるコーディングは、変更後は元に戻せません (ロールバックされません)。