V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ZSeptember
V2EX  ›  程序员

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

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

    背景:

    需求:

    预先创建一批 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
    生成时随机,分配时按顺序
    ZSeptember
        2
    ZSeptember  
    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 下的方案
    ZSeptember
        5
    ZSeptember  
    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 点抢购天怒人怨,连续热卖两个月不好吗?
    ZSeptember
        8
    ZSeptember  
    OP
       2022-03-04 15:35:52 +08:00
    @murmur 数量其实不是重点,重点是一个 coupon 只能给一个人发,不能重复发。
    ZSeptember
        9
    ZSeptember  
    OP
       2022-03-04 15:36:42 +08:00
    重点其实看怎么能提高随机读取 coupon 的性能以及随机性
    ZSeptember
        10
    ZSeptember  
    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. 随机的话, 是否能做到生成到数据库中时就是随机的呢
    ZSeptember
        12
    ZSeptember  
    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 没被发出去但被标记为已发送
    这个方案如何
    haython
        14
    haython  
       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 给一个发放时间点,时间点可以均匀分布在活动时间上,哪个用户最先在发放时间后访问(或者请求)就分给哪个用户。
    ZSeptember
        19
    ZSeptember  
    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 的发优惠券。发到完为止。就好啦。没这么多要操心的。
    ZSeptember
        23
    ZSeptember  
    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 一个出来
    ZSeptember
        26
    ZSeptember  
    OP
       2022-03-04 16:43:57 +08:00
    @mekingname 看我 23 楼。

    随机不是目的。
    而且随机入库以后,我多个服务实例读出来怎么错开
    ZSeptember
        27
    ZSeptember  
    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
    ------
    你后面的话,我一句也看不懂。
    ZSeptember
        29
    ZSeptember  
    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 有多少个

    这样你有多个分配服务,也不会重复,也不会冲突。也不涉及到其他的依赖,也不涉及到复杂的锁
    就算中间服务崩溃了,恢复之后也不会有重复的
    giiiiiithub
        32
    giiiiiithub  
       2022-03-04 17:22:17 +08:00
    必须得预先创建吗?可不可以请求分配时再创建 coupon ,写入成功代表分配成功。
    haython
        33
    haython  
       2022-03-04 17:30:16 +08:00
    @ZSeptember 只要是发到用户账户里,都可以一个码给多个人,使用的时候,只检查券的使用规则和用户的使用记录。只有让用户手动输入码的,才要保证唯一
    ZSeptember
        34
    ZSeptember  
    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 用户查询的地方改一下,加个 “分配中” 页面
    ZSeptember
        37
    ZSeptember  
    OP
       2022-03-04 18:12:13 +08:00
    @corningsun 服务多实例的,你这是转单实例了。
    giiiiiithub
        38
    giiiiiithub  
       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 ;


    ```
    ZSeptember
        39
    ZSeptember  
    OP
       2022-03-04 18:13:12 +08:00
    @edward1987 @mango88 可以,直接不落数据库
    ZSeptember
        40
    ZSeptember  
    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 查询和用户数相同的出来直接分配,再批量更新。
    ZSeptember
        42
    ZSeptember  
    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 数取模
    ZSeptember
        48
    ZSeptember  
    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 。
    ZSeptember
        52
    ZSeptember  
    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 而已,不影响你主体业务逻辑的完整性。
    ZSeptember
        54
    ZSeptember  
    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   ·   我们的愿景   ·   实用小工具   ·   983 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 22:00 · PVG 06:00 · LAX 15:00 · JFK 18:00
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.