线上故障小记：低效的组合算法导致的崩溃

快12点了，准备吃饭了，突然收到告警：Process [user2-activity] CPU Time > 50% 某个站点CPU占用超50%了。 注：因为是服务混部，所以对机器上的单个服务，CPU不应该超过50%。 排查步骤： 1、看了一下监控大屏，该服务的所有节点，CPU都偏高，不正常。 2、检查对应的数据库慢查询，一切正常。 3、网关上，下线某台节点，然后对该站点的进程，导出一个内存Dump文件； 4、用WinDebug打开分析，发现有4个线程执行时间较长，卡在 ProcessCalTicket方法 查看对应代码，发现是一个组合算法，代码如下：

List<Ticket> userTickets = xxx; // 用户的可用券清单 List<TicketMerge> list = new List<TicketMerge>(); var processedData = new List<string>(); // 防止重复组合的临时变量 foreach (var item in userTickets) { foreach (var item2 in userTickets) { // 同一对象，不组合 if (item == item2) continue; // 避免出现 AB 和 BA 这样的重复组合 if (CheckAdded(item, item2, processedData)) continue; // 业务逻辑代码，组合2个对象 list.Add(Combine(item, item2)); } } bool CheckAdded(Ticket item, Ticket item2, List<string> list) { string str1 = $"{item.Id}||{item2.Id}"; string str2 = $"{item2.Id}||{item.Id}"; if (list.Any(p => p == str1 || p == str2)) return true; list.Add(str1); list.Add(str2); return false; }

分析了一下，这段代码，是对某个用户的n张券，进行两两组合，以判断能否同时使用。 但是这段代码，执行了3个嵌套循环：2个foreach 和 1个list.Any，时间复杂度是 O(n * n * n) 配合日志，故障时间点有个用户，拥有1万张券，那么就要循环 1万亿次。 难怪会卡，临时解决方案，这个用户是线上拨测用户，清空它的券后恢复。

后续解决方案： 1、业务上优化，每个用户的可用券，不允许超过100张； 2、算法优化，下面的代码，时间复杂度为 O(n(n-1)/2) 1万张券，循环不到5千万次。

List<Ticket> userTickets = xxx; // 用户的可用券清单 List<TicketMerge> list = new List<TicketMerge>(); var arrLen = userTickets.Count; for (var i = 0; i < arrLen; i++) { var item = userTickets[i]; // 两层循环，两两组合 for (var j = i + 1; j < arrLen; j++) { var item2 = userTickets[j]; // 业务逻辑代码，组合2个对象 list.Add(Combine(item, item2)); } }