阿里妹導讀
記錄並分析一次線上支付系統出現OOM（Out Of Memory）故障的排查與解決過程。
一、問題發現
11.7上午10點半時，正值業務高峰期。預警群裡突然報警，支付閘道器的下游HSF請求出現失敗，下游額度中心一臺機子出現異常。於是第一時間通知下游同學緊急隔離問題機器，保證請求正常處理不再報警後，下游同學排查問題。
二、問題排查
下游同學透過grace分析問題機器dump檔案時，根據洩漏報表顯示的崩潰執行緒及程式碼找到我，讓我看一下這個問題，我才知道原來剛剛下游的機子異常是因為這段程式碼，這段程式碼已經執行三個月了，怎麼今天出問題了呢？
帶著疑問，先到執行緒資訊檢視崩潰執行緒的執行情況，發現程式在不斷遞迴，遞迴的過程在不斷建立連結串列佔用記憶體，最後OOM了。
這段程式碼是今年8.8上線的，跟下游同學諮詢得知，10月底到11月初大概還出現過三次某個機子異常，於是初步判斷是個別極端case進入了演算法的盲區。當時上線了AB兩種演算法，兩種演算法從8.8～11.03一直是以1:1的灰度比例執行，從11.03開始全部切到了B演算法，造成OOM的正是B演算法，切換後出問題的機率明顯提高了。先不管具體程式碼是什麼問題，第一時間透過diamond將使用者全量切到A演算法，保證系統穩定。
接下來具體問題具體分析。看case之前不得不先提一下程式碼的背景，1688的批次收銀臺在使用者進入批次支付時會進行支付諮詢，對於開通金融產品的客戶，支付諮詢時會到金融閘道器查詢該批訂單可用金融產品支付的訂單條目，得到結果後對客展示。
而額度中心管控的額度多種多樣，其中有一種叫透支額度，是在對客透傳的額度之外，使用者還可以使用的額度。當用戶其他額度都不夠支付這一批訂單時，會使用到這一部分額度，並且只能使用一次。我們希望在有限的額度裡實現使用者可支付訂單金額總和最大化，B演算法要做的也是這個事情。
進一步線上程資訊中找到過程引數，定位使用者id，先把case拉出來。
然後透過sls查詢具體的請求引數，發現這個使用者下了47筆訂單，突破了原本30筆的限制。
其實批次收銀臺前端是有30筆的支付上限的，而B演算法的執行上限在37筆，這個case的47筆使用者是怎麼進來的，後面再查。先看看這個case下暴露的程式碼問題。
程式碼如下，該演算法輸入一組訂單，以及該批訂單的最高可用額度maxQuota，返回最接近maxQuota的一組訂單，實現使用者可用額度應用盡用。比如有三筆訂單，訂單1金額為800元，訂單2金額為500元，訂單3金額為400元，使用者可使用額度為900元時，系統返回訂單2、3，使用者可用800元時，系統返回訂單1。這是一個nums與goal的問題，這個問題在leetcode上是一道真題：
https://leetcode.cn/problems/closest-subsequence-sum/，感興趣的同學可以看一下。B演算法解決這個問題的思路是分治加回溯，將訂單均分為左右兩部分，依次求出兩邊的子集，以及每個子集對應的金額和之後，根據金額和對兩部分子集分別排序，之後結合兩部分集合，透過雙指標求出最接近maxQuota的集合。但是跟leetcode不同的在於，題目要求的是最小差值，而我們要求最小差值對應的訂單集，因此在回溯求子集的過程中要記錄下最接近目標值的一組訂單。演算法的時間複雜度是O(n/2*(2^(2/n)))，空間複雜度原本是O(n)，即棧的深度，在這裡因為要記錄子集，是O(2^(2/n))。
publicstatic List<BatchPayOrder> findBestCanPayOrders(List<BatchPayOrder> input, long maxQuota) {if (input.size() == 1) {if (input.get(0).getAmount() <= maxQuota) {return input; } }int len = input.size() >> 1; List<BatchPayOrder> result = new LinkedList<>(); List<BatchPayOrder> numsLeft = input.subList(0, len); List<BatchPayOrder> numsRight = input.subList(len, input.size()); List<Temp> resultLeft = subsets(numsLeft); List<Temp> resultRight = subsets(numsRight); Collections.sort(resultLeft, getComparator()); Collections.sort(resultRight, getComparator());int i1 = 0, n1 = resultLeft.size(), i2 = resultRight.size() - 1;long ans = Math.abs(maxQuota);while (i1 < n1 && i2 >= 0) {long num = resultLeft.get(i1).getSum() + resultRight.get(i2).getSum() - maxQuota;if (num > 0) { i2--; } elseif (num < 0) {if(-num<ans){ result.removeAll(result); result.addAll(resultLeft.get(i1).getSubset()); result.addAll(resultRight.get(i2).getSubset()); } ans = Math.min(ans, -num); i1++; } else { result.removeAll(result); result.addAll(resultLeft.get(i1).getSubset()); result.addAll(resultRight.get(i2).getSubset());return result; } }return result; }publicstatic List<Temp> subsets(List<BatchPayOrder> input) { List<Temp> result = new LinkedList<>();if(input.size()==0){return result; } helper(input,0,new LinkedList<>(),result, 0);return result; }privatestaticvoidhelper(List<BatchPayOrder> input, int index, LinkedList<BatchPayOrder> subset, List<Temp> result, long sum){if(input.size()==index){ Temp temp = new Temp(); temp.setSubset(new LinkedList<>(subset)); temp.setSum(sum); result.add(temp); }elseif(index<input.size()){ helper(input,index+1,subset,result, sum); sum += input.get(index).getAmount(); subset.add(input.get(index)); helper(input,index+1,subset,result, sum); sum -= input.get(index).getAmount(); subset.removeLast(); } } @DatapublicstaticclassTemp{privatelong sum;private LinkedList<BatchPayOrder> subset; }在出現問題的case中，該使用者選擇了47筆訂單，對應回溯過程中resultLeft與resultRight會有2^23 = 8388608與2^24 = 16777216種組合，每個子集都需要記錄，這也是空間複雜度被打爆的原因。
三、問題解決
3.1、可選解法
3.1.1、最簡演算法
為了保證B演算法帶來的gmv，在當天緊急上線了簡單版的多筆演算法。簡單演算法將訂單排序後做一次遍歷，訂單金額小於額度就放進池子裡，原則是能用就用。在金融訂單貼現產品中用的就是這種方式，簡單粗暴。
privatestatic BiFunction<List<BatchPayOrder>, Long, List<Long>> SIMPLEST_MULTI_FUNC = (input, maxQuota) -> { List<Long> result = new ArrayList<>(); final long[] finalMaxQuota = {maxQuota}; Optional.ofNullable(input).orElse(Collections.emptyList()) .stream().sorted(Comparator.comparing(BatchPayOrder::getAmount).reversed()).forEach(order -> {if (finalMaxQuota[0] >= order.getAmount()) { result.add(order.getOrderId()); finalMaxQuota[0] -= order.getAmount(); } } );return result; };3.1.2、分治+回溯
之後對B演算法的空間複雜度進行最佳化，思路是把長訂單號做一個0～n的簡單對映，同時用String替代連結串列儲存子集，改進後的程式碼如下：
privatestatic BiFunction<List<BatchPayOrder>, Long, List<Long>> DIVIDE_AND_TRACE_BACK_FUNC = (input, maxQuota) -> {int len = input.size() >> 1; Map<Integer, Long> mapping = Maps.newHashMap(); List<BatchPayOrder> convertInput = convert(input, mapping); List<BatchPayOrder> numsLeft = convertInput.subList(0, len); List<BatchPayOrder> numsRight = convertInput.subList(len, input.size()); List<Temp> resultLeft = subsets(numsLeft); List<Temp> resultRight = subsets(numsRight); resultLeft = resultLeft.stream().sorted(Comparator.comparing(Temp::getSum)).collect(Collectors.toList()); resultRight = resultRight.stream().sorted(Comparator.comparing(Temp::getSum)).collect(Collectors.toList()); StringBuilder resultOrdersStr = new StringBuilder();int i1 = 0, n1 = resultLeft.size(), i2 = resultRight.size() - 1;long ans = Math.abs(maxQuota);while (i1 < n1 && i2 >= 0) {long num = resultLeft.get(i1).getSum() + resultRight.get(i2).getSum() - maxQuota;if (num > 0) { i2--; } elseif (num < 0) {if (-num < ans) { resultOrdersStr.delete(0, resultOrdersStr.length()); resultOrdersStr.append(resultLeft.get(i1).getChoiceChain()); resultOrdersStr.append(resultRight.get(i2).getChoiceChain()); } ans = Math.min(ans, -num); i1++; } else { resultOrdersStr.delete(0, resultOrdersStr.length()); resultOrdersStr.append(resultLeft.get(i1).getChoiceChain()); resultOrdersStr.append(resultRight.get(i2).getChoiceChain());return getListFromChoiceChain(resultOrdersStr, mapping); } }return getListFromChoiceChain(resultOrdersStr, mapping); };privatestatic List<BatchPayOrder> convert(List<BatchPayOrder> input, Map<Integer, Long> mapping){ final Integer[] i = {1};return input.stream().map(order->{ BatchPayOrder batchPayOrder = new BatchPayOrder(); batchPayOrder.setOrderId((long)i[0]); batchPayOrder.setAmount(order.getAmount()); mapping.put(i[0], order.getOrderId()); i[0]++;return batchPayOrder; }).collect(Collectors.toList()); }privatestatic List<Temp> subsets(List<BatchPayOrder> input) { List<Temp> result = new LinkedList<>();if(input.size()==0){return result; } helper(input,0, new StringBuilder(), result, 0);return result; }privatestaticvoidhelper(List<BatchPayOrder> input, int index, StringBuilder choiceChain, List<Temp> result,long sum) {if (input.size() == index) { Temp temp = new Temp(); temp.setChoiceChain(choiceChain.toString()); temp.setSum(sum); result.add(temp); } elseif (index < input.size()) { helper(input, index + 1, choiceChain, result, sum); sum += input.get(index).getAmount(); choiceChain.append("|").append(input.get(index).getOrderId()); helper(input, index + 1, choiceChain, result, sum); sum -= input.get(index).getAmount(); choiceChain.delete(choiceChain.length()-input.get(index).getOrderId().toString().length()-1, choiceChain.length()); } }privatestatic List<Long> getListFromChoiceChain(StringBuilder resultOrdersStr, Map<Integer, Long> mapping) { List<Long> result = new ArrayList<>(); String[] orderIds = resultOrdersStr.toString().split("\\|");for (int i = 1; i < orderIds.length; i++) { result.add(mapping.get(Integer.valueOf(orderIds[i]))); }return result; } @DatastaticclassTemp{privatelong sum;private String choiceChain; }3.1.3、揹包演算法
後來經小夥伴提醒，這個問題是可以用揹包問題解決的，仔細一看，還真是。將maxQuota看成揹包大小，訂單作為物品，amount[n]表示訂單金額陣列，不難寫出狀態轉移方程：
if (j >= amount[i]) { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - amount[i]] + amount[i]);} else { dp[i][j] = dp[i - 1][j];}其中 i: 1~n ，j: 1-maxquota，演算法實現如下，時間複雜度為：n*maxquota，空間複雜度為：n*maxquota ， 因為要回溯選擇路徑，不做狀態壓縮。演算法實現如下：
privatestatic BiFunction<List<BatchPayOrder>, Long, List<Long>> KNAPSACK_FUNC = (input, maxQuota) -> { List<Integer> orderAmount = input.stream().map(order -> Integer.valueOf(order.getAmount().toString())) .collect(Collectors.toList());int[][] dp = newint[orderAmount.size()][Integer.valueOf(maxQuota.toString()) + 1];int[] choice = newint[orderAmount.size()];for (int j = 1; j <= maxQuota; j++) {if (j >= orderAmount.get(0)) { dp[0][j] = orderAmount.get(0); } }for (int i = 1; i < orderAmount.size(); i++) {for (int j = 1; j <= maxQuota; j++) {if (j >= orderAmount.get(i)) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - orderAmount.get(i)] + orderAmount.get(i)); } else { dp[i][j] = dp[i - 1][j]; } } } traceOrderIds(input.size(), Integer.valueOf(maxQuota.toString()), orderAmount, choice, dp); List<Long> result = Lists.newArrayList();for (int i = 0; i < input.size(); i++) {if (choice[i] == 1) { result.add(input.get(i).getOrderId()); } }return result; };privatestaticvoidtraceOrderIds(int n, int maxQuota, List<Integer> orderAmount, int[] choice, int[][] dp){for (int i = n - 1; i >= 1; i--) {if (dp[i][maxQuota] == dp[i - 1][maxQuota]) {// 表示沒有選擇第i筆訂單 choice[i] = 0; } else { choice[i] = 1; maxQuota -= orderAmount.get(i); } }// 訂單1單獨判斷，>0表示選擇了 choice[0] = (dp[0][maxQuota] > 0) ? 1 : 0; }3.2、演算法比較與選擇
3.2.1、背景資料
寫完演算法，接下來面臨的問題是怎麼選擇演算法。當然用於生產，還是要參照資料進行選擇，已知情況如下：
1、介面rt
演算法在使用者支付鏈路上使用，整個介面rt<40ms，要求時間複雜度不能過高。
2、歷史資料
分析歷史資料，我們不難找出80%～90%使用者maxQuota跟orderNum。這部分內容出於安全考慮做了模糊化，真實情況屬於金額大，訂單小。
3.2.2、對比實驗
接下來通過幾組效能測試檢視分治+回溯與揹包演算法的效果。根據金額大，訂單小的資訊，我們假設幾個閾值，來看演算法效能。
1）設定maxquota為100000，使用者平均一個批次下單5筆
執行引數：
金額：100000; 訂單數：5; 耗時單位：us
預估時間複雜度：
分治+回溯: 3*2^3 =24；揹包：50w
預估空間複雜度：
分治+回溯: 2^3 = 8；揹包：50w
workbench測試：
2）保持100000不變，提高訂單量到20筆
執行引數：
金額：100000；訂單數：20; 耗時單位：us
預估時間複雜度：
分治+回溯: 10*2^10 = 10240；揹包：200w
預估空間複雜度：
分治+回溯: 2^10 = 1024；揹包：200w
workbench測試：
3）保持100000不變，提高訂單量到30筆
執行引數：
金額：100000；訂單數：30; 耗時單位：us
預估時間複雜度：
分治+回溯: 15*2^15；揹包：300w
預估空間複雜度：
分治+回溯: 2^15；揹包：300w
workbench測試：
4）保持訂單量30筆不變，金額降到50000
執行引數：
金額：50000；訂單數：30; 耗時單位：us
預估時間複雜度：
分治+回溯: 15*2^15；揹包：150w
預估空間複雜度：
分治+回溯: 2^15；揹包：150w
workbench測試：
3.2.3、最後選擇
觀察上述實驗可知，在80%的使用者金額大、訂單小的情況下，分治+回溯的表現會比揹包好，因為訂單量小，降低了時間與空間的複雜度。同時當訂單量上來時，分治+回溯顯得有些疲憊，而當金額上來時，揹包也捉襟見肘了，於是有了以下折衷選擇：
-
訂單數<ORDER_THRESHOLD，選擇分治+回溯；
-
訂單數>ORDER_THRESHOLD，可用額度<=AMOUNT_THRESHOLD，選擇揹包；
-
其他情況選擇兜底最簡演算法；
publicstatic List<Long> executeMultiOverDrawnAlgorithm(List<BatchPayOrder> inputOrder, long maxQuota){if (CollectionUtils.isEmpty(inputOrder)) {return Collections.emptyList(); }//透支金額滿足訂單總價值，直接返回long needOverDraftAmountSum = inputOrder.stream().mapToLong(order -> order.getAmount()).sum();if (needOverDraftAmountSum <= maxQuota) {return inputOrder.stream().map(order -> order.getOrderId()).collect(Collectors.toList()); }//訂單數<=ORDER_THRESHOLD，使用分治+回溯if (inputOrder.size() <= ORDER_THRESHOLD) {return DIVIDE_AND_TRACE_BACK_FUNC.apply(inputOrder, maxQuota); }//訂單數大於ORDER_THRESHOLD，額度<=AMOUNT_THRESHOLD使用揹包if (maxQuota <= AMOUNT_THRESHOLD) {return KNAPSACK_FUNC.apply(inputOrder, maxQuota); }//其他情況使用最簡演算法return SIMPLEST_MULTI_FUNC.apply(inputOrder, maxQuota); } 四、問題體會
這是成為練習時長兩年半的練習生以來第一次在線上遇到比較有趣的場景，可以跟leetcode演算法題聯動，也是第一次遇到OOM的問題，值得記錄。從中的感受有幾點，第一，因為組織架構變動等一些原因，這段跟業務強相關的程式碼一直被放在下層原子能力層（額度中心），未來尋求遷移方案；第二，在實際程式設計過程中，一定要充分考慮邊界以及做效能測試，避免一些極端情況對系統帶來未知影響；第三，演算法的探索是無止境的，感謝兩位夥伴在揹包演算法上的提醒。
企業雲上網路架構規劃
企業雲上網路架構規劃方案能夠為企業提供面向業務的網路架構，確保業務的可靠性，並保持架構的可擴充套件性和可持續性。
點選閱讀原文檢視詳情。
