Redis 有几种数据结构？Zset 是如何实现的？

字符串（String）、列表（list）、字典（hash）、集合（set）、有序集合（sortSet）.

# 字符串

源码

/*
- 保存字符串对象的结构
*/
struct sdshdr {

   // buf 中已占用空间的长度
   int len;

   // buf 中剩余可用空间的长度
   int free;

   // 数据空间
   char buf[];
};

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

sds与c字符串的区别

sds获取字符串长度的复杂度为O(1),c的是O(n)
c的api是不安全的，可能造成缓冲区溢出，sds的是安全的。
修改N次字符串，c需要N次内存分配。sds最多需要N次分配。sds有空间预分配和惰性回收。
sds可以使用部分c的字符串库。

# 链表

源码

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

  // 前置节点
  struct listNode *prev;

  // 后置节点
  struct listNode *next;

  // 节点的值
  void *value;

} listNode;

/*
* 双端链表结构
*/
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;

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

[外链图片转存中...(img-ua4uHhOc-1653145947289)]

# hash

源码

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

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

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

} dictEntry;

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

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

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

} dictht;

/*
* 字典
*/
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
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
54
55
56
57
58
59
60
61
62
63
64

[外链图片转存中...(img-3IEt2xy5-1653145947290)] 2. reHash

扩容场景：有BGSAVE或者BGREWRITEAOF时，负载因子超过5. 无BGSAVE或者BGREWRITEAOF时，负载因子超过1. 扩容为第一个大于等于ht[0].used*2的2的幂

缩容场景：负载因子小于0.1 缩容为第一个大于等于ht[0].used的2的幂

负载因子：ht[0].used/ht[0].size

渐进式rehash: rehashidx指向正在hash的索引。rehashidx=-1表示未进行rehash 每次访问dict结构时rehash一个索引

[外链图片转存中...(img-A0e54HI9-1653145947290)]

# 跳跃表

源码

/*
* 跳跃表节点
*/
typedef struct zskiplistNode {

   // 成员对象
   robj *obj;

   // 分值
   double score;

   // 后退指针
   struct zskiplistNode *backward;

   // 层
   struct zskiplistLevel {

       // 前进指针
       struct zskiplistNode *forward;

       // 跨度
       unsigned int span;

   } level[];

} zskiplistNode;

/*
* 跳跃表
*/
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

[外链图片转存中...(img-MbZS62dp-1653145947291)]

# 整数集合

源码

typedef struct intset {
   
   // 编码方式
   uint32_t encoding;

   // 集合包含的元素数量
   uint32_t length;

   // 保存元素的数组
   int8_t contents[];

} intset;

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

[外链图片转存中...(img-hdTbZZhS-1653145947291)] 2. 编码升级添加一个元素可能导致编码升级。编码升级需要做三件事

扩展空间
转变现有元素的类型并发至在合适的位置上。保证原有顺序防止
防止新加入的元素。新加入的元素一定是最大或最小的，所以放在最前或者最后

[外链图片转存中...(img-0R00I0BO-1653145947291)]

# 压缩列表

压缩列表是 Redis 为了节约内存而开发的，由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值

源码

/*
* 保存 ziplist 节点信息的结构
*/
typedef struct zlentry {

   // prevrawlen ：前置节点的长度
   // prevrawlensize ：编码 prevrawlen 所需的字节大小
   unsigned int prevrawlensize, prevrawlen;

   // len ：当前节点值的长度
   // lensize ：编码 len 所需的字节大小
   unsigned int lensize, len;

   // 当前节点 header 的大小
   // 等于 prevrawlensize + lensize
   unsigned int headersize;

   // 当前节点值所使用的编码类型
   unsigned char encoding;

   // 指向当前节点的指针
   unsigned char *p;

} zlentry;

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

示意图 [外链图片转存中...(img-NMDF8Bnt-1653145947292)] [外链图片转存中...(img-5KdqaS0e-1653145947292)]

# RedisObject

Redis 使用对象来表示数据库中的键和值，每次当我们在 Redis 的数据库中新创建一个键值对时，我们至少会创建两个对象，一个对象用作键值对的键（键对象），另一个对象用作键值对的值（值对象）。

源码

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
10
11
12
13
14
15
16
17
18

[外链图片转存中...(img-uT4NW4Ki-1653145947292)] 2. 类型和编码的对应关系 [外链图片转存中...(img-jkooRnC4-1653145947293)] 3. 字符串对象

值	编码
可以用long保存的整形	int
可以用long，double保存的浮点	embstr或row
长度太长，不可以用long，double保存的浮点	embstr或row
小于39字节的字符串	embstr
大于39字节的字符串	row

row要两次申请内存，两次释放内存。为这俩对象RedisObject、SdsStr。embstr申请一次释放一次，而且申请的是连续的内存空间，能更好的利用缓存。

链表对象

inkedList和zipList的转换临界值:每个元素长度都小于64、元素个数小于512。满足以上两个条件才能用zipList

hash对象

hashtable和zipList的转换临界值:每个元素长度都小于64、元素个数小于512。满足以上两个条件才能用zipList

集合对象

hashtable和intset的转换临界值:每个元素都是int、元素个数小于512。满足以上两个条件才能用intset

内存回收

redis是用C实现的，C没有自动回收内存的机制。RedisObject中的refCount记录对象的引用个数，当refCount=0的时候自动释放内存。

对象共享

0- 9999这1w个整数是共享对象。字符串不做共享对象，因为对比匹配太复杂

编辑

上次更新: 2022/05/22, 00:01:01

← 模糊查询是如何实现的？为什么 Redis 在单线程下能如此快？→