一、概述
1.1 业务背景
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.1 整体流程
统一去重服务的整体流程及其与上下游之间的交互如图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:00~2:00和9:00~10: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:${时间节点编号}:${用户Hash值}为Key保存某个时间节点某个分片下所有产生了播放数据的用户ID。
图片（图6：数据分片方案）
对应地，我们的定时任务也要进行分片，每个任务分片负责处理一定数目的数据分片。否则，如果两者一一对应的话，将分布式定时任务分成5000个分片，虽然对于失败重试是更好的，但是对于任务调度来说会存在压力，实际上公司的定时任务也不支持5000分分片。我们将定时任务分为了50个分片，任务分片0负责处理数据分片0~100，任务分片1负责处理数据分片100~199，以此类推。
3.4 数据淘汰
对于短视频推荐去重业务场景，我们一般保证让用户在看过某条视频后三个月内不会再向该用户推荐这条视频，因此就涉及到过期数据淘汰问题。布隆过滤器不支持删除操作，因此我们将用户的播放历史记录添加到布隆过滤器以后，按月存储并设置相应的过期时间，如图7所示，目前过期时间设置为6个月。在数据读取的时候，根据当前时间选择读取最近4个月数据用于去重。之所以需要读取4个月的数据，是因为当月数据未满一个月，为了保证三个月内不会再向用户重复推荐，需要读取三个完整月和当月数据。
图片（图7：数据淘汰方案）
对于数据过期时间的设置我们也进行了精心考虑，数据按月存储，因此新数据产生时间一般在月初，如果仅将过期时间设置为6个月以后，那么会造成月初不仅产生大量新数据，也需要淘汰大量老数据，对数据库系统造成压力。所以，我们将过期时间进行了打散，首先随机到6个月后的那个月任意一天，其次我们将过期时间设置在业务闲时，比如：00:00~05:00，以此来降低数据库清理时对系统的压力。
3.5 方案小结
通过综合上述流量汇聚、数据分片和数据淘汰三部分设计方案，整体的设计方案如图8所示，从左至右播放埋点数据依次从数据源Kafka流向Redis暂存，最终流向磁盘KV持久化。
图片（图8：整体方案流程）
首先，从Kafka播放埋点监听到数据以后，我们根据用户ID将该条视频追加到用户对应的播放历史中暂存，同时根据当前时间和用户ID的Hash值确定对应时间环，并将用户ID保存到该时间环对应的用户列表中。然后，每个分布式定时任务分片去获取上一个时间环的播放用户数据分片，再获取用户的播放记录更新到读出的布隆过滤器，最后将布隆顾虑其序列化后写入磁盘KV中。
四、数据迁移
为了实现从当前基于Redis ZSet去重平滑迁移到基于布隆过滤器去重，我们需要将统一去重服务上线前用户产生的播放记录迁移过来，以保证用户体验不受影响，我们设计和尝试了两种方案，经过对比和改进形成了最终方案。
我们已经实现了批量将播放记录原始数据生成布隆过滤器存储到磁盘KV中，因此，迁移方案只需要考虑将存储在原来Redis中的历史数据（去重服务上线前产生）迁移到新的Redis中即可，接下来就交由定时任务完成即可，方案如图9所示。用户在统一去重服务上线后新产生的增量数据通过监听播放埋点写入，新老数据双写，以便需要时可以降级。
（图9：迁移方案一）
但是，我们忽略了两个问题：第一，新的Redis仅用作暂存，因此比老的Redis容量小很多，没法一次性将数据迁移过去，需要分多批迁移；第二，迁移到新的Redis后的存储格式和老的Redis不一样，除了播放视频列表，还需要播放用户列表，咨询DBA得知这样迁移比较难实现。
既然迁移数据比较麻烦，我们就考虑能不能不迁移数据呢，在去重的时候判断该用户是否已迁移，如未迁移则同时读取一份老数据一起用于去重过滤，并触发将该用户的老数据迁移到新Redis（含写入播放用户列表），三个月以后，老数据已可过期淘汰，此时就完成了数据迁移，如图10所示。这个迁移方案解决了新老Redis数据格式不一致迁移难的问题，而且是用户请求时触发迁移，也避免了一次性迁移数据对新Redis容量要求，同时还可以做到精确迁移，仅迁移了三个月内需要迁移数据的用户。
图片（图10：迁移方案二）
于是，我们按照方案二进行了数据迁移，在上线测试的时候，发现由于用户首次请求的时候需要去迁移老的数据，造成去重接口耗时不稳定，而视频去重作为视频推荐重要环节，对于耗时比较敏感，所以就不得不继续思考新的迁移方案。我们注意到，在定时批量生成布隆过滤器的时候，读取到时间环对应的播放用户列表后，根据用户ID获取播放视频列表，然后生成布隆过滤器保存到磁盘KV，此时，我们只需要增加一个从老Redis读取用户的历史播放记录即可把历史数据迁移过来。为了触发将某个用户的播放记录生成布隆过滤器的过程，我们需要将用户ID保存到时间环上对应的播放用户列表，最终方案如图11所示。
图片（图11：最终迁移方案）
首先，DBA帮助我们把老Redis中播放记录的Key（含有用户ID）都扫描出来，通过文件导出；然后，我们通过大数据平台将导出的文件导入到Kafka，启用消费者监听并消费文件中的数据，解析后将其写入到当前时间环对应的播放用户列表。接下来，分布式批量任务在读取到播放用户列表中的某个用户后，如果该用户未迁移数据，则从老Redis读取历史播放记录，并和新的播放记录一起更新到布隆过滤器并存入磁盘KV。
五、小结
本文主要介绍短视频基于布隆过滤器构建推荐去重服务的设计与思考，从问题出发逐步设计和优化方案，力求简单、完美、优雅，希望能对读者有参考和借鉴价值。由于文章篇幅有限，有些方面未涉及，也有很多技术细节未详细阐述，如有疑问欢迎继续交流。
作者：vivo互联网服务器团队-Zhang Wei
