性能优化之搜索和推荐系统

为什么同样的查询我的代码p99要1s,别人的只要50ms?

为什么Google能20ms内检索800亿的文档,而我只能检索5百万?

为什么Facebook的faiss可以处理上亿数据最近邻而我的机器几百万都存不下?

在我之前的文章“白板面试和程序优化这么火,到底为什么?”中我们简单的聊了聊如何衡量优化程序的价值以及重要性。

最近我又一边实践一边重温了几篇经典文章,Jeff Dean的“Achieving Rapid Response Times in Large Online Services”,LinkedIn工程🦁博客的“Who moved my 99th percentile latency?”还有几篇“How to write efficient code”。

借着这个劲,今天我来聊一聊搜索和推荐系统中的性能问题与优化。我就随便说说,你且随便看看罢。

越快越好,越挑战

对于大部分互联网服务,网站相应时间和用户满意度是非常相关的。

如果你是一家电商,用户输入一个Query后1~2s都没有结果显示,这时间就足够他去访问Amazon或者Google,开始新的一次查询。

如果你是一家社交网络,用户登录1~2s内都没有信息出现在newsfeed上,那他们就会转战Facebook,Snapchat或者朋友圈,因为那里很快就能告诉你朋友们都在忙什么。

去衡量网页打开的时间,一台服务器返回结果的延时比较容易,每个工程师都会建立一些dashboard展示系统情况。但是去优化这些延时却很难,尤其是对搜索引擎,推荐系统的优化。

搜索和推荐系统的计算量很大,一个请求往往需要对上百万个文档打分,每个文档又有上百或者上千维特征,单个cpu进行打分可能就需要1s以上。

现代互联网服务的搜索和推荐cache命中率较低,因为大家都在提倡个性化搜索和推荐结果,用户数✖️问题数空间极大,降低了cache命中率。

大规模的搜索和推荐系统,每一个请求背后都对应着几百或者几千个小请求,服务器需要将搜索问题发送到每一个搜索叶子节点,然后汇总结果,延时取决于最慢的服务器。

从数据备份入手

搭建大规模的搜索和推荐引擎,系统方面需要考虑几个基本问题,scalability,availability和latency。

对于scalability,最常见的解决方案就是通过sharding将文档分散存储到不同的机器上,控制单机支持的文档数量,然后通过replication支持更多的请求。

当我们收到一个搜索请求后,通过superroot服务器将请求发送到不同的搜索机器上,然后汇总结果。

如何做sharding和replication?常见的方法就是设置N个备份,每个备份有M个shard,每一个搜索请求最后会发送到M个shard上进行计算。

这种做法实现简单,但是问题也比较多。

因为数据是均匀分布的,当你发出的M个请求里有1个请求没有在规定时间内返回搜索结果,那你有1/M的可能性丢失最好的搜索结果。

另外文档有质量高低之分,大部分低质量文档是用户这辈子不会接触到的,但普通的备份思路会把低质量文档也备份N份,浪费了存储空间。

如果我们先用这样的方式提供搜索文档,然后根据历史数据将文档分为高质量或新产生的文档集合A,以及低质量基本没有人看的文档集合B,我们可以更好地对数据进行分配。

我们像下图一样将集合A分割为4份,每份数据存到3台机器上,然后将集合B分割为6份,每份数据存到2台机器上。

对于一个搜索请求,我们仍然将它发送到第一个集群上去,在程序中加入优化,如果6台机器里任意2台包含不同高质量文档集合的机器返回足够多的搜索结果,我们就可以停止搜索。这样就可以更快的服务大部分请求,并且满足他们对搜索质量的要求。

另一方面,autoscale搜索或推荐引擎并不是一个简单的任务,通过特殊的备份方式,我们可以帮助在高峰期巧妙的增加容量。每到高峰期时,superroot有选择的将部分搜索问题只发送到一个集群的2台包含不同高质量文档的机器上,瞬间将备份数从2增加到了6。

牺牲容量换时间

说回latency,由于一个请求需要从很多台机器上获取结果,有的时候一台机器会因为系统中运行的其他程序产生高延时。我们既想优化时间,又不想丢失数据,那只能请Jeff Dean来帮忙了。

在Jeff Dean的“Achieving Rapid Response Times in Large Online Services”演讲中,介绍了一种叫备份请求(Backup Requests)的优化方案,目标是在不增加太多资源消耗又想拿到完整结果的前提下减少延时。

以In-memory BigTable Lookups为例,一个请求可能要查询1000个键值,均匀分布到100多台机器上,其中每个键值都被备份到多个机器上。当我们不做任何优化,去询问100多台机器时,平均耗时33ms,99%的延时52ms,99.9%的延时可能会高达1s,因为总有一台机器在做别的事情,返回速度很慢。

如果采用备份请求优化,一个机器在10ms内没有返回结果,我们将请求发送到另一个拥有一样数据的机器上,当某一个机器返回结果时候取消另一个请求。这样一来,平均耗时一下降到14ms,99%的延时23ms,99.9%的延时变成了50ms。

对比前者,通过不到5%的额外请求,99%的延时下降了一半,99.9%的延时只有之前的5%。由此可见,备份请求可以再很大程度上改善由于长尾效应带来的延时。

备份请求还有很多变种,比方多次备份,以及备份的机器间相互通讯,取消对方的请求。

但是要注意备份请求并不是万能的,对于查询的优化效果比较好,但是对于不可多次执行的更改,比方交易记录就有可能会出问题,这需要consensus algorithm来确保数据正确性。

优化程序与工具

谈优化谈到最后就是优化程序本身,如果单机进行各种计算就要1s,那就不用谈什么把集群99%延时降到50ms了。

程序优化第一步就是选择适合的算法。举一个简单的例子,我们要合并来自20台机器的搜索结果,每个机器返回300个文档,然后选出top 100,很明显,这是一个归并排序的过程,因为每台机器返回的搜索结果都已经排好序了。我们可以用一个Priority Queue找到top 100结果后返回。

我还真见过有工程🦁将这6000个搜索结果放在一个数组里,然后调用一下sort函数;或者用归并排序排好6000个结果中途没有调用break。

算法选好,接下来就是好的数据结构。一个常见的例子就是存储文档的feature。

最容易读的feature存储就是采用字典,document[category]=animal, document[repin probability]=0.1, …可是字典虽然容易理解但是使用效率低下,一个简单的包含10个特征的linear scoring function,如果我们传入字典进行打分耗时需要5731ns/op。

优化一下数据结构,采用sparse vector替代字典,每次打分耗时只需要338ns/op,这可是超过10倍的计算优化。

除了优化程序的运行速度,有一点常常被初级程序员忽略的就是程序启动时加载数据耗费时间。

在从前工作中,我常常使用tsv文档存储字典,对于一个包含10 million词组的字典,每一行是一个词对应一个词频。当程序启动时把tsv文档读到内存当中,耗费大约10秒钟。

但是如果我们用一个好的工具,比如Lucene里的FST(Finite State Transducers),Michael McCandless在他的文章“Using Finite State Transducers in Lucene”中有介绍,一个包含10 million的字典只需要8s建立,占用256MB空间,和69MB的硬盘大小,每次加载都在1s以内。

如果只看单次运行,对于程序启动的优化不算什么,但是实际工作中我们一天可能需要几十,几百次启动程序,进行调试,小的优化可以节省非常多的时间。

小结

对于程序的优化我们先讲到这里,今天简单的谈了谈如何更好的备份数据,通过额外的请求来降低长尾效应,还有对于程序本身优化的小想法。

对耐心读到这里的读者我要说一声谢谢,如果感兴趣还可以看看我之前的:

白话搜索,将你的搜索引擎提速100倍

Python,你怎么那么慢

Python,你怎么那么慢?看看并行和并发

不需要华丽技巧,也能写出高质量产品代码

对于性能的优化是没有尽头的,我也会继续积累知识,和你们分享在实践中的感悟,谢谢大家关注和转发。