優化攜程中轉交通方案的拼接效能

作者簡介

簡言，攜程後端開發經理 ，專注於技術架構、效能最佳化、交通規劃等領域。

一、背景介紹

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

圖1 攜程火車中轉交通清單

在提供中轉交通方案時，很重要的一個環節是將兩程或多程的火車、飛機、汽車、船隻等拼接起來組成可行的中轉方案。而中轉交通拼接的第一個困難是拼接空間極大，只考慮上海做中轉城市，就可以產生近億種組合；另一個難點在於對即時性有要求，因為產線資料隨時變化，需要不斷地查詢火車、飛機、汽車、船舶的資料。中轉交通拼接需要大量的運算資源和IO開銷，因此，對其效能進行最佳化顯得尤為重要。

本文將結合實例，介紹在中轉交通拼接效能最佳化過程中所遵循的原則、分析和最佳化方法，旨在為讀者提供有價值的參考和啟示。

二、最佳化原則

效能最佳化需要在滿足業務需求的前提下，在各種資源和限制條件下去平衡和取捨，遵循一些大的原則有助於消除不確定性，去逼近解決問題的最優解。具體來說，中轉交通拼接優化過程中主要遵循以下三個原則：

2.1 效能最佳化是手段而不是目的

##雖然本文是關於效能最佳化的，但仍需要在最開始強調：不要為了優化而優化。滿足業務需求的方式很多，效能優化只是其中一種。有時候問題非常複雜，限制也很多，在不顯著影響使用者體驗的前提下，透過放寬限製或採用其他流程來減少對使用者的影響，這也是解決效能問題的好方法。在軟體開發中，有許多透過犧牲少量效能來實現大幅降低成本的例子。例如，在Redis中用於基數統計（去重）的HyperLogLog演算法，它在標準誤差為0.81%的前提下，只需要12K空間就能夠統計264的資料。

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

2.2 不正確的最佳化是萬惡之源

Donald Knuth在《Structured Programming With Go To Statements》中提到：「程式設計師浪費大量的時間去思考、擔憂非關鍵路徑的效能，而嘗試優化這部分效能，對整體程式碼的調試和維護都有非常嚴重的負面影響，因此97%的情況，我們應該忘記小的優化點」。簡而言之，在沒有發現真正的效能問題之前，在程式碼層面過度炫技式的優化，不僅不會提高效能，反而可能會導致更多的錯誤。然而作者同樣也強調：「對於剩下關鍵的3%，我們也不要錯過優化的機會」。因此，需要時時注意效能問題，不做會影響效能的決策，並在必要的時候做正確的最佳化。

2.3 量化分析效能，明確優化方向

如如前一節所述，在進行最佳化之前，首先要量化效能並找出瓶頸，這樣最佳化的才更有針對性。量化分析效能可以藉助耗時監控、Profiler效能分析工具、Benchmark基準測試工具等，重點放在耗時特別長或執行頻率特別高的地方。如同阿姆達爾定律所述:「系統中對某一部件採用更快執行方式所能獲得的系統性能改進程度，取決於這種執行方式被使用的頻率，或所佔總執行時間的比例」。

此外，還需要注意到效能最佳化是一場持久戰。隨著業務的不斷發展，架構和程式碼也不停地變化，因此更需要持續量化效能，不斷分析瓶頸和評估最佳化效果。

三、效能分析之路

3.1 梳理業務流程

在效能分析之前，先整理業務流程。中轉交通方案拼接主要包含以下四個步驟：

a.  載入線路圖，如北京經南京中轉到上海，只考慮線路本身的信息，與具體的班次無關；

b.  查火車、飛機、汽車、船舶的產線數據，包括出發時間、到達時間、出發站、到達站、價格和餘票資訊等；

c.  拼接出所有可行的轉機交通方案，主要是考慮轉乘時間不能過短，以免無法完成轉乘；同時也不宜過長，以免等待太久。拼接出可行的方案後，還需要完善業務字段，例如總價格、總耗時和換乘資訊等；

d.  根據一定的規則，從拼接出的所有可行中轉方案中篩選出一些使用者可能感興趣的方案。

3.2 量化分析效能

（1）增加耗時監控

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

耗時監控可以藉助公司內部的指標監控警告系統，在中轉交通方案拼接的主要流程中增加耗時打點。這些流程包括載入線路圖、查詢班次資料並進行拼接、篩選和保存拼接方案等。各階段的耗時情況如圖2所示，可以看到，拼接（含查產線資料）的耗時佔比最高，因此成為未來重點優化的目標。

圖2 中轉交通拼接耗時監控

##（2）Profiler效能分析

耗時打點可能會入侵業務程式碼，並對效能產生影響，因此不宜過多，更適合監控主要流程。與之對應的Profiler效能分析工具（例如Async-profiler），可以產生更具體的呼叫樹以及各函數的CPU佔用比例，進而幫助關鍵路徑與效能瓶頸的分析與定位。

圖3 拼接呼叫樹與CPU佔比

如圖3所示，拼接方案（combineTransferLines）佔53.80%，查產線資料（querySegmentCacheable，已使用快取）佔21.45%。在拼接方案中， 計算方案評分(computeTripScore，佔48.22%)、創建方案實體（buildTripBO，佔4.61%）和檢查拼接可行性（checkCombineMatchCondition，佔0.91%）是佔比最大的三個環節可行性。

圖4 方案評分呼叫樹與CPU佔比#

繼續分析佔比最高的計算方案評分（computeTripScore）時，發現主要與自訂的字串格式化函數（StringUtils.format）有關，包括直接呼叫（用於展示方案評分細節），以及透過getTripId間接呼叫（用於生成方案的ID）。自訂的StringUtils.format中佔比最高的是java/lang/String.replace，Java 8原生的字串替換是透過正規實現的，效率比較低（這個問題在Java9之後已經改進了）。

// 计算方案评分(computeTripScore) 中调用的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 中调用StringUtils.format代码示例
StringUtils.format("{0}_{1}_{2}_{3}_{4}_{5}_{6}", aaaa, bbbb, cccc, dddd, eeee, ffff)


// 通过Java replace实现的自定义format函数
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基準測試

#借助Benchmark基準測試工具可以更準確地測量程式碼的執行時間。在表1中，我們透過JMH（Java Microbenchmark Harness）對三種字串格式化方法和一種字串拼接方法進行耗時測試。測試結果表明，使用Java8的replace方法實現的字串格式化效能最差，而使用Apache的字串拼接函數效能最佳。

表1 字串格式化與拼接效能比較

實作	執行1000次平均耗時(us)
使用Java8的replace實作的StringUtils.format	1988.982
#使用Apache replace實作的StringUtils.format	656.537
#Java8自帶String.format	#1417.474
Apache的StringUtils.join	#116.812

################################## ####

四、性能优化之路

通过以上的性能分析，我们发现拼接和查询产线数据是性能瓶颈，字符串格式化影响尤其大。因此，我们将致力于优化这些部分，以提高性能表现。

4.1 优化代码逻辑

优化代码逻辑是最简单且性价比最高的方法，可以是修正有问题的代码或替换为更好的实现。不同的实现，哪怕减上几纳秒，累加起来也是很可观的。借助一些经典算法或数据结构（如快速排序、红黑树等）可以在时间和空间复杂度方面带来显著优势。回到中转交通方案拼接性能优化本身，优化的代码逻辑主要包括：

（1）优化字符串拼接性能​

如前面的JMH的结果所示，自定义的字符串格式化函数性能最差，因此作为重点优化目标。优化前后的对比如下所示：

// 优化前，通过Java replace实现的format函数
public static String format(String template, Object... parameters) {
for (int i = 0; i < parameters.length; i++) {
template = template.replace("{" + i + "}", parameters[i] + "");
}
return template;
}
// 优化后，通过Apache replace实现的format函数
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;
}

根据JMH的测试结果，即使是优化后的格式化函数，其性能也不是最优的。在不显著影响可读性的前提下，应尽量使用性能更优的StringUtils.join函数。

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


// 优化后
StringUtils.join("_", aaaa, bbbb, cccc, dddd, eeee, ffff)

为进一步提升性能，可以在computeTripScore 函数中添加一个开关，仅在调试模式下才展示评分细节，这将确保该字符串格式化函数仅在需要时才被调用。

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);
}

优化后的CPU占比如图5所示，此时字符串格式化已经不再是性能瓶颈。

图5 优化后的拼接调用树和CPU占比

（2）增加索引降低拼接时间复杂度​

图6 增加索引降低拼接时间复杂度

在中转拼接过程中，我们需要将第一程每个班次的到达时间与第二程每个班次的出发时间进行比较，以判断中转时间是否过短或过长。为简化说明，假设换乘时间间隔需要满足大于30分钟且小于6小时。以北京到上海经南京中转的两程火车为例，3月9日北京到南京有66个班次，南京到上海有275个班次，考虑到隔夜车，还需要算上3月10日南京到上海的275个班次，那么最多需要比较36300（66*275*2）次。

为避免频繁比较，参考了MySQL B+树索引的思想，将第二程南京到上海的所有火车班次数据构建成红黑树。其中，树的键为秒级时间戳，例如2023-03-09 11:29出发的G367键为1677247680，值为G367的班次数据。有了索引树，最多只需要10次比较，就可以找到最近的满足最小换乘时间要求的班次。同理，最多需要10次比较，就能找到满足最大换乘时间要求的最晚班次。两者之间的所有班次都满足耗时要求，直接进行拼接即可。改进后最多需要比较1320(66*(10+10))次，约为原来的1/27.5。

（3）使用多路归并求Top-K算法​

在筛选方案时，会存在以下场景：有多个中转点，每个中转点都有数百个得分较高的方案（内部已按得分由高到低排序，通过小根堆实现）。最终需要将这些方案合并，并从中筛选出得分最高的K个方案。

最简单的方法是使用快速排序将所有的方案排序，然后选取前K个，时间复杂度约为O(nlog2n)。然而，这并没有利用到每个队列自身有序的特点。通过多路归并算法时间复杂度可降为O(nlog2k)，具体步骤为：

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

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

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

d.  重複步驟2和3，直到結果集中包含K個元素或所有的佇列都為空。

圖7 多路歸併求Top-K演算法

4.2 建構多層快取

快取是一種典型的以空間換時間策略，可以快取資料和計算結果，快取資料可以提高存取效率，快取結果避免了重複計算。快取在帶來效能提升的同時，又會引入新的問題：

• 快取容量有限，需要仔細斟酌資料的載入、更新、失效和取代策略；
• 快取架構的設計：通常來說記憶體快取（如HashMap、Caffeine等）效能最高，而Redis等分散式快取次之，RocksDB相對較慢，容量上限則正好相反，需要仔細選型並搭配使用；
• 快取不一致問題如何解決，能接受多久的不一致。

在中轉交通方案拼接過程中，需要使用大量的基礎資料（如車站、行政區域等），以及大量的動態資料（例如班次資料）。綜合以上因素並結合中轉交通拼接的業務特點，快取架構做如下設計：

• 基礎資料（如車站、行政區等），因資料量小，變化頻率低，全量保存到HashMap中，週期全量更新；
• 部分火車、飛機、汽車、船舶的班次資料快取到Redis中，以提高存取效率和穩定性。不同產線採取的快取策略稍有不同，但總的來說是定時更新與搜尋觸發更新相結合的方式；
• 一次拼接過程中可能查詢數百次產線數據，Redis毫秒的延遲累積起來也是非常大的。因此，希望在Redis之上再建構一層記憶體快取以提高效能。透過分析發現拼接過程中存在非常明顯的熱點數據，熱門日期和線路的查詢佔比非常高且數量相對有限。因此可以將這部分熱點資料儲存到記憶體快取中，使用LFU(Least Frequently Used)替換，最終產線資料記憶體快取命中率達到45%以上，相當於降低近一半的IO開銷。
• 因為可以接受分鐘級的資料不一致，所以將拼接結果快取起來，在有效期限內，如果下一個使用者查詢同一出發日期的相同線路，直接使用快取資料即可。因為拼接的中轉方案資料相對較大，所以將拼接結果儲存到RocksDB中，雖然效能不如Redis，但是對於單次查詢影響還可以接受。

#圖8 多層快取結構

4.3 預處理

儘管理論上可以選擇任意城市作為兩地的中轉點，但實際上大部分中轉城市都無法拼接出優質的方案。因此，先透過離線預處理篩選出部分高品質的中轉點，從而將求解空間從數千降至數十。相對於動態變化的班次，線路資料是相對固定的，每天計算一次即可。此外離線預處理可以藉助大數據技術，處理大量數據，相對對耗時不敏感。

4.4 多執行緒處理

在一次拼接過程中，需要處理數十條不同中轉點的線路。每個線路的拼接是相互獨立的，因此可以採用多執行緒處理，這樣可以最大程度地降低處理時間。但受線路班次數量和快取命中率的影響，不同線路的拼接耗時難以一致。很多時候，分配相同任務數量的兩個線程，即使一個線程很快執行完，也要等待另外一個線程執行完才能進行下一步操作。為避免這種情況，這裡借助ForkJoinPool的work-stealing機制。這個機制可以確保每個執行緒在完自己的任務後，也會分擔其他執行緒未完成的工作，提高並發效率，減少空閒時間。

但是多執行緒也不是萬能的，使用時需要注意：

• #子任務的執行需要相互獨立、互不影響。如果存在依賴關係，則需要等待前一個任務執行完才能開始下一個任務，這會使多執行緒失去意義；
• CPU核數決定了並發能力的上限，過多的執行緒會因頻繁切換上下文而降低效能，需要特別注意線程數、CPU使用率、CPU Throttled time等指標。

4.5 延遲計算

透過將計算延遲到必要的時刻，可能避免很多多餘的開銷。例如，在拼接完中轉方案後，需要建置方案實體並完善業務字段，這部分也比較消耗資源。而且並非所有拼接的方案都會被篩選出來，這意味著這部分未被篩選的方案仍然需要耗費運算資源。因此延遲完整方案實體對象的構建，先將拼接過程中的數以萬計的方案保存為輕量級的中間對象，只對篩選之後的數百個中間對象構建完整的方案實體。

4.6 JVM優化

中轉交通拼接專案是基於Java 8的，並使用G1(Garbage-First)垃圾收集器，部署在8C8G機器上。 G1在實現高吞吐量的同時盡可能滿足停頓時間的要求，系統架構部門設定的預設參數已經能夠適用於大多數場景，通常不需要專門的最佳化。

但有些線路中轉方案過多，導致封包太大，超過Region大小的一半(8G 預設Region大小是2M)，導致很多應該進入年輕代的大物件直接進入了老年代，為了避免這種情況，將Region大小改為16M。

五、總結

透過以上的分析與最佳化，拼接耗時變化如圖9所示：

圖9 中轉交通方案拼接效能最佳化效果

#雖然每個業務和場景都有各自的特點，但效能最佳化時也需要具體分析。但原理是相通的，依然可以參考本文所述的分析和最佳化方法。本文所有的分析與最佳化方法總結如圖10所示。

圖10 中轉交通方案拼接最佳化總結

以上是優化攜程中轉交通方案的拼接效能的詳細內容。更多資訊請關注PHP中文網其他相關文章！