飞腾公司：基于飞腾芯片的服务器首次入围中国移动、中国电信集中采购
06-06
简介：个性化推荐是推荐系统中最复杂的。个性化推荐涉及到很多基础技术：用户画像、用户曝光记录、推荐算法策略等，其中用户画像和用户曝光记录设计的好坏直接影响推荐系统的性能和效率。
布隆过滤器应用于用户曝光记录，在存储和判断方面具有非常明显的优势。本文结合自己的实践经验，简单介绍一下如何设计一个优雅的用户曝光记录功能。
为了过滤掉用户已经看过的内容，需要存储已经推荐给用户的内容的ID。当再次推荐时，会优先推荐已经推荐过的内容，这样从用户的角度来看，每次都是一样的。
是新内容。在我们的实践中，我们使用了两种实现方案：明文ID列表和布隆过滤器方案。
下面我们就来简单介绍一下。 1、纯文本ID列表解决方案 最容易想到的解决方案就是为每个用户存储一个纯文本内容曝光ID列表，然后结合缓存进行存储。
这里我们选择redis作为存储，存储结构为list，单个用户的暴露列表如下： 这样设计用户暴露列表的优点：纯文本内容id存储，对用户问题追溯非常友好，并且可以非常直观的看到某个用户的推荐内容。方便限制长度和更新淘汰。
我们可以限制单个用户的曝光列表的长度，在一侧添加新记录，如果太长则从另一侧淘汰旧记录。这样可以最大程度保证用户在一段时间内看到的新闻不重复。
，结合新闻的时效性要求，基本可以保证用户永远看到的内容不重复。易于实现，最基本的redis操作即可完成设计。
缺点也很明显：存储空间大，一篇文章ID一般为14字节。如果限制记录数的话，每个用户大约需要70k的存储空间，G大概可以存储几万条用户记录。
从比较效率上来说，首先需要将列表转换为MAP结构，达到O(1)的时间复杂度来判断一篇文章是否被曝光。记录越大，转换效率越低。
2、布隆过滤器方案理论：布隆过滤器（英文：Bloom Filter）是Bloom在2006年提出的，它实际上是一个长的二进制向量和一系列随机映射函数。布隆过滤器可用于检索元素是否在集合中。
它的优点是空间效率和查询时间比一般算法高很多，但缺点是有一定的误识别率和删除困难。布隆过滤器实现原理图 一个简单的布隆过滤器原理如上图所示：假设用户第一次接触到的文章ID是x、y、z，那么首先分配一个位数组并初始化，然后将每个位设置为0。
假设映射函数的数量为3，则每个文章ID依次通过3个映射函数进行映射。每次映射都会产生一个值，该值对应于位数组上的一个点，然后将该位数组中对应的位置标记为1。
当有新的文章w需要判断是否已经曝光时，只需要使用相同的映射函数映射到位数组上的三个点。如果有一点不为1，则该元素一定没有暴露过，否则可能会暴露。
经过。注：判断时存在一定的误判率。
比如文章z映射后，bit数组的三个下标3、4、5都为1，但确实还没有暴露出来。设计与实践：我不打算在这里自己实现布隆过滤器，因为有很多开源实现。
我们的主要实现语言是golang。经过研究和比较，这个开源实现比较简单优雅：(bloomfilterNum = 5 //每人允许的布隆过滤器最大数量 maxKeyNum = //单个布隆可以存储的最大元素数量 FalsePositives = 0. //误识别率) //设置曝光记录 func SetExpose(uid string, ids []string) (error) { if len(uid) < 2 || len(ids) == 0 { returnErrors.New("params error") } //预估Bloom数据块大小和映射函数个数 numBits, numHashFunc:=bloomfilter.EstimateParameters(maxKeyNum, FalsePositives) //用户曝光记录key key := uid //当前设置的文章id数量 num := 0 //判断是否需要新增 isNew := true //初始化一个布隆过滤器 bf :=bloomfilter.New(numBits, numHashFunc) rds := redis.New("local") ExposureData, err := redis.String(rds.Do(nil, "LINDEX", key, 0)) //如果已有记录的话，先加载 if err == nil && exposeData != ""{ arr := strings.Split(exposeData, "::") if len(arr) == 2 { num,err = strconv.Atoi(arr[ 0]) if err == nil && num +len(ids) < 最大值KeyNum{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的字符串编码:= fmt.Sprintf("%d::%s", num, base64.StdEncoding.EncodeToString(bf.ToBytes())) 如果编码!=暴露数据{ if isNew == true{ rds.Do(nil, "LPUSH", key, 编码) }else{ rds.Do(nil, "LSET", key, 0, 编码) } rds.Do(nil, "LTRIM ", key, 0,bloomfilterNum-1) rds.Do(nil, "EXPIRE", key, *24*bloomfilterNum) } return err}//获取曝光记录并返回bloomfilter列表 func GetExposed(uid string ) ( bfs []*bloomfilter.BloomFilter, err 错误) { if len(uid) <2 { return nil,errors.New("params error") } _, numHashFunc :=bloomfilter.EstimateParameters(maxKeyNum, FalsePositives) //用户曝光记录密钥 key := uid rds := redis.New("local")exposeData , err := redis.Strings(rds.Do(nil, "LRANGE", key, 0,bloomfilterNum-1)) if err == nil{ bfs = make([]*bloomfilter.BloomFilter, 0) for _,item := 范围暴露数据 { arr := strings.Split(item, "::") if len(arr) == 2 && arr[1] != ""{ 解码, err := base64.StdEncoding.DecodeString(arr[ 1]) if err == nil { bf :=bloomfilter.NewFromBytes(decoded, numHashFunc) bfs =append(bfs, bf) } } } return bfs, err } return nil, err}//判断key是否已存在暴露 func Exists(bfs []*bloomfilter.BloomFilter, key string) bool {for _, bf := range bfs {if bf.Test([]byte(key)) {return true}}return false} 3、最终效果数据 比较文章 ID 纯文本ID列表方案 布隆过滤器方案 单用户最大存储空间 70k10k 文章判断时间 0.57ms 0.18ms 可以看出，布隆过滤器在存储空间和判断速度上都远远优越。
后记对布隆过滤器不好 要直接查看用户的暴露列表，我们可以设计一套明文ID上报功能。平时不开启举报功能。
当我们需要跟踪用户的暴露记录时，我们可以为该用户添加一组单独的明文报告功能。 ，实现起来并不复杂。
由于本人水平有限，在设计和实现上难免存在不足之处。如果您发现任何问题，请纠正我。
版权声明：本文内容由互联网用户自发贡献，本站不拥有所有权，不承担相关法律责任。如果发现本站有涉嫌抄袭的内容，欢迎发送邮件 举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。
标签：
相关文章
06-21
06-18
06-17
06-06
06-17
最新文章
【玩转GPU】ControlNet初学者生存指南
【实战】获取小程序中用户的城市信息（附源码）
包雪雪简单介绍Vue.js：开学
Go进阶：使用Gin框架简单实现服务端渲染
线程池介绍及实际案例分享
JMeter 注释 18 - JMeter 常用配置组件介绍
基于Sentry的大数据权限解决方案
【云+社区年度征文集】GPE监控介绍及使用