Redis设计与实现简要笔记

2018-01-01 约 1433 字预计阅读 3 分钟

字符串实现

简单动态字符串（Simple Dynamic String)，简称SDS。

1
2
3
4
5
6


// 数据结构
struct sdshdr{
  int len;
  int free;
  char buf[];
};

与c的字符串的差异

查询字符串的时间复杂度不同，c 为 O(n), SDS 为 O(1)

对于字符串扩展（拼接），sds相对于c语言，不会出现缓冲区溢出问题。

减少修改字符串时带来的内存重分配次数

— SDS实现了空间预分配和惰性空间释放两种优化策略

二进制安全

sds可以重用部分<string.h>函数库

链表

源代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


/*
 * 双端链表节点
 */
typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

} listNode;

 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;

    // 节点值复制函数
    void *(*dup)(void *ptr);

    // 节点值释放函数
    void (*free)(void *ptr);

    // 节点值对比函数
    int (*match)(void *ptr, void *key);

    // 链表所包含的节点数量
    unsigned long len;

} list;

Redis 链表的特性

双端：获取某个节点的前置节点和后置节点的时间复杂度都是 O(1)

无环

带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的时间复杂度为O(1)

带链表长度计数器，获取长度的时间复杂度为O(1)

多态：使用void(*)指针来保存节点值，通过list结构的属性来设置类型特定函数，所以链表可以用来保存不同类型的值

字典

底层实现：一个hash表中有多个hash节点，每个hash节点保存一个键值对。

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


/*
 * 字典
 */
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;

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


/*
 * 哈希表
 *
 * 每个字典都使用两个哈希表，从而实现渐进式 rehash 。
 */
typedef struct dictht {
    
    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


/*
 * 哈希表节点
 */
typedef struct dictEntry {
    
    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;

hash算法

1

index = dict->type->hashFunction(key)  & dict->ht[x].sizemask;

Rehash 流程

为字典的ht[1]分配内存空间，内存空间的大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（ht[0].used的值）

拓展操作 ht[1]的大小为 >= ht[0].used * 2 的第一个2的n次方的值。

收缩操作 ht[1]的大小为 >= ht[0].used 的第一个2的n次方的值。

ht[0] »rehash» ht[1]
释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白hash表

其中第二部采用的是渐进式rehash操作

整数集合的实现

 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;

特性：整数集合的升级(操作灵活，解决内存)，但是不支持降级。

压缩列表

压缩列表是Redis为了节约内存开发的，是由一系列的特殊编码的连续的内存块组成的顺序型数据结构。

对象

 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;

对象的类型

REDIS_STRING
REDIS_LIST
REDIS_HASH
REDIS_SET
REDIS_HSET

对象的编码

REDIS_ENCODING_INT
REDIS_ENCODING_EMBSTR (embst编码的简单字符串)
REDIS_ENCODING_RAW (SDS)
REDIS_ENCODING_HT (字典)
REDIS_ENCODING_LINKEDLIST(双端链表)
REDIS_ENCODING_ZIPLIST(压缩列表)
REDIS_ENCODING_INTSET(整数集合)
REDIS_ENCODING_SKIPLIST(跳跃表和字典)

目录