Redis

基于单线程(IO读取&数据读写是单线程)并支持多种数据结构的高性能内存数据库，支持高效数据读写操作。

数据结构

String

预分配空间：采用动态字符串格式存储，类似于STL中vector的设计，当字符串大小小于1M时，会预分配和当前大小相同的空间；当字符串大小大于1M时，会预分配1M大小的空间；

惰性删除：缩短字符串时不立即删除空间，而是标注待后续使用；

String(datasize < 1M)

String(datasize > 1M)

List

双链表，顺序访问，便于删除和插入；

Redis里的list是一个链表，由于链表本身插入和删除比较块，查询的效率较低，所以常常被用于做异步队列比较合适；Redis里的List设计非常牛逼，当数据量比较小的时候，数据结构是压缩链表，而当数据量比较多的时候就是快速链表运用的场景：在业务中异步队列，使用rpush/lpush操作队列，使用lpop和rpop出队列；

Redis的发布订阅的存储就是采用链表的形式；

List

异步队列结构可参考

异步队列

Set

用于存储无序不重复的一组值，例如抽奖的编号、排行榜；

Hash

一个hash表中有多个hash节点，每个hash节点存储一组键值对，采用链表解决hash冲突，即将多个哈希值相同的键值对连接在一起。

随着数据量的逐渐扩大，hash表再分配(即rehash过程)时启用单独的异步线程渐进式的讲现有键值对rehash到新的哈希表中，在渐进式的rehash过程中，用户对原hash表的删改查等操作会在新旧两个hash表中生效。

具体Rehash过程可参考下图

ht[0]为原hash表，ht[1]为新hash表；需要将ht[0]中的元素rehash至ht[1]中

Rehash过程

Zset：跳跃表

跳跃表可以理解为有序的链表结构，利用链表的插入/删除的便利性，同时有序存储减少了链表顺序查询的时间；平均查询时间为O(N/2)~O(N)，跳跃表的结构如下：

skiplist

• head：指向跳跃表的表头节点
• tail：指向跳跃表的表尾巴=节点
• level：记录目前跳跃表内层数最大的那个节点层数，图中L开头的数字表示第几层，每一层有若干节点
• length：记录跳跃表的长度，即跳跃表目前包含节点的数量
• backward：记录节点的后退指针。它指向当前节点的前一个节点

1. 关于分层：分层的思想可以通过二分查找来理解，只是二分查找是每次将查找范围分为两层，图中将查找范围分为32层；
2. 关于有序：假设待插入节点大小为b1，相当于查找( a< b1 < c) 小于b1的最大节点a与大于b1最大节点c，将节点b1插入在a与c中即可；

线程模型

高并发

• IO多路复用+单线程

1.Redis基于内存存储及上述数据结构(时间复杂度是O(n)~O(log(n)))设计决定了对Redis操作属于I/O密集型服务，所以最初依赖于单线程的Redisqps可达8w+；

2.单线程设计可以减少多线程引起同一buf的同步成本；

3.单线程设计可内核线程上下文切换成本；

• 多线程

随着业务的发展，基于单线程的Redis存储已经无法满足需求，如何利用多核提高服务的并发度应该要拉出来讨论了。

有关线程模型可参考文章(https://cloud.tencent.com/developer/article/1793593 )。

为了充分利用多核，Redis6.0衍生出 多个IO线程+主线程模式。IO线程只负责IO的Write和read，主线程负责handle业务逻辑。

从下图可以看出：

• IO线程一批读或者一批写，主线程先获取一批可读scoket，IO线程读完毕->主线程处理完毕->IO线程写完毕后再继续执行下一步；个人理解这样做的目的可避免内存的同步竞争；
• 多个IO线程充分利用了多CPU优势缓解Scocket读写引起的用户态至内核态系统调用成本；

Redis多进程步骤

图片来源：https://ruby-china.org/topics/38957%EF%BC%89

持久化

基于内存的Redis必然要考虑其持久化方式：

AOF

保存对数据库操作的命令，数据load入内存过程类似于回放；

RBD

定期保存数据库数据，数据load简单直接，数据按照一定的时间周期checkpoint肯定会存在部分数据丢失;

思维导图

参考文献：

https://www.cnblogs.com/powertoolsteam/p/redis.html

http://dockone.io/article/10137

https://ruby-china.org/topics/38957%EF%BC%89

https://strikefreedom.top/multiple-threaded-network-model-in-redis