思考

1. redis有哪些数据类型，底层数据结构又有哪些?
2. 哪些情况会导致redis变慢？
3. 为什么有些数据结构查找速度慢，却还使用
4. string的弊端，如何优化

1.redis数据类型和底层数据结构

redis基础数据类型有五种:

• 字符串string ： 常用于缓存、限流、计数器、分布式锁、分布式session、签到等
• 列表List：有序，常用于存储时间轴上的事件，如生成历史报告
• 哈希Hash：常用于存储对象，如用户相关信息和商品信息
• 集合Set：常用于存储无序的多个元素，比如说说、朋友圈的赞、好友、文章标签、好友分组
• 有序集合Sorted Set：常用于排行榜，比如热搜、热销商品

底层数据结构：

• 简单动态字符串
• 压缩列表
• 双向链表
• 哈希表
• 跳表
• 整数数组
  
  image.png
  
  我们看到除了string类型底层实现只有一种，其他都有两种底层实现结构，我们把这四种类型称为集合类型（一个键对应一个集合的数据）

1.1键和值在redis中如何保存

image.png

redis使用哈希表保存所有键值对(一个数组，数组中的每个元素都是哈希桶)，哈希桶中的元素保存的不是值本身，而是指向具体值的指针(即不管是string还是集合类型，哈希桶里保存的都是值指针)

image.png

image.png

#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分配更大空间

2. 将表1数据重新映射并拷贝到哈希表2
3. 释放哈希表1

其中第二步中，为防止大量数据拷贝而阻塞redis线程，让redis无法提供服务，redis采用渐进式rehash：数据拷贝时，服务端仍接收请求，在处理请求时，从哈希表1的第一个位置开始，到该请求需要的索引位置为止，将中间所有拷贝到哈希表2，同理处理下一个请求。说白了就是把大量拷贝分摊到多次处理请求的过程中

2.其他数据结构

2.1压缩列表

上文介绍了底层数据结构哈希表和rehash机制，接下来介绍压缩列表(其余几个在算法题目中都很常见，我都了解就不记录了)
实际上压缩列表类似一个数组，每个元素保存一个数据，但是表头有三个字段:

• zlbytes 列表长度
• zltail 列表尾的偏移量
• entry 列表中元素的个数

列表尾部有一个zlend字段表示结束

image.png

2.2简单字符串

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

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结构存储

文章参考

1.一文搞定rehash

2. string应用场景