Redis 底层结构

BigKey

是什么？

BigKey通常以Key的大小和Key中成员的数量来综合判定，例如：

Key本身的数据量过大：一个String类型的Key，它的值为5 MB。
Key中的成员数过多：一个ZSET类型的Key，它的成员数量为10,000个。
Key中成员的数据量过大：一个Hash类型的Key，它的成员数量虽然只有1,000个但这些成员的Value（值）总大小为100 MB。

推荐值：

单个key的value小于10KB
对于集合类型的key，建议元素数量小于1000

有什么危害？

网络阻塞

对BigKey执行读请求时，少量的QPS就可能导致带宽使用率被占满，导致Redis实例，乃至所在物理机变慢

数据倾斜

BigKey所在的Redis实例内存使用率远超其他实例，无法使数据分片的内存资源达到均衡

Redis阻塞

对元素较多的hash、list、zset等做运算会耗时较旧，使主线程被阻塞

CPU压力

对BigKey的数据序列化和反序列化会导致CPU的使用率飙升，影响Redis实例和本机其它应用

怎么识别？

redis-cli –bigkeys

利用redis-cli提供的–bigkeys参数，可以遍历分析所有key，并返回Key的整体统计信息与每个数据的Top1的big key

scan扫描

自己编程，利用scan扫描Redis中的所有key，利用strlen、hlen等命令判断key的长度（此处不建议使用MEMORY USAGE）

第三方工具

利用第三方工具，如 Redis-Rdb-Tools 分析RDB快照文件，全面分析内存使用情况

网络监控

自定义工具，监控进出Redis的网络数据，超出预警值时主动告警

如何删除？

BigKey内存占用较多，即便时删除这样的key也需要耗费很长时间，导致Redis主线程阻塞，引发一系列问题。

redis 3.0 及以下版本

如果是集合类型，则遍历BigKey的元素，先逐个删除子元素，最后删除BigKey

Redis 4.0以后

Redis在4.0后提供了异步删除的命令：unlink

底层数据结构

动态字符串SDS

Redis并未使用C语言的字符串，因为存在一些问题：

获取字符串长度需要运算
非二进制安全
不可修改

因此Redis自己优化了字符串结构，为简单动态字符串（Simple Dynamic String），简称SDS。

我们在最初学习Redis时，会操作：set key value, 底层实际上创建了两个SDS，一个包含 key，一个包含 value。

我们看到它提到了动态字符串，那相应应该有动态扩容的能力，假如我们要给SDS追加一段字符串“,Amy”，这里首先会申请新内存空间：

如果新字符串小于1M，则新空间为扩展后字符串长度的两倍+1；
如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1。称为内存预分配。

优点：

获取字符串长度为 O(1)
支持动态扩容
减少内存分配次数
二进制安全

IntSet

IntSet 是Redis的Set结构的一种实现方式，基于整数数组来实现，并且长度可变，有序。

为了方便查找，本身按照整数进行升序存储保存到content[]内

假设最初存储元素：{5,10,20}采用的编码是INTSET_ENC_INT16，则每个整数占2字节。

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

升级编码为INTSET_ENC_INT32, 每个整数占4字节，并按照新的编码方式及元素个数扩容数组
倒序依次将数组中的元素拷贝到扩容后的正确位置（倒序保证，之前节点不会被覆盖）

新增流程

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);// 获取当前值编码
    uint32_t pos; // 要插入的位置
    if (success) *success = 1;
    // 判断编码是不是超过了当前intset的编码
    if (valenc > intrev32ifbe(is->encoding)) {
        // 超出编码，需要升级
        return intsetUpgradeAndAdd(is,value);
    } else {
        // 在当前intset中查找值与value一样的元素的角标pos
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0; //如果找到了，则无需插入，直接结束并返回失败
            return is;
        }
        // 数组扩容
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        // 移动数组中pos之后的元素到pos+1，给新元素腾出空间
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }
    // 插入新元素
    _intsetSet(is,pos,value);
    // 重置元素长度
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

升级流程

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    // 获取当前intset编码
    uint8_t curenc = intrev32ifbe(is->encoding);
    // 获取新编码
    uint8_t newenc = _intsetValueEncoding(value);
    // 获取元素个数
    int length = intrev32ifbe(is->length); 
    // 判断新元素是大于0还是小于0 ，小于0插入队首、大于0插入队尾
    int prepend = value < 0 ? 1 : 0;
    // 重置编码为新编码
    is->encoding = intrev32ifbe(newenc);
    // 重置数组大小
    is = intsetResize(is,intrev32ifbe(is->length)+1);
    // 倒序遍历，逐个搬运元素到新的位置，_intsetGetEncoded按照旧编码方式查找旧元素
    while(length--) // _intsetSet按照新编码方式插入新元素
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
    /* 插入新元素，prepend决定是队首还是队尾*/
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    // 修改数组长度
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

总结：

底层为整数数组，也就是一块儿完整的内存
内部元素，唯一，有序。
具备类型升级（倒序扩容）。
底层采用二分查找。（因为有序）

Dict

我们知道Redis中是Key-Value结构，在Java中类似的也有Map结构，能够快速的进行增删改查，底层一定是有关系的映射。Redis正是基于Dict实现的。

Dict有三个部分：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

typedef struct dictht {
    // entry数组
    // 数组中保存的是指向entry的指针
    dictEntry **table; 
    // 哈希表大小
    unsigned long size;     
    // 哈希表大小的掩码，总等于size - 1
    unsigned long sizemask;     
    // entry个数
    unsigned long used; 
} dictht;

typedef struct dictEntry {
    void *key; // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; // 值
    // 下一个Entry的指针
    struct dictEntry *next; 
} dictEntry;

typedef struct dict {
    dictType *type; // dict类型，内置不同的hash函数
    void *privdata;     // 私有数据，在做特殊hash运算时用
    dictht ht[2]; // 一个Dict包含两个哈希表，其中一个是当前数据，另一个一般是空，rehash时使用
    long rehashidx;   // rehash的进度，-1表示未进行
    int16_t pauserehash; // rehash是否暂停，1则暂停，0则继续
} dict;

我们可以看到Dict中有两个dictht，第一个负责存储值，第二个负责reHash。也就是当节点个数过多时，需要进行扩容，在Java的Map中，当数组中一个链表的长度大于8，就会进行数组扩容，否则查找遍历太慢。这里的原理是类似的。

dictht内部是dictEntry数组，dictEntry含有指向下一个节点的指针。

Dict扩容

这里还是有Java中Map举例，HashMap默认还有加载因子为0.75，也就是说不等我们把空间使用完，底层就会判断如果当前节点数/容量数大于0.75，会频繁导致Hash碰撞，并且链表长度太长，所以需要扩容。

Dict在每次新增键值对时都会检查负载因子（LoadFactor = used/size），满足以下两种情况时会触发哈希表扩容：

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

static int _dictExpandIfNeeded(dict *d){
    // 如果正在rehash，则返回ok
    if (dictIsRehashing(d)) return DICT_OK;    // 如果哈希表为空，则初始化哈希表为默认大小：4
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
    // 当负载因子（used/size）达到1以上，并且当前没有进行bgrewrite等子进程操作
    // 或者负载因子超过5，则进行 dictExpand ，也就是扩容
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio){
        // 扩容大小为used + 1，底层会对扩容大小做判断，实际上找的是第一个大于等于 used+1 的 2^n
        return dictExpand(d, d->ht[0].used + 1);
    }
    return DICT_OK;
}

Dict收缩

Dict除了扩容以外，每次删除元素时，也会对负载因子做检查，当LoadFactor < 0.1 时，会做哈希表收缩：

// t_hash.c # hashTypeDeleted() 
...
if (dictDelete((dict*)o->ptr, field) == C_OK) {
    deleted = 1;
    // 删除成功后，检查是否需要重置Dict大小，如果需要则调用dictResize重置    /* Always check if the dictionary needs a resize after a delete. */
    if (htNeedsResize(o->ptr)) dictResize(o->ptr);
}
...
// server.c 文件
int htNeedsResize(dict *dict) {
    long long size, used;
    // 哈希表大小
    size = dictSlots(dict);
    // entry数量
    used = dictSize(dict);
    // size > 4（哈希表初识大小）并且 负载因子低于0.1
    return (size > DICT_HT_INITIAL_SIZE && (used*100/size < HASHTABLE_MIN_FILL));
}
...
int dictResize(dict *d){
    unsigned long minimal;
    // 如果正在做bgsave或bgrewriteof或rehash，则返回错误
    if (!dict_can_resize || dictIsRehashing(d)) 
        return DICT_ERR;
    // 获取used，也就是entry个数
    minimal = d->ht[0].used;
    // 如果used小于4，则重置为4
    if (minimal < DICT_HT_INITIAL_SIZE)
        minimal = DICT_HT_INITIAL_SIZE;
    // 重置大小为minimal，其实是第一个大于等于minimal的2^n
    return dictExpand(d, minimal);
}

Dict的ReHash

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

计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：

如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n
如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）

按照新的realeSize申请内存空间，创建dictht，并赋值给dict.ht[1]
设置dict.rehashidx = 0，标示开始rehash
将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]
将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存

如果Key中的节点过多，那一次性进行Rehash就有可能导致主线程阻塞，怎么解决？

将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存

计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：

如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n
如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）

按照新的size申请内存空间，创建dictht，并赋值给dict.ht[1]
设置dict.rehashidx = 0，标示开始rehash
每次执行新增、查询、修改、删除操作时，都检查一下dict.rehashidx是否大于-1，如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1]，并且将rehashidx++。直至dict.ht[0]的所有数据都rehash到dict.ht[1]
将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存
将rehashidx赋值为-1，代表rehash结束
在rehash过程中，新增操作，则直接写入ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增，随着rehash最终为空

总结：

Dict的结构：

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

Dict的伸缩：

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

ZipList

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

ZipList说是特殊的来链表，但实际上并不是通过指针连接的，因为占用内存，所以Entry的结构是：

因为是一块儿内存，每个节点记录了前一个节点的长度，就可以计算出各个节点的位置。

这里有一个连锁更新（Cascade Update）的问题，但作者并未修改，因为发生的概率极低、

假设我们有N个连续的、长度为250~253字节之间的entry，因此entry的previous_entry_length属性用1个字节即可表示，如图所示：

现在在头位置插入一个新的节点，长度为254，则原先的头结点的previous_entry_length就会用5个字节来存储，那么该节点本身的长度就超过了254，则后续所有节点都必须更新。

总结：

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

QuickList

上面我们学习了ZipList，虽然好操作，但因为是连续的空间，所以如果长度太长，也会影响效率，并且申请更多的连续空间，

所以我们必须限制ZipList的长度和entry大小。

如果ZipList超出上线怎么办？

利用分片思想，形成多个ZipList，但分散后又不方便管理，则推出了：QuickList。它是一个双端链表，只不过链表中的每个节点都是一个ZipList。

为了避免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

默认值：config get list-max-ziplist-size

除了控制ZipList的大小，QuickList还可以对节点的ZipList做压缩。通过配置项list-compress-depth来控制。因为链表一般都是从首尾访问较多，所以首尾是不压缩的。这个参数是控制首尾不压缩的节点个数：

0：特殊值，代表不压缩
1：标示QuickList的首尾各有1个节点不压缩，中间节点压缩
2：标示QuickList的首尾各有2个节点不压缩，中间节点压缩
以此类推

默认值：config get list-compress-depth

源码：

特点：

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

kipList

原有链表的一个问题，就是查找元素时，需要一个个遍历，每个节点有一个指针指向下一个元素，那能不能多加几个指针？

跳表的结构图：

可以看到跳表的一个特性就是有序，如果无序，则多出来的指针没有意义。

总结：

跳跃表是一个双向链表，每个节点都包含score和ele值
节点按照score值排序，score值一样则按照ele字典排序
每个节点都可以包含多层指针，层数是1到32之间的随机数
不同层指针到下一个节点的跨度不同，层级越高，跨度越大
增删改查效率与红黑树基本一致，实现却更简单

RedisObject

Redis中的任意数据类型(String,List,Set,Hash,ZSet)都会被封装为RedisObject对象。

底层编码方式

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

五种数据类型的底层类型：

数据类型	编码方式
OBJ_STRING	int、embstr、raw
OBJ_LIST	LinkedList和ZipList(3.2以前)、QuickList（3.2以后）
OBJ_SET	intset、HT
OBJ_ZSET	ZipList、HT、SkipList
OBJ_HASH	ZipList、HT

五种数据类型

String

我们知道底层是通过SDS结构，但不同的SDS长度会使用不同的编码。

如果存储的是字符串是整数值，大小在Long_MAX范围内，则会使用INT编码，直接将数据保存在RedisObject的ptr指针位置（刚好8字节），不再需要SDS了。

如果存储的SDS长度小于44字节，则会采用EMBSTR编码，此时object head与SDS是一段连续空间。申请内存时只需要调用一次内存分配函数，效率更高。

否则用的就是raw编码了，SDS单独占一个内存，RedisObject用指针连接

List

我们可以自己想一想，底层结构中哪个合适?

List操作需要可以从两端插入或弹出，范围读取。

SDS是字符串（❎），intSet是完整的内存，支持有序，唯一（❎），Dict无法双端操作（❎）

ZipList：完整内存，双端操作，范围读取（✅）

QuickList：LinkedList + ZipList，可以从双端访问，内存占用较低，包含多个ZipList，存储上限高（✅）

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

Set

Set需要元素唯一（可判断是否元素存在），不保证有序，求交集，并集，差集，也就是对查询效率要求很高

我们能想到Java中，利用Map实现Set结构，Value存Null，那在Redis中应该也可以，所以Dict(✅)

IntSet内部是整数数组，不过可以保证唯一，且有序，二分查询也快。当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries时，Set会采用IntSet编码，以节省内存，IntSet(✅)

ZSet

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

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

那想到第一个应该是Dict结构，key为member，value为score，可以保证member唯一，✅
然后有分数的就是SkipList，可以排序，并且可以同时存储score和ele值（member）✅
当元素数量不多时，HT和SkipList的优势不明显，而且更耗内存。因此zset还会采用ZipList结构来节省内存，不过需要同时满足两个条件：✅
1. 元素数量小于zset_max_ziplist_entries，默认值128
2. 每个元素都小于zset_max_ziplist_value字节，默认值64

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

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

Hash

需求：

键值存储
根据键获取值
键唯一

我们发现与Zset需求很相似

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

因此，Hash底层采用的编码与Zset也基本一致，只需要把排序有关的SkipList去掉即可。也就是剩下ZipList和Dict

Hash结构默认采用ZipList编码，用以节省内存。 ZipList中相邻的两个entry 分别保存field和value ✅
当数据量较大时，Hash结构会转为HT编码，也就是Dict，触发条件有两个： ✅
- ZipList中的元素数量超过了hash-max-ziplist-entries（默认512）
- ZipList中的任意entry大小超过了hash-max-ziplist-value（默认64字节）