Redis 基本数据结构与应用

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注