工作总结

背景

从去年开始到现在，参与一个新业务的研发。其中一个模块经过了多次优化升级，因此总结于此。
业务场景可以简化为，用户参与活动需要签到，活动的形式为多人一组，因此业务场景为在固定可签到时间内，将用户划分到最‘适合’的小组。

抽象

• 业务高峰期 大概有20W左右用户同时参与
• 业务场景 已经将用户划分为 至多 2K 的集合
• 分组时 分组数据只在一个集合内 也就是说，不同集合分组是相互独立的
• 分组时 一个小组最多N人 M个小组为一个大组
• 用户签到时 默认签到至 最优小组(有人且人多的或者有人且人少的)
• 用户签到后 还可以从默认组 更换至 目标组 换组次数不限
• 活动开始时间后，会进行组分配优化 将人数少的小组合并为一组

业务逻辑

• 获取目标组
  获取目标小组逻辑比较简单，由于需要选择最优小组，最优策略有多种，再次仅写出了其中最简单的一种 - 即签至人数最多的小组。
  最优选择需要选择签至人数最多的，因此需要遍历全量才可以获得最优解。时间复杂度O(n),空间复杂度O(1).

 for (Map.Entry<String, Integer> entry : groupList.entrySet()) {
            // 组内已满 直接跳过
            if (entry.getValue() >= GroupEnum.GROUP_STU_NUM.getValue()) {
                continue;
            }
            // 初始化 或者 有更符合的小组 即替换
            if (targetGroup == null || targetGroup.getValue() < entry.getValue()) {
                targetGroup = entry;
            }
 }

但是，我们可以看到，由于现实场景，小组内人数是有限制的，且小组内人数为非负整数。于是，可以推理出，当小组人数达到 GROUP_STU_NUM - 1 时，即可退出。因此代码可优化为如下。

        for (Map.Entry<String, Integer> entry : groupList.entrySet()) {
            // 组内已满
            if (entry.getValue() >= GroupEnum.GROUP_STU_NUM.getValue()) {
                continue;
            }
            // 初始化 或者 有更符合的小组 即替换
            if (targetGroup == null || targetGroup.getValue() < entry.getValue()) {
                targetGroup = entry;
            }
            // 剪枝
            if (targetGroup.getValue() == GroupEnum.GROUP_STU_NUM.getValue() - 1) {
                break;
            }
        }

• 更换小组
  用户更换小组则更简单，我们只需要把用户从 S 组更换至 T 组即可。
  但是我们需要注意以下几个问题。

// 检测签到
if(!checkUserSign(uid)) {
    return;
}
// 这里还要检测该用户是否可以更换小组

// 判断小组已满
if(T.getNum() >= GROUP_STU_NUM) {
   return;
}

groupChange(uid, S, T);

• 组分配优化
  小组在开始活动时，肯定有许多的不满小组。需要将不满的小组进行合并。
  1.1 小组分配优化，第一步先进行小组的合并-即将一个小组完全并入另一个小组
  1.2 小组分配优化 如果合并至没有小组可以完全合并时，则进行小组的拆分

// 1 获取需分配小组 - 即不满或不空的小组
List<Group> mergeList = getMergeList();

// 2 对需分配小组进行排序 - 按照组人数排倒序
sort(mergeList, DESC);

// 3. 首尾进行尝试合并
int start = 0 , end = mergeList.size() - 1;
while(start < end) {
      // 合并至 组人数超出时 将预合并组向前移动 至下一个人数少的预合并组
      if (mergeList[start].num + mergeList[end].num > GROUP_STU_NUM) {
            start++;
      }
      // 可以合并 将end 组合并至 start组
      mergeGroup(mergeList[start], mergeList[end]);
      // end 组已合并 向前移动
      end--;
}

// 4. 进行拆分小组

• 主要问题
  1.1 逻辑太过复杂
  虽然上面写的比较简单，但是对于一个签到接口来说，逻辑还是相对过于复杂了(还有其他的前置逻辑)，如果同步执行，那么必然不能应对逐渐上升的业务。
  1.2 并发问题
  上面所有的代码都是‘假定’只有一个进程进行处理。但是如上面代码所展示，无论签到/换组 还是小组调优都有着大量的写入操作。而一旦有大量并发写操作，那么必然会导致数据错乱。
  比如在用户签到 至A组，另一些用户 同时换组至 A组，则在读取A组数据时，可能A组有4人，但是当写入时，已经由多个用户更换至A组，则A组人数会超出。
  处理方式
  1.1 加锁
  1.2 队列 写逻辑串行