Redisの高度なテクニック：底層ストレージデータ構造とメモリ最適化

はじめに

Redisは高性能なキャッシュミドルウェアとして知られており、他のキャッシュシステムと比較して多様なデータ構造をサポートしています。String、List、Set、SortedSet、HashなどがRedisが外部でサポートするデータ構造ですが、内部でのストレージ方法は伝統的な理解とは異なります。Redisは各データ構造タイプに対して最適化を行っており、異なるデータに応じて異なるデータ構造を使用してストレージを実現しています。

Redisオブジェクト（RedisObject）

Redis内のすべてのキーは文字列ですが、すべての値はString、List、Set、SortedSet、Hashといった構造で直接保存されるわけではありません。代わりにRedisObjectオブジェクトとしてカプセル化されます。Redisは巨大な<String, RedisObject>コレクションのような存在です。

Redisが新しいキー値ペアを作成するたびに、2つのRedisObjectオブジェクトが生成されます。一つはキーのオブジェクト、もう一つは値のオブジェクトです。

RedisObjectのデータ構造は以下の通りです：

  • type: 値が表すデータタイプを示し、String、List、Set、SortedSet、Hashなどの5種類の値を取ります
  • encoding: 値のエンコーディング形式を示し、int、embstr、raw、ziplist、linkedList、ht、intset、skipListなどを含みます
  • refCount: 値オブジェクトの参照カウントを示し、refCountが0になると回収可能となります
  • ptr: 底層データへのポインタ
  • lru: 最後にアクセスされた時間

異なるタイプのデータ構造は複数のエンコーディング方式に対応しており、異なるエンコーディング方式を採用することでメモリ最適化を実現できます。また、同じデータタイプでも異なるエンコーディング方式がメモリ最適化のために使用される場合があります。

Redisのエンコーディングメカニズム

Redisは異なるデータ構造タイプに対して複数のエンコーディング方式を採用しています：

エンコーディング方式 説明
int long型の整数
embstr embstrエンコーディングされた簡易動的文字列
raw 簡易動的文字列
ziplist 圧縮リスト
linkedlist 双方向リンクリスト
intset 整数セット
skiplist スキップリスト
hashtable 辞書

ziplistは圧縮されたリストで、データを保存するメモリ空間は連続的であり、占有スペースは比較的少ないですが、データ処理には時間がかかります。これは時間を犠牲にしてスペースを節約する方式です。

主なデータ構造の異なる状況におけるエンコーディング方式は以下の通りです：

データタイプ エンコーディング方式 使用条件
String int 値が8バイトの整数タイプである場合
embstr 長さが39バイト未満の文字列
raw 長さが39バイトを超える文字列
List ziplist List要素数がlist-max-ziplist-entries（デフォルト512個）未満であり、
すべての要素値のサイズがlist-max-ziplist-value（デフォルト64バイト）未満の場合
linkedlist ziplistの条件を満たさない場合、LinkedListを使用し、ziplistにダウングレードすることはできません
Set intset Set要素数がset-max-intset-entries（デフォルト512個）未満であり、
すべての要素が整数タイプである場合
hashtable intsetの条件を満たさない場合、hashtableを使用し、intsetにダウングレードすることはできません
SortedSet ziplist 有序集合要素数がzset-max-ziplist-entries（デフォルト512個）未満であり、
すべての要素値のサイズがzset-max-ziplist-value（デフォルト64バイト）未満の場合
skiplist ziplistの条件を満たさない場合、skiplistを使用し、ziplistにダウングレードすることはできません
Hash ziplist ハッシュ表要素数がhash-max-ziplist-entries（デフォルト512個）未満であり、
すべての要素値のサイズがhash-max-ziplist-value（デフォルト64バイト）未満の場合
hashtable ziplistの条件を満たさない場合、hashtableを使用し、ziplistにダウングレードすることはできません

Redisは異なるデータ状況に応じて異なるエンコーディング方式を採用し、メモリ占有が小さいデータ構造を使用してメモリ最適化の効果を達成します。

2.1 文字列エンコーディング方式

1. intエンコーディング

intエンコーディングは文字列の値にのみ使用され、文字列の値が整数タイプである場合に使用されます。

2. embstrエンコーディング

embstrは簡易動的文字列（SDS）の一種のエンコーディングで、比較的短い文字列を保存するために特化されています。Redisはデータを保存する際にRedisObjectを作成し、RedisObjectにはデータへのポインタを指すptr属性があります。文字列データを保存するデータ構造はSDS、つまりsdshdrデータ構造です。

embstrエンコーディング方式を使用する場合、RedisObjectとsdshdrの両方に連続したメモリ空間を割り当てるため、メモリ割り当て関数を一度だけ呼び出します。

また、embstrエンコーディングされた文字列は読み取り専用であり、一度変更されるとrawエンコーディング方式にアップグレードされます。

3. rawエンコーディング

rawも簡易動的文字列（SDS）の一種のエンコーディングで、文字列の長さが長い場合に使用されます。rawエンコーディング方式とembstrエンコーディング方式の違いは、rawが一度のメモリ割り当て関数のみを必要とするのに対し、rawはRedisObjectとsdshdrそれぞれにメモリ割り当て関数を別々に呼び出す必要がある点です。

rawとembstrは文字列を保存する効果は完全に同じですが、rawはメモリ割り当て時により多くのメモリを申請し、メモリ解放時にもembstrより多くの解放が必要です。

2.2 リストエンコーディング方式

リストオブジェクトのエンコーディング方式にはziplistとlinkedlistの2種類があります。

ziplistエンコーディングの底層は圧縮リストによって実装され、各ノードはリストの要素を保存します。リスト値のRedisObjectオブジェクトのptrはziplistオブジェクトを指します。

linkedlistエンコーディングの底層は双方向リンクリストによって実装され、各ノードはリストの要素を保存します。リスト値のRedisObjectオブジェクトのptrはlinkedlistオブジェクトを指します。

リストの要素が以下の2つの条件を同時に満たす場合にのみziplistを使用し、それ以外の場合はlinkedlistを使用します：

  1. リストの要素数が512個を超えないこと（カスタマイズ可能な値）
  2. リスト内のすべての要素のサイズが64バイト未満であること（カスタマイズ可能な値）

2.3 集合エンコーディング方式

集合のエンコーディング方式にはintsetとhashtableの2種類があります。

intsetエンコーディングの底層実装は整数セットであり、集合内に保存されるデータはすべて整数タイプです。

hashtableエンコーディングの底層実装は辞書であり、集合のすべての要素は辞書のキー値ペアのキーに存在し、辞書のすべてのキーの値はNULLです。

集合の要素が以下の2つの条件を同時に満たす場合にintsetを使用し、それ以外の場合はhashtableを使用します：

  1. 集合の要素数が512個を超えないこと（カスタマイズ可能な値）
  2. 集合のすべての要素が整数タイプであること

2.4 有序集合エンコーディング方式

有序集合のエンコーディング方式にはziplistとskiplistの2種類があります。有序集合の要素には2つの属性があります。一つは具体的な値、もう一つは並べ替えに使用されるスコアです。

ziplistエンコーディングの底層は圧縮リストであり、各有序集合の要素は2つの連続した圧縮リストのノードで保存され、一つは要素の値を保存し、もう一つは要素のスコアを保存します。

また、圧縮リストは集合要素をスコアに基づいて並べ替え、スコアが小さいものはリストの先頭に近い位置に、スコアが大きいものはリストの末尾に近い位置に配置されます。

skiplistエンコーディングの底層はzsetによって実装され、zsetは同時に辞書とスキップリストを含みます。

有序集合の要素が以下の2つの条件を同時に満たす場合にziplistを使用し、それ以外の場合はskiplistを使用します：

  1. 有序集合要素数がzset-max-ziplist-entries（デフォルト512個）未満であり、
  2. すべての要素値のサイズがzset-max-ziplist-value（デフォルト64バイト）未満である場合

2.5 ハッシュオブジェクトエンコーディング方式

ハッシュオブジェクトのエンコーディング方式はziplistとhashtableの2種類に分かれます。

ziplistエンコーディングの底層実装も圧縮リストであり、ハッシュオブジェクトが新しいキー値ペアを保存する場合、まずキーのノードを圧縮リストの末尾に挿入し、次に値のノードをリストの末尾に挿入します。したがって、各キー値ペアのキーと値は2つの連続した圧縮リストのノードを生成し、リスト内に連続して保存されます。後から挿入されたノードはリストの末尾に配置されます。

hashtableエンコーディングの底層実装は辞書構造であり、ハッシュオブジェクトのキー値ペアは辞書内のキー値ペアに対応し、キーと値は文字列構造です。

ハッシュオブジェクトの要素が以下の2つの条件を同時に満たす場合にのみziplistを使用し、それ以外の場合はhashtableを使用します：

  1. ハッシュが保存するキー値ペアの数量が512個を超えないこと（カスタマイズ可能な値）
  2. ハッシュが保存するすべてのキー値ペアの値のサイズが64バイトを超えないこと（カスタマイズ可能な値）

Redisの底層データ構造

3.1 簡易動的文字列（SDS）

RedisはC言語で実装されていますが、C言語の文字列を使用せず、代わりに簡易動的文字列（SDS）というデータ構造を使用して文字列を保存しています。これには文字列タイプのキーと値が含まれます。

SDSの定義は以下の通りです：

struct sdshdr{
    /** buf配列が使用済みのバイト数を記録 */
    int len;
  
    /** buf配列が未使用のバイト数を記録 */
    int free;

    /** バイト配列、文字列データを保存するために使用 */
    char buf[];
}

SDSはバイト配列に加えて、使用済みと未使用のバイト数を記録する2つのintタイプの変数を持ちます。これにより文字列の長さを簡単に取得できます。

また、C言語の文字列は自身の長さを保存しないため、底層実装はN+1文字長の配列（1文字のスペースは終了マークを表すNULL文字を保存）であり、文字列が変更されると、増加または短縮のいずれであってもメモリ再割り当てが必要になります。メモリ再割り当てを行わない場合、文字列が増加するとメモリオーバーフローが発生し、短縮するとメモリリークが発生するなど、メモリに不都合な結果が生じます。

SDSはC言語文字列の実装の基礎の上で、2つの最適化戦略を追加しています。分别是空间预先分配和空间惰性释放（スペースの事前割り当てと遅延解放）です。

1. スペースの事前割り当て戦略

SDSのlen長さが1MB未満の場合、事前に割り当てられたスペースは使用済みのスペースと同じサイズです。たとえば、文字列が増加した後のlen長さが100バイトの場合、拡張後のSDSバッファの総長さは201バイトが割り当てられ、そのうち100バイトが使用され、残りの100バイトが空きスペースとして確保されます。後続の文字列が再び増加する場合、メモリ再割り当てが必要ない可能性があります。

SDSのlen長さが1MBを超える場合、事前に割り当てられたスペースは常に1MBのスペースを保持します。たとえば、文字列の長さが30MBの場合、拡張後のスペースサイズは31MBとなり、残りの1MBが後続の文字列増加時に使用されるように確保されます。

したがって、メモリ事前割り当て戦略により、文字列がN回増加した後、最大でN回のメモリ再割り当てが発生するだけであり、C言語文字列の必然的なN回のメモリ再割り当てではなく、一部のメモリスペースを犠牲にすることでメモリ再割り当てによる効率向上の結果を得ることができます。これはスペースを時間に変換する方式です。

2. スペースの遅延解放戦略

スペースの遅延解放戦略とスペースの事前割り当て戦略の目的は同じで、メモリ再割り当ての回数を減らすためにあります。文字列が短縮された後、空きメモリスペースをすぐに解放するのではなく、freeの値を変更して空きスペースがあることを示すだけで、現在の空きスペースをすぐに解放しません。これにより、後続の文字列増加時にメモリ再割り当てが不要になります。

たとえば、元のSDS値が「ABCDE」で、free=0、len=6の場合、文字列値を「ABC」に変更すると、余分なスペースを解放するのではなく、free=2と変更して2バイトの空きスペースがあることを示します。

もちろん、SDSは空きスペースを明示的に解放するAPIも提供しているため、過剰な空きスペースによるメモリリークの問題を心配する必要はありません。

SDSがC言語文字列と比較して持つ利点をまとめると：

  1. O(1)の複雑度で文字列の長さを取得する
  2. バッファオーバーフローの問題を回避する
  3. 文字列の変更時に発生するメモリ再割り当ての回数を大幅に削減する
  4. バイナリセーフであり、SDSバッファは任意の形式のバイナリデータを保存でき、C文字列のテキストデータのみを保存できるのとは異なります
  5. SDSは一部のC文字列の関数と互換性があり、コードの再利用率を向上させます

3.2 リンクリスト

Redis内のリンクリストの実装は他の高級言語のリンクリストの実装ロジックと基本的に一致しており、主にリンクリストノードとリンクリストクラスで構成されています。定義は以下の通りです：

/** リンクリストノード構造定義 */
struct listNode{
   /** 前方ノード */
   struct listNode *prev;

   /** 後方ノード */
   struct listNode *next;

   /** ノードの値 */
   void *value;
}
/** リンクリスト構造定義 */
struct list{
   /** 先頭ノード */
   listNode *head;

   /** 末尾ノード */
   listNode *tail;

   /** ノード数 */
   unsigned long len;
}

まとめ：

  1. リンクリストは主にRedisのリストキー、パブリッシュ/サブスクライブ、スロークエリ、モニターなどで使用されます
  2. 各リンクリストノードには前方ノードと後方ノードのポインタが含まれているため、双方向リンクリストです
  3. 先頭ノードの前方ノードと末尾ノードの後方ノードは空であるため、リンクリストは循環リンクリストではありません

3.3 辞書

辞書はキー値ペアを保存する抽象データ構造であり、Java言語ではMapとして実装されていますが、C言語にはMapデータ構造がないため、Redisは辞書データ構造を独自に実装する必要があります。JavaのMapと同様の機能を持ちます。

Redisのデータベース底層は辞書によって実装されており、Redisのキーと値の操作は実際には辞書のキーと値の操作に基づいています。また、Redisのハッシュデータ構造の底層も辞書によって実装されています。

3.4 スキップリスト

スキップリスト（SkipList）は順序付きデータ構造であり、複数のノードが同時に他の複数のノードのポインタを維持することで、ノードへの高速アクセスを実現します。

スキップリストはRedisの有序集合の底層実装方案の一つであり、Redisの有序集合のデータ量がデフォルトの512個に達するか、または特定のキーの値のサイズが64KBに達すると、スキップリストを使用して実装されます。

同じスキップリスト内では、各ノードのスコア値は同じかもしれませんが、ノードのメンバーオブジェクトは一意でなければなりません。スコアに基づいて優先的に並べ替えられ、スコアが同じ場合はメンバーオブジェクトの値に基づいて並べ替えられます。

3.5 整数セット

整数セット（intset）はRedisが整数タイプの集合データ構造を保存するために使用されます。定義は以下の通りです：

typedef struct intset{
    
     /** エンコーディング方式 */
     unint32_t encoding;

     /** 集合内の要素数 */
     unint32_t length;

     /** 整数配列 */
     int8_t contents[];
}intset;

lengthは整数セットが保存するデータの個数を保存し、contentsは整数データを保存し、小さい順に順序付けられて保存されます。

contentsはint8_tタイプの値として定義されていますが、実際にはcontentsに保存されるデータが必ずint8_tタイプであるとは限りません。代わりにencodingの値によって決定されます。encodingはINTSET_ENT_INT8、INTSET_ENT_INT16、INTSET_ENT_INT32、INTSET_ENT_INT64の4種類をサポートしており、contentsはint8_t、int16_t、int32_t、int64_tタイプのデータを保存できます。contentsはデフォルトでint8_tタイプを使用していますが、int16_tタイプのデータをcontentsに保存する必要がある場合、contentsはint16_tタイプの配列にアップグレードされ、同様に保存するデータが大きくなるにつれて、contentsはint32_tおよびint64_tタイプにアップグレードされることもできます。

これにより、メモリを節約することができます。集合内に保存されるデータ値が小さい場合は、メモリ占有の小さいデータ構造で保存し、数値の大きなデータ構造を保存する必要がある場合にのみアップグレードします。しかし、contentsは小さいものから大きいものへアップグレードできますが、大きいものから小さいものへダウングレードすることはできません。

まとめ：

  1. 整数セットは集合キーの底層実装の一つです
  2. 整数セットの底層は順序付きで重複のない配列実装です
  3. 配列に保存されるデータタイプが変化するとアップグレード操作が行われ、アップグレードメカニズムはメモリスペースを節約できますが、ダウングレードは行われません

3.6 圧縮リスト

圧縮リスト（ziplist）はRedisのリストキーとハッシュキーの底層実装方式の一つであり、リストまたはハッシュキーのキー数量がデフォルトの512個未満であり、各キーの値のサイズが比較的小さい場合（64KB）、ziplistを使用して底層データストレージを実装します。

圧縮リストは名前が示すようにメモリが圧縮されたリストであり、一連の特殊なエンコードされた連続したメモリブロックで構成される順序型データ構造です。メモリスペースを節約する目的で使用されます。

圧縮リストは任意の数のノードで構成されており、各ノードはバイト配列または整数を保存します。

1. 圧縮リストの構造

属性 占有バイト 説明
zlbytes 4 圧縮リストが占有するバイト数を記録し、圧縮リストのメモリ再割り当て時およびzlendの位置を計算する際に使用されます
zltail 4 末尾ノードが圧縮リストの開始アドレスから何バイト離れているかを記録し、オフセットを通じてリスト全体を走査せずにリスト末尾ノードのアドレスを特定できます
zllen 2 圧縮リストのノード数を記録します
entry 不定 圧縮リストの各ノード、ノードが占有するメモリサイズは保存する具体的なデータに依存します
zlend 1 特殊値0XFF、10進数の255、圧縮リストの終了マークを示します

2. 圧縮リストのノード

属性 値の範囲 説明
previous_entry_length 1バイトまたは5バイトを占有します。前のノードの長さが254バイト未満の場合、前のノードの長さを保存するために1バイトを使用します；
前のノードの長さが254バイトを超える場合、5バイトを使用し、第1バイトは0XFE（254）を固定して保存し、後の4バイトは前のノードの具体的な占有バイト数を保存します		 前のノードの占有バイト数
encoding 1バイトまたは2バイトまたは5バイトを占有します
contentがバイト配列を保存する場合、1、2、または5バイトを占有し、最上位2ビットの値は00、01、または10であり、他のビットは数値の長さを保存します；
contentが整数を保存する場合、1バイトを占有し、最上位2ビットの値は11であり、他のビットは整数の具体的なタイプおよび長さを保存します		 contentが保存するデータタイプおよび長さを記録します
content バイト配列または整数值 ノードが保存するデータ内容、タイプおよび長さはencodingによって保存されます

3. 連鎖更新のリスク

連鎖更新は、新しいノードを挿入するか、ノードを削除する際に、圧縮リストのメモリが連続的であるため、他のノードのメモリ再割り当てが必要になる可能性がある問題です。

たとえば、圧縮リストに現在4つのノードがあり、4つのノードの長さがすべて250～253の間である場合、254未満であるため、後続のノードのprevious_entry_length値は1バイトで保存するだけで済みます。

この時点でノード1の前に新しいノードを挿入し、新しいノードの長さが254バイトを超える場合、ノード1は5バイトを使用して新しいノードの長さ値を保存する必要があり、ノード1が占有するメモリスペースが4バイト増加するため、ノード1が占有するスペースも254バイトを超えることになります；

同様に、ノード1の長さの変化により、ノード2のprevious_entry_lengthが1バイトから5バイトに変更される必要があり、ノード2の長さも254バイトを超えることになり、同様に後続のノードにも影響が及びます。これが、新しいノードを挿入することによる連鎖更新の反応です。

連鎖更新のリスクは比較的大きいですが、実際の状況ではシナリオは比較的少なく、圧縮リスト内に複数の連続した占有バイト数が250～253の間のノードが存在する確率は低いため、連鎖更新のノードが多くない限り、全体のパフォーマンスに影響を与えることはありません。

まとめ：

  1. 圧縮リストは連続メモリの順序型データ構造であり、メモリを節約する目的で使用されます
  2. 圧縮リストはRedisのリスト、有序集合、およびハッシュの底層実装方式の一つです
  3. 圧縮リストは複数のノードで構成されており、各ノードは整数またはバイト配列を保存できます
  4. 圧縮リストにノードを挿入または削除すると、連鎖更新のリスクがありますが、発生確率は非常に低いです

タグ: redis データ構造 メモリ最適化 SDS スキップリスト

5月21日 12:36 投稿

ホットタグ

©2026 異端開発室