redis图谱

作者: ytl_china | 来源:发表于2020-02-25 16:25 被阅读0次

redis 是什么？

redis(Remote Dictionary Service) 远程字典服务。
Redis 所有的数据结构都是以唯一的 key字符串作为名称，然后通过这个唯一 key 值来获取相应的 value 数据。不同类型的数据结构的差异就在于 value 的结构不一样。

redis 数据结构

String
redis中的字符串为动态字符串(Simple Dynamic String)，内部结构上实现类似java中的ArrayList。扩容机制为：当前实际分配的空间大于实际字符串长度，字符串长度小于1M时，采用翻倍扩容。大于1M时，每次只会多扩1M,直至最大长度512M。
value为整数时，最大最小值范围和java中long类型一致（int long 占8字节，每字节占8bit）。即-2^63 ~ 2^63-1(第一位为符号位)。

struct SDS<T> {
T capacity; // 数组容量
T len; // 数组长度
byte flags; // 特殊标识位，不理睬它
byte[] content; // 数组内容
}

redis字符串有两种存储方式，emb和raw，当长度大于44时，使用raw存储，通过debug object 可以看到：

10.130.216.126:6379> set name asdfasdfdsafsdafsdafdsfsdafdsafdsafdsafdsjakflfdsahflkdsafhdksjfaslfsfks
OK
10.130.216.126:6379> debug name
(error) ERR Unknown DEBUG subcommand or wrong number of arguments for 'name'
10.130.216.126:6379> debug object name
Value at:0x7f1cb294a380 refcount:1 encoding:raw serializedlength:61 lru:5555757 lru_seconds_idle:16
10.130.216.126:6379> set name asd
OK
10.130.216.126:6379> debug object name
Value at:0x7f1cb29b7d20 refcount:1 encoding:embstr serializedlength:4 lru:5555800 lru_seconds_idle:2
10.130.216.126:6379>

超过44存储形式就发生了改变，这个是怎么做到的呢？源头在于Redis对象头结构体，所有的redis头结构体为：

struct RedisObject {
int4 type; // 4bits 不同的对象有不同的类型
int4 encoding; // 4bits 同一type会有不同的存储方式
int24 lru; // 24bits 24bit的LRU即毫秒时间戳
int32 refcount; // 4bytes 对象引用计数器，数值为0时，对象被销毁，内存回收
void *ptr; // 8bytes，64-bit system ptr指针指向对象内容的具体存储位置，所以一个redis对象头要占据16字节的存储空间。
} robj;

image.png

由上图可知：内存分配器分配的最小单位2,4,8,16,32,64，为了容纳embstr只能分配64字节内存，除去redisObject的16字节，SDS中的最少三个字节，还剩余45个字节，content中字符串为了使用第三方库glibc字符串处理函数，字符串需以\0字节结尾。

Hash
redis中的hash相当于java中的HashMap。是无序字典，内部实现基本一致，数组+链表二维结构。一维产生hash碰撞时，转为链表（jdk8红黑树此处不详述）。
redis中不同的地方在于redis的value只能是字符串；rehash时采用渐进式rehash策略，避免java中一次性全部rehash,采用同时存在多个hash结构，查询时同时查询，后续定时任务及hash子指令中渐进式将旧的hash内容迁移到新的hash中。
Hash和String存储的区别在于对象是否一次性读取。合理的使用相应的结构。hash结构的存储消耗要多于String。

rehash
内部实现--字典
字典是redis中使用频繁的复合型数据结构，除了hash外，过期字典，zset中value和score的对应关系也是通过dict实现的。
dict 结构内部包含两个 hashtable，通常情况下只有一个 hashtable 是有值的。但是在
dict 扩容缩容时，需要分配新的 hashtable，然后进行渐进式搬迁，这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后，旧的 hashtable 被删除，新的hashtable 取而代之。
同时为了节约内存使用，hash结构和zset容器结构在元素较少时使用了压缩列表zipList进行存储，是一串连续的存储空间。

struct ziplist<T> {
int32 zlbytes; // 整个压缩列表占用字节数
int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个
节点
int16 zllength; // 元素个数
T[] entries; // 元素内容列表，挨个挨个紧凑存储
int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}

image.png

压缩列表为了支持双向遍历，所以才会有 ztail_offset 这个字段，用来快速定位到最后一
个元素，然后倒着遍历。

List
redis列表相当于java中的LinkedList，插入和删除时间复杂度为O(1),但是相应的查询时间复杂度O(n)。当列表弹出了最后一个元素之后，该数据结构自动被删除，内存被回收。Redis 的列表结构常用来做异步队列使用。
List底层结构使用的是quicklist(快速列表)。 quicklist将多个ziplist(压缩列表)使用双向指针串起来使用。所以当数据量比较小时，它会将所有元素紧挨在一起存储放入一个ziplist中。

快速列表

Set
redis集合相当于java中的HashSet，内部的键值对是无序的唯一的。内部实现相当于一个特殊的Hash，Hash中所有的value都是null。

ZSet
redis有序集合，类似java中的SortedSet和HashMap的组合，一方面内部value唯一，又可以给每个value赋予score权重。内部实现使用跳跃列表的数据结构。
跳表数据结构特殊且复杂，因为zset要支持随机的写入及删除。内部实现类似使用了层级制的机制。跳表之所以跳跃，就是因为内部元素可能身兼数职。跳表采取一个随机策略来决定新元素可以兼职到第几层。首先 L0 层肯定是 100% 了，L1 层只有 50% 的概率，L2 层只有 25% 的概率，L3层只有 12.5% 的概率，一直随机到最顶层 L31 层。绝大多数元素都过不了几层，只有极少数元素可以深入到顶层。列表中的元素越多，能够深入的层次就越深，能进入到顶层的概率就会越大。

image.png

image.png

容器型数据结构的通用规则

list/set/hash/zset 这四种数据结构是容器型数据结构，它们共享下面两条通用规则：
1 、create if not exists
如果容器不存在，那就创建一个，再进行操作。比如 rpush 操作刚开始是没有列表的，
Redis 就会自动创建一个，然后再 rpush 进去新元素。
2 、drop if no elements
如果容器里元素没有了，那么立即删除元素，释放内存。这意味着 lpop 操作到最后一
个元素，列表就消失了。
过期时间
Redis 所有的数据结构都可以设置过期时间，时间到了，Redis 会自动删除相应的对象。
需要注意的是过期是以对象为单位，比如一个 hash 结构的过期是整个 hash 对象的过期，
而不是其中的某个子 key。

三种变种数据结构

bitMap
位图不是特殊的数据结构，它的内容其实就是普通的字符串，也就是 byte 数组。Redis从2.2.0版本开始新增了setbit,getbit,bitcount等几个bitmap相关命令。虽然是新命令，但是并没有新增新的数据类型，因为setbit等命令只不过是在set上的扩展。如果想批量设置值，必须使用管道或者在3.2之后使用魔术指令 bitfield，bitfield 有三个子指令，分别是get/set/incrby，它们都可以对指定位片段进行读写，但是最多只能处理 64 个连续的位，如果超过 64 位，就得使用多个子指令，bitfield 可以一次执行多个子指令。
Redis 提供了位图统计指令 bitcount 和位图查找指令 bitpos，bitcount 用来统计指定位
置范围内 1 的个数，bitpos 用来查找指定范围内出现的第一个 0 或 1。
$\color{red}{PS}$ :bitcount指令支持范围查找，但是这个范围是指字节索引，如果需要查询某一段需要将所有字节取出，自行进行内存运算，繁琐。

HyperLogLog
这是个不常用的数据结构，HyperLogLog 提供不精确的去重计数方案，虽然不精确但是也不是非常不精确，标准误差是 0.81%。场景一般用于统计UV去重上。它需要占据一定 12k 的存储空间。在计数比较小时，它的存储空间采用稀疏矩阵存储，空间占用很小，仅仅在计数慢慢变大，稀疏矩阵占用空间渐渐超过了阈值时才会一次性转变成稠密矩阵，才会占用 12k 的空间。

Geo
redis3.2之后增加了地址位置GEO模块，可以通过这个模块来算附件的人，redis的GEO也使用了业界常用的GeoHash算法，将二维的经纬度数据映射到一维的整数，这样所有的节点都在同一线上，距离靠近的二维坐标映射到一维后的点之间距离也会很接近。当我们想要计算「附近的人时」，首先将目标位置映射到这条线上，然后在这个一维的线上获取附近的点就行了。在 Redis 里面，经纬度使用 52 位的整数进行编码，放进了 zset 里面，zset的 value 是元素的 key，score 是 GeoHash 的 52 位整数值。zset 的 score 虽然是浮点数，但是对于 52 位的整数值，它可以无损存储，在使用 Redis 进行 Geo 查询时，我们要时刻想到它的内部结构实际上只是一个zset(skiplist)。通过 zset 的 score 排序就可以得到坐标附近的其它元素。
$\color{red}{PS}$ :Geo内部结构就是一个普通的zset。只有6个指令：geoadd、geodist、geopos、geohash、georadiusbymember、georadius。因为底层就是zset,数据量大时将会影响对主从，集群等相关节点切换，因此一般单独部署，及按相关维度拆分缩小zset的大小。

一个新增数据结构Stream

Stream
Redis5.0新增了一个数据结构Stream,是一个新增的支持多播的可持久化的消息队列，设计理念借鉴了kafka。
redis Stream 是一个消息链表，是所有消息的汇总，每个消息体都有唯一的ID和对应的内容，创建Stream时使用xadd命令，如果没有链表则自动建立新的Stream，类似set的sadd命令。
Stream可以挂载多个消费组，消费组的名称是唯一的，由xgroup_create命令创建。每个消费组都会有自己的游标last_delivered_id用来标识消费到什么位置上了，消费组之间相互独立。
一个消费组下可以挂载多个消费者，消费者在组内名称也是唯一的，消费者之间是竞争关系，即一个消息只能被一个消费者读取，读取后last_delivered_id会往前移动。那Stream如何保证消息可靠性？这里redis官方引入了PEL数据结构(Pending Entries List),用来确保消息至少被消费了一次，而不会在网络环境中丢失。具体实现为：每个消费者都有一个pending_ids状态记录，他记录了当前被客户端读取但是还没有ack的消息，如果客户端没有ack,pending_ids中的消息ID数据会增多，直到某个消息被ack.
消息ID在Stream中的形式为timestampInMillis-sequence,即整数(毫秒时间戳)-整数(第几个消息),此ID可由服务端生成也可由客户端生成。消息对应的消息内容就是键值对，类似于hash。

image.png

$\color{red}{Q}$ : Stream必须定义消费组吗？
$\color{red}{A}$ : 非必要，Stream提供了单独消费的指令:xread.
$\color{red}{Q}$ : Stream是否有大小控制？
$\color{red}{A}$ : 有，Stream提供了一个定长的Stream,确保不超过此长度，暂未提供根据时间戳删除的方案
$\color{red}{Q}$ : 消费方忘记ACK怎样？
$\color{red}{A}$ :PEL列表会一直增长，占用内存增加
$\color{red}{Q}$ : 消费方忘记ACK怎样？
$\color{red}{A}$ :PEL列表会一直增长，占用内存增加
$\color{red}{Q}$ : Stream 和kafka的区别？
$\color{red}{A}$ :Stream借鉴了kafka的消费分组的概念，但不同的是没有引入分Partition，但可以建立多个Stream,客户端用策略来分配Stream.可以达到kafka的HashStrategy同样的功能。

redis 有什么用途？

分布式锁
为何要引入分布式锁？并发的根源？
并发的根源起于硬件工程师增加CPU缓存在多核场景下导致的。此文不详述。详见
https://www.jianshu.com/p/dbb2eeac46bc

redis分布式相关实现方案

# 一般使用 setnx(set if not exists) 指令，只允许被一个客户端占坑，用完了用del释放。
setnx 
#防止死锁需要加过期时间
expire 
# 事务不能使用，expire依赖于setnx的结果，要么全执行成功，要么全失败，无if else 
分支.故redis 2.8以后复杂的set可以setnx和expire可以原子性执行
set lock nx ... ex ... 
# 超时问题 
set 指令的value指定随机数，删除的时候匹配value后再进行删除但是这不是原子操作，最终引入lua脚本，借助redis.eval(script)指令进行原子性操作。

可重入性
可重入性是指线程在持有锁的情况下再次请求加锁，如果一个锁支持同一个线程的多次加
锁，那么这个锁就是可重入的。 java中的ReentrantLock 就是可重入锁
如果要支持可重入性需要对set进行包装，用threadLocal 变量存储当前持有锁的计数。
客户端分布式锁加锁失败的处理方案：

直接抛异常，通知用户重试，适用于C端流量，将重试控制交由外部控制（客户或前端代码）。
2.休眠在重试,sleep一般不常用，多使用spring retry机制，进行休眠重试，多次失败后进入延时队列或异常处理。
3.将请求放入延时队列重试,适用于异步消息处理。

消息队列
Redis 的 list(列表) 数据结构常用来作为异步消息队列使用，使用rpush/lpush操作入队列，使用 lpop 和 rpop 来出队列。

空队列问题
客户端对空队列处理，空轮询会给客户端和redis带来压力,一般是采用客户端休眠来解决空队列问题。
队列延迟问题
休眠会带来延迟问题，所以redis提供了brpop/blpop阻塞读，空队列则进入休眠状态，等待数据唤醒。 $\color{red}{**}$ 需要注意的是客户端在使用brpop/blpop需要进行容错，即捕获超时异常重试，因连接不释放会导致成为闲置连接，服务器会进行主动断开 $\color{red}{**}$ 。
延时队列的实现
使用zset有序集合实现，将时间戳作为score，使用zrangebyscore 和 zrem来进行相应操作，为保证原子性使用lua脚本来将两者进行原子性提交。
$\color{red}{Q}$ : Redis 作为消息队列为什么不能保证 100% 的可靠性？
$\color{red}{A}$ : 客户端没有ack机制，无法保证消息一定被消费。

布隆过滤器
布隆过滤器可以理解为一个不怎么精确的 set 结构，当你使用它的 contains 方法判断某
个对象是否存在时，它可能会误判。但是布隆过滤器也不是特别不精确，只要参数设置的合
理，它的精确度可以控制的相对足够精确，只会有小小的误判概率。
当布隆过滤器说某个值存在时，这个值可能不存在；当它说不存在时，那就肯定不存
在。打个比方，当它说不认识你时，肯定就不认识；当它说见过你时，可能根本就没见过
面，不过因为你的脸跟它认识的人中某脸比较相似 (某些熟脸的系数组合)，所以误判以前见
过你。

限流

简单限流
简单限流是利用zset的score，通过滑动时间窗口来实现，每一次行为的发生都要维护一次时间窗口，将时间窗口外的记录全部清掉，只保留窗口内的记录。
令牌桶限流（漏斗限流）
Redis 4.0 提供了一个限流 Redis 模块，它叫 redis-cell。该模块也使用了漏斗算法，并
提供了原子的限流指令 cl.throttle。

Redis过期策略

定时删除和惰性删除
redis会将设置了过期时间的key放到一个独立的字典中，定时扫描字典来删除到期的key。除此之外，惰性删除即客户端访问过期的key时，立即删除key。
定时扫描策略
贪心算法：1.在过期字典中随机20个key；2.删除其中过期的key；3.如果过期key比例超过1/4.则重复步骤1。所以这也是为何开发人员要避免同一时间大批量的key过期避免循环多次，虽然扫描有时间上限25ms,但是多个指令同时到达就会出现问题。
需要说明的是从库的删除策略和主库是不一样的。从库对过期的处理都是被动的。主库到期后会在AOF中增加一条del指令，同步所有从库，从库根据指令删除过期的key。这也是分布式锁主从切换造成的锁失效的问题根源。

LRU
redis当出现交换内存swap操作时，提供了几种LRU策略。

noeviction 不会继续服务写请求 (DEL 请求可以继续服务)，读请求可以继续进行。这样
可以保证不会丢失数据，但是会让线上的业务不能持续进行。这是默认的淘汰策略。
 volatile-lru 尝试淘汰设置了过期时间的 key，最少使用的 key 优先被淘汰。没有设置过
期时间的 key 不会被淘汰，这样可以保证需要持久化的数据不会突然丢失。
 volatile-ttl 跟上面一样，除了淘汰的策略不是 LRU，而是 key 的剩余寿命 ttl 的值，ttl
越小越优先被淘汰。
 volatile-random 跟上面一样，不过淘汰的 key 是过期 key 集合中随机的 key。
 allkeys-lru 区别于 volatile-lru，这个策略要淘汰的 key 对象是全体的 key 集合，而不
只是过期的 key 集合。这意味着没有设置过期时间的 key 也会被淘汰。
 allkeys-random 跟上面一样，不过淘汰的策略是随机的 key。
 volatile-xxx 策略只会针对带过期时间的 key 进行淘汰，allkeys-xxx 策略会对所有的
key 进行淘汰。如果你只是拿 Redis 做缓存，那应该使用 allkeys-xxx，客户端写缓存时
不必携带过期时间。如果你还想同时使用 Redis 的持久化功能，那就使用 volatile-xxx
策略，这样可以保留没有设置过期时间的 key，它们是永久的 key 不会被 LRU 算法淘
汰。
LRU算法
除了过期字典外，需要附加一个顺序链表，当空间满时删除链表尾部元素，当字典某元素被访问后则会移到头部。Redis中使用的类似LRU算法，LRU的缺点在于对数据结构进行较大的改造。redis给每个key增加了额外的24bit字段-最后一次访问的时间戳。具体步骤为：1.当redis写操作时，发现内存超过maxmemory,就会执行一次LRU淘汰算法，随机出5个key，淘汰掉最旧的key，如果内存还是超出则重复随机取样。随机取样的样本取决于配置的淘汰策略。

Redis持久化
Redis 的持久化机制有两种，第一种是快照RDB，第二种是 AOF 日志。快照是一次全量备份，AOF 日志是连续的增量备份。快照是内存数据的二进制序列化形式，在存储上非常紧凑，而 AOF 日志记录的是内存数据修改的指令记录文本。AOF 日志在长期的运行过程中会变的无比庞大，数据库重启时需要加载 AOF 日志进行指令重放，这个时间就会无比漫长。所以需要定期进行 AOF 重写，给 AOF 日志进行瘦身。
redis持久化采用的操作系统的多进程COW(Copy on Write),会调用 glibc 的函数 fork 产生一个子进程，快照持久化完全交给子进程来处理，父进程继续处理客户端请求。
操作系统的 COW 机制来进行数据段页面的分离。数据段是由很多操作系统的页面组合而成，当父进程对其中一个页面的数据进行修改时，会将被共享的页面复制一份分离出来，然后对这个复制的页面进行修改。这时子进程相应的页面是没有变化的，还是进程产生时那一瞬间的数据。随着父进程修改操作的持续进行，越来越多的共享页面被分离出来，内存就会持续增长。但是也不会超过原有数据内存的 2 倍大小。另外一个 Redis 实例里冷数据占的比例往往是比较高的，所以很少会出现所有的页面都会被分离，被分离的往往只有其中一部分页面。每个页面的大小只有 4K，一个 Redis 实例里面一般都会有成千上万的页面。子进程因为数据没有变化，它能看到的内存里的数据在进程产生的一瞬间就凝固了，再也不会改变，这也是为什么 Redis 的持久化叫「快照」的原因。接下来子进程可以非常安心的遍历数据了进行序列化写磁盘了。
AOF 重写
Redis 提供了 bgrewriteaof 指令用于对 AOF 日志进行瘦身。其原理就是开辟一个子进
程对内存进行遍历转换成一系列 Redis 的操作指令，序列化到一个新的 AOF 日志文件中。
序列化完毕后再将操作期间发生的增量 AOF 日志追加到这个新的 AOF 日志文件中，追加
完毕后就立即替代旧的 AOF 日志文件了，瘦身工作就完成了。

redis为何那么快？
redis是单线程程序，形同单线程程序多路复用的典范nodejs，nginx。它的运算都是内存级别的运算，使用非阻塞IO。在java中事件轮询 API就是NIO

redis图谱

redis 是什么？

redis 数据结构

容器型数据结构的通用规则

三种变种数据结构

一个新增数据结构Stream

redis 有什么用途？

redis分布式相关实现方案

Redis过期策略

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读