redis

Redis设计与实现笔记1-数据结构

参考\搬运资料: http://redisbook.com/index.html

设计哲学

设计简单优于巧妙实现:

表现 原因
不处理循环引用 不产生循环引用。数据结构足够简单，最多2层。
不处理事务回滚 程序员自己处理代码错误
换个角度就是，没把握做好的事情就干脆不做了。
解决问题的方法就是不产生问题。不写错代码，很科学，很彻底XD。

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

1
2
3
4
5
6
7
8
9
struct sdshdr {
    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;
    // 记录 buf 数组中未使用字节的数量
    int free;
    // 字节数组，用于保存字符串
    char buf[];//\0结尾，不计入len
};

类似head-body结构的消息。比\0分割的C字符串简单易用多了，性能更高，代价是付出了更多的内存。
之所以最后用上了\0结尾,是为了重用一部分c库里的字符串库，进一步降低了使用成本。

性能优势点:

  1. 获取字符串长度: O(1)
  2. 空间预分配，减少系统调用。
  3. 惰性空间释放，减少系统调用。

安全性优势点:

  1. 有效防止缓冲区溢出
  2. 二进制安全，可以保存\0。

缺点：

  1. 如果有大量字符串缩短，内存泄露严重。

sdscat

字符串拼接：

计算拼接后总长度len，扩展空间为2*len，拼入字符串。最后一定会有一半free空间。

空间预分配

假如现有空间不足以存放字符串：

  • 总长度len<1MB: 总空间为2*len+1;
  • 总长度len>=1MB: 总空间为len+1MB+1。
    换句话说，预分配的空间上限是1MB，尽量为len。
    这么做的目的是减少空间申请、回收的系统调用性能开销。

惰性空间释放

字符串缩短的时候，默认不进行内存回收（可能内存泄露）。
需要手动调API回收。

链表(RPush)

单个节点：

1
2
3
4
5
6
7
8
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
typedef struct list {
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
} list;

哈希表（HSet）

单个节点:

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {  // 三者取其1
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

整个表:

1
2
3
4
5
6
7
8
9
10
11
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
typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表,有两个，第二个扩容时候用
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1。 扩容时候用。
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

dictType:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct dictType {
    // 计算哈希值的函数
    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;

sizemask为3的话，也就是0x11，就是说取最后两位作为哈希序号，也就是0~3，4个数。
所以此时hash表长度为4。以此类推，sizemask有n位,哈希表长度就有2^n。

渐进式hash

具体还是要参见: http://redisbook.com/preview/dict/rehashing.html

逐步把ht[0]中的数据迁移到ht[1]中。rehashidx为0的时候，表示0号位置已经全部迁往ht[1],依次类推，直到全部迁完。
交换ht[0],ht[1]以后，rehashidx改为-1.
在此过程中ht[0]不会有新插入，新请求全部去ht[1]。

扩容/rehash的触发

由时间事件serverCron根据负载因子来决定是否进行扩容。
扩容的实际执行是由1个专门的单线程来进行; (类似cms一样高响应,一次resh一个桶,尽量不阻塞线上读写请求)
相比之下,concurrentHashMap的扩容则由多线程进行,阻塞所有读写,高吞吐低响应。

跳表

有序集合使用。(ZSET)
节点源码: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct zskiplistNode {
    // 后退指针
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
} zskiplistNode;

跳表容器:

1
2
3
4
5
6
7
8
typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
} zskiplist;

从高层向低层找:

  1. 在找的过程中用update[]数组记录每一层插入位置的上一个节点，
  2. 用rank[]数组记录每一层插入位置的上一个节点在跳跃表中的排名。
  3. 根据update[]插入新节点，插入完成后再根据rank[]更新跨度信息。

整数集合

整数集合（intset）是集合键的底层实现之一： 当一个集合只包含整数值元素， 并且这个集合的元素数量不多时， Redis 就会使用整数集合作为集合键的底层实现。

1
2
SADD numbers 1 3 5 7 9
OBJECT ENCODING numbers # 查看底层实现 "intset"

升级

默认用最小数据类型，新数据太大的话，会对整个集合数据类型升级，并且移动全部元素。
因此最坏时间复杂度为O(n)。

升级后不会降级。

压缩列表（ziplist）

压缩列表（ziplist）是列表键和哈希键的底层实现之一。
适用条件: 整数、小字符串。

1
2
RPUSH lst 1 3 5 10086 "hello" "world"
OBJECT ENCODING lst # 底层结构: ziplist

推荐文章