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

曝光去重设计与实践

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

为了过滤掉用户已经看过的内容,需要将已经推荐给用户的内容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上报的功能,平时不开启上报,当需要追踪某个用户曝光记录,则可以对该用户单独多增一套明文上报的功能即可,实现起来也不复杂。

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

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

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

登录 后参与评论
0 条评论

相关文章

  • loadrunner 场景设计-设计与实践

    说明:任务分布主要是基于时间的考虑,当然也可能是地区之类的,如果是基于时间即高峰期,则,可以通过场景中的持续时间设置,选择运行一段时间来模拟

    授客
  • vivo 短视频推荐去重服务的设计实践

    vivo短视频在视频推荐时需要对用户已经看过的视频进行过滤去重,避免给用户重复推荐同一个视频影响体验。在一次推荐请求处理流程中,会基于用户兴趣进行视频召回,大约...

    2020labs小助手
  • RocketMQ 设计原理与最佳实践

    RocketMQ 是一款开源的分布式消息系统,基于高可用分布式集群技术,提供低延时的、高可靠的消息发布与订阅服务。同时,广泛应用于多个领域,包括异步通信解耦、企...

    Java识堂
  • 服务API版本设计与实践

    下面为应用商店从百万日活到几千万日活的发展历程。应用商店客户端经历了大大小小上百个版本迭代后,服务端也在架构上完成了单体到服务集群、微服务升级。

    常见_youmen
  • 产品设计方法与实践

    作者:hedyse,腾讯高级产品经理 |导语 方法,行事之条理,指为获得某种东西或达到某种目的而采取的手段与行为方式。对产品经理而言,产品是什么角色,有怎样的...

    腾讯大讲堂
  • 开源SOC的设计与实践

    开源日志系统分析很常见, 现在基于开源中间件可以很有效的搭建日志中心,处理各种数据的收集与分析。 日志系统也是信息系统,从软件工程的角度来看和一般的信息系统有很...

    FB客服
  • 服务降级的设计与实践

    当服务整体负载超出预设的上限阈值或即将到来的流量顶,即将会超过预设阈值时,为了保证重要或基本的服务能正常运行,拒绝部分请求或者将一些不重要,[断句]不紧急的服务...

    彼岸舞
  • HBase RowKey 设计与查询实践

    HBase 作为一款分布式的NoSQL数据库,数据的分布根据rowKey range方式来划分,每个Region 存储了一定范围rowKey 的数据, 数据的读...

    Flink实战剖析
  • 智能风控系统设计与实践

    在主流互联网产品中,比如搜索和推荐的系统,为了挖掘用户潜在购买需求,缩短用户到商品或信息的距离,提高用户的使用体验,都需要使用大量的特征来刻画用户的行为。在信息...

    肉眼品世界
  • 服务API版本控制设计与实践

    笔者曾负责vivo应用商店服务器开发,有幸见证应用商店从百万日活到几千万日活的发展历程。应用商店客户端经历了大大小小上百个版本迭代后,服务端也在架构上完成了单体...

    2020labs小助手
  • 微前端的设计理念与实践初探

    微服务与微前端,都是希望将某个单一的单体应用,转化为多个可以独立运行、独立开发、独立部署、独立维护的服务或者应用的聚合,从而满足业务快速变化及分布式多团队并行开...

    王下邀月熊
  • 亿级用户中心的设计与实践

    用户中心,顾名思义就是管理用户的地方,几乎是所有互联网公司最为核心的子系统之一。它的核心功能是登录与注册,主要功能是修改密码、换绑手机号码、获取用户信息、修改用...

    2020labs小助手
  • 分布式事物的设计与实践

    这就是分布式事物问题,当APP要买东西,这个操作会涉及到多个服务,意味着要操作多个数据库,这样本地事物就无法保证数据的一致性,所以就产生了分布式事物问题.

    彼岸舞
  • JavaScript设计模式与开发实践 - 策略模式

    引言 本文摘自《JavaScript设计模式与开发实践》 在现实中,很多时候也有多种途径到达同一个目的地。比如我们要去某个地方旅游,可以根据具体的实际情况来选择...

    laixiangran
  • JavaScript设计模式与开发实践(图灵原创)

    本书是根据JavaScript语言的特性专门针对JavaScript语言全面总结的设计模式。全书共分为三个部分,一部分讲解了JavaScript语言面向对象和函...

    用户3157710
  • Scrapy分布式、去重增量爬虫的开发与设计

    分布式采用主从结构设置一个Master服务器和多个Slave服务器,Master端管理Redis数据库和分发下载任务,Slave部署Scrapy爬虫提取网页和解...

    机器学习AI算法工程
  • 设计模式之单例模式与场景实践

    单例介绍 上次总结了设计模式中的module模式,可能没有真真正正的使用在场景中,发现效果并不好,想要使用起来却不那么得心应手, 所以这次我打算换一种方式~~从...

    okaychen
  • JavaScript设计模式与开发实践 - 单例模式

    引言 本文摘自《JavaScript设计模式与开发实践》 在传统开发工程师眼里,单例就是保证一个类只有一个实例,实现的方法一般是先判断实例存在与否,如果存在直接...

    laixiangran

扫码关注腾讯云开发者

领取腾讯云代金券