Redis の底層 C 言語
データ構造#
動的文字列 SDS#
Redis は C 言語の String を使用していません。なぜなら、実際には文字配列だからです。
例:
char* s="hello" は {'h', 'e', 'l', 'l', 'o', '\0'} です。
そのため、Redis は新しい文字列構造を構築しました。これを単純動的文字列 Simple Dynamic String と呼び、略して SDS とします。
ここでは '\0' に基づいて読み取るのではなく、実際には 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 を超える可能性があり、その場合は必ず一つのバケットが連結リストに退化します。
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 バイト以上で 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 は双方向リストであり、各ノードにはスコアと要素が含まれています。
- ノードはスコア値でソートされ、スコア値が同じ場合は要素の辞書順でソートされます。
- 各ノードは複数のレイヤーのポインタを含むことができ、レイヤー数は 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 であり、各要素にはスコア値とメンバー値があり、スコア値に基づいてソートできます。メンバーの一意性があり、メンバーのスコアを照会できます。メンバーとスコアの関係は、ZSet がキー値ストレージ、キーの一意性、ソート可能性を要求するため、SkipList または HashTable を選択できます。
スキップリストはスコアに基づいてソートされ、キー値ストレージとソート可能性を満たしますが、メンバーに基づいてスコアを照会すると連結リストに退化し、メンバーの一意性も便利ではありません。
HashTable では key-value をメンバー - スコアに設定するだけで済みますが、スコアに基づいてソートする機能を満たすことはできません。
そのため、両方のデータ構造を使用し、Dict がメンバーの一意性を保証し、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 のキーはメンバーで、値はスコアです。Hash のキーと値は任意の値です。
- ZSet はスコアに基づいてソートされる必要がありますが、Hash はソートを必要としません。
Hash 構造はデフォルトで ZipList エンコーディングを使用し、ZipList では隣接する 2 つのエントリがそれぞれフィールドと値を保存します。
データ量が大きくなると、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