Redis源码阅读（二）底层数据结构

typedef struct redisObject {
    unsigned type:4;            // 对象的类型，字符串/列表/集合/有序集合/哈希表
    unsigned encoding:4;        // 编码的方式，Redis 为了节省空间，提供多种方式来保存数据
    unsigned lru:LRU_BITS;      // 缓存淘汰使用；淘汰的标准为：oversize & overtime
    int refcount;               // 引用计数；为优化内存，对数字字符串进行共享内存，引用计数方式管理
    void *ptr;                  // 数据指针，指向实际存储的某一种数据结构
} robj;

#define OBJ_STRING 0  /* 字符串对象*/
#define OBJ_LIST 1    /* 列表对象 */
#define OBJ_SET 2     /* 集合对象 */
#define OBJ_ZSET 3    /* 有序集合对象 */
#define OBJ_HASH 4    /* 散列表对象 */
#define OBJ_MODULE 5  /* 模块对象 */
#define OBJ_STREAM 6  /* 流对象 */

#define OBJ_ENCODING_RAW 0        /* Raw representation */
#define OBJ_ENCODING_INT 1        /* 编码为整数 */
#define OBJ_ENCODING_HT 2         /* 编码为散列表 */
#define OBJ_ENCODING_ZIPMAP 3     /* 编码为zipmap */
#define OBJ_ENCODING_LINKEDLIST 4 /* 不再使用：旧列表编码*/
#define OBJ_ENCODING_ZIPLIST 5    /* 编码为压缩列表 */
#define OBJ_ENCODING_INTSET 6     /* 编码为整数集合*/
#define OBJ_ENCODING_SKIPLIST 7   /* 编码为跳表*/
#define OBJ_ENCODING_EMBSTR 8     /* 编码为简短字符串*/
#define OBJ_ENCODING_Quicklist 9  /* 编码为快速链表*/
#define OBJ_ENCODING_STREAM 10    /* 编码为listpacks的基数树*/

# zset采用压缩列表时，元素个数最大值。默认值为128。
zset-max-ziplist-entries 128
# zset采用压缩列表时，每个元素的字符串长度最大值。默认值为64。
zset-max-ziplist-value 64

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;           // 字符串的实际使用长度
    uint8_t alloc;         // 总长度；5.0之前使用的是free，用于标识buff中剩余可用字节数
    unsigned char flags;   // 标志位，低三位表示类型，其余五位未使用
    char buf[];            // 字符数组，柔性数组，存放实际内容
};

typedef struct dictht {
    dictEntry **table;            // 指针数组，数组中的元素指向的是dictEntry的结构体
    unsigned long size;           // table数组的大小
    unsigned long sizemask;       // 掩码 = size - 1 
    unsigned long used;           // table数组已存元素个数，包含next单链表的数据
} dictht;

idx = hash & d->ht[table].sizemask；

typedef struct dictEntry {
    void *key;                      // 存储键 key
    union {
        void *val;                  // db.dict中的val
        uint64_t u64;
        int64_t s64;                // db.expires中存储过期时间*/
        double d;
    } v;                            // 值value，是个联合体;在不同场景下使用不同字段
    struct dictEntry *next;         // 当Hash冲突时，指向冲突的元素，形成单链表
} dictEntry;
​

typedef struct dict {
    dictType *type;             // 该字典对应的特定操作函数
    void *privdata;             // 该字典依赖的数据 
    dictht ht[2];               // Hash表，键值对存储在此
    long rehashidx;             // rehash标识，默认值为-1，代表没进行rehash操作
                                // 否则，该值表示Hash表ht[0]的rehash操作进行到了哪个索引值
    unsigned long iterators;  // 当前运行的安全迭代器数，当有安全迭代器绑定到该字典时，会暂停rehash
} dict;

/* 创建一个新的Hash表 */
dict *dictCreate(dictType *type, void *privDataPtr){
    dict *d = zmalloc(sizeof(*d));  //96字节
    _dictInit(d,type,privDataPtr);  //结构体初始化值
    return d;
}
/* Initialize the hash table */
int _ dictInit (dict *d, dictType *type, void *privDataPtr){
    _dictReset(&d->ht[0]);
    _dictReset(&d->ht[1]);
    d->type = type;
    d->privdata = privDataPtr;
    d->rehashidx = -1;
    d->iterators = 0;
    return DICT_OK;
}

/*调用前会查找key存在与否，不存在则调用dictAdd 函数*/
int dictAdd(dict *d, void *key, void *val){  
    dictEntry *entry = dictAddRaw(d,key,NULL); /*添加键，字典中键已存在则返回NULL，否则添加键至新节点中，返回新节点*/
    if (!entry) return DICT_ERR;               /*键存在则返回错误*/
    dictSetVal(d, entry, val);                 /*设置值*/
    return DICT_OK;
}

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)/*入参字典、键、Hash表节点地址*/
{
    if (dictIsRehashing(d)) _dictRehashStep(d);  /*该字典是否在进行rehash操作中,是则执行一次rehash*/
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1) 
/*查找键，找到则直接返回-1, 并把老节点存入existing字段，否则把新节点的索引值返回。如果遇到Hash表容量不足，则进行扩容*/
        return NULL;
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; /*是否进行rehash操作中,是则插入至散列表ht[1]中，否则插入散列表ht[0] */
    /*申请新节点内存，插入散列表中，给新节点存入键信息*/
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;
    dictSetKey(d, entry, key);
    return entry;
}

dictHashKey(d,key)                  //第1步：调用该字典的Hash函数得到键的Hash值
idx = hash & d->ht[table].sizemask; //第2步：用键的Hash值与字典掩码取与，得到索引值

int dictExpand(dict *d, unsigned long size){//传入size = d->ht[0].used*2
    dictht n;
    unsigned long realsize = _dictNextPower(size); /*重新计算扩容后的值，必须为2的N次方幂*/
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;
    d->ht[1] = n;         /*扩容后的新内存放入ht[1]中*/
    d->rehashidx = 0;       /*非默认的-1,表示需进行rehash*/
    return DICT_OK;
}

dictEntry *dictFind(dict *d, const void *key){
    // ...
    h = dictHashKey(ht, key) & ht->sizemask;        //根据Hash值获取到对应的索引值
    he = ht->table[h];
    while(he) {                                     //如果存在值则遍历该值中的单链表
        if (dictCompareHashKeys(ht, key, he->key))
            return he;                              //找到与键相等的值,返回该节点
        he = he->next;
    }
    // ...
}

void dbOverwrite(redisDb *db, robj *key, robj *val) {
    dictEntry *de = dictFind(db->dict,key->ptr); //查找键存在与否，返回存在的节点
    serverAssertWithInfo(NULL,key,de != NULL);   //不存在则中断执行
    dictEntry auxentry = *de;
    robj *old = dictGetVal(de);                  //获取老节点的val字段值
    dictSetVal(db->dict, de, val);               //给节点设置新的值
        dictFreeVal(db->dict, &auxentry);        //释放节点中旧val内存
}

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;
​
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;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;         // 跳跃表的首尾节点
    unsigned long length;        // 跳跃表长度（不含头节点）
    int level;                   // 跳跃表的高度
} zskiplist;

typedef struct zskiplistNode {
    sds ele;           // 用于存储字符串类型的数据
    double score;      // 用于存储排序的分值  
    struct zskiplistNode *backward;       // 后退指针，只能指向当前节点最底层的前一个节点
    struct zskiplistLevel {
        struct zskiplistNode *forward;    // 指向本层下一个节点
        unsigned long span;               // forward指向的节点与本节点之间的元素个数
    } level[];      // 生成跳跃表节点时，随机生成一个1～64的值
} zskiplistNode;

typedef struct intset {
    uint32_t encoding;   //编码类型，决定每个元素占用几个字节
    uint32_t length;     //元素个数
    int8_t contents[];   //柔性数组，存储具体元素；根据encoding字段决定几个字节表示一个元素
} intset;

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value); //获取添加元素的编码值
    uint32_t pos;
    if (success) *success = 1;
    if (valenc > intrev32ifbe(is->encoding)) {  //如果大于当前intset的编码，说明需要进行升级
        return intsetUpgradeAndAdd(is,value); //调用intsetUpgradeAndAdd进行升级后添加
    } else {
        if (intsetSearch(is,value,&pos)) {  //否则先进行查重,如果已经存在该元素，直接返回
            if (success) *success = 0;
            return is;
        }
        //如果元素不存在，则添加元素
        is = intsetResize(is,intrev32ifbe(is->length)+1); //首先将intset占用内存扩容
        //如果插入元素在intset中间位置，调用intsetMoveTail给元素挪出空间
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }
    _intsetSet(is,pos,value); //保存元素
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);  //修改intset的长度，将其加1
    return is;
}

intset \*intsetRemove（intset \*is, int64_t value, int *success）

//zl指向zlbytes字段
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))
​
//zl+4指向zltail字段
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
​
//zl+zltail指向尾元素首地址；intrev32ifbe使得数据存取统一采用小端法
#define ZIPLIST_ENTRY_TAIL(zl)                                               ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) 
​
//zl+8指向zllen字段
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
​
//压缩列表最后一个字节即为zlend字段
#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)

typedef struct zlentry {
    unsigned int prevrawlensize;     // previous_entry_length字段的长度
    unsigned int prevrawlen;         // previous_entry_length字段存储的内容
    unsigned int lensize;            // encoding字段的长度
    unsigned int len;                // 元素数据内容的长度
    unsigned int headersize;         // 当前元素的首部长度
    unsigned char encoding;          // 数据类型
    unsigned char *p;                // 当前元素首地址
} zlentry;

unsigned char *ziplistNew(void);

unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen);

unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p);

//后向遍历
unsigned char *ziplistNext(unsigned char *zl, unsigned char *p);
//前向遍历
unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p);

typedef struct quicklist {
    quicklistNode *head;        // 指向quicklist的头节点
    quicklistNode *tail;        // 指向quicklist的尾节点
    unsigned long count;        // 元素的总数
    unsigned long len;          // 节点的个数
    int fill : 16;              // 每个quicklistNode中ziplist长度
    unsigned int compress : 16; // 两端各有compress个节点不压缩
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev;   // 指向前一个节点
    struct quicklistNode *next;   // 指向后一个节点
    unsigned char *zl;        // 该节点对应的ziplist结构
    unsigned int sz;              // ziplist结构的大小
    unsigned int count : 16;      // ziplist的元素大小
    unsigned int encoding : 2;    // 采用的编码方式
    unsigned int container : 2;   // zl指向的容器类型：1代表none，2代表使用ziplist存储数据
    unsigned int recompress : 1;  // 代表这个节点之前是否是压缩节点
    unsigned int attempted_compress : 1;  // 测试时使用
    unsigned int extra : 10;    // 预留
} quicklistNode;

quicklist *quicklistCreate(void) {
    struct quicklist *quicklist;               //声明quicklist变量
    quicklist = zmalloc(sizeof(*quicklist));   //为quicklist申请空间
    quicklist->head = quicklist->tail = NULL;  //初始化quicklist结构体变量
    quicklist->len = 0;
    quicklist->count = 0;
    quicklist->compress = 0;
    quicklist->fill = -2;                      //从表7-1中可知, ziplist大小限制是8KB
    return quicklist;
}

// Total Bytes，整个listpack的空间大小
#define LP_HDR_SIZE 6
// Num Elem，listpack中的元素个数
#define LP_HDR_NUMELE_UNKNOWN UINT16_MAX
​
// Entry中的标志
#define LP_MAX_INT_ENCODING_LEN 9
#define LP_MAX_BACKLEN_SIZE 5
#define LP_MAX_ENTRY_BACKLEN 34359738367ULL
#define LP_ENCODING_INT 0
...
​
// End，结束标志
#define LP_EOF 0xFF

typedef struct rax {
    raxNode *head;
    uint64_t numele;
    uint64_t numnodes;
} rax;

typedef struct raxNode {
    uint32_t iskey:1;     // 该节点是否包含key
    uint32_t isnull:1;    // 是否存储value
    uint32_t iscompr:1;   // 是否压缩
    uint32_t size:29;     // 孩子节点数量，或压缩字符串的长度
    unsigned char data[];
} raxNode;

rax *raxNew(void) {
    rax *rax = rax_malloc(sizeof(*rax)); //申请空间
    rax->numele = 0;                     //当前元素个数为0
    rax->numnodes = 1;                   //当前节点个数为1
    rax->head = raxNewNode(0,0);         //构造头节点
    return rax;
}