(面试)场景方案：如何设计O(1)时间复杂度的抽奖算法？

小傅哥

发布于 2024-08-29 17:43:37

1240

发布于 2024-08-29 17:43:37

文章被收录于专栏：CodeGuide | 程序员编码指南

作者：小傅哥博客：https://bugstack.cn

❝沉淀、分享、成长，让自己和他人都能有所收获！😜 ❞

大家好，我是技术UP主小傅哥。

可能不少伙伴都看过网上的抽奖类算法，但大部分都是生成个概率做 for 循环就完事了。但这样的东西只能算做demo，在实际的高并发生产级别项目中，根本不会这么简单的 for 循环。为什么呢？那除了这样还有什么方法吗？

面试官是越来越喜欢问场景方案了吗？

是的，以前可能问问八股文就完事了。但我们面试中发现很多技术点 HashMap、ThreadLocal、Redis 背的66的，但换个实际场景使用或者基于这些知识点的技术迁移做同类场景方案设计时，又完全没有概念。

所以，现在的面试官一面扫盲点八股文后，接下来就很喜欢拿真实场景去问，问那些细节，什么场景的什么问题、你是怎么设计的、又是怎么实现的、最后的结果/效果怎么样。

好啦，接下来小傅哥就来介绍下今天的这个场景问题如何设计，后续也会陆续的系列分享此类实战内容。

文末有加入学习方式，可以获得整套课程的；视频、文档、代码、面试题、简历模板等。

一、场景介绍

在京东商城APP购物后，有一个抽奖页面。这个抽奖的并发体量是非常大的，所有支付完成的用户，都可以参与到抽奖。但这么大规模的用户参与抽奖，从来也不会感觉有卡顿。它是怎么设计的呢？同类的这样的抽奖还有很多，包括；拼多多、淘宝、滴滴出行、美团，各种让你抽奖领券的地方。

看着很简单的抽奖，但做起来一点也不容易！

二、方案设计

所有的抽奖，只要不是糊弄人的，一定会有概率的配置（假的抽奖就是直接给你写死一个中奖结果）。这些概率是为了抽奖过程中通过产生的随时值进行抽奖。

如图，8个奖品概率。1个0.79、6个0.03，1个0.0003，总概率和不是1。对于这样的一个可设定不同范围值的抽奖，怎么做研发方案呢？怎么让做的这个方案可以支撑不同概率类型的大规模抽奖呢？

在实际生产场景中，运营的奖品配置概率有时候百分位或者千分位，也就是小数点后有几个0，但有时候也有需要配置到万分位或者百万分位，来降低大奖的奖品概率配置。

对于不同概率的抽奖配置，我们也有为它设计出不同的抽奖算法策略。让万分位以下的这类频繁配置的，走O(1)时间复杂度。而对于超过万分位的，可以考虑循环对比，但在循环对比的中，还要根据奖品的数量设定出不同的计算模型。如；O(n)、O(logn) 如图；

算法1；是O(1) 时间复杂度算法，在抽奖活动开启时，将奖品概率预热到本地(Guava)/Redis。如，10%的概率，可以是占了1~10的数字区间，对应奖品A。11~15 对应奖品B。那么在抽奖的时候，直接用生成的随机数通过对 map 进行 get 即可。
算法2；是O(n) ~ O(logn)算法，当奖品概率非常大的时候，达到几十万以上，我们就适合在本地或者 Redis 来初始化这些数据存到 Map 里了。那么这个时候就要把奖品概率，拆分为一个个有限定范围的格子区间。比如 1~7900代表一个奖品、7901~8200代表另外一个奖品，把这些数据存储到 Map<Map<Integer,Integer>,Integer> 在抽奖的时候通过产生的随机值来与这些范围区间依次进行对比。那么为了更好的优化抽奖算法，可以的分别对<=8的进行for循环、<=16的二分查找、>16的进行多线程计算。因为数量很小开启多线程的资源也是一种消耗。

基于这样的设计，我们就可以编码实现了。而且要考虑下，这里的编码设计，便于后续扩展。

三、编码实现

1. 设计模式

在这种场景的编码中，千万不能大面积的写流水账。除非你说下个月不干了！所以要通过设计模式解耦代码流程，把职责分离，这样我们在迭代的时候才能更好的找到每一块功能的实现边界。让迭代需求变得容易一些，也减少一些错误发生。

如图，左侧通过接口、抽象类的模板方法，定义抽奖装配和抽奖算法的执行过程。之后有抽奖策略算法实现类完成功能细节。
如图，右侧通过接口和抽象类，设计抽奖算法标准结构。之后分别实现O(1)、O(Logn)代码实现流程。

2. 核心代码

在整个项目的 strategy 策略模块下抽奖算法中实现不同的逻辑。

2.1 策略装配、

public interface IStrategyArmory {

    /**
     * 装配抽奖策略配置「触发的时机可以为活动审核通过后进行调用」
     *
     * @param strategyId 策略ID
     * @return 装配结果
     */
    boolean assembleLotteryStrategy(Long strategyId);
  
}

public interface IStrategyDispatch {

    /**
     * 获取抽奖策略装配的随机结果
     *
     * @param strategyId 策略ID
     * @return 抽奖结果
     */
    Integer getRandomAwardId(Long strategyId);
  
}  

@Override
public boolean assembleLotteryStrategy(Long strategyId) {
    // 1. 查询策略配置
    List<StrategyAwardEntity> strategyAwardEntities = repository.queryStrategyAwardList(strategyId);
    // 2. 缓存奖品库存【用于decr扣减库存使用】
    for (StrategyAwardEntity strategyAward : strategyAwardEntities) {
        Integer awardId = strategyAward.getAwardId();
        Integer awardCount = strategyAward.getAwardCountSurplus();
        cacheStrategyAwardCount(strategyId, awardId, awardCount);
    }
    // 3.1 默认装配配置【全量抽奖概率】
    armoryAlgorithm(String.valueOf(strategyId), strategyAwardEntities);
    // 3.2 权重策略配置 - 适用于 rule_weight 权重规则配置【4000:102,103,104,105 5000:102,103,104,105,106,107 6000:102,103,104,105,106,107,108,109】
    StrategyEntity strategyEntity = repository.queryStrategyEntityByStrategyId(strategyId);
    String ruleWeight = strategyEntity.getRuleWeight();
    if (null == ruleWeight) return true;
    StrategyRuleEntity strategyRuleEntity = repository.queryStrategyRule(strategyId, ruleWeight);
    // 业务异常，策略规则中 rule_weight 权重规则已适用但未配置
    if (null == strategyRuleEntity) {
        throw new AppException(ResponseCode.STRATEGY_RULE_WEIGHT_IS_NULL.getCode(), ResponseCode.STRATEGY_RULE_WEIGHT_IS_NULL.getInfo());
    }
    Map<String, List<Integer>> ruleWeightValueMap = strategyRuleEntity.getRuleWeightValues();
    for (String key : ruleWeightValueMap.keySet()) {
        List<Integer> ruleWeightValues = ruleWeightValueMap.get(key);
        ArrayList<StrategyAwardEntity> strategyAwardEntitiesClone = new ArrayList<>(strategyAwardEntities);
        strategyAwardEntitiesClone.removeIf(entity -> !ruleWeightValues.contains(entity.getAwardId()));
        armoryAlgorithm(String.valueOf(strategyId).concat(Constants.UNDERLINE).concat(key), strategyAwardEntitiesClone);
    }
    return true;
}

assembleLotteryStrategy 从数据库查询抽奖概率配置之后进行装配。（权重是另外一个设计，满足达到不同范围后可以抽奖到指定范围奖品）
armoryAlgorithm 是一个抽象方法，放到 StrategyArmoryDispatch 子类实现。

2.2 抽奖算法

public interface IAlgorithm {

    void armoryAlgorithm(String key, List<StrategyAwardEntity> strategyAwardEntities, BigDecimal rateRange);

    Integer dispatchAlgorithm(String key);

}

定义算法接口，分为装配和抽奖。O(1)、O(logn) 时间复杂度的算法，装配和抽奖的实现都是不同的。

2.2.1 O(1) 时间复杂度

@Slf4j
@Component("o1Algorithm")
public class O1Algorithm extends AbstractAlgorithm {

    @Override
    public void armoryAlgorithm(String key, List<StrategyAwardEntity> strategyAwardEntities, BigDecimal rateRange) {
        log.info("抽奖算法 O(1) 装配 key:{}", key);
        // 1. 生成策略奖品概率查找表「这里指需要在list集合中，存放上对应的奖品占位即可，占位越多等于概率越高」
        List<Integer> strategyAwardSearchRateTables = new ArrayList<>(rateRange.intValue());
        for (StrategyAwardEntity strategyAward : strategyAwardEntities) {
            Integer awardId = strategyAward.getAwardId();
            BigDecimal awardRate = strategyAward.getAwardRate();
            // 计算出每个概率值需要存放到查找表的数量，循环填充
            for (int i = 0; i < rateRange.multiply(awardRate).intValue(); i++) {
                strategyAwardSearchRateTables.add(awardId);
            }
        }

        // 2. 对存储的奖品进行乱序操作
        Collections.shuffle(strategyAwardSearchRateTables);

        // 3. 生成出Map集合，key值，对应的就是后续的概率值。通过概率来获得对应的奖品ID
        Map<Integer, Integer> shuffleStrategyAwardSearchRateTable = new LinkedHashMap<>();
        for (int i = 0; i < strategyAwardSearchRateTables.size(); i++) {
            shuffleStrategyAwardSearchRateTable.put(i, strategyAwardSearchRateTables.get(i));
        }

        // 4. 存放到 Redis
        repository.storeStrategyAwardSearchRateTable(key, shuffleStrategyAwardSearchRateTable.size(), shuffleStrategyAwardSearchRateTable);
    }

    @Override
    public Integer dispatchAlgorithm(String key) {
        log.info("抽奖算法 O(1) 抽奖计算 key:{}", key);
        // 分布式部署下，不一定为当前应用做的策略装配。也就是值不一定会保存到本应用，而是分布式应用，所以需要从 Redis 中获取。
        int rateRange = repository.getRateRange(key);
        // 通过生成的随机值，获取概率值奖品查找表的结果
        return repository.getStrategyAwardAssemble(key, secureRandom.nextInt(rateRange));
    }

}

2.2.2 O(logn) 时间复杂度

@Slf4j
@Component("oLogNAlgorithm")
public class OLogNAlgorithm extends AbstractAlgorithm {

    @Resource
    private ThreadPoolExecutor threadPoolExecutor;

    /**
     * 预热活动概率值
     * 如概率值为；3、4、2、9，存储为 [1~3]、[4~7]、[8~9]、[10~18]，抽奖时，for循环匹配。
     *
     * @param key                   为策略ID、权重ID
     * @param strategyAwardEntities 对应的奖品概率
     */
    @Override
    public void armoryAlgorithm(String key, List<StrategyAwardEntity> strategyAwardEntities, BigDecimal rateRange) {
        log.info("抽奖算法 OLog(n) 装配 key:{}", key);
        int from = 1;
        int to = 0;

        Map<Map<Integer, Integer>, Integer> table = new HashMap<>();
        for (StrategyAwardEntity strategyAward : strategyAwardEntities) {
            Integer awardId = strategyAward.getAwardId();
            BigDecimal awardRate = strategyAward.getAwardRate();
            to += rateRange.multiply(awardRate).intValue();

            Map<Integer, Integer> ft = new HashMap<>();
            ft.put(from, to);
            table.put(ft, awardId);
            from = to + 1;
        }

        repository.storeStrategyAwardSearchRateTable(key, to, table);
    }

    @Override
    public Integer dispatchAlgorithm(String key) {
        int rateRange = repository.getRateRange(key);
        Map<Map<String, Integer>, Integer> table = repository.getMap(key);
        // 小于等于8 for循环、小于等于16 二分查找、更多检索走多线程
        if (table.size() <= 8) {
            log.info("抽奖算法 OLog(n) 抽奖计算（循环） key:{}", key);
            return forSearch(rateRange, table);
        } else if (table.size() <= 16) {
            log.info("抽奖算法 OLog(n) 抽奖计算（二分） key:{}", key);
            return binarySearch(rateRange, table);
        } else {
            log.info("抽奖算法 OLog(n) 抽奖计算（多线程） key:{}", key);
            return threadSearch(rateRange, table);
        }
    }

    private Integer forSearch(int rateRange, Map<Map<String, Integer>, Integer> table) {
        Integer result = null;
        for (Map.Entry<Map<String, Integer>, Integer> entry : table.entrySet()) {
            Map<String, Integer> rangeMap = entry.getKey();

            for (Map.Entry<String, Integer> range : rangeMap.entrySet()) {
                int start = Integer.parseInt(range.getKey());
                int end = range.getValue();

                if (rateRange >= start && rateRange <= end) {
                    result = entry.getValue();
                    break;
                }
            }

            if (result != null) {
                break;
            }
        }

        return result;
    }

    private Integer binarySearch(int rateRange, Map<Map<String, Integer>, Integer> table) {
        List<Map.Entry<Map<String, Integer>, Integer>> entries = new ArrayList<>(table.entrySet());
        entries.sort(Comparator.comparingInt(e -> Integer.parseInt(e.getKey().keySet().iterator().next())));

        int left = 0;
        int right = entries.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            Map.Entry<Map<String, Integer>, Integer> entry = entries.get(mid);
            Map<String, Integer> rangeMap = entry.getKey();
            Map.Entry<String, Integer> range = rangeMap.entrySet().iterator().next();

            int start = Integer.parseInt(range.getKey());
            int end = range.getValue();

            if (rateRange < start) {
                right = mid - 1;
            } else if (rateRange > end) {
                left = mid + 1;
            } else {
                return entry.getValue();
            }
        }

        return null;
    }

    private Integer threadSearch(int rateRange, Map<Map<String, Integer>, Integer> table) {
        List<CompletableFuture<Map.Entry<Map<String, Integer>, Integer>>> futures = table.entrySet().stream()
                .map(entry -> CompletableFuture.supplyAsync(() -> {
                    Map<String, Integer> rangeMap = entry.getKey();
                    for (Map.Entry<String, Integer> rangeEntry : rangeMap.entrySet()) {
                        int start = Integer.parseInt(rangeEntry.getKey());
                        int end = rangeEntry.getValue();
                        if (rateRange >= start && rateRange <= end) {
                            return entry;
                        }
                    }
                    return null;
                }, threadPoolExecutor))
                .collect(Collectors.toList());

        CompletableFuture<Void> allFutures = CompletableFuture.allOf(futures.toArray(new CompletableFuture[0]));

        try {
            // 等待所有异步任务完成，同时返回第一个匹配的结果
            allFutures.join();
            for (CompletableFuture<Map.Entry<Map<String, Integer>, Integer>> future : futures) {
                Map.Entry<Map<String, Integer>, Integer> result = future.getNow(null);
                if (result != null) {
                    return result.getValue();
                }
            }
        } catch (CompletionException e) {
            e.printStackTrace();
        }

        return null;
    }

}

forSearch 循环查找 - 一些配置低于8的，循环查找的速度也很快。
binarySearch 二分查找
threadSearch 多线程计算

3. 调用测试

@Before
public void test_strategyArmory() {
    // 动态Mock值操作，可用于调整选择哪个算法
    ReflectionTestUtils.setField(strategyArmory, "ALGORITHM_THRESHOLD_VALUE", 10);
    boolean success = strategyArmory.assembleLotteryStrategy(100006L);
    log.info("测试结果：{}", success);
}

/**
 * 从装配的策略中随机获取奖品ID值
 */
@Test
public void test_getRandomAwardId() {
    log.info("测试结果：{} - 奖品ID值", strategyDispatch.getRandomAwardId(100006L));
}

24-08-24.13:44:22.873 [main            ] INFO  O1Algorithm            - 抽奖算法 O(1) 装配 key:100006
24-08-24.13:44:27.570 [main            ] INFO  O1Algorithm            - 抽奖算法 O(1) 装配 key:100006_70:106,107
24-08-24.13:44:30.247 [main            ] INFO  O1Algorithm            - 抽奖算法 O(1) 装配 key:100006_10:102,103
24-08-24.13:44:32.489 [main            ] INFO  O1Algorithm            - 抽奖算法 O(1) 装配 key:100006_1000:104,105
24-08-24.13:44:32.521 [main            ] INFO  StrategyArmoryDispatchTest - 测试结果：true
24-08-24.13:44:41.457 [main            ] INFO  O1Algorithm            - 抽奖算法 O(1) 抽奖计算 key:100006
24-08-24.13:44:41.476 [main            ] INFO  StrategyArmoryDispatchTest - 测试结果：106 - 奖品ID值

两个测试案例，分别装配概率和执行抽奖。
ALGORITHM_THRESHOLD_VALUE 值mock的不同，可以走到O(1)、O(logn)两种算法。

四、加入学习

在实际的场景编码实现中还有非常多的内容需要学习，比如；分布式系统怎么架构、分布式技术栈怎么在项目中使用、分布式任务调度多实例怎么做锁、数据量大了怎么分库分表、分库分表怎么同步ES、同步ES怎么在系统中配置双数据源、部署的系统怎么配置监控，这样一套系统怎么做DDD架构和设计模式的运用呢？🤔

这些内容都在小傅哥的星球「码农会锁」中有实战项目可以学习到，这些项目不是拼凑的，也不是CRUD的demo，而是真实互联网场景的真实架构项目。加入可以学习到非常多的内容。

小傅哥的星球「码农会锁」有非常多的实战项目，包括业务的5个；大营销（大课）、OpenAI 大模型应用、Lottery、IM、AI 问答助手。组件的7个；OpenAI 代码评审、BCP 透视业务监控、动态线程池、支付SDK设计和开发、API网关、SpringBoot Starter、IDEA Plugin 插件开发。