redis设计与实现--数据结构与对象

发表于 | 分类于 |
字数统计: 2k | 阅读时长 ≈ 8

本文根据《redis设计与实现》，浅谈redis的数据结构实现原理。

引言

redis在业界受到越来越多的青睐，以其优秀的性能广受欢迎，抽空看了下《redis的设计与实现》，记录下读书笔记，根据书中的篇幅，一共分为下面几个部分，数据结构与对象，单机数据库的实现，多机数据库的实现。本文是数据结构与对象篇。

目前最新的redis的代码可能和书中有所出入。

字符串

结构

  • redis设计与实现的sds版本
    1
    2
    3
    4
    5
    6

    struct sdshdr {
        unsigned int len;
        unsigned int free;
        char buf[];
    };
graph LR
subgraph SDS
    len(len int 长度)
    free(free int 未使用的字节数)
    buf(buf char 字符串)
end
    buf --> str('a''b''\0')

自动扩容&空间预分配

  • 例子，当要保存一个10字节的字符串
graph LR
subgraph SDS
    len(len int 长度)
    free(free int 未使用的字节数)
    buf(buf char 字符串)
end
    len --> len10(10)
    free --> free10(10)
    buf --> str('0''1'...'9''\0')

当修改需要扩容的时候，如果小于1MB，会预分配同等大小的free空间，最后分配的是2X+1，其中多1字节用于保存结尾的'\0'

惰性删除

删除操作不会真的释放空间，而是改变free和len的大小。下次需要使用的时候，空间足够不用再次分配内存。

杜绝缓冲区溢出

c语言的字符串，需要调用方来保证分配足够的内存空间，防止出现溢出，但这其实是很危险的，由于sds保存了字符串的长度信息，可以高效的进行检查，扩容，保证不出现溢出。

二进制安全

对于c语言的字符串，'\0'是末未结束符，意味着，字符串内不能出现结束符，否则字符串将被截断，所以针对二进制数据，c语言的字符串无法保存。sds则不同。由于sds不再使用'\0'来判断字符串结束，并且所有api都是二进制安全的，因此可以直接保存二进制数据。

部分兼容c字符串

由于sds的末尾还是以'\0'结束，因此，当保存文本的数据的时候，sds可以兼容c语言的字符串操作函数。

链表

结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

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;
graph LR
subgraph List
    head(head listNode* 头)
    tail(tail listNode* 尾)
    len(len unsigned long 节点个数)
    dup(dup 复制节点的接口)
    free(free 释放节点的接口)
    match(match 判断节点相等的接口)

end


head --> node1
node1 --prev--> NULL1(NULL)
node1 --next--> node2
node2 --prev--> node1
node2 --next--> node3
node3 --prev--> node2
node3 --next--> NULL

tail --> node3
len --> 3

双向链表

redis的链表实现是双向链表，头结点前置和尾节点的后置都是NULL

接口实现

为了让链表更加通用，提供了三个接口函数以便使用者实现，分别是复制，释放，比较相等的操作，外部使用者可以根据存储的不同的对象，进行不同的实现，一种多态的编程方式。

字典

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
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

hash表

  • 这是一个没有rehash的字典
graph LR

subgraph 字典
    type
    privdate
    ht
    rehashindex
end


subgraph hash表
    table(table-hash表数组)
    size(size-hash表大小)
    sizemask
    used(used-已有节点数)
end

subgraph DictEntry*数组-桶
    0
    1
    2
    3
end

subgraph 键值对
    k1
    v1
end

subgraph DictEntry1
    k2
    v2
end


subgraph hash表1
    table1
    size1
    sizemask1
    used1
end


ht --> ht0
ht --> ht1
ht0 --> table
ht1 --> table1

table --> 0
2 --> NULL(NULL)
1 --> NULL1(NULL)
3 --> NULL2(NULL)
0 --> k1
k1 --next--> k2
k2 --next--> NULL3(NULL) 
size --> 4
sizemask --> 3num(3)
used --> 2num(2)

table1 --> NULL4(NULL)
size1 --> 0num(0)
sizemask1 --> 0num1(0) 
used1 --> 1num2(0)
rehashindex --> -1

接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct dictType {
    //计算hash值的函数接口
    unsigned int (*hashFunction)(const void *key);
    //复制键的函数接口
    void *(*keyDup)(void *privdata, const void *key);
    //复制值的接口
    void *(*valDup)(void *privdata, const void *obj);
    //对比键的接口
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    //销毁键的接口
    void (*keyDestructor)(void *privdata, void *key);
    //销毁值的接口
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

hash算法

提到hash表，不可避免的要提到hash算法，redis的字典的hash算法是通过上面的定义的接口，让使用者传入具体的实现，也是一种多态的方式，比如计算hash值的时候，会根据上面的hashFunction的具体实现，调用不同的计算方式。

MurmurHash

默认采用的murmurhash2算法

解决冲突

从上面的图可以看出，redis采用的是拉链式解决冲突，在键值对后面通过next指针进行索引。

rehash

当hash表负载过大或者过低时，会触发rehash的动作。试图增大或者缩小hash表的大小。

负载因子

load_factor=used/size

  • 负载因子越大，说明使用的越多，需要扩容。
  • 负载因子越小，说明空闲的越多，需要缩容。
扩缩容
- 若负载因子小于0.1，则进行缩容

渐进式rehash

rehash不是一次性完成的，因为，redis中的hash表可能非常大，如果一次性rehash，会严重阻塞服务器，所以redis的做法是分批次进行，也叫渐进式rehash。这就是为什么ht会有两个大小的原因。

  • rehashindex=0表示rehash开始，每次加1
  • 不是集中式的rehash，而是分布在每次查找，删除，更新操作中
  • 读取会同时读取ht[0]和ht[1]
  • 写入，不会再写入ht[0]

跳跃表

graph LR
subgraph 跳表
    header(header)
    tail(tail)
    level(level)
    length1(length)
end

subgraph Node
    L132(L32)
    L_(...)
    L5(L5)
    L4(L4)
    L3(L3)
    L2(L2)
    L1(L1)
end

subgraph Node1
    L14(L4)
    L13(L3)
    L12(L2)
    L11(L1)
    Score1(Score=1)
    Obj1(obj)
end

subgraph Node2

    L22(L2)
    L21(L1)
    Score2(Scor=2)
    Obj2(obj)
end

subgraph Node3
    L35(L5)
    L34(L4)
    L33(L3)
    L32(L2)
    L31(L1)
    Score3(Scor=3)
    Obj3(obj)
end

L5 --3--> L35
L4 --1--> L14
L14 --2--> L34
L3 --1--> L13
L13 --2--> L33
L2 --1--> L12
L12 --1--> L22
L22 --1--> L32
L1 --1--> L11
L11 --1--> L21
L21 --1--> L31

L31 --0--> NULL1(NULL)
L32 --0--> NULL2(NULL)
L33 --0--> NULL3(NULL)
L34 --0--> NULL4(NULL)
L35 --0--> NULL5(NULL)
L132 --> NULL6(NULL)

header --> L1
tail --> Obj3
level --> 5
length1 --> 3
  • 上面是跳表的结构，其实如果把跳表退化到只有一层，跨度全部是1，就可以看成是链表，同样，跳表可以看成是对一个节点有多层的描述的数据结构，每一层是链表。
  • 跳表是在分数的维度组织的，obj是关联的对象。分数相同，但是obj不同，属于不同的节点。
  • 遍历的时候，只需要找level中跨度最小的的层，依次往后走就能遍历整个跳表。
  • 跨度值可以帮助快速定位范围的节点。

整数集合

graph LR
subgraph 整数集合
    encoding(encdoding)
    length1(length)
    contents(contents)
end

subgraph contents
    1
    2
    3
end

contents --> 1
  • 有序
  • 整数集合可以根据元素范围，选择合适的编码格式，针对小元素集合，可以选择更少的bit来保存，节约内存
  • 自动进行编码升级，当集合无法表示一个大的数字，就会触发升级，使用更多的bit来保存，所以添加的复杂度是O(N)
  • 不支持降级
codelover wechat
原创公众号
-----若有不妥，敬请斧正-----