简
要
大
纲
1
看看系统诉求。
2
我们面临着什么问题。
3
我们的设计思路是怎样的。
4
粗略分享我们的大的搜索框架。
5
深入探讨一下其中的一个核心系统，报价引擎的设计与优化历程。
1
系统诉求
去哪儿网的定位是做全球最大的中文在线旅行网站。
对于机票业务来说，就是要从这些方面都做到最好。
1）我们希望用户在我们网站搜索出来的价格是全网最低的。
2）希望世界有的任何航线，都能在我们网站上搜出报价来。
3）希望报价的更新是最实时的，用户根本感知不到价格变化。
4）希望产品最大限度满足用户出行需求。
5）希望用户预订流畅，心情最愉快。
归根结底我们要取悦用户，用户第一是我们的口号，也是我们的压力所在。
2
面临问题
但是，这些方面要实现起来，做到最好，都不容易。机票行业与普通电商不同，有他的特点，最大的特点是价格和库存变化非常频繁，实时性要求很高。
1）库存变化体现在航班舱位的状态在时刻变动，特别是热门航线的航班，在出行高峰期尤其频繁。
2）价格变化则是因为机票的销售体系的特点，除了航空公司本身外，有大量的供应商，不同供应商的机票售价可能不一样，会根据各种情况动态调整，热门航线，出行高峰是价格变化的高峰。
3）除了供应商，作为机票的主要载体，航空公司也有很多运价方面的政策，这些政策也会根据各种情况进行调整，导致大量航班价格发生变化。
4）机票行业信息化比较早，所有的航班数据、运价数据、订座出票，都掌握在叫 GDS 的角色手中。国内主要的 GDS 是中航信。供应商和我们的数据都要从GDS 手中付费获取，付费一般是按指令执行次数来定的，价格不菲。因此我们不可能无限的获取航班数据，这就需要在新鲜度和费用上面做权衡。这也是导致报价变化不实时的一个因素。
5）此外，不同供应商在 GDS 的权限不一样，同样的航班拿到的报价可能不一样，这就对系统提出了更高的要求。
变化不是问题，问题在于变化的是海量的数据。
1）供应商在平台上录入大量的规则，来进行定价，这种规则相当复杂，数量级达到2亿；航司的运价规则也有上亿的量级，复杂度也很高。
2）全世界大概有28万条航线，我们粗略估算一下，全部的报价量大概会是千亿的量级。
3）搜索系统要面对每秒3千多次的搜索量，单看这个搜索量可能不算大，但是背后有大量的并发计算，每秒要计算1500万量级的报价产品。
3
设计思路
面对这些背景和问题，我们怎么做，能实现系统诉求呢？
1）有一次有朋友问我，你们怎么这么忙，机票搜索为啥搞这么复杂？放个静态页面上去不就好了，多少用户搜索预订都没问题。我有那么一瞬间，竟无言以对。
2）不过后来我想了想，要说这样搞也不是不可以，如果资源足够的话，我们大可以做一个很大很大的哈希表，把未来几个月的每条航线每天的航班报价计算好，用户来搜索直接就拿哈希表的数据展示就可以了。一旦监测到哪个渠道有价格变化，即时计算替换老的数据。这样一来我们的搜索将飞快，并且变价的情况会很少发生，这是最理想的。
然而现实是骨感的。有限的资源不允许我们这样做。所以我们只能从用户的角度入手。我们参考 CAP 和 BASE 理论，设计了分布式的系统。按需计算，用户需要搜索的数据，实时计算，计算完了将结果缓存起来，下一个用户再搜索同样的条件就不用再实时计算了。系统之间采用消息驱动的方式，使用异步机制来降低耦合，使系统扩展起来很简单。整个系统水平分了多层，各层有各层的缓存。各系统的计算流程都设计为无状态的，可以很容易横向扩展。
4
搜索框架
这个图就是我们搜索系统大的一个框架。
1）我们将系统分为4层，从上到下为应用层，聚合层，报价源层，基础数据层。纵向则根据各层的特点，划分为多个渠道或者多个源。这样划分的好处是不同的层可以独立发展，可以有各自的流量控制和服务降级策略，保证系统整体的高可用；不同的渠道和源可以有不同的处理方式，耦合度低，扩展方便。
2）应用层接受用户搜索条件，向聚合层要匹配条件的全量报价，经过筛选、包装和排序，输出给前端。按照不同渠道的特点，报价的包装和排序处理会有区别。
3）聚合层管理着所有航线的报价缓存，以供应商作为独立的存储单元。它接到一个搜索条件，会先问一下 Cachemanager ，有多少个供应商的缓存报价失效了，得到一个需要重新搜索的供应商列表，然后带着搜索条件：出发到达日期和供应商列表，向下层的报价源发消息，然后异步等报价源回消息。报价源接到消息之后，会对相应的供应商进行搜索，搜出报价之后放到redis里，然后发消息通知 PriceMerger 。PriceMerger 从 Redis 里将报价取出来，和没有失效的供应商的报价进行聚合，筛选出最优的价格进行包装。
4）CacheManager 是缓存失效管理系统。我们设计了主动和被动两套缓存更新机制。主动更新就是由各环节发现价格有变化，主动通知 CacheManager 。比如航班数据、运价数据发生变化、供应商规则数据发生变化、预订发生变价等等，都主动通知 CacheManager 。被动更新则是根据热度排行，对不同热度的航线，配置不同的过期时间，越热门航线的过期时间越短。
5）整个系统以供应商作为独立报价单元，报价源遵循这个规则。所以不同的报价源可以很容易接入搜索框架。
6）各层间的数据交换大多是异步的，用 Protobuf 序列化并 Gzip 压缩，通过 Redis 中转，能很好降低我们的 IO 和带宽使用，也使系统的耦合大大降低，扩展起来非常方便。
纵观整个系统的发展，我们遇到了不少问题，这里总结了一些有代表性的。
1）一个是报价数量很多，聚合层的系统，内存遇到了不少问题。有一次新上一种产品，直接导致了系统的崩溃。原因是新产品引进大量的字符串 Map ，这些 Map 还支持随意扩展，一下子涌进来很多对象， GC 都回收不过来了。这之后我们严格控制了数据的准入，只留必要的数据，尽量采用原生的数据类型，将很多小对象，编码成原生的数据类型，大大缩减内存占用。
2）另一个问题是报价源比较多，不稳定，有些供应商接口性能不好，回数很慢，而我们对响应时间要求很苛刻。对此我们采用分批回数的方式，先回来的报价，先返回给前端，多次轮询，直到报价回完，同时我们也设计了一个回数比例模型，如果达到这个比例或者超时，这次搜索就结束了，后台异步等报价源的回数，等下次的用户搜索，就可能看到新的报价了。
3）对于搜索条件，有个明显的冷热门问题，热门的航线和日期，搜索的人很多，数据量也很大。我们以航线+日期作为 Key 做了一致性哈希，将搜索条件均衡打到不同的服务器上，并且让相同的条件只会分配到同一台机器上，这样能最大限度地利用本地缓存。
以上是搜索框架的介绍。
5
报价引擎
下面我们来深入探讨一下报价引擎的设计和优化历程。
报价引擎作为一个报价源，是去哪儿网的供应商平台、我们内部叫 TTS 的搜索系统，是最核心的一个报价源。一开始的时候，是没有这个平台的，机票的报价都是从大量供应商的网站抓取的，预订交易都要跳转到外网进行。流量大了之后为了保障服务质量，有了这个 SaaS 平台，供应商通过这个平台录入他们的定价和服务规则，我们负责把价格计算好报出去，后续的预订交易流程，都在平台上完成。由分散到集中，这是机票服务发展到一定阶段的必然之路。到后来几乎80%的报价都是这个系统产生的。我们花了大量的精力对这个系统进行设计和优化。
一个机票报价是怎么产生的呢？决定因素有供应商规则，航司运价以及航班舱位状态，这些要素组合起来，即可计算出每个供应商每航班每个舱位的价格；我们会在这些价格当中，选取一些最优的价格，包装成套餐，比如低价特惠、商旅优选等产品，展示给用户预订。
报价引擎解决的核心问题就是，根据用户的搜索条件，对每一个供应商的定价规则库进行搜索，获取符合条件的规则，与航班舱位状态、航司运价进行匹配，计算出每个供应商每个舱位的最优价格。
供应商规则相当复杂，有日期限制、航司限制、航班限制、舱位限制、年龄限制等等，每条规则都有很多使用条件，几十个字段。这些规则量达2亿。
可以说供应商定价规则是决定机票价格的最重要因素之一。
成千上万的供应商在 TTS 平台上投放规则，少则几万，多则几千万。
这些规则的存储按供应商进行分库，每个供应商一个库，多个库作为一组，分布在一个 Mysql 的实例上，有多个 Mysql 实例。
在这个背景之下，系统面临这些问题
1）供应商更新规则数据很频繁，每时每刻都在更新，特别是热门航线。
2）最坏的情况下，每次用户的搜索都可能会触发所有供应商的规则搜索。 DB承受的压力是用户搜索量乘以供应商数量。这种情况下，业务增长一点， DB 的压力就大幅增加。
3）在老的系统里， DB 是压力最大的一环，读写都很频繁。曾经单独为搜索做了7、8组从库，但是还是扛不住业务的快速增长，故障频发，一家供应商出问题，比如更新太频繁，就可能拖累整个系统交易。
4）除此之外，频繁变化的航班舱位，热点航线的供应商规则量大、搜索量大，让系统的内存压力、计算压力很大，应用服务器也经常出问题。
新的报价引擎就是为了克服这些问题来设计的。我们回到搜索引擎的核心技术来看问题。搜索引擎主要是对收集到的信息进行整理、分类、索引以产生索引库。我们是不是应该组织一个合适的索引库，让搜索的效率大幅提升呢？
对用户搜索条件进行了分析，我们发现用户搜索的是航线日期，并不关心哪个供应商。但是我们因为系统结构的原因，要对所有的供应商库进行查询。聪明的做法是做一个适合航线搜索的索引库。我们将所有的航线拿过来，进行了热度排序，均衡打散为 N 个表， N 个表平均分布到 M 个库。然后开发了一个数据同步系统，将供应商维度的规则，实时同步到航线维度分表的索引库。
这个数据同步系统以 Binlog 同步方式工作。我们引入了阿里巴巴开源的项目 Canal ，这个项目通过实现 Mysql 的主从同步协议，能把自己伪装成从库，实时增量获取 Mysql 的 Binlog 数据。
我们通过 Canal 拿到增量的 Binlog 数据之后，做解析、拆分，将供应商规则按航线分布插入索引库，或者从索引库删除。
这时我们面临的问题是：
1）源数据写入量很大，集群峰值达20K TPS
2）为了保证报价的新鲜度，我们要求同步延迟很低，不超过60s
3）必须保持顺序一致性，如果先删后插变成先插后删，数据就不一致了
4）必须保持数据最终一致
5）系统必须是高可用的
针对前面4个问题我们的解决方案是这样的：
首先保证读 Binlog 的吞吐量：
源数据写入量、顺序性与同步延迟是矛盾的，为了保持顺序，一个 Mysql 实例只能由单线程来读 Binlog 。但是如果 Mysql 实例上的供应商数量很多，短时间数据更新量就可能很大，单线程处理不过来，同步延迟势必很大。因此我们将规则库分散到更多的 Mysql 实例上面，从物理层面保障了更多通道并行同步，提高读 Binlog 的吞吐量；
其次保证写索引库的吞吐量：
Binlog 数据解析、分拆处理到写入索引库阶段，为了保持顺序写，似乎也只能每个mysql实例单线程来做，可是这样写的吞吐量上不去，同步延迟也会很大。仔细分析一下，其实并不需要全局顺序一致，只需要每条航线的数据顺序保持一致就可以了。我们按航线划分了很多的队列，不同航线的 sql 在各自队列里保持顺序入库，这样并行度就高了，写入的吞吐量也就上去了。
再有就是保证数据的一致性：
增量同步可能会因为一些网络问题或者入库失败，导致数据不一致。这个时候，为了让数据最终一致，我们又设计了一个全量数据 Diff 的功能，定期（比如5分钟一次）对两个库的数据进行比对，如果有不一致的，通过增删来保持索引库的数据跟规则库保持一致。这就保证数据在异常情况下能短时间达到最终一致。
最后一个问题是系统的高可用。我们希望任何一个环节出现问题都不影响数据同步。
分两部分， Canal 这边本身已经提供了方案，应用服务器和 DB 都配备主备自动切换来保证高可用。这个不多说。
我们的同步程序呢，也设计了一套方案。系统是分布式的，一共有 K 个 Mysql 的实例，分配到 P 台服务器上。这其实是一个任务分配问题。要达到几个效果：
1）任务分配要均衡。
2）分配完之后保持稳定。
3）某台服务器挂掉了它上面的任务需要自动切换到健康的服务器上，不影响其他的任务。
4）加入了新的服务器，任务重新分配，保持各服务器的负载均衡。
我们利用 ZK 作为协调者，从集群服务器中选出一台 Leader 来执行任务分配，依靠 ZK 的节点发现和通知机制，实现了这四个功能。
这样我们的整个同步系统是高可用的，在吞吐量很大的情况下，峰值延迟不超过60秒，平均延迟10秒左右。
索引库构建好了之后，我们的系统结构可以是这样的。入口接收PriceMerger的搜索消息，这个消息会带着《出发》、《到达》、《日期》还有《供应商列表》这些参数，随机打到分布式集群的某一台搜索服务器上。服务器把符合这些条件的供应商规则从索引库查询出来，同时并行把航班数据、运价数据取回来，进行匹配、计算、筛选，计算出每个供应商的舱位最优价，将结果写入 Redis ，最后发消息通知 PriceMerger 。这个流程很清晰，只需要查一次库，理论上 DB 是没有什么问题的，应用系统也很容易扩展。但是系统做出来之后，还是遇到了大问题。
1）索引库压力很大。
2）是部分服务器的负载很高，GC频繁，吞吐量上不去。
为什么会这样呢？这个时候我们是比较沮丧的。但是问题还是要解决。我们考察了搜索条件的特点。
1）首先，搜索的请求条件冷热门很明显，热门航线比如北京到上海的请求很多，投放这些航线的供应商也很多，规则数量很大，热门航线的航班数量和运价数量也很多。这些因素结合起来，一次热门航线搜索， DB 和应用服务器的 IO 占用都很高， CPU 方面光反序列化就占用不少，报价计算的量很大，这就导致了 DB 和应用服务器的负载都很高，但是吞吐量上不去的情况。
2）另外我们的供应商规则，以及航班数据和运价数据，有大量的String、Map和 List 等对象，尤其热门航线的搜索，请求量稍微大一点，堆内存占用很多，释放不掉， GC 根本回收不过来。
4）分析了这些情况之后，我们有两个措施，一是想办法大幅减少 DB 的请求量，二是想办法减少内存的占用。
如何能减少 DB 的请求呢？
有效的办法是在应用服务器增加本地的 Cache 。查询出来的规则数据，不扔掉，放在 Cache 里下次同样条件的请求直接使用。然后每次搜索进来的时候，去索引库检查一下这个条件下的规则数量和最后更新时间，有变化的话就将缓存清掉，从 DB 取一遍，保证缓存数据的新鲜度。这样一来， DB 压力陡降，服务器 IO 也降了很多。
有了本地缓存，我们需要让缓存命中率尽量高，并且保持稳定。根本的办法是让同样的请求条件，每次都打到同样的服务器上。直接将请求按航线进行一致性哈希，可以达到效果，但是这样会有冷热门航线的问题，会导致部分服务器的负载不均衡。
我们对负载均衡策略进行了扩展，将航线+单个供应商作为哈希条件，一致性哈希分到某台服务器，之前的供应商列表就会分多批，一个请求分裂成多个请求，进行分发。
由于是一致性哈希，命中率会很高，并且我们增减服务器，不会引起缓存命中率的大面积变化。
单台服务器上的规则缓存，只是某些航线的部分供应商的规则，并不是全量规则，在集群服务器数量足够的情况下，不会占用单台服务器太多的内存。
DB 的压力在做了 Cache 之后大幅降低。但搜索量上涨后还是会出现负载高的情况。原因是每次搜索都会要检查规则是否更新。这个 sql 执行量很大。有没有办法减少它呢？回顾整个系统，其实我们已经在数据同步的时候就知道了供应商是否更新了规则，可以在这个时候，去通知引擎，将该条件的本地缓存失效掉。这样就不需要每次搜索都去 DB 里检查了，作为兜底可以1分钟检查一次。这样 DB 就毫无压力了。
另一个措施，是缩减内存的占用。
每条供应商的规则都有几十个字段，这些字段有很多 String ，整形，日期等对象类型。航班数据、运价数据，包含大量的 Map 数据。作为本地缓存，这些数据对象会长时间存在，如果占用内存太多， GC 都回收不过来。
分析一下特征。我们发现很多对象，都是一些个数有限的字符串，比如机场码，航司代码，航班号，舱位代码；还有一些日期的对象，只是精确到天；一堆定价的数值、一堆布尔值。
这些对象实际数据不大，但是对象的开销不小，比如一个两字节的航司代码的 String 对象，内存就要48字节，还有很多的小对象，由于 Java 的内存对齐，会导致大量的内存间隙，造成内存的浪费。
针对这些特点，我们做了一系列策略：
小的个数有限的字符串，做一个 Byte 类型的编码表，减少创建字符串对象。
针对一堆 Integer ，我们构造了一些 Short 数组，int数组来承载，减少对象开销，避免内存对齐产生的间隙。
针对日期，我们计算一个距离5年前的偏移量，存成 Short 数组。
总的来说，尽量减少内存的浪费，最后我们内存使用大幅减少，有接近50%的降幅。
这样一来内存也不是问题了，吞吐量就可以上去了。
除此之外，我们还在其他方面对系统进行了性能优化。
在计算中采用异步 Http 或者异步 Dubbo 方式，并行获取需要的资源；很多计算能并行的都并行来做，杜绝锁的出现，充分榨取多核 CPU 的计算能力；
对于一些复杂计算，结合业务进行剪枝，降低时间复杂度；
适当的用空间换时间，比如一些重复的循环计算，把中间结果缓存起来，后边直接用；
优化 Jvm 参数，缩短对象驻留内存的时间，减少 Gc 次数；
数据交换用 Protobuf ， Gzip 压缩，减少 IO ；
重启机器时候负载很高，每次发布都会影响服务性能，对此我们发现主要的问题在于 Jit 即时编译，在量上来的时候，启动 C2 线程进行的字节码编译，会耗费大量的 CPU 。对此我们做了预热机制，启动时对外服务前，先预跑让jit编译完成，同时会重建大部分本地缓存。
通过这些优化，这个集群的性能达到一个非常好的状态，在 QPS 达到5w的情况下，响应时间在50ms以内，负载也比较低。
以上就是我们搜索系统的设计和优化历程。我们回顾一下，对于搜索框架我们进行了水平分层，纵向分渠道，除了良好的扩展性，不同的层可以做不同的降级策略，流量控制，保证系统高可用。我们采用实时计算+阶梯式缓存，来做到成本与报价新鲜度的权衡。我们设计了闭环系统来保证缓存的更新。对于报价引擎我们设计了适合航线搜索的索引库，开发了高可用的实时同步系统。设计了一个分布式本地缓存，大大降低 DB 的压力，分享了我们是如何缩减对象内存的，还有就是如何合理利用一致性哈希做负载均衡。
我们会发现，不同的业务场景，有不同的特征，最好的思路是根据特征去进行设计和优化。由于木桶效应的存在，通用的实现大多数不是最优的，因为兼顾了通用性。高性能系统的设计，真的是需要量体裁衣。
