推荐去重机制探索

发表于 | 分类于
推荐去重机制探索

推荐去重机制探索

背景

目前公司首页等瀑布流推荐中，用户已读文章历史是存放在Redis的List列表中，用户每天1个List。Redis控制其过期时间

代码可以控制取最近X天的已读历史。

取出X天的List已读历史后， 将其合并转化为集合， 判断候选池中M千篇文章是否在此集合中，

如果在集合中，则过滤，如果不在，则保留。

当前方案存在的问题

  1. redis中明文存储历史文章ID， 占用空间大，用户日活增多，内存增长显著
  2. 从List取出历史文章，需要转化为集合，这里存在转化效率问题，文章越多，效率越低

总结，即需要降低内存占用，提高查询效率

解决方案探讨

bloomfilter算法在去重场景有很好的应用， 网上该算法的文章比较多，这里不详细介绍。 总结特点如下：

  1. 占用空间小， 利用bitmap的0,1状态表述是否存在，比明文存储能节约很大空间
  2. 执行快， 预先使用HASH函数处理文章ID， 比较操作是O(1)

其存在几个关键的 变量

  1. 需预设去重集数量大小， 数量越大，占用空间越大
  2. 需预设准确率， 比如0.01, 允许1%的假阳性，即将不在数量集合中的 元素 误判为 在集合中， 导致多过滤， 如果需要的准确率越高， 则需要占用更多的空间
  3. hash函数个数， 此计算为cpu计算密集类型， hash函数越多，则占cpu越多，相应的，对占用空间则越不敏感

如果要将bloomfiler使用最大化，则需考虑以上1，2，3限制条件

本机压测分析

本机写了demo压测方案， 来评估1，2，3限制条件

这里使用JAVA程序自带的bloomfilter类库， 并没有使用redis的bloomfilter插件

因为redis并不擅长充分使用CPU多核，而bloomfilter恰好是计算密集型， 如果并发稍微过高，会把CPU打高

预设数据：

  1. 记录最近14天的用户历史数据
  2. 1个用户1天最多存储1000篇历史文章
  3. 待遍历的用户ID： 200个用户ID
  4. 候选池文章数: 2000篇文章

存在以下四种情况

  • 方案1: 每天1个Redis List记录历史数据， 查询总共耗时： 3782ms

此方案为当前线上方案

  • 方案2: 全部历史文章使用1个bloomfilter持久化， 查询总耗时： 385ms

此方案需要预设较大文章数， 占用较大的内存空间，使用不灵活，但是较List查询,耗时减少： 80%

  • 方案3: 每天1个Redis key记录序列化后的bloomfilter对象， 查询总共耗时: 3417ms

改动较小，把list调整为存储bloomfilter对象， 耗时减少：10%

  • 方案4: 使用10个bloomfiter对象，每个记录1400条历史数据，记录最多14000条数据， 查询总耗时, 2588ms， 耗时减少：30%

这种方案，调整了产品策略：

  1. 原来产品策略： 是说取最近14天的历史数据
  2. 现在的策略： 取用户最近浏览的 1.4万条历史数据。如果最近xx天没有新的历史数据，则删除原有历史数据

这里bloomfilter对象动态创建，如果最近只有1000条历史数据，则使用1个bloomfilter对象记录，则更能方便的控制其占用内存大小。

线上实际情况是，大部分用户很可能只有<1000条的历史数据，使用效果会更好

但其写入逻辑较复杂

其他

同事提供了另外一种思路:

今天的明文list + 昨天的明文list + （定时作业写入前: 前天N条bloomfiler对象 或者 定时作业写入后: 昨天N条bloomfiler对象）

但是这里

总结

  1. 方案四最佳，能做到省内存，提升查询效率，使用bloomfilter确实能有效提高查询效率， 但需要更好的和业务结合， 即不能预设太大条目，需要做到能动态扩展。

相关demo代码地址： https://github.com/l1905/bloom_demo

参考文章

  1. https://cloud.tencent.com/developer/article/1474247