Redis五种基本数据类型底层详解
详细介绍Redis用到的数据结构简单动态字符串SDS和C字符串的区别总结
链表字典哈希表字典哈希算法解决键冲突rehash(重点)渐进式rehash
跳跃表Redis中跳跃表的实现跳跃表节点结构跳跃表总体结构
整数集合(intset)整数集合具体实现数组升级数组降级？没有降级，一旦升级就不会降级数组升级的好处
压缩列表连锁更新
快速列表quicklist快速列表的压缩机制
五种数据类型字符串对象列表对象哈希对象集合对象有序集合对象为什么要同时使用跳跃表和字典呢？？为什么要使用跳跃表，而不是用平衡树？？？
Redis内存回收机制Redis对象共享Redis对象的空转时长
一篇好的文章带来的是无限的价值！！！这篇文章写完时，窗外下着小雨，我坐在图书馆的桌前，我还在迷茫，不知道几个月后的我在何方
详细介绍Redis用到的数据结构
各位，稍安勿躁，讲解五种基本数据类型前，我们先来这些数据类型用到的数据结构，防止后面懵逼,本文所用源码来源：Redis源码链接，版本使用6.2
简单动态字符串
我们都知道Redis是用C写的，但Redis中并没有直接使用C语言传统的字符串(以空字符结尾的字符数组)，而是自己构建了一种名为简单动态字符串(simple dynamic string，简称SDS)的结构，并用作Redis的默认字符串。在Redis中，C字符串只会用作字符串字面量，一些不会对字符串发生修改的地方，比如说打印日志等等。
Redis中SDS的定义：
typedef char *sds;
struct __attribute__ ((__packed__)) sdshdr5 { // 对应的字符串长度小于 1<<5
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 { // 对应的字符串长度小于 1<<8
uint8_t len; /* used */ //目前字符串的长度
uint8_t alloc; //已经分配的总长度
unsigned char flags; //flag用3bit来标明类型
char buf[]; //柔性数组，以'\0'结尾
};
struct __attribute__ ((__packed__)) sdshdr16 { // 对应的字符串长度小于 1<<16
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[];
};
struct __attribute__ ((__packed__)) sdshdr32 { // 对应的字符串长度小于 1<<32
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[];
};
struct __attribute__ ((__packed__)) sdshdr64 { // 对应的字符串长度小于 1<<64
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和C字符串的区别
C字符串中使用n+1个字符数组表示n个长度的字符串，并且数组的最后一个总是‘\0’，表示该字符串结尾了。C字符串获取长度时，需要遍历一遍字符串，时间复杂度为O(N),而SDS获取字符串长度时，只需要从SDS结构中取出len字段便可以，时间复杂度为O(1)C字符串为其增加一段字符串时，如果没有为其分配足够的空间，则会造成缓冲区溢出；而使用我们的SDS时，则SDS会自动检查是否容量足够，不够的话就扩容，所以使用我们的SDS时不需要手动扩容，也就不会发生缓冲区溢出减少字符串带来的内存重分配次数,在C中，每次添加字符串都需要对数组扩容，删除字符串也需要内存重新分配。而SDS通过提前分配和惰性释放可以很好的改善内存重分配次数 提前分配：当SDS剩余空间不足时，Redis不但会给它分配足够的空间，还会给它分配多余的空间，如果下次增加字符串时，则可以使用这部分空余的空间，减少内存重分配 惰性释放:在删除一些字符时，Redis并不会立即释放空间，这样的话可以为将来的增加操作减少内存重分配的次数；于此同时，在Redis真正需要空间时，Redis也会释放掉这部分空间，不会内存泄露二进制安全：C字符串中不能包含一些空字符，否则可能会被认为是字符串结尾导致字符串截断，所以不能保存一些图片视频的二进制数据。而SDS并不是通过空字符来判断结束的，不会对内容进行任何处理，可以保存二进制数据兼容部分C字符串函数：Redis也会在结尾加上多余的一个‘\0’，使得某些情况可以使用C字符串的函数，减少自己实现重复功能
总结
由于Redis数据库的特性，会频繁的增删查改，保存一些二进制数据，而原来的C字符串并不能高性能的完成这些事，所以Redis才自己封装了SDS
链表
Redis定义的结构
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
这是双端链表最基础的定义，下图是示意图： 虽然使用多个listnode便可以组成链表的话，但Redis使用list结构来持有链表，操作更加方便
typedef struct list {
//表头结点
listNode *head;
//表尾结点
listNode *tail;
//结点复制函数
void *(*dup)(void *ptr);
//结点释放函数
void (*free)(void *ptr);
//结点对比函数，通过这三个函数可以为结点值设置不同的函数，从而包含各种不同类型的值，实现多态
int (*match)(void *ptr, void *key);
//结点的数量
unsigned long len;
} list;
总体结构如下：
字典
在字典中，一个键（key）可以和一个值（value）进行关联（或者 说将键映射为值），这些关联的键和值就称为键值对；
Redis的字典底层使用哈希表来实现，一个哈希表中有多个哈希表结点，一个哈希表结点保存了字典中的一个键值对
哈希表
Redis中源码表示：
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
//哈希表数组，里面是一个dictEntry结构
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值，总是等于size-1
unsigned long sizemask;
//已经存在结点的数量
unsigned long used;
} dictht;
//哈希表结点
typedef struct dictEntry {
//键
void *key;
//值
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
//下一个节点，使其形成链表
struct dictEntry *next;
} dictEntry;
以上两个结构总体为：
字典
Redis中字典结构源码表示：
typedef struct dict {
//类型特定函数
dictType *type;
//私有数据
void *privdata;
//两个哈希表，作用后面说
dictht ht[2];
//当rehash不进行时，值为-1
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;
type和privdata是针对不同类型的键值对，为多态而创建的 ht[2]两个哈希表是为了rehash而设计的，一般只使用ht[0]这个哈希表，ht[1]只会在对ht[0]进行rehash的时候使用 rehashidx它记录了目前rehash的进度，为-1时则说明不进行rehash
不进行rehash下的字典示意图：
哈希算法
当插入一个键值对时，需要用哈希算法算出对应的索引值，并把它插入其中(具体就不再多说什么，不了解的可以去查看数据结构这门课程)
Redis计算哈希值和索引的方法：
#使用字典设置的哈希函数，计算键key 的哈希值
hash = dict->type->hashFunction(key);
#使用哈希表的sizemask 属性和哈希值，计算出索引值
#根据情况不同，
ht[x] 可以是ht[0] 或者ht[1] index = hash & dict->ht[x].sizemask;
Redis使用MurmurHash2算法来计算键的哈希值，这种算法最大的优点就是当输入有规律的数时，也能平均散列到数组中
解决键冲突
Redis使用链地址法解决键冲突
rehash(重点)
随着操作的进行，哈希表的键值对会逐渐增多或者减少，为了让哈希表的负载因子保持在一个合理的范围区间，就必须对哈希表进行扩展或者收缩。而扩展或者收缩，我们需要执行rehash(重新散列)来完成一次操作 rehash执行步骤如下：
为字典的ht[1]分配空间，大小取决于ht[0]和所执行的扩展或者收缩操作。将ht[0]的所有键值对rehash到ht[1]上(rehash指的是重新计算哈希值和索引，重新散列到ht[1]这个哈希表中)移动完成后，释放ht[0]的空间，将ht[1]改为ht[0]，并为ht[1]重新创建一个空的哈希表，为下一次rehash准备
渐进式rehash
如果数据量比较多时，一次性移动我们的hash表，那么时间会比较久，就有可能造成redis服务停止。所以执行rehash时，并不是一次完成的，而是渐进式完成的 渐进式rehash步骤如下：
为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表在字典中维持一个rehashidx，也就是上面的字典结构的属性，将其值设置为0，表示rehash工作开始在rehash期间，程序除了执行指定的操作外，还会将索引为rehashidx的数据移动到ht[1]相当于将ht[0]里的数据删除，在ht[1]里面增加，当rehashidx这个索引的数据全部移动完成时，则将rehashidx值加1，直到全部完成完成后，将rehashidx的值表示为-1，并将ht[1]设置为ht[0].
在渐进式rehash期间，字典进行的删除，更新，查找会在两张哈希表上进行。比如查找，redis会先在ht[0]查找，找不到才会到ht[1]上面查找
而字典进行的插入操作，则只会在ht[1]表里执行。这样的话，ht[0]表里的数量只减 不增，也减少了重复插入的操作
跳跃表
在Redis中，有两个地方用到了跳跃表，一个是实现有序集合类型，一个是在集群节点中作内部数据结构
Redis中跳跃表的实现
跳跃表节点结构
跳跃表节点在/src/server.h/中zskiplistNode结构定义：
/* 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;
zskiplistLevel跳表层： 上图的L1,L2就表示的是跳表层，每个层有两个属性。 forward表示前进指针，用它来遍历后面的元素。span表示跨度：上图连线上的数字就是这个跨度，两个元素离的越远，跨度就越大；而这个跨度的作用就是计算我们的rank(排位) ，在遍历一个元素时，就他路径上的跨度全部加起来就是它的rank。比如查找下面的o3这个节点时，rank就为3
backward回退指针： 每个节点只有一个回退指针，所以每次只能回退到前一个节点，而不能跳来跳去；回退指针用于从后向前遍历 score分值：是一个double类型的浮点数，跳表中所有元素都是按分值来排序的。 ele成员对象：是一个sds的字符串对象。成员对象必须是唯一的，而分值可以是相同的。分值相同时，按成员变量的字典序排序
跳跃表总体结构
一个跳跃表有多个跳跃表节点。通过zskiplist来持有这些节点。 Redsi中zskiplist结构的定义如下：
typedef struct zskiplist {
//表示表头结点和表尾节点
struct zskiplistNode *header, *tail;
//节点数量
unsigned long length;
//最大层数
int level;
} zskiplist;
看到上面这张图应该就可以明白每个字段表示的含义了吧！表头那个节点并不计算在内。准确的来说，表头节点虽然都有对应的属性，但是我们是不会用到的，只是后面插入，删除时更加方便
整数集合(intset)
整数集合是Redis用来保存整数值的集合，保证集合中不会出现重复的元素
整数集合具体实现
typedef struct intset {
//编码方式
uint32_t encoding;
//集合数量
uint32_t length;
//保存元素的数组
int8_t contents[];
} intset;
encoding编码方式表示数组用什么类型来保存 length集合数量保存了集合中的数量 contents[]集合数组虽然是类型是int8_t，但是实际取决于encoding编码方式。数组内是大小有序的，从小到大，不含重复值
数组升级
当对数组中添加新元素时，如果新添加的元素类型大于原来的数组的类型，则需要对数组进行升级。 升级步骤如下：
按新的类型扩展原有数组大小，并为新元素分配空间将原来的数组元素转换为新的元素类型，并且保存有序将新添加的元素加入数组 大致流程如下：
因为新添加的类型是大于原有数组类型的，所以新添加的元素一定大于或者小于原有数组里的元素，每次插入也一定是插到头或者尾
数组降级？没有降级，一旦升级就不会降级
数组升级的好处
1. 更加方便 C语言中要保存两种不同类型的元素就必须使用两个类型数组来保存 而Redis则使用数组升级来避免了使用两个数组，更加方便，且不用担心类型错误 2. 节约内存 要让一个数组保存不同的类型，最简单就是直接定义一个最大的数组类型，但是这样会占用不必要的空间 而Redis则只是在必要的时候才升级数组，尽量节约了内存
压缩列表
压缩列表是Redis为了节约内存而开发的，是一种由连续内存块组成的顺序结构。一个压缩列表包含多个节点，每个节点可以是一个字节数组或者整数。 下图是压缩列表的各个组成部分： 各个字段含义如下： 下面是压缩列表的节点构成： previous_entry_length：表示前一个节点的长度，用于从尾向前遍历；如果前一个节点长度小于254个字节，那么就用1字节来保存，如果大于等于254字节，就用5字节来保存。 encoding：记录了content保存的数据类型和长度 content：保存节点的值，类型和长度由encoding类型决定
连锁更新
那我们考虑一种情况，如果每一个节点的长度都在靠近254字节。那么新插入了一个大于等于254字节的节点，那么下一个节点的头部就必须是5个字节了(本来previous_entry_length只用一个字节)，所以程序将对压缩列表执行空间重分配操作，将该节点扩容至5字节。但是该节点现在扩容后又大于254字节了，所以后面的节点又要接着扩容。当然，删除一个节点也可能造成这种情况：比如说第一个节点长度大于等于254，第二个节点长度小于254，那么后面一个节点previous_entry_length保存的就是1字节，那我们把第二个节点删除，现在不就又变成刚才的情况了嘛！！！Redis把这种特殊情况造成的连续更新叫做连锁更新
快速列表quicklist
quicklist由多个快速列表节点构成的双向链表，每一个快速列表节点都保存一个ziplist压缩列表
快速列表的压缩机制
在快速列表中，两端节点的数据被访问的可能性比较高，中间访问的可能性比较低。如果符合这种场景的话，就可以把中间节点的数据用LZF算法进行压缩，进一步节省空间。
我们可以对list-compress-depth参数进行配置： 默认情况下，list-compress- depth参数为O，也就是不压缩数据;当该参数被设置为1时，除了头部和尾部之外的结点都会被压缩;当该参数被设置为2时，除了头部、头部的下一个、尾部、尾部的上一个之外的结点都会被压缩;当该参数被设置为2时，除了头部、头部的下一个、头部的下一个的下一个、尾部、尾部的上一个、尾部的上一个的上一个之外的结点都会被压缩;以此类推。
五种数据类型
Redis使用对象来表示数据库中的键和值。当创建一个对象时，最少会包含两个对象，一个用作键值对的键(固定是字符串类型)，一个用作键值对的值(可以是五种数据类型)。我们可以使用type命令显示键对应值的数据类型 Redis的每个对象都用一个redisObject结构来表示（src/server.h）：
typedef struct redisObject {
//类型
unsigned type:4;
//编码方式
unsigned encoding:4;
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
//用来实现引用计数的，内存管理计数
int refcount;
//指向底层实现数据结构的指针
void *ptr;
} robj;
type类型：就是上面的五种类型 ptr指针指向底层实现的数据结构 ending编码方式:
/* Objects encoding. Some kind of objects like Strings and Hashes can be
* internally represented in multiple ways. The 'encoding' field of the object
* is set to one of this fields for this object. */
#define OBJ_ENCODING_INT 1 /* Encoded as integer */
#define OBJ_ENCODING_EMBSTR 8 /* Embedded sds string encoding */
#define OBJ_ENCODING_RAW 0 /* Raw representation */
#define OBJ_ENCODING_HT 2 /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3 /* Encoded as zipmap */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6 /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7 /* Encoded as skiplist */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */
通过object encoding可查看对应的编码
下面我们来讲讲这五种基本数据类型的对象，对象底层可以使用的编码方式等等
字符串对象
字符串对象的编码可以是以下这三种：
#define OBJ_ENCODING_INT 1 /* Encoded as integer */
#define OBJ_ENCODING_EMBSTR 8 /* Embedded sds string encoding */
#define OBJ_ENCODING_RAW 0 /* Raw representation */
int：存储8个字节的长整型(long,2的63次方-1)，那么字符串对象会将整数值保存在字符串里的ptr属性里面，将void*转换为long，并将字符串编码设置为int embstr：代表embstr格式的SDS，用来存储小于等于44字节的字符串；embstr只会调用一次内存分配函数来分配空间，因为redisObject结构和sdshdr结构是连在一起的 raw：存储大于44字节的字符串，需要调用两次内存分配函数 Redis浮点数也是用字符串值来表示的，需要用时先把它转为浮点数，计算完后又转为字符串值保存
列表对象
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */
在Redis早期的时候，当列表数量较少时使用ziplist压缩列表，数量较多时使用linkedlist来实现 (好多书上也是这样讲的)
后面版本列表对象都是由quicklist快速列表实现的。
哈希对象
当键值对的长度都小于64字节，且键值对数量小于512个时，使用ziplist，否则使用hashtable 底层使用ziplist实现： 总体结构如上。每次添加都会添加都末尾，添加时，需要遍历一遍整个压缩列表，如果有key和插入的key相同，则将它的value替换，否则就添加到末尾。
底层使用hashtable实现： 总体结构如上。hashtable底层的哈希对象使用字典作为底层实现
集合对象
集合对象底层可以是intset或者hashtable，如果集合对象全为整数，且数量小于等于512个，则使用intset；否则使用hashtable 使用intset实现： 使用hashtable实现：集合元素为字典的key，字典的value则为null。(类似Java的Set集合，底层也是使用map实现的，不过它的value值是一个final常量，不是null)
有序集合对象
有序集合对象使用ziplist或者skiplist来实现，当集合数量小于128且字符长度小于等于64字节时使用ziplist;否则使用skiplist 底层使用ziplist实现：压缩列表，示意图如下： 集合内的元素按分值大小排序
底层使用skiplist实现：这种编码的有序集合对象使用zset结构作为底层实现，一个zset结构包含一个字典和一个跳跃表
跳跃表中按分值从大到小进行保存所有元素，跳跃表节点保存一个集合元素，跳跃表的ele成员对象保存了元素的成员，跳跃表的score保存了元素的分值。
字典中也保存了集合的全部元素，字典的键是元素成员，字典的值是元素分值
注意：有序集合的每个元素成员是一个字符串，分值是double类型的浮点数。 并且虽然看起来是保存了两份，但是他们相同元素通过指针指向的都是同一个地方，所以并不会有冗余；
为什么要同时使用跳跃表和字典呢？？
虽然用单独的一种都可以实现有序集合的功能，但是两个都各有利弊，使用两个的话就相当于同时保留了他们的优点，摒弃了缺点。
比如我们只使用字典来实现，那么它查找一个元素的分值复杂度为O(1),但是如果范围查找的话，就需要先排序，时间复杂度为O(nlogn)，空间复杂度为O(n)
比如我们只使用跳跃表来实现，那么它可以很快的支持范围查找，但它查找一个分值的时间复杂度为O(logn）。
而范围查找和只查询分值在有序集合是很常见的，所以综合起来，同时使用两个最优。
为什么要使用跳跃表，而不是用平衡树？？？
文章来源 综合以上说法：跳跃表更加简单，使用范围查找比其他的平衡树效率要高；并且是容易实现容易调试的；并且跳表插入和删除只要维护节点指针即可，不需要调整树。
那为什么Java的HashMap底层不使用跳跃表呢？？？不是更加简单吗？？ 跳表是以空间换时间的数据结构，而红黑树并不需要额外空间 并且HashMap的Entry之间并没有排序关系，无法满足跳跃表的条件。 额外：TreeMap 的并发实现 ConcurrentSkipListMap 就是使用的跳表；concurrentHashMap8 之前采用链表数据结构，8 之后是红黑树。concurrentSkipListMap 跳表，是因为要实现线程安全的 TreeMapCAS 操作会很复杂，才产生的。高并发有序。
Redis内存回收机制
由于C语言并没有自动的内存回收机制，在redisObject结构中有一个refcount引用计数属性，当该值为0，也就是该对象不再被其他所引用时，就会释放内存。
Redis对象共享
可以让多个键共用一个值对象，只需要将指针指向它，并且将该值对象的引用计数+1便可以。注意这里只对整数值的字符串对象进行共享。如果对包含字符串值的对象进行共享，那么需要把两个字符串遍历一遍，时间复杂度为O(N),如果包含多个值的列表或者对象，那么时间复杂度为O(N^2).而整数值只需要转换完比较就ok了。所以为了时间效率，Redis只共享整数值的字符串
Redis对象的空转时长
redisObject还有一个属性lru:LRU_BITS：记录了该对象最后一次被访问的时间。 使用 object idletime命令便可以打印对象的空转时长：当前时间减去对象的lru属性值
好文链接
您阅读本篇文章共花了：
发表评论