的设计实践一、概述1.1业务背景vivo短视频在推荐视频时，需要对用户已经看过的视频进行过滤去重，避免影响。反复向用户推荐同一个视频的体验。在一个推荐请求处理过程中，会根据用户的兴趣召回视频，大概会召回2000到10000个视频，然后对视频进行去重过滤用户已经看过的视频，只保留那些已经看过的视频。该用户未观看。排序，选择得分高的视频发送给用户。1.2现状目前推荐的去重是基于RedisZset实现的。服务端将埋点上报的视频和发送给客户端的视频以不同的key播放到RedisZSet中。推荐算法在召回视频后会直接读取Redis中对应的视频。用户的播放和分发记录（整个ZSet）根据内存中的Set结构进行去重，即判断当前调用的视频是否存在于分发或播放视频集中。大致流程如图1所示。（图1：短视频去重现状）视频去重本身是根据用户实际观看的视频进行过滤，但是考虑到实际观看的视频是通过埋点上报的客户端，有一定的延迟，所以服务客户端会保存用户最近100条发送记录进行去重，保证即使客户端的埋点没有上报，也不会推荐用户已经看过的视频（即反复推荐）。发送给用户的视频不一定会曝光，所以只保存100个视频，这样发送100条记录后，用户还没有看过的视频仍然可以被推荐。当前方案的主要问题是占用大量Redis内存，因为视频ID是以原始字符串的形式存储在RedisZset中。为了控制内存占用，保证读写性能，我们限制了每个用户播放记录的最大长度。目前限制单个用户最大存储长度为10000，但这会影响重度用户的产品体验。2.方案研究2.1主流方案首先是存储形式。视频去重场景是一个典型的场景，只需要判断是否存在即可，不需要存储原始视频ID。目前比较普遍的方案是使用布隆过滤器存储视频的多个哈希值，可以减少存储空间。几次甚至十次。二、存储介质。如果要支持存储90天（三个月）的播放记录，而不是目前粗略的限制最大存储10000条，那么需要的Redis存储容量是非常大的。例如，以5000万用户计算，平均单个用户90天播放10000个视频，每个视频ID占用25B内存，共需要12.5TB。视频去重最终会被读入内存中完成。考虑牺牲一些读取性能以获得更大的存储空间。而且，目前使用的Redis并不是持久化的。如果Redis发生故障，数据会丢失，而且很难恢复（因为数据量大，恢复时间会很长）。目前业界最常用的方案是使用磁盘KV（一般底层基于RocksDB做持久化存储，硬盘使用SSD）。读写性能略逊于Redis，但与内存相比，磁盘在容量方面优势明显。2.2技术选择先，播放记录。因为需要支持至少三个月的播放历史，所以使用Bloomfilter来存储用户看过的视频记录。与存储原始视频ID相比，空间占用将大大压缩。我们根据5000万用户进行设计。如果使用Redis以布隆过滤器的形式存储播放记录，同样会超过TB级别的数据。考虑到我们最终会在宿主机的本地内存中进行过滤操作，稍微低一点是可以接受的，读取性能高，使用磁盘KV持久化存储以布隆过滤器的形式存储播放记录。二是出具备案。因为只需要存储100条发出的视频记录，整体数据量不大，考虑到剔除100条之前的数据，仍然使用Redis存储最新的100条发出的记录。3.方案设计基于以上技术选型，我们计划增加统一的去重服务，支持写入发送回放记录，实现基于发送回放记录的视频去重。其中，最需要考虑的是接收到埋点后将埋点存入Bloomfilter。接收到播放埋点后，分三步以Bloomfilter的形式写入磁盘KV，如图2所示：首先，读取并反序列化Bloomfilter，如果Bloomfilter不存在则需要创建布隆过滤器；第二，更新播放视频ID给布隆过滤器；第三，将更新后的Bloomfilter序列化，写回磁盘KV。（图2：统一去重服务的主要步骤）整个流程已经很清晰了，但是考虑到需要支持千万用户，假设设计是以5000万用户为目标，我们还是需要考虑四个问题：第一，视频是根据滑动次数发送（一次5-10个视频），播放埋点是根据视频粒度上报，所以在视频推荐去重方面，QPS的数据写入高于读取。但是，相较于Redis磁盘KV的性能要逊色，磁盘KV本身的写性能是低于读性能的。要支撑5000万用户，如何实现Bloomfilter写入磁盘KV是需要考虑的重要问题。二、由于布隆过滤器不支持删除，超过一定时间的数据需要过期淘汰，否则不再使用的数据会一直占用存储资源，那么如何实现过期淘汰布隆过滤器也是一个需要考虑的重要问题。第三，服务器和算法目前直接通过Redis进行交互。我们希望构建一个统一的去重服务。该算法调用此服务来过滤观看的视频。服务器基于Java技术栈，算法基于C++技术栈。技术栈为C++技术栈调用提供服务。我们最终使用gRPC来提供算法调用的接口，注册中心使用Consul。这部分不是重点，就不细说了。第四，切换到新方案后，我们希望将之前存储在RedisZSet中的播放记录迁移到Bloomfilter中，实现平滑升级，保证用户体验，因此设计迁移方案也是需要考虑的重要问题。3.1整体流程统一去重服务的整体流程及与上下游的交互如图3所示，服务端发送视频时，通过Dubbo接口将当前的投递记录保存到Redis投递记录对应的key中统一重复数据删除服务。使用Dubbo接口可以保证发送记录是即时写入的。同时监控视频播放的埋点，以Bloomfilter的形式存入磁盘KV。考虑到性能，我们采用了批量写入的方案，具体如下。统一去重服务提供RPC接口供推荐算法调用，过滤掉用户已经看过的视频，用于召回视频。（图3：统一去重服务整体流程）磁盘KV写性能比读性能差很多，尤其是当Value比较大的时候，写QPS会更差。考虑到日常活动数千万的情况下，磁盘KV写性能不好。为满足直写需求，需要设计写流量聚合方案，即聚合一段时间内同一用户的播放记录，一次性写入，这样会大大降低写入频率，减少磁盘KV的写入压力。3.2流量聚合为了实现写入流量聚合，我们需要将播放视频暂存在Redis中并进行聚合，然后在一段时间后将暂存视频的Bloomfilter写入磁盘KV进行存储。具体的，我们考虑了N分钟只写一次和定时任务批量写两种方式。下面详细阐述我们在流量聚合和Bloomfilter编写方面的设计和考虑。3.2.1近实时写入听客户端反馈的回放埋点，应该是直接更新到Bloomfilter，保存到磁盘KV，但是考虑到降低写入频率，我们只能改成播放视频ID先保存到Redis，N分钟内只写一次磁盘KV。这种解决方案称为近实时写入解决方案。最简单的思路就是每次写入在Redis中保存一个Value，N分钟后失效，每次听回放埋点判断Value是否存在。如果存在，说明磁盘KV已经在N分钟内写了一次，这次不要写，否则执行磁盘KV操作。这种考虑主要是当数据产生的时候，不要马上写入，而是等待N分钟，聚集了小批量的流量后再写入。这个Value就像一把“锁”，保护磁盘KV不会每N分钟只被写入一次。如图4所示，如果当前处于锁定状态，进一步锁定将失败，在锁定期间可以保护。磁盘KV未写入。从埋点数据流来看，原本连续的数据流，通过这个“锁”，变成每N分钟一批微批数据，从而实现流量聚合，降低磁盘KV的写入压力。（图4：近实时写入方案）近实时写入的出发点很简单，优势也很明显。播放埋点中的视频ID可以近乎实时的写入Bloomfilter，时间比较短（N分钟），可以避免数据暂存在RedisZset中过长。但是仔细分析也需要考虑很多特殊场景，主要有以下几点：第一，在Redis中保存一个Value其实就相当于一个分布式锁。实际上很难保证这个“锁”是绝对安全的，所以有可能认为两次接收回放埋点后可以进行磁盘KV写操作，但是这两次读取的暂存数据时间不一定相同。由于磁盘KV不支持Bloomfilter结构，写操作需要先从磁盘KV中读取。读出当前的Bloomfilter，然后更新需要写入Bloomfilter的videoID，最后写回磁盘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内存。而我们使用RedisZSet来临时存储用户播放记录，如果时间过长，会严重影响性能。因此，我们设计每小时增加一个定时任务，第二个任务补偿第一个任务。如果第二个任务还是没有补偿成功，那么绕一圈之后，就可以再次获得补偿（underthehood）。如果细心的话，你会发现图5中的“待写入数据”和定时任务并不是分布在环上的同一个点上。我们这样设计是为了让解决方案更简单，定时任务只会运行。然后更改数据，这样就可以避免并发操作的问题。就像Java虚拟机中的垃圾回收一样，我们不能回收垃圾，同时还在同一个房间里扔垃圾。因此设计环上节点只处理调度任务对应的前一个节点上的数据，保证不会发生并发冲突，解决方案简单。批量写入方案简单，不存在并发问题，但RedisZset需要保存一个小时的数据，可能会超过最大长度，但考虑到现实中一般用户不会在其中播放非常多的视频一个小时，这个OK接受了。最终我们选择了批量写入的方案，简单、优雅、高效。在此基础上，我们需要继续设计一个播放视频ID方案，用于暂存大量用户。3.3数据分片为了支持每天5000万次的活动，我们需要为定时批量写入方案设计相应的数据存储分片方式。首先，我们仍然需要将播放视频列表存储在RedisZset中，因为在编写布隆过滤器之前，我们需要使用这些数据来过滤用户观看过的视频。如上所述，我们将暂时存储一小时的数据。一般情况下，一个用户一个小时内播放的数据不会超过10000条，所以一般来说是没有问题的。除了视频ID本身，我们还需要保存这个小时有哪些用户产生了播放数据。否则定时任务不知道应该将哪些用户的播放记录写入布隆过滤器。如果存储5000万用户，则需要进行数据分析。片。结合批量同步部分介绍的时间循环，我们设计了如图6所示的数据分片方案，将5000万用户hash到5000个Set中，这样每个Set最多可以存储10000个用户ID而不影响Set性能。同时，时间环上的各个节点按照这种分片方式保存数据，并展开如图6下部所示，其中played:user:${timenodenumber}:${userHashvalue}为Key保存某个段下某个时间节点下所有产生播放数据的用户ID。（图6：数据分片方案）相应的，我们的定时任务也要分片，每个任务分片负责处理一定数量的数据分片。否则，如果两者一一对应，将分布式定时任务分成5000个分片，对于失败的重试效果更好，但会给任务调度带来压力。其实公司的定时任务是不支持的。5000个碎片。我们将定时任务分成50个分片，任务分片0负责处理数据分片0~100，任务分片1负责处理数据分片100~199，以此类推。3.4数据剔除针对短视频推荐去重业务场景，我们一般会保证用户在观看某个视频后的三个月内不会向用户推荐该视频，因此涉及到过期数据剔除的问题。Bloomfilter不支持删除，所以我们将用户的播放历史添加到Bloomfilter中，按月存储并设置相应的过期时间，如图7所示，当前过期时间设置为6个月。读取数据时，根据当前时间选择读取最近4个月的数据进行去重。之所以需要读取4个月的数据，是因为当月的数据不足1个月。为了保证三个月内不会给用户重复推荐，需要读取整整三个月和当月的数据。（图7：数据淘汰方案）我们也仔细考虑了数据过期时间的设置。数据按月存储，因此新数据一般在月初产生。如果过期时间只设置为6个月后，会导致在月初，不仅有大量新数据产生，还需要淘汰大量旧数据，给系统带来压力数据库系统。因此，我们分散了过期时间。首先，它被随机分配到6个月后该月的任何一天。其次，我们在业务空闲的时候设置过期时间，比如：00:00~05:00，在清除的同时减少数据库对系统的压力。3.5方案总结通过整合上述流量汇聚、数据分片和数据剔除三部分设计方案，整体设计方案如图8所示。从左到右，从数据中打出埋点数据sourceKafka到Redis暂存，最后流向DiskKV持久化。（图8：整体求解流程）首先我们从Kafka播放埋点监听数据后，我们根据用户ID将视频追加到用户对应的播放历史中暂存，同时根据判断将当前时间和用户ID的Hash值对应时间环，将用户ID保存到时间环对应的用户列表中。然后，每个分布式定时任务段获取上一个时间环的播放用户数据段，然后获取用户的播放记录更新到读取的Bloomfilter，最后将Bloomconcern序列化写入DiskKV。4.数据迁移为了实现从目前基于RedisZSet的去重到基于Bloomfilter的去重的平滑迁移，我们需要在统一去重服务上线前，将用户产生的播放记录进行迁移，保证用户体验。不受影响。我们设计并尝试了两种方案，经过比较和改进形成了最终的方案。我们实现了将播放记录的原始数据生成的Bloomfilters批量存储到磁盘KV中。因此，迁移计划只需要考虑将原Redis中存储的历史数据（去重服务上线前产生）迁移到新的Redis中即可，然后由定时任务完成即可。方案如图9所示，统一去重服务上线后，通过监听回放埋点写入用户新产生的增量数据，新老数据双写，实现降级必要时。（图9：迁移方案一）但是，我们忽略了两个问题：第一，新的Redis只是用于临时存储，所以容量比旧的Redis小很多，不可能一次迁移数据.批量迁移；第二，迁移到新Redis后的存储格式与旧Redis不同。除了播放视频列表，还需要播放用户列表。咨询了DBA，得知这样的迁移是很难实现的。由于迁移数据比较麻烦，我们考虑是否可以不迁移数据，在去重的时候判断用户是否已经迁移。如果不是，则同时读取一个旧数据进行去重和过滤，并触发该用户的旧数据迁移到新的Redis（包括写入播放用户列表）。三个月后，旧数据就可以过期淘汰了。此时数据迁移完成，如图10所示。该迁移方案解决了新旧Redis数据格式不一致迁移困难的问题，在用户请求时触发迁移，同时也避免了新Redis对一次性迁移数据的容量需求。同时，还可以实现精准迁移。一个月内只有三个用户需要迁移数据。（图10：迁移方案二）因此，我们按照方案二进行了数据迁移，在线测试时发现用户第一次请求时需要迁移旧数据，导致去重接口耗时且不稳定，而视频作为视频推荐的重要组成部分，去重对时间消耗敏感，因此我们不得不继续思考新的迁移方案。我们注意到，定时批量生成Bloomfilter时，读取时间环对应的播放用户列表后，根据用户ID获取播放视频列表，生成Bloomfilter并保存到磁盘KV。这个时候，我们只需要添加一条从老Redis读取的用户历史播放记录，就可以迁移历??史数据了。为了触发用户播放记录生成布隆过滤器的过程，我们需要将用户ID保存到时间环上对应的播放用户列表中。最终的解决方案如图11所示。（图11：最终迁移方案）首先，DBA帮我们扫描出旧Redis中播放记录的key（包括用户ID），并通过文件导出；然后，我们将导出的文件通过大数据平台导入到Kafka中，并启用消费者监听和消费文件中的数据，解析后写入到当前时间环对应的播放用户列表中。接下来，分布式批任务读取到播放用户列表中的某个用户后，如果该用户还没有迁移过数据，则会从旧的Redis中读取历史播放记录，并用新的播放记录更新Bloomfilter并保存到磁盘KV。五、总结本文主要介绍短视频基于Bloomfilter构建推荐去重服务的设计思路，并从问题出发，逐步设计优化解决方案，力求简单、完美、优雅。希望能对读者有所借鉴和参考价值。由于文章篇幅有限，有些方面没有涉及，很多技术细节也没有细说。如有任何问题，请继续交流。
