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