Redis典型使用场景
排行榜
我们分析一下排行榜,一个用户一个排名,意味着要去重,这时我们会想到Java的一种数据结构Set。不过Set又是无序的。有没有一种结构是可以保住元素唯一以及有序的呢。
幸运的是,还真的有。Redis的ZSet的就是这样的一种数据结构。Zset里面的元素是唯一的,有序的,按分数从小到大排序。作为一名优秀的crud程序员,我们从这几个方方面入手了解zset结构。
ZADD 增加与修改
其时间复杂度为 O(M*log(N)), N 是有序集的基数, M 为成功添加的新成员的数量。如果key不存在就插入,存在就更新。
1 | ZADD page_rank 10 google.com |
说明 :
page_rankde 是key,10是分数,google.com是value
ZREVRANGE查询
时间复杂度: O(log(N))
1 | ZREVRANGE salary 0 -1 # 显示所有成员 |
说明 :
salary的key,tom是value,只要输入特定的key与value就能查询到对应的排名。
del 删除
直接使用redis的del命令
分数设计
回到排行榜的实现,要利用zset结构来实现的话,重要的是如何设计分数。分析一下排行榜单的设计。如果排行榜的设计按一个维度比如金币数量,那只需把其数量取反作为分数score即可。取反是因为zset默认从小到大排序。
实现如下:
1 | public Double getScore( Long oneDayGoldBean) { |
如果排行榜的设计按两个维度比如金币数量和用时。由于score是一个可以double类型的参数,设计的时候可以把用时作为小数,用一天的总毫秒数减去花费毫秒数作为小数部分,然后当做字符串拼接起来,然后取反作为score.
实现如下:
1 | public Double getScore( Long oneDayGoldBean, Long useTime) { |
代码实现
1 |
|
计数器
redis由于incrby命令可以实现原子性的递增,所以可以运用于高并发的秒杀活动、分布式序列号的生成、具体业务还体现在比如限制一个手机号发多少条短信、一个接口一分钟限制多少请求、一个接口一天限制调用多少次等等。
位图
我们都知道8bit = 1b = 2^-10kb, bitmap
就是通过最小的单位 bit
来进行0或者1的设置,表示某个元素对应的值或者状态。
一个bit的值,或者是0,或者是1;也就是说一个bit能存储的最多信息是2。
位图并不是一种特殊的数据结构,其实本质上是二进制字符串,也可以看做是 byte 数组。可以使用普通的 get/set 直接获取和设置整个位图的内容,也可以使用位图操作 getbit/setbit 等将 byte 数组看成「位数组」来处理。
位图的优势
- 基于最小的单位bit进行存储,所以非常省空间。
- 设置时候时间复杂度O(1)、读取时候时间复杂度O(n),操作是非常快的
- 二进制数据的存储,进行相关计算的时候非常快
- 方便扩容
一般可以在如下场景使用
- 用户签到
- 用户在线状态
- 统计活跃用户
- 各种状态值
常用命令
SETBIT
对 key 所储存的字符串值,设置或清除指定偏移量上的位(bit)。SETBIT key offset value
offset 参数必须大于或等于 0 ,小于 2^32 (bit 映射被限制在 512 MB 之内)。
GETBIT
对 key 所储存的字符串值,获取指定偏移量上的位(bit)。
1 | GETBIT key offset |
BITCOUNT
计算给定字符串中,被设置为 1 的比特位的数量。
1 | BITCOUNT key |
BITPOS
返回位图中第一个值为 bit 的二进制位的位置。
1 | BITPOS key bit[start][end] |
BITOP
对一个或多个保存二进制位的字符串 key 进行位元操作,并将结果保存到 destkey 上。
BITOP operation destkey key[key…]
operation 可以是 AND 、 OR 、 NOT 、 XOR 这四种操作中的任意一种 BITOP AND destkey key[key...]
,对一个或多个 key 求逻辑并,并将结果保存到 destkey 。
BITFIELD
bitfield 有三个子指令,分别是 get/set/incrby,它们都可以对指定位片段进行读写,但是最多只能处理 64 个连续的位,如果超过 64 位,就得使用多个子指令,bitfield 可以一次执行多个子指令。
适用于各类统计应用
记录用户的签到,每日在线情况等,可以将当天或者当天的偏移量对应的bit位设置为1即可,使用 BITCOUNT
可以轻松统计签到次数。
还有一种使用比较多的情况,就是设置各类状态值,例如商城的设置:是否可以评价订单,是否展示售罄商品,是否正常营业等状态值可以使用bitmap来存储
在性能方面,如前面提到的签到,即使运行 10 年,占用的空间也只是每个用户 10*365 比特位(bit),也即是每个用户 456 字节。对于这种大小的数据来说, BITCOUNT key [start] [end] 的处理速度就像 GET key 和 INCR key 这种 O(1) 复杂度的操作一样快。
当然如果你的 bitmap 数据非常大,那么可以考虑使用以下两种方法:
- 将一个大的 bitmap 分散到不同的 key 中,作为小的 bitmap 来处理。使用 Lua 脚本可以很方便地完成这一工作。
- 使用 BITCOUNT key [start] [end] 的 start 和 end 参数,每次只对所需的部分位进行计算,然后在进行累加。
HyperLogLog
简介
如果你要统计网站的PV,你可以使用Redis计数器就好了,每来一个请求,调用一次incrby
即可。但是如果要统计UV就没那么简单呢,它需要去重,当然你肯定想到了Redis中的去重的Set
集合,当一个请求过来使用sadd
添加用户ID,通过scard
取出集合的大小。但是如果上千万的UV,使用集合来统计,就非常浪费空间了。而Redis提供的HyperLogLog
数据结构正是来解决这类统计问题的,当然在数据量很大的情况下,他会有一定的误差。
HyperLogLog
算法是一种非常巧妙的近似统计海量去重元素数量的算法。它内部维护了 16384 个桶(bucket)来记录各自桶的元素数量。当一个元素到来时,它会散列到其中一个桶,以一定的概率影响这个桶的计数值。因为是概率算法,所以单个桶的计数值并不准确,但是将所有的桶计数值进行调合均值累加起来,结果就会非常接近真实的计数值。
具体的原理解析可参考探索HyperLogLog算法(https://www.jianshu.com/p/55defda6dcd2)
使用方法
HyperLogLog 使用比较简单,主要提供提供了两个指令
- pfadd 增加计数
- pfcount 获取计数
HyperLogLog还提供了第三个指令 pfmerge
,用于将多个 pf 计数值累加在一起形成一个新的 pf 值。
比如在网站中我们有两个内容差不多的页面,运营需要将两个页面的数据进行合并。其中页面的 UV 访问量也需要合并,这时候就可以使用pfmerge
。
pf 的内存只有12k
HyperLogLog 实现中用到的是 16384 个桶,也就是 2^14,每个桶的 maxbits 需要 6 个 bits 来存储,最大可以表示 maxbits=63,于是总共占用内存就是2^14 * 6 / 8 = 12k字节
布隆过滤器
简介
布隆过滤器可以理解为一个不怎么精确的 set 结构,当你使用它的 contains 方法判断某个对象是否存在时,它可能会误判。但是布隆过滤器也不是特别不精确,只要参数设置的合理,它的精确度可以控制的相对足够精确,只会有小小的误判概率。
当布隆过滤器说某个值存在时,这个值可能不存在;当它说不存在时,那就肯定不存在。打个比方,当它说不认识你时,肯定就不认识;当它说见过你时,可能根本就没见过面,不过因为你的脸跟它认识的人中某脸比较相似 (某些熟脸的系数组合),所以误判以前见过你。
套在上面的使用场景中,布隆过滤器能准确过滤掉那些已经看过的内容,那些没有看过的新内容,它也会过滤掉极小一部分 (误判),但是绝大多数新内容它都能准确识别。这样就可以完全保证推荐给用户的内容都是无重复的。
Redis 中的布隆过滤器
Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中,给 Redis 提供了强大的布隆去重功能。
下面我们来体验一下 Redis 4.0 的布隆过滤器,为了省去繁琐安装过程,我们直接用 Docker 吧。
1 | docker pull redislabs/rebloom # 拉取镜像 |
如果上面三条指令执行没有问题,下面就可以体验布隆过滤器了。
布隆过滤器基本使用
隆过滤器的基本命令
- bf.add 添加元素
- bf.exists 查询元素是否存在
- bf.madd 一次添加多个元素
- bf.mexists 一次查询多个元素是否存在
1 | 127.0.0.1:6379> bf.add codehole user1 |
我们上面使用的布隆过滤器只是默认参数的布隆过滤器,它在我们第一次 add 的时候自动创建。Redis 其实还提供了自定义参数的布隆过滤器,需要我们在 add 之前使用bf.reserve指令显式创建。如果对应的 key 已经存在,bf.reserve会报错。bf.reserve有三个参数,分别是 key, error_rate和initial_size。错误率越低,需要的空间越大。initial_size参数表示预计放入的元素数量,当实际数量超出这个数值时,误判率会上升。
所以需要提前设置一个较大的数值避免超出导致误判率升高。如果不使用 bf.reserve,默认的error_rate是 0.01,默认的initial_size是 100。
在 redis 中有两个值决定布隆过滤器的准确率:
- error_rate:允许布隆过滤器的错误率,这个值越低过滤器的位数组的大小越大,占用空间也就越大。
- initial_size:布隆过滤器可以储存的元素个数,当实际存储的元素个数超过这个值之后,过滤器的准确率会下降。
redis 中有一个命令可以来设置这两个值:
1 | bf.reserve test 0.01 100 |
- 第一个值是过滤器的名字。
- 第二个值为 error_rate 的值。
- 第三个值为 initial_size 的值。
注意必须在add之前使用bf.reserve指令显式创建,如果对应的 key 已经存在,bf.reserve会报错。同时设置的错误率越低,需要的空间越大。如果不使用 bf.reserve,默认的error_rate是 0.01,默认的initial_size是 100。
注意事项
布隆过滤器的initial_size估计的过大,会浪费存储空间,估计的过小,就会影响准确率,用户在使用之前一定要尽可能地精确估计好元素数量,还需要加上一定的冗余空间以避免实际元素可能会意外高出估计值很多。
布隆过滤器的error_rate越小,需要的存储空间就越大,对于不需要过于精确的场合,error_rate设置稍大一点也无伤大雅。比如在新闻去重上而言,误判率高一点只会让小部分文章不能让合适的人看到,文章的整体阅读量不会因为这点误判率就带来巨大的改变。
应用场景
在爬虫系统中,我们需要对 URL 进行去重,已经爬过的网页就可以不用爬了。但是 URL 太多了,几千万几个亿,如果用一个集合装下这些 URL 地址那是非常浪费空间的。这时候就可以考虑使用布隆过滤器。它可以大幅降低去重存储消耗,只不过也会使得爬虫系统错过少量的页面。
布隆过滤器在 NoSQL 数据库领域使用非常广泛,我们平时用到的 HBase、Cassandra 还有 LevelDB、RocksDB 内部都有布隆过滤器结构,布隆过滤器可以显著降低数据库的 IO 请求数量。当用户来查询某个 row 时,可以先通过内存中的布隆过滤器过滤掉大量不存在的 row 请求,然后再去磁盘进行查询。
邮箱系统的垃圾邮件过滤功能也普遍用到了布隆过滤器,因为用了这个过滤器,所以平时也会遇到某些正常的邮件被放进了垃圾邮件目录中,这个就是误判所致,概率很低