redis...,用了好多年了,这也是面试八股文必问内容,但是你真的搞懂redis底层数据结构了吗?5种数据结构;对,但是然后呢,直击灵魂的一问~哈哈,下面咱们就重新回顾回顾。
一,服务器端整体数据结构
1.1 redisServer
redis服务器将所有的数据库保存在redisServer结构的db数组中,db数组中的每一个redisDB结构代表一个数据库。代码如下
typedef struct redisServer{
redisDb *db; // db是一个数组,服务器中的所有数据库
int dbNum; // 服务器的数量,一般是16个
...
}
同时在服务器内部,还有一个客户端状态的结构,redisClient,这个结构会记录客户端当前使用的数据库
typedef struct redisClient{
redisDb *db; // 记录客户端正在中正在使用的数据库,db中保存的就是reidsServer 中的元素,即正在使用服务器中的哪个数据库
...
}
比如说,某个客户端连接数据库后,执行了select 2, 则其结构为:
1.2 redisDB
tydef struct redisDb{
dict *dict; // 数据库的键空间,保存着数据库中的所有的键值对。 dict 的建对象是一个字符串对象,值对象是5种基本数据类型中的. 都是redisObject
dict * expire; // 键值对的过期时间
...
}
每个redisDB代表一个数据库,其中的dict保存了数据库中的所有键值对,这个字典也称为键空间。
1.3 一个例子
在redis中执行这些代码
redis> SET message "hello world"
OK
redis> RPUSH alphabet "a" "b" "c"
(integer)3
redis> HSET book name "Redis in Action"
(integer) 1
redis> HSET book author "Josiah L. Carlson"
(integer) 1
redis> HSET book publisher "Manning"
(integer) 1
redis> expire alphabet xxxxx
redis> expire book yyyy
结果为:
根据图可知,执行ttl key 或者 pttl key 的时间复杂度为O(1)
1.4 redisObject
刚才看到redisDB中的dict中key和value都是一个redisObject结构,其结构如下
typedef struct redisObject {
//类型
unsigned type:4;
//编码
unsigned encoding:4;
//指向底层实现数据结构的指针
void *ptr;
// ...
} robj;
详细介绍下每个字段的意思:
1. type记录了对象的类型,常说的redis中的5大数据类型
type key 命令输出的也是这个字段对应的值,如下图
2. encoding 记录了对象所使用的编码,也就是说此redis对象底层使用的数据结构,每种类型的对象可以使用的编码如下。
二,redis 数据结构
接下来我们就详细讲一讲每种数据结构的编码,这才是真正的底层数据结构。
2.1 字符串对象
(1)encoding=REDIS_ENCODING_INT 底层使用数字类型编码
当set 的value值是数字类型时,redis会用数字类型存储,举例如下,
(2)encoding =REDIS_ENCODING_EMPTR
如果设设置的value值得大小小于32字节,则会使用此种编码格式,结构如下
示例如下:
(3)encoding =REDIS_ENCODING_RAW
如果设置的value值得大小大于32字节,则会使用此种编码格式,结构如下
说明:
(2),(3) 的区别在于分配内存的方式,对于value值小于32字节的情况,redisObject和SDS用同一块连续的内存。释放的时候只需要释放一次。对于大于32字节的情况。分配了两块内存。一块是redisObject ,另一块是SDS.redisObject中的ptr指向SDS。释放的时候释放两次。
不得不感叹一句,redis的开发者真的太细了~~~
redis中用到的字符串对是自己封装的,叫SDS,介绍下
SDS redis底层存储字符串的数据结构,如下图所示
struct sdshdr {
//记录buf数组中已使用字节的数量
//等于SDS所保存字符串的长度
int len;
//记录buf数组中未使用字节的数量
int free;
//字节数组,用于保存字符串
char buf[];
};
示例:
2.2 列表对象编码
列表对象有两种编码方式, ziplist 和linkedlist,首先来介绍下这两种数据结构
linkedlist 列表:
typedef struct listNode {
// 前置节点
struct listNode * prev;
// 后置节点
struct listNode * next;
//节点的值
void * value;
}listNode;
typedef struct list {
//
表头节点
listNode * head;
//
表尾节点
listNode * tail;
//
链表所包含的节点数量
unsigned long len;
//
节点值复制函数
void *(*dup)(void *ptr);
//
节点值释放函数
void (*free)(void *ptr);
//
节点值对比函数
int (*match)(void *ptr,void *key);
} list;
示例如下:
zipList 压缩列表:
压缩列表的构成:
举个例子:
1. 列表zlbytes属性的值为0x50(十进制80),表示压缩列表的总长为80字节
2. 列表zltail属性的值为0x3c(十进制60),这表示如果我们有一个指向压缩列表起始地址的指针p,那么只要用指针p加上偏移量60,就可以计算出表尾节点entry3的地址
3. 列表zllen属性的值为0x3(十进制3),表示压缩列表包含三个节点
entry结构:
1. 节点的previous_entry_length属性以字节为单位,记录了压缩列表中前一个节点的长度
2. 节点的encoding属性记录了节点的content属性所保存数据的类型以及长度
3. content就是编码对应的数据
(1)列表对象使用ziplist 编码,使用ziplist 编码的列表对象有两个条件
1.列表对象保存的所有字符串元素的长度都小于64字节;
2.列表对象保存的元素数量小于512个;不能满足这两个条件的列表对象需要使用linkedlist编码
示例如下:
(2) 列表对象使用 linkelist ,不满足ziplist得即使用linkedlist,如下所示
2.3 哈希对象
哈希对象有两种编码方式 ziplist或者hashtable。
(1)使用ziplist 编码
1. 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节 2.哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
例如:
redis> HSET profile name "Tom"
(integer) 1
redis> HSET profile age 25
(integer) 1
redis> HSET profile career "Programmer"
(integer) 1
(2)使用hashtable字典实现
首先讲下字典的实现方式
1.字典的结构
typedef struct dict {
//类型特定函数
dictType *type;
//私有数据
void *privdata;
//哈希表
dictht ht[2];
// rehash索引
//当rehash不在进行时,值为-1
in trehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;
typedef struct dictht {
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码,用于计算索引值
//总是等于size-1
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
} dictht;
其中dictEntry的结构为:
typedef struct dictEntry {
//键
void *key;
//值
union{
void *val;
uint64_tu64;
int64_ts64;
} v;
//指向下个哈希表节点,形成链表
struct dictEntry *next;
} dictEntry;
(2)如果不满足(1)的条件,则其使用字典,结构如下
2.4 集合对象
集合对象的实现有两种实现方式,集合对象的编码可以是intset或者hashtable。
首先说下intset整数集合
inset整数集合的实现
typedef struct intset {
//编码方式
uint32_t encoding;
//集合包含的元素数量
uint32_t length;
//保存元素的数组
int8_t contents[];
} intset;
(1)集合使用inset编码
条件:
1. 集合对象保存的所有元素都是整数值;
2. 集合对象保存的元素数量不超过512个
当使用整数集合时,结构如下
举例如下:
(2)集合使用hastable结构如下
2.5 有序集合
有序集合的编码可以是ziplist或者skiplist
条件:1.有序集合保存的元素数量小于128个
2. 集合对象保存的元素数量不超过512个
(1)当使用ziplistb 编码时,其结构如下
redis> ZADD price 8.5 apple 5.0 banana 6.0 cherry
(integer) 3
跳跃表的实现
跳跃表(skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点
跳跃表示例:
由此看,在redis的实现中,跳跃表的实现分成了两部分。
左半部分参数说明:
1.header:指向跳跃表的表头节点
2. tail:指向跳跃表的表尾节点
3. 记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)
4.length:记录跳跃表的长度,也即是,跳跃表目前包含节点的数量(表头节点不计算在内)
右半部分参数说明:
1. Ln 代表第n层数,如L2代表第二层。每个层都带有两个属性:前进指针和跨度。前进指针用于访问位于表尾方向的其他节点,而跨度则记录了前进指针所指向节点和当前节点的距离,跨度可以计算目标节点在跳跃表中的排位
2. 后退(backward)指针:节点中用BW字样标记节点的后退指针,它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用
3. 分值(score):各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中,节点按各自所保存的分值从小到大排列。
4. 成员对象(obj):各个节点中的o1、o2和o3是节点所保存的成员对象。
(2)有序集合使用skiplist编码时
有序集合使用skiplist时,使用的数据结构是skiplist和dict组合而成。如下
typedef struct zset {
zskiplist *zsl;
dict *dict;
} zset;
即ptr指针指向的是zset 的地址,举例如下;
说明:为什么在使用skiplist和dict做有序集合的底层编码?
其实,skiplist和dict 两种数据结构都可以单独作为有序集合的底层编码的。如果单独使用dict作为底层编码,可以有O(1)的时间复杂度某个成员的分值,但是每次在执行范围型操作——比如ZRANK、ZRANGE等命令时,程序都需要对字典保存的所有元素进行排序,完成这种排序需要至少O(NlogN)时间复杂度,以及额外的O(N)内存空间。另一方面如果使用skiplist,范围操作的优势将会保存,但是所以根据成员查找分值这一操作的复杂度将从O(1)上升为O(logN)。因为以上原因,为了让有序集合的查找和范围型操作都尽可能快地执行,Redis选择了同时使用字典和跳跃表两种数据结构来实现有序集合。还有要注意的点,这样做也不会浪费内存,因为在redis中,数据是共享的,他们的指针都指向通一份数据。
不得不再感叹一句,redis真的太细了,太强了~~