曝光去重设计与实践

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

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

一、明文id列表方案

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

这样设计的优点：

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

缺点也同样明显：

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

二、布隆过滤器方案

理论：

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

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

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

设计与实践：

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

设计：

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

实现代码示例

代码语言：txt复制

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上报的功能，平时不开启上报，当需要追踪某个用户曝光记录，则可以对该用户单独多增一套明文上报的功能即可，实现起来也不复杂。

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

大数据云数据库Redis 存储推荐系统

0 人点赞