Redis学习笔记一、Redis数据结构和底层原理

《Redis设计与实现》学习笔记一、Redis数据结构和底层原理

1、简单动态字符串SDS

应用：
- 字符串对象底层实现
- 缓冲区（AOF，客户端状态中的输入缓冲区）

数据结构：

struct sdshdr {
    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;
    // 记录 buf 数组中未使用字节的数量
    int free;
    // 字节数组，用于保存字符串
    char buf[];
};

在这里插入图片描述

特性：
- 取字符串长度O(1)；
- 二进制安全：有len记录长度，相比C语言，字符串中间遇到’\0’不会中断；
- 杜绝缓存溢出-检查容量、自己扩容；
- 减少修改字符串长度时所需内存重分配次数-空间预分配（SDS增长,N次增长最多N次扩容）、惰性空间释放（SDS减少，不释放内存，用free记录）；
- 兼容部分C字符串函数。
- 唯一一种可以被其他四种对象嵌套的对象。

2、链表-list

应用：
- 列表键的底层实现：列表元素数量多、元素是长字符串；
- 发布、订阅、慢查询、监视器；

数据结构：

多个listNode组成一个list，listNode通过前后指针形成双端链表；

adlist.h/listNode

typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

adlist.h/list

typedef struct list {
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
} list;

在这里插入图片描述

特性
- head的prev和tail的next指针都指向null，链表无环。
- 可以保存不同类型数据。

3、字典-dict

应用：
- 保存数据库，数据库增删改查都是建立在字典上完成的；
- 哈希键底层实现（哈希键->字典dict->哈希表dictht->table指向->哈希表节点数组dictEntry[N]->哈希表节点dictEntry（K：V））；
数据结构：

在这里插入图片描述

特性
- 哈希算法：通过dict中规定的哈希函数和ht[0]的sizemask，获得新键值对在哈希节点数组中的index。
- 解决键冲突：算出来index相同，用单链表连接：
- rehash 渐进式：ht[0]空间不足，将ht[0]中的所有键值对放到ht[1]中，渐进完成效率高，迁移过程新增数据都放到ht[1]中，完成后ht[1]变为ht[0]

4、跳跃表-zskiplist

应用：
- 有序集合键底层实现：集合元素较多，成员较长；
- 集群节点用作内部数据结构。
数据结构：
zskiplistNode跳跃表节点；
zskiplist跳跃表：保存跳跃表节点信息

在这里插入图片描述

特性
- 跳跃表数据遍历方式：效率高

在这里插入图片描述

+ 节点按照分值大小和成员对象大小排序

5、整数集合-intset

应用：
- 集合键底层实现：集合中只含整数，元素数量不多；
- 集合键->整数集合->数组；
数据结构

在这里插入图片描述

特性
- 支持升级，使用最长数据，提升集合灵活性，节省内存；
- 不支持降级。

6、压缩列表-ziplist

应用：
- 列表键、哈希键和有序集合键的底层实现：少量元素，元素长度短；
数据结构：

在这里插入图片描述

7、对象

7.1 对象和键值对的关系

在redis数据库中每创建一个键值对，需要创建两个对象：
- 键值对的键：字符串对象
- 键值对的值：可能是五种对象
当称一个数据库键为“列表键”时，指的是键值对的值为列表对象；

>>SADD fruits apple banana cherry
>>TYPE fruits
set

7.2 数据结构

Redis中每个对象都是由一个redisObject结构表示的。

typedef struct redisObject{
	//类型
	unsigned type:4;
	//编码
	unsigned encoding:4;
	//指向底层实现数据结构的指针
	void *ptr;
	//引用计数
	int refcount;
	//对象最后一次被命令程序访问的时间
	unsigned lru:22;
}robj;

type
- 五大类型
ptr指针
- 指向对象底层实现的数据结构；
encoding
- 记录对象使用的数据结构–使用编码代指；
- 优点：提高Redis的灵活性和效率；可以根据数据的变化，改变encoding应用的数据结构。

OBJECT ENCODING 对象名称   //查看数据库键的值对象的编码

7.3 五种对象

7.3.1 字符串对象

编码方式：
SDS：按照长度划分 int<embstr<raw 类型。

在这里插入图片描述

编码转换

int->row:原本储存整数值的键值对中，增加了String类型；

embstr->row：embstr在执行修改命令后自动变为row，embstr没有修改方法，需要变成row才能修改；

常用命令

在这里插入图片描述

7.3.2 列表对象

编码方式：ziplist、linkedlist

在这里插入图片描述

linkedlist地层双端链表结构中，包含的是字符串对象–StringObject：
编码转换
ziplist适用于：字符串长度短，数量少；否则使用linkedlist；
常用命令

在这里插入图片描述

7.3.3 哈希对象

编码方式：ziplist、hashtable
hashtable中嵌套字符串对象StringObject
- ziplist：放表尾，键在前

在这里插入图片描述

hashtable：哈希对象的每个键值对都由一个字典键值对保存：
字典的键：字符串对象
字典的值：字符串对象
编码转换

由哈希对象保存键值对的字符串长度(小于64字节)、键值对数量来转换(小于512个)，ziplist小，hashtable大

常见指令

7.3.4 集合对象

编码方式：intset，hashtable
- intset：整数集合作为底层实现

在这里插入图片描述

hashtable：字典作为地层实现，每个键都是StringObject，value都是null

在这里插入图片描述

编码转换：所有元素都是整数值；保存元素数量不超过512个；否则用hashtable
常用指令：

在这里插入图片描述

7.3.5 有序集合对象-zset

编码方式：ziplist、zskiplist
- ziplist

在这里插入图片描述

skiplist
一个zset是由一个dict和一个zskiplist构成，实际上dict和zskiplist都是用指针指向同一份数据
同时使用dict和zskiplist数据结构的优点：dict查询成员分值：O(1)，zskiplist获得有序集合；
```
typedef struct zset{
	zskiplist *zsl;
	dict *dict;
}zset;
```

在这里插入图片描述

编码转换：有序集合保存的元素小于128个；元素长度小于64字节。
常用命令

7.4 其他

操作键的命令：适用于任何类型的键；适用于特定类型的键。

类型检查
- 执行特定命令前，检查键值对的值是否为命令所需类型，是执行，否报错。
命令多态
- 根据对象的编码方式，使用正确的命令实现：eg，zset有序集合对象有zlist和skiplist两种编码方式，可以认为zset对应的命令是多态的。

内存回收

引用计数：

typedef struct redisObject{
	...
	int refcount;  //引用计数
}

当refcount=0的时候，内存被释放；

对象共享
- 由引用计数器记录对象共享次数
- Redis初始化时，自动创建一万个字符串对象（含0-9999）的所有整数值，用到时直接共享，不用新建；
- 新建对象的引用计数为 2
```
redis>SET A 100
redis>OBJECT REFCOUNT a   //查看键值对的值对象引用计数
2    //第一个：共享值对象的键A； 第二个：持有值对象的服务器程序
```

在这里插入图片描述

不共享含字符串的对象（嵌套），时间复杂度太高（共享前需要检查给定共享对象和键想创建的目标对象是否完全相同）
对象的空转时长
redisObject中的lru：
```
OBJECT IDLETIME   //得到curTime-lru，当前对象空转时间
```
启用maxmemory，超过limit，回收内存。

总结

1、五种对象：

对象编码方式

字符串对象_____________SDS：int < embstr < row

列表对象_____________ziplist < linkedlist（list的节点嵌套StringObject）

哈希对象_____________ziplist < hashtable（dict节点中嵌套StringObject）

集合对象_____________intset < hashtable

有序集合对象_____________ziplist < zskiplist

2、六种底层数据结构

数据结构_____________构成对象

SDS 动态字符串_____________字符串对象

list 链表_____________列表对象

dict 字典_____________哈希对象、集合对象

zskiplist 跳跃表_____________有序集合对象

intset 整数集合_____________集合对象

ziplist 压缩列表_____________列表对象、哈希对象、有序集合对象

原文链接：https://blog.csdn.net/weixin_38115084/article/details/117430244

《Redis设计与实现》学习笔记 一、Redis数据结构和底层原理

1、简单动态字符串SDS

2、链表-list

3、字典-dict

4、跳跃表-zskiplist

5、整数集合-intset

6、压缩列表-ziplist

7、对象

7.1 对象和键值对的关系

7.2 数据结构

7.3 五种对象

7.3.1 字符串对象

7.3.2 列表对象

7.3.3 哈希对象

7.3.4 集合对象

7.3.5 有序集合对象-zset

7.4 其他

总结

《Redis设计与实现》学习笔记一、Redis数据结构和底层原理