导语:推荐系统中个性化推荐最为复杂,个性化推荐涉计到很多基础技术:用户画像,用户曝光记录,推荐算法策略等等,其中用户画像和用户曝光记录的设计好坏直接影响推荐系统的性能和效率,布隆过滤器应用到用户曝光记录,在存储和判断方面,有着非常明显的优势。本文结合自己的实践经验,简单介绍一下如何设计一个优雅的用户曝光记录功能。
为了过滤掉用户已经看过的内容,需要将已经推荐给用户的内容id存储起来,当再次推荐时,优先把已经推荐过的内容去重后在进行推荐,这样在用户看来,每次都是新内容。在我们实践的过程中先后使用了两种实现方案:明文id列表和布隆过滤器方案,下面做一下简单介绍。
最容易想到的方案就是给每个用户存储一个明文内容曝光id列表,然后结合缓存进行存储。这里我们选用redis作为存储,存储结构为list,单个用户的曝光列表如下:
布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。
一个简单的布隆过滤器原理如上图所示:
这里我不打算自己去实现一个布隆过滤器,因为开源的实现有很多,我们主要实现的语言是golang,经过调研对比,这个开源的实现比较简单和优雅:https://github.com/httpimp/bloomfilter
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 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。