推荐系统去重方案

去重分析概述

业务维度

推荐系统的去重从业务来分析，分为社交和电商，对于社交来讲比如抖音和微博用户经常刷到相同的 item,对用户体验较差。但对于电商来讲，因为item 有限，可以适当推荐重复商品，而对于去重要求没有社交的要求高，比如可以考虑复购去重。高曝光过滤等。对于点击和复购可能还会重复推荐，促进用户购买。所以电商的去重在工程上实现相对简单。

而对于社交来讲，用户曝光过的item就要考虑过滤，比如抖音，掘金的item. 等，本文主要针对社交去重的工程实现方案。

内容维度

内容维度的去重包括生产端去重和消费端去重，所谓生产端去重即内容的生产去重，电商业务一般由平台上架商品，一般不会上架上相同的SKU,但对于社交来讲一般都是UGC形式，可能产生大量重复内容。一般用户的去重是simhash，相似度90%以上，大概率是抄袭，不允许发布。相对来讲生产端去重技术实现相对简单。

而对于消费端去重，即指用户是消费内容时，不要看到重复的内容，相对生产的内容去重，消费内容去重相对复杂，尤其是社交产品。

功能维度

从功能层面，可以分成历史曝光去重和相似曝光去重两部分。所谓历史曝光去重，即不让用户看到完全相同的item.相似爆光去重指的是不应让用户看到相似的item。对于社交来讲历史曝光去重非常重要，尤其刚刚刷到的内容重复推荐，对于用户体验来讲是非常不好的。

综上分析，我们重点分析社交的消费端的历史曝光去重和相似爆光去重！

历史爆光去重

我们知道一般推荐分为召回、过滤、粗排和精排。那去重一般放在哪个阶段比较合适呢？

优点：从源头去重，保证效率。

缺点：一般推荐系统都是多路召回，那么每一路都需要去重，成本较大。

优点：过滤逻辑可以在多路聚合去重后，再进行曝光过滤，效率较高，而且工程实现简单，业务集中，好维护！

缺点：即召回的有效性，即有可能大部分都被过滤掉了，这个可能通过用户历史记录的大小来确定召回的item 数：比如用户已经看到200条，我们可以召回500条。如果用户没有历史记录，我们可以召回200条！

也有人建议在召回索引中线下去重，因为每个人的曝光数据不同，这个存储成本会非常大，不可取！

实现方案

历史记录

这种方案简单暴力，比如直接用redis 的order set,field 为item id，value为访问的时间戮，尤其item id一般int. 值，所以相对来说数据量不大。我们一般会对重复曝光的数据做限制：根据用户的访问频率，实现曝光历史记录的淘汰，比如最近N天和最大N条，只要满足其中一条限制，即淘汰，结合召回时的时间限制去重！（比如召回只召回近N天的热门文章）

Bloom 过滤

以上历史记录的方式，对于小规模系统来讲能够解决大部分问题，但对于象抖音这种大系统，每天的访问量较大，虽然通过id过滤，但大量用户会占用较大空间，所以采用bloom过滤以节省空间。关于布隆过滤的源码分析

布隆过滤器 基本原理及源码分析

关于使用bloom 过滤的挑战

数据的淘汰？

因为用户曝光浏览的数据会持续递增，而bloom 过滤不支持删除功能，所以到一定量之后就需要重建，重建过程会影响用户的访问体验，而且有实现成本。那么如何通过bloom 过滤实现淘汰呢？

我们分多个小bloom filter 块，组成一个bloom filter 链接，按小块淘汰。如下图所示：

每个小bloom filter 块分为mata 区和data 区，data 好理解，就是bitmap. （redis 的key）。

Mata 区作为元数据，包括以下信息：

• count 个数，保存的item数
• start_time 开始时间，即布隆的创建时间
• last_time 结束时间，即更新时间
• Resv 保留使用

根据start_time /last_time 判断是否需要淘汰。

关于验重的性能

去重时可以直接拿item 的生成时间和last_time 比较，如果大于last_time说明用户访问时，该item 还未生成，不可能有访问记录！减少匹配次数。

曝光回收

用户的曝光记录，有两种场景，其一是接口返回时，另一种是用户实际曝光时。而用户实际曝光一般会有延迟。有可能在用户刷新时，还没有来得及加入到曝光历史中，所以一般我们先将接口返回记录先实时加入到用户历史中，待实际曝光数据生成后再将其移除。一般这种用户曝光，但实际未曝光的数据对于用户来讲也很有价值的！

以上方案存在的问题

布谷鸟过滤

注：k随机哈希函数个数 d-left countfilter bloom filters 有d 个分区；

1x表示比1多一点点，3x ~ 4x表示为1的3~4倍左右；

布谷鸟哈希结构：布谷鸟过滤器由一个数组组成，数组中元素大小为4个字节，可以存储4个指纹，每个指纹占一个字节(128种)。同一个数组元素 上的多个座位在内存空间上是连续的，可以有效利用 CPU 高速缓存。

type bucket [4]byte          // 一个桶，4个座位 
type cuckoo_filter struct {
    bucket buckets [size]    // 一维数组     
    int nums                 // 容纳的元素个数     
    int kick_max             // 最大挤兑次数 
**}**

插入

首先计算数据的指纹和哈希值，并通过指纹和哈希值计算另一个哈希值，两个哈希值映射到两个位置(因为计算得到两个位置，每个位置存储4个指纹，所以相同对象最多存储8个)。

接下来进行插入，会尝试插入两个位置，如果都失败，随机挤走一个指纹，并重新为该指纹寻找新的位置(超过最大挤兑次数后扩容)。

i1,i2i_1,i_2i1​,i2​即计算出来两个桶的索引，其中第一个桶的索引是通过某个哈希函数计算出来，第二个是使用第一个索引和指纹的哈希做了一个异或操作，进行异或操作的好处是，因为异或操作的特性：同为0不同为1，且0和任何数异或是这个数的本身。那么i1i_1i1​也可以通过i2i_2i2​和指纹异或来计算。 换句话说，在桶中迁走一个键，我们直接用当前桶的索引iii和存储在桶中的指纹计算它的备用桶。

白话翻译：如果发布被占用，则顶掉，并把原来的换到备用桶！

扩容：如果数组过小，会发生循环挤兑的情况，就可以设置最大挤兑次数，如果超过该次数，进行扩容，重新计算每个指纹的位置。 查找：通过计算哈希值得到两个元素，对两个元素中的8个位置进行指纹对比，如果对比成功则表示数据存在。如果哈希值和指纹相同时会发生误判(小概率)。 删除：因为每个对象的指纹会存储到一个位置中，所以可以通过删除这个指纹来删除数据。删除功能无法使用的情况：如果相同对象存储超过8个，就无法使用删除功能；如果俩数据的哈希值和指纹相同时，会出现误删除情况。 更新：即删除后再添加新指纹。

关于淘汰

我们需要构建索引实现LRU-least recently used 32bit，可这样设计：

1、figerprint，布谷鸟哈希的指纹，必备。

2、index代表插入的顺序，那就可以做到数据的平滑淘汰，避免上面“挑战1”提到的一下子淘汰一整块数据。同时，可以以此为key，在db里面保存原始item id、曝光场景、时间、位置等详细信息，那后续就很容易做debug。

这个数据结构会比布隆过滤器占空间更多

但其实这块也取决于业务复杂度和细的设计，布隆过滤器做精确控制很难，布谷鸟过滤器对空间的整体利用率是可以做到更高的。

这里的索引会额外占用空间，如果过滤key为int 的id，而且量不大的情况下， 则用第一种zset 也可以满足业务需求！

当然，没有一个完美方案，需要基于产品实际情况大家去取舍。

相似爆光去重

同一刷次的item相似排重，在重排/打散阶段实现就行，比较简单，难的是隔刷的相似排重。

隔刷的相似排重，需要借助上面讲解的历史曝光排重，一个item a是否可以被曝光，可反查这个item的相似item a' a'是否已被曝光过，如果是，那item a需要被过滤掉。可以通过simhash 算法预先算好相似度。

参考文章

【闲聊推荐架构】推荐系统的曝光去重该怎么设计？

布隆过滤器与布谷鸟过滤器

www.cs.cmu.edu

布谷鸟过滤器(Cuckoo Filter) - 扯不断得红尘 - 博客园