Redis底层原理和数据结构-总结篇_redis底层是epoll嘛

本文数据结构部分内容转自：SmartKeyerror
先了解数据结构，后看具体应用部分，本文着重应用部分的优缺点进行总结！数据结构部分仅仅做初步了解介绍，源码实现具体请参考如下目录自行学习，本文以6.0源码为主：

• Github-redis-源码
• JAVA修仙-Redis设计与实现-笔记
  
• Redis设计与实现
• 黄建宏-Redis3.0-中文注释版本源码

Redis数据结构

SDS

SDS是什么？
SDS 为
Simple 
Daynamic 
String 的缩写，表示简单动态字符串，Redis 在原有的
C 语言的字符串之上进行了一层封装,根据数组char buf [] 长度不同，包含了五种结构体：分别是sdshdr5（源码提示没有用到仅用其中的flags字段），sdshdr8，sdshdr16，sdshdr32，sdshdr64。
C语言字符串
C语言用字符数组来模拟字符串，即用 char buf[] 来表示一个字符串！字符串以‘\0’结尾该字符在ACSII码表中第一个位置值为0，所以有了长度标记就可以根据长度判断数据是否已经结束，保证数据连续性！

sdshdr结构如下：

/*
 * 保存字符串对象的结构，位于源码 sds.h 中
 */
struct sdshdr {
    // buf 中已占用空间的长度
    int len;
    // buf 中剩余可用空间的长度
    int free;
    // 数据空间
    char buf[];
};
1
2
3
4
5
6
7
8
9
10
11

sds优点

• 常数复杂度获取字符串长度。
• 杜绝缓冲区溢出。
• 减少修改字符串长度时所需的内存重分配次数。
• 二进制安全。
• 兼容部分 C 字符串函数。

sds缺点

• 相较于原有
C 字符串，额外了多出了
8 字节的存储空间

链表

• Redis 和
Linux 内核一样，也是采用双向链表实现，并没有使用单链表来节省内存

• Redis中 list 这一结构体主要包含了
3 个成员: 头指针、尾指针，以及双向链表所包含的节点数量

• 链表结构的应用非常广泛，包括数据量较小时的列表、发布订阅、慢查询和监视器等

字典（hash）

• 采用哈希表实现，并且处理哈希冲突的方式为拉链法

• 拉链法： 即链地址法，java中的HashMap在存储数据就是用的这种方法，把具有相同散列地址的值放在同一个单链表中，有m个散列地址就有m个链表，同时用指针数组T[0…m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到以T[i]为指针的单链表中。T中各分量的初值应为空指针。

为什么采用渐进式
 rehash扩容

• 1.Redis 底层网络模型为单线程+epoll，也就是说，发送至
Redis 的命令是串行执行的

• 2.若采用直接扩容的方式，那么当遇到巨大的哈希表时，数据的复制将花费很长时间，势必会阻塞其它命令的执行，从而导致整体性能下降

• 3.在渐进式
rehash 过程中，会同时存在
ht[0]、ht[1] 两张哈希表，并且同时对外提供服务
  
  刷新过程

• 当我们新增一个
key 时，新的
key-value
将会保存在
ht[1] 中，也就是那个容量更大的哈希表中

• 当我们查找、更新以及删除某一个
key 时，会在两张哈希表上进行，而不仅仅只是对
ht[0] 或者是
ht[1] 中的某一个哈希表进行操作

• Redis 本身的数据库也是使用哈希表实现的，所以才能在
O(1) 时间内查找到某一个
key

跳跃表

跳跃表是一种有序的数据结构，可以简单的认为它是一种多层链表，支持平均
O(logn)、最坏
O(n) 复杂度的节点查找

跳跃表是实现有序集合底层数据结构之一，当有序集合
中的元素较多时，Redis 就会选择跳跃表来实现该集合

整数集合

整数集合的底层实现为数组，并且元素在该数组中以有序、无重复的方式排列，通过名字我们就知道它能够实现集合，并且是整数集合
整数集合中我们可以保存
3 种类型的整数，分别为
16 位、32 位和
64
位的整数

这么实现的原因还是那个初衷: 节省内存。因为在一般情况下，程序不知道用户会保存多大的整数，所以为了避免整数溢
出，可能会直接使用
64
位来保存。

Redis 出于这个考虑对
intset 进行动态编码，如果当前集合能够用
int16_t 来保存，那就用
int16_t。如果用户后续新增了
一个
32 位整数，那么
Redis 会对
intset 进行升级，改用
int32_t 来保存

ZipList-压缩列表

压缩列表，ziplist 由上图所示组件构成，其目的就是为了节省内存。当一个
LIST
中只包含少量的元素，并且每一个元素要
么是小正数，要么是长度很短的字符串，Redis 就会采用压缩列表来实现

理解压缩列表的一个关键点就在于，entry 中保存的数据大小是不固定的，也就是说，对于一个
ziplist 而言，我们既可以往里面扔
int，也可以往里面儿扔
string

entry 中保存的是数据，而非指针

因此，如果我们向
ziplist 中添加、删除、查询等操作时，平均时间复杂度均为
O(N)，并且添加和删除这两个操作的最坏
时间复杂度为
O(N^2)。不过没关系，反正
ziplist 只会在小数据量时使用，即使是
O(N^2) 也不会有太大的性能问题

源码实现可以参考：https://segmentfault.com/a/1190000017328042

源码精进 - Redis数据结构

redisObject介绍

redisObject 是 Redis 类型系统的核心, 数据库中的每个键、值, 以及 Redis 本身处理的参数, 都表示为这种数据类型.

/*
 * Redis 对象 位于源码 server.h 的头文件中
 */
typedef struct redisObject {
    // 类型：长度
    unsigned type:4;
    // 对齐位：长度
    unsigned notused:2;
    // 编码方式：长度
    unsigned encoding:4;
    // LRU 时间：长度（相对于 server.lruclock）
    unsigned lru:22;
    // 引用计数：长度
    int refcount; 32
    // 指向对象的值：长度
    void *ptr; 64

} robj;
此为对象头占用空间长度和为： 4+2+4+22+32+64 = 128bit = 16 Byte
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

type、 encoding 和 ptr 是最重要的三个属性.

/*
 * 对象类型 type
 */
#define REDIS_STRING 0  // 字符串
#define REDIS_LIST 1    // 列表
#define REDIS_SET 2     // 集合
#define REDIS_ZSET 3    // 有序集
#define REDIS_HASH 4    // 哈希表

/*
 * 对象编码 encoding 
 */
 
/* Objects encoding. Some kind of objects like Strings and Hashes can be
 * internally represented in multiple ways. The 'encoding' field of the object
 * is set to one of this fields for this object. */
#define OBJ_ENCODING_RAW 0     /* Raw representation */
#define OBJ_ENCODING_INT 1     /* Encoded as integer */
#define OBJ_ENCODING_HT 2      /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of listpacks */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */
#define OBJ_ENCODING_LISTPACK 11 /* Encoded as a listpack */


# ptr 是一个指针, 指向实际保存值的数据结构, 这个数据结构由 type 属性和 encoding 属性决定.

# redisObject 的 type 属性如果为 REDIS_LIST, encoding 属性为 OBJ_ENCODING_QUICKLIST , 那么这个对象就是一个 list , 它的值保存在一个快速列表内, 而 ptr 指针就指向这个快速列表;

# redisObject 中定义了上面提到的几种不通的数据结构，也就是对象编码encoding ，根据我们实际输入的命令即type的不同，redis会将对象指针ptr指向实际保存值数据结构！
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

Redis实际的数据类型：

• 字符串（String）
• 哈希（hash）
• 字符串列表（list）
• 字符串集合（set）
• 有序字符串集合（sorted set）

以下内容为本人的实际使用命令总结（部分图片源于网络，侵删）： 按照redis具体数据类型的特点、应用、结构图、使用场景、以及常用命令展开介绍

通用命令：

String类型详解

特点

• 最大支持521MB，建议不超过100KB存储

• 底层数据结构：sdshdr + redisObject

• 具体编码(encoding)实现：

    长度小于44时 = embstr
    长度大于等于44时 = raw 
    为数字则采用 int 类型
  1
  2
  3

• embstr和 raw 均为 sdshdr + redisObject的数据结构实现，不同之处在于内存分配时embstr分配一次，而raw会分配两次！

• 扩容机制：字符串小于1M，采用的是2倍扩容，也就是多分配100%的剩余空间，当大于1M，每次扩容，只会多分配1M的剩余空间。

String的应用

• 实现计数（统计页面的访问数） incr自增 decr自减 incrby指定值加上自定义的增量 decrby指定值加上自定义的减量
• 缓存基础信息，简单的 KV 缓存
• 实现分布式的ID生成器

String数据结构图：

这里需要注意：Redis3.0中embstr、raw的分界线为39。而Redis5.0高版本因为采用了多种不通长度sdshdr的数据格式，当字符串长度比较小的时候，会用sdshdr8来存储，len和alloc共占用2byte，flags占用1byte，\0结尾占用1byte，一共是4byte，64byte-16byte（对象头）-4byte=44byte，所以在高版本的Redis下，embstr、raw的分界线为44。

扩容部分的源码

小于1MB newlen *= 2; 可以看出为2倍扩容： 否则大于1MB时，则扩充1MB
1

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    //获取空闲长度
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
 
    /* Return ASAP if there is enough space left. */
    //空间足够  直接返回
    if (avail >= addlen) return s;
    //计算新的长度
    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    //如果新长度小于1MB
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2; //扩容2倍
    else
        newlen += SDS_MAX_PREALLOC; //SDS_MAX_PREALLOC = 1024*1024
 
    type = sdsReqType(newlen);
 
    /* Don't use type 5: the user is appending to the string and type 5 is
     * not able to remember empty space, so sdsMakeRoomFor() must be called
     * at every appending operation. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
 
    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);
    return s;
}
源码的原文链接：https://blog.csdn.net/zhang199563/article/details/115384259
其SDSHdr定义部分的源码见：
https://blog.csdn.net/qq_33774822/article/details/106490475
其他参考文章见：
https://zhuanlan.zhihu.com/p/164799075
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

string 的常用命令（非所有，以下这些应该够用）：

哈希Hash类型详解

特点

• OBJ_ENCODING_HT采用数组+链表来实现. 数组来做hash散列, 链表用来解决hash冲突的问题，可参考jdk7的hashmap实现。
• 底层编码形式有：OBJ_ENCODING_ZIPLIST、OBJ_ENCODING_HT
• 为了节省内存，会默认采用OBJ_ENCODING_ZIPLIST编码
• filed不能相同，值可以相同
• 数据量小时采用ziplist节省空间、大时采用hashtable实现，对应阈值在redis.conf配置文件中设置：
  hash-max-ziplist-value 64 // ziplist中最大能存放的值长度
  hash-max-ziplist-entries 512 // ziplist中最多能存放的节点数量
• 不支持从hashtable降级转换成ziplist的功能！
• 便于同类数据进行归类存储
• 相比String操作更节省内存、cpu，存储更节省空间，同时hash的过期功能不能用在field上面，只能用在key上面，redis集群架构下不适合大规模使用！

应用

• 统计网站访问量 ，格式参考：hincrby user:1:info pageView count 参考微信某用户对应文章的访问量统计！
• 缓存电商购物车，格式参考：
  key：用户id，filed：商品id，value：购物车的商品数量

以下是关于hash电商购物车中的具体应用可以使用对应的命令完成购物车的CRUD
链接参考：知乎JAVA十一

hash数据结构图

源码

#hash的结构说明
typedef struct redisObject {undefined
unsigned type:4; // hash类型
unsigned encoding:4; // hash结构，此字段为OBJ_ENCODING_ZIPLIST或OBJ_ENCODING_HT
unsigned lru:LRU_BITS; // 上一次操作的时间
int refcount; // 引用计数，便于内存管理
void *ptr; // 指向底层的数据结构
} robj;


# hash表的节点
typedef struct dictEntry {
    //节点的key
    void *key;
    //节点的值 v , v 可以是指针, 也可以是uint64整数, 也可以是int64整数, 还可以是浮点数
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    //下一个节点
    struct dictEntry *next;
} dictEntry;



# hash表结构体
typedef struct dictht {
    //hash表的指针数组, dictEntry * 表示hash节点的指针, 再加一个 *, 也就是dictEntry ** 表示数组的首地址
    dictEntry **table;
    //hash数组大小, 一般为 2^n
    unsigned long size;
    //hash数组长度掩码, sizemask =  size - 1
    unsigned long sizemask;
    //hash表的kv对的个数
    unsigned long used;
} dictht;

源码解析参考：https://blog.csdn.net/hmh13548571896/article/details/103549259
hash本身实现接近于java的hashtable源码不过多分析！
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

hash的常用命令

List类型详解

特点

• 底层采用OBJ_ENCODING_QUICKLIST
• 有序，可以存放重复的数据，左右两边均可以插入、弹出！
• 作为数据库可以非常快的将元素插入

应用

• 获取最新的更新列表！例如将用户最近更新的文章ID使用LPUSH 推入list，然后当用户访问首页时使用LRANGE 0 9 获取最近10个更新内容！以下为两个元素的例子：
  redis> LPUSH mylist “world”
  (integer) 1
  redis> LPUSH mylist “hello”
  (integer) 2
  redis> LRANGE mylist 0 -1
  1) “hello”
  2) “world”
  注：-1代表从尾部元素第一个元素开始的索引

• 存储最近的10个项目，使用LTRIM KEY 0 9 仅保存最近的10个元素。获得一个固定的列表长度！以下是使用例子：
  rpush mylist 1 2 3 4 5
  (integer) 5
  ltrim mylist 0 2
  OK
  lrange mylist 0 -1
  1) “1”
  2) “2”
  3) “3”

• 进程通信，实现生产者-消费者模型，list有的特性适合实现队列，并且通常作为进程间通信系统的构建模块：阻塞操作。
  简单的消息队列：一个进程用LPUSH向list中推送数据，另一个进程作为消费者使用RPOP消费数据！没有数据RPOP只返回NULL，因为返回NULL需要轮询的缘故，Redis提供了更好的解决方案：
  BRPOP：左阻塞删除
  BLPOP：右阻塞删除
  栈实现：LPUSH + LPOP
  队列实现：LPUSH + RPOP
  定长队列：LPUSH + LTRIM
  消息队列：LPUSH + BRPOP

数据结构

目前的Redis版本为：6.2 ，底层统一采用OBJ_ENCODING_QUICKLIST
源码

list的常用命令

set 类型详解

特点
应用
数据结构
源码
set的常用命令

sort Set 类型详解

特点
应用
数据结构
源码
sort Set的常用命令

性能测试见总结篇（2）