Redis源码阅读摘记

输入图片描述

总述

REmote DIctionary Server(Redis) 是一个由 Salvatore Sanfilippo 写的 key-value 存储系统，是跨平台的非关系型数据库。
Redis 是一个开源的使用 ANSI C 语言编写、遵守 BSD 协议、支持网络、可基于内存、分布式、可选持久性的键值对(Key-Value)存储数据库，并提供多种语言的 API。
Redis 通常被称为数据结构服务器，因为值（value）可以是字符串(String)、哈希(Hash)、列表(list)、集合(sets)和有序集合(sorted sets)等类型。
–wiki

最近阅读了redis的部分源代码，这里是我初读时的一些笔记和感受。应该会随着时间不断更新。

1.哈希表的自动扩容

Redis用变量dict_can_resize记录哈希是否可以自动扩容，由两个方法 dictEnableResize()和dictDisableResize()设置该变量。

dictExpand()进行扩容时，会先选择一个满足size需求的2的指数，然后分配内存空间，创建新的哈希表。

这与C++ STL中的vector扩容机制类似（不同标准库实现的底数会有所不同，VS2015中以1.5倍扩容，GCC以2倍扩容）。

k = 1.5 在几次扩展之后，可以重用之前的内存空间。详见：知乎

2.灵活的dictType

dictType在哈 希系统中包含了一系列可由应用程序定义的函数指针，包括Hash函数、Key复制、Value 复制、Key比较、Key析构、Value析构，以增加哈希系统的灵活性。其中系统定义了三种默认的type，表示最常用的三种哈希表。

1
2
3
4
5
6
7
8
9
10
11
typedef struct dictType {
 unsigned int (*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; 
extern dictType dictTypeHeapStringCopyKey; 
extern dictType dictTypeHeapStrings; 
extern dictType dictTypeHeapStringCopyKeyValue;

3.宏函数的大量使用

redis有很多以“__”开头的内部函数和以宏定义形式出现的API函数。

1
2
3
4
5
6
7
#define quicklistCompress(_ql, _node)                                          \
    do {                                                                       \
        if ((_node)->recompress)                                               \
            quicklistCompressNode((_node));                                    \
        else                                                                   \
            __quicklistCompress((_ql), (_node));                               \
    } while (0)

  宏定义中调用的quicklistCompressNode是另一个宏定义：

1
2
3
4
5
6
7
8
9
/* 对未压缩节点进行压缩操作
 * Compress only uncompressed nodes. 
 */
#define quicklistCompressNode(_node)                                           \
    do {                                                                       \
        if ((_node) && (_node)->encoding == QUICKLIST_NODE_ENCODING_RAW) {     \
            __quicklistCompressNode((_node));                                  \
        }                                                                      \
    } while (0)

  而实际的功能则在 __quicklistCompress((_ql), (_node))和__quicklistCompressNode((_node))中实现。

  通过#define定义的宏函数通常在预处理时被替换为内联形式，有效避免常规函数调用时的参数copy以及栈操作（出、入）的耗时，牺牲目标编译文件的的部分体积来提高程序的运行效率。

4.数据换入换出

Redis在vm中寻找连续空闲区域的算法比较简单，直接进行简单的枚举：如果当前区域空闲，则判断是否有满足需求连续的空闲区域；如果当前区域有数据，则标记遇到有数据的区域的次数，如果连续REDIS_VM_MAX_RANDOM_JUMP/4次遇到非空闲 区域，则将指针往前跳跃一个不超过REDIS_VM_MAX_RANDOM_JUMP的随机数。

我的问题：为什么不使用快速适配(quick fit)算法？
快速适配(quick fit) 算法为那些常用大小的空闲区维护单独的链表。例如有一个 n 项表，该表的第一项是指向大小为 4 KB 的空闲区链表表头指针，第二项是指向大小为 8 KB 的空闲区链表表头指针，第三项是指向大小为 12 KB 的空闲区链表表头指针，以此类推。比如 21 KB 这样的空闲区既可以放在 20 KB 的链表中，也可以放在一个专门存放大小比较特别的空闲区链表中。