Redis布隆过滤器实战

寻衅滋事？先过了我这道关

简介：布隆过滤器是什么，一定要用吗?

• 黑客流量攻击：故意访问不存在的数据，导致程序不断访问DB数据库的数据

• 黑客安全阻截：当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉

• 思考：如果让你实现这个功能你会怎么做？ key：10000 10001 10002 10003 大集合，key是否在集合里面

• 温故而知新：分析java常用数据结构复习 set map key,value list 有序get[0]、get[1]；

• list.contain (key)遍历数据，进行equals()比较，性能小

• set.contain(key) hashcode比较，性能较高，64位 1G

• map.get(key) hashcode比较，性能还行

• 概念：

  • 布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

• 优点:

  • 相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数（{\displaystyle O(k)}[图片上传失败...(image-1a8497-1636171354952)]

    ）。另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势

• 缺点

  • 但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣

布隆过滤器

简介：布隆过滤器是什么，一定要用吗?

布隆过滤器

• 布隆过滤器的其他使用场景

• 网页爬虫对URL的去重，避免爬取相同的URL地址；

  反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱（同理，垃圾短信）；

  缓存击穿，将已存在的缓存放到布隆中，当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。

• 布隆过滤器实现原理图解

布隆过滤器原理

谷歌布隆过滤器实现会员转盘抽奖

简介：抽奖程序功能需求分析，谷歌实现布隆过滤器，谷歌布隆过滤器的局限性

谷歌布隆过滤器抽奖图示

• 需求分析步骤

  • 互联网功能需求分析

    • 这是一个抽奖程序，只针对会员用户有效

  • 抽离出功能所有api

  • 制定存储方案

  • 性能优化方案分析

• 成型互联网产品用户量上千万，日常百万，怎么做到高性能非会员过滤

• 这是一个布隆过滤器的经典使用场景

• 通过google布隆过滤器存储会员数据实战

  • 程序启动时将数据放入内存中
  • google自动创建布隆过滤器
  • 用户ID进来之后判断是否是会员

• 代码演练

   CREATE TABLE `sys_user` (
      `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
      `user_name` varchar(11) CHARACTER SET utf8mb4 DEFAULT NULL COMMENT '用户名',
      `image` varchar(11) CHARACTER SET utf8mb4 DEFAULT NULL COMMENT '用户头像',
      PRIMARY KEY (`id`)
    ) ENGINE=InnoDB AUTO_INCREMENT=11 DEFAULT CHARSET=utf8;

代码：

引入guava包 加载的时候将用户ID加入到布隆过滤器 数据库现有数据 验证API 1-10的用户ID正常，其他位false

goole布隆过滤器与Redis布隆过滤器

简介：布隆过滤器两种实现方案的优缺点分析

• google布隆过滤器的缺陷与思考

  • 基于内存布隆过滤器有什么特点
  • 内存级别产物
  • 重启即失效
  • 本地内存无法用在分布式场景
  • 不支持大数据量存储

• 需求分析步骤

  • 互联网功能需求分析

    • 这是一个抽奖程序，只针对会员用户有效

  • 抽离出功能所有api

  • 制定存储方案

  • 性能优化方案分析

• Redis布隆过滤器

  • 可扩展性Bloom过滤器

    • 一旦Bloom过滤器达到容量，就会在其上创建一个新的过滤器

  • 不存在重启即失效或者定时任务维护的成本

    • 基于goole实现的布隆过滤器需要启动之后初始化布隆过滤器

  • 缺点：

    • 需要网络IO,性能比基于内存的过滤器低

• 选择:

  优先基于数据量进行考虑

Redis布隆过滤器安装

简介：

• Redis布隆过滤器安装过程 自己构建一个bitMap

  • git在centos7下面的安装

        1、安装git，直接使用yum安装即可：

        yum -y install git

        2、创建git用户，git用户可以正常通过ssh使用git，但无法登录shell，因为我们为git用户指定的git-shell每次一登录就自动退出。

        useradd -m -d /home/git -s /usr/bin/git-shell git

        3、初始化git仓库

        mkdir -p /data/git

        cd /data/git

        git init --bare project1.git

        chown git.git project1.git -R

        4、创建免密钥

        cd /home/git

        mkdir .ssh

        chmod 700 .ssh

        touch .ssh/authorized_keys

        chmod 600 .ssh/authorized_keys

        chown git.git .ssh -R

*   您应该首先下载并编译模块：

$ git clone git：//github.com/RedisLabsModules/rebloom
$ cd rebloom
$ make

*   将Rebloom加载到Redis中，在redis.conf里面添加

loadmodule /path/to/rebloom.so

*   命令实战

BF.ADD bloom redis
BF.EXISTS bloom redis
BF.EXISTS bloom nonxist

redis添加过滤器和测试

Redis布隆过滤器与springboot的整合探索

简介：基于lua脚本实现springboot和布隆过滤器的整合

• 通过普通命令无法实现springboot整合布隆过滤器

• 查找github开源框架的流程

• 分析开源框架的实现原理

• 通过lua脚本自己实现布隆过滤器

添加 判断是否存在

验证代码：

redis bloom验证代码

• 编写两个lua脚本

  • 添加数据到指定名称的布隆过滤器
  • 从指定名称的布隆过滤器获取key是否存在的脚本

添加布隆过滤器脚本

关于redis bloom的java实现：https://github.com/RedisBloom/JRedisBloom