思考
- redis有哪些数据类型，底层数据结构又有哪些?
- 哪些情况会导致redis变慢？
- 为什么有些数据结构查找速度慢，却还使用
- string的弊端，如何优化
1.redis数据类型和底层数据结构
redis基础数据类型有五种:
- 字符串string ： 常用于缓存、限流、计数器、分布式锁、分布式session、签到等
- 列表List：有序，常用于存储时间轴上的事件，如生成历史报告
- 哈希Hash：常用于存储对象，如用户相关信息和商品信息
- 集合Set：常用于存储无序的多个元素，比如说说、朋友圈的赞、好友、文章标签、好友分组
- 有序集合Sorted Set：常用于排行榜，比如热搜、热销商品
底层数据结构：
- 简单动态字符串
- 压缩列表
- 双向链表
- 哈希表
- 跳表
- 整数数组
image.png
我们看到除了string类型底层实现只有一种，其他都有两种底层实现结构，我们把这四种类型称为集合类型（一个键对应一个集合的数据）
1.1键和值在redis中如何保存
image.png
redis使用哈希表保存所有键值对(一个数组，数组中的每个元素都是哈希桶)，哈希桶中的元素保存的不是值本身，而是指向具体值的指针(即不管是string还是集合类型，哈希桶里保存的都是值指针)
image.png
当然，既然是哈希表，就不可避免哈希冲突问题，对于哈希冲突，常见的使用办法就是拉出一个链表保存哈希值冲突的值，此时对于元素的查找速度不再是O(1)，而是链表的逐个查找O(n)。
image.png
底层代码如下，一个键值对对应至少一个dict
#dict字典的数据结构
typedef struct dict{
dictType *type; //直线dictType结构，dictType结构中包含自定义的函数，这些函数使得key和value能够存储任何类型的数据
void *privdata; //私有数据，保存着dictType结构中函数的 参数
dictht ht[2]; //两张哈希表
long rehashidx; //rehash的标记，rehashidx=-1表示没有进行rehash，rehash时每迁移一个桶就对rehashidx加一
int itreators; //正在迭代的迭代器数量
}
#dict结构中ht[0]、ht[1]哈希表的数据结构
typedef struct dictht{
dictEntry[] table; //存放一个数组的地址，数组中存放哈希节点dictEntry的地址
unsingned long size; //哈希表table的大小，出始大小为4
unsingned long sizemask; //用于将hash值映射到table位置的索引，大小为（size-1）
unsingned long used; //记录哈希表已有节点（键值对）的数量
}
#哈希表节点结构定义
typedef struct dictEntity{
void *key;//键
//值
union{
void *val;//自定义类型
uint64_t u64;//无符号整形
int64_t s64;//符合整形
double d;//浮点型
} v;
struct dictEntity *next;//发生哈希冲突时使用。指向下一个哈希表节点，形成链表
}
随着数据量的增加，哈希冲突也越多，链表也被拉的很长，此时redis查找效率就会变低
1.2 rehash机制
为了防止上面的情况让redis变慢，redis会执行rehash操作，即增加现有的哈希桶，让增加的元素在更多哈希桶之间分散保存，减少单个桶元素数量(链表长度)
源码引入装载因子来判断是否需要扩容(rehash)
redis默认使用两个哈希表，一开始数据被插入在哈希表1中(此时哈希表2没有分配内存)，随数据量增加redis开始执行rehash操作:
1 . 给表2分配更大空间
- 将表1数据重新映射并拷贝到哈希表2
- 释放哈希表1
其中第二步中，为防止大量数据拷贝而阻塞redis线程，让redis无法提供服务，redis采用渐进式rehash：数据拷贝时，服务端仍接收请求，在处理请求时，从哈希表1的第一个位置开始，到该请求需要的索引位置为止，将中间所有拷贝到哈希表2，同理处理下一个请求。说白了就是把大量拷贝分摊到多次处理请求的过程中
2.其他数据结构
2.1压缩列表
上文介绍了底层数据结构哈希表和rehash机制，接下来介绍压缩列表(其余几个在算法题目中都很常见，我都了解就不记录了)
实际上压缩列表类似一个数组，每个元素保存一个数据，但是表头有三个字段:
- zlbytes 列表长度
- zltail 列表尾的偏移量
- entry 列表中元素的个数
列表尾部有一个zlend字段表示结束
image.png
从结构上看，列表头部和尾部的查找都是O(1)的时间复杂度，其余都是O(n)（和整数数组一样），那既然在查找时间复杂度上没有优势，为啥redis还会把它当作底层数据结构？数组的特点是所有元素存储是紧挨着的，意味着分配的是一块连续的内存(避免内存碎片），当数据量小的时候就很有用，redis是内存缓存，节省空间对于redis也是很重要的
2.2简单字符串
我们知道string类型能保存数字、字符串和二进制流(但是get返回的只能是字符串)
image.png
那么string类型具体底层是如何保持数据的？
-
当保存64位有符号整数时，会保存为一个8字节的long类型整数(int编码方式)
-
当保存数据中包含字符串时，会用简单动态字符串保存(sds,simple dynamic string)
image.png
-
len 4个字节表示buf已用长度
-
alloc 4个字节表示buf的实际分配长度，一般大于len
-
buf 字节数组，保存实际数据，会自动在数组末尾加"\0"(c 语言保存字符串特点)，额外占用一个字节开销
image.png
- 注意当保存Long类型整数时，ptr直接赋值为整数数据，不再是指向整数的指针
- 当字符串小于44字节时，redisobject中的元数据、指针和SDS是一块连续的内存区域(embstr编码方式，避免内存碎片)
- 当大于44字节时，redisobject和sds不再一起内存布局，而是sds分配独立空间，再指向sds(raw编码)
image.png
假设现在redis要用string存储8位的数字，用经由int编码的redisobject保存，元数据占8字节，ptr部分(被long整形占用)占8字节，一共16字节，但是key也要保存(也是用redisobject保存)，占用16字节，key和value一共32字节
image.png
dict结构体三个指针占用24字节，是不是总共24+32 = 56字节？实际是64字节！！因为redis内存分配库jemalloc在分配内存时，会根据申请的字节数N，找一个比N大，但是最接近N的2的幂次方作为分配空间(分配多点，减少频繁分配次数)，如申请6字节(B)实际分配8字节(2的3次方)，申请24字节，分配32字节(2的5次方)，同理申请56字节，实际分配64(2的6次方)
明明有效信息只有一个16个字节(两个redisobject的ptr)，却需要64字节内存空间，那么要保存1亿个该数据，就需要6.4GB内存空间，4.8GB内存都用来保存元数据,很明显，用string保存大量数据不是一个好选择，string的元数据占据了主要开销！！！
2.3 优化方案
我们上面提到压缩列表ziplist内存是连续的，不需要额外的ptr指针连接，能节约内存开销，那能不能使用该数据结构保存
image.png
ziplist用一系列连续的entry保存数据：
- pre_len 表示前一个entry长度，当前一个entry长度小于254字节，占1字节，否则5字节
- len 自身长度 4字节
- content实际保存数据为止
- encoding 编码方式1字节
我们再来模拟一下如何用ziplist存储8字节数字,1(prev_len)+ 4(len)+1(encoding)+8(content) = 14B
根据jemalloc分配内存规则，实际分配16B（2^4），那么对比SDS实际需要的64B是不是少了很多？
问题来了，key怎么办？这时集合类型，一个键对应一个集合数据，即我们如何用集合类型保存单值的键值对
一种办法是采用Hash类型的二级编码方法，即将一个单值数据拆分成两部分，前一部分作为hash的key，后一部分作为value保存
hash底层会使用ziplist，我们使用hset命令
以数字键11001060，值222222为例，键拆成 11001 和 060
127.0.0.1:6379[1]> hset 11001 060 222222
(integer) 1
至于hset类型底层什么时候使用压缩列表或哈希取决于两个阈值：
- hash-max-ziplist-entries 表示用压缩列表保存时哈希集合的元素最大个数超过时转为哈希
- hash-max-ziplist-value表示写入单个元素大小超过该值转为哈希
同理有序集合sorted set
当元素量少于zset-max-ziplist-entries，并且每个元素小于zset-max-ziplist-value时，默认也采用ziplist结构存储
网友评论