Redis の底層 C 言語
データ構造#
動的文字列 SDS#
Redis は C 言語の String を使用していません。なぜなら、実際には文字配列だからです。
例:
char* s="hello" は {'h', 'e', 'l', 'l', 'o', '\0'} です。
そのため、Redis は新しい文字列構造を構築しました。これを簡単動的文字列 Simple Dynamic String と呼び、略して SDS とします。
ここでの読み取りは '\0' に基づいていません。これは C 言語に合わせるためで、実際には len を使用しています。
1M 未満のときは迅速にメモリを割り当て、1M 以降は間隔を空けて申請します。メモリの消費は非常に大きいことに注意してください。
バイナリセーフとは、len に基づいて読み取ることを指し、中間に '\0' が現れても突然停止しないことを意味します。
IntSet#
IntSet は Redis のセットコレクションの実装方法の一つで、整数配列に基づいて実装されており、可変長や順序性などの特性があります。
encoding は各要素が占めるサイズを決定します。ここでは 16 ビット、つまり 2 バイトです。length は配列内に格納される要素の数を決定します。
もし 16 のエンコーディング方式で、エンコーディング方式を超える要素を追加すると、要素を正しい位置に逆順でコピーします（逆順は上書きしないためです）。その後、新しい要素を追加し、最後に Header の encoding と length を変更します。
IntSet は特別な整数配列と見なすことができ、いくつかの特徴を持っています：
- Redis は IntSet 内の要素が一意であり、順序があることを保証します。
- タイプアップグレードメカニズムを持ち、メモリ空間を節約できます。
- 基本的に二分探索方式を使用して検索します。
Dict#
Dict はキーと値の関係を持ち、ハッシュテーブルのサイズは常に $2^n$ です。used は size を超える可能性があり、その場合は必ず 1 つのバケットが連結リストに退化します。
union はその中の任意の一つを指します。
sizemask = size - 1、二進数で n 個の 1 です。
実際の構成
拡張
Dict の HashTable は配列と連結リストを組み合わせているため、データが多すぎてデータの衝突を解決するために、上に $2^n$ に拡大します。
収縮
削除するたびに loadFactor < 0.1 をチェックし、used の上に $2^n$ に収縮します。最小は 4 です。
再構築
拡張でも収縮でも再構築が関与し、size と sizemask を変更するため、rehash が必要です。これが dict に ht [2] が必要な理由で、一つは使用中、もう一つは空です。
拡張再構築の例
データ量が非常に大きい場合、一度に再構築を完了することはできないため、実際には漸進的なハッシュで、徐々に移行します。以前のデータは ht [0]/ht [1] に存在する可能性があるため、新しいデータは ht [1] に追加され、ht [0] は減少するだけです。
ZipList#
ZipList は特別な「双方向連結リスト」で、一連の特別にエンコードされた連続メモリブロックで構成されています。任意の一端でプッシュ / ポップ操作を行うことができ、時間計算量は O (1) です。
サイズ
前のエントリの占有長さを通じて前のエントリの開始アドレスを取得し、逆順に走査できます。構造内の長さを計算することで次のエントリの開始アドレスを取得し、順方向に走査できます。
注意：Redis ではここでリトルエンディアンを使用しています。
文字列型
整数型 0-12 は content を省略し、直接 encoding の後 4 ビットに数値を保存できます。
ZipList の連鎖更新問題#
主な問題は、前のエントリの長さを記録する prevlen フィールドが、長さが 254 バイト以上になると 1 バイトから 5 バイトに変わり、次のエントリの prevlen が連鎖更新される可能性があることです。
ZipList にエントリ 1 を挿入または変更して 254 バイト以上にすると、この時エントリ 1 の後のエントリ 2 の prevlen フィールドは 1 バイトから 5 バイトに変更され、エントリ 1 の新しい長さを記録する必要があります。
この変更により、エントリ 2 の後のエントリ 3 も prevlen3 フィールドを変更してエントリ 2 の変更後の新しい長さを記録する必要があり、極端な場合、各エントリの prevlen フィールドが 1 バイトから 5 バイトに変わるときに 254 バイト以上になると、一連の連鎖更新が発生し、挿入 O (1) が O (n) に退化します。
なぜ 254 バイト以上でなく 255 バイトで prevlen が 5 バイトになるのか？
prevlen は 8 ビットで、0~255 を表すことができますが、255 は 0xff で zlend 特殊マークが占有され、圧縮リスト ZipList の末端を示します。そして prevlen はちょうどエントリの開始であり、255 で区切ると zlend 終了符と衝突します。
ZipList 特性
- 圧縮リストは連続メモリ空間の「双方向連結リスト」と見なすことができます。
- リストのノード間はポインタで接続されるのではなく、前のノードと現在のノードの長さを記録してアドレス指定され、メモリ使用量が低くなります。
- リストデータが多すぎて連結リストが長くなると、クエリ性能に影響を与える可能性があります。
- 大きなデータを追加または削除する際に連続更新問題が発生する可能性があります。
QuickList#
ZipList の問題：
- 前後の連結リストポインタを保存するには 16 バイトが必要で、ZipList は非常に多くのメモリを節約しますが、連続メモリ空間を使用する必要があり、メモリの申請効率が低いです。ZipList の長さやエントリのサイズを制限します。
- 大量のデータを保存する必要があり、ZipList の最適な保存上限を超えます。複数の ZipList のスライスを作成して保存します。
- データが分割されすぎて管理や検索が不便になります。QuickList 双方向連結リストを導入し、ノードが ZipList を記録します。
設定項目 list-max-ziplist-szie=-2 はデフォルトで ZipList のメモリ使用量が 8kb を超えないようにします。
ノードを圧縮するかどうかの設定項目、つまり両端の圧縮されていないノードの数は、頻繁に使用される両端ノードと中間ノードがあまり使用されないことを意味します。
ここでは両端にそれぞれ 1 つのノードが圧縮されていないため、中間の 2 つの ZipList が再エンコードされました。
QuickList 特性：
- ノードが ZipList の双方向連結リストです。メモリの断片化が多く、連続的な占有が少ないです。
- ノードは ZipList を採用し、従来の連結リストのメモリ使用問題を解決します。ZipList はメモリを節約します。
- ZipList のサイズを制御し、連続メモリ空間の申請効率の問題を解決します。分割された ZipList は、連続した大きなメモリを必要としません。
- 中間ノードは圧縮でき、さらにメモリを節約します。
SkipList#
スキップリスト SkipList はまず連結リストです。
- 要素は昇順に並べられます。
- ノードは複数のポインタを含む可能性があり、ポインタのスパンは異なります。これにより、1 つずつ走査するよりも速くなります。最大で 32 個のポインタを許可します。
後方ポインタ backward、前方ポインタは level [] 配列を使用し、少なくとも 1 つのスパンポインタがあり、迅速に前に飛び、徐々に後ろに探索して正しいノードに到達できます。
検索時には高いレベルから下に検索し、二分探索のように、空間を時間で交換し、あるスパン後のノードを事前に保存します。
SkipList 特性：
- スキップリスト SkipList は双方向連結リストであり、各ノードは score と element を含みます。
- ノードは score 値でソートされ、score 値が同じ場合は element の辞書順でソートされます。
- 各ノードは多層ポインタを含むことができ、層数は 1 から 32 の間のランダムな数です。
- 異なる層のポインタは次のノードへのスパンが異なり、層が高いほどスパンが大きくなります。
- 増減改査の効率は赤黒木と基本的に一致しますが、実装はより簡単です。
RedisObject#
Redis の任意のデータ型のキーと値は RedisObject にカプセル化され、Redis オブジェクトとも呼ばれます。
type、encoding、lru は合計 32 ビット、4 バイト；refcount は 4 バイト；*ptr は 8 バイトで、RedisObject のヘッダーは 16 バイトを占めます。
例えば String 型では、1 つの key-value が 1 つの RedisObject ヘッダーを消費し、かなりのスペースを占めます。
エンコーディング方式 encoding
5 種類のデータ型#
では BitMap、HyperLogLog はどうでしょうか？
これらの派生データ構造は実際には String というデータ構造に基づいて実装されており、新しいタイプではありません。
また、GEO は SortedSet に基づいています。
String#
String は Redis で最も一般的なデータストレージタイプです。
String RAW エンコーディング#
String の基本的なエンコーディング方式は RAW で、簡単動的文字列 SDS に基づいて実装され、ストレージ上限は 512mb です。
String EmbStr エンコーディング#
もし保存される SDS の長さが 44 バイト以下であれば、EMBSTR エンコーディングが採用され、この時 RedisObject ヘッダーと SDS は連続した空間になります。メモリを申請する際には、メモリ割り当て関数を一度呼び出すだけで済み、効率が向上します。Redis のメモリ申請アルゴリズムに関連しています。要するに、SDS の長さが 44 バイトであれば、ヘッダー + SDS はちょうど 64 バイトになり、メモリの断片化が発生しません。
String INT エンコーディング#
もし保存される文字列が整数値で、サイズが LONG_MAX の範囲内であれば、INT エンコーディングが採用され、データは RedisObject の ptr ポインタ位置に直接保存され、ちょうど 8 バイトになります。もう SDS は必要ありません。
String raw、embstr、int エンコーディング#
List#
List データ型は両端の要素を操作でき、底層は LinkedList + ZipList を組み合わせた QuickList データ構造を使用しています。
List 構造
Set#
Set データ型は単一の集合であり、順序を保証せず、要素の一意性を保証します。交差、和、差を求めることができます。クエリにおいて SISMEMBER は非常に頻繁に使用されるため、HashTable を選択します。
HT エンコーディング Dict を使用し、key に要素を、value はすべて null に設定します。
全ての整数を保存し、要素数が set-max-intset-entries を超えない場合、Set は IntSet エンコーディングを使用してメモリを節約します。
もし IntSet を使用して最大数を超えたり、非整数を追加したりすると、HT エンコーディング Dict に変換されます。
IntSet エンコーディングの Set
HashTable エンコーディングの Set
ZSET#
ZSet は SortedSet であり、各要素には score 値と member 値があり、score 値に基づいてソートできます。member の一意性があり、member のスコアを照会できます。member と score の関係はキーと値のペアであり、ZSet はキーのストレージ、キーの一意性、ソート可能性を要求するため、SkipList と HashTable を選択できます。
SkipList は score に基づいてソートされ、キーのストレージとソート可能性を満たしますが、member に基づいて score を照会すると連結リストに退化し、member の一意性も便利ではありません。
HashTable は key-value を member-score に設定すればよいですが、score に基づいてソートする機能を満たすことはできません。
そのため、両方のデータ構造を使用し、Dict は member の一意性を保証し、ZSet はソート可能性と範囲クエリを保証します。
ZSet は Dict と SkipList を組み合わせて使用し、エンコーディングは SKIPLIST に設定されます。
しかし、要素が少ない場合、Dict + ZipList の組み合わせは非常にメモリを占有し、あまり明確ではないため、以下の条件を満たす場合、ZSet は ZipList 構造を選択してメモリを節約します。
- 要素数が zset_max_ziplist_entries より少ない、デフォルト値は 128 です。
- 各要素が zset_max_ziplist_value バイトより小さい、デフォルト値は 64 です。
初期値を作成する際に、初期値がこの 2 つの条件を同時に満たす場合、ZipList を使用します。
要素を追加する際、ZipList であれば、SkipList + HashTable 構造に変換するかどうかを判断します。
しかし、ZipList は ZSet の 3 つの要件を満たしません。なぜ小さなデータや小さなデータ量で ZipList を使用できるのでしょうか？
ビジネスロジックを使用してソート、キーと値のペアのソートをシミュレートし、連続メモリ空間を持ち、element/member が前に、value/score が後ろに配置されます。
Hash#
Hash 構造は ZSet 構造に似ており、キーのストレージ、キーの一意性が要求され、キーに基づいて値を取得できます。必然的に hashTable です。
ZSet との違い
- ZSet のキーは member で、値は score です。Hash のキーと値は任意の値です。
- ZSet は score に基づいてソートされる必要があります。Hash はソートを必要としません。
Hash 構造はデフォルトで ZipList エンコーディングを使用し、ZipList では隣接する 2 つのエントリがそれぞれ field と value を保存します。
データ量が多い場合、Hash 構造は HT エンコーディング、つまり Dict に変換されます。トリガー条件は 2 つあります。
- zipList 内の要素数が hash-max-ziplist-entries のデフォルト 512 を超えた場合。
- ZipList 内の任意のエントリのサイズが hash-max-ziplist-value のデフォルト 64 バイトを超えた場合。
いずれかの条件を破ると HT エンコーディングに変換されます。
Hash のソースコードでは、初期化時にデフォルトで ZipList に初期化されることがわかります。
次に、追加時に HT エンコーディングに変換するかどうかを判断し、要素のサイズに基づいて判断します。
最後に追加を行い、追加時に等しいかどうかを判断し、ZipList であれば、挿入後に長さをチェックし、超えた場合は HT エンコーディングに変換します。
この文は Mix Space によって xLog に同期更新されました。元のリンクは https://blog.0xling.cyou/posts/redis/redis-3