Redis基礎知識----SDS(単純動的文字列)

以下のまとめは、redisソース4.0.9バージョンに基づいています。 1.redisの最下位記憶データ構造単純動的文字列（SDS）、チェーンテーブル、辞書、ジャンプテーブル、ツリー全体集合、圧縮リストなど2、redisのデータ構造オブジェクト文字列、リスト、ハッシュ、集合、秩序集合など

単純動的文字列(sds)SDSは、文字列の長さの違いによって5つの異なるデータ構造を実現し、ヘッダが文字列の長さを識別するために使用されるタイプとは異なり、主に構造体のサイズを小さくし、メモリを節約するために使用される.たとえば、32未満の文字列では、sdshdr 5構造体が使用されます.sdshdr 5構造体は、lenおよびallocの属性がなく、flagsの高さ5ビットを巧みに使用して文字列の長さを識別します.

 sdshdr5   ---->    <32 
 sdshdr8   ---->    <256 
 sdshdr16  ---->    < 2^16
 sdshdr32  ---->    < 2^32
 sdshdr64  ---->    < 2^64

基本的なデータ構造は次のとおりです.

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

lenは文字列の真の長さを表します.allocヘッダーとterminator以外の割当長を除外flags型は、構造体の実際のタイプを識別するbuf[]実際のデータsdshdr5データ構造

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};

文字列の拡張

/*
 *        SDS    
 *
 *     
 *      1. s:     SDS      
 *      2. addlen:            
 *
 *    
 *             sds，         sds    
 */
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    //       SDS         
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;

    /* Return ASAP if there is enough space left. */
    //             
    if (avail >= addlen) return s;

    len = sdslen(s);
    //  sds（       ，     ）                
    //           ，   void *sh
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    //                     2 
    //                   SDS_MAX_PREALLOC  
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    //          ，             
    type = sdsReqType(newlen);
    //   SDS_TYPE_5        （       ），             
    //               ，      SDS_TYPE_8  
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        //                         
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        //                       SDS      
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        //        
        s_free(sh);
        s = (char*)newsh+hdrlen;
        //      
        s[-1] = type;
        sdssetlen(s, len);
    }
    //           
    sdssetalloc(s, newlen);
    return s;
}

重要なポイント:1.SDSの記録長、O(1)は全長2を取得する.文字列の変更時にメモリが割り当てられる回数を減らします.メモリの事前割り当て、一定の長さの文字列を割り当て、拡張時に拡張に必要なlenがSDS_より小さい場合MAX_PREALLOCは、lenの2倍に拡大し、そうでなければSDS_を拡大するMAX_PREALLOC(1M)( #define SDS_MAX_PREALLOC (1024*1024) ).lenとallocで不活性な解放を実現し、文字列削除後、長さは変わらず、次回の使用に便利です.3.バイナリセキュリティ.空の文字で文字列の終わりを判断するのではなく、lenという属性で判断します.4.キャッシュのオーバーフローを防止します.文字列をマージする前に、現在の文字列の長さ、不足、拡張がチェックされます.ルールは2.