Redis中的底层数据结构
redis的底层数据类型
String类型:
由于C语言中并不存在String数据类型,因此,redis自己创建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型,并将SDS用作Redis的默认字符串表示.打开sds.h文件可查看其对应的数据结构信息:
1struct sdshdr {
2 // buf 中已占用空间的长度
3 int len;
4 // buf 中剩余可用空间的长度
5 int free;
6 // 数据空间
7 char buf[];
8};
下图展示了我们执行了>set redis之后在内存中的存储方式.
如图,在buf属性是一个char类型的数组,数组的前五个字符分别保存了redis五个字符,而结尾使用了'/0'.表明在redis中,连续数据的结尾是使用'/0'的形式实现的.
链表
链表实现代码:
1typedef struct listNode {
2 // 前置节点
3 struct listNode *prev;
4 // 后置节点
5 struct listNode *next;
6 // 节点的值
7 void *value;
8} listNode;
9
10typedef struct list {
11 // 表头节点
12 listNode *head;
13 // 表尾节点
14 listNode *tail;
15 // 节点值复制函数
16 void *(*dup)(void *ptr);
17 // 节点值释放函数
18 void (*free)(void *ptr);
19 // 节点值对比函数
20 int (*match)(void *ptr, void *key);
21 // 链表所包含的节点数量
22 unsigned long len;
23} list;
多个listnode可以通过prev和next指针组成双端链表,如下图
虽然仅仅使用多个listnode结构就可以组成链表,但是使用adlist.h/list来持有链表的话,操作操作会更方便.list中包含了链表的头结点和尾结点的指针,以及链表长度计数器len,而dup,free和match成员则是用于实现多态链表所需的类型特定函数:dup函数用于复制节点所保存的值;free函数用于释放链表节点所保存的值;match函数则用于对比链表节点所保存的值和另一个输入值是否相等.
由一个list结构和三个listnode结构组成的链表
字典(dict)
字典,又称为无符号表,关联数组或者映射(map),是一种用于保存键值对的抽象数据结构.
字典中每个键都是独一无二的,程序可以在字典中根据键查找与之关联的值,或者通过键来更新值,等等.redis对字典的实现:
redis字典所使用的的哈希表由dict.h/dictht结构定义:
1typedef struct dictht {
2 // 哈希表数组
3 dictEntry **table;
4 // 哈希表大小
5 unsigned long size;
6 // 哈希表大小掩码，用于计算索引值
7 // 总是等于 size - 1
8 unsigned long sizemask;
9 // 该哈希表已有节点的数量
10 unsigned long used;
11} dictht;
table属性是一个数组,数组中的每个元素都是一个指向dict.h/dictEntry结构的指针,每个diictEntry结构保存着一个键值对.size属性记录了哈希表的大小,也即是table数组的大小,而used属性则记录了哈希表目前已有节点(键值对)的数量.sizemask属性的值总是等于size-1,这个属性和哈希值一起决定了一个键应该放到table数组的哪个索引上边.
1typedef struct dictEntry {
2 // 键
3 void *key;
4 // 值
5 union {
6 void *val;
7 uint64_t u64;
8 int64_t s64;
9 } v;
10 // 指向下个哈希表节点，形成链表
11 struct dictEntry *next;
12} dictEntry;
key属性保存着键值对中的键,而v属性保存着键值对中的值,其中键值对的值可以是一个指针,或者uint64_t整数,又或者是一个int64_t整数.next属性指向另一个哈希节点的指针.这个指针可以将多个哈希值相同的键值对连接在一起,以此来解决哈希碰撞的问题.
redis中字典有dict.h/dict结构表示:
1/*
2 * 字典
3 */
4typedef struct dict {
5 // 类型特定函数
6 dictType *type;
7 // 私有数据
8 void *privdata;
9 // 哈希表
10 dictht ht[2];
11 // rehash 索引
12 // 当 rehash 不在进行时，值为 -1
13 int rehashidx; /* rehashing not in progress if rehashidx == -1 */
14 // 目前正在运行的安全迭代器的数量
15 int iterators; /* number of iterators currently running */
16} dict;
type属性和privdata属性针对不同类型的键值对,为创建多态字典而设置的:type:是一个指向dictType结构的指针,每个dictType结构保存了一簇用于操作特定类型键值对的函数.private:保存了需要传递给那些类型特定函数的可选参数.
1/*
2 * 字典类型特定函数
3 */
4typedef struct dictType {
5 // 计算哈希值的函数
6 unsigned int (*hashFunction)(const void *key);
7 // 复制键的函数
8 void *(*keyDup)(void *privdata, const void *key);
9 // 复制值的函数
10 void *(*valDup)(void *privdata, const void *obj);
11 // 对比键的函数
12 int (*keyCompare)(void *privdata, const void *key1, const void *key2);
13 // 销毁键的函数
14 void (*keyDestructor)(void *privdata, void *key);
15 // 销毁值的函数
16 void (*valDestructor)(void *privdata, void *obj);
17} dictType;
ht属性是一个包含了两个项的数组,数组中的每个项都是一个dictht哈希表,一般情况下,字典只是用ht[0]哈希表,ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用.
除了ht[1]之外,另一个和rehash有关的属性就是rehashidx,它记录了rehash目前的进度,如果目前没有进行rehash,那么他的值为-1.
跳跃表(skipList)
跳跃表是一种有序的数据结构,通过每个节点维持多个指向其他节点的指针,从而达到快速访问节点的目的.
跳跃表的平均O(logN),最坏O(N)复杂度的节点查找.大部分情况下,跳跃表的效率可以和平衡树相媲美.并且实现比平衡树更简单.
redis的源码实现,redis.h:
1typedef struct zskiplistNode {
2 // 成员对象
3 robj *obj;
4 // 分值
5 double score;
6 // 后退指针
7 struct zskiplistNode *backward;
8 // 层
9 struct zskiplistLevel {
10 // 前进指针
11 struct zskiplistNode *forward;
12 // 跨度
13 unsigned int span;
14 } level[];
15} zskiplistNode;
16/*
17 * 跳跃表
18 */
19typedef struct zskiplist {
20 // 表头节点和表尾节点
21 struct zskiplistNode *header, *tail;
22 // 表中节点的数量
23 unsigned long length;
24 // 表中层数最大的节点的层数
25 int level;
26} zskiplist;
27/*
28 * 有序集合
29 */
30typedef struct zset {
31 // 字典，键为成员，值为分值
32 // 用于支持 O(1) 复杂度的按成员取分值操作
33 dict *dict;
34 // 跳跃表，按分值排序成员
35 // 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
36 // 以及范围操作
37 zskiplist *zsl;
38} zset;
zskiplist 字段释义:header:指向跳跃表的头结点.tail:指向跳跃表的尾结点.level:记录目前跳跃表内,层数最大的那个节点的层数.length:记录跳跃表的长度.也就是跳跃表目前包含的节点数量.
zskiplistNode 字段释义:level:节点使用L1,L2,L3字样标记节点的各层,每个层有两个属性:前进指针和跨度.前进指针用于访问位于表尾方向的其他节点,而跨度则记录了前进指针所指向节点和当前节点的距离.如上图,带数字的箭头代表前进指针,而那个数字就代表跨度.当程序从表头想表位进行遍历时,访问会沿着层的前进指针进行.backward后退指针:节点中用BW字样标记节点的后退指针,指向位于当前节点的前一个节点.后退指针在程序从表尾向表头遍历时使用.score分值:各个节点中的1.0,2.0和3.0是节点所保存的分值.在跳跃表中节点按照各自保存的分值从小到大排列.obj成员对象:各个节点中的o1,o2,o3是节点所保存的对象.
跳跃表本质是解决查找问题,当我们想要寻找一种查找效率高的解决方案时,可能会想到折半查找,建立树形结构等等.但是这两种方式分别存在一定的局限性.折半查找是针对有序数组的,链表没有办法直接进行位置定位.而建立树形结构的缺点也显而易见,如果想要树的平衡性,则需要对树进行左旋右旋等等操作,维护一棵树的平衡成本相对较高.
因此我们想到了在原有的链表的基础上,对链表建立的时候进行分层管理的方式来解决链表查询时需要对链表进行全部递归查询的复杂度.
如上图,如果我们查找数据为7的元素,则只需要进行一次查询即可命中数据,而且载入缓存的数据只有第四层的数据.大大加速了查找的效率.
随机层数:
对于每一个新插入的节点,都需要调用一个随机算法给他分配一个合理的层数,源码在t_zset_.c/zslRandomLevel(void)中被定义:
1/* Returns a random level for the new skiplist node we are going to create.
2 *
3 * 返回一个随机值，用作新跳跃表节点的层数。
4 *
5 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
6 * (both inclusive), with a powerlaw-alike distribution where higher
7 * levels are less likely to be returned.
8 *
9 * 返回值介乎 1 和 ZSKIPLIST_MAXLEVEL 之间（包含 ZSKIPLIST_MAXLEVEL），
10 * 根据随机算法所使用的幂次定律，越大的值生成的几率越小。
11 *
12 * T = O(N)
13 */
14int zslRandomLevel(void) {
15 int level = 1;
16 while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
17 level += 1;
18 return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
19}
而ZSKIPLIST_MAXLEVEL在redis.h中被定义:
1#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */
直观上期望的目标是50%的概率被分到Level 1,25%的概率被分到level 2,一次折半.Redis跳跃表默认允许最大层数为32,也就是说,理论上,当有2`64个元素时,才能达到32层.所以定义32层完全够用了.
压缩列表(ziplist)
压缩列表是列表键和哈希键的底层实现之一.当一个列表键只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么redis就会使用压缩列表来做列表键的底层实现.redis>RPUSH mytest 1 3 5 10086 "hello" "world"
redis>OBJECT ENCODING mytest "ziplist"
对应的数据结构图:
| 属性 | 类型 | 长度 | 用途 |
|---|---|---|---|
| zlbytes | uint_32t | 4B | 记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配， 或者计算 zlend的位置时使用 |
| zltail | uint_32t | 4B | 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节：通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。 |
| zllen | uint_16t | 2B | 记录了压缩列表包含的节点数量：当这个属性的值小于UINT16_ MAX （65535）时， 这个属性的值就是压缩列表包含节点的数量；当这个值等于 UINT16_MAX 时， 节点的真实数量需要遍历整个压缩列表才能计算得出。 |
| entryX | 列表节点 | 不定 | 压缩列表包含的各个节点，节点的长度由节点保存的内容决定。 |
| zlend | uint_8t | 1B | 特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。 |