首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
• 换工作是一件经过深思熟虑的严肃事情
• 频繁换工作是 loser 做的事情
• 公司应该提供给员工尽可能好的条件
• 这里不欢迎苦大仇深的公司
• 原则上这里不欢迎猎头发帖,除非是懂技术的猎头
• 如果你自己从来没有从期权上赚过钱,就不要在招聘时强调期权
• 招聘时请尽量给出薪酬范围
• 求职时请附上自己的薪酬要求
• 说话前经过足够的思考是好习惯
• 上传一个有意义的头像会更体现你们公司的品牌和诚意
• 请不要在 1 天的时间内在酷工作节点发布超过 3 个主题
• 在不同节点下发布内容相同的主题这种行为不科学
宝塔
V2EX  ›  酷工作

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

  •  
  •   jiansihun · 181 天前 · 4592 次点击
    这是一个创建于 181 天前的主题,其中的信息可能已经有所发展或是发生改变。
    在抽奖场景中,最高峰值为 2w QPS,运营部现有 20000 部 iPhone 手机,决定每 100 人随机抽中一台,覆盖人数 200w 人,送完即止。请如何技术上如何实现该机制。

    如有能回答上述问题的 Java 工程师请考虑一下我司广州工作: https://www.lagou.com/gongsi/j29385.html,或者站内私我简历。
    33 回复  |  直到 2019-05-27 09:43:54 +08:00
        1
    woahishui   181 天前 via Android
    创建一个数据表(可以用数据库或者 nosql),记录用户的的抽奖记录,每 100 个人分一个标识,使用随机函数标识查询到的记录作为中奖着,这样可以吗
        2
    NewDraw   181 天前 via Android
    @woahishui


    缓存+限流+消息队列,200wQPS 都没问题。
        3
    mooncakejs   181 天前
    2w QPS redis 就可以撑住,hset 用户 id 去重,抽奖形式就很多了,increment value % 100,pull list,或者干脆队列化单线程抽奖。
        4
    woahishui   181 天前 via Android
    呵呵
        5
    woahishui   181 天前 via Android
    都行,方案应该都可行吧
        6
    zyue   181 天前
    按奖品数量分为 20000 场,对用户 id hash 落到 1-20000 中的某个场次,检查缓存,看对应场次是否因有人抽中而结束,结束的话直接返回未抽中,没有的话执行抽奖等逻辑,可以同步抽取,也可以走 mq 异步处理。
        7
    zz656565   181 天前
    这点羊毛够黑产薅吗?
        8
    woahishui   181 天前 via Android
    不过我倒觉得这个想法有问题,那么快就完了容易导致服务器压力突然增大,不如让大家先报名,然后在一周后统一抽奖,这样关注度高,时间长,而且还能降低技术难度,降低技术难度意味着可以省去 5000 部手机的钱,相当于只要 15000 部就够了。这是我的建议
        9
    lihongming   181 天前 via iPhone
    200W 用户总不能是一下来的吧?何不换个姿势,把抽奖过程放到用户入库的过程中?

    比如分个随机数给它,根据这个随机数把用户放入一个长度为 2W 的数组,数小的顶走数大的,最后剩下的都是中奖的。
        10
    woahishui   181 天前 via Android
    参加抽奖是参加抽奖,不要将抽奖混合在一起,我是这么想的
        11
    matrix1986   181 天前
    消息队列,削峰不二之选
        12
    LuciferGo   181 天前
    刚好前两天在掘金看了这个问题,https://juejin.im/post/5ce1975af265da1bd42450b5
        13
    9684xtpa   181 天前
    @NewDraw #2
    基础之上只要保证,如何覆盖面达到 200W,毕竟是 100:1,这个利用 redis 的 incr 和缓存也能搞定,每个购买的人分配一个数值 ID,每 id%100=0 的人具有购买资格。
        14
    Leigg   181 天前 via iPhone
    记得奖品抽完后告诉前端请求不要发到后端。
        15
    qwerthhusn   181 天前
    当然是内定啊,a 这个是老板的意思。。。。
        16
    vincel   181 天前
    这种场景小米很有发言权,直接前端砍掉 2/3 的请求。
        17
    myself659   181 天前
    套方案吗?
        18
    horace1117   181 天前
    不是应该直接 redis 缓存未抽中就行了嘛,抽奖什么的当然是内定
        19
    cyndihuifei   181 天前
    随机拒绝 1 / 200 的概率,让用户进行后面的请求,直接削减大部分请求
        20
    CRVV   181 天前
    1. 给登录用户一个 jwt,客户端在发的请求的一个 HTTP header 里带上用户 id
    2. 在 load balancer 上,拿用户 id 来决定路由,让同一个用户的请求只会被路由到同一台机器上
    3. 接到请求的机器验证 jwt,并且记下来发过请求的用户,如果这个用户已经发过请求就直接返回
    4. 随机决定 1% 的用户中奖,然后把数据库上把剩余奖品的数量 atomic x--,如果 x>0 就给用户返回中奖了

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

    没做过类似的东西,大概想了一下这样应该能用
        21
    c4f36e5766583218   181 天前
    我看成要送手机,结果只是个题目。
        22
    petelin   181 天前 via iPhone
    这个题我觉得没描述好 应该改成需要用户实时看到结果
    要不然做成批次(够 100 人开一次奖)或者 200w 人都参与完在开奖就太简单(技术上太简单了 我会认为这公司很水)

    @woahishui 每秒就 10 个人抽奖.难道让他们等 10 秒才知道中没中?
    @NewDraw 200w QPS 过来 服务端延迟多少? 分布式机器怎么从队列取数据决定谁中奖?
    @CRVV 这个思路不错 不过为什么要路由到同一台机器?那台机器挂了呢 扩容了呢? 抽奖结束直接记录信息是不是更好 还有这个算法太简单了 可能抽不到 200w 所以要参考微信红包算法
        23
    murmur   181 天前
    如果是微博抽奖,就丢弃掉所有请求,反正这种东西一定是虚假抽奖
        24
    577322753   181 天前 via Android
    开个线程,一直阻塞到够 200 万人,不够就 sleep 一会,然后把这两百万人存到 list 里,存够了遍历 list,i %100==0,那 i 这个 b 就中奖了,让我们恭喜这 20000 个 b。贵公司缺 cto 吗?😬
        25
    largecat   181 天前 via Android
    上面答内定的同学你可以发简历过去了,
        26
    woahishui   181 天前 via Android
    @petelin 我后面的回复是从活动的角度想的,并非从技术,如果活动很快就结束了,感觉活动效果可能打折比较多,如果搞成彩票类型的感觉时间长,用户关注度高,更适合推广
        27
    wpzero   181 天前 via iPhone
    其实我感觉就只需要事先生成获奖的 2 万列表存在 redis 的 set 好了,每一个 request 的电话号产生一个 unique key,用 redis 来检测是否已经抽过,incr pk,然后得到的值是否在 set 中,在就中奖了。redis 这些操作应该都是 10 万每秒级别,如果你认为还不够 OK,多个 redis,用电话号 hash mod 来 map.至于服务器这种没有 rds 的操作用 nodejs golang java 几台服务器撑一下都可以。消息队列来解题也很合适。
        28
    lychnis   181 天前 via Android
    要什么自行车,蓄水池算法。

    其实楼主在筛选你们会不会算法和数据结构
        29
    Kylinsun   181 天前 via iPhone
        30
    CRVV   180 天前
    @petelin

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

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

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

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

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

    能抽到多少数字和算法简不简单没有关系
    如果你觉得不行,请直接指出来哪里有问题
        31
    larve   179 天前
    1. 库存控制:防止超发
    redis 自减或者 redis 队列出栈都能做到
    2. 随机用户
    200w 用户随机:若是同一场抽奖,有两百万个用户参与,可 redis 通过一个 key 自增,每自增 100 则对应用户是抽中的,抽中的用户再进入后续入库操作即可,最高时 2w redis QPS 应该是可以的,真正能入库的数据也不多
        32
    zc1249274251   179 天前
    1、限流
    2、利用 redis 做自增或者自减操作 提交请求到队列
    3、创建有界队列,如果队列满了,直接拒收请求
    4、让队列里边的请求 mysql 来做最终一致性
        33
    jiansihun   179 天前
    @petelin 考虑一下我司的的位置不。#这个题我觉得没描述好 应该改成需要用户实时看到结果# 这个问题要看到最高峰值 2w QPS,也就是 QPS 是 0 - 2w,另外要注意随机字眼,以及仅有的 2k 部手机,方案并不一定都可以实时(我有可能也不对),确实需要从用户端体验开始考虑的起。当然大力出奇迹的答复在上面的答案已经有了。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4239 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 27ms · UTC 03:12 · PVG 11:12 · LAX 19:12 · JFK 22:12
    ♥ Do have faith in what you're doing.