『redis設計と実現』ノート

この本を読むときに役に立つと思うものを記録するのは、ばらばらかもしれません.(第1部)
文字列
redisの文字列の下位層は、単純な動的文字列simple-dynamic-stringとして実装される.

struct sdshdr{
    int len;     ，   ‘/0’
    int free;          
    char buf[];     
}

くうかんぜんわりあて
空間事前割り当ては、SDSの文字列成長動作を最適化するために使用される.

sdsを変更した後、lenが1 MB未満である場合、lenと同じサイズの未使用空間が割り当てられる.bufの長さはlen+buf+1

となる.

修正後、lendが1 MB以上である場合、1 MBの未使用空間が割り当てられる.bufの長さはlen+1MB+1byte

となる.
ふかっせいくうかんほうしゅつ
SDSを最適化するための文字列短縮操作

で短縮操作を行う場合、bufの長さを減らすことなく、短縮した部分をfreeに加える.

は、メモリの無駄な使用を心配することなく、実際に未使用のスペースを解放するAPIも提供します.
C文字列とSDSの比較
C文字列
SDS
取得文字列長複雑度O(n)
複雑度O(1)
APIは安全ではなく、バッファオーバーフローの可能性がある
APIセキュリティ
文字列の長さをN回変更するには、必ずN回のメモリ再割り当てが必要です.
文字列の長さをN回変更するには、最大N回のメモリ再割り当てが必要です.
テキストデータのみ保存
テキストまたはバイナリデータを保存できます
すべてのライブラリの関数を使用できます.
使用可能なセクション
チェーンテーブル
チェーンテーブルはredisに広く適用され、1つのリストキーに多くの要素が含まれている場合、またはリストに含まれる要素が比較的長い文字列である場合、redisはチェーンテーブルをリストキーの下位層として実現する.
とくせい

双方向、無環

にはヘッダー、テールポインタ

があります.

チェーンテーブル付き長さカウンタ

マルチステート、異なるタイプの値

を保存できます.
辞書
広く応用されている.データベース全体がkvデータベースであり、次にハッシュキーというデータ構造の最下位も辞書である.
ハッシュ表構造

typedef struct dictht {
    //      
    dictEntry **table;

    //      
    unsigned long size;

    //        ，       ，    size-1
    unsigned long sizemask;

    //           
    unsigned long used;
} dictht;

ハッシュテーブルノード構造

typedef struct dictEntry {
    void *key;

    union(
        void *val;
        uint64_tu64;
        int64_ts64;
    ) v;

    struvt dictEntry *next;
} dictEntry;

ディクショナリ構造

typedef struct dict {
    //       
    dictType *type;

    //     
    void *privdata;

    //    
    dictht ht[2];

    // rehash  ，  rehash     ，  -1
    int trehashidx;
} dict;

辞書はht[0]に保存され、ht[1]はハッシュテーブルをrehashするために使用される.MurmueHashアルゴリズムを使用します.配列+チェーンテーブルの方法でハッシュ競合を解決します.
rehash最適化-漸進的rehash
辞書テーブルが大きすぎると、rehashが一度に完了すると、データベースがしばらくサービスを停止します.手順は次のとおりです.

はht[1]割り当て空間

である.

インデックスカウンタ変数rehashidxを辞書に保持し、値を0

に設定する.

rehash期間中、辞書の追加削除、検索または更新操作が行われるたびに、ht[0]ハッシュテーブルのrehashidxインデックス上のすべてのキー値をht[1]に順次付け、完了するとrehashidx+1

になる.

は最終的にすべてht[1]にrehashし、rehashidxを-1にして完了を示す.ht[0]のハッシュテーブルをht[1]のハッシュテーブルに、ht[1]がnullを指す.

リストの圧縮
圧縮リストは、リストおよびハッシュの最下位実装の1つであり、1つのリストキーが少量のリスト項目のみを含み、小さな整数値または短い文字列である場合に使用されます.以下の2点を同時に満たし、圧縮チェーンテーブルを使用します.

リストオブジェクトが保持するすべての文字列の長さは、64バイトの

未満である.

リストオブジェクトが保存する要素の数は512個未満

である.
ジャンプテーブル
redisは,ジャンプテーブルを秩序化集合の下位実装の1つとして用い,クラスタノードにおける内部データ構造としても用いた.ネット上のホップテーブルデータ構造分析を参照できます.(個人感覚は二分の思想と一致し,秩序ある場合には複雑さを低減する)
set
集合データ構造は辞書によって実現され,集合の値は辞書のキーであり,対応する値はnullである.