redis底层结构与对象

数据结构

SDS

SDS(simple dynamic string 动态简单字符串 )

结构体

1
2
3
4
5
6
7
struct sdshdr { 
//buf占用长度
int len;
//buf可用空间长度
int free;
char buf[];
}

图解

优点

  1. o(1)获取字符串长度
    C语言在获取字符串长度时会遍历整个字符串,遍历到’\0’为止,SDS直接读free属性

C的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
int cont_str(char *s)
{
int i = 0;
while (s[i++] != '\0');
return i;
}

int main()
{
char string[] = "test";
int c = cont_str(string);
printf("%d", c);
return 0;
}

=========
输出5(test+'\0'
  1. 杜绝缓冲区溢出
    标准C语言函数提供了一些没有边界检查的字符串处理函数 strcat()、strcpy()、 sprintf() 、vsprintf() 并不会检测溢出情况

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
     #include <stdio.h>
    #include <string.h>

    int main()
    {
    char str[14];
    strcpy(str, "www.");
    strcat(str, "phpzjj.");
    strcat(str, "com");
    printf("%s",str);
    return 0;
    }

    ======
    www.phpzjj.com + '\0' 长度为15字符,我们申请14字符就会存在缓冲区溢出报错的情况

    SDS在遇见buf空间不够时会动态扩容(1M以下空间X2,1M以上按1M递增)
    代码实现

  2. 减少内存分配次数

    • 空间预分配
      sdscat()函数每次执行的时候会调用 sdsMakeRoomFor,空间够的时候就返回不够进行动态扩容并预留了充分的空间。
    • 惰性空间释放
      SDS直接修改 int len; int free; 2个属性不会真正的去释放
  3. 二进制安全
    C语言在处理字符串的时候会把'\0'作为结尾符,如果字符串中包含这个关键字会出现问题,SDS会主要读 int len 然后取固定长度。

  4. 兼容C字符串函数
    SDS维护了'\0'结尾符,兼容了C原生的类库

链表

结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

typedef struct list {
//表头节点
listNode *head;
//表尾节点
listNode *tail;
//链表节点数
unsigned long len;
//节点复制函数
void *(*dup)(void *ptr);
//节点释放函数
void (*free)(void *ptr);
//节点值对比函数
int (*match)(void *ptr, void *key);
}

typedef struct listNode {
//前置节点
struct listNode *prev;
//后置节点
struct listNode * next;
//节点值
void *value
}

图解

优点

  1. 双端:获取某个节点的前后节点时间复杂度为o(1)
  2. 无环:头尾节点都指向null
  3. 带表头和表尾指针:通过list结构体可以o(1)找到表头和表尾
  4. 带表头指针和表尾指针获取链表头尾复杂度o(1)
  5. 带链表长度技术器获取链表节点数量复杂度o(1)
  6. 多态:void指针保存节点值,dup,free,match设置指定类型函数,可以保存不同类型的值

字典

结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
/*
* 字典
*/

typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时,值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 目前正在运行的安全迭代器的数量
int iterators; /* number of iterators currently running */
} dict;


/*
* 哈希表
*
* 每个字典都使用两个哈希表,
* 从而实现渐进式 rehash 。
*/
typedef struct dictht {
// 哈希表数组
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;
} v;
// 指向下个哈希表节点,形成链表
struct dictEntry *next;
} dictEntry;

图解

dict

写入

1
2
3
4
5
// 计算给定键的哈希值
#define dictHashKey(d, key) (d)->type->hashFunction(key)

// 计算新哈希表的哈希值,以及节点插入的索引位置
h = dictHashKey(d, de->key) & d->ht[1].sizemask;

键冲突

在hash键计算冲突的情况下,会以链表的方式把冲突数据写入链表头部(单项链表,放尾部o(n),头部则是o(1)redis的优化就很细) dictEntry

rehash

装载因子: load_factor = ht[0].used/ht[0].size

rehash策略: 当load_factor超过合理范围区间哈希表会进行扩张(used*2)或者收缩 (used/2)

load_factor 大于等于1 大于等于5
BGSAVE/BGREWRITEAOF 等待结束 不用等待结束

渐进式rehash

  1. ht[1]分配空间,同时持有ht[0]和ht[1]两个哈希表
  2. dict结构中的rehashidx设置为0表示开始渐进加载
  3. 期间每次crud都会进行一次对应操作一次顺带迁移,并且rehashidx会加一
  4. 迁移完成后rehashidx设置为-1表示完成

crud操作时会同时查找2个哈希表,期间新增加的键值对会保持到ht[1]。

跳跃表

跳跃表性能媲美平衡树并且实现比它简单,平均O(logN),最坏O(N),是有序集合的底层实现之一。跳表的实现是链表加上多级索引的结构

结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
* 跳跃表
*/
typedef struct zskiplist {

// 表头节点和表尾节点
struct zskiplistNode *header, *tail;

// 表中节点的数量
unsigned long length;

// 表中层数最大的节点的层数
int level;

} zskiplist;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* ZSETs use a specialized version of Skiplists */
/*
* 跳跃表节点
*/
typedef struct zskiplistNode {

// 成员对象
robj *obj;

// 分值
double score;

// 后退指针
struct zskiplistNode *backward;

// 层
struct zskiplistLevel {

// 前进指针
struct zskiplistNode *forward;

// 跨度
unsigned int span;

} level[];

} zskiplistNode;

实现思路

最直观的是下面这种表现方式,原始链表上衍生出了多级索引加快定位数据的速度。

极客时间插图

《redis设计与实现》中插图是这样表示的

redis设计与实现-跳表

两者从直观感受上来说还是有一定的差别的,我尝试用图形来表示但是发现它是一种错误的理解表示形式

错误的理解

他们的区别是极客时间中跳表的表示是一类更为宏观的理解,既跳表是链表+多级索引
redis书上更偏向于代码实现,既生成当前zskiplistNode 用代码逻辑来达到宏观上的链表+多级索引,最后发现了一种比较贴合两者之前的画法。

每插入一个数据,redis跳表的实现会抛硬币即50%的几率来决定层数(最大32层)这样可以解决跳表数据过于集中退化成链表的情况,一个数据会包含多层,每层指针会指向本层的下一个数据

多个zskiplistNode可以组成一个跳表,zskiplist更好的提供了定位头尾节点的能力并且在o(1)复杂度获取相关的长度和层数信息

整数集合

结构体

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct intset {

// 编码方式
uint32_t encoding;

// 集合包含的元素数量
uint32_t length;

// 保存元素的数组
int8_t contents[];

} intset;

整数集合会根据encoding值来确定contents[]中的数据类型,它包含int16_t int32_t int64_t

升级

整数集合是可以提供动态向上升级的,但是不能降级这要做的好处能有效节省内存空间,做到有需要再升级。

压缩列表

列表键和哈希键的底层实现之一,当列表键只包含少量列表项,并且列表项是小整数值或者比较短的字符串,就会采用压缩列表。压缩列表是一种为了节约内存而设计的顺序型数据结构。

zlbytes|zltail|zllen|entry1| entry2 |…| entryN | zlend
:-:|

属性|类型|长度|用途|
:-:|:-:|:-:|:-:|:-:
zlbytes|uint32_t|4字节|整个压缩列表占用内存字节数
zltail|uint32_t|4字节|压缩列表尾节点到起始地址多少字节
zllen|uint16_t|2字节|包含节点数,小于65535是真实数据,等于需要遍历技术得出
entryx|列表节点|不定|压缩列表的各个节点
zlend|uint8_t|1字节|特殊值0XFF标识末端

压缩列表节点

previous_entry_length encoding content
  • previous_entry_length

    小于254为1字节,大于等于254会扩展为5字节(5字节高位表示254,后4字节表示实际长度)

    高位表示大于254

    实际大小

previous_entry_length encoding content
0X05
previous_entry_length encoding content
0XFE00002766
1
通过当前节点  p- previous_entry_length 可以得到上一个节点
  • encoding

    记录了content的长度用约定好的二进制结构表示

  • content

    节点数据

连锁更新

压缩列表会存在连锁更新的情况O(n)的时间复杂度,但是它所储存的数据量级不会太大这种情况是设计内可以接受的

embstr

专门用于保存短字符串的一种优化编码方式REDIS_ENCODING_RAW 会调用两次内存分配函数分别创建redisObject和结构sds, embstr通过一次内存分配函数给到redisObject和sds的连续空间。

优点

  • REDIS_ENCODING_RAW 内存分配两次降为一次
  • 释放同理降为一次
  • 放在连续内存中更友好的利用缓存优势

注:1.redis会把long double也当成字符串保存哎需要的时候转回long double过后再变成字符串保存起来
2. embstr是只读的做修改操作会转换为SDS

对象

每当我们新建一个键值对时至少会建立两个对象,一个是键值对的键一个是值。对象的值不会固定是某一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef struct redisObject {

// 类型
unsigned type:4;

// 编码
unsigned encoding:4;

// 对象最后一次被访问的时间
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */

// 引用计数
int refcount;

// 指向实际值的指针
void *ptr;

} robj;

对象编码

1
2
3
4
5
6
7
8
9
#define REDIS_ENCODING_RAW 0     /* Raw representation  简单字符串sds*/ 
#define REDIS_ENCODING_INT 1 /* Encoded as integer */
#define REDIS_ENCODING_HT 2 /* Encoded as hash table */
#define REDIS_ENCODING_ZIPMAP 3 /* Encoded as zipmap */
#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define REDIS_ENCODING_INTSET 6 /* Encoded as intset */
#define REDIS_ENCODING_SKIPLIST 7 /* Encoded as skiplist */
#define REDIS_ENCODING_EMBSTR 8 /* EMBSTR 简单动态字符串*/

对象对应关系

类型 编码 对象
string REDIS_ENCODING_INT 整数字符串对象
string REDIS_ENCODING_EMBSTR EMBSTR简单动态字符串
string REDIS_ENCODING_RAW 简单字符串SDS
list REDIS_ENCODING_ZIPLIST 压缩列表
list REDIS_ENCODING_LINKEDLIST 双端链表
hash REDIS_ENCODING_ZIPLIST 压缩列表
hash REDIS_ENCODING_HT 字典
set REDIS_ENCODING_INTSET 整数集合
set REDIS_ENCODING_HT 字典
zset REDIS_ENCODING_ZIPLIST 压缩列表
zset REDIS_ENCODING_SKIPLIST 跳表

字符串对象

REDIS_ENCODING_INT

long int

REDIS_ENCODING_RAW SDS

string leng > 32

REDIS_ENCODING_EMBSTR

string leng <= 32

列表对象

REDIS_ENCODING_ZIPLIST

  • 列表所有对象保存的字符串元素长度都小于64字节
  • 列表对象保存元素量小于512个

REDIS_ENCODING_LINKEDLIST

不满足上述2个条件会转换

哈希对象

REDIS_ENCODING_ZIPLIST

  • 哈希对象保存所有键值对键和值的字符串长度都小于64字节
  • 哈希对象数量小于512个

哈希对象在压缩列表中的存储是紧凑的先键后值

zlbytes zltail zllen key vlen key1 vlen1 zlend

REDIS_ENCODING_HT

不满足上述2个条件会转换

集合对象

REDIS_ENCODING_INTSET

  • 保留所有对象都是整数
  • 集合元素不超过512个

REDIS_ENCODING_HT

  • 不满足上述2个条件会转换

如果我没理解错,集合在使用字典作为底层实现的时候是没有值的,只会用到键

有序集合对象

REDIS_ENCODING_ZIPLIST

每个集合元素两个紧挨一起进行保存,第一个节点保存元素成员第二个元素保存元素分值,按分值从小到大进行排序。

  • 有序集合保存元素小于 128个
  • 所有元素成员长度都小于 64字节

REDIS_ENCODING_SKIPLIST

不满足上面2个要求会转换成跳表

有序集合使用跳表时会用到zset对象,同时用到了map和zskiplist。他们需要交叉服用功率大增,map能保证单个查询O(1)的查询效率,zskiplist能保证区间查询O(logN)的效率。指针指向同一份内存地址也不会有空间浪费的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
* 有序集合
*/
typedef struct zset {

// 字典,键为成员,值为分值
// 用于支持 O(1) 复杂度的按成员取分值操作
dict *dict;

// 跳跃表,按分值排序成员
// 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
// 以及范围操作
zskiplist *zsl;

} zset;

注: redis会共享整数对象

参考文档

极客时间-跳表
segmentfault-跳表

  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!

请我喝杯咖啡吧~