首发于公众号MXPlayer技术团队,欢迎关注。

引言

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,则被检索元素很可能存在

图1. BloomFilter原理

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)的可能性。

BloomFilter在mx中的实践

BloomFilter有各种各样的实现,mx推荐系统直接使用了google guava库中的BloomFilter,为每个用户分配一个容量为10000,假阳性率为0.01的BloomFilter。

  • 历史存储过程

    每次推荐系统将数据返回给用户之前,将每条数据的id添加到该用户的BloomFilter中,然后将BloomFilter导出为字节数组并存储到redis中,设置失效时间为7天,同时异步将原始item id存储到pika的zset中(留底)

  • 历史过滤过程

    从redis取出BloomFilter的字节数组构造guava BloomFilter对象,进行过滤

图2. BloomFilter历史过滤流程

两种方案对比

  1. 存储

    BloomFilter vs ItemList
    由上图可知,存储同样数量的历史数据,BloomFilter所占内存大小大概比item list小一个数量级。测试结果表明,容量为10000,假阳性率为0.01的guava BloomFilter对象导出的字节数组的长度为11990,所占内存大约为12KB,也就是说存储一个用户10000条历史数据只占用12KB。而如果历史数据以item id list的形式存储,由于item id是一个32位字符(十六进制数)的字符串,用utf-8编码,一个字符占用一个字节,所以存储10000条item id,则会占用10000×32×1=320000B,大约是312KB,是用BloomFilter存储时占用的内存的 26 倍!也就是使用BloomFilter比item list节省了大约 96% 的内存,减少一大笔存储开销。虽然我们同时也使用pika存储item id list作为存底,但是pika是硬盘数据库,远比内存便宜,相比较redis而言几乎可以忽略不计。

  2. 效率

    方案一在将数据写入redis的zset有两种方法,一是用循环将item list中的id异步添加到zset中,另一种是将item id list和对应的分数添加到一个数组,然后将该数组作为zadd参数一次性传输到redis并执行,这两种方法在效率上其实不会差很多。方案二只需要把BloomFilter导出为byte数组,然后直接以byte类型存储到redis即可。从编码角度来看,BloomFilter要简单地多;从网络传输的角度看,item id list由于数据量大,所以要比BloomFilter消耗的时间长;从redis端执行命令的角度看,方案一需要多次执行zadd命令,而方案二只需要执行一次set(bytes),所以方案二还是比方案一耗时更少。所以综合来看,方案二的效率要高得多。

扩展

  1. BloomFilter的选择

    redis从4.0版本开始支持模块(Module),我们可以开发和加载任意模块,官方也提供了很多优秀的模块,其中就有针对BloomFilter的实现模块——RedisBloom,所以我们可以直接使用redis自带的BloomFilter,而不必再用guava BloomFilter导出byte array再存入redis。但是如果系统的负载均衡是具有会话亲和性(即粘滞会话)的,那么使用guava BloomFilter并进行本地缓存将大大提高系统性能,而RedisBloom则无法缓存到本地,因为我们不知道RedisBloom的算法是怎样的,或者说不好实现与RedisBloom相同的算法。

  2. BloomFilter的假阳性率

    假设Hash 函数以等概率条件选择并设置位数组中的某一位,假定由每个Hash 计算出需要设置的位(bit) 的位置是相互独立, m 是该位数组的大小,k是Hash 函数的个数,n为要插入的元素个数,那么假阳性率大约为:

    (1-e^\frac{-kn}{m})^k

    详细的计算过程可参考《数学之美 第二版》中的布隆过滤器一章。通过上面的公式可以知道,我们可以预测目标元素的个数,通过调整位数组的大小来达到可接受的假阳性率,同样的,通过设置目标元素个数和假阳性率可以计算出位数组大小(参考guava BloomFilter的构造参数)。