redis存储原理与数据模型笔记

redis是不是单线程

redis其实不是单线程，有如下几个线程

• redis-server: 命令处理，网络事件的监听；
• bio_close_file:异步关闭大文件；
• bio_aof_fsync:异步aof刷盘
• bio_lazy_free:异步清理大块内存
• io_thd_*:io多线程
• jemalloc_bg_thd:jemalloc后台线程

redis单线程的含义

redis单线程的含义是指命令处理在一个单独的线程中。

命令处理为什么是单线程

单线程的局限

• 不能有耗时操作
• 对于redis而言会影响性能

redis有没有io密集型或cpu密集型

io密集型

• 磁盘io
  fork进程，在子进程持久化
  异步刷盘
• 网络io
  服务多个客户，造成io密集
  数据请求或返回数据量比较大
  开启io多线程

cpu密集型

为什么不采用多线程

redis是kv数据库，v支持丰富的数据结构（string、list、hash、set、zset），加锁复杂，锁粒度不好控制；

多线程频繁的cpu上下文切换，抵消多线程的优势。

redis中dict数据结构源码解析

typedef struct dict {
	dictType *type;
    void *privdata;
    dictht ht[2]; //ht[0]是原来的hashtable，ht[1]是扩容或缩容后的hashtable
    long rehashidx;
    unsigned long iterators;
}dict;
1
2
3
4
5
6
7

typedef struct dictht {
	dictEntry **table;
    unsigned long size; //数组长度，必须为 2^n
    unsigned long sizemask; //数组长度-1，用于将hash(key) % size优化为 hash(key) & sizemask
    unsigned long used; //实际存储的元素个数
} dictht;
1
2
3
4
5
6

hash冲突

• 负载因子 = $used/size$， 负载因子越大冲突越大，复杂度可能由$O(1)$变为$O(n)$

• 扩容

  • 当负载因子>1，翻倍扩容

• 缩容

  • 负载因子 < 0.1，恰好大于 used 的$2^n$。比如used = 9，那么$size=16=2^4$时候缩容。

• 扩容和缩容会导致 rehash

• 缩容条件没有设置为负载因子 < 1是为什么？

  防止频繁缩容，会造成内存操作的频繁，会造成io密集。

scan

scan cursor [MATCH pattern] [COUNT count] [TYPE type]
1

使用方法：

• 这是一种迭代遍历方法，数据很大的时候使用keys *可能会导致阻塞；
• 采用高位进位加法的遍历顺序， rehash 后的槽位在遍历顺序上是相邻的；
• 遍历的目标是：不重复、不遗漏
• 会出现一种重复的情况：在scan过程当中，发生两次缩容的时候，会发生数据重复；如果出现重复在server端去重。

渐进式rehash

• 对dict增删改查移动一步，_dictRehashStep()
• 不能整体进行移动
• dictRehashMilliseconds(dict *d, int ms)定时处理
• reactor中，一次事件循环中 ，处理网络事件后再处理定时事件。只有在空闲的时候才会定时的去操作一下定时事件

对象编码

zset

• skiplist ： 数量大于128或者有一个字符串长度大于64
• ziplist：子节点数量（zset-max-ziplist-entries）小于等于128，且字符串长度小于等于64

set

• intset（整数数组）：元素都为整数且节点数量小于等于512(set-max-intset-entries)
• dict：元素有一个不为整数或者数量大于512

hash

• dict：节点数量大于512,或字符串长度大于64
• ziplist：节点数量(hash-max-ziplist-entries)，且字符串长度小于等于64（hash-max-ziplist-value）

list

• quicklist (双向链表)
• ziplist

string

• int:字符串长度小于等于20 且能转成整数
• raw：字符串长度大于44
• embstr：字符串长度小于等于44

跳表

介绍

• 跳表（多层级有序链表）结构用来实现有序集合；

• 鉴于 redis 需要实现 zrange 以及 zrevrange 功能；需要节点间最好能直接相连并且增删改操作后结构依然有序；

• B+ 树时间复杂度为$h\ast O({\log }_{2}n)$,由于其分裂操作导致

• 时间复杂度：有序数组通过二分查找能有$O({\log }_{2}n)$时间复杂度；平衡二叉树也能获得$O({\log }_{2}n)$时间复杂度

理想跳表

每隔一个节点生成一个层级节点；模拟二叉树结构，以此达到搜索时间复杂度为$O({\log }_{2}n)$ ;
这是一个空间换时间的结构；

但是如果对理想跳表结构进行删除增加操作，很有可能改变跳表结构；如果重构理想结构，将是巨大的运算；考虑用概率的方法来进行优化；从每一个节点出发，每增加一个节点都有$\frac{1}{2}$的概率增加一个层级，$\frac{1}{4}$ 的概率增加两个层级， $\frac{1}{8}$的概率增加3 个层级，以此类推；经过证明，当数据量足够大（256）时，通过概率构造的跳表趋向于理想跳表，并且此时如果删除节点，无需重构跳表结构，此时依然趋向于理想跳表；此时时间复杂度为 $(1-\frac{1}{n^c})O({\log }_{2}n)$；

个人理解：跳表通过增加层级，让链表也能够执行二分查找。

数据结构

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough
for 2^64 elements */
#define ZSKIPLIST_P 0.25 /* Skiplist P = 1/4
*/
/* ZSETs use a specialized version of Skiplists
*/
typedef struct zskiplistNode {
    sds ele;
	double score; // WRN: score 只能是浮点数
	struct zskiplistNode *backward;
	struct zskiplistLevel {
    	struct zskiplistNode *forward;
   	 	unsigned long span; // 用于 zrank
	} level[]; //柔性数组，不算空间大小，free时不需要考虑level
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
    unsigned long length; // zcard
    int level; // 最高层
} zskiplist;
typedef struct zset {
    dict *dict; // 帮助快速索引到节点
    zskiplist *zsl;
} zset;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 工程实现上跳表用循环双向链表实现

​ 方便范围查询，通过$O({\log }_{2}n)$的时间复杂度快速找到边界，然后在最底层找到范围内所有元素)

io多线程

用于优化网络io密集的问题

• io多线程主要解决send和encode的步骤
• io多线程开启的总前提：多个并发连接，一条连接不会用io多线程
• 打日志的写到redis时候优化read和decode
• 从redis获取大量数据（获取1-100名数据）优化send和encode
• 命令处理（即compute）是在主线程中完成的。