Redis 3.0源码分析-数据结构与对象 SDS LIST DICT

SDS

Redis定义的简单动态字符串（SDS）

登录后复制

      
      

       
       struct sdshdr { 
       
       
    // buf 中已占用空间的长度
       
       
    int len;
       
       
    // buf 中剩余可用空间的长度
       
       
    int free;
       
       
    // 数据空间
       
       
    char buf[];
       
       
};
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
      
      

从下面的测试中可以看出，该结构的大小为8字节。len指定buf数组中已使用字节的数量等于SDS所保存字符串的长度，不包括字符串末尾存放的\0，在分配内存时会为\0多分配一个内存单元，如​​sh = zmalloc(sizeof(struct sdshdr)+initlen+1);​​。

登录后复制

      
      

       
       /*
       
       
 * 返回 sds 实际保存的字符串的长度
       
       
 * s 指向 sdshdr 的 buf 属性
       
       
 * T = O(1)
       
       
 */
       
       
static inline size_t sdslen(const sds s) {
       
       
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
       
       
    return sh->len;
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
      
      

参数s指向sdshdr的buf，而s-(sizeof(struct sdshdr))指向sdshdr的首地址，因为sizeof(struct sdshdr)是8字节。

内存分配

内存分配主要在文件zmalloc.c和zmalloc.h中，在下面的系列中分析，这里开个头。

两种分配方式：zmalloc和zcalloc

登录后复制

      
      

       
       void *zmalloc(size_t size) {
       
       
    void *ptr = malloc(size+PREFIX_SIZE);
       
       
    if (!ptr) zmalloc_oom_handler(size);
       
       
#ifdef HAVE_MALLOC_SIZE
       
       
    update_zmalloc_stat_alloc(zmalloc_size(ptr));
       
       
    return ptr;
       
       
#else
       
       
    *((size_t*)ptr) = size;
       
       
    update_zmalloc_stat_alloc(size+PREFIX_SIZE);
       
       
    return (char*)ptr+PREFIX_SIZE;
       
       
#endif
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
      
      

zmalloc是由malloc函数来分配内存的

登录后复制

      
      

       
       #define zmalloc_size(p) tc_malloc_size(p)
      
      
      
      

       
       
1.
      
      

登录后复制

      
      

       
       #define zcalloc(x) calloc(x,1)
       
       
#define calloc(count,size) tc_calloc(count,size)
      
      
      
      

       
       
1.
       
       
2.
      
      

zfree释放内存

zrealloc

jemalloc
tcmalloc
tc_malloc_size
​​ ​ https://yq.aliyun.com/articles/6045​​

链表

存储在adlist.c中的，主要3种结构体：list、listIter、listNode。这些结构都在堆中使用zmalloc申请内存。

登录后复制

      
      

       
       typedef struct listNode {
       
       
    // 前置节点
       
       
    struct listNode *prev;
       
       
    // 后置节点
       
       
    struct listNode *next;
       
       
    // 节点的值
       
       
    void *value;
       
       
} listNode;
       
       
#define listPrevNode(n) ((n)->prev) // 返回给定节点的前置节点
       
       
#define listNextNode(n) ((n)->next) // 返回给定节点的后置节点
       
       
#define listNodeValue(n) ((n)->value) // 返回给定节点的值
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
      
      

登录后复制

      
      

       
       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;
       
       
#define listLength(l) ((l)->len) // 返回给定链表所包含的节点数量
       
       
#define listFirst(l) ((l)->head) // 返回给定链表的表头节点
       
       
#define listLast(l) ((l)->tail) // 返回给定链表的表尾节点
       
       

       
       
#define listSetDupMethod(l,m) ((l)->dup = (m)) // 将链表 l 的值复制函数设置为 m
       
       
#define listGetDupMethod(l) ((l)->dup) // 返回给定链表的值复制函数
       
       
#define listSetFreeMethod(l,m) ((l)->free = (m)) // 将链表 l 的值释放函数设置为 m
       
       
#define listGetFree(l) ((l)->free) // 返回给定链表的值释放函数
       
       
#define listSetMatchMethod(l,m) ((l)->match = (m)) // 将链表的对比函数设置为 m
       
       
#define listGetMatchMethod(l) ((l)->match) // 返回给定链表的值对比函数
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
       
       
23.
       
       
24.
      
      

登录后复制

      
      

       
       /*
       
       
 * 双端链表迭代器
       
       
 */
       
       
typedef struct listIter {
       
       
    // 当前迭代到的节点
       
       
    listNode *next;
       
       
    // 迭代的方向
       
       
    int direction;
       
       
} listIter;
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
      
      

哈希表

哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对

添加键值对

rehash

随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表执行rehash的步如下：

1. 为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（也即是ht[0].used属性的值）：如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2ⁿ。如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].use的2ⁿ。
2. 将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。
3. 将ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。