系统介绍
ATPCO系统是Qunar国际机票的运价系统，它通过美国ATPCO公司接收全球近500家航空公司的运价、规则数据进行计算，为上层的机票搜索系统提供运价搜索服务。系统的基础数据主要分为运价、规则、航路等数据，其中运价数据有9000万条，规则数据有1.2亿条，平均每条运价关联20条规则数据。规则数据分为Record 0/1/2/3/6/8六大类，其中Record3数据又包含Category1~Category50几十种子规则，以及Table 900系列的若干表、Category 10下面的各种子表。所以业务规则复杂，数据量大是这个系统的一大特点。
ATPCO系统的另外一个特点是计算量大。我们以北京-香港，2018年7月1日的单程搜索为例来粗略估算一下搜索发生时系统的计算量：
- 航路数量（中转点，如上海、厦门等）：5
- 运价数量：500
- 航班数量：20
- 舱位数量：10
- 舱位规则：2
上述因素之间是叉乘的关系，所以总的计算量=550020102=1000000。也就是单次搜索产生的计算量是100万，而且这只是单程的部分计算，还没有考虑addon、两次中转……。在这种情况的，即便我们使用了24核的物理机并发计算，系统的压力依然很大。下图是我们用vmstat命令查看到的CPU运行队列的情况，也可以看到在处理请求时，CPU的运行队列都超过了CPU Processor数量。
所以，系统上线初期，系统响应比较慢，单程平均响应时间500ms，往返多达1500ms，部分往返搜索甚至超时。
问题分析及应对策略
在积累了一段时间的运行数据的基础上，结合业务的特点，我们对系统性能较低的原因进行分析，总结有以下几点：
- 代码存在瓶颈：如锁等待（如早期QMonitor中的synchronized）、代码效率低（如频繁从InfoCenter中获取机场信息）等；
- 计算量太大：一次搜索的计算量太大，线程超时严重，尤其是往返的计算；
- 部分计算流程不合理：如有些互相没有依赖的逻辑串行处理、CPU核心忙闲不均拖慢整体响应时间；
其他因素：GC停顿、外部依赖性能低
针对上述的问题，我们采用了不同的方案来解决。当然从事后诸葛亮的角度来总结，我们借鉴了2个法则的思想来进行系统性能的提升：针对问题1和问题2，我们可以使用利特尔法则解决；针对问题3，可以利用阿姆达尔定律来解决。
利特尔法则实践
利特尔法则由麻省理工大学斯隆商学院（MIT Sloan School of Management）的教授John Little于1961年所提出与证明，其英文名称为：Little’s Law。利特尔法则是一个有关提前期与在制品关系的简单数学公式，这一法则为精益生产的改善方向指明了道路。如何有效地缩短生产周期呢？道理很简单：一个方向是提高单位效率，另一个方向就是降低任务数量。
所以基于利特尔法则，我们对系统优化的工作就沿着2个方向前进：
- 提高代码性能，这里是我们努力的主要方向；
- 减少计算量：也就是剪枝。
提高代码性能
要提高代码性能，首要的工作就是找到代码中耗时比较久的地方，也就是“热点”。这里我们使用了JMC(Java Mission Control)来查找热点。通过热点分析，我们做了以下4个方面的改进：
减少字符串使用
因为需要降低内存占用的缘故，系统中将部分的字符串转成了int/long在堆内存储，这同时也带来了一个好处就是提高了字符串的操作效率，毕竟相比String，int/long的执行效率要高一些。当然String转int/long这种方式比较适合大量存储且不需要频繁转换的场景，所以要慎用。
减少/避免低性能的使用方式
为提升性能，代码中尽量避免低性能的使用方式。比如String.split方法，因为支持正则的缘故而性能偏低，而我们的场景中很少使用正则，所以我们就换成了Guava Splitter；比如尽量避免使用BigDecimal这种为保证精度而牺牲一定性能的类，如果必须使用，那么也优先使用BigDecimal.valueOf方法而不是new BigDecimal()这种方式；再比如要求集合、StringBuilder在使用前必须指定初始化容量，避免扩容造成的内存浪费，从而减少GC时间；
减少IO阻塞、锁等待
IO阻塞、锁等待是系统性能提升的大敌。对于减少IO阻塞，一个典型的例子就是减少日志的打印以及调整日志组件的配置。虽然我们的系统中使用了异步方式打印日志，但当日志量比较大的时候，依然可能引起日志的阻塞。所以我们的策略是减少不必要的日志打印。同时，为避免logback阻塞主线程，我们将其neverBlock属性设置为true，允许丢失一部分非关键日志，但换来的好处就是不会因为日志打印而阻塞主线程。
另外，通过热点查找，我们还定位到了当时使用的监控组件存在锁等待的问题，并推动相关团队进行了改进。
提高缓存效率
由于系统大量使用了缓存，在进行优化的过程中，我们一度发现使用的Guava Cache也成了热点，于是我们也寻求了解决方案。通过搜索引擎和github，我们发现Caffeine宣称拥有比Guava Cache高几倍的读写效率，于是我们进行了测试和试用，发现在我们的应用场景下（读多写少），Caffeine的性能确实要好于Guava Cache。所以我们最终采用Caffeine作为了本地缓存方案。对于Caffeine Cache，感兴趣的同学可以通过文末给出的链接进行了解。
剪枝
在对代码性能进行充分压榨后，我们依然无法解决往返计算时间太长甚至超时的问题，原因在于往返的去程、回程航班组合存在笛卡尔积的缘故，导致往返的计算量比单程要多2个数量级。
在无法对程序性能做进一步榨取的情况下，我们开始考虑在庞大的计算量中进行取舍。前面我们提到了，初期的系统对往返去程、回程的航班组合比较粗放，采取笛卡尔积的方式，如下图：
这样带来的结果就是航班组合数量非常庞大，系统处理不过来。所以我们将去程、回程航班以价格进行排序，在去程航班的基础上选取回程航班，如下图所示：
通过这样的优化，往返搜索需要处理的航班组合数量减少了50%以上，搜索超时的量也减少了30%以上。
当然，在剪枝的层面上的优化，我们还是比较保守的，毕竟这需要强大的业务及分析能力做后盾才有能力取得比较好的成果。在剪枝策略上，携程的引擎团队做得比我们要激进得多，但效果也好很多。他们将航班组合剪枝到了我们的20%，但对业务的影响小到可以忽略。因此在这一点上，我们需要向他们好好学习。
阿姆达尔定律实践
阿姆达尔定律（英语：Amdahl’s law，Amdahl’s argument），一个计算机科学界的经验法则，因吉恩·阿姆达尔(Gene Amdahl)而得名。它代表了处理器平行运算之后效率提升的能力。譬如说，你的程序50%是串行的，其他一半可以并行，那么，最大的加速比就是2。不管你用多少处理器并行，这个加速比不可能提高。在这种情况下，改进串行算法可能比多核处理器并行更有效。
撇开上面那些文绉绉的话，在这个方向上，我们做的优化就是：
- 提高并发效率
- 并行处理
提高并发效率
在提高并发效率方面，值得一提的一点就是：针对计算量比较大的逻辑，将普通的线程池改成了ForkJoinPool。事情的起因还是在提升往返计算性能的过程中，我们通过mpstat命令查看线上服务器CPU Processor的使用率，发现各CPU Processor忙闲不均，如下图：
这种现象引起了我们的警觉，我们意识到在忙闲不均的情况下，运行压力最大的线程将拖慢整个请求的处理速度。因此我们将计算量比较大的线程池改成了ForkJoinPool，依赖它的Work-Stealing机制来确保各线程都有任务可以执行，避免出现忙闲不均的情况。
通过这个优化，往返搜索的超时率进一步降低，同时服务器CPU Processor使用率也变得更加均衡，下面这张图就是优化后再通过mpstat查看到CPU核心使用率的情况。
不管ForkJoinPool也好，还是Java8中出现的stream（默认基于ForkJoinPool）也好，都是有自己适合的场景，不是什么情况都适合的。Work-Stealing的适用场景是不同的任务的耗时相差比较大，即某些任务需要运行较长时间，而某些任务会很快的运行完成，这种情况下用 Work-Stealing很合适；但是如果任务的耗时很平均，则此时 Work-Stealing 并不适合，因为窃取任务时不同线程需要抢占锁，这可能会造成额外的时间消耗，而且每个线程维护双端队列也会造成更大的内存消耗。所以 ForkJoinPool 并不是 ThreadPoolExecutor 的替代品，而是作为对 ThreadPoolExecutor 的补充。
并行处理
在并行处理方面，我们将互相独立的计算类型（Specified fare/Constructed fare/End-on-end）拆分到不同的机器上进行处理，以减轻单台机器的计算压力，同时也能通过并行来进一步提高处理系统的处理能力。当然，这方面我们要面对的挑战就是系统的逻辑将变得更加复杂，毕竟任务调度的效率也将影响整个搜索的效率。
总结
上述内容就是我们在对系统优化过程中提炼的一些值得一提的点，因为篇幅的限制，还有一些较为底层的优化在这里无法展开来分享，这里讲考虑后续通过小专题的方式继续分享。针对本文的内容或相关的领域，也欢迎大家提出宝贵的意见和建议，谢谢。
相关链接：
- Caffeine github：https://github.com/ben-manes/caffeine
- Caffeine原理：https://segmentfault.com/a/1190000008751999