Redis で SDS の単純な動的文字列問題を解決する方法

1. SDS

C 言語の構造には文字列型はなく、本質的には char[] 配列であり、C 言語配列のサイズは作成時に初期化する必要があります。型を指定した後は変更できず、最後の文字配列の要素は常に null 文字 '\0' になります。

以下は、値「Redis」を持つ C 文字列を示しています。

Redis は、C 言語の string メソッドを直接使用するのではなく、A 型を構築します。単純な動的文字列 (SDS) のです。Redis の基になる文字列は、SDS 構造を使用して保存されます。たとえば、文字列を含む基になるキーと値のペアはすべて、SDS 構造を使用して実装されます。

SDS 構造は sds.h

struct sdshdr{


    int len;//SDS保存的字符串长度


    int free;//buf数组中未使用字节数量


    char buf[];//字符数组，保存字符串


}

で定義されています。最後のバイトはヌル文字 '\0' を保存し、C 文字列の仕様を保持します。 , これにより、SDS 構造化文字列は C 関数ライブラリの一部の関数を再利用できます。

2. C 文字列を使用しない理由

主な理由は、C 文字列には次の欠点があるためです:

文字列長を取得する時間計算量は O(N) です。文字列の長さを取得するには、ヌル文字「\0」が見つかるまで文字列全体をたどる必要があります。文字列追加操作中に割り当てられたメモリが不十分な場合、バッファ オーバーフローが発生する可能性があります。メモリの再割り当て: 文字列が増加または切り詰められるたびに、プログラムは C 文字列を保持する配列に対してメモリの再割り当て操作を実行する必要があります。メモリの再割り当てには複雑なアルゴリズムが含まれ、システム コールの実行が必要になる場合があるため、通常は比較的時間がかかります。 1時間かかります。 Null 文字の問題: C 文字列の途中にスペースを格納することはできません。そうしないと、プログラムが走査するときに、それが文字列の終わりであると誤って認識してしまいます。この制限により、C 文字列はテキスト データの保存にのみ使用でき、画像、オーディオ、ビデオなどのバイナリ データ、圧縮ファイルの保存には適していません。

3. C 文字列の問題を解決する方法

1. SDS は len 属性を通じて SDS の長さを記録するため、長さを取得する時間は複雑になります。は O( 1)、つまり strlen コマンドの時間計算量は O(1) です。

2. SDS スペース割り当て戦略はバッファ オーバーフローを回避します: SDS が変更されると、最初に SDS スペースが変更を満たすかどうかがチェックされ、満たさない場合は、変更を実行する前に必要なサイズまで自動的に拡張されます。

3. 文字列変更時のメモリ再割り当て回数が少なくなります: SDS の free は、buf バイト配列内の未使用のバイトを記録します。

Redis は、スペースの事前割り当てと、free 属性による遅延スペースの解放という 2 つの最適化戦略を実装しています。

スペースの事前割り当て: SDS で拡張操作を実行する場合、プログラムは変更に必要なスペースを割り当てるだけでなく、追加の未使用スペースも SDS に割り当てます。文字列の拡張操作が継続的に実行されると、メモリの再割り当ての数が減少します。これは、事前割り当て戦略によって実現されます。遅延スペース解放: SDS が切り詰められると、プログラムは短縮後の余分なバイトによって占有されていたメモリをすぐに再利用せず、代わりに、free 属性を使用して、将来の使用に備えて余分なバイトを記録します。未使用のスペースは、将来の SDS の拡張に役立つ可能性があります。拡張操作では必ずしもメモリの再割り当てが必要ではありません。

SDS 構造の buf バイト配列はバイナリ セーフであり、文字だけでなくバイナリ データも保存できます。

SDS は C 文字列の規則を保持し、データの末尾をヌル文字 '\0' に設定します。SDS がこの仕様を保持する理由は、C 文字列関数ライブラリの一部の関数を再利用できるためです。文字列の追加など。

4. 文字列のさらなる最適化

Redis 文字列の 3 つのエンコーディング:

int は 8 バイトの長整数 (long、2^63-1) embstr、embstr 形式を格納します。 SDS (Simple Dynamic String) raw、生の形式の SDS、44 バイトを超える長い文字列を格納します

int 型は数値を参照し、raw と embstr は両方とも表します 文字列間の類似点と相違点は何ですか? 以下で分析してみましょう。

図は 2 つの違いを示しており、embstr は redisObject と SDS を連続した 64 バイト領域に保存するため、必要なメモリ割り当ては 1 つだけであることがわかります。 raw の場合、SDS と redisObject を分離するには 2 つのメモリ割り当てが必要となり、より多くのメモリ領域が必要になります。

embstr は 3.2 で sdshdr8 と呼ばれる構造を使用していることがわかります。この構造では、メタデータには 3 バイトのみが必要ですが、Redis には 8 バイトが必要です。つまり、合計 64バイトから redisObject (16 バイト) を差し引いた後、SDS の元の情報を差し引くと、最終的な実際のコンテンツは 44 バイトと 39 バイトになります。

文字列が 44 バイト以下の場合、Redis は埋め込み文字列作成メソッドを使用して、メモリ割り当てとメモリの断片化を削減します。

次の図は、埋め込み文字列を作成する createEmbeddedStringObject のプロセスを示しています。

つまり、Redis は設計上、連続した文字列を認識することを覚えておいてください。 . メモリ空間には、redisObject 構造体と SDS 構造体をコンパクトにまとめて配置します。

このようにして、44 バイト以下の文字列の場合、メモリの断片化と 2 つのメモリ割り当てのオーバーヘッドを回避できます。

SDS は Redis における効率的な文字列実装であり、自動拡張、バイナリ安全性、O(1) 長さの取得と変更などの利点があります。実際のアプリケーションでは、SDS は効率的な文字列操作を実現し、バッファ オーバーフローなどの一般的な文字列操作の問題を回避するのに役立ちます。 SDS の内部構造と実装原理を深く理解することで、Redis の基礎となるメカニズムをより深く理解し、Redis アプリケーションの機能をさらに向上させることができます。

以上がRedis で SDS の単純な動的文字列問題を解決する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。