vivo短视频在视频推荐时需要对用户已经看过的视频进行过滤去重，避免给用户重复推荐同一个视频影响体验。在一次推荐请求处理流程中，会基于用户兴趣进行视频召回，大约召回2000~10000条不等的视频，然后进行视频去重，过滤用户已经看过的视频，仅保留用户未观看过的视频进行排序，选取得分高的视频下发给用户。
1.2 当前现状当前推荐去重基于Redis Zset实现，服务端将播放埋点上报的视频和下发给客户端的视频分别以不同的Key写入Redis ZSet，推荐算法在视频召回后直接读取Redis里对应用户的播放和下发记录（整个ZSet），基于内存中的Set结构实现去重，即判断当前召回视频是否已存在下发或播放视频Set中，大致的流程如图1所示。
（图1：短视频去重当前现状）
视频去重本身是基于用户实际观看过的视频进行过滤，但考虑到实际观看的视频是通过客户端埋点上报，存在一定的时延，因此服务端会保存用户最近100条下发记录用于去重，这样就保证了即使客户端埋点还未上报上来，也不会给用户推荐了已经看过的视频（即重复推荐）。而下发给用户的视频并不一定会被曝光，因此仅保存100条，使得未被用户观看的视频在100条下发记录之后仍然可以继续推荐。
当前方案主要问题是占用Redis内存非常大，因为视频ID是以原始字符串形式存在Redis Zset中，为了控制内存占用并且保证读写性能，我们对每个用户的播放记录最大长度进行了限制，当前限制单用户最大存储长度为10000，但这会影响重度用户产品体验。
二、方案调研 2.1 主流方案第一，存储形式。视频去重场景是典型的只需要判断是否存在即可，因此并不需要把原始的视频ID存储下来，目前比较常用的方案是使用布隆过滤器存储视频的多个Hash值，可降低存储空间数倍甚至十几倍。
第二，存储介质。如果要支持存储90天（三个月）播放记录，而不是当前粗暴地限制最大存储10000条，那么需要的Redis存储容量非常大。比如，按照5000万用户，平均单用户90天播放10000条视频，每个视频ID占内存25B，共计需要12.5TB。视频去重最终会读取到内存中完成，可以考虑牺牲一些读取性能换取更大的存储空间。而且，当前使用的Redis未进行持久化，如果出现Redis故障会造成数据丢失，且很难恢复（因数据量大，恢复时间会很长）。
目前业界比较常用的方案是使用磁盘KV（一般底层基于RocksDB实现持久化存储，硬盘使用SSD），读写性能相比Redis稍逊色，但是相比内存而言，磁盘在容量上的优势非常明显。
2.2 技术选型第一，播放记录。因需要支持至少三个月的播放历史记录，因此选用布隆过滤器存储用户观看过的视频记录，这样相比存储原始视频ID，空间占用上会极大压缩。我们按照5000万用户来设计，如果使用Redis来存储布隆过滤器形式的播放记录，也将是TB级别以上的数据，考虑到我们最终在主机本地内存中执行过滤操作，因此可以接受稍微低一点的读取性能，选用磁盘KV持久化存储布隆过滤器形式的播放记录。
第二，下发记录。因只需存储100条下发视频记录，整体的数据量不大，而且考虑到要对100条之前的数据淘汰，仍然使用Redis存储最近100条的下发记录。
三、方案设计基于如上的技术选型，我们计划新增统一去重服务来支持写入下发和播放记录、根据下发和播放记录实现视频去重等功能。其中，重点要考虑的就是接收到播放埋点以后将其存入布隆过滤器。在收到播放埋点以后，以布隆过滤器形式写入磁盘KV需要经过三步，如图2所示：第一，读取并反序列化布隆过滤器，如布隆过滤器不存在则需创建布隆过滤器；第二，将播放视频ID更新到布隆过滤器中；第三，将更新后的布隆过滤器序列化并回写到磁盘KV中。
（图2：统一去重服务主要步骤）
整个过程很清晰，但是考虑到需要支持千万级用户量，假设按照5000万用户目标设计，我们还需要考虑四个问题：
-
第一，视频按刷次下发（一刷5~10条视频），而播放埋点按照视频粒度上报，那么就视频推荐消重而言，数据的写入QPS比读取更高，然而，相比Redis磁盘KV的性能要逊色，磁盘KV本身的写性能比读性能低，要支持5000万用户量级，那么如何实现布隆过滤器写入磁盘KV是一个要考虑的重要问题。
-
第二，由于布隆过滤器不支持删除，超过一定时间的数据需要过期淘汰，否则不再使用的数据将会一直占用存储资源，那么如何实现布隆过滤器过期淘汰也是一个要考虑的重要问题。
-
第三，服务端和算法当前直接通过Redis交互，我们希望构建统一去重服务，算法调用该服务来实现过滤已看视频，而服务端基于Java技术栈，算法基于C++技术栈，那么需要在Java技术栈中提供服务给C++技术栈调用。我们最终采用gRPC提供接口给算法调用，注册中心采用了Consul，该部分非重点，就不详细展开阐述。
-
第四，切换到新方案后我们希望将之前存储在Redis ZSet中的播放记录迁移到布隆过滤器，做到平滑升级以保证用户体验，那么设计迁移方案也是要考虑的重要问题。
统一去重服务的整体流程及其与上下游之间的交互如图3所示。服务端在下发视频的时候，将当次下发记录通过统一去重服务的Dubbo接口保存到Redis下发记录对应的Key下，使用Dubbo接口可以确保立即将下发记录写入。同时，监听视频播放埋点并将其以布隆过滤器形式存放到磁盘KV中，考虑到性能我们采用了批量写入方案，具体下文详述。统一去重服务提供RPC接口供推荐算法调用，实现对召回视频过滤掉用户已观看的视频。
（图3：统一去重服务整体流程）
磁盘KV写性能相比读性能差很多，尤其是在Value比较大的情况下写QPS会更差，考虑日活千万级情况下磁盘KV写性能没法满足直接写入要求，因此需要设计写流量汇聚方案，即将一段时间以内同一个用户的播放记录汇聚起来一次写入，这样就大大降低写入频率，降低对磁盘KV的写压力。
3.2 流量汇聚为了实现写流量汇聚，我们需要将播放视频先暂存在Redis汇聚起来，然后隔一段时间将暂存的视频生成布隆过滤器写入磁盘KV中保存，具体而言我们考虑过N分钟仅写入一次和定时任务批量写入两种方式。接下来详细阐述我们在流量汇聚和布隆过滤器写入方面的设计和考虑。
3.2.1 近实时写入监听到客户端上报的播放埋点后，原本应该直接将其更新到布隆过滤器并保存到磁盘KV，但是考虑到降低写频率，我们只能将播放的视频ID先保存到Redis中，N分钟内仅统一写一次磁盘KV，这种方案姑且称之为近实时写入方案吧。
最朴素的想法是每次写的时候，在Redis中保存一个Value，N分钟以后失效，每次监听到播放埋点以后判断这个Value是否存在，如果存在则表示N分钟内已经写过一次磁盘KV本次不写，否则执行写磁盘KV操作。这样的考虑主要是在数据产生时，先不要立即写入，等N分钟汇聚一小批流量之后再写入。这个Value就像一把“锁”，保护磁盘KV每隔N分钟仅被写入一次，如图4所示，如果当前为已加锁状态，再进行加锁会失败，可保护在加锁期间磁盘KV不被写入。从埋点数据流来看，原本连续不断的数据流，经过这把“锁”就变成了每隔N分钟一批的微批量数据，从而实现流量汇聚，并降低磁盘KV的写压力。
（图4：近实时写入方案）
近实时写入的出发点很单纯，优势也很明显，可以近实时地将播放埋点中的视频ID写入到布隆过滤器中，而且时间比较短（N分钟），可以避免Redis Zset中暂存的数据过长。但是，仔细分析还需要考虑很多特殊的场景，主要如下：
第一，Redis中保存一个Value其实相当于一个分布式锁，实际上很难保证这把“锁”是绝对安全的，因此可能会存在两次收到播放埋点均认为可以进行磁盘KV写操作，但这两次读到的暂存数据不一定一样，由于磁盘KV不支持布隆过滤器结构，写入操作需要先从磁盘KV中读出当前的布隆过滤器，然后将需要写入的视频ID更新到该布隆过滤器，最后再写回到磁盘KV，这样的话，写入磁盘KV后就有可能存在数据丢失。
第二，最后一个N分钟的数据需要等到用户下次再使用的时候才能通过播放埋点触发写入磁盘KV，如果有大量不活跃的用户，那么就会存在大量暂存数据遗留在Redis中占用空间。此时，如果再采用定时任务来将这部分数据写入到磁盘KV，那么也会很容易出现第一种场景中的并发写数据丢失问题。
如此看来，近实时写入方案虽然出发点很直接，但是仔细想来，越来越复杂，只能另寻其他方案。
3.2.2 批量写入既然近实时写入方案复杂，那不妨考虑简单的方案，通过定时任务批量将暂存的数据写入到磁盘KV中。我们将待写的数据标记出来，假设我们每小时写入一次，那么我们就可以把暂存数据以小时值标记。但是，考虑到定时任务难免可能会执行失败，我们需要有补偿措施，常见的方案是每次执行任务的时候，都在往前多1~2个小时的数据上执行任务，以作补偿。但是，明显这样的方案并不够优雅，我们从时间轮得到启发，并基于此设计了布隆过滤器批量写入的方案。
我们将小时值首尾相连，从而得到一个环，并且将对应的数据存在该小时值标识的地方，那么同一小时值（比如每天11点）的数据是存在一起的，如果今天的数据因任务未执行或执行失败未同步到磁盘KV，那么在第二天将会得到一次补偿。
顺着这个思路，我们可以将小时值对某个值取模以进一步缩短两次补偿的时间间隔，比如图5所示对8取模，可见1:002:00和9:0010:00的数据都会落在图中时间环上的点1标识的待写入数据，过8个小时将会得到一次补偿的机会，也就是说这个取模的值就是补偿的时间间隔。
（图5：批量写入方案）
那么，我们应该将补偿时间间隔设置为多少呢？这是一个值得思考的问题，这个值的选取会影响到待写入数据在环上的分布。我们的业务一般都会有忙时、闲时，忙时的数据量会更大，根据短视频忙闲时特点，最终我们将补偿间隔设置为6，这样业务忙时比较均匀地落在环上的各个点。
确定了补偿时间间隔以后，我们觉得6个小时补偿还是太长了，因为用户在6个小时内有可能会看过大量的视频，如果不及时将数据同步到磁盘KV，会占用大量Redis内存，而且我们使用Redis ZSet暂存用户播放记录，过长的话会严重影响性能。于是，我们设计每个小时增加一次定时任务，第二次任务对第一次任务补偿，如果第二次任务仍然没有补偿成功，那么经过一圈以后，还可以得到再次补偿（兜底）。
细心一点应该会发现在图5中的“待写入数据”和定时任务并不是分布在环上的同一个点的，我们这样设计的考虑是希望方案更简单，定时任务只会去操作已经不再变化的数据，这样就能避免并发操作问题。就像Java虚拟机中垃圾回收一样，我们不能一边回收垃圾，一边却还在同一间屋子里扔着垃圾。所以，设计成环上节点对应定时任务只去处理前一个节点上的数据，以确保不会产生并发冲突，使方案保持简单。
批量写入方案简单且不存在并发问题，但是在Redis Zset需要保存一个小时的数据，可能会超过最大长度，但是考虑到现实中一般用户一小时内不会播放非常大量的视频，这一点是可以接受的。最终，我们选择了批量写入方案，其简单、优雅、高效，在此基础上，我们需要继续设计暂存大量用户的播放视频ID方案。
3.3 数据分片为了支持5000万日活量级，我们需要为定时批量写入方案设计对应的数据存储分片方式。首先，我们依然需要将播放视频列表存放在Redis Zset，因为在没写入布隆过滤器之前，我们需要用这份数据过滤用户已观看过的视频。正如前文提到过，我们会暂存一个小时的数据，正常一个用户一个小时内不会播放超过一万条数据的，所以一般来说是没有问题的。除了视频ID本身以外，我们还需要保存这个小时到底有哪些用户产生过播放数据，否则定时任务不知道要将哪些用户的播放记录写入布隆过滤器，存储5000万用户的话就需要进行数据分片。
结合批量同步部分介绍的时间环，我们设计了如图6所示的数据分片方案，将5000万的用户Hash到5000个Set中，这样每个Set最多保存1万个用户ID，不至于影响Set的性能。同时，时间环上的每个节点都按照这个的分片方式保存数据，将其展开就如同图6下半部分所示，以played:user:${时间节点编号}