redis缓存数据结构

‘壹’ redis常用数据结构介绍和业务应用场景分析

redis内置了很多常用数据结构，了解这些数据结构的功能和应用场景能够让我们在需求开发时灵活运用来解决实际问题。

String是redis中最基础的数据结构，你可以把它用作缓存最基础的kv（key-value）类型的缓存(value最大为512MB)，只需要把需要缓存的对象进行string的编解码即可。另外String也可以保存数值类型的数据，就可以来实现计数功能（redi提供了incr等原子操作）

常见应用场景

List列表更多的时候是把它当成队列使用(最大2^32 - 1个元素)，使用入队出队功能，如果来使用它作为各种列表的话，很多时候不具备防重功能在使用的时候不是很方便。

常见应用场景

Set是一种无序不重复的集合，添加删除检查是否存在都是O(1)的时间复杂度。

常见应用场景

hash是一个map结构，可以像存储对象的多个字段一样存储一个key的多类数据。

常见应用场景

redis中的pub/sub可以实现广播功能，类似rocketmq中的broadcast

常见应用场景

除了上述最基本的数据结构外，redis还提供了一些其他的数据结构，有的是需要安装相关redis stack来使用的。

bitmap本质上还是使用的string字符串，不过可以通过bit来进行操作，把这个key的value值想象成bit组成的数组。

常见应用场景

bloomfilter（也叫布隆过滤器）可以理解成一种特殊的set集合，它可以用来判断一个值是否在这个集合中，不过不同于普通的set，它的判断存在一定误判的可能（假阳性），如果bloomfilter判断一个值不在这个集合中，那么一定不在，但是如果判断在，那么有可能不在。

常见应用场景

hyperloglog是一种概率性的去重计数数据结构，可以实现一定精度的去重计数

常见应用场景

geohash可以实现距离计算、距离查询等地理位置相关的功能

常见应用场景

‘贰’ redis 常见数据结构以及使用场景分析

Redis 提供了 5种数据结构，每一种数据结构有各种的使用场景。
1、String 字符串
字符串类型是 Redis 最基础的数据结构，首先键都是字符串类型，而且 其他几种数据结构都是在字符串类型基础上构建的，我们常使用的 set key value 命令就是字符串。常用在缓存、计数、共享Session、限速等。
2、Hash 哈希
在Redis中，哈希类型是指键值本身又是一个键值对 结构，形如value={{field1，value1}，...{fieldN，valueN}}，添加命令：hset key field value。哈希可以用来存放用户信息，比如实现购物车
3、List 列表
列表（list）类型是用来存储多个有序的字符串。可以做简单的消息队列的功能。另外，可以利用 lrange 命令，做基于 Redis的分页功能，性能极佳，用户体验好。
4、Set 集合
集合（set）类型也是用来保存多个的字符串元素，但和列表类型不一 样的是，集合中不允许有重复元素，并且集合中的元素是无序的，不能通过 索引下标获取元素。利用 Set 的交集、并集、差集等操作，可以计算共同喜好，全部的喜好，自己独有的喜好等功能。
5、Sorted Set 有序集合
Sorted Set 多了一个权重参数 Score，集合中的元素能够按 Score 进行排列。可以做排行榜应用，取 TOP N 操作。

‘叁’ Redis的五种数据结构及其底层实现原理

redis的字符串类型是由一种叫做简单动态字符串(SDS)的数据类型来实现

SDC和C语言字符串的区别：
1：SDS保存了字符串的长度，而C语言不保存，只能遍历找到第一个的结束符才能确定字符串的长度
2：修改SDS，会检查空间是否足够，不足会先扩展空间，防止缓冲区溢出，C字符串不会检查
3：SDS的预分配空间机制，可以减少为字符串重新分配空间的次数
备注：重新分配空间方式，小于1M的数据 翻倍+1，例如：13K+13K+1，如果大于1M，每次多分配1M，例如：10M+1M+1,如果字符串变短，并不会立即缩短，而是采用惰性空间释放，有专门的API可以释放多余空间

hash结构里其实是一个字典，有许多的键值对
redis的哈希表是一个dictht结构体：

哈希表节点的结构体如下：

hash算法：
当要将一个新的键值对添加到字典里面时， 程序需要先根据键值对的键计算出哈希值和索引值， 然后再根据索引值， 将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

hash冲突解决方式：链表法，后入的放到最前面
rehash：
键值数据量变动时，时为了让哈希表的负载因子（load factor）维持在一个合理的范围之内， 当哈希表保存的键值对数量太多或者太少时， 程序需要对哈希表的大小进行相应的扩展或者收缩。
如果是扩充，新数组的空间大小为 大于2*used的2的n次方，比如：used=5,则去大于10的第一个2的n次方，为16
如果是缩小，新数组的空间大小为第一个不大于used的2的n次方，比如：used=5,则新大小为4

redis的list列表是使用双向链表来实现的
···
typedef struct listNode {
struct listNode * pre; //前置节点
struct listNode * next; //后置节点
void * value; //节点的值
}

typedef struct list {
listNode *head; //表头节点
listNode tail; //表尾节点
unsigned long len; //链表所包含的节点数量
void ( p) (void ptr); //节点值赋值函数 这里有问题
void ( free) (void ptr); //节点值释放函数
int ( match) (void *ptr, void *key) //节点值对比函数
}
···

1：有序集合的底层实现之一是跳表， 除此之外跳表它在 Redis 中没有其他应用。
2：整数集合（intset）是集合键的底层实现之一： 当一个集合只包含整数值元素， 并且这个集合的元素数量不多时， Redis 就会使用整数集合作为集合键的底层实现。
3：数据少是，使用ziplist(压缩列表)，占用连续内存，每项元素都是(数据+score)的方式连续存储，按照score从小到大排序。ziplist为了节省内存，每个元素占用的空间可以不同，对于大数据(long long),就多用一些字节存储，而对于小的数据(short)，就少用一些字节来存储。因此查找的时候需要按顺序遍历。ziplist省内存但是查找效率低。

无序集合可以用整数集合(intset)或者字典实现

Redis的5.0版本中，放出一个新的数据结构Stream。其实也是一个队列，没一个不同的key对应的是不同的队列，没个队列的元素，也就是消息，都有一个msgid，并且需要保证msgid是严格递增的。在Stream当中，消息是默认持久化的，即便是Redis重启，也能够读取到信息。
Stream的多播，与其它队列系统相似，对不同的消费者，也有消费者Group这样的概念，不同的消费组，可以消费通一个消息，对于不同的消费组，都维护一个Idx下标，表示这一个消费群组费到了哪里，每次进行消费，都会更新一下这个下标，往后面一位进行偏移。

跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而大道快速访问节点的目的，具有以下性质：
1：有很多层结构组成
2：每一层都是一个有序的链表，排列顺序为由高到低，都至少包含两个链表节点，分别是前面的head节点和后面的nil节点
3：最底层的链表包含了所有的元素
4：如果一个元素出现在某一层的链表中，那么在该层之下的链表也全部都会出现
5：链表中的每个节点都包含两个指针，一个指向同一层的下一个链表节点，另一个指向下一层的通一个链表节点

多个跳跃表节点构成一个跳跃表

1：搜索，从最高层的链表节点开始，如果比当前节点要大和比当前层的下一个节点要小，那么则往下找，也及时和当前层的下一层的节点下一个节点
2：插入，首先确定插入的层数，有一种方法是抛一个硬币，如果是正面就累加，直到遇到反面为止，最后记录正面的次数作为插入的层数，当确定插入的层数K后，则需要将新元素插入从底层到K层
3：删除，在各个层中找到包含指定值得节点，然后将节点从链表中删除即可，如果删除以后只剩下头尾两个节点，则删除这一层。

整数集合是Redis用于保存整数值集合的抽象数据类型，它可以保存int16_t、int32_t、int64_t的整数值，并且保证集合中不会出现重复元素。

整数集合的每个元素都是contents数组的一个数据项，他们按照从小到大的顺序排列，并且不包含任何重复项。
length属性记录了contents数组的大小。
需要注意的是虽然contents数组声明为int8_t类型，但是实际上contents数组并不保存任何int8_t类型的值，其真正类型由encoding来决定。

压缩列表(ziplist)是Redis为了节省内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含任意多个节点(entry)，每个节点可以保存一个字节数组或一个整数值。
压缩列表的原理：压缩列表并不是对数据利用某种算法进行压缩的，而是将数据按照一定规则编码在一块连续的内存区域，目的是节省内存。

压缩列表的每个节点构成如下：

‘肆’ 一、Redis基础与高级数据结构

1.基本结构：ziplist、数组+链表（个数大于512或长度超过64）
2.扩容方式：为追求性能采用渐进式rehash策略，同时保留新旧2个hash结构
3.扩容原理：哈希扩容的时候会有卡顿，所有同时保留现有哈希和扩容缩容后的哈希，在原哈希没有找到再另一个哈希再进行查找，在定时任务以及后续的hash操作指令中渐渐的将旧数组的元素迁移到新数组。

1.数据结构：intset、哈希的特殊结构，所有的value都是NULL（个数大于512）
intset结构，动态调整类型为uint16~uint64的数组

1.数据结构：ziplist、哈希（存储key-value）+跳跃列表（提供排序）（个数大于512或长度超过64）
2.quicklist数据结构：

1.基本结构：位数组
2.使用场景：用户的一年签到记录
3.基本操作：

1.基本结构：稀疏矩阵、HyperLogLog（2的14次方个桶用于调和平均，所以占12KB）
2.使用场景：提供不精确的去重计数方案，标准误差为0.81%，可以统计每天访问系统的UV数据
3.基本操作：pfadd、pfcount、pfmerge（多个pf计数累加）

1.基本结构：位数组、无偏hash函数

2.使用场景：推荐算法中的是否已经看过该文档、邮件过滤、爬虫记录已经爬过的URL，会有一定误判，但是不存在一定不存在，存在不一定一定存在。
3.基本使用：bf.add、bf.exists 、bf.mexists
4.参数调优：

1.算法原理：GeoHash将二维的经纬度数据映射到一维的整数（反向从证书还原有损），所有的坐标都存储在zset中，score是坐标52位整数，所以可以查看附件的元素（实际会复杂一些）

2.基本使用：geoadd、geodist（距离）、geopos（经纬度）、geohash（位置编码）、georadiusbymemeber(位置附近)、georadius(经纬附近)
3.注意事项：

1.产生背景：为了取代ziplist，不会有级联更新的问题，每个节点单独存在
2.数据结构：

1.数据结构：与zset不同的是zset基于score进行排序，rax基于key进行排序（字典序），rax是基数树radix tree的特殊结构，与基数树不同的是节点可以进行压缩存多个字符

2.使用场景：使用在Stream机构中用于存储消息队列

‘伍’ redis源码解读：单线程的redis是如何实现高速缓存的

redis可能是最近几年最火的缓存数据库方案了，在各个高并发领域都有应用。

这篇文章，我们将从源代码的角度来分析一下，为何如此一个高性能，高应用的缓存，会是单线程的方案，当然一个方案的高性能，高并发是多方面的综合因素，其它的因素我们将在后续解读。后续分析主要以LINUX操作系统为基础，这也是redis应用最广的平台。

单线程最大的受限是什么？就是CPU，现在服务器一般已经是多CPU，而单线程只能使用到其中的一个核。

redis作为一个网络内存缓存数据库，在实现高性能时，主要有4个点。

1.网络高并发，高流量的数据处理。

一个异步，高效，且对CPU要求不高的网络模型，这个模型主要是由OS来提供的，目前在LINUX最主流使用的是EPOLL，这个网上介绍很多，主要是基于事件驱动的一个异步模型。

2.程序内部的合理构架，调用逻辑，内存管理。

redis在采用纯C实现时，整体调用逻辑很短，但在内存方面，适当的合并了一些对象和对齐，比如sds等，在底层使用了内存池，在不同情况下使用的不太一样。

但整体处理上没有NGINX的内池设计巧妙，当然二者不太一样，NGINX是基于请求释放的逻辑来设计的，因此针对请求，可以一次申请大块，分量使用，再最后统一释放。

3.数据复制的代价，不管是读取数据或是写入数据，一般都是需要有数据复制的过程。

数据复制其实就是一次内存，真正的代价是在于存在大VALUE，当value值长度超过16KB时，性能会开始下降。因为单线程的原因，如果存在一个超大VALUE，比如20MB，则会因为这个请求卡住整个线程，导致后续的请求进不来，虽然后面的请求是能快速处理的小请求。

4.redis中数据结构中算法的代价，有些结构在大数据量时，代价是很高的。

很多时间，大家忽略了算法的运算代码，因为像memcached等这类是完全的KV缓存，不存在什么算法，除了一个KEY的查找定位HASH算法。

而redis不一样，提供了不少高阶的数据对象，这些对象具有上层的一些算法能力，而这些能力是需要比如GEO模块。

‘陆’ redis做mysql的缓存

redis缓存其实就是把经常访问的数据放到redis里面，用户查询的时候先去redis查询，没有查到就执行sql语句查询，同时把数据同步到redis里面。redis只做读操作，在内存中查询速度快。

使用redis做缓存必须解决两个问题，首先就是确定用何种数据结构存储来自mysql的数据；确定数据结构之后就是需要确定用什么标识来作为数据的key。
mysql是按照表存储数据的，这些表是由若干行组成。每一次执行select查询，mysql都会返回一个结果集，这个结果是由若干行组成的。redis有五种数据结构：列表list，哈希hash，字符串string，集合set，sorted set(有序集合)，对比几种数据结构，string和hash是比较适合存储行的数据结构，可以把数据转成json字符串存入redis。

全量遍历键： keys pattern keys *
有人说 KEYS 相当于关系性数据的库的 select * ，在生产环境几乎是要禁用的

不管上面说的对不对， keys 肯定是有风险的。那我们就换一种方案，在存数据的时候。把数据的键存一下，也存到redis里面选hash类型，那么取的时候就可以直接通过这个hash获取所有的值，自我感觉非常好用！

‘柒’ Redis数据结构和编码

String/Hash/Set/Zset/List

redis会将常见的值放入一个共享对象中，避免了程序重新分配的麻烦，类似于jvm中的常量池。
预分配的对象如下：

redis内的refcount，如果为0，则表示可以回收。

Redis3.2之前

Redis3.2之后

整体存储格式：

Redis在存储集合时，如果集合内只包含整数且数目较少时，会采用IntSet来存储。

在int16类型的集合内插入一个int32的数据：

当最大元素删除后，是否需要降级？
不会，为了减少开销

数据结构

ps： redis对于浮点数类型也是作为字符串保存的，在需要的时候再转换为浮点数类型

从目前的版本（6.0）来看，List仅支持quickList（之前的版本有linked和ziplist这2种编码）。

当同时满足以下2个条件时，使用ziplist：

当同时满足以下2个条件时，使用intset

tips：对于skipList的编码格式，其实是同时采用了dict和skiplist的数据结构来存储
说明：有序集合本身使用dict或skiplist其中一种都可以实现，如果单独使用dict来实现，那么查找可以达到O(1)的复杂度，但是每次范围查询排序需要进行额外操作；如果单独使用skiplist，虽然可以使用范围操作，但是查找复杂度却是O(logn)，所以redis采用了2种数据结构混合。但虽然同时使用了2种数据结构，但数据其实只有1份，通过指针指向到对应地址。

当同时满足以下2个条件，使用ziplist编码：

参考文章： https://www.pdai.tech/md/db/nosql-redis/db-redis-x-redis-ds.html

‘捌’ redis缓存原理

1、Redis是一种内存高速cache，如果使用redis缓存，那经常被访问的内容会被缓存在内存中，需要使用的时候直接从内存调取，不知道比硬盘调取快了多少倍，并且支持复杂的数据结构，应用于许多高并发的场景中。
2、Redis支持主从同步。数据可以从主服务器向任意数量的从服务器上同步，从服务器可以是关联其他从服务器的主服务器。这使得Redis可执行单层树复制。存盘可以有意无意的对数据进行写操作。由于完全实现了发布/订阅机制，使得从数据库在任何地方同步树时，可订阅一个频道并接收主服务器完整的消息发布记录。同步对读取操作的可扩展性和数据冗余很有帮助。zset是set的一个升级版本，他在set的基础上增加了一个顺序属性，这一属性在添加修改元素的时候可以指定，每次指定后，zset会自动重新按新的值调整顺序。可以理解了有两列的mysql表，一列存value，一列存顺序。操作中key理解为zset的名字。
更多关于redis缓存原理，进入：https://www.abcgonglue.com/ask/66eab61616100681.html?zd查看更多内容

‘玖’ 基于redis做缓存分页

在实际业务中我们会将一些热数据缓存到redis里面，这时候数据量比较大的话，我们就要对这些热数据进行分页，分页的方式有2种：

第一：从redis拿出所有数据后，再做内存分页（不推荐），热点数据小的时候可以这样做，性能相差不是很大，但是当数据量大的时候，分页期间就会占用大量内存，或撑爆；

第二：基于redis的数据结构做缓存分页，这里又分2种

①：基于redis的list数据结构，直接通过list的数据结构，用range方法可以进行分页，在数据量大的时候，性能也很可观，但是当存在接口高并发访问时，这个list可能会无限延长，且里面的数据会存在很多重复，这就会影响到正常的业务（不是很推荐）；

②：基于redis的ZSet数据结构，通过Zset这个有序集合我们也可以做分页，同样也是用range方法，但是这里比较麻烦的是在初始化数据的时候Zset必须存放TypedTuple类型的数据，这个类型是一个value和score的键值对，具体可以查网络，这个score的生成比较麻烦我这边测试时用的是当前数据在这个list的位置，然后Zset是根据这个score值来排序的，默认是从小到大；用这个的好处是，即使在高并发情况下Zset中也不会存在重复数据从而影响正常的业务；而且分页效率也和list结构差不多；

③：用hash和Zset来一起实现；这个是问了一个朋友和得知的，Zset中存储有序的id字段，通过分页后拿到id，然后再用id去hash中取，感觉应该效率相差不大的，只是中间多了层从hash结构取，还需要维护又一个hash；（为何这样做我也不清楚）；

贴一张我测试list和ZSet的结果图

‘拾’ redis面试之数据结构

redis是面试中最常问的中间件，关于数据结构主要集中在列举和用法。下面我们就数据结构和主要的使用方式做一个描述。

大家都知道redis的几种数据结构，包括string （字符串),hash（哈希），list（列表），set（集合），zset（有序集合）。下面我们来列举一下关于这几种结构的常用命令和一些使用场景。

string是redis的最基本的数据类型。

string类型是二进制安全的，也就是说string里可以包含任何的数据类型。

string类型的值最大能存储512MB

1、 普通的单值缓存

2、对象数据缓存(json格式)

3、分布式锁的应用

4、计数器的使用，使用INCR和DECR

redis hash 是一个string类型的field(字段)和value(值)的映射表，很适合存储对象。

hash最适合的就是做对象缓存

list是redis的字符串行表，可以选择将值插入到头部或尾部。

1、 可以利用list的头部尾部增删属性实现栈和队列

2、 可以用来实现时间轴模型，根据时间依次插入数据，使用LPUSH插入和LRANGE获取最近范围的数据

set是redis的无序集合，是通过哈希表实现的，因此任何操作(添加、删除和测试成员的存在性等)的时间复杂度是O(1)。(无论集合中包含多少元素，时间都是常量)

1、 可以根据set集合的不可重复的特性，统计一些像网站访问IP啊，访问用户啊这些信息，无论访问多少次，SADD加入的都只有一条。

2、 也可以使用SRANDMEMBER和SPOP获取数据的随机性 ，做一些抽奖的小程序等随机功能

3、 作为集合，可以利用交并运算等计算一些复杂的逻辑关系，比如说人物关系之间的网络关系。

ZSet和set类似，都是字符串的非重复集合。不同之处在于，ZSet的每个成员都与分数相关，分数是用来进行排序的。然后可以使用分数来取一个范围内的数

应用场景：

ZSet是有序的集合，可以使用它来做一个排行榜。