电商中如何高效的判断某用户已参加了某活动?

JAVA herman 202浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xttblog,发送下载链接帮助你免费下载!
本博客日IP超过1800,PV 2600 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog,之前的微信号好友位已满,备注:返现
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领

看了这个话题,我相信很多人都会说,这还不简单。某用户参加了某优惠活动,购买了某商品等,数据库中肯定有对应记录吧。查询一下不久好了!

好吧,如果这是在面试中,你这样回答。game over,你肯定挂掉了。

我前面所有的文章,包括网上其他的一些文章,都在描述一件事,高并发场景下,一定要减少 DB 的访问。因为,压力一般都在 DB 端。所以,查询 DB,是一个非常笨的方法,而且很可能引起灾难性问题。

漏斗流量模型

从 Nginx 到 DB 数据库,流量是成漏斗型的,能访问到 DB 的,最终都是很少很少的请求,大部分请求都被过滤掉了,这一点你一定要清楚。

既然你说了不能用 DB,那我可以使用内存吧。内存很好高,HashSet 存储的元素不能重复,刚好可以利用。

但我要告诉你的是,HashSet 在数据规模小时是王者,随着数据规模增大,变青铜,到黑铁,最后是塑料,崩溃了!

假设现在有 1 亿的数据,下面的测试代码,大家自己去执行一下,我就不贴结果了。

@Test
public void hashSetTest(){
    long start = System.currentTimeMillis();
    Set<Integer> hashset = new HashSet(capacity);  // e.g. int capacity=100000
    for(int i=0; i<capacity; i++){hashset.add(i);}
    Assert.assertTrue(hashset.contains(1));
    long end = System.currentTimeMillis();
    System.out.println("执行时间:" + (end - start));
}

所以,在数据量很大的时候,HashSet 并不是一个很好的选择。比如,某知名面试题,直接问你,如何判断一个数是否在40亿个整数中?

如果你要使用 HashSet,则可能直接 Game over!

所以,有没有好办法呢?不知道布隆过滤器,大家有没有听说过。

布隆过滤器,英文叫 BloomFilter,可以说是一个二进制向量和一系列随机映射函数实现。 可以用于检索一个元素是否在一个集合中。

Bloom Filter 是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter 的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter 不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter 通过极少的错误换取了存储空间的极大节省。

布隆过滤器原理

布隆过滤器的原理很简单。有一组函数和一个位数组,每个元素经过这一组 hash 函数,得到第对应位为 1。比如,存储“xttblog”,经过 2 个哈希函数得出位数组的下标为 3 和 6。那么 3 和 6 下标的元素改为 1。再比如,存储“业余草”,经过这一组 hash 函数计算出位数组的下标为 6 和 10,那么 6 和 10 下标的元素改为 1。其他元素以此类推。

上面我这组 Hash 函数是有两个计算方法。实际使用中可以存在多个哈希函数,哈希函数越多,散列度越高,计算出来的误识别率相对也会低一些。这个大家可以自己去尝试,位数组的大小,哈希函数的多少,散列度都有些关系。
知道这个原理后,判断元素是否存在就很简单了。判断之前,先计算通过一组 Hash 函数,计算出哈希值,判断对应位数组中的元素全为 1,则这个元素一定存在。否则不存在。

布隆过滤器效率非常的高,被广泛的采用。网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统以及解决缓存穿透问题等,处处有它的影子。我们这里用来判断用户是否参加某个活动,是有一定的错误率的,但是影响不大。具体其他公司是否采用,和具体的业务也有一定的关系。

今天先不讲布隆过滤器的实现源码。我直接先来一个使用。Guava 工具包中有现成的实现,不再重复造轮子。

public static void main(String[] args) {
    BloomFilter<String> b = BloomFilter.create(
        Funnels.stringFunnel(Charset.forName("utf-8")), 
        1000, 0.000001);
    b.put("121");
    b.put("122");
    b.put("123");
    System.out.println(b.mightContain("12321"));
    BloomFilter<String> b1 = BloomFilter.create(
        Funnels.stringFunnel(Charset.forName("utf-8")), 
        1000, 0.000001);
    b1.put("aba");
    b1.put("abb");
    b1.put("abc");
    b1.putAll(b);
    System.out.println(b1.mightContain("123"));
}

使用 Guava 有一个缺陷就是分布式系统下,不太好用。所以,Redis 中有一个高级模块 RedisBloom。使用它需要先安装它。

git clone https://github.com/RedisBloom/RedisBloom.git
cd RedisBloom
make //编译 会生成一个rebloom.so文件
redis-server --loadmodule /path/to/rebloom.so
redis-cli -h 127.0.0.1 -p 6379

这个模块不仅仅实现了布隆过滤器,还实现了 CuckooFilter(布谷鸟过滤器),以及 TopK 功能。今天主要说布隆过滤器。安装好后,使用很简单,测试代码如下:

127.0.0.1:6379> bf.add xttblog u01
(integer) 1
127.0.0.1:6379> bf.add xttblog u02
(integer) 1
127.0.0.1:6379> bf.add xttblog u03
(integer) 1
127.0.0.1:6379> bf.exists xttblog u01
(integer) 1
127.0.0.1:6379> bf.exists xttblog u02
(integer) 1
127.0.0.1:6379> bf.exists xttblog u03
(integer) 1
127.0.0.1:6379> bf.exists xttblog u04
(integer) 0
127.0.0.1:6379> bf.madd xttblog u05 u06 u07
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists xttblog u05 u06 u07 u08
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0

上面用到的几个命令,解释一下:

  • bf.add 添加元素到布隆过滤器
  • bf.exists 判断元素是否在布隆过滤器
  • bf.madd 添加多个元素到布隆过滤器,bf.add只能添加一个
  • bf.mexists 判断多个元素是否在布隆过滤器

更多相关功能,建议大家到 Redis 官网学习。喜欢本文的,动动手指,谢谢!

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加QQ1群:135430763(2000人群已满),QQ2群:454796847(已满),QQ3群:187424846(已满)。QQ群进群密码:xttblog,想加微信群的朋友,之前的微信号好友已满,请加博主新的微信号:xttblog,备注:“xttblog”,添加博主微信拉你进群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作可添加助理微信进行沟通!

本文原文出处:业余草: » 电商中如何高效的判断某用户已参加了某活动?