一、概述
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