遇到一个问题,需要从预插入数据的表,随机找一条,分配给一个用户,求一个简洁的方案 - V2EX
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
请不要在回答技术问题时复制粘贴 AI 生成的内容
looplj
V2EX    程序员

遇到一个问题,需要从预插入数据的表,随机找一条,分配给一个用户,求一个简洁的方案

  •  
  •   looplj
    looplj 2022-03-04 15:05:53 +08:00 3687 次点击
    这是一个创建于 1389 天前的主题,其中的信息可能已经有所发展或是发生改变。

    背景:

    需求:

    预先创建一批 coupons ,存到 coupons 表里面,然后将这些 coupons 发给用户,要求是一个 coupon 只能发给一个用户,不能重复发放。

    分配性能越高越好。

    现状:

    1. coupons 分配服务有多实例
    2. 其他服务请求 coupons 分配服务获取 coupon

    当前方案:

    两个步骤:

    1. 随机读一个 coupon
    2. 分配 coupon 使用数据库事务+乐观锁,保证不重复分配

    所以优化重点是:尽量少访问数据库;随机读到的 coupon 尽量不要冲突。

    优化方案:

    预读取 100 个 coupons 到内存,分配的时候优先从缓存中读取,缓存没有从数据库再读一批。

    为了解决多实例读取冲突问题,在 redis 记录一个 coupon id 作为 cursor ,每读一批,将 redis 中的 cursor 更新为最新的,下一批读取的是,id > cursor 的 coupons 。

    redis 可以做到 cas 更新 cursor ,可以保证读取的每一批都不会重复。

    cursor 也是 30min 失效,下一次继续从 0 开始,就算读取了一批,但是没有分配,然后挂了,被跳过的 coupons 还是会有机会读到的。

    求教

    因为公司大佬觉得引入 redis ,方案比较复杂,不好维护;想跟大家请教下,看有没有什么更简洁的方案,不用引入数据库以外依赖

    第 1 条附言    2022-03-04 17:13:39 +08:00
    附加一条现状
    1. 辣鸡 spanner 没有 random 函数,做不到运行时读取随机
    第 2 条附言    2022-03-04 20:19:14 +08:00
    暂定方案

    1. 创建的 coupon 不落数据库,直接 rpush 到 redis queue
    2. 分配的时候,直接 lpop 一条数据
    3. 分配的时候用 coupon id 做唯一索引控制,保证不会重复分配。
    56 条回复    2022-03-06 14:14:33 +08:00
    sagaxu
        1
    sagaxu  
       2022-03-04 15:14:02 +08:00 via Android   1
    生成时随机,分配时按顺序
    looplj
        2
    looplj  
    OP
       2022-03-04 15:22:28 +08:00
    @sagaxu 可以具体一点吗。生成的时候随机,其实生成以后已经不随机了。
    我们用的 spanner ,不支持 random 函数。。不然每一批可以 random 选择 100 个,冲突概率也不高了。
    agzou
        3
    agzou  
       2022-03-04 15:22:59 +08:00
    coupons 分配服务有多个的时候,肯定要用到分布式锁,最简单就是用 redis ,有现成代码,也可以用 JDBC+数据库实现一个分布式锁。
    agzou
        4
    agzou  
       2022-03-04 15:24:10 +08:00
    @agzou #3 忘了看 OP 语言,我说的是 java 下的方案
    looplj
        5
    looplj  
    OP
       2022-03-04 15:28:38 +08:00
    @agzou 分布式锁更重了,分布式锁的 timeout 很难解决。用数据库乐观锁简单点,但是大佬还是觉得复杂了,不希望引入 redis 。
    murmur
        6
    murmur  
       2022-03-04 15:29:53 +08:00
    我感觉这个可以从业务层面解决,不想用 redis ,不想上排它锁,那就把数设置灵活点,比如 100 张的名额,那我做活动就发 80 ,万一锁出了问题发了 90 张也在承受范围内

    另外大额优惠券在实际电商的时候本来就是看人的,有些人生来就失去资格了,所以并发也是可以优化的
    murmur
        7
    murmur  
       2022-03-04 15:33:14 +08:00
    另外,实际上发卡系统对实时性也没有明确要求,京东不是经常告诉你你的优惠券 5-10 分钟才会到账么

    很多东西就得用业务解决,死磕技术是没用的,就跟双十一抢购一样,0 点抢购天怒人怨,连续热卖两个月不好吗?
    looplj
        8
    looplj  
    OP
       2022-03-04 15:35:52 +08:00
    @murmur 数量其实不是重点,重点是一个 coupon 只能给一个人发,不能重复发。
    looplj
        9
    looplj  
    OP
       2022-03-04 15:36:42 +08:00
    重点其实看怎么能提高随机读取 coupon 的性能以及随机性
    looplj
        10
    looplj  
    OP
       2022-03-04 15:39:20 +08:00
    @murmur 实时性其实要求也不是特别高,但是还是需要提高分配性能而已。

    现在其实有一个最基本的方案:

    1. 读 100 个 coupons
    2. 随机选择一个

    冲突概率还是挺低的,但是每一次都要读数据库,有点浪费
    Habyss
        11
    Habyss  
       2022-03-04 15:56:00 +08:00
    1. 读取 100 个 coupons(条件是未标记预分配), 并数据库标记预分配
    2. 随机的话, 是否能做到生成到数据库中时就是随机的呢
    looplj
        12
    looplj  
    OP
       2022-03-04 16:06:52 +08:00
    @Habyss
    1. 第一种考虑过,读取 100 个,然后全部删除掉,和预分配状态本质差不多;就是考虑到这时候挂掉了就浪费一批 coupons 。
    2. 存到数据库可以给一个随机编号,但是不知道怎么能读出来是随机的?
    mxT52CRuqR6o5
        13
    mxT52CRuqR6o5  
       2022-03-04 16:11:53 +08:00
    从数据库选取一条未被发出的 coupon 并标记为已发送(直接用原子操作实现,就不需要关心锁的问题)
    把这条 coupon 发给用户,发失败的话就从头再来
    代价是可能会有一些 coupon 没被发出去但被标记为已发送
    这个方案如何
    displayabc
        14
    displayabc  
       2022-03-04 16:13:54 +08:00
    我们当时也这样做过,后来发现,既然跟用户绑定了,券一样也无所谓
    mxT52CRuqR6o5
        15
    mxT52CRuqR6o5  
       2022-03-04 16:19:55 +08:00
    你很强调随机,不是很明白你这个随机具体是要用来干嘛的
    就像#1 说的 [生成时随机,分配时按顺序] ,分配时根本不需要随机
    luckyrayyy
        16
    luckyrayyy  
       2022-03-04 16:20:28 +08:00
    @ZSeptember 这种情况不用删除掉啊,打个已经被获取的标记,等到真的分配成功后再删除或者打标记分配成功。如果有一批 coupons 被获取了,但是服务器挂掉,那就用一个 Task 扫表长时间获取未分配的重新改成未分配。
    Habyss
        17
    Habyss  
       2022-03-04 16:26:34 +08:00
    @ZSeptember
    1. 挂掉是极端情况, 按照预分配状态的话, 即使挂掉了也是可以再将预分配还原的(预分配 /未分配 /已分配)
    这样有一种情况就是, 数据库未分配 coupon 发完了, 但是还存在极少部分在内存中预分配, 这时候基本上已经尾声了, 那就直接查出预分配的来分... 反正也是有数据库的乐观锁的.
    2. 我想的简单, 就是打乱之后再存数据库, 那顺序拿出来的也就相当于随机了...
    InternetExplorer
        18
    InternetExplorer  
       2022-03-04 16:29:14 +08:00
    生成的时候随机好,每个 coupon 给一个发放时间点,时间点可以均匀分布在活动时间上,哪个用户最先在发放时间后访问(或者请求)就分给哪个用户。
    looplj
        19
    looplj  
    OP
       2022-03-04 16:29:19 +08:00
    @mxT52CRuqR6o5 看分配步骤,随机性是为了避免乐观锁冲突,影响分配性能,因为要保证不能重复分配同一个 coupon 。

    你的那个方案和我 10 楼回复的一样,能 work ,但是性能应该应该比较差。其实我测试过,性能应该能满足我们系统现在的需求,但是天花板比较低。
    ryd994
        20
    ryd994  
       2022-03-04 16:29:53 +08:00 via Android
    @ZSeptember #12
    自增 id+随机 coupon 内容 /id
    读出的结果不就是随机的了吗?
    clf
        21
    clf  
       2022-03-04 16:30:31 +08:00
    coupons 表先不会动,随机往数据库 U 表里塞 N 个用户,各个服务自由塞,超过 coupons 表个数无所谓。

    然后由一个服务取最前面 N 个不同的用户和 coupons 里一一对应即可。
    freelancher
        22
    freelancher  
       2022-03-04 16:32:57 +08:00
    考虑用伪随机吗?例如给用户手机尾号是 9 的发优惠券。发到完为止。就好啦。没这么多要操心的。
    looplj
        23
    looplj  
    OP
       2022-03-04 16:35:18 +08:00
    @Habyss
    @mxT52CRuqR6o5

    我强调随机是是因为当前的保证不重复分配的方案是乐观锁,随机能避免冲突,提高性能。

    如果分配方案不使用乐观锁,可以不需要
    但是整体方案需要考虑到正确性以及性能
    mekingname
        24
    mekingname  
       2022-03-04 16:38:31 +08:00
    如果你是随机取一个 coupon ,那为什么你不一开始就把所有 coupon 顺序打乱再入库,这样按顺序读取不就相当于原来顺序入库时的随机读取了吗?这样用户请求的时候,你就按顺序返回就好了。每次返回的时候就把这一条锁定。
    mango88
        25
    mango88  
       2022-03-04 16:43:15 +08:00
    不用乐观锁的话,
    就把生成好的 coupons 读出来放 redis 里,每次 lpop 一个出来
    looplj
        26
    looplj  
    OP
       2022-03-04 16:43:57 +08:00
    @mekingname 看我 23 楼。

    随机不是目的。
    而且随机入库以后,我多个服务实例读出来怎么错开
    looplj
        27
    looplj  
    OP
       2022-03-04 16:46:33 +08:00
    @freelancher 你这是一种方案,对用户分区,冲突概率会低一些,但是哪个实例负责哪个分区也是一个问题,需要协商。。。
    RickyC
        28
    RickyC  
       2022-03-04 16:49:00 +08:00
    遇到一个问题:ASDJAF!@#, ASDASD , @EDQMQOW , ASDAD , V(@#(JD
    ------
    你后面的话,我一句也看不懂。
    looplj
        29
    looplj  
    OP
       2022-03-04 17:05:30 +08:00
    @haython 这一点和我们业务不一样,我们的 coupon 是一个 coupon code 发给用户就需要能使用的。
    现在的方案,不是在生成 coupon 的时候就给用户绑定,不过确实启发了一下,可以在生成的时候就绑定到人。就是较大调整。
    CantSee
        30
    CantSee  
       2022-03-04 17:20:11 +08:00
    通过 Queue 进行读取是不是好点呢,每次读取一个,绑定用户,预加载到 Queue 中,没有了再查一批加载到 Queue 中;
    oddcc
        31
    oddcc  
       2022-03-04 17:21:09 +08:00
    感觉就是个发号器啊

    可以考虑这样做
    有两张表,一个表放未使用的,一个表放已使用的
    提前生成一大批可用的 coupon 放到未使用的表中

    每次把一批 coupon 读到内存之后,就移动到已使用的表中,视为已使用的
    根据并发的压力调整这一批 coupon 有多少个

    这样你有多个分配服务,也不会重复,也不会冲突。也不涉及到其他的依赖,也不涉及到复杂的锁
    就算中间服务崩溃了,恢复之后也不会有重复的
    9c04C5dO01Sw5DNL
        32
    9c04C5dO01Sw5DNL  
       2022-03-04 17:22:17 +08:00
    必须得预先创建吗?可不可以请求分配时再创建 coupon ,写入成功代表分配成功。
    displayabc
        33
    displayabc  
       2022-03-04 17:30:16 +08:00
    @ZSeptember 只要是发到用户账户里,都可以一个码给多个人,使用的时候,只检查券的使用规则和用户的使用记录。只有让用户手动输入码的,才要保证唯一
    looplj
        34
    looplj  
    OP
       2022-03-04 17:38:31 +08:00
    @oddcc 你这个和我 12 楼的一样的,是可以的。读 100 个,然后把这 100 个删掉,就不会被其他实例读取了。
    edward1987
        35
    edward1987  
       2022-03-04 17:48:28 +08:00
    同 #1 #25 。 生成时随机,然后直接存 redis,用 lpop 读取就行。 你原本的 redis 方案太麻烦。。
    corningsun
        36
    corningsun  
       2022-03-04 17:48:56 +08:00
    同步并发操作转异步单线程就好了,加个中间状态。

    1 用户请求后是标记为 “待分发” 状态。
    2 再单独起个线程跑任务,取所有 “待分发” 的用户,按顺序从 coupon 分配,这时候就不存在冲突的问题了。
    3 用户查询的地方改一下,加个 “分配中” 页面
    looplj
        37
    looplj  
    OP
       2022-03-04 18:12:13 +08:00
    @corningsun 服务多实例的,你这是转单实例了。
    9c04C5dO01Sw5DNL
        38
    9c04C5dO01Sw5DNL  
       2022-03-04 18:12:50 +08:00
    我的意思是,如果预创建只是为了限制数量的话,就不需要预创建了。可以用乐观锁计数,和请求时分配 coupon 放在同一个事务中。

    比如:

    ```

    begin;

    update ct set count=count+1
    where count=? and count<?;

    update 成功则继续:

    insert into coupon_user ......

    insert 成功则表示分配成功

    commit ;


    ```
    looplj
        39
    looplj  
    OP
       2022-03-04 18:13:12 +08:00
    @edward1987 @mango88 可以,直接不落数据库
    looplj
        40
    looplj  
    OP
       2022-03-04 18:21:14 +08:00
    @giiiiiithub 忘记说明一个大限制,因为一些不可控的原因,创建 coupon 是有 rate limit 限制的 2 QPS ,40 RPM 。但是提供批量创建机制 每次 100 个。
    corningsun
        41
    corningsun  
       2022-03-04 18:29:04 +08:00
    @ZSeptember

    用户请求还是多实例啊,只是把分发 coupon 变成单线程了。

    单线程操作的速度是很快的,比如设置批量操作上限 1 万条。

    每次查询 “待分发” 的用户最多 1 万个,然后去 coupon 查询和用户数相同的出来直接分配,再批量更新。
    looplj
        42
    looplj  
    OP
       2022-03-04 18:43:22 +08:00
    @corningsun 可以,转串行,没问题,就是改动比较大。
    siweipancc
        43
    siweipancc  
       2022-03-04 18:53:20 +08:00 via iPhone
    随机入库的数据有一个唯一索引列 1 开始递增,用户每次请求 redis 原子加一取对应数据行。
    缺点是每次初始化数据批量入库都要全局锁,而且业务回滚之后对应的行要删除下次入库不能复用。
    rekulas
        44
    rekulas  
       2022-03-04 21:42:32 +08:00
    如果不想用 redis ,消息队列也可以实现该功能,预先把可用 coupon 都推到消息队列,消费即确认该 coupon ,还可以进一步集合消息队列延迟更新数据库,几乎不会造成压力
    lldld
        45
    lldld  
       2022-03-04 22:01:12 +08:00
    好比手机号嘛, 按号段先分配给不同的运营商, 运营商再卖给个人.

    另起一个服务, 目前的服务每次向新的服务申请若干连续的优惠券(申请记录在一张新表里面, 请求比较少, 可以不用 redis), 用完了再申请.
    darkengine
        46
    darkengine  
       2022-03-04 22:04:58 +08:00
    我觉得完全没有必要随机啊,只要 coupon code 不会被猜出来就行了。对于开发者来说你觉得是顺序的,但是对于单个用户来说,随机领跟按顺序领没有区别。
    ZeawinL
        47
    ZeawinL  
       2022-03-04 22:37:54 +08:00
    用用户 id 和可分配的 coupon 数取模
    looplj
        48
    looplj  
    OP
       2022-03-04 22:46:19 +08:00
    @ZeawinL 每次都要 count 一次,然后 offset 一次,性能不太行。
    chihiro2014
        49
    chihiro2014  
       2022-03-04 22:51:15 +08:00
    不一定要 redis ,用 Guava Cache ,本地缓存
    Huelse
        50
    Huelse  
       2022-03-04 23:05:18 +08:00
    插入的时候就做好随机了,取的时候按顺序取这么做应该没问题
    xy90321
        51
    xy90321  
       2022-03-04 23:35:30 +08:00 via iPhone
    1 ) coupon 表乱序插入,并且每行加一个自增 ID 。2 )为自增 ID 做一个 Sequence 。3 )所有服务通过 Sequence.nextval 拿到 ID 来取 coupon 。
    looplj
        52
    looplj  
    OP
       2022-03-05 00:03:50 +08:00
    @xy90321 自增步长改成 100 ,就是和我最开始的方案差不多,只是我是用 redis 保存 sequence 。使用自增连续序列确实可以,不过我们使用 spanner ,自增插入会有热点问题,一般不考虑。
    不过我的方案,相比,去掉了 redis 依赖,热点影响应该还可以接受,感觉确实还行。
    xy90321
        53
    xy90321  
       2022-03-05 14:38:07 +08:00 via iPhone
    @ZSeptember
    如果 redis 做原子操作的性能能接受的话,那无非是再加个允许接受 coupon 意外灭失的前提。
    这样 redis 每次从 coupon 表里面读出一套 coupon (比如 5000 条)的同时,把 coupon 表里对应的 coupon 状态直接切成已消费完毕。
    这样不论 redis 怎么搞,最多就是意外灭失 5000 个 coupon 而已,不影响你主体业务逻辑的完整性。
    looplj
        54
    looplj  
    OP
       2022-03-05 20:27:06 +08:00
    @xy90321 看我 12 楼,你这个方案提过了
    snowsui
        55
    snowsui  
       2022-03-06 12:37:12 +08:00
    给你一个方案,这一批 coupon 我理解应该是一个规则吧,假设这个规则叫做活动,缓存里存下活动 id&用户的关系就行了,这样是否领取通过缓存判断,有这个用户就领取过了。没有的话再去通过发号器也好,还是之前生成的也好,落库 couponId 绑定用户
    sampeng
        56
    sampeng  
       2022-03-06 14:14:33 +08:00
    redis 要维护麻烦,就没有比 redis 更麻烦的了。。。再说了。。没有 redis ,很多性能问题需要花很大的精力才能解决。。

    另外,如果实例数是固定的,一致性 hash 就能把预生成好的直接匹配到每个实例上去。我觉得每次 load 几百条进来挺好的。。简单可依赖。。
    关于     帮助文档     自助推广系统     博客     API     FAQ     Solana     5717 人在线   最高记录 6679       Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 36ms UTC 03:12 PVG 11:12 LAX 19:12 JFK 22:12
    Do have faith in what you're doing.
    ubao msn snddm index pchome yahoo rakuten mypaper meadowduck bidyahoo youbao zxmzxm asda bnvcg cvbfg dfscv mmhjk xxddc yybgb zznbn ccubao uaitu acv GXCV ET GDG YH FG BCVB FJFH CBRE CBC GDG ET54 WRWR RWER WREW WRWER RWER SDG EW SF DSFSF fbbs ubao fhd dfg ewr dg df ewwr ewwr et ruyut utut dfg fgd gdfgt etg dfgt dfgd ert4 gd fgg wr 235 wer3 we vsdf sdf gdf ert xcv sdf rwer hfd dfg cvb rwf afb dfh jgh bmn lgh rty gfds cxv xcv xcs vdas fdf fgd cv sdf tert sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf shasha9178 shasha9178 shasha9178 shasha9178 shasha9178 liflif2 liflif2 liflif2 liflif2 liflif2 liblib3 liblib3 liblib3 liblib3 liblib3 zhazha444 zhazha444 zhazha444 zhazha444 zhazha444 dende5 dende denden denden2 denden21 fenfen9 fenf619 fen619 fenfe9 fe619 sdf sdf sdf sdf sdf zhazh90 zhazh0 zhaa50 zha90 zh590 zho zhoz zhozh zhozho zhozho2 lislis lls95 lili95 lils5 liss9 sdf0ty987 sdft876 sdft9876 sdf09876 sd0t9876 sdf0ty98 sdf0976 sdf0ty986 sdf0ty96 sdf0t76 sdf0876 df0ty98 sf0t876 sd0ty76 sdy76 sdf76 sdf0t76 sdf0ty9 sdf0ty98 sdf0ty987 sdf0ty98 sdf6676 sdf876 sd876 sd876 sdf6 sdf6 sdf9876 sdf0t sdf06 sdf0ty9776 sdf0ty9776 sdf0ty76 sdf8876 sdf0t sd6 sdf06 s688876 sd688 sdf86