LeetCode子集求和算法在实际应用中引发OOM问题，本文分享了故障排查、优化及最终解决方案。
原文标题：当leetcode真题上了生产引发的线上问题
原文作者：阿里云开发者
冷月清谈：
该算法的背景是1688批量收银台的支付咨询功能，旨在帮助用户在有限额度下最大化可支付订单金额。线上使用的B算法借鉴了LeetCode的子集求和问题思路，采用分治加回溯的策略。然而，与LeetCode题目不同的是，该场景需要记录订单集合而非最小差值，导致空间复杂度增加。当用户订单数量超过预期时，算法的空间复杂度会急剧上升，最终引发OOM。
为了解决这个问题，开发团队首先紧急上线了简单的贪心算法作为临时方案。随后，他们对B算法进行了空间复杂度优化，将链表替换为字符串存储子集，并对订单进行映射以减少内存占用。此外，他们还考虑了使用动态规划的背包算法来解决这个问题。
通过性能测试对比，团队发现优化后的分治+回溯算法在订单量较小的情况下性能优于背包算法。最终，他们采用了一种混合策略：当订单数量小于阈值时使用优化后的分治+回溯算法，当订单数量超过阈值且可用额度低于阈值时使用背包算法，其他情况则使用最简算法。
怜星夜思：
2、除了文中提到的三种算法，还有其他更优的算法可以解决这个问题吗？例如，有没有时间复杂度和空间复杂度都更低的算法？
3、文章中提到将代码从额度中心迁移出去，具体应该迁移到哪个服务更合适？迁移过程中需要注意哪些问题？
原文内容
阿里妹导读
记录并分析一次线上支付系统出现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下暴露的代码问题。
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<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--; } else if (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; }public static 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;
}private static void helper(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);
}else if(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();
}
}
@Data
public static class Temp{
private long sum;
private LinkedList<BatchPayOrder> subset;
}
在出现问题的case中，该用户选择了47笔订单，对应回溯过程中resultLeft与resultRight会有2^23 = 8388608与2^24 = 16777216种组合，每个子集都需要记录，这也是空间复杂度被打爆的原因。
三、问题解决
3.1、可选解法
3.1.1、最简算法
为了保证B算法带来的gmv，在当天紧急上线了简单版的多笔算法。简单算法将订单排序后做一次遍历，订单金额小于额度就放进池子里，原则是能用就用。在金融订单贴现产品中用的就是这种方式，简单粗暴。
private static 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替代链表存储子集，改进后的代码如下：
private static 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--; } 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<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());
}private static 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;
}private static void helper(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);
} 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<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;
}
@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<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 = 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<Long> 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<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，选择背包；
-
其他情况选择兜底最简算法；
public static 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的问题，值得记录。从中的感受有几点，第一，因为组织架构变动等一些原因，这段跟业务强相关的代码一直被放在下层原子能力层（额度中心），未来寻求迁移方案；第二，在实际编程过程中，一定要充分考虑边界以及做性能测试，避免一些极端情况对系统带来未知影响；第三，算法的探索是无止境的，感谢两位伙伴在背包算法上的提醒。
企业云上网络架构规划
企业云上网络架构规划方案能够为企业提供面向业务的网络架构，确保业务的可靠性，并保持架构的可扩展性和可持续性。
点击阅读原文查看详情。