banner
Violet

Violet's Blog

A Web <Developer />. Code_ for Fun.
x
github
bilibili
email

Redis基础&数据结构

简介#

什么是 Redis#

Redis 是内存高速缓存数据库。全称为:Remote Dictionary Server(远程数据服务)。

Redis 由 c 语言编写,key-value 存储系统,支持 string、list、set、zset、hash 物种数据类型。

Redis 可用于缓存、事件发布或订阅、高速队列等场景。基于内存,可持久化。

Redis 的优势#

  • 读写性能优异
  • 丰富的数据类型
  • 原子性
  • 丰富的特性(发布订阅、通知、过期)
  • 支持持久化(RDB 和 AOF 方式持久化)
  • 分布式

Redis 可以做什么#

  • 数据缓存
  • 限时业务
  • 计数器(incrby)
  • 分布式锁(基于 Redisson 实现分布式锁)
  • 限流(使用 Redis 中的 List 作为消息队列)
  • 消息队列

安装 / 启动#

安装#

Centos8 安装 Redi🔗

启动#

# 在前台启动
redis-server
# 在后台启动
brew services start redis
# 关闭
brew services stop redis

连接#

redis-cli

默认 6379 端口

redis 默认有 16 个数据库,0-15

使用select 1来切换

基础命令#

  • keys *查看当前数据库中有哪些 key(有 16 个数据库)
  • exists key判断这个 key 是否存在
  • type key查看这个 key 的类型
  • del keyunlink key删除某个 key
    • unlink异步删除
  • expire key 10设置 key 过期时间 秒
  • ttl key查看 key 多少秒过期 -1 永不过期 -2 已经过期
  • select切换数据库
  • dbsize查看当前数据库中 key 数量
  • flushdb清除当前数据库所有 key

基础类型(5 种)#

string(字符串)#

  • string 类型是二进制安全的,可以包含任何数据
  • string 是 redis 的基本数据类型,一个 value 最大 512Mb

命令#

  • set <key> <value>
  • get <key>查看
  • append <key> <value>在 key 后追加 value
    • 如果这个 key 不存在,则会创建
  • strlen <key>获取这个 key 对应 value 长度
  • setnx <key> <value>只有当 key 不存在是创建
  • incr <key>这个 key 的 value+1
  • decr <key>value-1
  • incrby/decrby <key> <num>key 的 value 加 num 或者减 num

这些操作是原子性操作,在执行操作期间不会别别的线程打断,因为 redis 是单线程

  • mset <key> <value> <key> <value> <key> <value>一次设置多个 ky
  • mget <key> <key> <key>一次获取多个 key
  • msetnx <key> <value> <key> <value>一次设置多个 当 key 不存在时候
    • 原子性操作 一个失败全部失败
  • getrange <key> <开始> <结束>获取 key 中第 <开始>< 结束 > 中间的所有 value
  • setrange <key> <offset> <value>在 key 中第 offset 之后覆盖设置 value
  • setex <key> <过期时间> <value>在设置 key 时设置过期时间
  • get set <key> <value>取之前的,取完之后再设置新的

数据结构#

Arraylist

使用场景#

  1. 缓存:使用 Redis 作为 MySQL 缓存,降低 MySQL 读写压力
  2. 计数器:Redis 是单线程的优势
  3. session:spring session + redis 实现 session 共享

list(列表)#

单键多值,底层双向链表

命令#

  • lpush/rpush <key> <v1> <v2> <v3>从双向链表左右两边 push 值
  • Large <key> 0 -1编列链表,获取所有
  • rpop/lpop <key>从左右获取并删除值
  • rpoplpush <k1> <k2>从 k1 右边 pop 一个值,在 push 到 k2 左边
  • lindex <key> idnex获取第 index 个值
  • llen <k>获取长度
  • linsert before/after <v1> <v2>在 v1 前 / 后插入 v2
  • lrem <key> <n> <v>从做百年删除 n 个 value
  • lset <k> <idnex> <v>将 index 设置成 v

数据结构#

元素较少的情况下是 ziplist,元素多了之后会将多个 ziplist 组成一个 quicklist

使用场景#

  1. 消息队列

set(集合)#

set 集合中的元素不能重复,底层 hash 表,增删改查都是 O (1) 复杂度

命令#

  • sadd <k> <v1> <v2>添加
  • smamber <k>取出该集合中所有值
  • sismamber <k> <v>判断是否存在这个 value
  • scard <k>返回这个集合长度
  • srem <k> <v> <v>删除
  • spop <k>随机取出并删除一个
  • srandmameber <k> <n>随机取出 n 个,不删除
  • smove <k1> <k2> <v>把 k1 中的 value 取出来,放到 k2 中
  • sinter <k1> <k2>返回 交集
  • sunion <k1> <k2> 返回 并集
  • sdiff <k1> <k2>返回差集

使用场景#

  1. 点赞、转发、收藏等

hash(散列)#

类似于 java 中的 map<string,object>,key 是对象名,value 里边是 fild 和 value

命令#

  • hset <k> <field> <value>设置 key 和 key 中的 field 和 value
  • hget <k> <field> 获取 k 中 field 中的 value
  • hmset <k> <field1> <v1> <field2> <v2>一次设置多个
  • hexists <k1> <field>查看 key 中的 filed 是否存在
  • hkeys <key>获取该 key 的所有 field
  • havals <key>获取该 key 的所有 vlaue,没有 field
  • hincrby <k> <f> <n>给 f 的 value 加 n
  • hsetnx <k> <f> <v>filed 不存在则设置 value

数据结构#

当 field-value 长度短且个数少时使用 ziplist,否则使用 hashtable

使用场景#

  1. 缓存

Zset(有序集合)#

有序集合

每个元素都有评分(score),使用这个 score 来给集合排序,score 可以重复

加权排序 set,类似于 Java 中优先队列,只不过 redis 中将队列更换为 set

命令#

  • zadd <k> <score> <k> <score> <k> <score>添加 key 和 score,会根据 score 排名
  • arange <k> <start> <stop> withscores获取 scores 在开始和结束之间的元素
  • zrangebyscore <k> <mim> <max>返回并且排名 最小 scores 和最大 scores
  • zincrbg <k> <n> <v>为元素 v 添加 n 的 scores
  • zrem <k> <v>删除
  • zcount <k> <min> <max>统计 min scores 和 max scores 之间元素个数
  • zrank <k> <v>获取该元素的排名,从 0 开始

数据结构#

hash 跳跃表

使用场景#

  1. 排行榜

特殊类型(3 种)#

以下内容的学习均来自于此,使用了代码片段

原文地址🔗

HyperLogLogs(基数统计)#

什么是基数#

两个集合的全集

例如:A = {1,2,3,4,5,6} ; B = {5,6,7,8,9} ; 基数 = {1,2,3,4,7,8,9} ,即不重复元素。

使用场景#

统计和计数,用于统计注册 IP 数,每日访问 IP 书,页面实时 UV,在线用户数等。

优势#

基于基数估算的算法,能比较准确的估算出基数,可以使用少量固定的内存存储并识别集合中唯一的原色。

这个算法并不一定准确,有 0.81% 的错误率,基数统计适合接受一定容错的场景,比如统计访客数量等。

命令#

127.0.0.1:6379> pfadd key1 a b c d e f g h i	# 创建第一组元素
(integer) 1
127.0.0.1:6379> pfcount key1					# 统计元素的基数数量
(integer) 9
127.0.0.1:6379> pfadd key2 c j k l m e g a		# 创建第二组元素
(integer) 1
127.0.0.1:6379> pfcount key2
(integer) 8
127.0.0.1:6379> pfmerge key3 key1 key2			# 合并两组:key1 key2 -> key3 并集
OK
127.0.0.1:6379> pfcount key3
(integer) 13

Bitmap(位存储)#

Bitmap 是通过二进制记录信息,只有 0 和 1 两个状态

使用场景#

  1. 统计用户登陆信息,登陆和未登陆
  2. 统计用户点赞信息,点了和没点
  3. 统计员工打卡信息,打了和没打

命令#

  • 使用setbit <key> <offset> <value>写入数据,其中 key 可以任意,offset 只能为 Integer,value 只能为 0 或 1

    如果要统计员工一周的打卡情况,key 可以设置为 sign,offset 设置为 0-6,打卡为 0,未打卡为 1

127.0.0.1:6379> setbit sign 0 1
(integer) 0
127.0.0.1:6379> setbit sign 1 1
(integer) 0
127.0.0.1:6379> setbit sign 2 0
(integer) 0
127.0.0.1:6379> setbit sign 3 1
(integer) 0
127.0.0.1:6379> setbit sign 4 0
(integer) 0
127.0.0.1:6379> setbit sign 5 0
(integer) 0
127.0.0.1:6379> setbit sign 6 1
(integer) 0
  • 使用getbit <key> <offset>来查看某一个 key 的状态,返回 0 或 1
127.0.0.1:6379> getbit sign 3
(integer) 1
127.0.0.1:6379> getbit sign 5
(integer) 0
  • 使用bitcount <key>统计某一项数据的总数
127.0.0.1:6379> bitcount sign
(integer) 3

geospatial(地理位置)#

可以用户推算地理位置信息,如两地之间距离等

命令#

  • geoadd添加位置
127.0.0.1:6379> geoadd china:city 118.76 32.04 nanjing 112.55 37.86 taiyuan 123.43 41.80 shenyang
(integer) 3
127.0.0.1:6379> geoadd china:city 144.05 22.52 shengzhen 120.16 30.24 hangzhou 108.96 34.26 xian
(integer) 3
  • geopop获取指定成员的地理位置
127.0.0.1:6379> geopos china:city taiyuan nanjing
1) 1) "112.54999905824661255"
   1) "37.86000073876942196"
2) 1) "118.75999957323074341"
   1) "32.03999960287850968"
  • geodist获取两地之间的距离,可以指定单位
127.0.0.1:6379> geodist china:city taiyuan shenyang m
"1026439.1070"
127.0.0.1:6379> geodist china:city taiyuan shenyang km
"1026.4391"
  • georadius

这里有详细解释🔗

附近的人,获得所有附近的人的地址,定位,通过半径来查询

  • georadiusbymember

link🔗

显示与指定成员一定半径范围内的其他成员

Redis 中的数据结构#

  • 5 种基础数据结构:string(字符串)、list(列表)、set(集合)、hash(散列)、zset(有序集合)
  • 3 种特殊数据结构:HyperLogLogs(基数统计)、Bitmap(位存储)、Geospatial(地理位置)

对应关系#

图片来自

image

动态字符串 SDS#

Redis 并没有使用 C 中的字符串,而是自己定义了一种数据结构,即简单动态字符串(Simple Dynamic String SDS)。Redis 中 String 的底层数据结构使用的就是 SDS。

SDS 内存结构#

  • len保存 SDS 保存字符串的长度
  • buf[]数组保存字符串的每个元素
  • alloc分别以 unint8、unint16、unint32、unint64 表示整个 SDS
  • flags始终为一字符,以低三位标示着头部的类型

SDS 的优势#

  • O (1) 复杂度获取字符串长度:在 Redis 中如果要获取字符串长度只需读取 len 属性即可,在 C 中如果要获取字符串长度需要遍历整个字符串,是 O (n) 复杂度。使用strlen <K>获取字符串长度。
  • 防止缓冲区溢出:在 C 中,使用strcat中拼接两字符串,如果没有分配足够的内存空间,会造成缓冲区溢出。SDS 会先根据 len 先推算拼接后的长度是否满足内存空间要求。不满足会先扩展,再拼接,从而防止缓冲区溢出。
  • 减少修改字符串内存重新分配次数:SDS 使用lenalloc实现空间预分配惰性空间释放
    • 空间预分配:对字符串空间扩展时,扩展大于需求,从而减少字符串长度增加所需的内存重新分配次数。当字符串小于 1M 时,redis 会分配字符串大小一倍的空间,当字符串大小大于 1M 是,额外多分配 1M 空间。
    • 惰性空间释放:字符串长度减少时,不立即归还内存,而是使用alloc属性将这些空间记录下来,等待后续使用。如果觉得这样会浪费空间,可以自行设置定时释放未使用空间。
  • 二进制安全:C 中使用空字符来表示一个字符串的结束。但是如果 Redis 中保存的二进制文件(如图片)中可能包含空字符,C 无法正确读取。SDS 使用len属性表示的长度来判断字符串是否结束。

压缩列表 ZipList#

ziplist 是一种为提高存储效率设计的特殊编码的双向链表。可用于存储字符串或整数。

ziplist 内存结构#

  • zlbytes存储整个 ziplist 所占用内存字节数
  • zltail存储 ziplist 中最后一个 entry 的偏移量,用于快速定位最后一个 entry,方便快速 pop 操作
  • zllen存储 ziplist 中 entry 的数量。
  • zlend是终止字节

Entry 结构#

  • prevlen前一个 entry 的大小
  • encoding当前 entry 的类型和长度
  • entry-dataentry 数据

PS:如果 entry-data 中保存的是整形数据,encoding 会和 entrydata 合为一个,此时 entry 结构为

ziplist 优点#

节省内存

  • 普通 List 保存是,每个元素占用空间大小一致,均为当前 List 中最大元素所占的空间大小,造成了空间浪费。
  • ziplist 通过特殊的数据结构,尽量是每个元素占用与自身大小相同的空间,减少空间浪费。
  • 传统 List 在内存中地址连续,ziplist 所占大小不一致,所以地址不连续,需要通过prelen字段保存上一个元素的 length 来解决遍历问题。

ziplist 缺点#

  • 不预留内存空间,list 中元素被移除之后 list 无用空间立即归还,这导致每一次修改 list 都需要重新分配空间。

快表 QuickList#

以 ziplist 作为结点的双端链表,如何理解 QuickList:List<List<ziplist>> quickList

quicklist 在内存中结构#

  • quicklistNode链表中的节点,在 quicklist 中,这个节点是 ziplist
  • quickListLZFziplist 经过 LZ4 算法压缩后,可以包装成一个quickListLZF结构
  • quicklistBookmark位于 quicklist 尾部
  • quicklist
    • head、tail 指向头尾指针
    • len 表示链表中的节点
    • count 表示 quicklist 中 ziplist 中 entry 数目
    • fill 控制每个 quicklist 中 ziplist 最大所占空间
    • compress 控制是否要对每个 ziplist 以 LZ4 算法进行压缩以节省空间
  • quicklistIter迭代器
  • quicklistEntry对 ziplist 中 entry 封装

哈希表 - Dict-HashTable#

哈希表于大多数语言中的 HashTable 无异,差别主要存在于解决哈希冲突、扩容。

哈希冲突#

使用链地址法

扩容#

扩容步骤:

  1. 根据原哈希表所占空间大小创建一个新哈希表,大小为原哈希表一倍,(收缩也是减小为原来一倍大小)
  2. 使用哈希算法重新计算索引值
  3. 新表创建并赋值完毕之后删除原表

扩容发生条件

  1. redis 没有执行bgsavebgrewriteaof命令,负载因子大于等于 1
  2. redis 没有执行bgsavebgrewriteaof命令,负载因子大于等于 5

负载因子 = 哈希表中节点数量 / 哈希表大小

整数集 IntSet#

intset 是 redis 中集合类型底层实现之一,当一个集合只包含整数数值元素,并且元素数量较少,redis 使用 intset 作为集合键的底层实现

内存结构#

  • encoding编码方式
  • length存储整数个数
  • contents指向实际存储数值的连续内存区域

扩容#

intset 底层为数组,当新插入的元素大小大于原数组中最大元素的大小是,就需要对整个数组进行扩容,每个元素所占空间大小修改为最大元素的大小

会扩容但不会缩容!

跳表 ZSkipList#

跳跃表的目的类似于红黑树,为了性能。跳跃表可以在对数时间内完成插入、查找、删除。但是跳跃表所占空间较大,属于空间换时间的数据结构。

什么是跳跃表#

传统链表如果需要查询元素,需要从头遍历整个链表知道找到查询元素,时间复杂度 O (n)。跳跃表通过增加多级索引的方式减少遍历长度,从而加快查找速度。跳跃表实现了平衡树、哈希表类似的效果。

为什么不使用平衡树,而是跳跃表

链接🔗

图片来自

image

加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。