携程 | 响应速度与智能化如何平衡,携程酒店搜索系统实践

作者简介
mczhao,携程资深软件工程师,关注自然语言处理、搜索引擎和数据库内核开发。

概览

随着线上旅游业务的不断发展,携程酒店的数据量不断增加,用户对于搜索功能的要求也在不断提高。携程酒店搜索系统是一个基于 Lucene 开发的类似 Solar 的搜索引擎系统,本文将从四个部分描述对搜索引擎的优化。

第一部分,通过优化存储来降低响应时延,提升用户体验,降低硬件成本。第二三部分,通过召回和纠错的智能化来提升用户体验。第四部分,通过重新设计搜索 DSL 提高业务灵活性和研发效率。本文也描述了在优化过程中遇到的各种问题和解决方法。

一、存储优化

1.1 数据压缩

在 Lucene 8 中,long 型的数据会被自动压缩存储。我们可以去除搜索 shema 中原有的 byte、short、int 类型,对整型字段统一使用 long 类型存储,而不用担心其占用多余的空间。这既降低了对内存和磁盘的需求,也降低了运维的人力成本。###

1.2 空间索引

在地理查询和存储这块,使用 PointValues 来替换原来的 GeoHash 索引。PointValues 是从 Lucene 6 开始引入的一个新特性,使用 kd 树作为地理空间数据结构,来加速几何图形内点的过滤筛选。

踩过的坑

  1. 尽管 Lucene 官方极力宣传 PointValues 的性能优势,也许在二维地理搜索场景下是这样,但是在一维数据中其性能还是远逊于普通的倒排索引,甚至不如走逐个访问过滤。究其原因是 PointValue 中 KD 树的节点都是压缩存储,其 CPU 时间大部分消耗在对存储的解压和反序列化,造成浪费。
  2. 而对于高维空间的搜索,例如通过 word2vec 的词向量搜索某个词的相似词,无论是 KD 树还是 VP 树,其时间复杂度都会退化到不可忍受的地步。

1.3 KV 存储

搜索流程不仅需要依靠倒排的索引,也需要正排的数据。在过滤和排序的搜索步骤中,需要根据主键来访问 doc 的一些维度信息,来判断该 doc 是否满足过滤条件,或者用来计算这个 doc 的排序分数。

在早期 Solar 版本中,使用了 FieldCache——一种内存中 SST 来保存这些 KV 数据。从 Lucene 4 开始,DocValues 作为 KV 数据的一种磁盘存储方案。在 Lucene 7 版本中,使用倒排索引中的 DISI 作为 DocValues 的索引,而 FieldCache 已经被移除。在 Lucene 8 版本中,DocVaues 添加了 jump table 来增强其随机访问能力。

Lucene DocValues 相对于 FieldCache 的优势是:

  1. 存储在磁盘,对内存需求减少。
  2. 存储经过压缩,消耗资源进一步减少。

Lucene 内部的 KV 存储有一定局限性,例如:

  1. 使用磁盘的存储时,需要将 byte 数组反序列化,还是略慢于内存中直接存储的数据结构。
  2. 只能用 docid 作为 key,如果使用业务 id 来访问,需要先查询倒排索引获取其 docid,再访问正排数据获取值。
  3. DISI 存储的 docid 范围只能在 32 位整型内,当遇到单点几十亿级别的数据,就无法存储了。

在某些场景下,给酒店打排序分时,需要获取酒店到 POI 之间的关联分数,此类分数不仅仅是通过直线距离计算得来,还需要考虑驾车步行距离的时间,以及距离筛选的酒店点击量等等因素,所以需要一个酒店到 POI 之间关联的 KV 存储。酒店和 POI 数据量各自是百万级别,而一个 POI 周边的酒店数平均是千级别,这样他们之间关联数据条数可达数十亿。

为此,我们自研了一种 Java 内嵌 KV 存储,和 Lucene 的索引中"mmap"模式一样,利用 JDK 自带的 MappedDirectedBuffer,将数据存储在磁盘上,将磁盘和内存的交换交给操作系统托管,也不会给堆内存造成压力。不同于 Lucene 的 DISI 和 LevelDB 的 SST,考虑到减少磁盘和内存的交换,已经提高 TLB 的命中率,其索引是固实化(compacted)的 BTree,也就是一棵用数组表示的完全 n 叉树,其查询的时间复杂度为对数,索引合并时间复杂度为线性。相比使用排序数组的 SST,空间占用一样,优势是查询时内存页跳转减少,劣势是 compact 的时候需要随机访问磁盘,而不是顺序访问。

踩过的坑

  1. 虽然 Lucene DocValues 是一种磁盘存储,但由于其实现和 FieldCache 有着诸多相似特性,部分元数据甚至是数据本身还是需要加载到内存的,这个加载的过程在 DocValues 的 API 中是懒加载的,并且会消耗一定的时间,需要注意其争用引起的线程阻塞。最好在初次加载索引和之后,或者写线程每次 flush 和 compact 之后,触发一次 DocValues 的数据加载,再让读线程可见。
  2. 虽然 Lucene DocValues 支持随机访问,但其 API 的实现还是相对滞后。在一次请求中,不允许访问的 docid 大于或等于上次访问的 docid,强制整个打分过程是顺序访问的。这自然有他的道理:顺序访问的性能更好。但排序过程可能依据多个分数,多个分数的计算公式中可能引用同一维度的字段,这样会造成重复访问同一 doc 的同一字段的 DocValues,使得 API 报错。解决的方法是将之前查询到的字段值缓存入当期的 context 中,下次访问时直接获取缓存。另外一种解决方案,直接修改 Lucene 源代码,消除这个不必要的限制,代码位置在 MultiDocValues.NumericDocValues.advanceExact 和 MultiDocValues.SortedNumericDocValues.advanceExact。
  3. 虽然可以使用 MappedDirectedBuffer 将存储移出 JVM 堆,减轻了堆 GC 的压力,但是当堆外内存脏块超过一定阈值,操作系统还是会触发阻塞整个进程的 flush 工作。解决方法是将磁盘映射文件打开为 read-only,用作 append-only 数据库的存储。没有对现有块的修改就不会存在脏块,而内部异步 compact 来实现增量更新。这样,只会存在缺页加载的 IO 操作,被淘汰的页可以立即丢弃,而不用刷回磁盘。

二、查询智能化

当今搜索系统中,单纯的文本召回已经不能满足用户的要求。搜索引擎需要根据用户的输入,识别用户输入的语义和意图,进而修改召回和排序方式。

2.1 语义查询生成流程

  1. 第一步是实体标注。将实体名称作为词库给用户输入分词以后,给分出的每一个词标注实体,识别其类型和对应 ID。
  2. 第二步是提取核心语义。例如,用户 输入” 浙江杭州西湖希尔顿”,需要识别出浙江是杭州的上级、杭州是西湖的上级,从而忽略掉” 浙江” 和” 杭州”,其核心语义就是” 西湖” 和” 希尔顿”。
  3. 第三步是查询生成。根据上面的核心语义” 西湖” 和” 希尔顿”,通过规则系统,生成查询,优先查找西湖周边的希尔顿集团下的酒店,即使这些酒店文本中,看不出包含” 浙江”、” 杭州”、”西湖”、”希尔顿” 中的任意一个。

2.2 语义分析的常用算法

2.2.1 上下文无关句法分析(CFG)

  1. 优点:可以转化为自动机,计算速度快
  2. 缺点:语法规则固定,不适合分析比较灵活的自然语言

2.2.2 依存句法分析

依存图的主要思想是连接短语的中心词与其依存词。用有向边把中心词与依存词连接起来。依存分析中一个重要的概念是投射性,是由单词之间依存的线性词序决定的一种约束。投射性的的依存句法等价于 CFG,非投射的依存句法的描述范围比 CFG 更广。

  1. 优点:较为灵活,规则简单
  2. 缺点:有的情形,时间复杂度会退化到指数级别

2.2.3 酒店联想引擎中使用的语义分析

为了克服上述经典语法分析的一些弱点,酒店联想使用一种依据知识图谱分类分层的简化依存分析方式。根据酒店的业务场景,将标注后的实体词性放入不同的 bucket 中,进而进一步查询 bucket 内部实体和 bucket 之间实体的关联关系,进而去除修饰词,提取核心语义。同一 bucket 中的实体类型可以进一步分层,例如区域类型中省份、国家、城市、景区都可以分为单独的一层,再去获取彼此之间的关系。从而避免算法复杂度的爆炸。

三、智能纠错

Lucene 自带的英文单词相似度纠错,是通过 ngram 分词索引召回,从词库中粗筛出候选词,进一步使用 Levenshtein 编辑距离精筛出相似度高的词。

我们在 Lucene 纠错的基础上,做了更多的优化,我们的纠错会考虑上下文,纠错词库的数据来源也更加多元化,目标是使得我们的英文纠错可以媲美 Bing 或者 Google。

3.1 LSH 局部敏感哈希

随着业务增长,作为基础语料的实体数量也在增长,纠错词库的数据量随之增长,Lucene 默认的 ngram 召回的候选词集合开始变得不那么准确,很多的用户目标词在粗筛过后就不在候选集内,导致无法正确纠出。我们需要考虑加入不同的维度作为 Hash 桶,来进一步缩小粗筛的范围,比如词长是一个比较好的维度;并且调整 ngram 中参数 n 的大小,以及分词以后的查询交并关系,使有限的粗筛召回结果更加精确。

3.2 上下文纠错

只考虑单词而不考虑上下文的纠错,就像只考虑单词热度而不考虑上下文的分词,有诸多局限性。例如真词纠错 case,用户输入把 le meridien(艾美酒店)错输入为 let meridien,单看 let 这个单词是并没有错的,即使认为它是错的,那么 let 和 le 直接的相似度最高也只有 66.7%,看起来也不高,不一定能达到精筛过滤的相似度阈值。



所以我们在纠错的时候也需要考虑上下文。通过现有实体语料以及其热度,统计出热门的二元词组及其热度。然后在纠错词,将二元词组作为单词来进行纠错。这样也可以对用户少输入或者多输入的空格进行纠错,并且可以解决空格问题和拼写错误同时存在的场景。例如:用户输入 southcoase,通过一次纠错就可以纠出 south coast 这个词组。

通过二元词组库的纠错,只能往前/后多看一个词的上下文,有的情况下这么短的上下文并不能判断出最佳的纠错词。这时候可以将所有实体名称作为词库来纠错,由于其数据量庞大,粗筛的桶参数调整难度更大。另一方面,由于 Lucene 倒排索引下都是按 docid 排序的,docid 是按数据插入顺序自增,所以我们可以先按热度排好序建入索引,再使用 totalHitsThreshold=n 限制召回的匹配条数,确保粗筛召回的是最热的 n 条记录。

3.3 优化编辑距离算法

经典的 Levenshtein 编辑距离算法,其状态转移发生在矩阵的 2x2 的范围内,无法识别出字符交换的操作。如果我们把其状态转移方程扩充到 3x3 的方格内,根据行和列上各自前两个字母来计算本单元格内的距离,即可识别出字符交换的操作。除此以外还能识别出字符双写漏写为单写,以及单写漏写为双写等场景,分别根据不同场景配置不同的距离权重,可以更加精细地计算两个词的相似度。

如果把根据前两个字母算的编辑距离称为 2 阶编辑距离,那么 2 阶可以扩展到 n 阶,n 越大,能覆盖的情形越丰富,相似度越准确,纠错效果更好。但是算法的时间复杂度也随着 n 几何增加。实际使用时,按场景需求选择 n。这种扩充到 n 阶的想法来自于 Damerau-Levenshtein 编辑距离,Damerau-Levenshtein 编辑距离是一种 2 阶编辑距离。

编辑距离加权的思想也是在很多 NLP 论文中有提到,除了处理双写、调换等场景以外,也可以处理音近词特别是一些从别的语言翻译而来的音近词,特别是旅游业务背景下,很多地名都是按当地语言翻译过来的。举个中文的例子,从英文翻译而来的亚马逊和亚马孙,从"逊"到"孙"的编辑距离权重几乎可以配置为 0,意味着亚马逊和亚马孙相似度 100%,类似的 case 在作为表音语言的韩文和俄文的翻译文本中更多。

四、搜索 DSL

DSL(Domain Specific Language),中文翻译为领域特定语言,相对于 GPL(General Purpose Language)通用编程语言,DSL 指的是专注于某个应用程序领域的计算机语言。

James Gosling 曾经说过:每个配置文件最终都会变成一门编程语言。搜索系统的复杂化导致其配置的复杂化,根据不同的用户输入核心语义、不同的用户偏好、不同的搜索上下文,生成搜索查询和排序,这样的规则系统需要复杂的配置。Lucene 原本也有自带的查询语言,类似 SQL,可以定义召回、排序、分页等逻辑,但这样的查询语言已经不能满足我们日益复杂的需求,严重制约了开发效率,我们需要将搜索语言扩展甚至重写,就像从 SQL 扩展到 PL/SQL 那样。

4.1 设计考量

4.1.1 降低学习成本

设计查询语言的时候,需要尽量向 SQL 语言看齐。SQL 是大家已经广泛熟知的查询语言,语法越和 SQL 一致,越是降低学习难度。

在 Elasticsearch 的结构化 DSL 中,使用的是 must、should、must not 查询方式,这样的查询方式虽然贴合 lucene 底层查询方式,但是从一个没有接触过类似搜索产品的开发看来需要学习成本。在 Lucene 自带的查询语言中,虽然可以使用 AND、OR 这些交并条件,但其实现是有 bug 的,其运算符优先级有问题,导致一些场景优先执行 OR 再执行 AND,需要开发小心翼翼地给所有的子表达是添加合适的括号,更不幸的是,lucene 的查询语言编译器通过 JavaCC 自动生成,不是人手写的代码,可读性很差,很难修改。

SQL 和其他 GPL 相比,最显著的特征是其逻辑运算符的优先级,需要低于比较运算符。另外一个特征是两个整型相除,一般数据库实现默认返回的是浮点型数据,而不是整型,对于整数相除,另外使用内置函数实现。

除了向 SQL 看齐,其数字类型和字符串类型的表达方式向 EMCAScript 看齐,因为当前 JSON 作为最常用的序列化方式被大家广泛熟知,JS 的字符串转义也比 Java 更加方便。当然,EMCAScript 不支持 64 位整型,而我们需要支持,特别是当日期时间转化为 long 参与计算的时候。

4.1.2 面向高性能场景

一次搜索请求中需要对召回的数以万计的 doc 去做过滤和计算排序分,但又对响应时间比较敏感,特别是在联想推荐的场景中,用户每输入一个字,就要立时修改推荐的内容。所以在设计语言时,需要保留对 CPU 和内存友好的特性:

  1. 基于性能考虑保留 primitive type,借鉴基于 C 的脚本语言 lua,只保留两种数值类型——整型的 long 和浮点型的 double,并且强转系统。基础类型是现阶段 Elasticsearch script 的诸多实现中仍没有实现的功能。
  2. 查询过滤,比较字段和值时,使用 lucene 列式存储,即 DocValues,而不是去获取行数据。
  3. 去除 CBO(基于成本的优化器)。如果开发对执行计划了然于胸,就会发现在一些复杂场景下传统数据库中的 CBO 经常帮倒忙,导致我们不得不使用 use index 这种语法。去除 CBO 的同时,用不同的语法让开发可以自定义执行计划是走索引还是走过滤,降低执行计划的不确定性,也可以降低查询编译期的耗时。而 RBO(基于规则的优化器)中的一些规则可以保留,比如任何条件和 false 取交集,默认就返回 false,而不是真的去执行其查询。

4.1.3 多态

搜索语言需要支持编译时的多态,提高用户友好性。

  1. 函数多态,例如 max 函数,如果传入的是整型那么返回的也是整型,如果传入的是浮点型,返回的也是浮点型。
  2. 运算符多态,例如加号"+"运算,如果两边都是数值类型,那么按数值相加,并且设计合适的隐式转换规则;如果一边是字符串,那么就把两边按字符串 concat 起来。

支持更多的地理搜索功能

从语言层面支持地理搜索,而不需要编写各种语法糖。

除了支持常用的距离范围搜索,还利用了计算图形学的算法和 KD 树,支持多边形内的点的搜索、点到多边形的距离搜索,用于查询多边形区域范围内以及周边的召回。

4.1.4 安全性

搜索语言需要支持查询参数化,来避免查询脚本注入。这一点和 SQL 一样,Elasticsearch 也已经支持参数化的 script。我们对参数化进行了扩展,使其参数本身可以为一个表达式,在查询编译时预执行,实现类似 Shell 或者是 JS 中 eval 的功能。

4.1.5 支持描述业务流程

上文中所说的在查询编译时预执行的表达式,是一种 doc 无关的表达式。相比而言,查询执行时的表达式都需要传入一个 docid 来获取当前 doc。

上文中描述的语义分析提取核心词以后,需要通过核心词以及规则系统生成新的查询和排序。这种 doc 无关的表达式,我们正可以用来支持规则系统这种和具体 doc 无关的业务逻辑,类似 PL/SQL 这种面向存储过程的语言,这也是 Elasticsearch 中暂未实现的功能。

踩过的坑

上设计一门新的语言时,不要一开始就设计为词法分析和语法分析双层编译结构,也不要一开始就设计 action 表,因为在设计新语言的一开始可能并不清楚词法和语法的边界在哪里,即使事先明确定义,做到一半的时候可能还会再做修改。对于语法简单的 DSL,使用基于字符的递归下推自动机实现编译功能是更好的选择,对于后续的语法修改会更加灵活。

总结

搜索引擎本身对数据库事务要求不强,数据计算量比较大,是一种 CPU 密集型的、对响应时间敏感的信息检索系统。一方面是用户对于其智能化的需求,一方面又是用户对于其响应速度的需求,保持两者之间的平衡一直是个难题。

所幸业界有很多较为成熟的搜索产品:Solar/Lucene、Elasticsearch,也有很多可供借鉴的算法,还有很多或新或旧的存储,例如 HBase、LevelDB、RocksDB 等等。他山之石可以攻玉,只要我们不迷信权威,充分了解这些产品或者算法背后的实现原理,就可以站在巨人的肩膀上,更加灵活地找到适合当前场景的技术方案,甚至创造出全新的算法和工具,不断提升用户的搜索体验。


本文地址:https://www.6aiq.com/article/1604530710213
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出