Redis五种数据类型的底层结构

RedisObject:

Redis 中只有一个 K，一个 V。其中 K 绝对是字符串对象，而 V 可以是 String、List、Hash、Set、ZSet 任意一种。

typedef struct redisObject {
    // 类型 string list set hash zset等 4bit
    unsigned type:4;
    // 编码方式 4bit
    unsigned encoding:4;
    // LRU 时间 24bit
    unsigned lru:LRU_BITS; 
    // 引用计数  4byte
    int refcount;
    // 指向对象的指针  8byte	指针指向具体的数据，如set test hello，ptr指向的就是存储hello的字符串。
    void *ptr;
} robj;

encoding：

/*
* 对象编码
*/
#define REDIS_ENCODING_RAW 0    // 编码为字符串
#define REDIS_ENCODING_INT 1    // 编码为整数
#define REDIS_ENCODING_HT 2     // 编码为哈希表
#define REDIS_ENCODING_ZIPMAP 3 // 编码为 zipmap(2.6 后不再使用)
#define REDIS_ENCODING_LINKEDLIST 4 // 编码为双端链表
#define REDIS_ENCODING_ZIPLIST 5    // 编码为压缩列表
#define REDIS_ENCODING_INTSET 6     // 编码为整数集合
#define REDIS_ENCODING_SKIPLIST 7    // 编码为跳跃表

lru

记录对象最后一次被命令程序访问的时间，通过lru时间和当前时间可以计算某个对象的空转时间；利用object idletiem命令可以显示空转时间(单位为秒)，且不会改变该对象的lru。
refcount

该对象被引用的次数，目前共享对象只支持整数值的字符串对象。

1.String

三种编码方式：

int：存储的字符串全是数字
embstr：存储的字符串长度小于44个字符
raw：存储的字符串长度大于44个字符

embstr类型，它的数据指针和SDS对象在内存地址是连在一起的；但对于raw类型，二者在内存地址不是连续的。

SDS封装char[]，一个SDS最大512M

struct sdshdr{  
	unsigned int len; // 标记char[]的长度  
	unsigned int free; //标记char[]中未使用的元素个数  
	char buf[]; // 存放元素的坑
}

Redis底层对SDS做的优化

预空间分配

SDS长度(len的值)小于1MB，那么程序将分配和len属性同样大小的未使用空间，此时 free和len属性值相同。假如SDS的len将变成15字节，则程序也会分配15字节的未使用空间，SDS的buf数组的实际长度变为15+15+1=31字节(额外一个字节用户保存空字符串)

SDS长度(len的值)大于等于1MB，程序会分配1MB的未使用空间。如进行修改之后，SDS的len变成30MB，那么它的实际长度为30MB+1MB+1byte
惰性释放空间

当执行sdstrim(截取字符串)之后，SDS不会立即释放多出来的空间，如果下次在进行字符串拼接操作，且拼接的没有刚才释放的大，就会使用刚才的空间，不需要再重新申请空间。
二进制安全

C语言通过是否存在空字符\0来判断是否已经是字符串的结尾。某些情况下(如使用空格进行分割一段字符串、或图片、视频等二进制文件)时，就会出现问题。SDS通过len字段判断，因此具备二进制安全性。

2.List

quickList(快速列表，是zipList压缩列表和linkedList双端链表的组合)，最大长度2^32-1，自测两端插入和弹出，并可以获得指定位置(或范围)的元素，可以充当数组、队列和栈。

lpush+lpop 先进后出的栈
lpush+rpop 先进先出的队列
lpush+ltrim 有限集合
lpush+Brpop 消息队列

linkedList

//定义链表节点的结构体 
typedef struct listNode {
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
 }
typedef struct list{
    //表头节点
    listNode *head;
    //表尾节点
    listNode *tail;
    //链表包含节点的数量
    unsigned long len;
    //节点复制函数，用于链表转移复制时对节点value拷贝的实现，一般情况下使用等号，某些特殊情况下给这个函数赋值NULL即表示使用等号进行节点转移
    vode *(*dup) (void *ptr);
    //节点释放函数，用于释放一个节点所占用的内存空间，默认赋值NULL，即使用Redis自带的zfree函数进行内存空间释放
    vode *(*free) (void *ptr);
    //节点对比函数，用于对比两个链表节点的value是否相等，相等返回1，不相等返回0
    vode *(*match) (void *ptr,void *key);
}

获取前置节点、后置节点、表头节点和表尾节点的复杂度都是O(1)，获取节点数量也是O(1)。与双端链表相比，压缩列表可以节省空间，但进行修改或增删操作时，复杂度较高；因此节点数量较少时，可以使用压缩列表，但节点数量较多时，还是使用双端链表。

zipList

typedf struct ziplist<T>{
    //压缩列表占用字符数
    int32 zlbytes;
    //最后一个元素距离起始位置的偏移量，用于快速定位最后一个节点
    int32 zltail_offset;
    //元素个数
    int16 zllength;
    //元素内容
    T[] entries;
    //结束位 0xFF
    int8 zlend;
}ziplist
    
typede struct entry{
    //前一个entry的长度，倒序遍历可以通过这个参数定位到上一个entry的位置
    int<var> prelen;
    //元素类型编码
    int<var> encoding;
    //元素内容
    optional byte[] content;
}entry

zltail_offset这个参数可以快速定位到最后一个entry节点的位置，然后开始倒序遍历，即ziplist支持双向遍历。zipList遍历的时候，先根据zlbytes和zltail_offset定位到最后一个entry的位置，然后根据根据entry的prelen时确定前一个entry的位置。

zipList相比linkedList少了pre和next两个指针16个字节(64位系统1个指针就是8个字节)，linkedList每个节点内存都是单独分配，家具内存碎片化，zipList是由连续的内存组成的。

连锁更新

entry的prelen字段：前一个节点的长度小于254个字节时，prelen长度为1字节；前一个节点的长度大于254个字节时，prelen长度为5字节

假设现在有一组压缩列表，长度都在250~253字节之间，突然新增一个entry节点，这个entry节点长度大于等于254字节。由于新的entry节点大于等于254字节，这个entry节点的prelen为5个字节，随后会导致其余的所有entry节点的prelen增大为5字节；同样地，删除操作也会导致出现连锁更新这种情况。
zipList与linkedList的区别

当列表中元素的长度较小或数量较少时，通常采用zipList，当列表中元素长度较大或者数量较多时，使用linkedList
1. 双向链表linkedList便于在列表的两端进行push和pop，插入节点复杂度很低，但内存开销比较大。(额外保存prev和next指针；内存碎片)
2. zipList存储在一块连续的内存上，所以存储效率高，但插入和删除操作需要频繁的申请和释放内存。

3.2版本之后List使用quickList代替了zipList和linkedList，是zipList和linkedList的混合体。它将linkedList按段切分，每一段使用zipList来紧凑存储，多个zipList之间使用双向指针串接起来。

quickList内部默认单个zipList长度为8k字节，即redis.conf中list-max-ziplist-size的值为-2，超过这个阈值就会重新生成一个zipList来存储数据。当list-max-ziplist-size为正数n时，表示每个quicklist节点上的ziplist最多包含n个数据项。

压缩深度

quickList可以使用LZF算法对zipList进一步压缩，压缩后的zipList结构为
1
2
3
4
5
6
typedf struct ziplist_compressed{
//元素个数
int32 size;
//元素内容
byte[] compressed_data
}
此时quicList为：

redis.conf中list-compress-depth表示一个quickList两端不被压缩的节点的个数(指quickList双向链表节点个数，而不是zipList里数据项个数)，quickList默认压缩深度为0，即不开启压缩；当list-compress-depth为1，表示quickList的两端各有1个节点不进行压缩，中间节点进行压缩；当list-compress-dept为2，表示quickList的首尾各有2个节点不进行压缩，中间节点进行压缩；由此类推，对于quickList来说，首尾两个节点永远不会被压缩。

3.Hash

dict

底层可以是zipList或hashtable(字典也叫哈希表)，hash中元素数量小于512个且所有键值对的键和值字符串长度都小于64字节时，才会使用zipList。

typedf struct dict{
    dictType *type;//类型特定函数，包括一些自定义函数，这些函数使得key和value能够存储
    void *private;//私有数据
    dictht ht[2];//两张hash表 
    int rehashidx;//rehash索引，字典没有进行rehash时，此值为-1
    unsigned long iterators; //正在迭代的迭代器数量
}dict;

type和private这两个属性是为了实现字典多态而设置的，当字典中存放着不同类型的值，对于的一些复制、比较函数也不一样。
rehashidx，这是一个辅助变量，用于记录rehash过程的进度，以及是否正在进行rehash等信息，等于-1时，表示dict此时没有rehash过程。
iterators，记录此时dict有几个迭代器正在进行遍历过程。

dictht

dict本质上是对dicht的一个简单封装

typedf struct dictht{
    dictEntry **table;//存储数据的dicEntry类型的数组 二维
    unsigned long size;//数组的大小
    unsigned long sizemask;//哈希表的大小的掩码，用于计算索引值，总是等于size-1
    unsigned long used;//// 哈希表中中元素个数
}dictht;

dicthtEntry

typedf struct dictEntry{
    void *key;//键
    union{
        void val;
        unit64_t u64;
        int64_t s64;
        double d;
    }v;//值
    struct dictEntry *next；//指向下一个节点的指针
}dictEntry;

扩容与缩容

渐进式hash
1. 假设当前数据在dictht[0]中，那么首先未dictht[1]分配足够的空间，如果是扩容，则dictht[1]的大小按照扩容规则进行扩容，如果是缩减，则dictht[1]的大小按照缩减规则进行缩减。
2. 在字典dict中维护一个变量，rehashidx=0，表示rehash正式开始。
3. rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，还会顺带将dictht[0]哈希表在rehashidx索引上的所有键值对rehash到dichth[1]，当一次rehash工作完成之后，程序将rehashidx属性的值+1。同时在serverCron中调用rehash相关函数，在1ms的时间内，进行rehash处理，每次仅处理少量的转移任务(100个元素)。
4. 当dichth[0]的所有键值对都会被rehash至dichth[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。
- 每次对字典执行增删改查才会触发rehash，万一某段时间没有任何命令请求命令呢？
  
  Redis有一个定时器，会定时判断rehash是否完成，如果没有完成，则继续hash。
- 如果是添加操作，会将新的数据直接添加到dichth[1]上，而对于删除、更改、查询操作，会直接在dictht[0]上进行，当dictht[0]上查询不到时，会接着去dictht[1]上查找，如果再找不到，则表明不存在该K-V值。
- 优点：采用分而治之的思想，将rehash操作分散到每一次到hash表的操作上及定时函数上，避免了集中式hash带来的性能压力。
- 缺点：在rehash过程中，需要保存两个hash表，对内存的占用比较大，如果在Redis服务器本来内存满了的时候，突然进行rehash会造成大量的key被抛弃。

4.Set

无序且存储元素不重复。当value是整数时，且数据量不大时使用inset存储，其他情况用字典dict来存储。

inset

typedf struct inset{
    uint32_t encoding;//编码方式 有三种 默认 INSET_ENC_INT16 会根据插入数据的大小选择不一样的类型来存储
    uint32_t length;//集合元素个数
    int8_t contents[];//实际存储元素的数组，元素类型并不一定是ini8_t类型，柔性数组不占intset结构体大小，并且数组中的元素从小到大排列
}inset;
#define INTSET_ENC_INT16 (sizeof(int16_t))   //16位，2个字节，表示范围-32,768~32,767
#define INTSET_ENC_INT32 (sizeof(int32_t))   //32位，4个字节，表示范围-2,147,483,648~2,147,483,647
#define INTSET_ENC_INT64 (sizeof(int64_t))   //64位，8个字节，表示范围-9,223,372,036,854,775,808~9,223,372,036,854,775,807

inset升级过程
1. 了解旧的存储格式，计算出目前已有元素占用大小，计算规则是length*encoding，如4 * 16=64
2. 确定新的编码格式，当原有的编码格式不能存储下新增的数据时，此时就要选择新的合适的编码格式
3. 根据新的编码格式计算出需要新增的内存大小，然后从尾部将数据插入
4. 根据新的编码格式重置之前的值，此时contents存在两种编码格式的值，需要统一，从插入新数据的位置开始，从后向前将之前的数据按照新的编码格式进行移动和设置。从后往前是为了防止数据被覆盖。
  - 优点：根据存入的数据选择合适的编码方式，且只在必要的时候进行升级操作，节省内存。
  - 缺点：耗费系统资源，不支持降级。

5.SortedSet

常用作排行榜等功能，以用户id为value，关注事件或者分数作为score进行排序。zipList和skipList两种不同的实现：

zipList
- [score,value]键值对数量少于128个
- 每个元素的长度小于64字节
skipList

不满足以上两个条件时使用跳表、组合了hash和skipList，hash用来存储value到score的映射，这样就可以在O(1)时间内找到value对应的分数；skipList按照从小到大的顺序存储分数；skipList每个元素的值都是[score,value]对。

skipList

空间换时间

跳表一个节点最高可以达到64层，一个跳表中最多可以存储2^64个元素。跳表中，每个节点都是一个skipListNode，每个跳表的节点也都会维护一个score值，这个值在跳表中是按照从小到大的顺序排列好的。

typedf struct zskiplist{
    //头节点
    struct zskiplistNode *header;
    //尾节点
    struct zskiplistNode *tail;
    //跳表中元素个数
    unsigned long length;
    //目前表内节点的最大层数
    int level;
}zskiplist;

typedf struct zskiplistNode{
    sds ele;// 具体的数据 每个节点所保存的数据是唯一的，但节点的分数可以是一样的。两个相同分数的节点是按照元素的字典序进行排列的；
    double score;// 分数 从小到大排序
    struct zskiplistNode *backward;//后退指针，用于从表尾向表头遍历，每个节点只有一个，即每次只能后退一步
    struct zskiplistLevel{  
        struct zskiplistNode *forward;//前进指针forward，指向下一个节点
        unsigned int span;//跨度span用来计算当前节点在跳表中的一个排名
    }level[];//层级数组 最大32
}zskiplistNode;