作者簡介

簡言，攜程后端開發(fā)經(jīng)理 ，關(guān)注技術(shù)架構(gòu)、性能優(yōu)化、交通規(guī)劃等領(lǐng)域。

一、背景介紹

由于交通規(guī)劃和運力資源的限制，用戶查詢的兩地之間可能沒有直達(dá)交通，或者在重大節(jié)假日時，直達(dá)交通都已售罄。不過，通過火車、飛機、汽車、船舶等兩程或多程中轉(zhuǎn)的方式，用戶仍然可以到達(dá)目的地。此外，中轉(zhuǎn)交通有時在價格和耗時方面更具有優(yōu)勢。例如，對于從上海到運城，通過火車中轉(zhuǎn)可能比直達(dá)火車更加快捷和便宜。

圖1 攜程火車中轉(zhuǎn)交通列表

在提供中轉(zhuǎn)交通方案時，很重要的一個環(huán)節(jié)是將兩程或多程的火車、飛機、汽車、船舶等拼接起來組成可行的中轉(zhuǎn)方案。而中轉(zhuǎn)交通拼接的第一個難點是拼接空間極大，僅考慮上海做中轉(zhuǎn)城市，就可以產(chǎn)生近億種組合；另一個難點在于對實時性有要求，因為產(chǎn)線數(shù)據(jù)隨時變化，需要不斷地查詢火車、飛機、汽車、船舶的數(shù)據(jù)。中轉(zhuǎn)交通拼接需要大量的計算資源和IO開銷，因此，對其性能進(jìn)行優(yōu)化顯得尤為重要。

本文將結(jié)合實例，介紹在中轉(zhuǎn)交通拼接性能優(yōu)化過程中所遵循的原則、分析和優(yōu)化方法，旨在為讀者提供有價值的參考和啟示。

二、優(yōu)化原則

性能優(yōu)化需要在滿足業(yè)務(wù)需求的前提下，在各種資源和約束條件下去平衡和取舍，遵循一些大的原則有助于消除不確定性，去逼近解決問題的最優(yōu)解。具體來說，中轉(zhuǎn)交通拼接優(yōu)化過程中主要遵循以下三個原則：

2.1 性能優(yōu)化是手段而不是目的

雖然本文是關(guān)于性能優(yōu)化的，但仍需要在最開始強調(diào)：不要為了優(yōu)化而優(yōu)化。滿足業(yè)務(wù)需求的方式有很多，性能優(yōu)化只是其中一種。有時候問題非常復(fù)雜，限制也很多，在不顯著影響用戶體驗的前提下，通過放寬限制或采用其他流程來減少對用戶的影響，這也是解決性能問題的好方法。在軟件開發(fā)中，存在許多通過犧牲少量性能來實現(xiàn)大幅降低成本的事例。例如，在Redis中用于基數(shù)統(tǒng)計（去重）的HyperLogLog算法，它在標(biāo)準(zhǔn)誤差為0.81%的前提下，只需要12K空間就能夠統(tǒng)計264的數(shù)據(jù)。

回到問題本身，由于需要頻繁地查詢產(chǎn)線數(shù)據(jù)，并且進(jìn)行海量的拼接操作，那么如果要求每個用戶查詢時都立刻返回最新鮮的中轉(zhuǎn)方案，成本將會非常高。為了降低成本，需要在響應(yīng)時間和數(shù)據(jù)新鮮度之間進(jìn)行平衡。經(jīng)過仔細(xì)考慮選擇可以接受分鐘級的數(shù)據(jù)不一致，對于一些冷門線路和日期，可能在首次查詢時沒有好的中轉(zhuǎn)方案，此時引導(dǎo)用戶重新刷新頁面即可。

2.2 不正確的優(yōu)化是萬惡之源

Donald Knuth在《Structured Programming With Go To Statements》中提到：“程序員們浪費大量的時間去思考、擔(dān)憂非關(guān)鍵路徑的性能，而嘗試優(yōu)化這部分性能，對整體代碼的調(diào)試和維護(hù)都有非常嚴(yán)重的負(fù)面影響，因此97%的情況，我們應(yīng)該忘記小的優(yōu)化點”。簡而言之，在沒有發(fā)現(xiàn)真正的性能問題之前，在代碼層面過度炫技式的優(yōu)化，不僅不會提高性能，反而可能會導(dǎo)致更多的錯誤。然而作者同樣也強調(diào)：“對于剩下關(guān)鍵的3%，我們也不要錯過優(yōu)化的機會”。因此，需要時刻關(guān)注性能問題，不做會影響性能的決策，并在必要的時候做正確的優(yōu)化。

2.3 量化分析性能，明確優(yōu)化方向

正如前一節(jié)所述，在進(jìn)行優(yōu)化之前，首先要量化性能并找出瓶頸，這樣優(yōu)化的才更有針對性。量化分析性能可以借助耗時監(jiān)控、Profiler性能分析工具、Benchmark基準(zhǔn)測試工具等，重點關(guān)注耗時特別長或者執(zhí)行頻率特別高的地方。正如阿姆達(dá)爾定律所述:“系統(tǒng)中對某一部件采用更快執(zhí)行方式所能獲得的系統(tǒng)性能改進(jìn)程度，取決于這種執(zhí)行方式被使用的頻率，或所占總執(zhí)行時間的比例”。

此外，還需要注意到性能優(yōu)化是一場持久戰(zhàn)。隨著業(yè)務(wù)的不斷發(fā)展，架構(gòu)和代碼也不停地變化，因此更需要持續(xù)量化性能，不斷分析瓶頸和評估優(yōu)化效果。

三、性能分析之路

3.1 梳理業(yè)務(wù)流程

在性能分析之前，首先要梳理業(yè)務(wù)流程。中轉(zhuǎn)交通方案拼接主要包含以下四個步驟：

a.  加載線路圖，如北京經(jīng)南京中轉(zhuǎn)到上海，只考慮線路本身的信息，與具體的班次無關(guān)；

b.  查火車、飛機、汽車、船舶的產(chǎn)線數(shù)據(jù)，包括出發(fā)時間、到達(dá)時間、出發(fā)站、到達(dá)站、價格和余票信息等；

c.  拼接出所有可行的中轉(zhuǎn)交通方案，主要是考慮換乘時間不能過短，以免無法完成換乘；同時也不宜過長，以免等待太久。拼接出可行的方案后，還需要完善業(yè)務(wù)字段，例如總價格、總耗時和換乘信息等；

d.  根據(jù)一定的規(guī)則，從拼接出的所有可行中轉(zhuǎn)方案中篩選出一些用戶可能感興趣的方案。

3.2 量化分析性能

（1）增加耗時監(jiān)控?

耗時監(jiān)控是一種最直觀的從宏觀角度觀察各個階段耗時情況的手段。它不僅可以查看業(yè)務(wù)流程各階段的耗時值與耗時占比，還可以長期觀察耗時變化趨勢。

耗時監(jiān)控可以借助公司內(nèi)部的指標(biāo)監(jiān)控告警系統(tǒng)，在中轉(zhuǎn)交通方案拼接的主要流程中增加耗時打點。這些流程包括加載線路圖、查詢班次數(shù)據(jù)并進(jìn)行拼接、篩選和保存拼接方案等。各個階段的耗時情況如圖2所示，可以看到，拼接（含查產(chǎn)線數(shù)據(jù)）的耗時占比最高，因此成為未來重點優(yōu)化的目標(biāo)。

圖2 中轉(zhuǎn)交通拼接耗時監(jiān)控

（2）Profiler性能分析?

耗時打點可能會侵入業(yè)務(wù)代碼，并對性能產(chǎn)生影響，因此不宜過多，更適合監(jiān)控主要流程。與之對應(yīng)的Profiler性能分析工具（例如Async-profiler），可以生成更具體的調(diào)用樹以及各函數(shù)的CPU占用比例，從而幫助關(guān)鍵路徑和性能瓶頸的分析與定位。

圖3 拼接調(diào)用樹與CPU占比

如圖3所示，拼接方案（combineTransferLines）占53.80%，查產(chǎn)線數(shù)據(jù)（querySegmentCacheable，已使用緩存）占21.45%。在拼接方案中， 計算方案評分(computeTripScore，占48.22%)、創(chuàng)建方案實體（buildTripBO，占4.61%）和檢查拼接可行性（checkCombineMatchCondition，占0.91%）是占比最大的三個環(huán)節(jié)。

圖4 方案打分調(diào)用樹和CPU占比

繼續(xù)分析占比最高的計算方案評分（computeTripScore）時，發(fā)現(xiàn)主要與自定義的字符串格式化函數(shù)（StringUtils.format）有關(guān)，包括直接調(diào)用（用于展示方案評分細(xì)節(jié)），以及通過getTripId間接調(diào)用（用于生成方案的ID）。自定義的StringUtils.format中占比最高的是java/lang/String.replace，Java 8原生的字符串替換是通過正則實現(xiàn)的，效率比較低（這一問題在Java9之后已經(jīng)改進(jìn)了）。

// 計算方案評分(computeTripScore) 中調(diào)用的StringUtils.format代碼示例
StringUtils.format("AAAA-{0},BBBB-{1},CCCC-{2},DDDD-{3},EEEE-{4},FFFF-{5},GGGG-{6},HHHH-{7},IIII-{8},JJJJ-{9}",
            aaaa, bbbb, cccc, dddd, eeee, ffff, gggg, hhhh, iiii, jjjj)


// getTripId 中調(diào)用StringUtils.format代碼示例
StringUtils.format("{0}_{1}_{2}_{3}_{4}_{5}_{6}", aaaa, bbbb, cccc, dddd, eeee, ffff)


// 通過Java replace實現(xiàn)的自定義format函數(shù)
public static String format(String template, Object... parameters) {
    for (int i = 0; i < parameters.length; i++) {
        template = template.replace("{" + i + "}", parameters[i] + "");
    }
    return template;
}

（3）Benchmark基準(zhǔn)測試?

借助Benchmark基準(zhǔn)測試工具可以更準(zhǔn)確地測量代碼的執(zhí)行時間。在表1中，我們通過JMH（Java Microbenchmark Harness）對三種字符串格式化方法和一種字符串拼接方法進(jìn)行耗時測試。測試結(jié)果表明，使用Java8的replace方法實現(xiàn)的字符串格式化性能最差，而使用Apache的字符串拼接函數(shù)性能最佳。

表1 字符串格式化與拼接性能對比

四、性能優(yōu)化之路

通過以上的性能分析，我們發(fā)現(xiàn)拼接和查詢產(chǎn)線數(shù)據(jù)是性能瓶頸，字符串格式化影響尤其大。因此，我們將致力于優(yōu)化這些部分，以提高性能表現(xiàn)。

4.1 優(yōu)化代碼邏輯

優(yōu)化代碼邏輯是最簡單且性價比最高的方法，可以是修正有問題的代碼或替換為更好的實現(xiàn)。不同的實現(xiàn)，哪怕減上幾納秒，累加起來也是很可觀的。借助一些經(jīng)典算法或數(shù)據(jù)結(jié)構(gòu)（如快速排序、紅黑樹等）可以在時間和空間復(fù)雜度方面帶來顯著優(yōu)勢?；氐街修D(zhuǎn)交通方案拼接性能優(yōu)化本身，優(yōu)化的代碼邏輯主要包括：

（1）優(yōu)化字符串拼接性能?

如前面的JMH的結(jié)果所示，自定義的字符串格式化函數(shù)性能最差，因此作為重點優(yōu)化目標(biāo)。優(yōu)化前后的對比如下所示：

// 優(yōu)化前，通過Java replace實現(xiàn)的format函數(shù)
public static String format(String template, Object... parameters) {
    for (int i = 0; i < parameters.length; i++) {
        template = template.replace("{" + i + "}", parameters[i] + "");
    }
    return template;
}
// 優(yōu)化后，通過Apache replace實現(xiàn)的format函數(shù)
public static String format(String template, Object... parameters) {
    for (int i = 0; i < parameters.length; i++) {
        String temp = new StringBuilder().append('{').append(i).append('}').toString();
        template = org.apache.commons.lang3.StringUtils.replace(template, temp, String.valueOf(parameters[i]));
    }
    return template;
}

根據(jù)JMH的測試結(jié)果，即使是優(yōu)化后的格式化函數(shù)，其性能也不是最優(yōu)的。在不顯著影響可讀性的前提下，應(yīng)盡量使用性能更優(yōu)的StringUtils.join函數(shù)。

// 優(yōu)化前
StringUtils.format("{0}_{1}_{2}_{3}_{4}_{5}_{6}", aaaa, bbbb, cccc, dddd, eeee, ffff)


// 優(yōu)化后
StringUtils.join("_", aaaa, bbbb, cccc, dddd, eeee, ffff)

為進(jìn)一步提升性能，可以在computeTripScore 函數(shù)中添加一個開關(guān)，僅在調(diào)試模式下才展示評分細(xì)節(jié)，這將確保該字符串格式化函數(shù)僅在需要時才被調(diào)用。

if (Config.getBoolean("enable.score.detail", false)) {
    scoreDetail = StringUtils.format("AAAA-{0},BBBB-{1},CCCC-{2},DDDD-{3},EEEE-{4},FFFF-{5},GGGG-{6},HHHH-{7},IIII-{8},JJJJ-{9}",
            aaaa, bbbb, cccc, dddd, eeee, ffff, gggg, hhhh, iiii, jjjj);
}

優(yōu)化后的CPU占比如圖5所示，此時字符串格式化已經(jīng)不再是性能瓶頸。

圖5 優(yōu)化后的拼接調(diào)用樹和CPU占比

（2）增加索引降低拼接時間復(fù)雜度?

圖6 增加索引降低拼接時間復(fù)雜度

在中轉(zhuǎn)拼接過程中，我們需要將第一程每個班次的到達(dá)時間與第二程每個班次的出發(fā)時間進(jìn)行比較，以判斷中轉(zhuǎn)時間是否過短或過長。為簡化說明，假設(shè)換乘時間間隔需要滿足大于30分鐘且小于6小時。以北京到上海經(jīng)南京中轉(zhuǎn)的兩程火車為例，3月9日北京到南京有66個班次，南京到上海有275個班次，考慮到隔夜車，還需要算上3月10日南京到上海的275個班次，那么最多需要比較36300（66*275*2）次。

為避免頻繁比較，參考了MySQL B+樹索引的思想，將第二程南京到上海的所有火車班次數(shù)據(jù)構(gòu)建成紅黑樹。其中，樹的鍵為秒級時間戳，例如2023-03-09 11:29出發(fā)的G367鍵為1677247680，值為G367的班次數(shù)據(jù)。有了索引樹，最多只需要10次比較，就可以找到最近的滿足最小換乘時間要求的班次。同理，最多需要10次比較，就能找到滿足最大換乘時間要求的最晚班次。兩者之間的所有班次都滿足耗時要求，直接進(jìn)行拼接即可。改進(jìn)后最多需要比較1320(66*(10+10))次，約為原來的1/27.5。

（3）使用多路歸并求Top-K算法?

在篩選方案時，會存在以下場景：有多個中轉(zhuǎn)點，每個中轉(zhuǎn)點都有數(shù)百個得分較高的方案（內(nèi)部已按得分由高到低排序，通過小根堆實現(xiàn)）。最終需要將這些方案合并，并從中篩選出得分最高的K個方案。

最簡單的方法是使用快速排序?qū)⑺械姆桨概判?，然后選取前K個，時間復(fù)雜度約為O(nlog2n)。然而，這并沒有利用到每個隊列自身有序的特點。通過多路歸并算法時間復(fù)雜度可降為O(nlog2k)，具體步驟為：

a.  從每個隊列中拿出第一個元素（得分最高的方案），放入大根堆中；

b.  從大根堆堆頂拿出最大的元素，放到結(jié)果集中；

c.  如果該元素所在的隊列還有剩余元素，則將下一個元素加入堆中；

d.  重復(fù)步驟2和3，直到結(jié)果集中包含K個元素或所有的隊列都為空。

圖7 多路歸并求Top-K算法

4.2 構(gòu)建多級緩存

緩存是一種典型的以空間換時間策略，可以緩存數(shù)據(jù)和計算結(jié)果，緩存數(shù)據(jù)可以提高訪問效率，緩存結(jié)果避免了重復(fù)計算。緩存在帶來性能提升的同時，又會引入新的問題：

• 緩存容量有限，需要仔細(xì)斟酌數(shù)據(jù)的加載、更新、失效和替換策略；
• 緩存架構(gòu)的設(shè)計：通常來說內(nèi)存緩存（如HashMap、Caffeine等）性能最高，而Redis等分布式緩存次之，RocksDB相對較慢，容量上限則正好相反，需要仔細(xì)選型并搭配使用；
• 緩存不一致問題如何解決，能接受多久的不一致。

在中轉(zhuǎn)交通方案拼接過程中，需要使用大量的基礎(chǔ)數(shù)據(jù)（如車站、行政區(qū)域等），以及海量的動態(tài)數(shù)據(jù)（例如班次數(shù)據(jù)）。綜合以上因素并結(jié)合中轉(zhuǎn)交通拼接的業(yè)務(wù)特點，緩存架構(gòu)做如下設(shè)計：

• 基礎(chǔ)數(shù)據(jù)（如車站、行政區(qū)域等），因數(shù)據(jù)量小，變化頻率低，全量保存到HashMap中，周期全量更新；
• 部分火車、飛機、汽車、船舶的班次數(shù)據(jù)緩存到Redis中，以提高訪問效率和穩(wěn)定性。不同產(chǎn)線采取的緩存策略稍有不同，但總的來說是定時更新與搜索觸發(fā)更新相結(jié)合的方式；
• 一次拼接過程中可能查詢數(shù)百次產(chǎn)線數(shù)據(jù)，Redis毫秒級的延遲累加起來也是非常大的。因此，希望在Redis之上再構(gòu)建一層內(nèi)存緩存以提高性能。通過分析發(fā)現(xiàn)拼接過程中存在非常明顯的熱點數(shù)據(jù)，熱門日期和線路的查詢占比非常高且數(shù)量相對有限。因此可以將這部分熱點數(shù)據(jù)保存到內(nèi)存緩存中，使用LFU(Least Frequently Used)替換，最終產(chǎn)線數(shù)據(jù)內(nèi)存緩存命中率達(dá)到45%以上，相當(dāng)于降低近一半的IO開銷。
• 因為可以接受分鐘級的數(shù)據(jù)不一致，所以將拼接結(jié)果緩存起來，在有效期內(nèi)，如果下一個用戶查詢同一出發(fā)日期的相同線路，直接使用緩存數(shù)據(jù)即可。因為拼接的中轉(zhuǎn)方案數(shù)據(jù)相對較大，所以將拼接結(jié)果保存到RocksDB中，雖然性能不如Redis，但是對于單次查詢影響還可以接受。

圖8 多級緩存結(jié)構(gòu)

4.3 預(yù)處理

盡管理論上可以選擇任意城市作為兩地的中轉(zhuǎn)點，但實際上大部分中轉(zhuǎn)城市都無法拼接出優(yōu)質(zhì)的方案。因此，先通過離線預(yù)處理篩選出部分高質(zhì)量的中轉(zhuǎn)點，從而將求解空間從幾千降至數(shù)十。相對于動態(tài)變化的班次，線路數(shù)據(jù)是相對固定的，每天計算一次即可。此外離線預(yù)處理可以借助大數(shù)據(jù)技術(shù)，處理海量數(shù)據(jù)，相對對耗時不敏感。

4.4 多線程處理

在一次拼接過程中，需要處理數(shù)十條不同中轉(zhuǎn)點的線路。每個線路的拼接是相互獨立的，因此可以采用多線程處理，這樣可以最大程度地降低處理時間。但受線路班次數(shù)量和緩存命中率的影響，不同線路的拼接耗時很難一致。很多時候，分配相同任務(wù)數(shù)量的兩個線程，即使一個線程很快執(zhí)行完，也要等待另外一個線程執(zhí)行完才能進(jìn)行下一步操作。為避免這種情況，這里借助ForkJoinPool的work-stealing機制。這個機制可以確保每個線程在完自己的任務(wù)后，還會分擔(dān)其他線程未完成的工作，提高并發(fā)效率，減少空閑時間。

但是多線程也不是萬能的，使用時需要注意：

• 子任務(wù)的執(zhí)行需要相互獨立、互不影響。如果存在依賴關(guān)系，則需要等待前一個任務(wù)執(zhí)行完才能開始下一個任務(wù)，這樣會使多線程失去意義；
• CPU核數(shù)決定了并發(fā)能力的上限，過多的線程會因頻繁切換上下文而降低性能，需要特別關(guān)注線程數(shù)、CPU使用率、CPU Throttled time等指標(biāo)。

4.5 延遲計算

通過將計算推遲到必要的時刻，可能避免很多多余的開銷。例如，在拼接完中轉(zhuǎn)方案后，需要構(gòu)建方案實體并完善業(yè)務(wù)字段，這部分也比較消耗資源。而且并非所有拼接的方案都會被篩選出來，這意味著這部分未被篩選的方案仍然需要耗費計算資源。因此延遲完整方案實體對象的構(gòu)建，先將拼接過程中的數(shù)以萬計的方案保存為輕量的中間對象，只對篩選之后的數(shù)百個中間對象構(gòu)建完整的方案實體。

4.6 JVM優(yōu)化

中轉(zhuǎn)交通拼接項目是基于Java 8的，并使用G1(Garbage-First)垃圾收集器，部署在8C8G機器上。G1在實現(xiàn)高吞吐量的同時盡可能滿足停頓時間的要求，系統(tǒng)架構(gòu)部門設(shè)置的默認(rèn)參數(shù)已經(jīng)能夠適用于大多數(shù)場景，通常不需要專門的優(yōu)化。

但有些線路中轉(zhuǎn)方案過多，導(dǎo)致報文太大，超過Region大小的一半(8G 默認(rèn)Region大小是2M)，導(dǎo)致很多應(yīng)該進(jìn)入年輕代的大對象直接進(jìn)入了老年代，為了避免這種情況，將Region大小改為16M。

五、總結(jié)

通過以上的分析和優(yōu)化，拼接耗時變化如圖9所示：

圖9 中轉(zhuǎn)交通方案拼接性能優(yōu)化效果

雖然每個業(yè)務(wù)和場景都有各自的特點，性能優(yōu)化時也需要具體分析。但原理是相通的，依然可以參考本文所述的分析和優(yōu)化方法。本文所有的分析和優(yōu)化方法總結(jié)如圖10所示。

圖10 中轉(zhuǎn)交通方案拼接優(yōu)化總結(jié)