Redis 原理

动态字符串SDS

Redis中保存的key时字符串，value往往是字符串或字符串集合，字符串是Redis中常见的数据结构
Redis没有直接使用C语言中的字符串，因为C语言字符串存在很多问题，使用起来不方便

Redis构建了一种新型的字符串数据结构，称为简单动态字符串（Simple Dynamic String），简称SDS，是使用C语言实现的结构体

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; //buf已保存的字符串长度，不包含结束标识‘\0’
    uint8_t alloc; //buf申请的总的字节数，不包含结束标识
    unsigned char flages; //不同SDS的头类型，用来控制SDS的头大小有 8为、16为、32为、64为
    char buf[];
};

SDS具备自动扩容能力，如果要在原字符串基础上追加字符串，首先会申请内存空间，如果新字符串小于1M，则新空间为扩展后字符串的两倍+1；如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1，称为内存预分配。
优点：获取字符串长度的时间复杂度为O(1)、支持动态扩容、减少内存分配次数、二进制安全

IntSet

IntSet是Redis中Set集合的一种实现方式，基于整数数组来实现，具备长度可变、有序等特性

typedef struct intset {
  	uint32_t encoding; //编码格式,存放格式包括：16位、32位、64位整数
    uint32_t length; //元素个数
    int8_t contents[]; //整型数组，保存集合数据
} intset;

为了方便查找，Redis会将IntSet中所有的整数按升序排列，保存在contents数组中
如果添加的元素超过了存储范围，intSet会自动升级编码格式，找到合适大小，并按照新的编码方式及元素个数扩容数组，倒序依次将数组中的数据拷贝到扩容后的正确位置，并将待添加的数据放入数组末尾
intSet特点：确保元素的唯一、有序性；具备类型升级机制，可以节省内存空间；底层采用二分查找方式查询；
因为intSet采用数组，内存空间是连续的，在数据量较大的时候，是不方便的，查找效率也会下降，所以适合在数据量较小时使用

Dict 字典

Redis是一个键值型的数据库，然后根据键实现快速的增删改查，而键值的映射关系是通过Dict实现的

Dict有三部分组成：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）；与HashMap思想类似

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

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

当向Dict中添加键值对时，Redis首先根据key计算出hash值h，然后利用h & sizemask（和取余效果相同）来计算元素应该存储到数组中的哪个索引位置

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

Dict扩容及rehash

当集合元素较多时，导致哈希表冲突增多，链表过长，查询效率降低
Dict在每次新增键值对时都会检查负载因子（LoadFactor=used/size），满足一下两种情况会触发哈希表扩容：
- 哈希表 LoadFactor >= 1 ，并且服务器没有执行 bgsave 或 bgrewriteaof 等后台进程
- 哈希表 LoadFactor >= 5
扩容也会扩容到大于容量最小的2的n次方
Dict除了扩容，每次删除元素时，也会对负载因子做检查，当LoadFactor<0.1时，会做哈希表收缩
rehash并不是一次性完成的，因为dict的数据量如果是百万级别的Entry，依次rehash极有可能导致主线程阻塞，因此采用渐进式的rehash过程
- 不管扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询跟sizemask有关，因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表
- 首先会计算hash表的realSize，值取决于扩容还是收缩
- 按照新的realSize申请空间，创建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最终清空

ZipList

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

在这里插入图片描述

ZipList 中的Entry并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用16字节，浪费内存，而是采用下面的结构：
- previous_entry_length：前一节点的长度，占用1个或5个字节
- encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节
- content：负责保存节点数据，可以是字符串或整数
特点：
- 压缩列表可以看做是一种连续内存空间的“双向链表”
- 列表之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低
- 如果列表数据过多，导致链表过长，可能影响查询性能
- 增或删较大数据时有可能发生连续更新问题

QuickList

ZipList虽然节省内存，但申请内存空间必须是连续的，如果内存占用较多，申请内存效率很低，该怎么办？
在Redis3.2中，引入了新的数据结构QuickList，他是一个双端链表，只不过链表中的每一个节点都是一个ZipList
QuickList特点：
- 是一个节点为ZipList的双端链表
- 节点采用ZipList，解决了传统链表的内存占用问题
- 控制了ZipList大小，解决连续内存空间申请效率问题
- 中间节点可以压缩，进一步节省内存

SkipList

在这里插入图片描述

SkipList称为跳表，它是一种链表，但与传统的链表相比有几点差异：

元素按照升序排列存储
节点可能包含多个指针，指针跨度不同

特点：

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

RedisObject

Redis中任意数据类型的键值都会被封装为一个RedisObject，也叫Redis对象，不包含数据时占16字节

typedef struct redisObject {
    unsigned type:4; //对象类型，分别是string hash list set zset，占4个bit位
    unsigned encoding:4; //底层编码方式，有11中，占4bit位
    unsigned lru:LRU_BITS; //lru表示该对象最后一次被访问的时间，占24bit位
    int refcount; //引用计数器，计数器为0表示无引用，可以被回收
    void *ptr; //指针，指向存放实际数据的空间
} robj;

Redis中会根据存储的数据不同，选择不同的数据类型，选择不同的编码格式：

数据类型	编码格式
string	int、embstr、raw
list	linkedList和ZipList（3.2以前）、QuickList（3.2以后）
set	intset、hashTable（Dict）
zset	ZipList、hashTable+SkipList
hash	ZipList、hashTable

Redis 内存回收

Redis是基于内存存储，单节点Redis内存不宜过大，会影响持久化或者主从同步性能，可以修改配置文件来设置Redis的最大内存：

maxmemory 1gb; #最大内存为 1gb

Redis 过期策略

通过expire命令给Redis的key设置TTL（存活时间），当key的TTL到期之后，对应的内存也得到释放

DB结构：Redis本身是一个典型的key-value内存存储数据库，因此所有的key、value都保存在Dict结构中，不过在database结构体中，有两个Dict：一个用来记录key-value；另一个记录key-TTL

在这里插入图片描述

typedef struct redisDb {
    dict *dict; //存放了所有key及value，也称keyspace
    dict *expires; //存放每一个key的ttl存活时间，只包含设置了ttl的key
    dict *blocking_keys;
    dict *ready_keys;
    dict *watched_keys;
    int id;
    long long avg_ttl;
    unsigned long expires_cursor;
    list *defrag_later;
} redisDb;