Redis原理学习

一、Redis的数据类型

1. Redis的数据类型

2. Redis键值对数据库及其底层结构

3. Redis对象(RedisObject)

3.1 概念

Redis中的任意数据类型的键和值都会被封装为一个RedisObject，也叫做Redis对象。

思考：什么是redisObject：

• 答：从Redis的使用者的角度来看，⼀个Redis节点包含多个database（非cluster模式下默认是16个，cluster模式下只能是1个），而一个database维护了从key space到object space的映射关系。这个映射关系的key是string类型，⽽value可以是多种数据类型，比如：
  string, list, hash、set、sorted set等。我们可以看到，key的类型固定是string，而value可能的类型是多个。
  ⽽从Redis内部实现的⾓度来看，database内的这个映射关系是用⼀个dict来维护的。dict的key固定用⼀种数据结构来表达就够了，这就是动态字符串sds。而value则比较复杂，为了在同⼀个dict内能够存储不同类型的value，这就需要⼀个通⽤的数据结构，这个通用的数据结构就是robj，全名是redisObject。

3.2 RedisObject结构体定义

//server.h
typedef struct redisObject {
    unsigned type:4;//5种可能的Redis对象类型，string、hash、list、set、和zset,占4个bit, 半个字节
    unsigned encoding:4;//底层对应的数据结构类型/编码存储方式 共有11种，占4个bit，半个字节
    unsigned lru:LRU_BITS; //最近最久未使用，记录该redis对象最后一次被访问的时间，占24个bit，3个字节，便于淘汰
    			//以maxmemory-policy 配置内存淘汰策略，默认为noeviction，超设置的最大内存时，不淘汰任何key，只拒绝命令
    			//LRU:以秒为单位记录最近一次访问时间，长度24bit
    			//LFU:高16位以分钟为单位记录最近一次访问时间，低8位记录逻辑访问次数
    int refcount;//对象引用计数器，记录当前对象被引用的次数，如果为0，则表示没有被引用，可以被回收
    void *ptr;//任意类型指针，指向当前redis对象实际的底层数据结构，即存储数据的实际空间，8个字节
} robj;//总共16个字节
1
2
3
4
5
6
7
8
9
10
11

3.3 Redis的五种数据结构

Redis中会根据存储的数据类型不同，选择不同的编码方式,对应RedisObject的type字段，每种数据类型的使用的编码方式如下：

3.4 Redis的编码方式

Redis中会根据存储的数据类型不同，选择不同的编码方式，对应RedisObject的encoding字段，共包含11种不同类型：

3.5 创建一个RedisObject

//object.c
//创建redis对象，需要指定底层的数据结构类型以及底层的数据结构的指针
robj *createObject(int type, void *ptr) {
    robj *o = zmalloc(sizeof(*o));//分配内存
    o->type = type;//设置redis对象的类型
    o->encoding = OBJ_ENCODING_RAW;//设置redis对象的编码方式,默认为字符串RAW编码方式
    o->ptr = ptr;//给redis对象的底层结构指针赋值
    o->refcount = 1;//对象的引用计数器初始化为1

    /* Set the LRU to the current lruclock (minutes resolution), or
     * alternatively the LFU counter. */
    // 将LRU设置为当前lruclock(分钟分辨率)，或者设置为LFU计数器。
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
        o->lru = LRU_CLOCK();
    }
    return o;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二、Redis底层数据结构的实现

1. 简单动态字符串(SDS)

1.1 概念：

Redis构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称SDS。

1.2 SDS结构体定义

// 弃用
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
// 最常用 长度255 2^8-1   1个字节
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[];
};
// 2个字节
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
// 4个字节  2^30==1GB 2^32 == 4 * 2^30 == 4GB
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
// 8个字节 0 ~ 2^64-1
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

//SDS的头类型，用于控制SDS头的大小，用flags字段标识
#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

1.3 C语言中数据类型定义

typedef unsigned   char 		uint8_t; // 1个字节
typedef unsigned short  int 	uint16_t;// 2个字节
typedef unsigned     int 		uint32_t;// 4个字节
typedef unsigned    __INT64 	uint64_t;// 8个字节
1
2
3
4

1.4 Redis中SDS的优点

1.4.1 获取字符串长度时间复杂度为O(1)

SDS结构，可以直接访问结构体中的len字段，获取字符串长度，不需要遍历一遍字符串，时间复杂度为O(1)

1.4.2 支持动态扩容

• 

1.4.3 二进制安全

C语言中的字符串，读取到’\0’就结束，无法遍历完包含有特殊字符’\0’的字符串，二进制不安全。而Redis设计的数据结构，根据SDS结构体中的实际存储字符串长度进行读取，可以让字符串中包含特殊字符串’\0’，二进制安全。 SDS 的 API 都是以处理二进制的方式来处理 SDS 存放在 buf[] 里的数据，程序不会对其中的数据做任何限制，数据写入的时候时什么样的，它被读取时就是什么样的。

1.4.5 减少内存分配次数

• 内存预分配：Linux系统分为用户空间和内核空间，应用程序无法直接操作硬件，申请内存的时候需要跟Linux内核进行交互，CPU会有一个从用户态切换到内核态的过程，需要进行上下文切换，会消耗一定的资源。如果在第一次内存分配的时候进行内存预分配，可以减少内存分配次数。
• 惰性空间释放:SDS 缩短时，并不会回收多余的内存空间，而是使用 free 字段将多出来的空间记录下来。如果后续有变更操作，直接使用 free 中记录的空间，减少了内存的分配。

2. 整数集合(inset)

2.1 概念

IntSet是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序、不重复等特征。

为了方便查找，Redis会将intset中所有的整数按照升序依次保存在contents数组中，结构如图：

现在，数组中每个数字都在int16_t的范围内，因此采用的编码方式是INTSET_ENC_INT16，每部分占用的字节大小为：
encoding：4字节
length：4字节
contents：2字节 * 3 = 6字节

我们向该其中添加一个数字：50000，这个数字超出了int16_t的范围，intset会自动升级编码方式到合适的大小。
以当前案例来说流程如下：

• 升级编码为INTSET_ENC_INT32, 每个整数占4字节，并按照新的编码方式及元素个数扩容数组
• 倒序依次将数组中的元素拷贝到扩容后的正确位置
• 将待添加的元素放入数组末尾
• 最后，将inset的encoding属性改为INTSET_ENC_INT32，将length属性改为4

2.2 inset结构体定义

typedef struct intset {
    uint32_t encoding;//编码方式，支持16位、32位、64位整数
    uint32_t length;//元素个数
    int8_t contents[];//整数数组，集合的元素，虽然是int8_t，但是实际是使用encoding的编码指定的大小来存储，这里只是一个地址
} intset;

// 三种编码格式
#define INTSET_ENC_INT16 (sizeof(int16_t))//2字节整数，范围类似java中的short
#define INTSET_ENC_INT32 (sizeof(int32_t))//4字节整数，范围类似java中的int
#define INTSET_ENC_INT64 (sizeof(int64_t))//8字节整数，范围类似java中的long

//API
intset *intsetNew(void);
intset *intsetAdd(intset *is, int64_t value, uint8_t *success);//重要，可能会触发到编码类型升级
intset *intsetRemove(intset *is, int64_t value, int *success);
uint8_t intsetFind(intset *is, int64_t value);
int64_t intsetRandom(intset *is);
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value);
uint32_t intsetLen(const intset *is);
size_t intsetBlobLen(intset *is);
int intsetValidateIntegrity(const unsigned char *is, size_t size, int deep);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.3 inset的插入元素时的编码升级

插入新元素

// 插入一个元素，可能会进行类型升级
/* Insert an integer in the intset */
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);//获取当前数组值得编码类型
    uint32_t pos;//存储要插入的位置
    if (success) *success = 1;//标记是否插入成功

    // 判断要插入的值value的编码类型是否超过当前inset的编码类型
    if (valenc > intrev32ifbe(is->encoding)) {
        // inset进行编码类型升级
        return intsetUpgradeAndAdd(is,value);
    } else {
        // 二分查找是否inset中是否已经有了value，如果已经存在，则标记插入失败并返回inset集合
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }
        // 重新设置数组的大小
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        // 如果不是插入到数组末尾，则把pos位置后面的元素往后移动一个位置
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }

    // 把value插入到pos的位置
    _intsetSet(is,pos,value);
    // 修改数组的长度
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    // 返回inset集合
    return is;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

类型升级并插入新值：

/* Upgrades the intset to a larger encoding and inserts the given integer. */
// 升级inset的编码类型并且插入给的新值value
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    // 获取当前inset的编码类型
    uint8_t curenc = intrev32ifbe(is->encoding);
    // 获取value的编码类型
    uint8_t newenc = _intsetValueEncoding(value);
    // 获取inset实际存储的元素个数
    int length = intrev32ifbe(is->length);
    // value值正负的标记，如果value为负数，则直接插入到下标为0的位置，否则插入到数组末尾
    int prepend = value < 0 ? 1 : 0;

    /* First set new encoding and resize */
    // 重新设置inset的编码类型
    is->encoding = intrev32ifbe(newenc);
    // 重新设置数组大小
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    /* Upgrade back-to-front so we don't overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    // 按照原编码格式获取原数组的元素值，按照新的编码格式倒叙插入新的数组，实际是在同一个数组上进行
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* Set the value at the beginning or the end. */
    // 根据标记判断将超过编码的值插入到数组头还是数组末尾
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    // 重新设置数组的元素个数
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    // 返回inset集合
    return is;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

二分查找过程：

// 二分查找value应该插入的位置，如果返回0，则说明需要插入，否则不需要插入
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    int64_t cur = -1;

    /* The value can never be found when the set is empty */
// 特判，如果数组为空，则返回0；如果大于inset中的最大值，则插入位置pos为数组末尾；如果小于数组最小值，则插入到数组第一个位置
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;//整数集合没有元素，那么插入到第0号位置
        return 0;
    } else {
        /* Check for the case where we know we cannot find the value,
         * but do know the insert position. */
        if (value > _intsetGet(is,max)) {//如果大于集合最大值，则插入到末尾
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        } else if (value < _intsetGet(is,0)) {//如果小于集合最小值，则插入到第0号位置
            if (pos) *pos = 0;
            return 0;
        }
    }

// 二分查找
    while(max >= min) {
        mid = ((unsigned int)min + (unsigned int)max) >> 1;
        cur = _intsetGet(is,mid);//cur是二分结束时的边界位置的值，min为边界的索引
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {
            break;
        }
    }

// 如果查找过程中发现数组已经存在相同的值，则返回1;否则返回需要插入的位置
    if (value == cur) {//如果元素已经存在
        if (pos) *pos = mid;
        return 1;
    } else {//元素不存在，需要插入到min位置
        if (pos) *pos = min;
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

2.4 总结

Intset可以看做是特殊的整数数组，具备一些特点：

• Redis会确保Intset中的元素唯一、有序
• 具备类型升级机制，可以节省内存空间
• 底层采用二分查找方式来查询 O(logN)

优点：

• 提升整数集合的灵活性，可以随意的添加整数，而不用关心整数的类型；
• 可以尽可能的节约内存。

缺点：

• 不支持降级，一旦对数组进行了升级，就会一直保持升级后的状态。

3. 哈希/字典(Dict)

3.1 概念

我们知道Redis是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。
Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

底层是数组+链表的结构

优点：查询速度快

缺点：占用内存大，内存不连续，导致内存碎片多

3.2 Dict结构体定义

3.2.1 字典的hash节点

typedef struct dictEntry {
    void *key;//键
    union {//共用体
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;//值
    struct dictEntry *next;//Dict结构应用hash冲突的拉链法
} dictEntry;
1
2
3
4
5
6
7
8
9
10

3.2.2 字典的hash表

typedef struct dictht {
    dictEntry **table;//hash节点二级指针，指向存储了hash节点地址的数组
    unsigned long size;//hash表的大小,规定大小为2^n    如：2^4 == 16  2^4 - 1 == 15 -> 二进制00..001111
    unsigned long sizemask;//hash表大小的掩码，等于size-1，方便求hash值时取余操作，位运算更快捷
    unsigned long used;//hash节点的个数
} dictht;
1
2
3
4
5
6

3.2.3 字典Dict

typedef struct dict {
    dictType *type;//hash表的类型，内置了不同的hash函数
    void *privdata;//私有数据，在做特殊hash运算时使用
    dictht ht[2];/*一个字典包含两个hash表，第一个hash表是当前数据，另一个hash表一般是空，rehash时使用  */
    long rehashidx; //标记rehash的进度，渐进式rehash，为-1时表示没有进行rehash
    int16_t pauserehash; //rehash是否暂停，1则暂停，0则继续
} dict;
1
2
3
4
5
6
7

3.2.4 关系示例图：

3.3 解决hash冲突的方案

3.3.1 简介

拉链法/链地址法，发生hash冲突时进行相同hash位置链表的头插

思考：头插法有什么好处？

答：如果是用尾插入法，需要保存尾指针，这会占用一定的内存空间；或者采用遍历的方式获得链表的尾指针，则性能较差。而采用头插法仅需修改两个指针的值即可完成新节点的插入

3.3.2 示例：

当我们向Dict添加键值对时，Redis首先根据key计算出hash值（h），然后利用 h & sizemask来计算元素应该存储到数组中的哪个索引位置。我们存储k1=v1，假设k1的哈希值h =1，则1&3 =1，因此k1=v1要存储到数组角标1位置。

如果此时需要插入k2，其计算出来的hash值也是角标为1，则进行链表的头插，仅需修改两个指针的指向即可

3.4 Dict的扩容机制

Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。
Dict在每次新增键值对时都会检查负载因子（LoadFactor = used/size） ，满足以下两种情况时会触发哈希表扩容：

负载因子=hash节点数 / hash表的大小

哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程；
哈希表的 LoadFactor > 5 ；

3.4.1 如果达到扩容条件则进行扩容

//dict.c
/* Expand the hash table if needed */
// 判断是否需要进行扩容
static int _dictExpandIfNeeded(dict *d)
{
    // 如果字典已经在rehash,则直接返回OK
    if (dictIsRehashing(d)) return DICT_OK;

    // 如果字典刚被创建，则将字典的hash表扩容为4的默认大小
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    // 如果负载因子大于1，即hash节点数 大于 hash表的大小， 并且当前没有后台BGReWrite等子进程操作，
    // 或者负载因子大于5 则进行扩容
    // 扩容是扩大到大于used+1 的第一个2^n的大小
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio) &&
        dictTypeExpandAllowed(d))
    {
        return dictExpand(d, d->ht[0].used + 1);
    }
    return DICT_OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.4.2 判断是否需要重置缩小hash表数组的大小

// server.c
// 判断是否需要重置hash数组的大小
int htNeedsResize(dict *dict) {
    long long size, used;
    // 获取字典hash表数组的大小
    size = dictSlots(dict);
    // 获取hash节点的个数
    used = dictSize(dict);
    // 如果hash表数组大小 > 初始大小4 并且 负载因子小于0.1，则需要重置
    return (size > DICT_HT_INITIAL_SIZE &&
            (used*100/size < HASHTABLE_MIN_FILL));//HASHTABLE_MIN_FILL默认是10
}
1
2
3
4
5
6
7
8
9
10
11
12

3.4.3 重置hash表的大小

//dict.c
int dictResize(dict *d)
{
    unsigned long minimal;
    // 如果后台有子进程或者正在进行ReHash，则返回ERROR
    if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
    // 如果当前hash节点个数小于默认大小4，则设置hash表大小为4，
    // 否则重新设置hash表的大小为第一个大于等于当前hash节点个数 的2^n
    minimal = d->ht[0].used;//获取当前hash节点的个数
    if (minimal < DICT_HT_INITIAL_SIZE)
        minimal = DICT_HT_INITIAL_SIZE;
    return dictExpand(d, minimal);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.4.4 删除hash表数组中的一个元素

//t_hash.c
int hashTypeDelete(robj *o, sds field) {
    ...
	if (dictDelete((dict*)o->ptr, field) == C_OK) {
            deleted = 1;//标记删除成功

            /* Always check if the dictionary needs a resize after a delete. */
       		//判断是否需要重置缩小hash数组的大小，如果不是处于刚创建状态，并且hash数组的负载因子小于0.1，则需要重置hash数组的大小
            if (htNeedsResize(o->ptr)) dictResize(o->ptr);
        }
    ...
}
1
2
3
4
5
6
7
8
9
10
11
12

3.4.5 hash表结构的扩容(重要)

//dict.c
/* Expand or create the hash table,
 * when malloc_failed is non-NULL, it'll avoid panic if malloc fails (in which case it'll be set to 1).
 * Returns DICT_OK if expand was performed, and DICT_ERR if skipped. */
int _dictExpand(dict *d, unsigned long size, int* malloc_failed)
{
    if (malloc_failed) *malloc_failed = 0;

    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    // 如果当前正在进行rehash，或者当前hash节点的个数大于申请的size，则返回ERROR
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    // 声明一个新的hash表结构
    dictht n; /* the new hash table */
    // 获取第一个大于等于size的2^n为hash数组真实的size
    unsigned long realsize = _dictNextPower(size);

    /* Detect overflows */
    // 程序健壮性判断
    // 如果真实size还小于size，或者申请的内存大小却小于真实size，则返回ERROR
    if (realsize < size || realsize * sizeof(dictEntry*) < realsize)
        return DICT_ERR;

    /* Rehashing to the same table size is not useful. */
    // 如果真实size跟size相等，也返回ERROR
    if (realsize == d->ht[0].size) return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    // 申请内存初始化新的hash表
    // 设置新的hash表的大小为真实size
    n.size = realsize;
    // 设置新的hash表的掩码值，方便hash值的取余
    n.sizemask = realsize-1;
    if (malloc_failed) {//malloc_failed一般为NULL

        n.table = ztrycalloc(realsize*sizeof(dictEntry*));
        *malloc_failed = n.table == NULL;
        if (*malloc_failed)
            return DICT_ERR;
    } else // 给新的hash数组分配内存
        n.table = zcalloc(realsize*sizeof(dictEntry*));
// 初始化hash节点的个数为0
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    // 如果当前的hash表是处于初始化状态，还没有hash数组，则把hash表结构体赋值给0号位的hash表
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    //扩容或者缩容都会重新申请内存空间，需要重新计算hash值，进行rehash
    // 否则把新的hash表结构赋值给1号位的hash表，并标识正在进行rehash
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

3.4.6 Dict的渐进式rehash

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表，这个过程称为rehash。

渐进式rehash:Dict的rehash过程不是一次性完成的。如果Dict中包含数百万的entry,要在一次rehash完成，极易导致主线程阻塞。因此Dict的rehash是分多次进行、渐进式完成的，因此成为渐进式rehash。

过程是这样的：

• 1、计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：
  • 如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n
  • 如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）
• 2、按照新的realeSize申请内存空间，创建dictht，并赋值给dict.ht[1]
• 3、设置dict.rehashidx = 0，标示开始rehash
• 4、将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]
• 4、每次执行CURD操作的时候，都检查一下dict.rehashidx是否大于-1，如果是则将dict.ht[0].table[rehashidx]的hash节点链表rehash到dict.ht[1]，并且将rehash++。直至dict.ht[0]的所有数据都rehash到dict.ht[1]
• 5、将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存
• 6、将rehashidx赋值为-1，代表rehash结束
• 7、在rehash过程中，新增操作，则直接写入ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增，随着rehash最终为空

3.4.7 rehash的示意图

3.5 总结：

3.5.1 Dict的结构：

• 类似java的HashTable，底层是数组加链表来解决哈希冲突
• Dict包含两个哈希表，ht[0]平常用，ht[1]用来rehash

3.5.2 Dict的伸缩：

• 当LoadFactor大于5或者LoadFactor大于1并且没有子进程任务时，Dict扩容
• 当LoadFactor小于0.1时，Dict收缩
• 扩容大小为第一个大于等于used + 1的2^n
• 收缩大小为第一个大于等于used 的2^n
• Dict采用渐进式rehash，每次访问Dict时执行一次rehash
• rehash时ht[0]只减不增，新增操作只在ht[1]执行，其它操作在两个哈希表

4. 压缩链表(ZipList)

4.1 概念

ZipList 是一种特殊的“双端链表” ，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 O(1)。

4.2 ZipListEntry

ZipList 中的Entry并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用16个字节，浪费内存。而是采用了下面的结构：

• previous_entry_length：前一节点的长度，占1个或5个字节。

  • 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
  • 如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据

• encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节

• contents：负责保存节点的数据，可以是字符串或整数

**ZipList中所有存储长度的数值均采用小端字节序，即低位字节在前，高位字节在后。**例如：数值0x1234，采用小端字节序后实际存储值为：0x3412

4.3 Encoding编码

ZipListEntry中的encoding编码分为字符串和整数两种：

4.3.1 字符串：

如果encoding是以“00”、“01”或者“10”开头，则证明content是字符串

例如，我们要保存字符串：“ab”和 “bc”

4.3.2 整数：

如果encoding是以“11”开始，则证明content是整数，且encoding固定只占用1个字节

4.4 ZipList的连锁更新问题

ZipList的每个Entry都包含previous_entry_length来记录上一个节点的大小，长度是1个或5个字节：

• 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
• 如果前一节点的长度大于等于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据
  现在，假设我们有N个连续的、长度为250~253字节之间的entry，因此entry的previous_entry_length属性用1个字节即可表示，如图所示：

ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新（Cascade Update）。新增、删除、修改都可能导致连锁更新的发生。

4.5 总结：

ZipList特性：

• 压缩列表的可以看做一种连续内存空间的"双向链表"
• 列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低
• 如果列表数据过多，导致链表过长，可能影响查询性能
• 增或删较大数据时有可能发生连续更新问题
• 数据较多时，申请内存的效率较低

5. 快表(QuickList)

5.1 思考

问题1：ZipList虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低。怎么办？

​ 答：为了缓解这个问题，我们必须限制ZipList的长度和entry大小。

为了避免QuickList中的每个ZipList中entry过多，Redis提供了一个配置项：list-max-ziplist-size来限制。
如果值为正，则代表ZipList的允许的entry个数的最大值
如果值为负，则代表ZipList的最大内存大小，分5种情况：

• -1：每个ZipList的内存占用不能超过4kb
• -2：每个ZipList的内存占用不能超过8kb(默认)
• -3：每个ZipList的内存占用不能超过16kb
• -4：每个ZipList的内存占用不能超过32kb
• -5：每个ZipList的内存占用不能超过64kb

其默认值为 -2:

问题2：但是我们要存储大量数据，超出了ZipList最佳的上限该怎么办？

​ 答：我们可以创建多个ZipList来分片存储数据。

问题3：数据拆分后比较分散，不方便管理和查找，这多个ZipList如何建立联系？**

​ 答：Redis在3.2版本引入了新的数据结构QuickList，它是一个双端链表，只不过链表中的每个节点都是一个ZipList。

5.2 概念

在 Redis 3.0 之前，List 对象的底层数据结构是双向链表或者压缩列表。然后在 Redis 3.2 的时候，List 对象的底层改由 quicklist 数据结构实现。

其实 quicklist 就是「双向链表 + 压缩列表」组合，因为一个 quicklist 就是一个链表，而链表中的每个元素又是一个压缩列表。

5.3 QuickList结构体定义

5.3.1 quickList

//quicklist.h
typedef struct quicklist {
    quicklistNode *head;//quicklist的链表头
    quicklistNode *tail;//quicklist的链表尾
    unsigned long count;//快表中所有压缩列表的所有节点个数        /* total count of all entries in all ziplists */
    unsigned long len;//快表中压缩列表的总数量          /* number of quicklistNodes */
    int fill : QL_FILL_BITS;//设置单个压缩列表的占用的最大内存类型，默认为-2，占用8kb              /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS;//双向链表首尾不压缩节点的个数 /* depth of end nodes not to compress;0=off */
    //内存重分配时的书签数量及数组，一般用不到
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;
1
2
3
4
5
6
7
8
9
10
11
12

5.3.2 quickListNode

//quicklist.h
typedef struct quicklistNode {
    struct quicklistNode *prev;//前一个节点指针
    struct quicklistNode *next;//后一个节点指针
    unsigned char *zl;//当前ZipList指针
    unsigned int sz;//当前ZipList所占用字节数大小             /* ziplist size in bytes */
    unsigned int count : 16;//当前ZipList中entry的个数     /* count of items in ziplist */
    unsigned int encoding : 2;//编码方式：1 ZipList 2 lzf压缩模式   /* RAW==1 or LZF==2 */
    unsigned int container : 2;//数据容器类型(预留)：1 其他 2 ZipList  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1;//是否被解压缩： 1 说明被解压了，将来需要重新进行压缩 /* was this node previous compressed? */
    unsigned int attempted_compress : 1; //测试使用  /* node can't compress; too small */
    unsigned int extra : 10; //预留字段 /* more bits to steal for future usage */
} quicklistNode;
1
2
3
4
5
6
7
8
9
10
11
12
13

5.3.3 quickList关系示意图

5.3.3.1 未压缩状态

5.3.3.2 首尾压缩1个节点

5.4 总结：

QuickList的特点：

• 是一个节点为ZipList的双端链表
• 节点采用ZipList，解决了传统链表的内存占用问题
• 控制了ZipList大小，解决连续内存空间申请效率问题
• 中间节点可以压缩，进一步节省了内存

6. 跳表(SkipList)

6.1 概念

SkipList（跳表）首先是链表，但与传统链表相比有几点差异：
元素按照升序排列存储
节点可能包含多个指针，指针跨度不同。

6.2 SkipList结构体定义

6.2.1 zset中的zskiplist跳表结构体定义

//server.h
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;//跳表的头尾指针
    unsigned long length;//跳表节点数量
    int level;//最大的索引层级，默认是1
} zskiplist;//zset中的跳表结构体定义
1
2
3
4
5
6

6.2.2 zset中的跳表中的节点的结构体定义

//server.h
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;//节点的值
    double score;//节点的分数，用于排序、查找
    struct zskiplistNode *backward;//前一个节点指针
    // 后节点指针数组
    struct zskiplistLevel {
        struct zskiplistNode *forward;//后一个节点指针
        unsigned long span;//与当前指向的后一个节点的跨度
    } level[];
} zskiplistNode;//zset中的跳表中的节点的结构体定义
1
2
3
4
5
6
7
8
9
10
11
12

6.2.3 跳表结构关系示意图

6.2.3.1 跳表链表中的每个节点只有一个后继节点

6.2.3.2 跳表链表中的每个节点可能有多个后继节点

6.3总结：

SkipList的特点：

• 跳跃表是一个双向链表，每个节点都包含score和ele值
• 节点按照score值排序，score值一样则按照ele字典排序
• 每个节点都可以包含多层指针，层数是1到32之间的随机数
• 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
• 增删改查效率与红黑树基本一致，实现却更简单
• 深入思考： 为什么 Zset 的实现用跳表而不用平衡树（如 AVL树、红黑树等）？

7. listpack(在6.2版本中还未发布)

7.1 概念

为了解决ZipList连锁更新的问题，Redis 在 5.0 新设计一个数据结构叫 listpack，目的是替代压缩列表，它最大特点是 listpack 中每个节点不再包含前一个节点的长度了，压缩列表每个节点正因为需要保存前一个节点的长度字段，就会有连锁更新的隐患。

listpack 采用了压缩列表的很多优秀的设计，比如还是用一块连续的内存空间来紧凑地保存数据，并且为了节省内存的开销，listpack 节点会采用不同的编码方式保存不同大小的数据。

7.2 结构示意图

主要包含三个方面内容：

• encoding：定义该元素的编码类型，会对不同长度的整数和字符串进行编码；
• data：实际存放的数据；
• len：encoding+data的总长度；

可以看到，listpack 没有压缩列表中记录前一个节点长度的字段了，listpack 只记录当前节点的长度，当我们向 listpack 加入一个新元素的时候，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题。

三、Redis的数据类型的底层应用

1. 数据类型及其底层结构关系

左边是 Redis 3.0版本的，也就是《Redis 设计与实现》这本书讲解的版本

右边是现在 Github 最新的 Redis 代码的（还未发布正式版本）

2. String

String是Redis中最常见的数据存储类型：

• 其基本编码方式是RAW，基于简单动态字符串（SDS）实现，存储上限为512mb。RAW编码方式需要申请两次内存，一次申请RedisObject的内存，一次申请SDS的内存，因为两段内存不连续，用指针进行关联。

• 如果存储的SDS长度小于44字节，则会采用EMBSTR编码，此时object head与SDS是一段连续空间。申请内存时

只需要调用一次内存分配函数，效率更高。

• 如果⼀个String类型的value的值是数字，并且大小在LONG_MAX范围内，那么Redis内部会把它转成long类型来存储，从⽽减少内存的使用则会采用INT编码：直接将数据保存在RedisObject的ptr指针位置（刚好8字节），不再需要SDS了。

2.1 SDS的特点

2.2 String的三类编码以及示意图

确切地说，String在Redis中是⽤⼀个robj来表示的。

用来表示String的robj可能编码成3种内部表⽰：OBJ_ENCODING_RAW，OBJ_ENCODING_EMBSTR，OBJ_ENCODING_INT。
其中前两种编码使⽤的是sds来存储，最后⼀种OBJ_ENCODING_INT编码直接把string存成了long型。

• 在对string进行incr, decr等操作的时候，如果它内部是OBJ_ENCODING_INT编码，那么可以直接进行ASCII码的加减操作；如果它内部是OBJ_ENCODING_RAW或OBJ_ENCODING_EMBSTR编码，那么Redis会先试图把sds存储的字符串转成long型，如果能转成功，再进行加减操作。

对⼀个内部表示成long型的string执行append, setbit, getrange这些命令，针对的仍然是string的值（即⼗进制表示的字符串），而不是针对内部表⽰的long型进⾏操作。比如字符串”32”，如果按照字符数组来解释，它包含两个字符，它们的ASCII码分别是0x33和0x32。当我们执行命令setbit key 7 0的时候，相当于把字符0x33变成了0x32，这样字符串的值就变成了”22”。⽽如果将字符串”32”按照内部的64位long型来解释，那么它是0x0000000000000020，在这个基础上执⾏setbit位操作，结果就完全不对了。因此，在这些命令的实现中，会把long型先转成字符串再进行相应的操作。

3. List

3.1 List的特点

Redis的List类型可以从首、尾操作列表中的元素：

思考：哪一个数据结构能满足上述特征？

• LinkedList ：双向链表，可以从双端访问，内存占用较高，内存碎片较多
• ZipList ：压缩列表，可以从双端访问，内存占用低，存储上限低
• QuickList：LinkedList + ZipList，可以从双端访问，内存占用较低，包含多个ZipList，存储上限高

3.2 结构示意图

Redis的List结构类似一个双端链表，可以从首、尾操作列表中的元素：

• 在3.2版本之前，Redis采用ZipList和LinkedList来实现List，当元素数量小于512并且元素大小小于64字节时采用ZipList编码，超过则采用LinkedList编码。

• 在3.2版本之后，Redis统一采用QuickList来实现List：

4. Set

4.1 Set的特点

Set是Redis中的单列集合，满足下列特点：

• 不保证有序性
• 保证元素唯一性
• 可以求集合的交集、并集、差集

可以看出，Set对查询元素的效率要求非常高

• 思考一下，什么样的数据结构可以满足？

答：HashTable，也就是Redis中的Dict，不过Dict是双列集合（可以存键、值对）

Set是Redis中的集合，不一定确保元素有序，可以满足元素唯一、查询效率要求极高。

为了查询效率和唯一性，set采用HT编码（Dict）。Dict中的key用来存储元素，value统一为null。

当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries时，Set会采用IntSet编码，以节省内存

4.2 Set的两种编码方式以及示意图

5. ZSet

5.1 ZSet的特点

ZSet也就是SortedSet，其中每一个元素都需要指定一个score值和member值：

• 可以根据score值排序后
• member必须唯一
• 可以根据member查询分数

因此，zset底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求。

思考：之前学习的哪种编码结构可以满足？

• SkipList：可以排序，并且可以同时存储score和ele值（member）
• HT（Dict）：可以键值存储，并且可以根据key找value

5.2 ZSet的两类种编码方式以及示意图

5.2.1 Dict + SkipList的编码方式

//server.h
// ZSet结构体
typedef struct zset {
    dict *dict;//Dict指针
    zskiplist *zsl;//SkipList指针
} zset;

//object.c
//创建ZSet类型的RedisObject
robj *createZsetObject(void) {
    zset *zs = zmalloc(sizeof(*zs));//分配内存
    robj *o;//声明Redis对象指针

    zs->dict = dictCreate(&zsetDictType,NULL);//初始化dict
    zs->zsl = zslCreate();//初始化skipList
    o = createObject(OBJ_ZSET,zs);//初始化ZSet类型的RedisObject
    o->encoding = OBJ_ENCODING_SKIPLIST;//设置ZSet的编码类型为OBJ_ENCODING_SKIPLIST，但底层是dict和skipList
    return o;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

5.2.2 ZipList的编码方式

当元素数量不多时，HT和SkipList的优势不明显，而且更耗内存。因此zset还会采用ZipList结构来节省内存，不过需要同时满足两个条件：

• 元素数量小于zset_max_ziplist_entries，默认值128
• 每个元素都小于zset_max_ziplist_value字节，默认值64

ziplist本身没有排序功能，而且没有键值对的概念，因此需要有zset通过编码实现：

• ZipList是连续内存，因此score和element是紧挨在一起的两个entry， element在前，score在后
• score越小越接近队首，score越大越接近队尾，按照score值升序排列

6. Hash

6.1 Hash的特点

Hash结构与Redis中的Zset非常类似：

• 都是键值存储

• 都需求根据键获取值

• 键必须唯一

• 两者区别如下：

  • zset的键是member，值是score；hash的键和值都是任意值
  • zset要根据score排序；hash则无需排序

因此，Hash底层采用的编码与Zset也基本一致，只需要把排序有关的SkipList去掉即可：

hash结构如下：

zset集合如下：

6.2 Hash的两类种编码方式以及示意图

6.2.1 ZipList 或 Dict

Hash结构默认采用ZipList编码，用以节省内存。 ZipList中相邻的两个entry 分别保存field和value

当数据量较大时，Hash结构会转为HT编码，也就是Dict，触发条件有两个：

• ZipList中的元素数量超过了hash-max-ziplist-entries（默认512）
• ZipList中的任意entry大小超过了hash-max-ziplist-value（默认64字节）

Redis的hash之所以这样设计，是因为当ziplist变得很⼤的时候，它有如下几个缺点：

• 每次插⼊或修改引发的realloc操作会有更⼤的概率造成内存拷贝，从而降低性能。
• ⼀旦发生内存拷贝，内存拷贝的成本也相应增加，因为要拷贝更⼤的⼀块数据。
• 当ziplist数据项过多的时候，在它上⾯查找指定的数据项就会性能变得很低，因为ziplist上的查找需要进行遍历。

总之，ziplist本来就设计为各个数据项挨在⼀起组成连续的内存空间，这种结构并不擅长做修改操作。⼀旦数据发⽣改动，就会引发内存realloc，可能导致内存拷贝。

四、Redis的IO模型

1. IO 概念

Linux系统为了提高IO效率，会在用户空间和内核空间都加入缓冲区：

写数据时，要把用户缓冲数据拷贝到内核缓冲区，然后写入设备

读数据时，要从设备读取数据到内核缓冲区，然后拷贝到用户缓冲区

针对这个操作：我们的用户在读写数据时，会去向内核态申请，想要读取内核的数据，而内核数据要去等待驱动程序从硬件上读取数据，当从磁盘上加载到数据之后，内核会将数据写入到内核的缓冲区中，然后再将数据拷贝到用户态的buffer中，然后再返回给应用程序，整体而言，速度慢，就是这个原因，为了加速，我们希望read也好，还是wait for data也最好都不要等待，或者时间尽量的短。

2. 五种IO模型

2.1 概念

在《UNIX网络编程》一书中，总结归纳了5种IO模型：

• 阻塞IO（Blocking IO）
• 非阻塞IO（Nonblocking IO）
• IO多路复用（IO Multiplexing）
• 信号驱动IO（Signal Driven IO）
• 异步IO（Asynchronous IO）

应用程序想要去读取数据，是无法直接读取到磁盘数据的，需要先到内核里边去等待内核操作硬件拿到数据，这个过程就是1，是需要等待的，等到内核从磁盘上把数据加载出来之后，再把这个数据写给用户的缓存区，这个过程是2

2.2 阻塞IO模型

整个过程中，用户从发起读请求开始，一直到读取到数据，都是一个阻塞状态。

具体流程如下图：

用户去读取数据时，会去先发起recvform一个命令，尝试从内核上加载数据，如果内核没有数据，那么用户就会等待，此时内核会去从硬件上读取数据，内核读取数据之后，会把数据拷贝到用户空间，并且返回ok，整个过程，都是阻塞等待的，这就是阻塞IO

总结如下：

顾名思义，阻塞IO就是两个阶段都必须阻塞等待：

阶段一：

• 用户进程尝试读取数据（比如网卡数据）
• 此时数据尚未到达，内核需要等待数据
• 此时用户进程也处于阻塞状态

阶段二：

• 数据到达并拷贝到内核缓冲区，代表已就绪
• 将内核数据拷贝到用户缓冲区
• 拷贝过程中，用户进程依然阻塞等待
• 拷贝完成，用户进程解除阻塞，处理数据

可以看到，阻塞IO模型中，用户进程在两个阶段都是阻塞状态。

2.3 非阻塞IO模型

顾名思义，非阻塞IO的recvfrom操作会立即返回结果而不是阻塞用户进程。

阶段一：

• 用户进程尝试读取数据（比如网卡数据）
• 此时数据尚未到达，内核需要等待数据
• 返回异常给用户进程
• 用户进程拿到error后，再次尝试读取
• 循环往复，直到数据就绪

阶段二：

• 将内核数据拷贝到用户缓冲区
• 拷贝过程中，用户进程依然阻塞等待
• 拷贝完成，用户进程解除阻塞，处理数据
• 可以看到，非阻塞IO模型中，用户进程在第一个阶段是非阻塞，第二个阶段是阻塞状态。虽然是非阻塞，但性能并没有得到提高。而且忙等机制会导致CPU空转，CPU使用率暴增。

2.4 IO多路复用模型

2.4.1 概念

无论是阻塞IO还是非阻塞IO，用户应用在一阶段都需要调用recvfrom来获取数据，差别在于无数据时的处理方案：

如果调用recvfrom时，恰好没有数据，阻塞IO会使CPU阻塞，非阻塞IO使CPU空转，都不能充分发挥CPU的作用。
如果调用recvfrom时，恰好有数据，则用户进程可以直接进入第二阶段，读取并处理数据

所以怎么看起来以上两种方式性能都不好

而在单线程情况下，只能依次处理IO事件，如果正在处理的IO事件恰好未就绪（数据不可读或不可写），线程就会被阻塞，所有IO事件都必须等待，性能自然会很差。

就比如服务员给顾客点餐，分两步：

• 顾客思考要吃什么（等待数据就绪）
• 顾客想好了，开始点餐（读取数据）

要提高效率有几种办法？

方案一：增加更多服务员（多线程）
方案二：不排队，谁想好了吃什么（数据就绪了），服务员就给谁点餐（用户应用就去读取数据）

那么问题来了：用户进程如何知道内核中数据是否就绪呢？

所以接下来就需要详细的来解决多路复用模型是如何知道到底怎么知道内核数据是否就绪的问题了

这个问题的解决依赖于提出的

文件描述符（File Descriptor）：简称FD，是一个从0 开始的无符号整数，用来关联Linux中的一个文件。在Linux中，一切皆文件，例如常规文件、视频、硬件设备等，当然也包括网络套接字（Socket）。

通过FD，我们的网络模型可以利用一个线程监听多个FD，并在某个FD可读、可写时得到通知，从而避免无效的等待，充分利用CPU资源。

阶段一：

• 用户进程调用select，指定要监听的FD集合
• 核监听FD对应的多个socket
• 任意一个或多个socket数据就绪则返回readable
• 此过程中用户进程阻塞

阶段二：

• 用户进程找到就绪的socket
• 依次调用recvfrom读取数据
• 内核将数据拷贝到用户空间
• 用户进程处理数据

当用户去读取数据的时候，不再去直接调用recvfrom了，而是调用select的函数，select函数会将需要监听的数据交给内核，由内核去检查这些数据是否就绪了，如果说这个数据就绪了，就会通知应用程序数据就绪，然后来读取数据，再从内核中把数据拷贝给用户态，完成数据处理，如果N多个FD一个都没处理完，此时就进行等待。

用IO复用模式，可以确保去读数据的时候，数据是一定存在的，他的效率比原来的阻塞IO和非阻塞IO性能都要高

2.4.2 IO多路复用的三种方式

2.4.2.1 概念

IO多路复用是利用单个线程来同时监听多个FD，并在某个FD可读、可写时得到通知，从而避免无效的等待，充分利用CPU资源。不过监听FD的方式、通知的方式又有多种实现，常见的有：

• select
• poll
• epoll

其中select和pool相当于是当被监听的数据准备好之后，他会把你监听的FD整个数据都发给你，你需要到整个FD中去找，哪些是处理好了的，需要通过遍历的方式，所以性能也并不是那么好

而epoll，则相当于内核准备好了之后，会把准备好的数据直接拷贝到用户空间，省去用户程序的查找遍历的动作。

2.4.2.2 select模式

select是Linux最早是由的I/O多路复用技术：

简单说，就是我们把需要处理的数据封装成FD，然后在用户态时创建一个fd的集合（这个集合的大小是要监听的那个FD的最大值+1，但是大小整体是有限制的 ），这个集合的长度大小是有限制的，同时在这个集合中，标明出来我们要控制哪些数据，

比如要监听的数据，是1,2,5三个数据，此时会执行select函数，然后将整个fd发给内核态，内核态会去遍历用户态传递过来的数据，如果发现这里边都数据都没有就绪，就休眠，直到有数据准备好时，就会被唤醒，唤醒之后，再次遍历一遍，看看谁准备好了，然后再将处理掉没有准备好的数据，最后再将这个FD集合写回到用户态中去，此时用户态就知道了，奥，有人准备好了，但是对于用户态而言，并不知道谁处理好了，所以用户态也需要去进行遍历，然后找到对应准备好数据的节点，再去发起读请求，我们会发现，这种模式下他虽然比阻塞IO和非阻塞IO好，但是依然有些麻烦的事情， 比如说频繁的传递fd集合，频繁的去遍历FD等问题

2.4.2.3 poll模式

poll模式对select模式做了简单改进，但性能提升不明显，部分关键代码如下：

IO流程：

• 创建pollfd数组，向其中添加关注的fd信息，数组大小自定义
• 调用poll函数，将pollfd数组拷贝到内核空间，转链表存储，无上限
• 内核遍历fd，判断是否就绪
• 数据就绪或超时后，拷贝pollfd数组到用户空间，返回就绪fd数量n
• 用户进程判断n是否大于0,大于0则遍历pollfd数组，找到就绪的fd

与select对比：

• select模式中的fd_set大小固定为1024，而pollfd在内核中采用链表，理论上无上限
• 监听FD越多，每次遍历消耗时间也越久，性能反而会下降

2.4.2.4 epoll模式(重要)

2.4.2.4.1 epoll模式的执行流程

epoll模式是对select和poll的改进，它提供了三个函数：

第一个是：

eventpoll的函数，他内部包含两个东西

一个是：

1、红黑树-> 记录的事要监听的FD

2、一个是链表->一个链表，记录的是就绪的FD

紧接着调用epoll_ctl函数操作，将要监听的数据添加到红黑树上去，并且给每个fd设置一个监听函数，这个函数会在fd数据就绪时触发，就是准备好了，现在就把fd把数据添加到list_head中去

3、调用epoll_wait函数

就去等待，在用户态创建一个空的events数组，当就绪之后，我们的回调函数会把数据添加到list_head中去，当调用这个函数的时候，会去检查list_head，当然这个过程需要参考配置的等待时间，可以等一定时间，也可以一直等， 如果在此过程中，检查到了list_head中有数据会将数据添加到链表中，此时将数据放入到events数组中，并且返回对应的操作的数量，用户态的此时收到响应后，从events中拿到对应准备好的数据的节点，再去调用方法去拿数据。

2.4.2.4.2 epoll中的ET和LT

当FD有数据可读时，我们调用epoll_wait（或者select、poll）可以得到通知。但是事件通知的模式有两种：

• LevelTriggered：简称LT，也叫做水平触发。只要某个FD中有数据可读，每次调用epoll_wait都会得到通知。(默认模式)
• EdgeTriggered：简称ET，也叫做边沿触发。只有在某个FD有状态变化时，调用epoll_wait才会被通知。

举个栗子：

• 假设一个客户端socket对应的FD已经注册到了epoll实例中
• 客户端socket发送了2kb的数据
• 服务端调用epoll_wait，得到通知说FD就绪
• 服务端从FD读取了1kb数据回到步骤3（再次调用epoll_wait，形成循环）

结论

如果我们采用LT模式，因为FD中仍有1kb数据，则第⑤步依然会返回结果，并且得到通知
如果我们采用ET模式，因为第③步已经消费了FD可读事件，第⑤步FD状态没有变化，因此epoll_wait不会返回，数据无法读取，客户端响应超时。

2.4.2.4.3 基于epoll的服务器端流程

服务器启动以后，服务端会去调用epoll_create，创建一个epoll实例，epoll实例中包含两个数据

1、红黑树（为空）：rb_root 用来去记录需要被监听的FD

2、链表（为空）：list_head，用来存放已经就绪的FD

创建好了之后，会去调用epoll_ctl函数，此函数会会将需要监听的数据添加到rb_root中去，并且对当前这些存在于红黑树的节点设置回调函数，当这些被监听的数据一旦准备完成，就会被调用，而调用的结果就是将红黑树的fd添加到list_head中去(但是此时并没有完成)

3、当第二步完成后，就会调用epoll_wait函数，这个函数会去校验是否有数据准备完毕（因为数据一旦准备就绪，就会被回调函数添加到list_head中），在等待了一段时间后(可以进行配置)，如果等够了超时时间，则返回没有数据，如果有，则进一步判断当前是什么事件，如果是建立连接时间，则调用accept() 接受客户端socket，拿到建立连接的socket，然后建立起来连接，如果是其他事件，则把数据进行写出

2.4.2.5 总结：

select模式存在的三个问题：

• 能监听的FD最大不超过1024
• 每次select都需要把所有要监听的FD都拷贝到内核空间
• 每次都要遍历所有FD来判断就绪状态

poll模式的问题：

• poll利用链表解决了select中监听FD上限的问题，但依然要遍历所有FD，如果监听较多，性能会下降

epoll模式中如何解决这些问题的？

• 基于epoll实例中的红黑树保存要监听的FD，理论上无上限，而且增删改查效率都非常高
• 每个FD只需要执行一次epoll_ctl添加到红黑树，以后每次epol_wait无需传递任何参数，无需重复拷贝FD到内核空间
• 利用ep_poll_callback机制来监听FD状态，无需遍历所有FD，因此性能不会随监听的FD数量增多而下降

2.5 信号驱动IO模型

信号驱动IO是与内核建立SIGIO的信号关联并设置回调，当内核有FD就绪时，会发出SIGIO信号通知用户，期间用户应用可以执行其它业务，无需阻塞等待。

阶段一：

• 用户进程调用sigaction，注册信号处理函数
• 内核返回成功，开始监听FD
• 用户进程不阻塞等待，可以执行其它业务
• 当内核数据就绪后，回调用户进程的SIGIO处理函数

阶段二：

• 收到SIGIO回调信号
• 调用recvfrom，读取
• 内核将数据拷贝到用户空间
• 用户进程处理数据

当有大量IO操作时，信号较多，SIGIO处理函数不能及时处理可能导致信号队列溢出，而且内核空间与用户空间的频繁信号交互性能也较低。

2.6 异步IO

这种方式，不仅仅是用户态在试图读取数据后，不阻塞，而且当内核的数据准备完成后，也不会阻塞

他会由内核将所有数据处理完成后，由内核将数据写入到用户态中，然后才算完成，所以性能极高，不会有任何阻塞，全部都由内核完成，可以看到，异步IO模型中，用户进程在两个阶段都是非阻塞状态。

2.7 五种IO模型的比较

五、Redis的线程模型

Redis到底是单线程还是多线程？

• 如果仅仅聊Redis的核心业务部分（命令处理），答案是单线程
• 如果是聊整个Redis，那么答案就是多线程

在Redis版本迭代过程中，在两个重要的时间节点上引入了多线程的支持：

• Redis v4.0：引入多线程异步处理一些耗时较旧的任务，例如异步删除命令unlink
• Redis v6.0：在核心网络模型中引入 多线程，进一步提高对于多核CPU的利用率

因此，对于Redis的核心网络模型，在Redis 6.0之前确实都是单线程。是利用epoll（Linux系统）这样的IO多路复用技术在事件循环中不断处理客户端情况。

为了提升网络 IO 的读写性能，Redis 在6.0推出了多线程，通过多线程的 IO 来处理网络请求。不过需要注意的是这里的多线程仅仅是针对客户端的读写是并行的，Redis 处理事件队列中的命令，还是单线程处理的。

为什么Redis要选择单线程？

• 抛开持久化不谈，Redis是纯 内存操作，执行速度非常快，使用 Redis 时，几乎不存在 CPU 成为瓶颈的情况， Redis 主要受限于内存和网络。随着硬件水平的提升，Redis 中的性能慢慢主要出现在网络 IO 的读写上。虽然采用 IO 多路复用机制，但是读写客户端数据依旧是同步IO，只能单线程依次读取客户端的数据，无法利用到CPU多核。它的性能瓶颈是网络延迟而不是执行速度，因此多线程并不会带来巨大的性能提升。因为CPU 不是瓶颈，那么自然就采用单线程的解决方案了
• 多线程会导致过多的上下文切换，带来不必要的开销
• 引入多线程会面临线程安全问题，必然要引入线程锁这样的安全手段，实现复杂度增高，而且性能也会大打折扣

当我们的客户端想要去连接我们服务器，会去先到IO多路复用模型去进行排队，会有一个连接应答处理器，他会去接受读请求，然后又把读请求注册到具体模型中去，此时这些建立起来的连接，如果是客户端请求处理器去进行执行命令时，他会去把数据读取出来，然后把数据放入到client中， clinet去解析当前的命令转化为redis认识的命令，接下来就开始处理这些命令，从redis中的command中找到这些命令，然后就真正的去操作对应的数据了，当数据操作完成后，会去找到命令回复处理器，再由他将数据写出。

六、参考资料

小林图解Redis介绍

博文：Redis为什么这么快

京东技术面：Redis是如何保证高效查询的？

黑马程序员Redis入门与实战

黑马《Redis入门到实战教程》
在线学习：https://www.bilibili.com/video/BV1cr4y1671t/
资料领取：
https://pan.baidu.com/s/1189u6u4icQYHg_9_7ovWmA?pwd=eh11
提取码：eh11

思考：Redis为什么快？

1、基于内存实现(最关键)

Redis 是一种基于内存的数据库，对数据的读写操作都是在内存中完成，因此读写速度非常快。与磁盘数据库相比，如Mysql数据库，是需要把数据先从磁盘中读取到内存，这个过程中会有磁盘I/O的限制。

2、不同的Redis数据类型应用了不同的底层数据结构

3、使用了IO多路复用模型

• Redis 采用了 I/O 多路复用机制处理大量的客户端 Socket 请求，IO 多路复用机制是指一个线程处理多个 IO 流，就是我们经常听到的 select/epoll 机制。简单来说，在 Redis 只运行单线程的情况下，该机制允许内核中，同时存在多个监听 Socket 和已连接 Socket。内核会一直监听这些 Socket 上的连接请求或数据请求。一旦有请求到达，就会交给 Redis 线程处理，这就实现了一个 Redis 线程处理多个 IO 流的效果。

4、Redis 中是单线程（引入了多线程，但核心内存读写仍为单线程）

• 为什么Redis要选择单线程

5、用多线程处理后台程序，如内存淘汰、删除BigKey、持久化等等耗费时间的任务