侧边栏壁纸
博主头像
东家博主等级

东家不是家,心里有个她!

  • 累计撰写 6 篇文章
  • 累计创建 8 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

慢接口优化之回溯算法应用

Administrator
2023-05-05 / 0 评论 / 0 点赞 / 46 阅读 / 6401 字

阅读前置条件:了解深度优先搜索回溯算法技巧

背景

每到月初月末的时候,系统都会达到使用高峰。使用人数的增加难免会出现一些平时不能发现的问题,比如在平时响应很快的接口突然变得缓慢,甚至影响到系统的稳定性。这些接口在平时比较难以发现,在没有专业的压测流程的情况下很容易被忽略。今天优化的接口也是这种情况之一,在预发布环境和线上环境都能好好运行,且满足接口响应时间限制,但是到了线上高峰大流量的使用时段,接口就显著变慢。

接口需求

该接口用于计算员工的KPI、相关订单、升星进度信息

由于公司内部一些规定不方便粘贴源码,我将接口抽象到下面的代码中:

数据库建模

CREATE TABLE data_a
(
    id       INT AUTO_INCREMENT PRIMARY KEY,
    order_id varchar(26) not null default ''
    -- 其他相关字段
);
CREATE TABLE data_b
(
    id      INT AUTO_INCREMENT PRIMARY KEY,
    setting varchar(10)
    -- 其他相关字段
);
CREATE TABLE data_c
(
    id            INT AUTO_INCREMENT PRIMARY KEY,
    progress_info varchar(10)
    -- 其他相关字段
);
CREATE TABLE junction
(
    id   INT AUTO_INCREMENT PRIMARY KEY,
    a_id INT comment '订单表',
    b_id INT comment 'KPI规则表',
    c_id INT comment '进度表'
);

即可以简单理解为:将data_a、data_b、data_c表中的数据处理完成后整理到junction表中,并对a、b、c三张表建立一个多对多的关系,供其他系统使用

排查思路

  1. Redis缓存是否被击穿或穿透?
  2. MySQL数据库索引是否合理且正常?
  3. 是否有大事务?
  4. 代码时间复杂度太高?
  5. 本身设计是否合理?

排除流程

通过和DBA方的沟通并结合自己的所学,可以排除数据库层面的(思路1、2)问题。(这里如何确定是数据库问题,可以先走Redis调优和MySQL调优流程)

那么我们现在的重心就落到了排查(是否有大事务?代码时间复杂度是否太高?)上面

🦀是否有大事务?

大事务:粗略的理解为数据量大,执行时间长的MySQL事务操作。常在批量操作的时候出现

很明显从数据库建模可以看出data_a表中数据量较大,需要重点关注。

分析数据量:

员工在某个时间段(一个月)完成的订单数量大致在200到400左右不等,员工数量(特定的员工才处理)大致在200-300。

极限情况下,需要处理12万左右,为了可靠性,我们将接口吞吐设计到15万。

到此,如果一次性处理完所有逻辑,必定是一个大事务。

处理

  • 小批量多线程处理订单信息(多线程还需要考虑数据丢失怎么处理……)
  • 清理代码中的事务逻辑,拆分大事务,前置查询等操作

(这篇文章讲算法优化,所以简述事务优化)

🦀代码时间复杂度太高?

还记得在MySQL建模部分,我们最终需要将 a、b、c中的操作数据清洗到一张宽表(junction)中供其他系统使用

原有逻辑抽象出来的代码:

public class Polymerization {
    private String a;
    private String b;
    private String c;
    // 省略
}

数据整合逻辑:

实际项目中使用了stream来处理,这里只是将业务代码抽象了

private void demo1() {
    List<String> a = new ArrayList<>();
    List<String> b = new ArrayList<>();
    List<String> c = new ArrayList<>();
    a.add("a1");
    a.add("a2");
    b.add("b1");
    b.add("b2");
    c.add("c1");
    c.add("c2");

    List<Polymerization> res = new ArrayList<>();
    for (String sa : a) {
        for (String sb : b) {
            for (String sc : c) {
                res.add(new Polymerization(sa, sb, sc));
            }
        }
    }
    System.out.println(res);
}

我们可以很清晰的看到目前代码的时间复杂度为:O(n^3)

Time Complexity

从上图时间复杂度的函数曲线可以看到 O(n3)是一条明显陡增的曲线,所以会导致接口请求少的时候没有什么变慢的感觉,但是月底清账需要大数据量处理的时候就会变慢。

至此,我们就可以确定一个最大收益比的点:优化代码的时间复杂度

优化思路

可用算法

由于多层循环导致的时间复杂度变高,那么我们第一个思路就是降低循环次数,用于解决具有多重循环结构问题的方法大致有:

  • 分治处理(Divide and Conquer)
  • 深度优先搜索回溯(Depth-First Search Backtracking)

分治处理(Divide and Conquer):

  • 思想:将一个大问题划分为若干个子问题,递归地解决子问题,然后将子问题的解合并得到原问题的解。
  • 实现:通常通过递归函数来实现。在每一层递归中,将问题分成两个或多个较小的子问题,然后对每个子问题进行递归调用。最后将子问题的解合并得到原问题的解。
  • 时间复杂度:通常情况下,分治算法的时间复杂度可以用递推关系式来描述,如T(n) = a * T(n/b) + f(n),其中a表示划分的子问题个数,b表示问题的规模缩小的比例,f(n)表示合并子问题的时间复杂度。时间复杂度可以通过主定理(Master Theorem)进行求解。

深度优先搜索回溯(Depth-First Search Backtracking):

  • 思想:通过递归地尝试每个可能的解决方案来解决问题。当发现当前尝试的解决方案不能达到目标时,回溯到上一个状态,尝试其他的选择。
  • 实现:通常使用递归函数实现。递归函数尝试每个可能的选择,并在每个选择上进行递归调用,然后回溯到上一个状态,继续尝试其他的选择。

算法选择

❓既然我们找到两种方案可以解决多重循环结构带来的问题,那我们具体选择什么呢?

还记得前面我们需要清理出多对多的关系吧,可以理解为每个属性的解决方案(业务中可能是多个属性使用同一个解决方案),而不是将一个对象的属性划分成小的属性去解决,所以我们选择 深度优先搜索回溯(Depth-First Search Backtracking)

可以简单的理解junction中的数据是关于data_a、data_b、data_c表中数据的组合排列问题

private static void dfs(List<List<String>> data, int indexData, int indexA, int indexB, int indexC, Polymerization current) {
    if (indexData >= data.size()) {
        System.out.println(current);
        return;
    }
    if (indexData == 0) {
        for (int i = indexA; i < a.size(); i++) {
            current.setA(a.get(i));
            dfs(data, indexData + 1, i, indexB, indexC, current);
        }
    } else if (indexData == 1) {
        for (int i = indexB; i < b.size(); i++) {
            current.setB(b.get(i));
            dfs(data, indexData + 1, indexA, i, indexC, current);
        }
    } else {
        for (int i = indexC; i < c.size(); i++) {
            current.setC(c.get(i));
            dfs(data, indexData + 1, indexA, indexB, i, current);
        }
    }
}
private static void demo() {
    a.add("a1");
    a.add("a2");
    b.add("b1");
    b.add("b2");
    c.add("c1");
    c.add("c2");
    List<List<String>> data = new ArrayList<>();
    data.add(a);
    data.add(b);
    data.add(c);

    dfs(data, 0, 0, 0, 0, new Polymerization());
}

indexData:表示处理对象中的哪个一批属性,业务自己扩展

indexA\indexB\indexC:该指针是为了防止重复匹配到已经用到的属性。可以理解为数据选取的开始位置。

输出结果:

Polymerization{a='a1', b='b1', c='c1'}
Polymerization{a='a1', b='b1', c='c2'}
Polymerization{a='a1', b='b2', c='c1'}
Polymerization{a='a1', b='b2', c='c2'}
Polymerization{a='a2', b='b1', c='c1'}
Polymerization{a='a2', b='b1', c='c2'}
Polymerization{a='a2', b='b2', c='c1'}
Polymerization{a='a2', b='b2', c='c2'}

总结:

tree

综上所述,其实就是将多个列表的嵌套遍历放到了一颗树中进行,从而降低时间复杂度。

但这种解决方案只能在特定条件下使用,且编码和维护都比较困难,需要对DFS和回溯思想有一定的了解,如果编写代码出错也很容易导致栈溢出

如果通过各方面的努力问题还没有得到解决,那就只有考虑这招了:本身设计是否合理?

0

评论区