前言
参考资料：《Redis设计与实现 第二版》；
本篇笔记按照书里的脉络，将知识点分为四个部分。其中第一部分数据结构与对象分为上中下篇，上篇包括：SDS、链表和字典；中篇包括跳跃表、整数集合和压缩列表；下篇为对象；
上篇的链接：https://www.jianshu.com/p/33f4cb95c008
中篇的链接：https://www.jianshu.com/p/c170d1e132ba
与本章相关的 Redis 命令总结在下篇文章，欢迎点击收藏，本篇将不再重复：
《Redis常用命令及示例总结（API）》：https://www.jianshu.com/p/f8eb9afaa908
1. Redis对象概述
- Redis没有直接使用前面介绍的数据结构来实现键值对数据库，而是基于这些数据结构的对象系统；
- Redis有五种基本对象，分别是字符串、列表、哈希、集合、有序集合。使用以下8种编码方式中的几种作为底层实现底层实现：long类型整数、embstr编码的SDS、SDS、字典、双端链表、压缩列表、整数集合、跳跃表；
- Redis在创建键值对时，至少会生成两个对象，键对象和值对象；
1.1 对象的定义
-
Redis中的每个对象都由一个
redisObject结构来表示：typedef struct redisObject{ //类型 unsigned type:4; //编码 unsigned encoding:4; //指向底层实现数据结构的的指针 void *ptr; //…… }-
类型
type的可选类型：类型常量 对象的名称 TYPE命令的输出 REDIS_STRING 字符串对象 string REDIS_LIST 列表对象 list REDIS_HASH 哈希对象 hash REDIS_SET 集合对象 set REDIS_ZSET 有序集合对象 zset -
编码
encoding的可选类型；同种类型可以有不同的编码形式：类型 对象 编码 编码方式 OBJECT ENCODING命令输出 REDIS_STRING 字符串 REDIS_ENCODING_INT 使用整数数值实现 int REDIS_STRING 字符串 REDIS_ENCODING_EMBSTR 使用embstr编码 embstr REDIS_STRING 字符串 REDIS_ENCODING_RAW 使用SDS实现 raw REDIS_LIST 列表 REDIS_ENCODING_ZIPLIST 使用压缩列表实现 ziplist REDIS_LIST 列表 REDIS_ENCODING_LINKEDLIST 使用双端链表实现 linkedlist REDIS_HASH 哈希 REDIS_ENCODING_ZIPLIST 使用压缩列表实现 ziplist REDIS_HASH 哈希 REDIS_ENCODING_HT 使用字典实现 hashtable REDIS_SET 集合 REDIS_ENCODING_INTSET 使用整数集合实现 intset REDIS_SET 集合 REDIS_ENCODING_HT 使用字典实现 hashtable REDIS_ZSET 有序集合 REDIS_ENCODING_ZIPLIST 使用压缩列表实现 ziplist REDIS_ZSET 有序集合 REDIS_ENCODING_SKIPLIST 使用跳跃表和字典实现 skiplist
-
2. 字符串对象
-
字符串编码可以是
int、raw、embstr；编码类型 说明 int 字符串保存整数值，并且这个整数可以用long类型表示 raw 字符串值的长度大于39字节 embstr 字符串值的长度小于39字节 embstr编码是专门用于保存短字符串的一种优化编码方式；-
raw与embstr的异同：- 二者都使用
redisObject结构与sdshdr结构来表示字符串； -
embstr通过调用一次内存分配函数来分配一块连续的空间； -
raw通过调用两次内存分配函数来分配一块连续的空间；
- 二者都使用
-
embstr的优点：- 创建时只需要分配一次内存；
- 释放时只需要调用一次内存释放函数；
-
连续保存在一块连续内存里，对缓存友好；
embstr编码的字符串对象.png
long double类型表示的浮点数在Redis中也是作为字符串值来保存的；
embstr编码的字符串对象实际上是只读的，要修改先会转成raw编码，再执行修改命令；字符串命令请见《Redis常用命令及示例总结》；
3. 列表对象
- 列表的编码对象可以是
ziplist或linkedlist； - redis 3.2以后，
quicklist作为列表键的实现底层实现之一，代替了压缩列表。 -
ziplist编码的条件：- 列表对象保存的所有字符串元素的长度都小于64字节；
- 列表对象保存的元素数量小于512个；
ziplist编码的list.png
-
linklist编码：
linkedlist编码的list.png
- 列表命令请见《Redis常用命令及示例总结》；
3.1 quicklist 快速链表
-
quicklist的定义在
quicklist.h：typedef struct quicklist { //指向头部(最左边)quicklist节点的指针 quicklistNode *head; //指向尾部(最右边)quicklist节点的指针 quicklistNode *tail; //ziplist中的entry节点计数器 unsigned long count; //quicklist的quicklistNode节点计数器 unsigned int len; //保存ziplist的大小，配置文件设定，占16bits int fill : 16; //保存压缩程度值，配置文件设定，占16bits，0表示不压缩 unsigned int compress : 16; } quicklist; -
quicklist节点的定义：
typedef struct quicklistNode { struct quicklistNode *prev; //前驱节点指针 struct quicklistNode *next; //后继节点指针 //不设置压缩数据参数recompress时指向一个ziplist结构 //设置压缩数据参数recompress指向quicklistLZF结构 unsigned char *zl; //压缩列表ziplist的总长度 unsigned int sz; //ziplist中包的节点数，占16 bits长度 unsigned int count : 16; //表示是否采用了LZF压缩算法压缩quicklist节点，1表示压缩过，2表示没压缩，占2 bits长度 unsigned int encoding : 2; //表示一个quicklistNode节点是否采用ziplist结构保存数据，2表示压缩了，1表示没压缩，默认是2，占2bits长度 unsigned int container : 2; //标记quicklist节点的ziplist之前是否被解压缩过，占1bit长度 //如果recompress为1，则等待被再次压缩 unsigned int recompress : 1; //测试时使用 unsigned int attempted_compress : 1; //额外扩展位，占10bits长度 unsigned int extra : 10; } quicklistNode;
quicklist逻辑图.png
4. 哈希对象
- 哈希对象编码可以是
ziplist或hashtable； - 使用
ziplist编码的条件：- 键和值的字符串长度小于64字节；
- 键值对数量少于512个；
- 使用
ziplist编码时：
使用ziplist编码时.png
- 使用
hashtable编码时：
使用hashtable编码时.png
- 哈希表命令请见《Redis常用命令及示例总结》；
5. 集合对象
集合对象的编码可以是
intset或hashtable；-
使用
inset编码的条件：- 所有元素为整数值；
- 保存的元素不超过512个；
-
使用
inset编码时：
使用inset编码的集合.png -
使用
hashtable编码时：
使用hashtable编码的集合.png 集合命令请见《Redis常用命令及示例总结》；
6. 有序集合对象
- 有序集合的编码可以是
ziplist或skiplist； - 压缩列表内的集合元素按分值从小到大排列；
- 使用
ziplist编码时：
使用ziplist编码的有序集合.png
-
使用
ziplist编码的条件：- 元素数量少于128个；
- 元素长度小于64字节；
使用
skiplist编码时，使用zset结构作为底层实现；-
zset的定义：typedef struct zset{ //跳跃表 zskiplist *zsl; //字典 dict *dict; } zset;-
跳跃表和字典使用指针来共享相同的元素和分值，因此不会产生重复，也不会造成内存浪费；
使用skiplist编码的有序集合.png
-
- 有序集合命令请见《Redis常用命令及示例总结》；
7. Redis对象的特点
7.1 类型检查与命令多态
- Redis的命令基本上分两类。一种是可以对任意类型的键操作（基于类型的多态），一种是只能对特定类型的键执行（基于编码的多态）；
- 在执行特定类型命令之前，服务器会先检查
redisObject结构的type属性，判断是否为执行该命令所需的类型。是则执行，否则返回类型错误； - Redis还会根据值对象的编码方式选择正确底层方法，使一个命令可以同时用于处理多种不同编码方式的数据结构，进而实现多态命令；
类型检查与命令多态.png
7.2 内存回收
C语言不具备自动回收内存的功能，Redis构建一个引用计数计数实现内存回收机制；
-
引用计数由
redisObject结构的refcount属性记录：typedef struct redisObject{ //... //引用计数 int refcount; //... }- 创建新对象时，
refcount被初始化为1； - 对象被新程序使用时，
refcount++； - 对象不被一个程序使用时，
refcount--； - 对象计数值为0时，对象占用的内存会被释放；
- 创建新对象时，
7.3 对象共享
- 对象的计数属性带有对象共享的作用；
- 当多个键保存同一个值时，这些键的值指针指向同一个值对象，值对象的
refcounr为n； - Redis在初始化服务器时，会创建一万个字符串对象（0~9999的字符串对象），当服务器需要用到这些值对象时，服务器会使用这些共享对象，而不是创建新对象；
- Redis只对包含整数值的字符串对象进行共享，验证数字的时间复杂度为O(1)；
对象共享.png
7.4 对象的空转时长
-
redisObject结构里有个lru属性，记录对象最后一次被命令程序访问的时间；typedef struct redisObject{ //... unsigned lru:22; //... } - 使用命令
OBJECT IDLETIME可以显示对象的空转时间，不会改变对象的空转时间； - 如果服务器打开
maxmemory选项，并且回收内存的算法为volatile-lru或allkeys-lru，那么当服务器占用的内存数超过maxmemory选项设置的上限值是，空转时间较高的键会优先被服务器释放，回收内存；
