Press "Enter" to skip to content

BloomFilter在MX推荐系统中的实践

Mxplayer作为一款受欢迎的在线视频播放器,拥有着大量的用户。在诸如短视频推荐在内的很多场景下,需要将用户之前看过的短视频从召回的结果中过滤掉,确保推荐内容的多样性,以提升用户体验。所以需要在将已经推荐过的数据保存到用户的历史中,随着用户的增长和用户历史的增加, 海量历史数据的存储和高效过滤是需要解决的难题,mx推荐系统通过使用BloomFilter有效地解决了这一难题。

 

MX曾经的解决方案(方案1)

 

在最初的的用户历史过滤中,用户的历史数据(item id列表)被存储在redis的zset中,因为用户的历史数量可能会很多,所以做了一个截断操作,只保留最近的1400条数据。每次先从redis中取出用户所有的历史数据,进行过滤操作,然后在结果列表返回前,将该列表的数据添加到历史数据中,然后一起push到redis中。这种历史过滤不仅占用redis大量内存,而且每条请求都需要与redis进行两次大量历史数据的传输,耗费大量时间和网络带宽,同时server端也因为缓存历史数据而消耗大量内存。

 

BloomFilter历史过滤(方案2)

 

BloomFilter简介

 

Bloom Filter是一种空间效率很高的随机数据结构,它的原理是,当一个元素被加入集合时,通过K个Hash函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就知道集合中有没有它了:如果这些点有任何一个0,则被检索元素一定不在;如果都是1,则被检索元素 很可能存在 。

An example of a Bloom filter, representing the set {x, y, z}. The colored arrows show the positions in the bit array that each set element is mapped to. The element w is not in the set {x, y, z}, because it hashes to one bit-array position containing 0. For this figure, m = 18 and k = 3.

 

详细说明请参考Wikipedia article。由上图可知,假如某个元素v并不存在于集合中,但是通过三个hash函数得到的值为(1,3,4),那幺BloomFilter将判定v存在于集合中,所以BloomFilter存在假阳性(False Positive)的可能性。

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注