Redis 基本数据结构与应用
Redis 基本数据结构
1.string (字符串)
2.list (列表)
3.set (集合)
4.hash (哈希)
5.zset (有序集合)
6.bitMap (位图)
7.HyperLogLogs
8.Geospatial (地理空间)
String
Redis 字符串是动态字符串,采用预分配冗余空间的方式来减少内存的频繁分配。字符串小于1M时,扩容都加倍现有空间,如果查过1M,扩容一次最多1M空间。
键值对
127.0.0.1:6379> set name libo OK 127.0.0.1:6379> get name "libo" 127.0.0.1:6379> exists name (integer) 1 127.0.0.1:6379> del name (integer) 1 127.0.0.1:6379> get name (nil) 127.0.0.1:6379> set name libo OK 127.0.0.1:6379> get name "libo" 127.0.0.1:6379> expire name 5 # 设置5秒后过期 (integer) 1 127.0.0.1:6379> get name (nil) 127.0.0.1:6379> setex name 5 libo # 设置 5秒后过期,等价于 set + expire OK 127.0.0.1:6379> get name "libo" 127.0.0.1:6379> get name (nil) 127.0.0.1:6379> setnx name libo # 如果 name 不存在就执行 set 创建 (integer) 1 127.0.0.1:6379> get name "libo" 127.0.0.1:6379> setnx name cikewang # 因为 name 已经存在,所以坚持不成功 (integer) 0 127.0.0.1:6379> get name "libo"
批量键值对
127.0.0.1:6379> mset name1 lisi name2 zhangsan OK 127.0.0.1:6379> mget name1 name2 1) "lisi" 2) "zhangsan"
计数
127.0.0.1:6379> set number 1 OK 127.0.0.1:6379> incr number (integer) 2 127.0.0.1:6379> incr number (integer) 3 127.0.0.1:6379> incrby number 5 (integer) 8 127.0.0.1:6379> decr number (integer) 7 127.0.0.1:6379> decrby number 6 (integer) 1 127.0.0.1:6379> get number "1"
List
Redis 是链表接口,插入和删除操作非常快,时间复杂度O(1),但索引定位很慢,时间复杂度为O(n).
队列 : 右边进左边出
127.0.0.1:6379> rpush users libo cikewang zhangsan (integer) 3 127.0.0.1:6379> llen users (integer) 3 127.0.0.1:6379> lpop users "libo" 127.0.0.1:6379> lpop users "cikewang" 127.0.0.1:6379> lpop users "zhangsan" 127.0.0.1:6379> lpop users (nil)
栈 : 右边进右边出
127.0.0.1:6379> rpush users libo cikewang zhangsan (integer) 3 127.0.0.1:6379> rpop users "zhangsan" 127.0.0.1:6379> rpop users "cikewang" 127.0.0.1:6379> rpop users "libo" 127.0.0.1:6379> rpop users (nil)
慢操作
lindex 需要对链表进行遍历,性能锁着参数 index 增大而变差 (http://redis.cn/commands/lindex.html)
ltrim
127.0.0.1:6379> rpush users libo cikewang zilong (integer) 3 127.0.0.1:6379> lindex users 1 # 通过索引1获取元素 "cikewang" 127.0.0.1:6379> lindex users 0 "libo" 127.0.0.1:6379> llen users (integer) 3 127.0.0.1:6379> lrange users 0 -1 1) "libo" 2) "cikewang" 3) "zilong" 127.0.0.1:6379> lrange users 1 -1 1) "cikewang" 2) "zilong" 127.0.0.1:6379> lrange users 0 -1 1) "libo" 2) "cikewang" 3) "zilong" 127.0.0.1:6379> ltrim users 1 -1 OK 127.0.0.1:6379> lrange users 0 -1 1) "cikewang" 2) "zilong" 127.0.0.1:6379> ltrim users 1 0 OK 127.0.0.1:6379> llen uesrs (integer) 0
快速链表
ziplist
hash (字典)
Reids hast 是数组 + 链表二维结构,当 hash 数组位置冲突时,会使用链表结构存储元素。
127.0.0.1:6379> hset users name1 libo (integer) 1 127.0.0.1:6379> hset users name2 cikewang (integer) 1 127.0.0.1:6379> hset users name3 zilong (integer) 1 127.0.0.1:6379> hgetall users 1) "name1" 2) "libo" 3) "name2" 4) "cikewang" 5) "name3" 6) "zilong" 127.0.0.1:6379> hlen users (integer) 3 127.0.0.1:6379> hget users name1 "libo" 127.0.0.1:6379> hget users name2 "cikewang" 127.0.0.1:6379> hset users name3 zhangsan (integer) 0 127.0.0.1:6379> hget users name3 "zhangsan" 127.0.0.1:6379> hmset users name1 zhangsan name2 libo name3 cikewang OK 127.0.0.1:6379> hgetall users 1) "name1" 2) "zhangsan" 3) "name2" 4) "libo" 5) "name3" 6) "cikewang"
set (集合)
键值对是无序的唯一的,字典中所有的 value 都是一个值 NULL。
当集合中最后一个元素移除之后,数据结构自动删除,内存被回收。
127.0.0.1:6379> sadd userset libo (integer) 1 127.0.0.1:6379> sadd userset cikewang zhangsan (integer) 2 127.0.0.1:6379> smembers userset 1) "cikewang" 2) "zhangsan" 3) "libo" 127.0.0.1:6379> sismember userset libo # 查询摸个 value 是否存在 (integer) 1 127.0.0.1:6379> scard userset (integer) 3 127.0.0.1:6379> spop userset "cikewang"
zset (有序集合)
实现上是一个 set 集合,保证了内部 value 的唯一性,另一个方面是给每个 value 赋予一个 score,代表了 value 的排序权重。内部实现用的是 跳跃列表的数据结构。
127.0.0.1:6379> zadd users 99 libo (integer) 1 127.0.0.1:6379> zadd users 80 cikewang (integer) 1 127.0.0.1:6379> zadd users 60 zhangsan (integer) 1 127.0.0.1:6379> zrange users 0 -1 1) "zhangsan" 2) "cikewang" 3) "libo" 127.0.0.1:6379> zrevrange users 0 -1 1) "libo" 2) "cikewang" 3) "zhangsan" 127.0.0.1:6379> zcard users # 统计总数 count (integer) 3 127.0.0.1:6379> zscore users libo # 查询 score "99" 127.0.0.1:6379> zrank users cikewang # 查询排名 (integer) 1 127.0.0.1:6379> zrank users libo # 查询排名 (integer) 2 127.0.0.1:6379> zrangebyscore users 0 80 # 查询权重范围内 1) "zhangsan" 2) "cikewang" 127.0.0.1:6379> zrangebyscore users -inf 80 withscores # 相当于 (-∞,80],小于等于 80 1) "zhangsan" 2) "60" 3) "cikewang" 4) "80" 127.0.0.1:6379> zrem users zhangsan # 删除 zhangsan (integer) 1 127.0.0.1:6379> zrange users 0 -1 1) "cikewang" 2) "libo"
Redis分布式锁
Redis 2.8 之前使用
127.0.0.1:6379> setnx lock:user true (integer) 1 127.0.0.1:6379> expire lock:user 5 (integer) 1 127.0.0.1:6379> get lock:user "true" 127.0.0.1:6379> get lock:user (nil)
以上存在问题:如果执行完 setnx 命令后,由于其他什么原因没有执行 expire 命令,将会产生死锁。
Reids 2.8版本及以后扩展了 set 参数 EX 设置过期时间 NX 查看是否存在
127.0.0.1:6379> set lock:user true EX 5 NX OK 127.0.0.1:6379> get lock:user "true" 127.0.0.1:6379> get lock:user (nil)
锁冲突处理:处理请求是加锁没有成功怎么办
1. 直接抛出异常,通知用户稍后重试
2. sleep 一会儿再重试
3. 将请求转移到延时队列,过一会儿再试
延时队列
异步消息队列使用 rpush/lpush 入队列,使用 lpop/rpop 出队列。
如果队列为空时,pop 将陷入死循环,因没有数据将产生空轮询,这样将会拉高客户端CPU,Redis的QPS。
处理办法:
1. 当队里为空是 sleep 1s。
2. 使用 blpop/brpop 阻塞方式。当队列没有数据是进入休眠状态,一旦数据到来,则立刻醒来读取队列。有个问题是空闲连接时间过长,服务器一般会主动断开连接,减少资源占用,这是会 blpop/brpop 会保存异常。
BitMap 位图
位图就是byte数组,使用 getbit/setbit 来操作,将 byte 数组看成位数组来处理。
使用 Python 获取二进制
[root@izj6cde73iq3iwyybzjxyqz ~]# python >>> bin(ord('L')) '0b1001100' >>> bin(ord('i')) '0b1101001'
将位数组需要的位置设置为1,L 字母为:1/4/5, i 字母为 9/10/12/15
127.0.0.1:6379> setbit name 1 1 (integer) 0 127.0.0.1:6379> setbit name 4 1 (integer) 0 127.0.0.1:6379> setbit name 5 1 (integer) 0 127.0.0.1:6379> setbit name 9 1 (integer) 0 127.0.0.1:6379> setbit name 10 1 (integer) 0 127.0.0.1:6379> setbit name 12 1 (integer) 0 127.0.0.1:6379> setbit name 15 1 (integer) 0 127.0.0.1:6379> get name # 获取 "Li"
bitcount : 统计字符串被设置为1的bit数。 时间复杂度 O(N)
127.0.0.1:6379> set name "Li" OK 127.0.0.1:6379> bitcount name 0 -1 (integer) 7
bitpos : 时间复杂度 O(N)
返回字符串里第一个被设置为1或者0的位。
127.0.0.1:6379> bitpos name 0 (integer) 0 127.0.0.1:6379> bitpos name 1 (integer) 1
bitfield : [3.2.0], 时间复杂度 O(1)
批量操作位,三个子命令: get / set / incrby
127.0.0.1:6379> set name libo OK 127.0.0.1:6379> bitfield name get u4 0 # 从第一个位置开始获取 4 个位,结果是无符号数(u) 1) (integer) 6 127.0.0.1:6379> bitfield name get u3 0 # 从第一个位置开始获取 3 个位,结果是无符号数(u) 1) (integer) 3 127.0.0.1:6379> bitfield name get i4 0 # 从第一个位置开始获取 4 个位,结果是有符号数(i) 1) (integer) 6 127.0.0.1:6379> bitfield name get i3 2 # 从第三个位置开始获取 3 个位置,结果是有符号数(i) 1) (integer) -3
有符号数是指获取的位数组中第一个位是符号位,剩下的才是值。如果第一位是1,那就是负数。无符号数表示非负数,没有符号位,获取的维数组全部都是值。
有符号数最多可获取64位,无符号数只能获取63位。因为 Redis 协议中的integer是有符号数,最大64位,不能传递64位无符号值。
一次执行多个子命令
127.0.0.1:6379> bitfield name get u4 0 get u3 2 get i4 0 get i3 2 1) (integer) 6 2) (integer) 5 3) (integer) 6 4) (integer) -3
使用 set 子命令将第二个字符 i 变成 a, a 的 ASCII 码是 97。
127.0.0.1:6379> bitfield name set u8 8 97 # 从第 8 个位开始,将接下来的 8 个位用无符号数 97 替换 1) (integer) 105 127.0.0.1:6379> get name "labo"
使用 incrby 对指定范围的位进行自增操作。如果自增就可能出现溢出。如果增加了整数,会出现上溢出,如果增加的是负数,就会出现下溢出。
Redis默认的处理方式是折返。如果出现了溢出,就将溢出的符号位丢掉。如果是 8位无符号数 255,加1后就会溢出,会全部变零。如果是8位有符号数 127,加1后就会溢出变成 -128
[root@izj6cde73iq3iwyybzjxyqz ~]# python >>> bin(ord('l')) # 查看 1 的二进制 '0b1101100'
使用 incrby 命令
127.0.0.1:6379> bitfield name incrby u4 0 1 1) (integer) 7 127.0.0.1:6379> bitfield name incrby u4 0 1 1) (integer) 8 127.0.0.1:6379> bitfield name incrby u4 0 1 1) (integer) 9 127.0.0.1:6379> bitfield name incrby u4 0 1 1) (integer) 10 127.0.0.1:6379> bitfield name incrby u4 0 1 1) (integer) 11 127.0.0.1:6379> bitfield name incrby u4 0 1 1) (integer) 12 127.0.0.1:6379> bitfield name incrby u4 0 1 1) (integer) 13 127.0.0.1:6379> bitfield name incrby u4 0 1 1) (integer) 14 127.0.0.1:6379> bitfield name incrby u4 0 1 1) (integer) 15 127.0.0.1:6379> bitfield name incrby u4 0 1 1) (integer) 0 127.0.0.1:6379> get name "\x0cabo" 127.0.0.1:6379> bitfield name set u4 0 6 # 从第一个位置开始设置4位无符号数为 6 ,相当于二进制 0110 1) (integer) 0 127.0.0.1:6379> get name "labo"
针对 bitfield 命令的溢出问题,Redis 提供了策略命令 overflow[wrap | sat | fail]
warp : (默认) 回环算法,适用于有符号和无符号整数两种类型。
sat : 饱和算法,下溢出之后设为最小的整数值,上溢出之后设置为最大的整数值
fail:失败算法,在溢出的情况下不做任何操作。响应返回值会设为 NULL,并返回给调用者。
sat 从第一位开始,设置4位加10, l 前4位是 0110 + 1010, 如果是十进制将等于 16,二进制将会溢出,根据 sat 饱和算法将等于 15,二进制为 1111
127.0.0.1:6379> get name "labo" 127.0.0.1:6379> bitfield name overflow sat incrby u4 0 10 1) (integer) 15
fail: 从第一位开始,设置4位加10, l 前4位是 0110 + 1010, 如果是十进制将等于 16,二进制将会溢出,跟进 fail 失败算法,将返回 null
127.0.0.1:6379> bitfield name overflow fail incrby u4 0 10 1) (nil) 127.0.0.1:6379> get name "labo"
HyperLogLogs
Redis 提供 Hyperloglogs 概率数据结构用来解决统计问题,用于计算唯一性,HyperLoglogs 提供不精确的去重计数方案,标准误差小于 1%。
HyperLoglogs 提供了两个命令 pfadd 和 pfcount。
127.0.0.1:6379> pfadd names libo cikewang zhangsan (integer) 1 127.0.0.1:6379> pfcount names (integer) 3 127.0.0.1:6379> pfadd names lisi (integer) 1 127.0.0.1:6379> pfcount names (integer) 4 127.0.0.1:6379> pfadd names libo (integer) 0 127.0.0.1:6379> pfcount names (integer) 4
还有一个 pfmerge 将两个或多个参数值合并
127.0.0.1:6379> pfadd books java php c (integer) 1 127.0.0.1:6379> pfcount books (integer) 3 127.0.0.1:6379> pfmerge cou names books OK 127.0.0.1:6379> pfcount cou (integer) 7 127.0.0.1:6379> pfcount cou (integer) 3
rebloom 布隆过滤器
插件[github]
实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用来减少一个元素是否存在一个集合中。它的有点是空间效率和查询时间都远超过一般算法,缺点是有一定误识别率和删除困难。【百度百科】
Keys 和 scan 命令
Keys 查找对应规则的 key
127.0.0.1:6379> keys * 1) "name" 2) "name2" 3) "names" 4) "number" 5) "users" 6) "books"
keys 命令缺点:
1. 没有分页,一次性获取对应规则全部的 key
2. keys 算法是遍历算法,时间复杂度是 O(n),key多是会导致Redis 服务器卡顿
scan 与 keys 命令相比较:
1. 时间复杂度 O(n),但是他是通过游标分布进行,不会阻塞线程
2. 提供 limit 分页
3. 提供匹配功能
4. 服务器不需要为游标保存状态,游标的唯一状态就是 scan 返回客户端的游标整数。
5. 返回的结果可能会有重复,需要客户端去重复
6. 遍历的过程中如果有数据修改,改动后的数据能不能遍历到不确定
7. 单词返回的结果是空并不意味着遍历结束,而要看返回的游标值是否为零。
127.0.0.1:6379> scan 0 match name* count 5 1) "5" 2) 1) "names" 2) "name" 3) "name2"
查找 Reids 中的大 key
./redis-cli -h 127.0.0.1 -p 6379 --bigkeys
每个 100 条 scan 命令休息 0.1秒
./redis-cli -h 127.0.0.1 -p 6379 --bigkeys -i 0.1