通用搜索引擎应用在互联网商用搜索通常会遇到如下几个问题:
实时索引我们采用面向队列的架构,数据首先写入DB(或文件),然后通过数据库同步机制将数据流写入kafka队列。这种同步机制和数据库主从同步的原理相同,主要的开源产品有mypipe和阿里推出的canal。es通过订阅相应的topic实现实时建立索引。
如果数据源是文件,则使用flume实时写入Kafka。
另外一个索引问题是全量索引。有如下几个场景让全量索引是一个必要过程:
我们采用Hadoop-es利用hadoop分布式的特性来创建索引。hadoop-es让分布式索引对用户透明,就像单机更新索引一样。一个是分布式的数据平台,一个是分布式搜索引擎,如果能把这两个结合就能够实现分布式的全量索引过程。Hadoop-es正式我们想要的工具。
我们给出一个通过Hivesql创建索引的栗子:
系统把es映射成hive的一个外部表,更新索引就像是写入一个hive表一样。实际上所有分布式问题都被系统透明了。
不建议从数据库或文件系统来全量索引。一方面这会对业务系统造成很大的压力,另一方面因为数据库和文件系统都不是真正分布式系统,自己写程序保证全量索引的水平扩展性很容易出问题,也没有必要这么做。
全量索引和增量索引的架构如下图所示。另外一点是hadoop也是订阅kafka备份数据库和日志的。我个人建议一个公司所有DB和文件都存储在hadoop上,这样做起码有二个好处:
为什么我们选择Kafka?Kafka是一个以高吞吐著名的消息系统。Kafka开启了日志合并(logcompaction)功能后,可以永久保存每条消息。每一条消息都有一个key,正好对应数据库的主键,Kafka始终保存一个key最新的一条消息,历史版本会被垃圾回收掉。有了这个特性,Kafka不仅可以保存数据库最新的快照,而且可以实现实时更新的消息系统。
第一次同步的时候,数据表中每行记录都转化成以主键为key的消息进入Kafka,并且可以被任意数量的broker消费。之后数据库的每次更新(insert,updated,delete)都会被转化成Kafka的消息。如果一行记录频繁被更改,Kafka会识别这些重复的消息,把旧的消息回收掉。
Kafka既保存数据库最新的全量数据,又提供实时数据流的这个特性为架构的可维护性提供极大便捷。如果你想从零扫描整个数据库,你只需要从开始消费这个Kafka的topic即可完成,当读到topic末端,自动获得实时更新的特性。
高级搜索模块(AS)在商业搜索引擎起到至关重要的作用。在各大商业搜索引擎公司里面AS已经成为标配,也是变更最为频繁的模块。
AS在商业搜索引擎中主要起到如下作用:
AS一个主要的功能是通过一个个业务插件来代表相应的搜索。一个最简单的插件只需要包含对应的ESsearchAPI,它实际上就是一个配置项,说明es的地址。这样AS就是一个纯代理。但是商业搜索的需求都是不是ES本身能够支持的,所以就需要根据需求写相应的Queryrewriter,rerank等算法插件。这样就实现了框架和业务分离,AS具有极强的扩展性和复用性。
AS另一个功能是提供通用算法库,实际上它只为每种算法提供编程框架。算法也是通过插件的方式加入算法库的。这种方法可以让算法工程师抽象公共算法库供业务方使用,避免重新造轮子。一个具体业务要么使用已经存在的算法(并修改参数),要么自己实现算法。
上图是一个实例。商品搜索和分销搜索各自实现一个rerank的的算法,同时都调用了系统提供的rerank1的算法库,并加入了自己特有的逻辑。
AS除了基本proxy功能外,还提供基于query的cache功能用于应用级别的缓存。内部有一个缓冲队列,防止出现雪崩现象。下一节性能优化中会详细说明。
下面几个小结,我们写了几个我们遇到的性能优化场景。
ES一个问题是在高峰期时候极容易发生雪崩。ES有健全的线程池系统来保证并发与稳定性问题。但是在流量突变的情况下(比如双十一秒杀)还是很容易发生瘫痪的现象,主要的原因如下:
在AS里我们实现了面向请求的全局队列来保证稳定性。它主要做了3件事情。
应用级队列解决雪崩问题有点粗暴,如果一个应用本身查询就非常慢,很容易让一个应用持续超时很久。我们根据搜索引擎的特点编写了自动降级功能。
对于有降级方案的slide,AS在队列响应过慢时候直接使用降级query代替正常query。这种方法让我们在不扩容的情况下成功度过了双十一的流量陡增。
理解lucencefilter工作原理对于写出高性能查询语句至关重要。许多搜索性能优化都和filter的使用有关。filter使用bitsets进行布尔运算,quey使用倒排索引进行计算,这是filter比query快的原因。bitsets的优势主要体现在:
举个例子:
lucence处理这个query的方式是在倒排索引中寻找这三个term的倒排链,并使用跳指针技术求交,在运算过程中需要对每个doc进行算分。实际上tag和region对于算分并没有作用,他们充当是过滤器的作用。
一个lucence金科玉律是:能用filter就用filter,除非必须使用query(当且仅当你需要算分的时候)。
lucence的filteredquery会智能的先计算filter语句,然后才计算query语句,尽可能在进行复杂的倒排算法前减少计算空间。
除非有必要把all字段去掉。索引默认除了索引每个字段外,还有额外创建一个all的字段,保存所有文本,去掉这个字段可以把索引大小降低50%。
创建索引时候,尽可能把查询比较慢的索引和快的索引物理分离。
本文对es本身的优化写的不多,因为es官网和其他的博客有很多es优化的意见,就不在一一枚举。本文的主要目的是能够对搭建商用电商搜索引擎给读者一个一般性的建议,另外,困扰商用搜索引擎的最常见的问题是排序和算法问题。
在上半部分中,我们介绍了有赞搜索引擎的基本框架。搜索引擎主要3个部件构成。第一,hadoop集群,用于生成大规模搜索和实时索引;第二,ElasticSearch集群,提供分布式搜索方案;第三,高级搜索集群,用于提供商业搜索的特殊功能。
创建索引过程从原始数据创建倒排索引的过程。这个过程中我们对商品(doc)进行分析,计算商品静态分,并对商品进行相似度计算。商品的静态分对于提升搜索引擎质量起到至关重要的作用,相当于网页搜索的pagerank,想象一下如果没有pagerank算法,网页搜索的质量会有多么差。在电商搜索中,最常见的问题是相似商品太多,必须在建立索引过程中就对商品间的相似度进行预计算,以便在检索过程中进行有效去重。
创建索引的过程如下:
step1,计算每个doc的静态分;
step2,计算两两doc的相似度;
step3,根据相似度和其他信息对数据进行分库;
step4,建立ES索引。
重要性是指商品被信赖的程度,我们应该吧最被消费之信赖的商品返回给消费者,而不是让消费之自己鉴别。尤其是在商品充分竞争的电商搜索,我们必须赋予商品合理的重要性分数,才能保证搜索结果的优质。重要性分,又叫做静态分,使用Tscore表示。
搜索引擎最终的排序依据是:
Score=Dscore*Tscore
检索的过程大致抽象为如下几个步骤。
step1,对原始query进行query分析;
step2,在as中根据query分析结果进行query重写;
step3,在as中使用重写后的query检索es;
step4,在es查询过程中根据静态分和动态分综合排序;
step5,在as中吧es返回的结果进行重排;
step6,返回结果。
在电商搜索引擎里面商品的静态分是有网页搜索里面的pagerank同等的价值和重要性,他们都是doc固有的和查询query无关的价值度量。pagerank通过doc之间的投票关系进行运算,相对而言商品的静态分的因素会更多一些。商品静态计算过程和pagerank一样需要解决如下2个问题:
我们假设商品的静态分有3个决定性因素:1,下单数;2,好评率;3,发货速度。
静态分我们使用Tsocre表示,Tscore可以写成如下形式:
Tscore=a*f(下单数)+b*g(好评率)+c*h(发货速度)
a,b,c是权重参数,用于平衡各个指标的影响程度。f,g,h是代表函数用于把原始的指标转化成合理的度量。
首先,我们需要寻找合理的代表函数。
z-score标准化方法
“概率论”告诉我们对于满足正态分布的数据来说,均值前后3个z-score的范围可以覆盖99%的数据。经验地,我们把>5个zscore或者小于-5个zscore的分数设置成5*zscore或者-5zscore。特别说明的是,我们不建议使用min-max标准化方法。这种方法又叫离差标准化,是对原始数据的线性变换,使结果值映射到[0-1]之间,转化函数如下:
这种方法非常不稳定,假设一个奇异点是第二大的值的1000倍,会让大部分的值都集中在0~0.01,同样失去了归一化的目的。
图一是使用min-max归一化后的数据分布,显然大部分数据被”压扁”在很小的范围;图二使用log归一化后的数据分布,由于log缓解了增长速度,可以看出来已经有一个不错的结果了;图三是在log的基础上进行z-score归一化,可以看出来,z-score让数据变得非常平滑。
(图一:min-max归一化)
(图二:log归一化)
(图三:log-zscore归一化)
最后,选择合适的权重经过log-zscore归一化以后,我们基本上吧f,g,h的表示的代表函数说明清楚。Tscore=af(下单数)+bg(好评率)+c*h(发货速度),下一步就是确定a,b,c的参数。一般有两个方法:
商品标题去重在电商搜索中起到重要作用,根据数据,用户通过搜索页购买商品80%选择搜索的前4页。商品标题的重复会导致重要的页面没有含金量,极大降低了搜索的购买率。
举个例子:
Title1:美味/香蕉/包邮/广东/高州/香蕉/banana//无/催熟剂/
Title2:美味/香蕉/广东/高州/香蕉//非/粉蕉/包邮/
这里用到“bagofword”技术,将词汇表作为空间向量的维度,标题的每个term的词频作为这个feature的值。以这个例子来说。这个词汇的维度为:美味(0),香蕉(1),包邮(2),广东(3),高州(4),banana(5),无(6),催熟剂(7),非(8),粉蕉(9)位置:0,1,2,3,4,5,6,7,8,9
Title1:1,2,1,1,1,1,1,1,0,0
Title2:1,2,1,1,1,0,0,0,1,1
这个每个title都用一个固定长度的向量表示。
再次,计算两两相似度。
相似度一般是通过计算两个向量的距离实现的,不失一般性,在这里我们使用1-cosine(x,y)来表示两个向量的距离。这是一个”AllPairSimilarity”的问题,即需要两两比较,复杂度在O(n^2)。在商品量巨大的时候单机很难处理。我们给出两种方法用于实现”AllPairSimilarity”。
方法一:spark的矩阵运算。
rddRows=sc.parallelize([“102001”,“004200″])
rddRows.map(lambdax:Vectors.dense([float(each)foreachinstr(x).split(”“)]))
mat=RowMatrix(rddRows)
simsPerfect=mat.columnSimilarities()
方法二:map-reduce线性方法。
doc1=我爱北京
doc2=我北京天安门
doc3=我天安门
转化为倒排格式,这个需要一次mapperreduce
我->doc1,doc2,doc3
爱->doc1
北京->doc1,doc2
天安门->doc2,doc3
然后,对于value只有一个元素的过滤掉,对于value大于2个doc的两两组合:
最后,对于输出进行聚合,value为重复次数和两个doc乘积开根号的比。
doc1,doc2->2/(len(doc1)*len(doc2))^1/2=0.7
doc1,doc3->1/(len(doc1)*len(doc3))^1/2=0.3
doc2,doc3->2/(len(doc2)*len(doc3))^1/2=0.3
对于2个title1,title2,如果X(title1,title2)>0.7则认为title1和title2相似,对于相似的两个doc,静态分大的定义为主doc,静态分小的定义为辅doc。主doc和辅doc分别建库。
区别于网页搜索(网页搜索直接将辅doc删除),我们将主doc和辅doc分别建库。每一次搜索按比例分别搜主库和辅库,并将结果融合返回。这样可以保证结果的多样性。
设想一下,如果我们根据店铺是否相同,把同一店铺的商品分到主库和从库中,如下图所示。
A和B代表不同的店铺。
在搜索香蕉的时候,的确可以控制A店铺结果的数量,但是在搜索”梨”的时候就错误的吧B店铺的梨排在前面了(假设A:梨比B:梨静态分高)。
实际上想达到店铺去重的效果通过分桶搜索是很容易做的事情。我们假设每页搜索20个结果,我们把索引库分成4个桶,每个商品对桶数取模得到所在桶的编号。这样可以保证同一店铺的商品仅在一个桶里面。搜索的过程每个桶平均分摊搜索任务的25%,并根据静态分合并成一页的结果。这样同一保证结果的相对顺序,又达到了店铺去重的目的。
如上图所示,搜索”香蕉”,虽然A店铺有10个满足需求的结果,但是每页搜索醉倒只有5个结果可以展示。
query分析与Query改写技术
上面介绍了几个建立索引过程中几项技术,检索过程中的关键技术有很多。其中最著名的是query分析技术。我们使用的query分析技术主要包括核心词识别,同义词拓展,品牌词识别等等。query分析技术大部分都是NLP研究范围,本文就不详细阐述很多理论知识。我们重点介绍同义词拓展技术。这个技术一般都需要根据自己的商品和和用户日志特定训练,无法像分词技术和品牌词识别一样有标准的库可以适用。
同义词拓展一般是通过分析用户session日志获取。如果一个用户输入”苹果手机”没有得到想要的结果,他接着输入”iphone”,我们在”苹果手机”和”iphone”之间创建一个转移关系。基于统计,我们可以把用户query创建一个相互联系的权重图。
用户输入query“苹果手机”,根据query分析,”苹果手机”有“iphone”0.8,”iphone6″0.5两个同义词。0.8和0.5分别表示同义的程度。我们想要”苹果手机”,”iphone”,”iphone6”3个query同时输入,并且按照同义的程度对不同的query赋予不同的权重。ElasticSearch提供的BoostingQuery可以支持这个需求。
原始的query:
优化后的query:
其他比如核心词识别,歧义词纠正等方法差不多,本文不做详细阐述。
搜索算法是一个非常值得一个电商产品持续投入的技术。一方面如果技术人员要有良好的技术背景,可以借鉴很多成熟的技术,避免重复造轮子;另一方面,每个产品的搜索都有自身的特点,需要深入研究产品的特性给出合理的解决方案。