redis的数据结构，内存处理，缓存问题

redisObject

redis任意数据的key和value都会被封装为一个RedisObject，也叫redis对象：

这就redis的头信息，占有16个字节

redis中有两个热门数据结构

1.SkipList，跳表，首先是链表，和普通链表有以下差异：

元素按照升序排列存储
节点可能包含多个指针，指针跨度不同

那么跳表的特点有以下：

跳跃表是一个有序的双向链表
每个节点都可以包含多层指针，层数是1到32之间的随机数
不同层指针到下一个节点的跨度不同，层级越高，跨度越大
增删改查效率与红黑树基本一致，实现却更加简单。但空间复杂度更高

2.Sorted数据结构的特点：

每组数据都包含score和memeber
memeber唯一
可根据score排序

所以SortedSet的底层数据结构是怎么样的？

首先SortedSet需要能存储score和memeber值，而且要快捷的根据member查询score，因此底层有一个哈希表，以member为键，以score为value
其次StoredSet还需要能根据score排序，因此底层还维护了一个跳表
当需要根据member查询score时，就去哈希表中查询
当需要根据score排序查询时，则基于跳表查询

内存处理

1. 过期key处理

redis的本身是键值型数据库，其所有数据都存在一个redisDB的结构体中，其中包含两个哈希表：

dict：保存Redis中所有的键值对
expires：保存Redis中所有的设置了过期时间的KEY及其到期时间（写入时间+TTL）

        Redis是何时删除过期KEY的呢？

        Redis并不会在KEY过期时立刻删除KEY，因为要实现这样的效果就必须给每一个过期的KEY设置时钟，并监控这些KEY的过期状态。无论对CPU还是内存都会带来极大的负担。

Redis的过期KEY删除策略有两种：

惰性删除

周期删除

        惰性删除，顾明思议就是过期后不会立刻删除。那在什么时候删除呢？

Redis会在每次访问KEY的时候判断当前KEY有没有设置过期时间，如果有，过期时间是否已经到期。

        周期删除：顾明思议是通过一个定时任务，周期性的抽样部分过期的key，然后执行删除。执行周期有两种：

SLOW模式：Redis会设置一个定时任务serverCron()，按照server.hz的频率来执行过期key清理

FAST模式：Redis的每个事件循环前执行过期key清理（事件循环就是NIO事件处理的循环）。

2. 内存淘汰策略

Redis支持8种不同的内存淘汰策略：

noeviction：不淘汰任何key，但是内存满时不允许写入新数据，默认就是这种策略。
volatile-ttl：对设置了TTL的key，比较key的剩余TTL值，TTL越小越先被淘汰
allkeys-random：对全体key ，随机进行淘汰。也就是直接从db->dict中随机挑选
volatile-random：对设置了TTL的key ，随机进行淘汰。也就是从db->expires中随机挑选。
allkeys-lru：对全体key，基于LRU算法进行淘汰
volatile-lru：对设置了TTL的key，基于LRU算法进行淘汰
allkeys-lfu：对全体key，基于LFU算法进行淘汰
volatile-lfu：对设置了TTL的key，基于LFI算法进行淘汰

比较容易混淆的有两个算法：

LRU（Least Recently Used），最近最久未使用。用当前时间减去最后一次访问时间，这个值越大则淘汰优先级越高。
LFU（Least Frequently Used），最少频率使用。会统计每个key的访问频率，值越小淘汰优先级越高。

缓存问题

1.缓存一致性

我们采用Cache aside方案，这个方案就是由业务开发者在更新数据库的同时，更新缓存。

如果是查询操作，假如先查到redis，redis中没有，那就查数据库，然后把这个数据缓存在redis，并设置TTL。如果是增加数据，那么之间不用管redis，等下一次查到这个数据的时候，再缓存在reids中，如果是删除和修改，那就直接把redis中的这个数据删除掉，等下一次查询的时候再做缓存。但是这个是由线程安全问题的，假如有一个线程在做修改操作，那么它先会把redis中的数据删除，然后这时有另一个线程执行查询操作，查询操作看redis中没有这个数据，就去把数据库的旧数据又缓存在redis中，这时，上一个线程又把数据库的数据修改了，那么这时redis和数据库就出现了数据不一致问题。然后这个问题的出现是由于先删除redis，再操作数据库。那么我们先操作数据库，再操作redis，就不会出现数据不一致了。

所以缓存一致性策略的最佳实践方案：

1. 低一致性要求：使用redis的key过期清理方案

2. 高一致性需求：主动更新，并以超时剔除作为兜底方案

读操作：

缓存命中直接返回

缓存未命中则查询数据库，并写入缓存，设定超时时间

写操作：

先写到数据库，然后再删除缓存

要确保数据库与缓存操作的原子性（同时成功或失败）

2. 缓存穿透

由于数据库中不存在该数据，那么缓存中肯定也不存在。因此不管请求该数据多少次，缓存永远不可能建立，请求永远会直达数据库。此为缓存穿透。

那么解决这个问题有两种方案：缓存空值和布隆过滤器

缓存空值实现起来简单，但是有额外的内存消耗

布隆过滤首先需要一个很长的bit数组，默认数组中每一位都是0

然后还需要K个hash函数，将元素基于这些hash函数做运算的结果映射到bit数组的不同位置，并将这些位置置为1，例如现在k=3：

hello经过运算得到3个角标：1、5、12
world经过运算得到3个角标：8、17、21
java经过运算得到3个角标：17、25、28

此时，我们要判断元素是否存在，只需要再次基于K个hash函数做运算，得到K个角标，判断每个角标的位置是不是1：

只要全是1，就证明元素存在
任意位置为0，就证明元素一定不存在

假如某个元素本身并不存在，也没添加到布隆过滤器过。但是由于存在hash碰撞的可能性，这就会出现这个元素计算出的角标已经被其它元素置为1的情况。那么这个元素也会被误判为已经存在。

因此，布隆过滤器的判断存在误差：

当布隆过滤器认为元素不存在时，它肯定不存在
当布隆过滤器认为元素存在时，它可能存在，也可能不存在

当bit数组越大、Hash函数K越复杂，K越大时，这个误判的概率也就越低。由于采用bit数组来标示数据，即便4,294,967,296个bit位，也只占512mb的空间

3. 缓存雪崩

缓存雪崩是指在同一时段大量的缓存key同时失效或者Redis服务宕机，导致大量请求到达数据库，带来巨大压力。

常见的解决方案有：

给不同的Key的TTL添加随机值，这样KEY的过期时间不同，不会大量KEY同时过期

利用Redis集群提高服务的可用性，避免缓存服务宕机

给缓存业务添加降级限流策略，降级就是直接拒绝一部分请求，当然必要情况也可以熔断服务

给业务添加多级缓存，比如先查询本地缓存，本地缓存未命中再查询Redis，Redis未命中再查询数据库。即便Redis宕机，也还有本地缓存可以抗压力