Redis-数据结构
2021-08-23 17:51:53 0 举报AI智能生成
登录查看完整内容
Redis-数据结构
作者其他创作
大纲/内容
Redis数据结构
简介
Redis是一个Key-Value的存储系统，使用ANSI C语言编写
Key是字符串，value的数据类型有
常见
String、List、Set、SortedSet、Hash
不常见
Bitmap、Geo
v5.0新增
Stream
Redis中命令忽略大小写，但是key不忽略大小写
key设计
1. 用 ： 分割
2. 把表名转换为key前缀
3. 第二段放置主键值
4. 第三段放置列名
类型
String字符串
Redis的String能表达3种值的类型
字符串、整数、浮点数
常见操作
set
set key value
赋值
get
get key
取值
getset
getset key value
取值并赋值
setnx
setnx key value
当value不存在时赋值
append
append key value
向尾部追加值
strlen
strlen key
获取字符串长度
incr
incr key
递增数字
incrby
incrby key increment
增加指定的整数
decr
decr key
递减数字
decrby
decrby key decrement
减少指定的整数
应用场景
1. key/value是字符串
2. 普通的赋值
3. incr用于乐观锁
用于实现乐观锁watch
4. setnx用于分布式锁
List列表
可以存储有序、可重复的元素，个数最多为2^32-1个
获取头部或尾部附近的记录是极快的
lpush
lpush key v1 v2 v3....
从左侧插入列表
lpop
lpop key
从左侧取出
rpush
rpush key v1 v2 v3.....
从右侧插入列表
rpop
rpop key
从右侧取出
lpushx
lpushx key value
将值插入到列表头部
rpushx
rpushx key value
将值插入到列表尾部
blpop
blpop key timeout
从左侧取出，当列表为空时阻塞，可以设置最大阻塞时间（s）
brpop
brpop key timeout
从右侧取出，当列表为空时阻塞，可以设置最大阻塞时间（s）
llen
llen key
获取列表中元素个数
lindex
lindex key index
获取列表中下表为index的元素，从0开始
lrange
lrange key start end
返回列表中指定区间的元素
lrem
lrem key count value
删除列表中与value相等的元素
count 0
从列表左侧开始删除
从列表右侧开始删除
count = 0
删除所有值为value的元素
lset
lset key index value
将列表index位置的元素设为value值
ltrim
ltrim key start end
对列表进行修剪，只保留start-end区间
rpoplpush
rpoplpush key1 key2
从key1列表右侧弹出并插入到key2列表左侧
brpoplpush
brpoplpush key1 key2
从key1列表右侧弹出并插入到key2列表左侧，会阻塞
linsert
linsert key BEFORE/AFTER pivot value
将value插入到列表，且位于值pivot之前或之后
1. 作为栈或队列使用
2. 可用于各种列表
Set集合
无序、唯一元素，集合中最大的成员数为2^32-1
sadd
sadd key mem1 mem2
为集合添加新成员
srem
srem key mem1 mem2
删除集合中指定成员
smembers
smembers key
获得集合中所有元素
spop
spop key
返回集合中一个随机元素，并将该元素删除
srandmember
srandmember key
返回集合中一个随机元素，不会删除该元素
scard
scard key
获取集合中元素的数量
sismember
sismember key member
判断元素是否在集合内
sinter
sinter key1 key2 key3
求多集合的交集
sdiff
sdiff key1 key2 key3
求多集合的差集
sunion
sunion key1 key2 key3
求多集合的并集
适用于不能重复且不需要顺序的数据结构
SortedSet有序集合
元素本身是无序不重复的，每个元素关联一个分数，可按分数排序，分数可重复
zadd
zadd key score1 member1 score2 member2 .....
为有序集合添加新成员
zrem
zrem key mem1 mem2
删除有序集合中指定成员
zcard
zcard key
获得有序集合中的元素数量
zcount
zcount key min max
zincrby
zincrby key increment member
在集合的member分值上加increment
zscore
zscore key member
获得集合中member的分值
zrank
zrank key member
获得集合中member的排名（按分值从小到大）
zrevrank
zrevrank key member
获得集合中member的排名（按分值从大到小）
zrange
zrange key start end
获得集合中指定区间成员，按分数递增排序
zrevrange
zrevrange key start end
获得集合中指定区间成员，按分数递减排序
由于可以按照分值排序，所以适用于各种排行榜
Hash散列表
Redis_Hash是一个String类型的field和value的映射表，它提供了字段和字段值的映射，每个hash可以存储2^32-1键值对
hset
hset key field value
赋值，不区别新增或修改
hmset
hmset field1 value1 field2 value2....
批量赋值
hsetnx
hsetnx key field value
赋值，如果field存在则不操作
hexists
hexists key field
查看某个field是否存在
hget
hget key field
获取一个字段值
hmget
hmget key field1 field2.....
获取多个字段值
hgetall
hgetall key
获取所有字段值
hdel
hdel key field1 field2 ....
删除指定字段
hincrby
hincrby key field increment
指定字段自增increment
hlen
hlen key
获得字段数量
对象的存储，表数据的映射
Bitmap位图
用于进行位操作，通过一个bit位来表示某个元素对应的值或状态，其中key就是对应元素本身
Bitmap本身会极大的节省存储空间
setbit
setbit key offset value
设置key在offset处的bit值（0/1）
getbit
getbit key offset
获取key在offset处的bit值
bitcount
bitcount key
获得key的bit位为1的个数
bitpos
bitpos key value
返回第一个被设置为bit值的索引值
bitop
bitop [and/or/xor/not] destkey key [key......]
对多个key进行逻辑运算后存入destkey中
1. 用户每月签到，用户id为key，日期作为偏移量，1表示签到
2. 统计活跃用户，日期为key，用户id为偏移量，1表示活跃
3. 查询用户在线状态，日期为key，用户id为偏移量，1表示在线
Geo地理位置
geo是Redis用来处理位置信息的，在Redis3.2中正式使用，主要是利用了Z阶曲线、Base32编码和gethash算法
概念
Z阶曲线
在X轴和Y轴上将十进制数转化为二进制数，采用X轴和Y轴对应的二进制数依次交叉后得到一个六位数编码，把数字从小到大依次连接起来的曲线称为Z阶曲线，是一种把多维转换成一维的方法
Base32编码
主要用来把二进制数据编码成可见的字符串
编码规则
任意给定一个二进制数，以5个位（bit）为一组进行切分，对切分而成的每个组进行编码得到一个字符
Geohash算法
是一种地理位置信息编码方法，经过Geohash映射后，地球上任意位置的经纬度坐标可以表示成一个较短的字符串，可以方便的存储在数据库中，附在邮件上，以及方便的使用在其他服务中
Redis中经纬度使用52位的整数进行编码，放入zset中，在使用Redis进行Geo查询时，其内部对应的操作只是zset的操作
通过zset的score进行排序就可以得到坐标附近的其他元素
通过将score还原成坐标值就可以得到元素的原始坐标
常用操作
geoadd
geoadd key 经度 纬度 成员名称1 经度1 纬度1 成员名称2 经度2 纬度2 ....
添加地理坐标
geohash
geohash key 成员名称1 成员名称2....
返回标准的geohash串
geopos
geopos key 成员名称1 成员名称2 ....
返回成员经纬度
geodist
geodist key 成员1 成员2 单位
计算成员间距离
georadiusbymember
georadiusbymember key 成员 值单位 count 数 asc/desc
根据成员查找附近的成员
1. 记录地理位置
2. 计算距离
3. 查找“附近的人”
Stream数据流
Redis5.0后新增的数据结构，用于可持久化的消息队列
它几乎满足了消息队列具备的全部内容
消息ID的序列化生成
消息遍历
消息阻塞和非阻塞读取
消息的分组消费
未完成消息的处理
消息队列监控
每个Stream都有唯一的名称，就是Redis的key，首次使用xadd指令追加消息时自动创建
xadd
xadd key id field1 field2 ....
将指定消息数据追加到指定队列（key）中，*表示最新生成的id（当前时间+序列号）
xread
xread [Count count] [BLOCK milliseconds] STREAMS key [key ....] ID [ID ....]
从消息队列中读取
Count：读取条数
BLOCK：阻塞读（默认不阻塞）
key：队列名称
id：消息id
xrevrange
xrange key start end [COUNT]
读取队列中给定ID范围的消息COUNT：返回消息条数（id从小到大）
xdel
xdel key id
删除队列的消息
xgroup
xgroup create key groupname id
创建一个新的消费组
xgroup destroy key groupname
删除指定消费组
xgroup delconsumer key groupname cname
删除指定消费组中的某个消费者
xgroup setid key id
修改指定消息的最大id
xreadgroup
xreadgroup group groupname consumer COUNT streams key
从队列中的消费组中创建消费者并消费数据（consumer不存在则创建）
消息队列
底层数据结构
结构
实例
DB(RedisDB)
Key
Value(RedisObject)
String
List
Map(hash)
Set
Sorted-Set
Redis没有表的概念，Redis实例所对应的db以编号区分，db本身就是Key的命名空间
RedisDB
Redis中存在数据库概念，该结构由redis.h中的redisDb定义
redis服务器初始化时，会预先分配16个数据库，所有数据库保存到结构redisServer的一个成员redisServer.db数组中
redisClient中存在一个名叫db的指针指向当前使用的数据库
redisDb
id：数据库库号，为0-15
dict：存储数据库所有的key-value
expires：存储key的过期时间
RedisObject
是一个对象，包含字符串对象，列表对象，哈希对象，集合对象和有序集合对象
type(4位)
表示对象的类型，占4位
REDIS_STRING、REDIS_LIST、REDIS_HASH、REDIS_SET、REDIS_ZSET
执行type命令时，就是通过读取RedisObject的type字段获得对象的类型
encoding(4位)
表示对象的内部编码，占4位
每个对象有不同的实现编码，Redis可以跟不同不同的使用场景来为对象设置不同的编码，大大提高了Redis的灵活性和效率
通过object encoding命令，可以查看对象采用的编码方式
LRU(24位)
记录的是对象最后一次被命令程序访问的时间（v4.0占24位，v2.6占22位）
高16位存储一个分钟数级别的时间戳，低8位存储访问计数
refcount
记录的是该对象被引用的次数，类型为整型
主要用于对象的引用次数和内存回收
refcount1，称为共享对象
Redis为了节省内存，当有一些对象重复出现时，新的程序不会创建新对象，而是仍然使用原来的对象
ptr
指向具体的数据
Type
字符串对象
Redis使用SDS(Simple_Dynamic_String)，用于存储字符串和整型数据
优势
1. SDS在C字符串基础上加入了free和len字段，获取字符串长度：SDS是O(1)，C字符串是O(n)
2. SDS由于记录了长度，在可能造成缓冲区溢出时会自动重新分配内存，杜绝了缓存区溢出
3. 可以存取二进制数据，以字符串长度len来作为结束标识
场景
主要用于存储字符串和整型数据、存储key、AOF缓冲区和用户输入缓冲
跳跃表
它是有序集合的底层实现，效率高，实现简单
基本思想
将有序链表中的部分节点分层，每一层都是一个有序链表
查找
查找时优先从最高层开始向后查找，当到达某个节点时，如果next节点值大于要查找的值或next指针指向null，则从当前节点下降一层继续向后查找
插入
通过抛硬币（概率1/2）的方式来决定新插入节点跨越的层数
正面：插入上层
背面：不插入
删除
找到指定元素并删除每层的改元素即可
特点
每层都是一个有序链表，查找次数近似于层数
底层包含所有元素
空间复杂度O(n)扩充了一倍
1. 可以快速查找到需要的节点
2. 可以在O(1)的时间复杂度下，快速获得跳跃表的头节点、尾节点、长度和高度
有序集合的实现
字典
字典dict又称散列表（hash），是用来存储键值对的一种数据结构
Redis整个数据库使用字典来存储的
对Redis进行CRUD操作其实就是对字典中的数据进行CRUD操作
数组
用来存储数据的容器，采用头指针+偏移量的方式能够以O(1)的时间复杂度定位到数据所在的内存地址
Hash函数
作用是把任意长度的输入通过散列算法转换成固定类型、固定长度的散列值
Hash函数可以把Redis里的key：包括字符串、整数、浮点数统一转换成整数
数组下标
= hash(key) % 数组容量 （hash值 % 数组容量得到的余数）
hash冲突
不同的key经过计算后出现数组下标一致，称为Hash冲突
采用单链表在相同的下标位置处存储原始Key/Value
当根据Key查找Value时，找到数组下标，遍历单链表可以找出Key相同的value
实现
包括字典(dict)、Hash表(dictht)、Hash表节点（dictEntity）
Dict字典
type字段指向dictType结构体，里边包括了对该字典操作的函数指针，是为了实现各种形态的字典而抽象出来的操作函数（多态）
Redis字典除了主数据库的K-V数据存储之外，还可以用于：散列表对象、哨兵模式中的主从节点管理等，不同应用中，字典的形态都可能不同
Hash表
1. hash表的数组初始容量为4，随着k-v存储量的增加需要对hash表数组进行扩容，新扩容量为当前量的一倍
2. 索引值 = Hash值 & 掩码值（Hash值与Hash表容量取余）
Hash表节点
Key字段存储的是键值对中的键
v字段是个联合体，存储的是键值对中的值
next指向下一个哈希表节点，用于解决hash冲突
扩容
字典达到存储上限，需要rehash（扩容）
流程
申请新内存 - 地址赋给h[1] - rehashidx=0 - h[1]=h[0]（索引重新计算）
说明
1. 初次申请默认容量为4个dictEntry，非初次申请为当前hash表容量的一倍
2. rehashidx=0标识要进行rehash操作
3. 新增加的数据在新的hash表h[1]
4. 修改、删除、查询在老hash表h[0]、新hash表h[1]中（rehash中）
5. 将老的hash表h[0]的数据重新计算索引值后全部迁移到新的hash表h[1]中，这个过程称为rehash
渐进式rehash
当数据量巨大时rehash的过程是非常缓慢的，所以需要进行优化
服务器忙则只对一个节点进行rehash，闲时可批量rehash（100节点）
1. 主数据库的K-V数据存储
2. 散列表对象（hash）
3. 哨兵模式中的主从节点管理
压缩列表
ziplist是由一系列特殊编码的连续内存块组成的顺序型数据结构
是一个字节数组，可以包含多个节点（entry），每个节点可以保存一个字节数组或一个整数
数据结构
zlbytes：压缩列表的字节长度
zltail：压缩列表为元素相对于压缩列表起使地址的偏移量
zllen：压缩列表的元素个数
entry1.....entryX：压缩列表的各个节点
zlend：压缩列表的结尾，占一个字节，恒为0xFF
entryX编码结构
previous_entry_length：前一个元素的字节长度
encoding：表示当前元素的编码
content：数据内容
直接使用
sorted-set和hash元素个数少且是小整数或短字符串
间接使用
list用快速链表数据结构存储，而快速链表是双向列表和压缩列表的组合
整数集合
intset是一个有序的（整数升序）、存储整数的连续存储结构
当Redis集合类型的元素都是整数并且都处在64位有符号整数范围内（2^64），使用该结构体存储
可以保存类型为int16_t、int32_t或int64_t的整数值，并且保证集合中不会出现重复元素
快速列表
quicklist是Redis底层重要的数据结构，是列表的底层实现
Redis3.2之前，Redis采用双向链表（adlist）和压缩列表（ziplist）实现，Redis3.2以后结合两者的优势设计出了quicklist
双向列表
1. 双向：链表具有前置节点和后置节点的引用，获取这两个节点时间复杂度都是O(1)
2. 普通链表(单链表)：节点类保留下一节点的引用，链表类只保留头节点的引用，只能从头节点插入删除
3. 无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问都是以NULL结束
4. 带链表长度计数器：通过len属性获取链表长度的时间复杂度为O(1)
5. 多态：链表节点使用void*指针来保存节点值，可以保存各种不同类型的值
是一个双向链表，链表中每个节点都是一个ziplist结构（每个节点都能够存储多个数据元素）
数据压缩
quicklit每个节点的实际数据存储结构为ziplist，这种结构优势在于节省存储空间
为了进一步降低ziplist的存储空间，还可以对ziplist进行压缩
Redis采用的压缩算法是LZF，其基本思想是：数据与前面重复的记录重复位置及长度，不重复的记录原始数据
压缩过的数据可以分为多个片段，每个片段有：解释字段和数据字段
列表的底层实现、发布与订阅、慢查询、监视器等功能
流对象
stream主要由：消息、生产者、消费者和消费组构成
Redis Strean底层主要使用了listpack(紧凑列表)和Rax树(基数树)
listpack
表示一个字符串列表的序列化，可用于存储字符串或整数，用于存储stream的消息内容
Rax树
是一个有序字典树，按照key的字典排序，支持快速定义、插入和删除操作
被用在Redis_Stream结构内存储消息队列，在Stream里面消息ID的前缀是时间戳+序号，这样的消息可以理解为时间序列消息
使用Rax结构进行存储就可以快速地根据消息ID定位到具体的消息，然后继续遍历指定消息后的所有消息
stream的底层实现
encoding
Redis通过encoding属性为对象设置不同的编码
对于少而小的数据，Redis采用小的和压缩的存储方式，体现了Redis的灵活性，大大提高了Redis的存储量和执行效率
int
REDIS_ENCODING_INT
RAW
REDIS_ENCODING_RAW
简单动态字符串
大字符串，长度大于44字节
embstr
REDIS_ENCODING_EMBSTR
编码的简单动态字符串
小字符串，长度小于44字节
list
quicklist
REDIS_ENCODING_QUICKLIST
hash
dict
REDIS_ENCODING_HT
当散列表元素的个数较多或元素不是小整数或短字符串时
ziplist
REDIS_ENCODING_ZIPLIST
当散列表元素的个数比较少，且元素都是小整数或短字符串时
intset
REDIS_ENCODING_INTSET
当Redis集合类型元素都是整数且都处于64位有符号整数范围内
当Redis集合类型元素都是整数且都处于64位有符号整数外
zset
当元素个数较少，且元素都是小整数或短字符串时
skiplist + dict
REDIS_ENCODING_SKIPLIST
当元素个数较多或元素不是小整数或短字符串时
缓存过期/淘汰策略
Redis长期使用，key不断增加，Redis作为缓存使用，物理内存会占满，内存开始与硬盘交换（swap），频繁IO下性能急剧下降
解决
maxmemory
不设置的场景
Redis的key是固定的，不会增加
Redis作为DB使用，保证数据完整性，不能淘汰，可以做集群，横向扩展
缓存淘汰策略：禁止驱逐（默认）
设置的场景
Redis作为缓存使用，不断增加Key
maxmemory默认为0，不限制，造成：超过物理内存后性能急剧下降，甚至崩溃
一个Redis实例，保证系统运行1G，剩下的就都可以设置Redis
一般来说物理内存的3/4
设置后，当趋近maxmemory时，通过缓存淘汰策略，从内存中删除对象
设置
redis.conf
maxmemory 1024mb
shell
CONFIG GET maxmemory
expire
Redis中可以使用expire命令设置一个键的存活时间，过了这段时间，改键就会自动被删除
命令
expire key ttl （单位：s）
设置失效时间
ttl key
查看剩余失效时间，-2表示失效
原理
redisDb结构体定义了一个expires字典，用于维护一个Redis数据库中设置了失效时间的键
当使用expire命令设置key的失效时间时，Redis首先到dict字典表中查找要设置的key是否存在，如果存在则添加对应映射到expires
使用setex命令插入数据时，Redis首先将key/value添加到dict字典表中，然后将key/expire添加到expires中
删除策略
Redis数据删除有定时删除、惰性删除和主动删除三种，目前采用惰性+主动的方式
定时删除
在设置键的过期时间同时，创建一个定时器，让定时器在键过期时间来临时，立即执行对键的删除操作
需要创建定时器，且消耗CPU，一般不推荐
惰性删除
在key被访问时，如果发现它已经失效，则删除它
主动删除
redis.conf可以配置主动删除策略，默认是no-enviction（不删除）
maxmemory-policy allkeys-lru
LRU (Least Recently used)
最近最少使用算法，根据数据的历史访问记录来进行淘汰数据
核心思想
如果数据最近被访问过，那么将来被访问的几率也更高
最常见的实现是使用一个链表保存缓存数据
1. 新数据插入到链表头部
2. 每当缓存命中（缓存数据被访问），则将数据移到链表头部
3. 当链表满时，将链表尾部的数据丢弃
4. 在Java中可以用LinkHashMap实现
Redis的LRU
在服务器配置中保存了LRU计数器server.lrulock，会定时更新，该值根据server.unixtime计算出来
另外，每一个redis对象都会设置相应的lru，每次访问数据时，会更新redisObject.lru
淘汰机制
在数据集中随机挑选几个键值对，取出其中lru最大的键值对淘汰
不会遍历key
两种策略
volatile-lru
从已设置过期时间的数据集中挑选最近最少使用的数据淘汰
allkeys-lru
从数据集中挑选最近最少使用的数据淘汰
LFU (Least frequently used)
最不经常使用，如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小
volatile-lfu
allkeys-lfu
Random
策略
volatile-random
从已设置过期时间的数据集中任意选择数据淘汰
allkeys-random
从数据集中任意选择数据淘汰
ttl
从过期时间表中随机挑选几个键值对，取出其中ttl最小的键值对淘汰
volatile-ttl
从已设置过期时间的数据集中挑选将要过期的数据淘汰
noenviction
禁止驱逐数据，默认
策略选择
在不确定时一般采用的策略
比allkeys-lru性能差
希望请求符合平均分布
自己控制，防止缓存穿透
redis
0 条评论
回复 删除
下一页
