redis底层结构与对象

字数统计: 3k   |   阅读时长≈ 11 分钟

数据结构

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-跳表

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

请我喝杯咖啡吧~