redis设计和原理

本文是《redis设计与实现–黄健宏》一书的读后感和笔记。

SDS（simple dynamic string）

简单动态字符串： redis自定义的字符串结构：

1
2
3
4
5
6
7
struct sdshdr {
  // 已经使用的长度
  int len;
  // 未使用的长度
  int free;
  char buf[];
}

为什么不使用C语言的字符串字面量的原因：

  1. 获取字符串长度复杂度为O(1), 而不是O(N)
  2. 杜绝缓冲区溢出： 增加字符串内容而忘记分配合适的长度造成覆盖等
  3. 减少修改字符串的内存重分配： 主要采用了2种策略
    1. 空间预分配： 低于1MB长度时，扩展会翻倍，超过1MB时每次多分配1MB
    2. 惰性空间释放： 缩短字符串时并不内存分配，只是修改free的长度
  4. 二进制安全： 可以保存除文本外，图像、视频、音频等2进制信息，因为不以\0来判断结尾，而是len
  5. 兼容部分C语言库函数： sds依然保留\0结尾，所以可以重复使用部分字符串函数。

链表

list的数据结构

单个节点: 是一个双向链表

1
2
3
4
5
6
7
typedef struct listNode {
  struct listNode *prev;

  struct listNode *next;

  void *value;
} listNode;

list结构：

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct list {
  listNode *head;

  listNode *tail;

  unsigned long len;

  // 几个函数 
  void (*dup)(void *ptr);
  void (*free)(void *ptr);
  void (*match)(void *ptr,void *key);
} list;

dict

保存键值对

数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct dictht {
  // hash entry array
  dictEntry **table;

  // hash table size
  unsigned long size;

  // 用于计算索引值，总是等于size-1
  unsigned long sizemask;

  // used size
  unsigned ling used;
} dictht;

下面是dictEntry: 每个entry后面可以跟一串entry， 用于到hash出的索引冲突时。

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct dictEntry {
  void *key;

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

  // 链表
  struct dictEntry *next;
} dictEntry;

下面才是字典的最后封装：

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct dict {
  // 类型特定函数
  dictType *type;

  // 私有数据保存传给特定函数的可选参数
  void *privdata;

  // hash table
  dictht ht[2];

  // rehash index: 当rehash没有进行时值为-1
  int rehashidx;
} dict;
  1. hash table为什么需要2个？
    因为ht[1]是在rehash时使用的，后面会说
  2. rehashidx的作用是啥？
    是一个计数器，标记rehash的进度和是否完成。
  3. 绘制出dict的数据结构图

hash算法

1
2
3
4
hash = dict->type->hashFunction(key);

// 看到这里的sizemask的作用了把
index = hash & dict->ht[x].sizemask;

这个索引值就是dictEntry数组里的下标。

hash算法： MurmurHash

冲突解决

采用链地址法： 采用前插法，在dictEntry形成链表。

rehash

  1. 为什么需要？
    因为一段时间后hash表会变得要么很大，要么很少，为了维持一个负载均衡因子，会有2种可能：扩展和收缩。
  2. rehash的步骤？
  3. 分配空间给ht[1]
    1. 扩展： newSize >= used*2
    2. 收缩： newSize >= used
  4. 转移，这是一个渐近的过程，并不是一下就过去了，后面会说
  5. 释放ht[0], 交换ht[1]为ht[0]
  6. 什么时候hash表会扩展？
  7. 负载因子： load_factor = ht[0].used / ht[0].size
  8. 当没有BGSAVE或BGREWRITEAOF在执行且负载因子>=1, 不知什么时候会大于1？
  9. 当上述命令在执行，且负载因子>=5，执行时负载因子会变大，因为copy on write技术需要节约内存
  10. 什么时候收缩？
    当负载因子 < 0.1

渐近式rehash

  1. why？
    因为当键值对很大时，一次性转移会暂停服务，需要慢慢来
  2. 步骤
  3. 这个过程会同时用到ht[0],ht[1]
  4. 初始rehashidx设为0
  5. 每移动一个key-value，rehashidx++
  6. 直到完成，rehashidx重置为-1
  7. 在rehash阶段，CRUD怎么办？
    修改会只在ht[1]上进行， 查询会从ht[0]到ht[1]

跳跃表

  1. 什么是跳跃表？解释其原理。
    见： skip list理解与java实现
  2. 在redis中哪里用到了跳跃表？
    2个地方：1.有序集合集（sorted set） 2.集群节点中用作内部数据结构

对象

实际上，redis的键值都是对象。

1
2
3
4
5
6
typedef struct redisObject {
  unsigned type:4;
  unsigned encoding:4;
  // 指向底层数据结构的指针
  void *ptr;
}

type

有： string, list, hash, set, zset, 通过下面的命令可以查看：

1
2
3
4
5
redis> SET msg "hello world"
OK

redis> TYPE msg
string

encoding

表示使用哪种数据结构，有：int,embstr,raw,hashtable,linkedlist,ziplist,intset,skiplist,
可以使用OBJECT ENCODING xxx查看：

1
2
3
4
5
redis> SET msg "hello string"
OK

redis> OBJECT ENCODING msg
"embstr"

一个数据结构可以有多种编码：

  1. string: int/raw/embstr
  2. list: ziplist/linkedlist
  3. hash: ziplist/hashtable
  4. set: intset/hashtable
  5. zset: ziplist/skiplist

问：

  1. 在什么条件由一种结构换到另一种？
  2. 有什么是embstr呢？ 见下面。

string对象

字符串对象的编码可以是： int, raw, embstr

  1. long能存下的数字肯定是int编码
  2. 小于等于39字节的恩字符串是 embstr
  3. 大于39字节的是 raw，用sds存

embstr与raw的区别？
embstr只分配一次内存就将redisObject和sds存好，也只需要释放一次，而raw是2次。

long double类型的浮点数也是存的字符串对象， 在需要运算时才转换。

编码的转换

编码在一定条件是会转换的，比如：

  1. int会转为embstr或raw， 在整数中加入字符串时。
  2. embstr没有修改函数，要修改时也会转成raw。