打开

为什么抖音从来没有重复内容?无关数据库,背后的算法有大学问

subtitle
吴老师英语教学 2020-10-03 08:20

你在刷抖音的时候,有没有发现,抖音从来不会给你推送相同内容的视频?你可能会想,这有啥难的,给每个人都存一个记录,以后推送的时候避开就好了呀。nononono!可没有这么简单啊!

打开网易新闻 查看更多图片

海量用户的重复内容过滤

这是一个非常严肃的问题。在互联网领域,重复推送是一件非常影响用户体验的行为。一旦出现重复内容,会大大增加用户跳出的几率。

搞数据库的同学会说:这还不简单?反正有用户日志,我们给每个人都存一个访问日志表,推送之前exists一下就好了。

怎么说呢,如果用户量只有你们公司几百号人,这个方案是没问题的。但是抖音、快手动辄几亿人,每天都刷,这得存多少份log??每一个用户的log有多大?每一个推送都要从这个大log里exists一下,得耗多少时间?

等你exists一下,用户早就跑了好么?所以在抖音、快手动辄几亿日活,每人每天最少看几百个短视频的情况,如何快速推送不重复的内容是非常困难的事情。

高速过滤的秘密武器

需求:几亿个用户,每个用户有1~几万(甚至更多)个已看记录,快速判断下一个推送给用户的视频是否已经看过。

解决方案1-表级处理:每个用户一张表,存视频id,推荐之后,展示之前,过滤一下。这个表太多,表里的数据也太多,过滤效率太慢了。信息得进一步压缩,速度要再快点才行。

解决方案2-图计算:把每个用户与每个视频发生的关系都存到图数据库。推荐的时候直接通过关系过滤掉。这个虽然不用建N张表,只是存用户和视频的关系就行了。但是用过图数据库的人就知道,节点太多了,计算效果也是非常的慢。不行,信息还得进一步压缩。还能咋压缩啊?

解决方案3-位图:把所有用户当天是否登录的信息映射到一张位图中,这样我们就能迅速通过某个位是0还是1快速判定这个用户当天是否登录过系统。

假如说我们同样使用位图,把每个用户是否看过这个视频映射到位图中,是不是就可以通过某个位是0还是1快速判定这个用户是否看过这个视频呢?哆啦A梦告诉我们:可以!而且有更完善的方法--布隆过滤器!

布隆过滤器:1970年由布隆提出的一种方法,由随机映射函数和二进制向量组成,可以快速检索一个元素是否在一个集合中。

如布隆过滤器的描述,其实就是随机映射函数(hash散列)+二进制向量(位图)组成的。我们把任意需要存储的内容,经过hash散列映射成为一个随机数字,然后存在这张超大的位图中,将对应的位上的值由0改成1就可以了。这样我们就能知道这个这个事情是否发生过。

上图中,用户A看了视频B,hash后的值是5,那么第5位的值就变成1了。如果我们想判断用户A是否看了视频B,只要看看第5位是不是1就可以了。

但是hash有个问题,当数据量超大的时候,就有可能会重复(碰撞)。幸好布隆早就想到了,他是这么解决的:

多hash几次就好了,这样就能就大大降低了重复(碰撞)的问题。总不可能连续好几次hash都是一样的结果吧?

视频推荐过滤器

原理有了,那么就可以开始设计了。

这里我们可以看到,有两个实体:用户和视频。简单组合一下,就有三种方法:

1、给每个用户建一个看过视频的布隆过滤器,推荐系统推送的内容使用布隆过滤器过滤一下,把不在列表里的让客户可见即可;

2、给每个视频建一个观看列表的布隆过滤器,推荐系统给用户推送的时候使用布隆过滤器过滤一下,不在列表里的才能推送即可;

3、建一个大的布隆过滤器,把每个用户的观看记录都放在这个过滤器中,推荐系统给用户推送的时候到大布隆过滤器中过滤一下,不在列表里的才能推送。

以上三种方法都可以,我也不太清楚抖音用的是那种方法,我猜是第一种,因为视频总比用户多,而一个大布隆过滤器的话,又太大了。

布隆过滤器的优化

不过即便是每个用户一个布隆过滤器,数据量还是太大了。任何事情都会引发量变引起质变的问题。所以布隆过滤器误判的问题仍然是存在的。比如:

用户A看视频B,3次hash散列结果是2、5、6;用户A看视频D,3次hash散列结果是5、7、8;用户A看视频F,3次hash散列结果是1、9、3;

这时候,位图中的1、2、3、5、7、8、9都被打上1了。

而我们需要询问布隆过滤器用户A是否看过视频H的时候就出现了:

用户A看视频H,3次hash散列结果是3、8、9,

布隆过滤器里3、8、9的结果内容里已经被打上1了,也就是说布隆过滤器告诉我

们,这个视频已经被看过了(实际上并没有看)。那我们怎么解决这个问题呢?

简单的两招:

1、增加位图的位数(或者减少原始数据量);

2、适当增加hash次数;

布隆大大早就给我们算好了,最佳的原始数据和位图位数比是1:20,经过8次hash,误判率会在千分之一左右。如果把hash次数提高,误判率会更低。

不过,我们的应用是要知道这个用户没看过的,那就不用咋优化了。因为布隆过滤器告诉我们看过,可能是误判,但是如果告诉我们没看过,那就肯定是没看过。

特别声明:本文为网易自媒体平台“网易号”作者上传并发布,仅代表该作者观点。网易仅提供信息发布平台。
126赞
大家都在看打开应用 查看全部
网易热搜每30分钟更新
打开应用 查看全部
打开