我司的面试题目公开诚聘 Java 工程师入坑

[jiansihun]

在抽奖场景中，最高峰值为 2w QPS，运营部现有 20000 部 iPhone 手机，决定每 100 人随机抽中一台，覆盖人数 200w 人，送完即止。请如何技术上如何实现该机制。

如有能回答上述问题的 Java 工程师请考虑一下我司广州工作： https://www.lagou.com/gongsi/j29385.html，或者站内私我简历。

[woahishui]

创建一个数据表(可以用数据库或者 nosql)，记录用户的的抽奖记录，每 100 个人分一个标识，使用随机函数标识查询到的记录作为中奖着，这样可以吗

[NewDraw]

@woahishui


缓存+限流+消息队列，200wQPS 都没问题。

[mooncakejs]

2w QPS redis 就可以撑住，hset 用户 id 去重，抽奖形式就很多了，increment value % 100，pull list，或者干脆队列化单线程抽奖。

[woahishui]

呵呵

[woahishui]

都行，方案应该都可行吧

[zyue]

按奖品数量分为 20000 场，对用户 id hash 落到 1-20000 中的某个场次，检查缓存，看对应场次是否因有人抽中而结束，结束的话直接返回未抽中，没有的话执行抽奖等逻辑，可以同步抽取，也可以走 mq 异步处理。

[zz656565]

这点羊毛够黑产薅吗？

[woahishui]

不过我倒觉得这个想法有问题，那么快就完了容易导致服务器压力突然增大，不如让大家先报名，然后在一周后统一抽奖，这样关注度高，时间长，而且还能降低技术难度，降低技术难度意味着可以省去 5000 部手机的钱，相当于只要 15000 部就够了。这是我的建议

[lihongming]

200W 用户总不能是一下来的吧？何不换个姿势，把抽奖过程放到用户入库的过程中？

比如分个随机数给它，根据这个随机数把用户放入一个长度为 2W 的数组，数小的顶走数大的，最后剩下的都是中奖的。

[woahishui]

参加抽奖是参加抽奖，不要将抽奖混合在一起，我是这么想的

[matrix1986]

消息队列，削峰不二之选

[LuciferGo]

刚好前两天在掘金看了这个问题，https://juejin.im/post/5ce1975af265da1bd42450b5

[9684xtpa]

@NewDraw #2
基础之上只要保证，如何覆盖面达到 200W，毕竟是 100:1，这个利用 redis 的 incr 和缓存也能搞定，每个购买的人分配一个数值 ID，每 id%100=0 的人具有购买资格。

[Leigg]

记得奖品抽完后告诉前端请求不要发到后端。

[qwerthhusn]

当然是内定啊，a 这个是老板的意思。。。。

[vincel]

这种场景小米很有发言权，直接前端砍掉 2/3 的请求。

[myself659]

套方案吗？

[horace1117]

不是应该直接 redis 缓存未抽中就行了嘛，抽奖什么的当然是内定

[cyndihuifei]

随机拒绝 1 / 200 的概率，让用户进行后面的请求，直接削减大部分请求

[CRVV]

1. 给登录用户一个 jwt，客户端在发的请求的一个 HTTP header 里带上用户 id
2. 在 load balancer 上，拿用户 id 来决定路由，让同一个用户的请求只会被路由到同一台机器上
3. 接到请求的机器验证 jwt，并且记下来发过请求的用户，如果这个用户已经发过请求就直接返回
4. 随机决定 1% 的用户中奖，然后把数据库上把剩余奖品的数量 atomic x--，如果 x>0 就给用户返回中奖了

数据库上只有 200 QPS 的请求，只要是支持 atomic 操作的数据库应该都能用
其它的部分互不依赖可以无限加机器

没做过类似的东西，大概想了一下这样应该能用

[c4f36e5766583218]

我看成要送手机，结果只是个题目。

[petelin]

这个题我觉得没描述好 应该改成需要用户实时看到结果
要不然做成批次（够 100 人开一次奖）或者 200w 人都参与完在开奖就太简单（技术上太简单了 我会认为这公司很水）

@woahishui 每秒就 10 个人抽奖.难道让他们等 10 秒才知道中没中？
@NewDraw 200w QPS 过来 服务端延迟多少？ 分布式机器怎么从队列取数据决定谁中奖？
@CRVV 这个思路不错 不过为什么要路由到同一台机器？那台机器挂了呢 扩容了呢？ 抽奖结束直接记录信息是不是更好 还有这个算法太简单了 可能抽不到 200w 所以要参考微信红包算法

[murmur]

如果是微博抽奖，就丢弃掉所有请求，反正这种东西一定是虚假抽奖

[577322753]

开个线程，一直阻塞到够 200 万人，不够就 sleep 一会，然后把这两百万人存到 list 里，存够了遍历 list，i %100==0,那 i 这个 b 就中奖了，让我们恭喜这 20000 个 b。贵公司缺 cto 吗？😬

[largecat]

上面答内定的同学你可以发简历过去了，

[woahishui]

@petelin 我后面的回复是从活动的角度想的，并非从技术，如果活动很快就结束了，感觉活动效果可能打折比较多，如果搞成彩票类型的感觉时间长，用户关注度高，更适合推广

[wpzero]

其实我感觉就只需要事先生成获奖的 2 万列表存在 redis 的 set 好了,每一个 request 的电话号产生一个 unique key,用 redis 来检测是否已经抽过，incr pk，然后得到的值是否在 set 中，在就中奖了。redis 这些操作应该都是 10 万每秒级别，如果你认为还不够 OK，多个 redis,用电话号 hash mod 来 map.至于服务器这种没有 rds 的操作用 nodejs golang java 几台服务器撑一下都可以。消息队列来解题也很合适。

[lychnis]

要什么自行车，蓄水池算法。

其实楼主在筛选你们会不会算法和数据结构

[Kylinsun]

@woahishui

[CRVV]

@petelin

> 为什么要路由到同一台机器？

如果同一个用户的请求会被路由到不同的机器上，就需要一个中心的数据库来记录哪些用户发过请求，这个数据库会成为瓶颈

> 那台机器挂了呢 扩容了呢？

这里的点是按照用户的 id 来分请求，减少后面每一台机器上的负担
后面的“一台机器”可以不是一台机器，你改成若干台机器加 Redis， 是一样的
这个若干台机器加 Redis 的东西可以继续扩容，但是 load balancer 上的后端不能增加
另外楼主给定了请求数量的上限，在这个题目的范围里不需要考虑扩容

> 还有这个算法太简单了 可能抽不到 200w

能抽到多少数字和算法简不简单没有关系
如果你觉得不行，请直接指出来哪里有问题

[larve]

1. 库存控制：防止超发
redis 自减或者 redis 队列出栈都能做到
2. 随机用户
200w 用户随机：若是同一场抽奖，有两百万个用户参与，可 redis 通过一个 key 自增，每自增 100 则对应用户是抽中的，抽中的用户再进入后续入库操作即可，最高时 2w redis QPS 应该是可以的，真正能入库的数据也不多

[zc1249274251]

1、限流
2、利用 redis 做自增或者自减操作 提交请求到队列
3、创建有界队列，如果队列满了，直接拒收请求
4、让队列里边的请求 mysql 来做最终一致性

[jiansihun]

@petelin 考虑一下我司的的位置不。#这个题我觉得没描述好 应该改成需要用户实时看到结果# 这个问题要看到最高峰值 2w QPS，也就是 QPS 是 0 - 2w，另外要注意随机字眼，以及仅有的 2k 部手机，方案并不一定都可以实时（我有可能也不对），确实需要从用户端体验开始考虑的起。当然大力出奇迹的答复在上面的答案已经有了。