[大数据]Redis

Redis

1 什么是缓存

缓存原指CPU上的一种高速存储器，它先于内存与CPU交换数据，速度很快。现在泛指存储在计算机上的原始数据的复制集，便于快速访问。在互联网技术中，缓存是系统快速响应的关键技术之一，采用以空间换时间的一种技术。

2 缓存的应用场景

• DB缓存，减轻DB服务器压力
• 提高系统响应
• 提高系统响应
• 做分布式锁（Redis）
  一般讲锁是多线程的锁，是在一个进程中的,多个进程（JVM）在并发时也会产生问题，也要控制时序性可以采用分布式锁。使用Redis实现 setNX
• 做乐观锁（Redis）
  同步锁和数据库中的行锁、表锁都是悲观锁，悲观锁的性能是比较低的，响应性比较差
  高性能、高响应（秒杀）采用乐观锁Redis可以实现乐观锁 watch + incr

常见缓存分类

客户端缓存

• 页面缓存
  页面自身对某些元素或全部元素进行存储，并保存成文件
  html5：Cookie、WebStorage（SessionStorage和LocalStorage）、WebSql、indexDB、ApplicationCache等
• 浏览器缓存
  当客户端向服务器请求资源时，会先抵达浏览器缓存，如果浏览器有“要请求资源”的副本，就可以直接
  从浏览器缓存中提取而不是从原始服务器中提取这个资源。
  浏览器缓存可分为强制缓存和协商缓存。
  强制缓存：直接使用浏览器的缓存数据
  条件：Cache-Control的max-age没有过期或者Expires的缓存时间没有过期

<meta http-equiv="Cache-Control" content="max-age=7200" /> 
<meta http-equiv="Expires" content="Mon, 20 Aug 2010 23:00:00 GMT" />

协商缓存：服务器资源未修改，使用浏览器的缓存（304）；反之，使用服务器资源（200）。

<meta http-equiv="cache-control" content="no-cache">

• APP缓存
  原生APP中把数据缓存在内存、文件或本地数据库（SQLite）中。比如图片文件。

网络端缓存

通过代理的方式响应客户端请求，对重复的请求返回缓存中的数据资源。

• Web代理缓存
  可以缓存原生服务器的静态资源，比如样式、图片等。
  常见的反向代理服务器比如大名鼎鼎的Nginx。
  
• 边缘缓存
  边缘缓存中典型的商业化服务就是CDN了。
  CDN的全称是Content Delivery Network，即内容分发网络。
  CDN通过部署在各地的边缘服务器，使用户就近获取所需内容，降低网络拥塞，提高用户访问响应速度和命中率。
  CDN的关键技术主要有内容存储和分发技术。现在一般的公有云服务商都提供CDN服务。
  

服务端缓存

服务器端缓存是整个缓存体系的核心。包括数据库级缓存、平台级缓存和应用级缓存。

• 数据库级缓存
  数据库是用来存储和管理数据的。
  MySQL在Server层使用查询缓存机制。将查询后的数据缓存起来。
  K-V结构，Key：select语句的hash值，Value：查询结果
  InnoDB存储引擎中的buffer-pool用于缓存InnoDB索引及数据块。
• 平台级缓存
  平台级缓存指的是带有缓存特性的应用框架。
  比如：Caffeine（性能最高）、GuavaCache 、EhCache（二级缓存，硬盘）、OSCache（页面缓存）等。
  部署在应用服务器上，也称为服务器本地缓存。
• 应用级缓存（重点）
• 具有缓存功能的中间件：Redis、Memcached、EVCache（AWS）、Tair（阿里 、美团）等。
  采用K-V形式存储。
  利用集群支持高可用、高性能、高并发、高扩展。
  分布式缓存

缓存优劣势

优势

提升系统性能
系统性能指标：响应时间、延迟时间、吞吐量、并发用户数和资源利用率等。
缓存技术可以：
缩短系统的响应时间
减少网络传输时间和应用延迟时间
提高系统的吞吐量
增加系统的并发用户数
提高了数据库资源的利用率

劣势

• 额外的硬件支出
  缓存是一种软件系统中以空间换时间的技术
  需要额外的磁盘空间和内存空间来存储数据
  搭建缓存服务器集群需要额外的服务器
  采用云服务器的缓存服务就不用额外的服务器了
  阿里云（Tair、Redis），百度云（Redis），提供缓存服务
  AWS亚马逊云服务：EVCache
• 高并发缓存失效
  在高并发场景下会出现缓存失效（缓存穿透、缓存雪崩、缓存击穿）

缓存穿透

缓存穿透是指缓存和数据库中都没有的数据，而用户不断发起请求
解决方案

1. 接口层增加校验，如用户鉴权校验，id做基础校验，id<=0的直接拦截；
2. 从缓存取不到的数据，在数据库中也没有取到，这时也可以将key-value对写为key-null，缓存有效时间可以设置短点。
3. 布隆过滤器

缓存雪崩

热点数据的key失效，导致同一个时间点，很多请求获取缓存都失败，从而访问数据库压力剧增。
解决方案

1. 设置缓存永不过期
2. 设置互斥锁，热点数据同一时间点只能一个请求访问数据库
3. 回填机制，在过期之前回填数据，从新设置键值对

缓存击穿

缓存雪崩是指缓存中数据大批量到过期时间，而查询数据量巨大，引起数据库压力过大甚至down机。
和缓存击穿不同的是： 缓存击穿指并发查同一条数据，缓存雪崩是不同数据都过期了，很多数据都查不到从而查数据库造成瞬间数据库访问量增大，甚至崩溃

1. 缓存数据的过期时间设置随机，防止同一时间大量数据过期现象发生。
2. 如果缓存数据库是分布式部署，将热点数据均匀分布在不同搞得缓存数据库中。
3. 设置热点数据永远不过期

• 缓存与数据库数据同步
  缓存与数据库无法做到数据的时时同步
  Redis无法做到主从时时数据同步
• 缓存并发竞争
  多个redis的客户端同时对一个key进行set值得时候由于执行顺序引起的并发问题

缓存读写

1. 先更新数据库，再更新缓存
   update与commit之间，更新缓存，commit失败
   则DB与缓存数据不一致
2. 先删除缓存，再更新数据库
   update与commit之间，有新的读，缓存空，读DB数据到缓存 数据是旧的数据
   commit后 DB为新数据
   则DB与缓存数据不一致
3. 先更新数据库，再删除缓存（推荐）
   update与commit之间，有新的读，缓存空，读DB数据到缓存 数据是旧的数据
   commit后 DB为新数据
   则DB与缓存数据不一致
   采用延时双删策略
   
   如图：延时双删也会出现脏数据的区域如上图中的双横线之间，此时可以使用加互斥锁的方式保证数据一致性。但会牺牲一部分性能。
   互斥锁代码实现
   

Redis底层树结构

RedisDB结构

Redis中存在“数据库”的概念，该结构由redis.h中的redisDb定义。
当redis 服务器初始化时，会预先分配 16 个数据库
所有数据库保存到结构 redisServer 的一个成员 redisServer.db 数组中
redisClient中存在一个名叫db的指针指向当前使用的数据库
RedisDB结构体源码：

typedef struct redisDb { 
        int id; //id是数据库序号，为0-15（默认Redis有16个数据库） 
        long avg_ttl; //存储的数据库对象的平均ttl（time to live），用于统计 
        dict *dict; //存储数据库所有的key-value 
        dict *expires; //存储key的过期时间 
        dict *blocking_keys;//blpop 存储阻塞key和客户端对象 
        dict *ready_keys;//阻塞后push 响应阻塞客户端 存储阻塞后push的key和客户端对象 
        dict *watched_keys;//存储watch监控的的key和客户端对象 
    } redisDb;

RedisObject结构

Value是一个对象
包含字符串对象，列表对象，哈希对象，集合对象和有序集合对象

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

4位type

type 字段表示对象的类型，占 4 位；
REDIS_STRING(字符串)、REDIS_LIST (列表)、REDIS_HASH(哈希)、REDIS_SET(集合)、REDIS_ZSET(有序集合)。
当我们执行 type 命令时，便是通过读取 RedisObject 的 type 字段获得对象的类型

4位encoding

encoding 表示对象的内部编码，占 4 位
每个对象有不同的实现编码
Redis 可以根据不同的使用场景来为对象设置不同的编码，大大提高了 Redis 的灵活性和效率。
通过 object encoding 命令，可以查看对象采用的编码方式

24位LRU

lru 记录的是对象最后一次被命令程序访问的时间，（ 4.0 版本占 24 位，2.6 版本占 22 位）。
高16位存储一个分钟数级别的时间戳，低8位存储访问计数（lfu ： 最近访问次数）
lru----> 高16位: 最后被访问的时间
lfu----->低8位：最近访问次数

refcount

refcount 记录的是该对象被引用的次数，类型为整型。
refcount 的作用，主要在于对象的引用计数和内存回收。
当对象的refcount>1时，称为共享对象
Redis 为了节省内存，当有一些对象重复出现时，新的程序不会创建新的对象，而是仍然使用原来的对
象。

ptr

ptr 指针指向具体的数据，比如：set hello world，ptr 指向包含字符串 world 的 SDS。

7种type结构

字符串对象

C语言： 字符数组 “\0”
Redis 使用了 SDS(Simple Dynamic String)。用于存储字符串和整型数据。

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

buf[] 的长度=len+free+1

SDS的优势：

1. SDS 在 C 字符串的基础上加入了 free 和 len 字段，获取字符串长度：SDS 是 O(1)，C 字符串是
   O(n)。
   buf数组的长度=free+len+1
2. SDS 由于记录了长度，在可能造成缓冲区溢出时会自动重新分配内存，杜绝了缓冲区溢出。
3. 可以存取二进制数据，以字符串长度len来作为结束标识
   C： \0 空字符串 二进制数据包括空字符串，所以没有办法存取二进制数据
   SDS ： 非二进制 \0
   二进制： 字符串长度 可以存二进制数据
   使用场景：
   SDS的主要应用在：存储字符串和整型数据、存储key、AOF缓冲区和用户输入缓冲。

有序集合（sorted-set）的跳跃表

将有序链表中的部分节点分层，每一层都是一个有序链表。
在查找时优先从最高层开始向后查找，当到达某个节点时，如果next节点值大于要查找的值或next指针指向null，则从当前节点下降一层继续向后查找。
如图：

第一次分层。
遍历5次找到元素9（红色的线为查找路径）

第二次分层
遍历三次找到元素9

这种数据结构，就是跳跃表，它具有二分查找的功能。

插入：

上面例子中，9个结点，一共3层，是理想的跳跃表。
通过抛硬币（概率1/2）的方式来决定新插入结点跨越的层数：
正面朝上：插入上层
背面朝上：不插入上层
达到1/2概率（计算次数）

删除

找到指定元素并删除每层的该元素即可

跳跃表特点：

每层都是一个有序链表
查找次数近似于层数（1/2）
底层包含所有元素
空间复杂度 O(n) 扩充了一倍

redis实现

typedef struct zskiplistNode { 
    sds ele; /* 存储字符串类型数据 redis3.0版本中使用robj类型表示， 但是在redis4.0.1中直接使用sds类型表示 */ 
    double score;//存储排序的分值 
    struct zskiplistNode *backward;//后退指针，指向当前节点最底层的前一个节点 /* 层，柔性数组，随机生成1-64的值 */
    struct zskiplistLevel{ 
        struct zskiplistNode *forward; //指向本层下一个节点 
        unsigned int span;//本层下个节点到本节点的元素个数 
    }level[]; 
} zskiplistNode; //链表 
typedef struct zskiplist{ //表头节点和表尾节点 
    structz skiplistNode *header, *tail; //表中节点的数量 
    unsigned long length; //表中层数最大的节点的层数 
    int level; 
}zskiplist;

跳跃表的优势：

1、可以快速查找到需要的节点 O(logn)
2、可以在O(1)的时间复杂度下，快速获得跳跃表的头节点、尾结点、长度和高度。
应用场景：有序集合的实现

字典

字典dict又称散列表（hash），是用来存储键值对的一种数据结构。
Redis整个数据库是用字典来存储的。（K-V结构）
对Redis进行CURD操作其实就是对字典中的数据进行CURD操作。

数组

数组：用来存储数据的容器，采用头指针+偏移量的方式能够以O(1)的时间复杂度定位到数据所在的内
存地址。
Redis 海量存储 快

Hash函数

Hash（散列），作用是把任意长度的输入通过散列算法转换成固定类型、固定长度的散列值。
hash函数可以把Redis里的key：包括字符串、整数、浮点数统一转换成整数。
key=100.1 String “100.1” 5位长度的字符串
Redis-cli :times 33
Redis-Server : MurmurHash
数组下标=hash(key)%数组容量(hash值%数组容量得到的余数)

Hash冲突

不同的key经过计算后出现数组下标一致，称为Hash冲突。
采用单链表在相同的下标位置处存储原始key和value
当根据key找Value时，找到数组下标，遍历单链表可以找出key相同的value

字典的实现

redis字典实现包含：字典（dict）,Hash表(dictht)，hash表节点（dicEntry）



添加元素图解

rehash

dict实现中主要用到如下结构体,其实就是个典型的链式hash。

一个dict会有2个hash table，由dictht结构管理，编号为0和1.

使用是优先使用0号hash table，当空间不足（在数据插入的时候会调用dictKeyIndex,该方法里会调用_dictExpandIfNeeded，判断dict是否需要rehash，当dict中元素大于桶的个数时，调用dictExpand扩展hash）时会调用dictExpand来扩展hash table，此时准备1号hash table用于增量的rehash使用。rehash完成后把0号释放，1号保存到0号。
rehashidx是下一个需要rehash的项在ht[0]中的索引，不需要rehash时置为-1。也就是说-1时，表示不进行rehash。

active rehashing ：

serverCron中，当没有后台子线程时，会调用incrementallyRehash，最终调用dictRehashMilliseconds。incrementallyRehash的时间较长，rehash的个数也比较多。这里每次执行 1 millisecond rehash 操作；如果未完成 rehash，会在下一个 loop 里面继续执行。

lazy rehashing：

_dictRehashStep中，也会调用dictRehash，而_dictRehashStep每次仅会rehash一个值从ht[0]到 ht[1]，但由于_dictRehashStep是被dictGetRandomKey、dictFind、 dictGenericDelete、dictAdd调用的，因此在每次dict增删查改时都会被调用，这无疑就加快rehash了过程。

dictRehash每次增量rehash n个元素，由于在自动调整大小时已设置好了ht[1]的大小，因此rehash的主要过程就是遍历ht[0]，取得key，然后将该key按ht[1]的 桶的大小重新rehash，并在rehash完后将ht[0]指向ht[1],然后将ht[1]清空。在这个过程中rehashidx非常重要，它表示上次rehash时在ht[0]的下标位置
但是在调用dictFind的时候，可能需要对两张dict表做查询。唯一的优化判断是，当key在ht[0]不存在且不在rehashing状态时，可以速度返回空。如果在rehashing状态，当在ht[0]没值的时候，还需要在ht[1]里查找。
dictAdd的时候，如果状态是rehashing，则把值插入到ht[1]，否则ht[0]。

压缩列表

压缩列表（ziplist）是由一系列特殊编码的连续内存块组成的顺序型数据结构
节省内存
是一个字节数组，可以包含多个节点（entry）。每个节点可以保存一个字节数组或一个整数。
压缩列表的数据结构如下：

zlbytes：压缩列表的字节长度
zltail：压缩列表尾元素相对于压缩列表起始地址的偏移量
zllen：压缩列表的元素个数
entry1…entryX : 压缩列表的各个节点
zlend：压缩列表的结尾，占一个字节，恒为0xFF（255）
entryX元素的编码结构：

previous_entry_length：前一个元素的字节长度
encoding:表示当前元素的编码
content:数据内容
ziplist结构体如下：

应用场景：
sorted-set和hash元素个数少且是小整数或短字符串（直接使用）[存储指针8字节，而数字长度会小于指针长度]
list用快速链表(quicklist)数据结构存储，而快速链表是双向列表与压缩列表的组合。（间接使用）

整数集合

整数集合(intset)是一个有序的（整数升序）、存储整数的连续存储结构。
当Redis集合类型的元素都是整数并且都处在64位有符号整数范围内（2^64），使用该结构体存储。
应用场景：
可以保存类型为int16_t、int32_t 或者int64_t 的整数值，并且保证集合中不会出现重复元素。

快速列表（重要）

快速列表（quicklist）是Redis底层重要的数据结构。是列表的底层实现。（在Redis3.2之前，Redis采
用双向链表（adlist）和压缩列表（ziplist）实现。）在Redis3.2以后结合adlist和ziplist的优势Redis设
计出了quicklist。

双向链表

双向链表优势：

1. 双向：链表具有前置节点和后置节点的引用，获取这两个节点时间复杂度都为O(1)。
2. 普通链表（单链表）：节点类保留下一节点的引用。链表类只保留头节点的引用，只能从头节点插
   入删除
3. 无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL,对链表的访问都是以 NULL 结
   束。
   环状：头的前一个节点指向尾节点
4. 带链表长度计数器：通过 len 属性获取链表长度的时间复杂度为 O(1)。
5. 多态：链表节点使用 void* 指针来保存节点值，可以保存各种不同类型的值。

快速列表

quicklist是一个双向链表，链表中的每个节点时一个ziplist结构。quicklist中的每个节点ziplist都能够存
储多个数据元素。

// 快速列表
struct quicklist {
    quicklistNode* head;
    quicklistNode* tail;
    long count; // 元素总数
    int nodes; // ziplist 节点的个数
    int compressDepth; // LZF 算法压缩深度
    ...
}
// 快速列表节点
struct quicklistNode {
    quicklistNode* prev;
    quicklistNode* next;
    ziplist* zl; // 指向压缩列表
    int32 size; // ziplist 的字节总数
    int16 count; // ziplist 中的元素数量
    int2 encoding; // 存储形式 2bit，原生字节数组还是 LZF 压缩存储
    ...
}

struct ziplist_compressed {
    int32 size;
    byte[] compressed_data;
}

struct ziplist {
    ...
}

流对象

stream主要由：消息、生产者、消费者和消费组构成。

Redis Stream的底层主要使用了listpack（紧凑列表）和Rax树（基数树）。

listpack

listpack表示一个字符串列表的序列化，listpack可用于存储字符串或整数。用于存储stream的消息内容。

listpack是对ziplist的改进，它比ziplist少了一个定位最后一个元素的属性（最后一个元素距离起始偏移量），listpack无需这个字段辅助逆序遍历。它的entry将长度字段放在了尾部，且记录的是本entry的长度，有了它就可以快速定位前一个entry的末尾，依然可以逆序遍历（在listpack定位到最后一个元素只需要总长度减去最后一个entry的长度即可）。这样本entry的属性不会出现在其他entry中了，消除了级联更新。但listpack目前只用在stream中。

Rax Tree

Rax 是一个有序字典树 (基数树 Radix Tree)，按照 key 的字典序排列，支持快速地定位、插入和删除操作。

Rax 被用在 Redis Stream 结构里面用于存储消息队列，在 Stream 里面消息 ID 的前缀是时间戳 + 序
号，这样的消息可以理解为时间序列消息。使用 Rax 结构 进行存储就可以快速地根据消息 ID 定位到具
体的消息，然后继续遍历指定消息 之后的所有消息。

redis扩展功能

LUA脚本

从Redis2.6.0版本开始，通过内置的lua编译/解释器，可以使用EVAL命令对lua脚本进行求值。
脚本的命令是原子的，RedisServer在执行脚本命令中，不允许插入新的命令。脚本的命令可以复制，RedisServer在获得脚本后不执行，生成标识返回，Client根据标识就可以随时执行。

EVAL命令

通过执行redis的eval命令，可以运行一段lua脚本。

EVAL script numkeys key [key ...] arg [arg ...]

命令说明：

• script参数：是一段Lua脚本程序，它会被运行在Redis服务器上下文中，这段脚本不必(也不应该)
  定义为一个Lua函数。
• numkeys参数：用于指定键名参数的个数。
• key [key …]参数： 从EVAL的第三个参数开始算起，使用了numkeys个键（key），表示在脚本中
  所用到的那些Redis键(key)，这些键名参数可以在Lua中通过全局变量KEYS数组，用1为基址的形
  式访问( KEYS[1] ， KEYS[2] ，以此类推)。
• arg [arg …]参数：可以在Lua中通过全局变量ARGV数组访问，访问的形式和KEYS变量类似(ARGV[1] 、 ARGV[2] ，诸如此类)。

eval "return {KEYS[1],KEYS[2],ARGV[1],ARGV[2]}" 2 key1 key2 first second

lua脚本中调用Redis命令

• edis.call()：
  • 返回值就是redis命令执行的返回值
  • 如果出错，则返回错误信息，不继续执行
• redis.pcall()：
  • 返回值就是redis命令执行的返回值
  • 如果出错，则记录错误信息，继续执行
• 注意事项
  • 在脚本中，使用return语句将返回值返回给客户端，如果没有return，则返回nil

eval "return redis.call('set',KEYS[1],ARGV[1])" 1 n1 zhaoyun

慢日志查询

监视器