专栏首页一诺千金曝光去重设计与实践
原创

曝光去重设计与实践

导语:推荐系统中个性化推荐最为复杂,个性化推荐涉计到很多基础技术:用户画像,用户曝光记录,推荐算法策略等等,其中用户画像和用户曝光记录的设计好坏直接影响推荐系统的性能和效率,布隆过滤器应用到用户曝光记录,在存储和判断方面,有着非常明显的优势。本文结合自己的实践经验,简单介绍一下如何设计一个优雅的用户曝光记录功能。

为了过滤掉用户已经看过的内容,需要将已经推荐给用户的内容id存储起来,当再次推荐时,优先把已经推荐过的内容去重后在进行推荐,这样在用户看来,每次都是新内容。在我们实践的过程中先后使用了两种实现方案:明文id列表和布隆过滤器方案,下面做一下简单介绍。

一、明文id列表方案

最容易想到的方案就是给每个用户存储一个明文内容曝光id列表,然后结合缓存进行存储。这里我们选用redis作为存储,存储结构为list,单个用户的曝光列表如下:

用户曝光列表

这样设计的优点:

  1. 明文内容id存储,对用户问题追查非常友好,可以非常直观的看到某个用户的推荐内容。
  2. 方便限制长度和更新淘汰,我们可以限制单个用户的曝光列表长度,一侧新增记录,如果超长从另外一次淘汰旧记录,这样能够最大限度的保证用户在一段时间内看到的新闻不重复,在结合新闻的时效性要求,能够基本达到用户永远看到的内容不重复。
  3. 易于实现,最基本的redis操作就能够完成设计。

缺点也同样明显:

  1. 存储空间大,一个文章id一般14个字节,如果限定记录条数为5000,每个用户大概需要70k左右的存储空间,100G大概也就能够存储100多万个用户记录。
  2. 比较效率方面,首先需要将列表转换成MAP结构,才能实现O(1)时间复杂度的判断文章是否曝光过,记录越大,转换效率越低。

二、布隆过滤器方案

理论:

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

布隆过滤器实现原理图

一个简单的布隆过滤器原理如上图所示:

  1. 假设某个用户第一次曝光文章id分别为x, y, z,那么先分配一块位数组并进行初始化,将每个位都设置为0.
  2. 假设映射函数个数为3,那么每个文章id依次通过3个映射函数进行映射,每次映射都会产生一个值,这个值对应位数组上面的一个点,然后将位数组对应的位置标记为1。
  3. 当有新的文章w需要判断是否已经曝光过,只需要将其以同样的映射函数映射到位数组上的三个点,如果有一个点不为1则该元素肯定没有曝光过,否则有可能曝光过。注意:判断的时候有一定的误判率,比如文章z映射之后在位数组的下标3,4,5这三个点,虽然都为1,但是它确实没有曝光过。

设计与实践:

这里我不打算自己去实现一个布隆过滤器,因为开源的实现有很多,我们主要实现的语言是golang,经过调研对比,这个开源的实现比较简单和优雅:https://github.com/httpimp/bloomfilter

设计:

  1. 根据我们实际的业务场景,对于用户曝光记录,不太可能无限制的增加,考虑到新闻的时效性,每个用户保留最近5000条曝光记录足矣,用户5天内没有新增曝光记录则记录淘汰,这样既能保证去重效果,又能节省资源,具体可根据自己业务场景而定。
  2. 5000条记录不能单独存在一个布隆块中,这样用户初始数据量太大,就算只曝光一条记录也需要分配足以容纳5000条记录的位数组,浪费严重,所以需要对其进行分片。
  3. 分片多少比较合适?这里需要兼顾性能和效率,片太小,需要维护的分片太多,最终比较的时候性能低;片太大,比较时效率高,但是初始资源占的多,浪费资源。最终我选择每块布隆过滤器容量为1000,最终用户可增加至5片布隆存储数据。
  4. 最终的设计方案如下图所示,以list形式将布隆过滤器数据块存储到redis,单块容量未超限时,更新最新的一块数据,否则新增新的布隆数据块,单个用户超出最大块数限制时,则对老的数据块进行裁剪:
    布隆过滤器数据分片设计
  5. 判断时将该用户所有的布隆数据块进行加载,并且生成对应数量的布隆过滤器,然后将需要判断的文章id与每个布隆过滤器进行对比,只要有一个命中,说明它已经曝光过,否则说明该文章未推荐给过该用户。

实现代码示例

const (
   bloomfilterNum = 5          //每个人允许布隆过滤器最大个数
   maxKeyNum = 1000            //单个布隆最多能存元素个数
   FalsePositives = 0.001      //误识别率
)

//设置曝光记录
func SetExposed(uid string, ids []string) (error)  {
   if len(uid) < 2 || len(ids) == 0 {
      return errors.New("params error")
   }
   //预估布隆数据块大小和映射函数个数
   numBits, numHashFunc := bloomfilter.EstimateParameters(maxKeyNum, FalsePositives)
   //用户曝光记录key
   key := uid
   //当前已经设置文章id数量
   num := 0
   //判断是否需要新增
   isNew := true
   //初始化一个布隆过滤器
   bf := bloomfilter.New(numBits, numHashFunc)
   rds := redis.New("local")
   exposedData, err := redis.String(rds.Do(nil, "LINDEX", key, 0))
   //如果已经有记录则先加载
   if err == nil && exposedData != ""{
      arr := strings.Split(exposedData, "::")
      if len(arr) == 2 {
         num,err = strconv.Atoi(arr[0])
         if err == nil && num+len(ids) < maxKeyNum+10{
            decoded, err := base64.StdEncoding.DecodeString(arr[1])
            if err == nil{
			  //加载已有曝光记录
               bf = bloomfilter.NewFromBytes(decoded, numHashFunc)
            }
            isNew = false
         }else{
            num = 0
         }
      }
   }

   //添加新的曝光记录
   for _,id := range ids{
      if !bf.Test([]byte(id)){
         bf.Add([]byte(id))
         num++
      }
   }
   //开头代表此块已用容量,格式:数量::bloomfilter的字符串
   encoded := fmt.Sprintf("%d::%s", num, base64.StdEncoding.EncodeToString(bf.ToBytes()))
   if encoded != exposedData{
      if isNew == true{
         rds.Do(nil, "LPUSH", key, encoded)
      }else{
         rds.Do(nil, "LSET", key, 0, encoded)
      }
      rds.Do(nil, "LTRIM", key, 0, bloomfilterNum-1)
      rds.Do(nil, "EXPIRE", key, 3600*24*bloomfilterNum)
   }
   return err
}

//获取曝光记录,返回布隆过滤器列表
func GetExposed(uid string) (bfs []*bloomfilter.BloomFilter, err error) {
   if len(uid) < 2 {
      return nil, errors.New("params error")
   }
   _, numHashFunc := bloomfilter.EstimateParameters(maxKeyNum, FalsePositives)
   //用户曝光记录key
   key := uid
   rds := redis.New("local")
   exposedData, err := redis.Strings(rds.Do(nil, "LRANGE", key, 0, bloomfilterNum-1))
   if err == nil{
      bfs = make([]*bloomfilter.BloomFilter, 0)
      for _,item := range exposedData {
         arr := strings.Split(item, "::")
         if len(arr) == 2 && arr[1] != ""{
            decoded, err := base64.StdEncoding.DecodeString(arr[1])
            if err == nil {
               bf := bloomfilter.NewFromBytes(decoded, numHashFunc)
               bfs = append(bfs, bf)
            }
         }
      }
      return bfs, err
   }

   return nil, err
}

// Exists 判断key是否已经曝光过
func Exists(bfs []*bloomfilter.BloomFilter, key string) bool {
	for _, bf := range bfs {
		if bf.Test([]byte(key)) {
			return true
		}
	}
	return false
}

三、最终效果数据对比

5000个文章id

明文id列表方案

布隆过滤器方案

单个用户最大存储空间

70k

10k

文章判断时间

0.57ms

0.18ms

可以看出无论是存储空间还是判断速度,布隆过滤器都远胜一筹。

四、后记

对于布隆过滤器不好直接查看用户已曝光列表的问题,我们可以设计一套明文id上报的功能,平时不开启上报,当需要追踪某个用户曝光记录,则可以对该用户单独多增一套明文上报的功能即可,实现起来也不复杂。

由于本人水平有限,设计和实现中难免会存在不足的地方,如果发现还望指正。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【计算摄影】图像美学专栏上线,先从学点摄影知识开始

    大家好,这是专栏《计算摄影》的第一篇文章,这一个专栏来自于计算机科学与摄影艺术的交叉学科。这是第一篇文章,本篇文章的重点不是技术,但却是一个很有意思的主题,也是...

    用户1508658
  • DeepFM在贝壳房源详情页推荐场景的实践

    上一篇文章《wide&deep 在贝壳推荐场景的实践[1]》中,我们介绍了贝壳首页推荐展位使用的 Wide & Deep 模型,本文向大家介绍贝壳房源详情页推荐...

    石晓文
  • 搜推实战-有内味了!

    在电商搜索中,例如淘宝,拼多多,京东等的搜索的场景往往是:用户A通过搜索框Query找到他/她想要购买的东西,然后搜索引擎通过某些算法策略返回一系列商品,用户再...

    炼丹笔记
  • 腾讯云+运维,助力运维领域技术发展

    在云计算时代和互联网持续高速发展的今天,数据和服务规模迅速升级,传统运维面临着许多新型挑战,如何结合DevOps理念,解决云计算时代的运维难题?

    云加社区
  • 通过自定义 Vue 指令实现前端曝光埋点

    互联网发展至今,数据的重要性已经不言而喻,尤其是在电商公司,数据的统计分析尤为重要,通过数据分析可以提升用户的购买体验,方便运营和产品调整销售策略等等。埋点就是...

    政采云前端团队
  • KDD 2020 | 多任务保量优化算法在优酷视频场景的实践

    导读:今天分享一下阿里优酷视频在KDD 2020上的一篇关于新热视频保量分发上的实践,建立了新热内容曝光敏感模型并给出了一种多目标优化保量的算法,推荐工业界实战...

    石晓文
  • 比赛 | 第三届腾讯广告算法大赛完美收官,20000 美金最终花落谁家?

    AI 科技评论按:7 月 8 日,2019 腾讯广告算法大赛「终极之战」在深圳腾讯滨海大厦顺利举行。经过三个月的激烈角逐,实力超强的 10 强决赛队伍从 105...

    AI研习社
  • CTR预估中GBDT与LR融合方案

    1背景 CTR预估,广告点击率(Click-Through Rate Prediction)是互联网计算广告中的关键环节,预估准确性直接影响公司广告收入。CTR...

    腾讯大数据
  • 推荐系统之眼

    这半个月除了工作上的事,一直忙于学习机器学习基础理论,每天背着四五本书上下班,还蛮有读书时的感觉。之前写了一篇文章,叫基于用户画像的实时异步化视频推荐系统,应该...

    用户2936994

扫码关注云+社区

领取腾讯云代金券