记一次Redis实现布隆过滤器的优化实践

背景

业务方需要实现一个曝光去重的功能，决定采用布隆过滤器，又因为是多节点应用，为保证数据一致性，通过Redis实现。本文记录下开发时的思路，以及优化过程。

初次实现

Redis4.0以上对布隆进行了插件支持，可以用特定的指令进行元素添加和判重，但考虑到不是所有环境的Redis都支持插件安装，以及违背死磕精神，决定自行实现。

第一版的实现使用Guava的BloomFilter进行hash操作，redis通过String类型存放bit数组。

估算空间

在实现业务前，估算大致需要插入的元素以及能接受的误判率，来计算预计需要的空间（引用Guava中的方法）。

 /** * @param n 预计插入的元素 * @param p 误判率（0 < p < 1） */ long optimalNumOfBits(long n, double p) { if (p == 0) {  p = Double.MIN_VALUE; } return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2))); }

例如我们预计插入500个元素，误判率取千分之三，输入到函数中得到 6045 ，即6045 bit = 755.625 B = 0.73 KB ， 当然在Redis中数据结构还有额外存储，所以结果仅供参考。

Setbit & Getbit

布隆的Hash算法有很多，例如MURMUR128_MITZ_32，算法实现此处不赘述，可以google一下，经过数次hash后得到下标数组，储存着元素映射到数组的下标。

判重：

 for (int i : offset) {  if (!redisTemplate.opsForValue().getBit(key, i)){   return false;  } } return true;

添加：

 for (int i : offset) {  redisTemplate.opsForValue().setBit(key, i, true); }

至此，布隆就实现完毕了。

Pipeline

虽然getbit和setbit都是O(1)操作，然而每个元素的 添加/判重 都需要进行数次setbit，其次数与插入量和布隆过滤器长度相关：

 /**  * @param n 预估插入量  * @param m 布隆过滤器长度  */ int optimalNumOfHashFunctions(long n, long m) {  return Math.max(1, (int) Math.round((double) m / n * Math.log(2))); }

取上文中的6045bit以及500个预估插入，进行代入得到操作次数 = 5。

每 添加/判重 1个元素就需要进行 5 次bit操作，这期间建立了5次TCP连接，显然对通道造成浪费，我们用redis pipeline优化一下～

添加：

 redisTemplate.executePipelined((RedisCallback) connection -> {  for (int i : offset) {   connection.setBit(redisTemplate.getKeySerializer().serialize(key), i, true);  }  return null; });

判重：

 List<Boolean> list = redisTemplate.executePipelined((RedisCallback) connection -> {  for (int i : offset) {   connection.getBit(redisTemplate.getKeySerializer().serialize(key), i);  }  return null; }); List<List<Boolean>> valuePairs = Lists.partition(list, numHashFunctions); Map<R, Boolean> result = Maps.newHashMapWithExpectedSize(values.size()); for (int i = 0; i < values.size(); i++) {  R v = values.get(i);  result.put(v, valuePairs.get(i).stream().reduce(true, Boolean::logicalAnd)); } return result;

同时笔者将方法改造成可批量判重元素的形式，将结果集按操作次数拆分成数个子集（pipeline返回的结果集是有序的，这点很重要），每个子集各自累加，最终得到一张[元素:是否存在]的Map。

实测pipeline化后速度提升了不少，不过还没完。

bitfield

bit操作快，但请求次数也多，在上述pipeline上线后，redis在业务高峰时qps有明显的上升。

set/get bit每次只能操作单个bit位。是否可以一条命令操作完成多个bit位的操作？

BITFIELD

BITFIELD key [GET type offset] [SET type offset value] [INCRBY type offset increment] [OVERFLOW WRAP|SAT|FAIL]

BITFIELD 命令可以将一个 Redis 字符串看作是一个由二进制位组成的数组， 并对这个数组中任意偏移进行访问。

BITFIELD可以指定多个子命令，有 get/set/incr 三种操作类型，可以在一条命令中完成复合操作，并返回结果集，当然命令的执行速度取决于由多少个子命令组成。

Redis官方解释开发bitfield的动机是为了方便操作bitmap，但不妨碍我们在布隆过滤器中使用它。

添加：

 BitFieldSubCommands commands = BitFieldSubCommands.create(); for (int i : offset) {  commands.set(BitFieldSubCommands.BitFieldType.unsigned(1))     .valueAt(i)     .to(1); } redisTemplate.opsForValue().bitField(key, commands);

注意在定义子命令时要声明操作数的长度，指定为无符号1位即可。

判重：

 BitFieldSubCommands commands = BitFieldSubCommands.create(); for (int i : offset) {  commands.get(BitFieldSubCommands.BitFieldType.unsigned(1))    .valueAt(i); } List<Long> result = redisTemplate.opsForValue().bitField(key, commands);

判重时对结果集的处理同pipeline。

使用bitfield后，经测试高qps现象有明显改善，但对cpu改善不大，因为redis内部执行的bit操作并没有减少。

原文转载：http://www.shaoqun.com/a/527574.html

跨境电商：https://www.ikjzd.com/

transfer：https://www.ikjzd.com/w/1735

电霸：https://www.ikjzd.com/w/2597

背景业务方需要实现一个曝光去重的功能，决定采用布隆过滤器，又因为是多节点应用，为保证数据一致性，通过Redis实现。本文记录下开发时的思路，以及优化过程。初次实现Redis4.0以上对布隆进行了插件支持，可以用特定的指令进行元素添加和判重，但考虑到不是所有环境的Redis都支持插件安装，以及违背死磕精神，决定自行实现。第一版的实现使用Guava的BloomFilter进行hash操作，redis通
cbo：cbo
logo免费制作：logo免费制作
新手做亚马逊都有哪些坑？：新手做亚马逊都有哪些坑？
速卖通新手怎么运营？方向搞对了吗？：速卖通新手怎么运营？方向搞对了吗？
快速打造爆款，是如何做到的？：快速打造爆款，是如何做到的？