记录并分析一次线上支付系统出现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))。
public static List findBestCanPayOrders(List input, long maxQuota) { if (input.size() == 1) { if (input.get(0).getAmount() <= maxQuota) { return input; } } int len = input.size() >> 1; List result = new LinkedList<>(); List numsLeft = input.subList(0, len); List numsRight = input.subList(len, input.size()); List resultLeft = subsets(numsLeft); List 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--; } else if (num < 0) { if(-num 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; }
public static List subsets(List input) { List result = new LinkedList<>(); if(input.size()==0){ return result; } helper(input,0,new LinkedList<>(),result, 0); return result; }
private static void helper(List input, int index, LinkedList subset, List result, long sum){ if(input.size()==index){ Temp temp = new Temp(); temp.setSubset(new LinkedList<>(subset)); temp.setSum(sum); result.add(temp); }else if(index 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(); } }
@Data public static class Temp{ private long sum; private LinkedList subset; }
在出现问题的case中，该用户选择了47笔订单，对应回溯过程中resultLeft与resultRight会有2^23 = 8388608与2^24 = 16777216种组合，每个子集都需要记录，这也是空间复杂度被打爆的原因。
3.1.1、最简算法
为了保证B算法带来的gmv，在当天紧急上线了简单版的多笔算法。简单算法将订单排序后做一次遍历，订单金额小于额度就放进池子里，原则是能用就用。在金融订单贴现产品中用的就是这种方式，简单粗暴。
private static BiFunction, Long, List> SIMPLEST_MULTI_FUNC = (input, maxQuota) -> {
List 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替代链表存储子集，改进后的代码如下：
private static BiFunction, Long, List> DIVIDE_AND_TRACE_BACK_FUNC = (input, maxQuota) -> {
int len = input.size() >> 1; Map mapping = Maps.newHashMap(); List convertInput = convert(input, mapping); List numsLeft = convertInput.subList(0, len); List numsRight = convertInput.subList(len, input.size()); List resultLeft = subsets(numsLeft); List 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--; } else if (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); };
private static List convert(List input, Map 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()); }
private static List subsets(List input) { List result = new LinkedList<>(); if(input.size()==0){ return result; } helper(input,0, new StringBuilder(), result, 0); return result; }
private static void helper(List input, int index, StringBuilder choiceChain, List result, long sum) { if (input.size() == index) { Temp temp = new Temp(); temp.setChoiceChain(choiceChain.toString()); temp.setSum(sum); result.add(temp); } else if (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()); } }
private static List getListFromChoiceChain(StringBuilder resultOrdersStr, Map mapping) { List 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; }
@Data static class Temp{ private long 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 ， 因为要回溯选择路径，不做状态压缩。算法实现如下：
private static BiFunction, Long, List> KNAPSACK_FUNC = (input, maxQuota) -> {
List orderAmount = input.stream().map(order -> Integer.valueOf(order.getAmount().toString())) .collect(Collectors.toList()); int[][] dp = new int[orderAmount.size()][Integer.valueOf(maxQuota.toString()) + 1]; int[] choice = new int[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 result = Lists.newArrayList(); for (int i = 0; i < input.size(); i++) { if (choice[i] == 1) { result.add(input.get(i).getOrderId()); } } return result; };
private static void traceOrderIds(int n, int maxQuota, List orderAmount, int[] choice, int[][] dp) { for (int i = n - 1; i >= 1; i--) { if (dp[i][maxQuota] == dp[i - 1][maxQuota]) { choice[i] = 0; } else { choice[i] = 1; maxQuota -= orderAmount.get(i); } } choice[0] = (dp[0][maxQuota] > 0) ? 1 : 0; }
3.2.1、背景数据
写完算法，接下来面临的问题是怎么选择算法。当然用于生产，还是要参照数据进行选择，已知情况如下：
