拉勾教育学习-笔记分享のRedis"苏醒" I_ArchieSelfless的专栏文章_微信文章

【文章内容输出来源：拉勾教育Java高薪训练营】
--- 所有脑图均本人制作，未经允许请勿滥用 ---
Redis 是分布式学习中必须要掌握的重点技术，可以多花时间啃一啃

合抱之木，生于毫末；九层之台，起于垒土

Redis官网

一、缓存原理&设计

part 1 - 基本思想

「使用场景」

为DB减轻压力

最早：应用程序 <==> DBMS（数据in硬盘）
访问量上升（万级）：主从架构 + 分库分表
访问量骤增（十万~百万级）：缓存（数据in内存）

提高响应速度

数据库的数据是存在文件里，也就是硬盘。与内存做交换（swap）

在大量瞬间访问时（高并发）MySQL单机会因为频繁IO而造成无法响应，而且 MySQL 的 InnoDB 有行锁！

将数据缓存在Redis中，也就是存在了内存中。内存天然支持高并发访问。可以瞬间处理大量请求。

Redis：QPS 可到达 11万/S, 读请求可达 8万写/S

做 Session 分离

传统的 session 是由 tomcat 自己进行维护和管理。集群或分布式环境，不同的 tomcat 管理各自的 session。只能在各个 tomcat 之间，通过网络和 IO 进行 session 的复制，极大的影响了系统的性能。

各个 Tomcat 间复制 session，性能损耗
不能保证各个 Tomcat 的 Session 数据同步

将登录成功后的 Session 信息，存放在 Redis 中，这样多个服务器(Tomcat)可以共享Session信息。Redis的作用是数据的临时存储

做分布式锁（Redis）

一般讲锁是多线程的锁，是在一个进程中的

多个进程（JVM）在并发时也会产生问题，也要控制时序性

可以采用分布式锁。使用Redis实现 setNX

做乐观锁（Redis）

同步锁和数据库中的行锁、表锁都是悲观锁

悲观锁的性能是比较低的，响应性比较差

高性能、高响应（秒杀）采用乐观锁

Redis可以实现乐观锁 watch + incr

「什么是缓存」

缓存原指CPU上的一种高速存储器，它先于内存与CPU交换数据，速度很快; 现在泛指存储在计算机上的原始数据的复制集，便于快速访问。

在互联网技术中，缓存是系统快速响应的关键技术之一,是 以空间换时间的一种技术（艺术）

明显的，Processor(我们写的程序) 运行时，首选同在CPU中的缓存进行数据判定，而后才是同主板的内存，最后不远万里去硬盘看看。

「大型网站中的缓存使用」

「常见的缓存分类」

客户端缓存
1. 页面缓存：Cookie、WebStorage（SessionStorage和LocalStorage）、WebSql、indexDB、Application Cache等
2. 浏览器缓存：当客户端向服务器请求资源时，会先抵达浏览器缓存，如果浏览器有“要请求资源”的副本，就可以直接从浏览器缓存中提取而不是从原始服务器中提取这个资源。
  - 强制缓存：直接使用浏览器的缓存数据
  - 协商缓存：服务器资源未修改，使用浏览器的缓存（304）；反之，使用服务器资源（200）
3. app缓存：原生APP中把数据缓存在内存、文件或本地数据库（SQLite）中。比如图片文件。
网络端缓存
1. Web代理缓存：Nginx等，可以缓存原生服务器的静态资源
2. 边缘缓存：如已经商业化的 CDN（Content Delivery Network-内容分发网络），通过部署在各地的边缘服务器，使用户就近获取所需内容，降低网络拥塞，提高用户访问响应速度和命中率。
服务端缓存
1. 数据库级缓存：使用数据库的内部buffer缓存数据。如 MySQL 的 InnoDB引擎，将InnoDB索引、数据块缓存在 buffer-pool 中
2. 平台级缓存：带有缓存特性的应用框架。如 GuavaCache 、EhCache（二级缓存，硬盘）、OSCache（页面缓存）等。因为被部署在应用服务器上，也称为服务器本地缓存。
3. 应用级缓存（重点）：具有缓存功能的中间件：Redis（阿里、百度）、Memcached、EVCache（AWS）、Tair（阿里、美团）等

part 2 - 缓存の优势、代价

「优势」

响应速度快，提升了用户的体验
减轻服务器压力
提高系统的吞吐量、并发用户数目

「代价」

额外的硬件技术（如果用云服务器提供的服务就可以避免）
高并发下，一旦出现缓存失败（缓存穿透、雪崩、击穿），会造成DB的压力剧增，甚至导致崩溃
缓存无法和 DB 实时同步
缓存并发竞争（多个Redis同时对一个key进行set value操作时，由于执行顺序引起并发问题）

part 3 - 读写模式

「Cache Aside Pattern 旁路缓存 ☆」

最经典的 缓存+数据库 读写模式 —— 读的时候，先读缓存，缓存没有的话，就读数据库，然后取出数据后放入缓存，同时返回响应。

读 ==> 先读缓存，缓存没有再读数据库，并将数据同步到缓存后，返回响应

写 ==> 先更新数据库，然后把缓存全部删除（之所以写后删缓存，是因为缓存往往是一种数据结构：List、Hash，若写后同步，需要遍历，而对于上万级的数据遍历是非常耗时的）

高并发下脏读情况：

先更新数据库，再更新缓存（数据库{A:1}=>{A:2},但缓存依旧保持{A:1}，用户读到的"A 的值为 1"就是个脏数据）

先删除缓存，再更新数据库（缓存被删，数据库还未来得及更新数据时，用户调用得到 (旧) 数据！脏读）

先更新数据库，再删除缓存（在数据库 update ----> commit 之间，有用户来读数据，然而此时系统识别update已经操作完成，所以立马清除了缓存，于是用户读取操作未命中缓存，而是去读取了数据库中的尚未被 commit 成功的旧数据，脏读）

虽然高并发下都会存在脏读，但几率最小的依旧是 先写后删，后续可以通过各类手段(延时双删...)再次降低错误率

「Read/Write Through Pattern 直读/直写缓存」

应用程序只操作缓存，缓存操作数据库.

Read-Through（穿透读模式/直读模式）：应用程序读缓存，缓存没有，由缓存回源到数据库，并写入缓存
Write-Through（穿透写模式/直写模式）：应用程序写缓存，缓存写数据库

该种模式需要提供数据库的handler，开发较为复杂。代表技术——GuavaCache

「Write Behind Caching Pattern 后写缓存」

应用程序只更新缓存.缓存通过异步的方式将数据批量或合并后更新到DB中.

不能实时同步，甚至会丢数据

part 4 - 缓存架构的设计思路

「多层次」

即便分布式缓存宕机了，本地缓存也还可以使用

「数据类型」

简单数据类型：
- 满足以下条件时:
  1. value 是字符串/二进制
  2. value 值较大（>100K）
  3. 只需要进行 setter、getter
往往选择 MemCache，它是纯内存缓存，多线程 k-v
复杂数据类型：
- 满足以下条件时:
  1. value 是 Hash、Set、List...
  2. 需要进行关系的存储、聚合操作、计算...
往往选择 Redis

「需做集群」

可以考虑: Redis (分布式情形)、Codis、哨兵+主从、RedisCluster...

二、数据类型和底层数据结构

part 1 - Redis数据类型和应用场景

Redis是一个 Key-Value 的存储系统，使用 ANSI C语言 编写

key：字符串（大小写敏感）
value：
1. 常用类型：string、list、set、sortedset（zset）、hash
2. bitmap位图、geo地理位置
3. stream（Redis5.0新增）

「Redis的key设计」

key的命名规则不同于一般语言，键盘上除了空格、\n换行外的其他大部分字符都可以组合使用
反例：“my key” × | “mykey\n” ×
key的形式可以由我们自己自由定义
- 建议的命名规范：TABLE_NAME : PRIMARY_KEY_VALUE : COLLUME_NAME ==> 表名:主键值:当前列名
- 举例：user:7:user_name（语义为：user表中id为7的字段user_name）
过短（可读性差）过长（占内存）都不好，最少要保证语义表述清晰：
- u:1000:pwd ×
- user:1000:password √

【key常用命令】

del key : 删除key
type key : 查看key的类型
keys [pattern] : 模糊查找
- keys * ：匹配当前数据库的所有key
- keys n?am ：匹配 name、neme、ngme...
- keys n*me ：匹配 name、naaaaame...
- keys n[ae]me ：只匹配 name 和 neme
expire key seconds : 指定key的过期时间
ttl key : 查看key的剩余时间（2-已过期 / 1-永生）
exists key : 检查key是否存在

「string 字符串类型」

string 可表示三种值得类型：字符串、整数、浮点数。value存储最大数据量为512M，可以存放json数据，图像数据等等

【常用操作】

set key value : 赋值，若已存在则覆盖
get key : 取值，若key不存在，返回 nil
getset key value : 取值并赋值(不存在key时返回nil，存在时先返回原值再覆盖)
setex key seconds value : 设置value值并设置过期时间命令setex（单位秒）
setnx key value : 当value不存在时采用赋值（用于分布式锁）
append key valu : 向尾部追加值，若key不存在则变为set操作
strlen key : 获取字符串长度
incr key : 递增数字（用于乐观锁）
incrby key increment : 增加指定的整数
decr key : 递减数字
decrby key decrement : 减少指定的整数
getrange key start end ：从start->end截取字符串（下标从0开始）

在实际的开发过程中，如果涉及到多线程安全问题。能不加锁，尽量不加锁。因为加锁效率低。（需要频繁去判断是否存在锁；要不断的等待|唤醒）
对于线程加锁的问题，可以考虑使用redis来解决。原因：redis的key是单线程模式。

「list 列表类型」

可以存储有序、可重复的元素,且获取头部或尾部附近的记录是极快的
list的元素个数最多为 2^32-1个（40亿）

【常用操作】

lpush key v1 v2 ... : 从左侧插入列表
lpop key : 从列表左侧取出
rpush key v1 v2 ... : 从右侧插入列表
rpop key : 从列表右侧取出
lpushx key value : 将值插入到列表头部
rpushx key value : 将值插入到列表尾部
blpop key timeout : 从列表左侧取出，当列表为空时阻塞，可以设置最大阻塞时间，单位为秒
brpop key timeout : 从列表右侧取出，当列表为空时阻塞，可以设置最大阻塞时间，单位为秒
llen key : 获得列表中的元素个数
lindex key index : 获得列表中下标为index的元素 index从0开始
lrange key start end : 返回列表中指定区间的元素，区间通过start和end指定，-1 表示最后一个索引。
lrem key count value : 删除列表中与value相等的元素
- 当count>0时， lrem会从列表左边开始删除
- 当count<0时， lrem会从列表右边开始删除
- 当count=0时， lrem会删除所有值为value的元素
lset key index value : 将列表index位置的元素设置成value的值
ltrim key start end : 对列表进行修剪，只保留start到end区间
rpoplpush key1 key2 : 从key1列表右侧弹出并插入到key2列表左侧
brpoplpush key1 key2 : 从key1列表右侧弹出并插入到key2列表左侧，会阻塞
linsert key BEFORE/AFTER pivot value : 将value插入到列表，且位于值pivot之前或之后

「set 集合类型」

无序且元素唯一，集合中最大的成员数为 2^32-1

【常用操作】

sadd key mem1 mem2... : 为集合添加新成员
srem key mem1 mem2... : 删除集合中指定成员
smembers key : 获得集合中所有元素
spop key : 返回集合中一个随机元素，并将该元素删除
srandmember key : 返回集合中一个随机元素，不会删除该元素
scard key : 获得集合中元素的数量
sismember key member : 判断元素是否在集合内
sinter key1 key2 key3 : 求多集合的交集
sdiff key1 key2 key3 : 求多集合的差集
sunion key1 key2 key3 : 求多集合的并集

「sortedset 有序集合类型」

元素本身是无序不重复的，每个元素关联一个分数（score），可按分数排序，分数可重复

【常用操作】

zadd key score1 member1 score2 member2... : 为有序集合添加新成员
（score可以是整数，也可以是浮点数，还可以是+inf表示无穷大，-inf表示负无穷大）
zrem key mem1 mem2 : 删除有序集合中指定成员
zcard key : 获得有序集合中的元素数量
zcount key min max : 返回集合中score值在[min,max]区间的元素数量
zincrby key increment member: 在集合的member分值上加increment
zscore key member : 获得集合中member的分值
zrank key member : 获得集合中member的排名（按分值从小到大）
zrevrank key member : 获得集合中member的排名（按分值从大到小）
zrange key start end (withscores) : 获得集合中指定区间成员，按分数递增排序
zrevrange key start end (withscores) : 获得集合中指定区间成员，按分数递减排序

「hash 散列表类型」

Redis hash 是一个 string 类型的 field 和 value 的映射表，它提供了字段和字段值的映射。

【常用操作】

hset key field value : 赋值，不区别新增或修改
hmset key field1 value1 field2 value2 : 批量赋值
hsetnx key field value : 赋值，如果filed存在则不操作
hexists key field : 查看某个field是否存在
hget key key field : 获取一个字段值
hmget key field1 field2 : 获取多个字段值
hgetall key : 获取该key下所有的值
hdel key filed1 field2 : 删除指定字段
hincrby key field increment : 指定字段自增increment
hlen key : 获得键值对数量

「bitmap 位图类型」

bitmap是进行位操作的,通过一个bit位来表示某个元素对应的值或者状态,其中的key就是对应元素本身

【常用操作】

setbit key offset value : 设置key在offset处的bit值(1或0)
getbit key offset : 获得key在offset处的bit值
bitcount key : 获得key的bit位为1的个数
bitpos key value : 返回第一个被设置为bit值的索引值
bitop and[or/xor/not] destkey key [key] : 对多个key 进行逻辑运算后存入destkey中

「geo 地理位置类型」

geo是Redis用来处理位置信息的。在Redis3.2中正式使用。主要是利用了 Z阶曲线、Base32编码和geohash算法

z阶曲线：在x轴和y轴上将十进制数转化为二进制数，采用x轴和y轴对应的二进制数依次交叉后得到一个六位数编码。把数字从小到大依次连起来的曲线称为Z阶曲线，Z阶曲线是把多维转换成一维的一种方法。
Base32编码：Base32这种数据编码机制，主要用来把二进制数据编码成可见的字符串，其编码规则是：任意给定一个二进制数据，以5个位(bit)为一组进行切分(base64以6个位(bit)为一组)，对切分而成的每个组进行编码得到1个可见字符。Base32编码表字符集中的字符总数为32个（0-9、b-z 去掉a、i、l、o），这也是Base32名字的由来。
geohash算法：Gustavo在2008年2月上线了geohash.org网站。Geohash是一种地理位置信息编码方法。经过geohash映射后，地球上任意位置的经纬度坐标可以表示成一个较短的字符串。可以方便的存储在数据库中，附在邮件上，以及方便的使用在其他服务中。以北京的坐标举例，[39.928167,116.389550]可以转换成 wx4g0s8q3jf9 。

Redis中经纬度使用52位的整数进行编码，放进zset中，zset的value元素是key，score是GeoHash的52位整数值。在使用Redis进行Geo查询时，其内部对应的操作其实只是zset(skiplist)的操作。通过zset的score进行排序就可以得到坐标附近的其它元素，通过将score还原成坐标值就可以得到元素的原始坐标。

【常用操作】

geoadd geoadd key 经度1 纬度1 成员名称1 经度2 纬度2 成员名称2... : 添加地理坐标
geohash key 成员名称1 成员名称2... : 返回标准的geohash串
geopos key 成员名称1 成员名称2... : 返回成员经纬度
geodist key 成员1 成员2 单位 : 计算成员间距离
georadius key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count]:
以给定的经纬度为中心，返回键包含的位置元素当中，与中心的距离不超过给定最大距离的所有位置元素
范围可以使用以下其中一个单位：
- m 米 / km 千米 / mi 英里 / ft 英尺
在给定以下可选项时，命令会返回额外的信息：
- withdist 返回位置元素的同时，将位置元素与中心之间的距离也一并返回
- withcoord 将位置元素的经度和维度也一并返回
- withhash 以 52 位有符号整数的形式，返回位置元素经过原始 geohash 编码的有序集合分值
使用 COUNT count 可以获取前 count 个匹配元素
georadiusbymember key member radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] :
和 GEORADIUS 命令一样，都可以找出位于指定范围内的元素，但是 GEORADIUSBYMEMBER 的中心点是由给定的位置元素决定的

「stream 数据流类型」

stream是Redis5.0后新增的数据结构，用于可持久化的消息队列

每个 Stream 都有唯一的名称，它就是 Redis 的 key，首次使用 xadd 指令追加消息时自动创建

【常用操作】

xadd key id<*> field1 value1 : 将指定消息数据追加到指定队列(key)中，*表示最新生成的id（当前时间+序列号）
xread [COUNT count] [BLOCK milliseconds] STREAMS key [key...] ID [ID...] : 从消息队列中读取
COUNT：读取条数，BLOCK：阻塞读（默认不阻塞）key：队列名称 id：消息id
xrange key start end [COUNT] : 读取队列中给定ID范围的消息。 COUNT：返回消息条数（消息id从小到大）
xrevrange key start end [COUNT] : 读取队列中给定ID范围的消息。COUNT：返回消息条数（消息id从大到小）
xdel key id : 删除队列的消息
xgroup create key groupname id : 创建一个新的消费组
xgroup destroy key groupname : 删除指定消费组
xgroup delconsumer key groupname cname : 删除指定消费组中的某个消费者
xgroup setid key id : 修改指定消息的最大id
xreadgroup group groupname consumer COUNT streams key : 从队列中的消费组中创建消费者并消费数据（consumer不存在则创建）

part 2 - Redis 底层数据结构

Redis没有表的概念，实例所对应的 db 以编号区分，db 本身就是 key 的命名空间.

「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;
复制代码

重点关注 id / dict / expires 三个参数，后面会详细解析

「RedisObject 结构 ☆」

结构信息概览

redisDb结构体：

typedef struct redisObject {
    unsigned type:4; // 类型，对应所有的对象类型
    unsigned encoding:4; // 对象的内部编码
    int refcount; // 引用计数
    unsigned lru:LRU_BTIS; // LRU_BITS (24bit)，记录最后一次被命令程序访问的时间
}robj;
复制代码

4位 type

REDIS_STRING(字符串) / REDIS_LIST (列表) / REDIS_HASH(哈希) / REDIS_SET(集合) / REDIS_ZSET(有序集合)

4位 encoding

每个对象有不同的实现编码，Redis 可以根据不同的使用场景来为对象设置不同的编码，大大提高了 Redis 的灵活性和效率

通过 object encoding 命令，可以查看对象采用的编码方式

24位 LRU

记录的是对象最后一次被命令程序访问的时间，（ 4.0 版本占 24 位，2.6 版本占 22 位）

refcount

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

【7种type】

I 字符串对象

Redis 使用了 SDS(Simple Dynamic String)。用于存储字符串和整型数据。

struct sdshdr {
    // 记录buf数组中已使用字节的数量
    int len;
    // 记录buf数组中未使用字节的数量
    int free;
    // 字符数组，用于保存字符串。( 长度=free+len+1 )
    char buf[];
}
复制代码

【优势】

SDS 在 C 字符串的基础上加入了 free 和 len 字段，获取字符串长度。

时间复杂度从 C 字符串的 O(n) 优化到了 SDS 的 O(1)

SDS 由于记录了长度，在可能造成缓冲区溢出时会自动重新分配内存，杜绝了缓冲区溢出

可以存取二进制数据，以字符串长度len来作为结束标识

C 语言 ==> 本身就是以 \0 结束标识空字符串，如果要表示二进制串，会由于 \0 的语义而混淆"是否结束"这个概念（二进制本身存在\0的语义）

SDS ==> 将二进制和非二进制区分开来：

非二进制结束标识： \0

二进制结束标识： len

II 跳跃表

跳跃表是有序集合（sorted-set）的底层实现，效率高，实现简单。
基本思想：将有序链表中的部分节点分层，每一层都是一个有序链表

查找：在查找时优先从最高层开始向后查找，当到达某个节点时，如果next节点值大于要查找的值或next指针指向null，则从当前节点下降一层继续向后查找。(具有二分查找的功能)
- 举个栗子：在以下链表中查找元素9
  - 直接循环，不分层查找，要遍历8次
  - 一次分层，遍历5次
  - 二次分层，遍历4次
  - 三次分层，遍历5次
删除：找到指定元素并删除每层的该元素

III 字典

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

C 语言中没有内置这种数据结构的实现，所以字典依然是 Redis 自己构建的。

Redis 的字典结构定义如下：

typedef struct dict {
    // 对应的特定操作函数
    dictType *type;
    // 上述类型函数所对应的可选参数
    void *privdata;
    // 两张哈希表，ht[0]：原生表，ht[1]：rehash表
    dictht ht[2];
    // rehash 标识，等于-1时代表未处在rehash状态，不等于-1则表示了rehash的表索引
    long rehashidx;
    // 当前运行的迭代器数量
    int iterators;
}dict;
复制代码

Redis 的操作函数使用dictType结构体，如下：

typedef struct dictType {
    // 计算哈希值得函数
    unsigned int (*hashFunction)(const void *key);
    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
    // 复制值得函数
    void *(*valDup)(void *privdata, const void *obj);
    // 比较键的函数
    int (*keyCopare)(void *privdata, const void *key1, const void *key2);
    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
}dictType;
复制代码

Redis 的字典使用哈希表作为底层实现，结构如下：

typedef struct dictht{
     //哈希表数组
     dictEntry **table;
     //哈希表大小
     unsigned long size;
     //哈希表大小掩码，用于计算索引值
     //总是等于 size-1
     unsigned long sizemask;
     //该哈希表已有节点的数量
     unsigned long used;
}dictht
复制代码

哈希表是由数组 table 组成，table 中每个元素都是指向 dict.h/dictEntry 结构，dictEntry 结构定义如下：

// key 用来保存键，val 属性用来保存值，值可以是一个指针，也可以是uint64_t整数，也可以是int64_t整数
typedef struct dictEntry{
     //键
     void *key;
     //值
     union{
          void *val;
          uint64_tu64;
          int64_ts64;
     }v;
     // 指向下一个哈希表节点，形成链表
     // 通过这个指针采用链地址法，解决哈希冲突
     struct dictEntry *next;
}dictEntry
复制代码

哈希算法

// 1.使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);
// 2.使用哈希表的sizemask属性和第一步得到的哈希值，计算索引值
index = hash & dict->ht[x].sizemask;	
复制代码

解决哈希冲突
- 通过字典里面的 *next 指针指向下一个具有相同索引值的哈希表节点（链地址法）
扩容和缩容
1. 如果执行扩展/收缩操作，会基于原哈希表创建一个大小等于 ht[0].used*2n/ht[0].uesd*n/2 的哈希表
  （扩展==>根据原哈希表已使用的空间扩大一倍创建另一个哈希表）
  （扩展==>根据原哈希表已使用的空间缩小一倍创建另一个哈希表）
2. 重新利用上面的哈希算法，计算索引值，然后将键值对放到新的哈希表位置上
3. 所有键值对都迁徙完毕后，释放原哈希表的内存空间
触发扩容的条件
- 服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子¹大于等于1
- 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于5
渐进式 rehash
- "渐进式"语义：扩容和收缩操作不是一次性、集中式完成的，而是分多次、渐进式完成的
  键值对几十个左右的rehash操作可以一瞬间完成，一旦上百万乃至上亿，便无法一次性rehash，所以 "渐进式" 因运而生 ——
  - 查找&删除：在两个哈希表上进行，第一个哈希表没有找到，就会去第二个哈希表上进行查找
  - 新增：在新的哈希表上进行

完整的Redis字典数据结构：

IV 压缩列表

压缩列表（ziplist）是由一系列特殊编码的连续内存块组成的顺序型数据结构，和数组不同的是，它允许存储的数据大小不同

压缩列表主要特点就是 "节省内存"，这个 "节省" 是相对于数组来说的；
最早的数组每个数据域的大小是固定的，如果想要动态加入数据，可以将每个待加入的数据跟上一个length属性来标识：当前数据的大小。

Redis中压缩列表的实现主要体现在list和hash中：
- 当一个列表只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做列表的底层实现
- 当一个哈希只包含少量键值对,比且每个键值对的键和值要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做哈希的底层实现
Redis压缩列表的构成:
- 【节点entry】一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一个字节数组或者一个整数值
  - 结构体：
```
typedef struct zlentry {
    // previous_entry_length字段的长度
    unsigned int prevrawlensize;
    // previous_entry_length字段存储的内容
    unsigned int prevrawlen;
    // encoding字段的长度
    unsigned int lensize;
    // 数据内容长度
    unsigned int len;
    // 当前元素的首部长度，即previous_entry_length字段长度 + encoding字段长度
    unsigned int headersize;
    // 数据类型
    unsigned char encoding;
    // 当前元素首地址
    unsigned char *p;
}zlentry;
复制代码
```
  - 节点保存字节数组时可以是：
    1. 长度小于等于63(2^6-1)字节的字节数组
    2. 长度小于等于16383(2^14-1)字节的字节数组
    3. 长度小于等于4294967295(2^32-1)字节的字节数组
  - 节点保存整数值时可以是：
    1. 4位长,介于0至12之间的无符号整数
    2. 1字节长的有符号整数
    3. 3字节长的有符号整数
    4. int16_t类型整数
    5. int32_t类型整数
    6. int64_t类型整数
  - 节点的构成：
    - previous_entry_length: 以字节为单位,记录了压缩列表中前一个节点的长度
    - encoding: 记录了节点的content属性所保存数据的类型以及长度
    - content: 保存节点的值 (值的类型和长度由节点的encoding属性决定)
- 【总字节长度zlbytes】 压缩列表的字节长度
- 【偏移量zltail】 压缩列表尾元素相对于压缩列表起始地址的偏移量
- 【元素个数allen】 压缩列表的元素个数
- 【结尾zlend】 压缩列表的结尾，占一个字节，恒为0xFF（255）

V 整数集合

整数集合(intset)是一个有序的（整数升序）、不重复存储整数的连续存储结构
当Redis集合类型的元素都是整数并且都处在64位有符号整数范围内（2^64），使用该结构体存储。(超过范围就会使用hashtable)
举个栗子：

结构定义：
- 结构体：
```
typedef struct intset{
    //编码方式
    uint32_t encoding;
    //集合中包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
} intset;
复制代码
```
  - contents数组: 是整数集合的底层实现，整数集合的每个元素都是 contents数组的个数组项(item),各个项在数组中按值的大小从小到大有序地排列,并且数组中不包含任何重复项
  - length：记录了数组的长度
  - encoding：记录了数组的编码方式
  intset结构将contents属性声明为int8_t类型的数组,但实际上 contents数组并不保存任何int8t类型的值, contents数组的真正类型取决于encoding属性的值。
  - encoding == INTSET_ENC_INT16: 数组为uint16_t类型(数组中的每一个元素都是int16_t类型的整数值)
  - encoding == INTSET_ENC_INT32: 数组为uint32_t类型(数组中的每一个元素都是int13_t类型的整数值)

VI 快速列表

快速列表（quicklist）是Redis底层重要的数据结构。是列表的底层实现。

在Redis3.2之前，Redis采用双向链表（adlist）和压缩列表（ziplist）实现）
在Redis3.2以后，结合adlist和ziplist的优势Redis设计出了quicklist

quicklist也是一个双向链表，每个节点都有一个aiplist结构来存储多个数据元素。

qucklist的结构体如下：

typedef struct quicklist {
    // 指向quicklist的头部
    quicklistNode *head;
    // 指向quicklist的尾部
    quicklistNode *tail;
    // 列表中所有数据项的个数总和
    unsigned long count;
    // quicklist节点的个数，即ziplist的个数
    unsigned int len;
    // ziplist大小限制，可以通过list-map-ziplist-size配置
    int fill : 16;
    // 节点压缩深度设置，可以通过list-compress-depth配置
    unsigned int compress : 16;
}quicklist;
复制代码

quicklistNode 结构体如下：

typedef struct quicklistNode {
    // 指向上一个ziplist节点
    struct quicklistNode *prev;
    // 指向下一个ziplistNode节点
    struct quicklistNode *next;
    // 数据指针，如果没有被压缩，就指向ziplist结构；反之指向quicklistLZF结构
    unsigned char *zl;
    // 表示指向ziplist结构的总长度(内存占用长度)
    unsigned int sz;
    // 表示ziplist中的数据项个数
    unsigned int count : 16;
    // 编码方式，1--ziplist，2--quicklistLZF
    unsigned int encoding : 2;
    // 预留字段，存放数据的方式，1--NONE，2--ziplist
    unsigned int container : 2;
    // 解压标记，当查看一个被压缩的数据时，需要暂时解压，标记此参数为1，之后再重新进行压缩
    unsigned int recompress : 1;
    // 测试相关
    unsigned int attempted_compress : 1;
    // 扩展字段，暂时没用
    unsigned int extra : 10;
}quicklistNode;
复制代码

数据压缩
- quicklist每个节点的实际数据存储结构为ziplist，这种结构的优势在于节省存储空间。
  为了进一步降低ziplist的存储空间，还可以对ziplist进行压缩。
  Redis采用的压缩算法是LZF。其基本思想是：数据与前面重复的记录重复位置及长度，不重复的记录原始数据。
- 压缩过后的数据可以分成多个片段，每个片段有两个部分：解释字段和数据字段
- quicklistLZF 结构体如下：
```
typedef struct quicklistLZF {
    // LZF压缩后占用的字节数
    unsigned int sz;
    // 柔性数组，指向数据部分
    char compressed[];
}
复制代码
```

VII 流对象

特指stream类型，主要组成：
- 底层数据结构：listpack（紧凑列表）+ Rax树（基数树）
  - listpack：表示一个字符串列表的序列化，listpack可用于存储字符串或整数。用于存储stream的消息内容。
  - Rax：有序字典树 (基数树 Radix Tree)，按照 key 的字典序排列，支持快速地定位、插入和删除操作。
    
    Rax 被用在 Redis Stream 结构里面用于存储消息队列，在 Stream 里面消息 ID 的前缀是时间戳 + 序号，这样的消息可以理解为时间序列消息。使用 Rax 结构进行存储就可以快速地根据消息 ID 定位到具体的消息，然后继续遍历指定消息之后的所有消息。

【10种encoding】

encoding 表示对象的内部编码，占 4 位。对于少的和小的数据，Redis采用小的和压缩的存储方式，体现Redis的灵活性。

string：
- int：REDIS_ENCODING_INT（int类型的整数）
- embstr：REDIS_ENCODING_EMBSTR（编码的简单动态字符串）
  小字符串长度小于44个字节
- raw：REDIS_ENCODING_RAW（简单动态字符串）
  大字符串长度大于44个字节
list：
- quicklist：REDIS_ENCODING_QUICKLIST（快速列表）
hash：
- dict：REDIS_ENCODING_HT（字典）
  当散列表元素的个数比较多或元素不是小整数或短字符串时
- ziplist：REDIS_ENCODING_ZIPLIST（压缩列表）
  当散列表元素的个数比较少，且元素都是小整数或短字符串时
set：
- intset：REDIS_ENCODING_INTSET（整数集合）
  当Redis集合类型的元素都是整数并且都处在64位有符号整数范围内（<18446744073709551616）
- dict：REDIS_ENCODING_HT（字典）
  当Redis集合类型的元素都是整数并且都处在64位有符号整数范围外（>18446744073709551616）
zset：
- ziplist：REDIS_ENCODING_ZIPLIST（压缩列表）
  当元素的个数比较少，且元素都是小整数或短字符串时
- skiplist: REDIS_ENCODING_SKIPLIST（跳跃表+字典）
  当元素的个数比较多或元素不是小整数或短字符串时

part 3 - 缓存过期和淘汰策略

「maxmemory」

redis 的 maxmemory 默认为 0，即不限制最大存储上限。

不设置 maxmemory：
- redis作为DB使用，保证数据的完整性；key将不再增加地保持固定
- 淘汰策略——noeviction（禁止驱逐）
设置 maxmemory：
- redis作为缓存使用，key可以不断增加

设置方式：在 redis.conf 中配置 maxmemory XXXXmb
(如果配置了maxmemory，也要同步配置 maxmemory-policy 淘汰策略)
查询方式：在控制台使用 config get maxmemory 查看

设置maxmemory多少合适？
1个Redis实例，保证系统运行 1 G ，剩下的就都可以设置Redis中物理内存的 3/4
此外官方还建议了：如果存在slave的附加，最好留出一定的内存出来(适当降低maxmemory)。
# In short... if you have slaves attached it is suggested that you set a lower
# limit for maxmemory so that there is some free RAM on the system for slave
# output buffers (but this is not needed if the policy is 'noeviction').
复制代码

「expire数据结构」

在Redis中可以使用expire命令设置一个键的存活时间(ttl: time to live)，过了这段时间，该键就会自动被删除

redisDb 结构体如下：

typedef struct redisDb {
  dict *dict;
  dict *expires;
  dict *blocking_keys;
  dict *ready_keys;
  dict *watched_keys;
  int id;
} redisDb;
复制代码

我们重点关注下 dict指针 & expires指针：

dict：用来维护一个 Redis 数据库中包含的所有 Key-Value 键值对
expires：用于维护一个 Redis 数据库中设置了失效时间的键（key 与失效时间的映射）
当我们使用 expire 命令设置一个key的失效时间时，Redis 首先到 dict 这个字典表中查找要设置的key是否存在：
- 存在 ==> 将目标key和失效时间添加到expires这个字典表
当我们使用 setex 命令向系统插入数据时，Redis 首先将 Key 和 Value 添加到 dict 这个字典表中，然后将 Key 和失效时间添加到 expires 这个字典表中

设置了失效时间的key和具体的失效时间全部都维护在 expires 这个字典表中

「过期策略」

【定时删除】：在设置键的过期时间的同时，创建一个定时器，让定时器在键的过期时间来临时，立即执行对键的删除操作
- tips ：虽然对内存友好，但是需要创建定时器，而且消耗CPU，一般不推荐使用

【惰性删除】：在key被访问时如果发现它已经失效，那么就删除它

tips ：该策略可以最大化地节省CPU资源，却对内存非常不友好。极端情况可能出现大量的过期key没有再次被访问，从而不会被清除，占用大量内存

底层：调用expireIfNeeded函数，该函数的意义是：读取数据之前先检查一下它有没有失效，如果失效了就删除它

int expireIfNeeded(redisDb *db, robj *key) {
  //获取主键的失效时间
  long long when = getExpire(db,key);
  //假如失效时间为负数，说明该主键未设置失效时间（失效时间默认为-1），直接返回0
  if (when < 0) return 0;
  //假如Redis服务器正在从RDB文件中加载数据，暂时不进行失效主键的删除，直接返回0
  if (server.loading) return 0;
 ...
  //如果以上条件都不满足，就将主键的失效时间与当前时间进行对比，如果发现指定的主键
  //还未失效就直接返回0
  if (mstime() <= when) return 0;
  //如果发现主键确实已经失效了，那么首先更新关于失效主键的统计个数，然后将该主键失
  //效的信息进行广播，最后将该主键从数据库中删除
  server.stat_expiredkeys++;
  propagateExpire(db,key);
  return dbDelete(db,key);
}
复制代码

【主动删除】: 在redis.conf文件中可以配置主动删除策略, 默认是no-enviction（不删除）

「内存淘汰策略」

内存淘汰策略是指：在Redis的用于缓存的内存不足时，怎么处理需要新写入且需要申请额外空间的数据

noeviction：当内存不足以容纳新写入数据时，新写入操作会报错。
allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用²的key。
allkeys-random：当内存不足以容纳新写入数据时，在键空间中，随机移除某个key。
volatile-lru：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，移除最近最少使用³的key。
volatile-random：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，随机移除某个key。
volatile-ttl：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，有更早过期时间的key优先移除。

负载因子=哈希表已保存节点数量/哈希表大小↩
LFU(Least frequently uesd)↩
LRU(Least recently uesd)↩

拉勾教育学习-笔记分享のRedis"苏醒" I

正文

拉勾教育学习-笔记分享のRedis"苏醒" I

一、缓存原理&设计

part 1 - 基本思想

「使用场景」

为DB减轻压力

提高响应速度

做 Session 分离

做 分布式锁（Redis）

做 乐观锁（Redis）

「什么是缓存」

「大型网站中的缓存使用」

「常见的缓存分类」

part 2 - 缓存の优势、代价

「优势」

「代价」

part 3 - 读写模式

「Cache Aside Pattern 旁路缓存 ☆」

「Read/Write Through Pattern 直读/直写缓存」

「Write Behind Caching Pattern 后写缓存」

part 4 - 缓存架构的设计思路

「多层次」

「数据类型」

「需做集群」

二、数据类型和底层数据结构

part 1 - Redis数据类型和应用场景

「Redis的key设计」

「string 字符串类型」

「list 列表类型」

「set 集合类型」

「sortedset 有序集合类型」

「hash 散列表类型」

「bitmap 位图类型」

「geo 地理位置类型」

「stream 数据流类型」

part 2 - Redis 底层数据结构

「RedisDB 结构」

「RedisObject 结构 ☆」

结构信息概览

【7种type】

【10种encoding】

part 3 - 缓存过期和淘汰策略

「maxmemory」

「expire数据结构」

「过期策略」

「内存淘汰策略」

做分布式锁（Redis）

做乐观锁（Redis）