Redis简介

Redis全称为Remote Dictionary Server(远程字典服务) 是一个由Salvatore Sanfilippo开发的一款开源的，使用C语言编写，支持网络、基于内存，可选持久化的Key-Value数据库；其支持丰富的数据类型：字符串(String)、哈希(Map)、 列表(list)、 集合(sets) 和 有序集合(sorted sets)、位图(bitmaps)、HyperLogLogs等数据结构。目前开发主要由Redis Labs公司赞助，最新稳定版为6.2.4。

Redis 快到什么程度？

在探究redis为什么这么快之前，我们先来分析下影响一个系统快慢的指标有哪些。

• 响应时间：指系统对请求做出响应的时间，用户对该指标有直观感受。

• 吞吐量：指单位时间内处理请求的数量。

• 并发数：指系统可以同时承载的正常使用系统功能的用户的数量。

吞吐量 = 并发数量/响应时长

因此响应时长越短，并发数越高，吞吐量就越好，应用响应能力就越优秀。

下面我们可以通过redis提供的基准测试工具redis-benchmark测试下到底有多快。 硬件环境：centos7 单核CPU(主频 2.1GHz) 2G内存、 redis版本 3.2.4

• 100并发,常用命令每秒执行次数
  image.png

• 100并发，使用10 万随机 key 连续GET、 SET 200 万次
  image.png

• 100并发，使用10 万随机 key ，GET、 SET 200 万次，16个指令一批次
  image.png

  压测过程中CPU使用率 16%

  [图片上传失败...(image-f03165-1624415605556)]

  由上测试可以看到redis的一般读写速度可以达到10w+以上，范围查询也有1w+ qps的表现，通过pipeline批量执行读写更是可以达到50w+以上。

Redis 为什么这么快？

系统实现来看

• key-value（字典）结构 字典结构的时间复杂度为O(1)，类比java中的HashMap。

• 绝大部分请求是纯粹的内存操作，速度非常快。 redis是一个内存数据库，内存读写相对于磁盘IO来说要快几个数量级，系统运行如果需要等待磁盘I/O的完成，将导致整个系统的性能下降。

• C语言编写 C语言简洁高效，可以直接操作内存，编译后生成的机器码基本上和直接写汇编生成的机器码是相当的；但语法限制不严格，面向过程缺乏封装，难以掌握，对使用者要求高。

IO模型

image.png

图中fd就是套接字，当select/epoll等系统函数监听到一旦fd上有请求到达时，就会出发相应的事件，这些事件会被放进一个事件队列，Redis 以单线程对该事件队列不断进行处理。 为什么redis采用单线程效率这么高？

• 基于非阻塞的IO多路复用机制。

• redis的获取 (socket 读)、解析、执行、内容返回 (socket 写) 采用单线程，有以下好处：

  • 避免了不必要的多进程或者多线程的上下文切换和竞态条件消耗的CPU，不用去考虑各种锁的问题，不存在加锁、释放锁操作，没有因为可能出现死锁而导致的性能消耗；

  • 避免线程不安全的情况，简化数据结构和算法的实现（不用考虑并发）；

采用的单线程而不是因为单线程性能高而使用单线程，主要是因为单线程实现很简单，且限制redis性能主要是内存及网络IO。实际上Redis6.0中的多线程也只是IO多线程，将主线程的 IO 读写任务拆分出来给一组独立的线程执行，使得多个 socket 的读写可以并行化，命令执行仍是单线程。

Redis的数据结构是精心设计的

redis主要的基本数据结构有

• string 字符串类型

• list 列表类型

• hash 哈希表类型

• set 无序集合类型

• zset 有序集合类型

Redis的核心对象为redisObject位于server.h源码中，结构定义如下

typedef struct redisObject { 
 unsigned type:4;// 类型
 unsigned encoding:4;// 编码  
 unsigned lru:LRU_BITS; //LRU算法,对象最后一次被访问的时间
int refcount; //引用计数 
void *ptr;// 底层数据结构的指针 
} robj;

type类型

encoding 编码

不同类型编码与对象的结构关系

image.png

image.png

下面我们sds及list两种类型为例讲解redis的数据结构设计

string

Redis中，字符串是可以修改的，长度是动态可变的，在底层它是以字节数组的形式存在的，被称为简单动态字符串sds(simple dynamic string)。数据结构定义如下：

struct sdshdr { 
    int len;   // buf 中已占用空间的长度
    int free;  //  buf 中剩余可用空间的长度
    char buf[]; // 内容,字节数组
};

image-20210618215247254.png

如上图表示空闲空间长度为0、已经使用的空间长度为4的SDS字符串。同时SDS为了能够使用部分C字符串函数，遵循了C字符串以空字符（\0）结尾的惯例，保存空字符的1字节不计算在SDS len属性中。

SDS有以下优点：

1. 保存了len属性,获取字符串长度, 常数复杂度O(1) , c语言中获取字符串长度为O(n)。

2. 增长时空间预分配,减少内存的频繁分配，惰性内存空间回收。

   • C字符串在处理增长或者缩短操作时，程序会对这个C字符串的数组进行一次内存重分配操作。

   • 对SDS的空间进行扩展的时候，程序不仅会为SDS分配修改所必须的空间，还会为SDS分配额外的未使用的空间,这样可以减少连续执行字符串增长操作所需的内存重分配次数。

   • 对SDS的字符串进行缩短操作的时候，程序不会立刻使用内存重分配来回收缩短之后多出来的字节，使用free属性将多余字节调配记录下来，通过惰性空间释放策略，SDS避免了缩短字符串时所需的内存重分配次数也为将来可能存在的增长操作提供了优化。

3. 避免缓冲区溢出

   • C语言字符串不记录自身长度，容易造成缓冲区溢出。如当对两个内存紧挨着的字符串中的一个执行拼接操作（strcat），就会导致concat的内容覆盖了另一个字符的内容。

   • 当 SDS 进行字符串扩充时，首先会检查当前的字节数组的长度是否足够。如果不够的话，会先进行自动扩容，然后再进行字符串操作。

4. 二进制安全

   • SDS的API都是二进制安全的。

   • SDS的buf属性为字节数组，程序不会对其中的数据做任何的限制，数据存进去是什么样子，读出来就是什么样子，因此可以用来保存的音频、图片、视频等数据。

list

版本3.2之前，当列表对象中元素的长度比较小或者数量比较少的时候，采用ziplist来存储，当列表对象中元素的长度比较大或者数量比较多的时候，则会转而使用双向列表linkedlist来存储。

这两种链表存储方式的优缺点

• 双向链表linkedlist节点带有prev、next指针、head指针和tail指针，获取前置节点、后置节点、表头节点和表尾节点的复杂度都是O(1)，便于在表的两端进行push和pop操作，但是它的内存开销比较大，每个node上除了要保存数据之外，还要额外保存两个指针；另外双向链表的各个节点是单独的内存块，地址不连续，容易产生内存碎片。

• ziplist存储在一段连续的内存上，由一系列特殊编码的连续内存块组成的顺序型数据结构，查找，添加、修改、删除操作时间复杂度为O(n)，且添加、修改、删除时需要频繁的申请和释放内存，因此它适合数据比较小的情况。

ziplist 结构

redis/src目录下ziplist.c中：

image.png

• zlbytes：32bit无符号整数，表示ziplist占用的字节总数（包括本身占用的4个字节）；

• zltail：32bit无符号整数，记录最后一个entry的偏移量，方便快速定位到最后一个entry；

• zllen：16bit无符号整数，记录entry的个数；

• entry：存储的若干个元素，可以为字节数组或者整数；

• zlend：ziplist最后一个字节，是一个结束的标记位，值固定为255。

image.png

如上图所示，zlbytes的值为0x50（十进制80），表示压缩列表的总长度为80字节。 zltail的值为0x3c（十进制60），entry3元素距离列表起始位置的偏移量为60，起始位置的指针加上60就能算出表尾节点entry3的地址。 zllen的值为0x3（十进制3），表示压缩列表包含3个节点。

ziplist entry结构

image.png

ziplist entry由previous_entry_length、encoding、content三部分组成。 previous_entry_length previous_entry_length 是一个变长字段

• 前一个元素的长度小于254字节时，previous_entry_length用1个字节表示；

• 前一个元素的长度大于等于254字节时，previous_entry_length用5个字节进行表示，此时，previous_entry_length的第一个字节是固定的254（0xFE）（作为这种情况的一个标志），后面4个字节才表示前一个元素的长度。

encoding Redis为了节约空间，对encoding字段进行复杂的设计，Redis通过encoding来判断存储数据的类型。

• 00xxxxxx 最大长度位 63 的短字符串，后面的6个位存储字符串的位数；

• 01xxxxxx xxxxxxxx 中等长度的字符串，后面14个位来表示字符串的长度；

• 10000000 pppppppp rrrrrrrr ssssssss tttttttt 特大字符串，需要使用额外 4 个字节来表示长度。第一个字节前缀是10，剩余 6 位没有使用，统一置为零；

• 11000000 表示 int16；

• 11010000 表示 int32；

• 11100000 表示 int64；

• 11110000 表示 int24；

• 11111110 表示 int8；

• 11111111 表示 ziplist 的结束，也就是 zlend 的值 0xFF；

• 1111xxxx 表示极小整数，xxxx 的范围只能是 (0001~1101), 也就是1~13。

content 保存节点的值，节点值可以是字节数组或者整数，值的类型和长度由encoding决定。

什么条件下会用ziplist？

• 列表对象保存的所有字符串元素的长度都小于等于64字节

• 列表对象保存的元素数量小于等于512个

  
  
  image-20210618214019087.png

image-20210618214349155.png

quickList

3.2版本后列表为将ziplist和双向列表linkedlist的各自优点结合后的quickList

image.png

其结构源码位于quicklist.h中

typedef struct quicklistNode {
    struct quicklistNode *prev; /*指向链表前一个节点的指针*/
    struct quicklistNode *next; /*指向链表后一个节点的指针*/
    unsigned char *zl;
    unsigned int sz;             /* ziplist占用byte数*/
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* 数据类型，RAW==1 or LZF==2  */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* 这个节点以前是否被压缩过 */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

typedef struct quicklistLZF {
    unsigned int sz; /* 表示压缩后的ziplist大小*/
    char compressed[]; /*存放压缩后的ziplist字节数组*/
} quicklistLZF;

typedef struct quicklist {
    quicklistNode *head;        /*指向头节点的指针*/
    quicklistNode *tail;        /*指向尾节点的指针*/
    unsigned long count;        /* 所有ziplist中entry的数量 */
    unsigned long len;          /* quicklistNode的数量 */
    int fill : 16;              /* 16bit，ziplist大小设置，存放list-max-ziplist-size参数的值 */
    unsigned int compress : 16; /* 16bit，节点压缩深度设置，存放list-compress-depth参数的值 */
} quicklist;

image.png

黄色背景是普通的ziplist节点，紫色背景是被压缩后的ziplist节点(LZF节点)，LZF是种无损压缩算法。 redis为了节省内存空间，会将quicklist的节点用LZF压缩后存储，不是所有节点均压缩，可以通过配置compress的值，compress为0表示所有节点都不压缩，否则就表示从两端开始有多少个节点不压缩，图中所示，compress就是1，表示从两端开始，第1个节点不做LZF压缩。compress默认是0(不压缩)，具体可根据业务实际使用场景去配置。

问题：为什么quicklist 的全部ziplist节点不都压缩？

list两端的数据变更最为频繁，像lpush,rpush,lpop,rpop等命令都是在两端操作，如果频繁压缩或解压缩会代码不必要的性能损耗。

由结构可见quicklist是一个双向链表的结构，内部节点quicklistnode均保存一个ziplist，每个ziplist中保存一批列表的数据(ziplist大小可通过redis.conf中list-max-ziplist-size配置)，这样既可以避免大量链表指针带来的内存消耗，也可以避免ziplist更新导致的性能损耗。

综上可见redis在数据结构设计上下了很多心思，几乎到了变态的地步，很多结构追求时间与空间的平衡。

总结

redis 能做到如此之快，除了其内存操作、IO模型、极致的数据结构外，也包括其精妙的系统设计，如简洁的协议、渐进式rehash、key的惰性过期策略、multi事务操作等等。本文所讲为抛砖引玉之作，远远不能够涵盖redis的极致设计，redis中有更多精彩的设计值得我们大家去探索去深究。