背景
从去年开始到现在，参与一个新业务的研发。其中一个模块经过了多次优化升级，因此总结于此。
业务场景可以简化为，用户参与活动需要签到，活动的形式为多人一组，因此业务场景为在固定可签到时间内，将用户划分到最‘适合’的小组。
抽象
- 业务高峰期 大概有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 队列 写逻辑串行
网友评论