Redisが深く解析したデータ構造

Redis                 ，          （string object），          、    （list object）、    （hash object）、    （set object）       （sorted set object）   。         。

一、単純な動的文字列
1、定義

 Redis3.2  ，sds   5   ，5               。    sds.h    ，    

typedef char *sds;

 //sdshdr5        
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /*     type,           */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /*        */
    uint8_t alloc; /*         ，           */
    unsigned char flags; /*     type,           */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; 
    uint16_t alloc;
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; 
    uint32_t alloc; 
    unsigned char flags;
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len;
    uint64_t alloc;
    unsigned char flags;
    char buf[];
};

2、SDSとC言語文字列の区別と改善
2.1文字列長を取得する複雑さは定数レベル

C                   ，        O(N)。 SDS         len。            ，       。

2.2バッファオーバーフローの回避

C         ，                  ，          。 SDS          alloc            ，        。      ，SDS      。

2.3文字列変更時のメモリ再割り当て回数を減らす

C                      。SDS       、               。              。

2.4バイナリセキュリティ

C           ，         ，        、         。Redis buf             ，        。SDS   len          ，       。

二、チェーン時計
1、定義

               ， Redis   ，     、     、   、   ，       。      adlist.h ，    ：

//      
typedef struct listNode {
    //   
    struct listNode *prev;
    //   
    struct listNode *next;
    //   
    void *value;
} listNode;
//     
typedef struct listIter {
    //      
    listNode *next;
    //    
    int direction;
} listIter;
//    
typedef struct list {
    //     
    listNode *head;
    //     
    listNode *tail;
    //       
    void *(*dup)(void *ptr);
    //       
    void (*free)(void *ptr);
    //       
    int (*match)(void *ptr, void *key);
    //    
    unsigned long len;
} list;

2、Redisチェーンテーブルの特性

  ：      prev next  ，                      O（1）。
  ：     prev        next     NULL，       NULL   。
          ：  list   head   tail  ，                     O（1）。
        ：    list   len    list           ，                O（1）。
  ：      void*        ，      list   dup、free、match                ，                  。

三、辞書

  ，      （symbol table）、    （associative array）   （map），          （key-value pair）       。
   Redis        ，  Redis                  ，      、 、 、                 。           ，              ，               ，                    ，Redis                。

1、定義

Redis              ，                 ，                     。      dict.h   ，    ：

1.1、ハッシュテーブルノード

//     
typedef struct dictEntry {
    //   
    void *key;
    //   
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    //          
    struct dictEntry *next;
} dictEntry;

key           ， v            ，              ，     uint64_t  ，      int64_t  。next                ，                       ，        （collision）   。

1.2型特定関数

//      
typedef struct dictType {
    //       
    uint64_t (*hashFunction)(const void *key);
    //       
    void *(*keyDup)(void *privdata, const void *key);
    //       
    void *(*valDup)(void *privdata, const void *obj);
    //       
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    //       
    void (*keyDestructor)(void *privdata, void *key);
    //       
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

  dictType                     ，Redis                    。

1.3ハッシュ表

//     
typedef struct dictht {
    //     
    dictEntry **table;
    //     
    unsigned long size;
    //     ，    size-1，       
    unsigned long sizemask;
    //          
    unsigned long used;
} dictht;

1.4辞書

//Redis      
typedef struct dict {
    //      ， dictType  
    dictType *type;
    //    
    void *privdata;
    //   
    dictht ht[2];
    //rehash  ， rehash     ，  -1
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    //        
    unsigned long iterators; /* number of iterators currently running */
} dict;

type   privdata             ，           ：
type       dictType     ，  dictType                     ，Redis                    。
 privdata                       。

1.5辞書の反復器

 //           1    ，       dictAdd, dictFind   。  
 //        ，    dictNext()  
typedef struct dictIterator {
    dict *d;
    long index;
    int table, safe;
    dictEntry *entry, *nextEntry;
    //  fingerprint       
    long long fingerprint;
} dictIterator;

ハッシュアルゴリズム