Now 直播发现页短视频瀑布流优化

发现页是Now直播短视频的主要曝光平台（如下图），内容以运营人工筛选为主，瀑布流式展示。

为了兼顾短视频质量和时效性，短视频排序采用了重力算法：

H为短视频的质量分，通过观看，点赞，评论，转发等数据加权求和计算，T为短视频发布时间戳，T0位基准时间，取发现页最早发布的短视频创建时间戳，单位均为秒。A为时间系数，根据发现页短视频的平均更新间隔，取36000(10小时)。该算法的效果是，发布时间接近，质量分高的短视频靠前，随着时间推移，短视频不断下沉，削弱头部曝光产生的马太效应。

为了提高内容的新鲜感，我们希望用户在每次下拉刷新以及翻页的时候，都能看到新的短视频，同时在短视频列表头部加入新的短视频时，能得到优先展示，如下图所示：

左图为首屏显示的短视频，如在此时，短视频列表顺序发生了更新，C+和D+插入了EF的前面，我们希望在下次刷新的时候，优先插入C+、D+。实现这个需求最简单的方法是保存用户最近观看过的全部短视频作为过滤器，每次返回列表的时候，从头部开始遍历，去掉用户看过的短视频。显然，过滤器的容量，决定了短视频列表的最大展示深度。根据产品需求，发现页需要展示最近一个月的短视频，大约4000个，平均每个短视频id的长度为50字节，这个过滤器如果用传统的redis set等手段实现，存储成本和过滤效率都比较低，针对这个问题，我们采用了一个简单而强大的数据结构---布隆过滤器。

Bloom Filter(布隆过滤器)是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。

为了表达S={x1, x2,…,xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位）。

在判断y是否属于这个集合时，我们对y应用k次哈希函数，如果所有hi(y)的位置都是1（1≤i≤k），那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素。y2或者属于这个集合，或者刚好是一个false positive。

我们使用MurmurHash和bitset实现了一个可以序列化成整形数组的布隆过滤器，可以利用redis支持的简单key-value数据结构进行存取，在本地实现高效的过滤运算，一个能保存4000个短视频id的布隆过滤器，只占用不到8KB的空间，get&set的效率都比较高。

因为布隆过滤器容量有限，且无法删除元素，需要配合重建策略使用。我们用redis维护了一个最近观看的100个短视频id，当布隆过滤器空间利用率超过百分之50的时候，清空并使用这100个id进行重建，避免了极端情况下的重复问题。

短视频瀑布流刷新涉及到大量的图片下载，在图片加载期间，会显示默认底图（如下图）：

为了优化图片加载体验，尤其是网络条件较差时的展示效果，我们采用了预加载图片主色调的方法，即离线计算好短视频封面的主色调RGB值，使前端在完成图片下载前用主色调代替默认的底图，平滑图片的加载过程：

关于图片主色调的提取，我们尝试了多种算法，最终参考了《基于OTSU分割与K-均值聚类的MPEG-7主颜色提取算法》这篇论文，实现了短视频封面图片主色调的提取，基本方法如下：

1. 提取图片的RGB空间值，转化为HSV空间值
2. 对HSV空间下的像素点进行k均值迭代。
3. 选择点数量最多的一个聚类，将聚类中心的HSV空间值转换为RGB空间值。

以上几点是我们在NOW直播发现页瀑布流迭代优化中的一些尝试和技术总结，希望能给大家在开发Feeds流类型应用时提供一些参考，如有意见或建议，可与本文作者联系。