Redis笔记梳理(二)

基础数据结构

String

Redis 的字符串是动态字符串,是可以修改的字符串,内部结构实现上类似于 Java 的 ArrayList,采用预分配冗余空间的方式来减少内存的频繁分配,

如图中所示,内部为当前字符串实际分配的空间 capacity 一般要高于实际字符串长度 len。
当字符串长度小于 1M 时,扩容都是加倍现有的空间,如果超过 1M,扩容时一次只会多扩 1M 的空间。需要注意的是字符串最大长度为 512M

键值对

1
2
3
4
5
6
7
8
> set name codehole
OK
> get name"codehole"> exists name
(integer) 1
> del name
(integer) 1
> get name
(nil)

  • 批量键值对 可以批量对多个字符串进行读写,节省网络耗时开销。
  • 过期和 set 命令扩展
  • 计数,如果 value 值是一个整数,还可以对它进行自增操作。自增是有范围的,它的范围是signed long 的最大最小值,超过了这个值,Redis 会报错

List

Redis 的列表相当于 Java 语言里面的 LinkedList
注意它是链表而不是数组。这意味着 list 的插入和删除操作非常快,时间复杂度为 O(1),但是索引定位很慢,时间复杂度为 O(n)。
当列表弹出了最后一个元素之后,该数据结构自动被删除,内存被回收。

右边进左边出:队列
右边进右边出:栈

  • lindex 相当于 Java 链表的 get(int index)方法,它需要对链表进行遍历,性能随着参数 index增大而变差。
  • ltrim 两个参数 start_index和 end_index定义了一个区间,在这个区间内的值,ltrim 要保留,区间之外统统砍掉(index 可以为负数, index=-1表示倒数第一个元素,同样 index=-2表示倒数第二个元素)

Redis 底层存储的还不是一个简单的linkedlist,而是称之为快速链表quicklist 的一个结构。

Hash

Redis 的字典相当于 Java 语言里面的 HashMap,它是无序字典。

内部实现结构上同 Java 的 HashMap 也是一致的,同样的数组 + 链表二维结构。第一维 hash 的数组位置碰撞时,就会将碰撞的元素使用链表串接起来。

不同的是,Redis 的字典的值只能是字符串,另外它们 rehash 的方式不一样,因为 Java 的 HashMap 在字典很大时,rehash 是个耗时的操作,需要一次性全部 rehash。

Redis 为了高性能,不能堵塞服务,所以采用了渐进式 rehash 策略。

hash 也有缺点:

  • hash 结构的存储消耗要高于单个字符串,到底该使用 hash 还是字符串,需要根据实际情况再三权衡。

同字符串一样,hash 结构中的单个子 key 也可以进行计数,它对应的指令是 hincrby,和 incr 使用基本一样。

Set

Redis 的集合相当于 Java 语言里面的 HashSet,它内部的键值对是无序的唯一的。
它的内部实现相当于一个特殊的字典,字典中所有的 value 都是一个值NULL
当集合中最后一个元素移除之后,数据结构自动删除,内存被回收

场景:

  • set 结构可以用来存储活动中奖的用户 ID,因为有去重功能,可以保证同一个用户不会中奖两次

ZSet

zset 可能是 Redis 提供的最为特色的数据结构,它也是在面试中面试官最爱问的数据结构。
它类似于 Java 的 SortedSet 和 HashMap 的结合体,
一方面它是一个 set,保证了内部 value 的唯一性,另一方面它可以给每个 value 赋予一个 score,代表这个 value 的排序权重。
它的内部实现用的是一种叫做「跳跃列表」的数据结构。
zset 中最后一个 value 被移除后,数据结构自动删除,内存被回收。

场景:

  • zset 可以用来存粉丝列表,value 值是粉丝的用户 ID,score 是关注时间。我们可以对粉丝列表按关注时间进行排序。
  • zset 还可以用来存储学生的成绩,value 值是学生的 ID,score 是他的考试成绩。我们可以对成绩按分数进行排序就可以得到他的名次。

分布式锁

Redis 2.8 版本中作者加入了 set 指令的扩展参数,使得 setnx 和 expire 指令可以一起执行,彻底解决了分布式锁的乱象。从此以后所有的第三方分布式锁 library 可以休息了。

1
2
3
4
> set lock:codehole true ex 5 nx
OK
... do something critical ...
> del lock:codehole...

锁冲突处理

一般有 3 种策略来处理加锁失败:

  • 直接抛出异常,通知用户稍后重试;
  • sleep 一会再重试;
  • 将请求转移至延时队列,过一会再试

延时队列

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

队列空了怎么办?

客户端是通过队列的 pop 操作来获取消息,然后进行处理。处理完了再接着获取消息,再进行处理。如此循环往复,这便是作为队列消费者的客户端的生命周期。
可是如果队列空了,客户端就会陷入 pop 的死循环,不停地 pop,没有数据,接着再 pop,又没有数据。这就是浪费生命的空轮询。
空轮询不但拉高了客户端的 CPU,redis 的 QPS 也会被拉高,如果这样空轮询的客户端有几十来个,Redis 的慢查询可能会显著增多。
通常我们使用 sleep 来解决这个问题,让线程睡一会,睡个 1s 钟就可以了。不但客户端的 CPU 能降下来,Redis 的 QPS 也降下来了。

阻塞读

用上面睡眠的办法可以解决问题。但是有个小问题,那就是睡眠会导致消息的延迟增大。
如果只有 1 个消费者,那么这个延迟就是 1s。如果有多个消费者,这个延迟会有所下降,因为每个消费者的睡觉时间是岔开来的。

降低延迟:

  • 1、将sleep时间缩短
  • 2、blpop / brpop

这两个指令的前缀字符b代表的是blocking,也就是阻塞读。
阻塞读在队列没有数据的时候,会立即进入休眠状态,一旦数据到来,则立刻醒过来。消息的延迟几乎为零。
blpop/brpop替代前面的lpop/rpop,就完美解决了上面的问题。

空闲连接自动断开 你以为上面的方案真的很完美么?其实还有个问题需要解决。
什么问题?—— 空闲连接的问题。

如果线程一直阻塞在哪里,Redis 的客户端连接就成了闲置连接,闲置过久,服务器一般会主动断开连接,减少闲置资源占用。
这个时候blpop/brpop会抛出异常来。 所以编写客户端消费者的时候要小心,注意捕获异常,还要重试

位图

Redis 的位数组是自动扩展,如果设置了某个偏移位置超出了现有的内容范围,就会自动将位数组进行零扩充。

统计和查找

Redis 提供了位图统计指令 bitcount 和位图查找指令 bitpos,bitcount 用来统计指定位置范围内 1 的个数,bitpos 用来查找指定范围内出现的第一个 0 或 1。

比如我们可以通过 bitcount 统计用户一共签到了多少天,通过 bitpos 指令查找用户从哪一天开始第一次签到。如果指定了范围参数 [start, end],就可以统计在某个时间范围内用户签到了多少天,用户自某天以后的哪天开始签到。

遗憾的是, start 和 end 参数是字节索引,也就是说指定的位范围必须是 8 的倍数,而不能任意指定。
因为这个设计,我们无法直接计算某个月内用户签到了多少天,而必须要将这个月所覆盖的字节内容全部取出来 (getrange 可以取出字符串的子串) 然后在内存里进行统计。

HyperLogLog

业务场景:

果你负责开发维护一个大型的网站,有一天老板找产品经理要网站每个网页每天的 UV 数据,然后让你来开发这个统计模块,你会如何实现?

如果统计 PV 那非常好办,给每个网页一个独立的 Redis 计数器就可以了,这个计数器的 key 后缀加上当天的日期。这样来一个请求,incrby 一次,最终就可以统计出所有的 PV 数据。
但是 UV 不一样,它要去重,同一个用户一天之内的多次访问请求只能计数一次。这就要求每一个网页请求都需要带上用户的 ID,无论是登陆用户还是未登陆用户都需要一个唯一 ID 来标识。

你也许已经想到了一个简单的方案,那就是为每一个页面一个独立的 set 集合来存储所有当天访问过此页面的用户 ID。当一个请求过来时,我们使用 sadd 将用户 ID 塞进去就可以了。
通过 scard 可以取出这个集合的大小,这个数字就是这个页面的 UV 数据。
没错,这是一个非常简单的方案。 但是,如果你的页面访问量非常大,比如一个爆款页面几千万的 UV,你需要一个很大的 set 集合来统计,这就非常浪费空间。
如果这样的页面很多,那所需要的存储空间是惊人的。

为这样一个去重功能就耗费这样多的存储空间,值得么?

其实老板需要的数据又不需要太精确,105w 和 106w 这两个数字对于老板们来说并没有多大区别,
So,有没有更好的解决方案呢?

Redis 提供了 HyperLogLog 数据结构就是用来解决这种统计问题的。

HyperLogLog 提供不精确的去重计数方案,虽然不精确但是也不是非常不精确,标准误差是 0.81%,这样的精确度已经可以满足上面的 UV 统计需求了。

布隆过滤器

它就是专门用来解决这种去重问题的。它在起到去重的同时,在空间上还能节省 90% 以上,只是稍微有那么点不精确,也就是有一定的误判概率。

布隆过滤器可以理解为一个不怎么精确的 set 结构,当你使用它的 contains 方法判断某个对象是否存在时,它可能会误判。
但是布隆过滤器也不是特别不精确,只要参数设置的合理,它的精确度可以控制的相对足够精确,只会有小小的误判概率。

当布隆过滤器说某个值存在时,这个值可能不存在;当它说不存在时,那就肯定不存在。

打个比方,当它说不认识你时,肯定就不认识;当它说见过你时,可能根本就没见过面,不过因为你的脸跟它认识的人中某脸比较相似 (某些熟脸的系数组合),所以误判以前见过你。

套在上面的使用场景中,布隆过滤器能准确过滤掉那些已经看过的内容,那些没有看过的新内容,它也会过滤掉极小一部分 (误判),但是绝大多数新内容它都能准确识别。
这样就可以完全保证推荐给用户的内容都是无重复的。

Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。
布隆过滤器作为一个插件加载到 Redis Server 中,给 Redis 提供了强大的布隆去重功能。

布隆过滤器有二个基本指令,bf.add 添加元素,bf.exists 查询元素是否存在,它的用法和 set 集合的 sadd 和 sismember 差不多。

  • 注意 bf.add 只能一次添加一个元素,如果想要一次添加多个,就需要用到 bf.madd 指令。同样如果需要一次查询多个元素是否存在,就需要用到 bf.mexists 指令。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
127.0.0.1:6379> bf.add codehole user1
(integer) 1
127.0.0.1:6379> bf.add codehole user2
(integer) 1
127.0.0.1:6379> bf.add codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehole user1
(integer) 1
127.0.0.1:6379> bf.exists codehole user2
(integer) 1
127.0.0.1:6379> bf.exists codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehole user4
(integer) 0
127.0.0.1:6379> bf.madd codehole user4 user5 user6
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists codehole user4 user5 user6 user7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0...

限流

简单限流

场景:

系统要限定用户的某个行为在指定的时间里只能允许发生 N 次,如何使用 Redis 的数据结构来实现这个限流的功能?

解决方案:
这个限流需求中存在一个滑动时间窗口,想想 zset 数据结构的 score 值,是不是可以通过 score 来圈出这个时间窗口来。
而且我们只需要保留这个时间窗口,窗口之外的数据都可以砍掉。那这个 zset 的 value 填什么比较合适呢?它只需要保证唯一性即可,用 uuid 会比较浪费空间,那就改用毫秒时间戳吧。

如图所示,用一个 zset 结构记录用户的行为历史,每一个行为都会作为 zset 中的一个 key 保存下来。同一个用户同一种行为用一个 zset 记录。
为节省内存,我们只需要保留时间窗口内的行为记录,同时如果用户是冷用户,滑动时间窗口内的行为是空记录,那么这个 zset 就可以从内存中移除,不再占用空间。
通过统计滑动窗口内的行为数量与阈值 max_count 进行比较就可以得出当前的行为是否允许。

用代码表示如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class SimpleRateLimiter {

private Jedis jedis;

public SimpleRateLimiter(Jedis jedis) {
this.jedis = jedis;
}

public boolean isActionAllowed(String userId, String actionKey, int period, int maxCount) {
String key = String.format("hist:%s:%s", userId, actionKey);
long nowTs = System.currentTimeMillis();
Pipeline pipe = jedis.pipelined();
pipe.multi();
pipe.zadd(key, nowTs, "" + nowTs);
pipe.zremrangeByScore(key, 0, nowTs - period * 1000);
Response<Long> count = pipe.zcard(key);
pipe.expire(key, period + 1);
pipe.exec();
pipe.close();
return count.get() <= maxCount;
}

public static void main(String[] args) {
Jedis jedis = new Jedis();
SimpleRateLimiter limiter = new SimpleRateLimiter(jedis);
for(int i=0;i<20;i++) {
System.out.println(limiter.isActionAllowed("laoqian", "reply", 60, 5));
}
}

}

地理位置GEO模块

edis 在 3.2 版本以后增加了地理位置 GEO 模块,意味着我们可以使用 Redis 来实现摩拜单车「附近的 Mobike」、美团和饿了么「附近的餐馆」这样的功能了。  

Redis 提供的 Geo 指令只有 6 个 ,它只是一个普通的 zset 结构

增加

geoadd 指令携带集合名称以及多个经纬度名称三元组,注意这里可以加入多个三元组

1
2
3
4
5
6
7
8
127.0.0.1:6379> geoadd company 116.48105 39.996794 juejin
(integer) 1
127.0.0.1:6379> geoadd company 116.514203 39.905409 ireader
(integer) 1
127.0.0.1:6379> geoadd company 116.489033 40.007669 meituan
(integer) 1
127.0.0.1:6379> geoadd company 116.562108 39.787602 jd 116.334255 40.027400 xiaomi
(integer) 2...

距离

geodist 指令可以用来计算两个元素之间的距离,携带集合名称、2 个名称和距离单位。

1
2
3
4
5
6
7
8
9
10
127.0.0.1:6379> geodist company juejin ireader km
"10.5501"
127.0.0.1:6379> geodist company juejin meituan km
"1.3878"
127.0.0.1:6379> geodist company juejin jd km
"24.2739"
127.0.0.1:6379> geodist company juejin xiaomi km
"12.9606"
127.0.0.1:6379> geodist company juejin juejin km
"0.0000"...

获取元素位置

geopos 指令可以获取集合中任意元素的经纬度坐标,可以一次获取多个。

1
2
3
4
5
6
7
8
9
10
11
127.0.0.1:6379> geopos company juejin
1) 1) "116.48104995489120483"
2) "39.99679348858259686"
127.0.0.1:6379> geopos company ireader
1) 1) "116.5142020583152771"
2) "39.90540918662494363"
127.0.0.1:6379> geopos company juejin ireader
1) 1) "116.48104995489120483"
2) "39.99679348858259686"
2) 1) "116.5142020583152771"
2) "39.90540918662494363"...

geohash 对二维坐标进行的一维映射是有损的,通过映射再还原回来的值会出现较小的差别

获取元素的 hash 值

geohash 可以获取元素的经纬度编码字符串,上面已经提到,它是 base32 编码。 你可以使用这个编码值去 http://geohash.org/${hash}中进行直接定位,它是 geohash 的标准编码值。

1
2
3
4
127.0.0.1:6379> geohash company ireader
1) "wx4g52e1ce0"
127.0.0.1:6379> geohash company juejin
1) "wx4gd94yjn0"

附近的公司

georadiusbymember 指令是最为关键的指令,它可以用来查询指定元素附近的其它元素,它的参数非常复杂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 范围 20 公里以内最多 3 个元素按距离正排,它不会排除自身
127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 asc
1) "ireader"
2) "juejin"
3) "meituan"
# 范围 20 公里以内最多 3 个元素按距离倒排
127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 desc
1) "jd"
2) "meituan"
3) "juejin"
# 三个可选参数 withcoord withdist withhash 用来携带附加参数
# withdist 很有用,它可以用来显示距离
127.0.0.1:6379> georadiusbymember company ireader 20 km withcoord withdist withhash count 3 asc
1) 1) "ireader"
2) "0.0000"
3) (integer) 4069886008361398
4) 1) "116.5142020583152771"
2) "39.90540918662494363"
2) 1) "juejin"
2) "10.5501"
3) (integer) 4069887154388167
4) 1) "116.48104995489120483"
2) "39.99679348858259686"
3) 1) "meituan"
2) "11.5748"
3) (integer) 4069887179083478
4) 1) "116.48903220891952515"
2) "40.00766997707732031"...

根据坐标查附近的元素

1
2
3
4
5
6
7
127.0.0.1:6379> georadius company 116.514202 39.905409 20 km withdist count 3 asc
1) 1) "ireader"
2) "0.0000"
2) 1) "juejin"
2) "10.5501"
3) 1) "meituan"
2) "11.5748"...

Keys 和Scan

edis 在 3.2 版本以后增加了地理位置 GEO 模块,意味着我们可以使用 Redis 来实现摩拜单车「附近的 Mobike」、美团和饿了么「附近的餐馆」这样的功能了。  

Redis 提供的 Geo 指令只有 6 个 ,它只是一个普通的 zset 结构

增加

geoadd 指令携带集合名称以及多个经纬度名称三元组,注意这里可以加入多个三元组

1
2
3
4
5
6
7
8
127.0.0.1:6379> geoadd company 116.48105 39.996794 juejin
(integer) 1
127.0.0.1:6379> geoadd company 116.514203 39.905409 ireader
(integer) 1
127.0.0.1:6379> geoadd company 116.489033 40.007669 meituan
(integer) 1
127.0.0.1:6379> geoadd company 116.562108 39.787602 jd 116.334255 40.027400 xiaomi
(integer) 2...

距离

geodist 指令可以用来计算两个元素之间的距离,携带集合名称、2 个名称和距离单位。

1
2
3
4
5
6
7
8
9
10
127.0.0.1:6379> geodist company juejin ireader km
"10.5501"
127.0.0.1:6379> geodist company juejin meituan km
"1.3878"
127.0.0.1:6379> geodist company juejin jd km
"24.2739"
127.0.0.1:6379> geodist company juejin xiaomi km
"12.9606"
127.0.0.1:6379> geodist company juejin juejin km
"0.0000"...

获取元素位置

geopos 指令可以获取集合中任意元素的经纬度坐标,可以一次获取多个。

1
2
3
4
5
6
7
8
9
10
11
127.0.0.1:6379> geopos company juejin
1) 1) "116.48104995489120483"
2) "39.99679348858259686"
127.0.0.1:6379> geopos company ireader
1) 1) "116.5142020583152771"
2) "39.90540918662494363"
127.0.0.1:6379> geopos company juejin ireader
1) 1) "116.48104995489120483"
2) "39.99679348858259686"
2) 1) "116.5142020583152771"
2) "39.90540918662494363"...

geohash 对二维坐标进行的一维映射是有损的,通过映射再还原回来的值会出现较小的差别

获取元素的 hash 值

geohash 可以获取元素的经纬度编码字符串,上面已经提到,它是 base32 编码。 你可以使用这个编码值去 http://geohash.org/${hash}中进行直接定位,它是 geohash 的标准编码值。

1
2
3
4
127.0.0.1:6379> geohash company ireader
1) "wx4g52e1ce0"
127.0.0.1:6379> geohash company juejin
1) "wx4gd94yjn0"

附近的公司

georadiusbymember 指令是最为关键的指令,它可以用来查询指定元素附近的其它元素,它的参数非常复杂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 范围 20 公里以内最多 3 个元素按距离正排,它不会排除自身
127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 asc
1) "ireader"
2) "juejin"
3) "meituan"
# 范围 20 公里以内最多 3 个元素按距离倒排
127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 desc
1) "jd"
2) "meituan"
3) "juejin"
# 三个可选参数 withcoord withdist withhash 用来携带附加参数
# withdist 很有用,它可以用来显示距离
127.0.0.1:6379> georadiusbymember company ireader 20 km withcoord withdist withhash count 3 asc
1) 1) "ireader"
2) "0.0000"
3) (integer) 4069886008361398
4) 1) "116.5142020583152771"
2) "39.90540918662494363"
2) 1) "juejin"
2) "10.5501"
3) (integer) 4069887154388167
4) 1) "116.48104995489120483"
2) "39.99679348858259686"
3) 1) "meituan"
2) "11.5748"
3) (integer) 4069887179083478
4) 1) "116.48903220891952515"
2) "40.00766997707732031"...

根据坐标查附近的元素

1
2
3
4
5
6
7
127.0.0.1:6379> georadius company 116.514202 39.905409 20 km withdist count 3 asc
1) 1) "ireader"
2) "0.0000"
2) 1) "juejin"
2) "10.5501"
3) 1) "meituan"
2) "11.5748"...

分享到: