通过 Lua 脚本批量插入数据到布隆过滤器
有关布隆过滤器的原理之前写过一篇博客: 算法 (3)--- 布隆过滤器原理
在实际开发过程中经常会做的一步操作, 就是判断当前的 key 是否存在.
那这篇博客主要分为三部分:
, 几种方式判断当前 key 是否存在的性能进行比较.
,Redis 实现布隆过滤器并批量插入数据, 并判断当前 key 值是否存在.
, 针对以上做一个总结.
一, 性能对比
主要对以下方法进行性能测试比较:
1,List 的 contains 方法
2,Map 的 containsKey 方法
3,Google 布隆过滤器 mightContain 方法
前提准备
在 SpringBoot 项目启动的时候, 向 List 集合, Map 集合, Google 布隆过滤器 分布存储 500 万条, 长度为 32 位的 String 字符串.
1, 演示代码
- @Slf4j
- @RestController
- public class PerformanceController {
- /**
- * 存储 500 万条数据
- */
- public static final int SIZE = 5000000;
- /**
- * list 集合存储数据
- */
- public static List<String> list = Lists.newArrayListWithCapacity(SIZE);
- /**
- * map 集合存储数据
- */
- public static Map<String, Integer> map = Maps.newHashMapWithExpectedSize(SIZE);
- /**
- * guava 布隆过滤器
- */
- BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.unencodedCharsFunnel(), SIZE);
- /**
- * 用来校验的集合
- */
- public static List<String> exist = Lists.newArrayList();
- /**
- * 计时工具类
- */
- public static Stopwatch stopwatch = Stopwatch.createUnstarted();
- /**
- * 初始化数据
- */
- @PostConstruct
- public void insertData() {
- for (int i = 0; i <SIZE; i++) {
- String data = UUID.randomUUID().toString();
- data = data.replace("-", "");
- //1, 存入 list
- list.add(data);
- //2, 存入 map
- map.put(data, 0);
- //3, 存入本地布隆过滤器
- bloomFilter.put(data);
- // 校验数据 相当于从这 500 万条数据, 存储 5 条到这个集合中
- if (i % 1000000 == 0) {
- exist.add(data);
- }
- }
- }
- /**
- * 1,list 查看 value 是否存在 执行时间
- */
- @RequestMapping("/list")
- public void existsList() {
- // 计时开始
- stopwatch.start();
- for (String s : exist) {
- if (list.contains(s)) {
- log.info("list 集合存在该数据 ============= 数据 {}", s);
- }
- }
- // 计时结束
- stopwatch.stop();
- log.info("list 集合测试, 判断该元素集合中是否存在用时:{}", stopwatch.elapsed(MILLISECONDS));
- stopwatch.reset();
- }
- /**
- * 2, 查看 map 判断 k 值是否存在 执行时间
- */
- @RequestMapping("/map")
- public void existsMap() {
- // 计时开始
- stopwatch.start();
- for (String s : exist) {
- if (map.containsKey(s)) {
- log.info("map 集合存在该数据 ============= 数据 {}", s);
- }
- }
- // 计时结束
- stopwatch.stop();
- // 获取时间差
- log.info("map 集合测试, 判断该元素集合中是否存在用时:{}", stopwatch.elapsed(MILLISECONDS));
- stopwatch.reset();
- }
- /**
- * 3, 查看 guava 布隆过滤器 判断 value 值是否存在 执行时间
- */
- @RequestMapping("/bloom")
- public void existsBloom() {
- // 计时开始
- stopwatch.start();
- for (String s : exist) {
- if (bloomFilter.mightContain(s)) {
- log.info("guava 布隆过滤器存在该数据 ============= 数据 {}", s);
- }
- }
- // 计时结束
- stopwatch.stop();
- // 获取时间差
- log.info("bloom 集合测试, 判断该元素集合中是否存在用时:{}", stopwatch.elapsed(MILLISECONDS));
- stopwatch.reset();
- }
- }
2, 测试输出结果
测试结果
这里其实对每一个校验是否存在的方法都执行了 5 次, 如果算单次的话那么, 那么在 500 万条数据, 且每条数据长度为 32 位的 String 类型情况下, 可以大概得出.
,List 的 contains 方法执行所需时间, 大概 80 毫秒左右.
,Map 的 containsKey 方法执行所需时间, 不超过 1 毫秒.
,Google 布隆过滤器 mightContain 方法, 不超过 1 毫秒.
总结
Map 比 List 效率高的原因这里就不用多说, 没有想到的是它们速度都这么快. 我还测了 100 万条数据通过 list 遍历 key 时间竟然也不超过 1 毫秒. 这说明在实际开发过程中, 如果数据
量不大的话, 用哪里其实都差不多.
3, 占用内存分析
从上面的执行效率来看, Google 布隆过滤器 其实没什么优势可言, 确实如果数据量小, 完全通过上面就可以解决, 不需要考虑布隆过滤器, 但如果数据量巨大, 千万甚至亿级
别那种, 用集合肯定不行, 不是说执行效率不能接受, 而是占内存不能接受.
我们来算下 key 值为 32 字节的 500 万条条数据, 存放在 List 集合需要占多少内存.
500 万 * 32 = 16000000 字节 ≈ 152MB
一个集合就占这么大内存, 这点显然无法接受的.
那我们来算算布隆过滤器所需要占内存
设 bit 数组大小为 m, 样本数量为 n, 失误率为 p.
由题可知 n = 500 万, p = 3%(Google 布隆过滤器默认为 3%, 我们也可以修改)
通过公式求得:
m ≈ 16.7MB
是不是可以接收多了.
那么 Google 布隆过滤器也有很大缺点
, 每次项目启动都要重新将数据存入 Google 布隆过滤器, 消费额外的资源.
, 分布式集群部署架构中, 需要在每个集群节点都要存储一份相同数据到布隆过滤器中.
, 随着数据量的加大, 布隆过滤器也会占比较大的 JVM 内存, 显然也不够合理.
那么有个更好的解决办法, 就是用 Redis 作为分布式集群的布隆过滤器.
二, Redis 布隆过滤器
1,Redis 服务器搭建
如果你不是用 docker, 那么你需要先在服务器上部署 Redis, 然后单独安装支持 Redis 布隆过滤器的插件 rebloom.
如果你用过 docker 那么部署就非常简单了, 只需以下命令:
- docker pull redislabs/rebloom # 拉取镜像
- docker run -p 6379:6379 redislabs/rebloom # 运行容器
这样就安装成功了.
2,Lua 批量插入脚本
SpringBoot 完整代码我这里就不粘贴出来了, 文章最后我会把整个项目的 GitHub 地址附上, 这里就只讲下脚本的含义:
- bloomFilter-inster.lua
- local values = KEYS
- local bloomName = ARGV[1]
- local result_1
- for k,v in ipairs(values) do
- result_1 = Redis.call('BF.ADD',bloomName,v)
- end
- return result_1
1) 参数说明
这里的 KEYS 和 ARGV[1] 都是需要我们在 java 代码中传入, redisTemplate 有个方法
execute(RedisScript<T> script, List<K> keys, Object... args)
script 实体中中封装批量插入的 lua 脚本.
keys 对于脚本的 KEYS.
ARGV[1] 对于可变参数第一个, 如果输入多个可变参数, 可以可以通过 ARGV[2]..... 去获取.
2) 遍历
Lua 遍历脚本有两种方式一个是 ipairs, 另一个是 pairs 它们还是有差别的. 这里也不做展开, 下面有篇博客可以参考.
注意 Lua 的遍历和 java 中遍历还有有点区别的, 我们 java 中是从 0 开始, 而对于 Lua 脚本 k 是从 1 开始的.
3) 插入命令
BF.ADD 是往布隆过滤器中插入数据的命令, 插入成功返回 true.
3, 判断布隆过滤器元素是否存在 Lua 脚本
- bloomFilter-exist.lua
- local bloomName = KEYS[1]
- local value = KEYS[2]
- -- bloomFilter
- local result_1 = Redis.call('BF.EXISTS', bloomName, value)
- return result_1
从这里我们可以很明显看到, KEYS[1] 对于的是 keys 集合的 get(0) 位置, 所以说 Lua 遍历是从 1 开始的.
BF.EXISTS 是判断布隆过滤器中是否存在该数据命令, 存在返回 true.
4, 测试
我们来测下是否成功.
- @Slf4j
- @RestController
- public class RedisBloomFilterController {
- @Autowired
- private RedisService redisService;
- public static final String FILTER_NAME = "isMember";
- /**
- * 保存 数据到 Redis 布隆过滤器
- */
- @RequestMapping("/save-redis-bloom")
- public Object saveReidsBloom() {
- // 数据插入布隆过滤器
- List<String> exist = Lists.newArrayList("11111", "22222");
- Object object = redisService.addsLuaBloomFilter(FILTER_NAME, exist);
- log.info("保存是否成功 ====object:{}",object);
- return object;
- }
- /**
- * 查询 当前数据 Redis 布隆过滤器是否存在
- */
- @RequestMapping("/exists-redis-bloom")
- public void existsReidsBloom() {
- // 不存在输出
- if (!redisService.existsLuabloomFilter(FILTER_NAME, "00000")) {
- log.info("redis 布隆过滤器不存在该数据 ============= 数据 {}", "00000");
- }
- // 存在输出
- if (redisService.existsLuabloomFilter(FILTER_NAME, "11111")) {
- log.info("redis 布隆过滤器存在该数据 ============= 数据 {}", "11111");
- }
- }
- }
这里先调插入接口, 插入两条数据, 如果返回 true 则说明成功, 如果是同一个数据第一次插入返回成功, 第二次插入就会返回 false, 说明重复插入相同值会失败.
然后调查询接口, 这里应该两条日志都会输出, 因为上面 "00000" 是取反的, 多了个! 号.
我们来看最终结果.
符合我们的预期, 说明, Redis 布隆过滤器从部署到整合 SpringBoot 都是成功的.
三, 总结
下面个人对整个做一个总结吧. 主要是思考下, 在什么环境下可以考虑用以上哪种方式来判断该元素是否存在.
1, 数据量不大, 且不能有误差.
那么用 List 或者 Map 都可以, 虽然说 List 判断该元素是否存在采用的是遍历集合的方式, 在性能在会比 Map 差, 但就像上面测试一样, 100 万的数据,
List 遍历和 Map 都不超过 1 毫秒, 选谁不都一样, 何必在乎那 0. 几毫秒的差异.
2, 数据量不大, 且允许有误差.
这就可以考虑用 Google 布隆过滤器了, 尽管查询数据效率都差不多, 但关键是它可以减少内存的开销, 这就很关键.
3, 数据量大, 且不能有误差.
如果说数量大, 为了提升查询元素是否存在的效率, 而选用 Map 的话, 我觉得也不对, 因为如果数据量大, 所占内存也会更大, 所以我更推荐用
Redis 的 map 数据结构来存储数据, 这样可以大大减少 JVM 内存开销, 而且不需要每次重启都要往集合中存储数据.
4, 数据量大, 且允许有误差.
如果是单体应用, 数据量内存也可以接收, 那么可以考虑 Google 布隆过滤器, 因为它的查询速度会比 Redis 要快. 毕竟它不需要网络 IO 开销.
如果是分布式集群架构, 或者数据量非常大, 那么还是考虑用 Redis 布隆过滤器吧, 毕竟它不需要往每一节点都存储数据, 而且不占用 JVM 虚拟机内存.
GitHub 地址:
参考
1,Redis lua 官方文档 https://redis.io/commands/eval
2,Redis lua 中文翻译文档 http://redisdoc.com/script/eval.html#
3,Lua 泛型 for 遍历 table 时 ipairs 与 pairs 的区别 https://www.azimiao.com/2738.html
只要自己变优秀了, 其他的事情才会跟着好起来 (上将 10)
posted on 2019-07-28 16:09 雨点的名字 阅读 (...) 评论 (...) 编辑 收藏
来源: https://www.cnblogs.com/qdhxhz/p/11259078.html