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

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

  •  
  •   ZSeptember · 214 天前 · 2173 次点击
    这是一个创建于 214 天前的主题,其中的信息可能已经有所发展或是发生改变。

    背景:

    需求:

    预先创建一批 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 条附言  ·  214 天前
    附加一条现状
    1. 辣鸡 spanner 没有 random 函数,做不到运行时读取随机
    第 2 条附言  ·  214 天前
    暂定方案

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

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

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

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

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

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

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

    然后由一个服务取最前面 N 个不同的用户和 coupons 里一一对应即可。
    freelancher
        22
    freelancher  
       214 天前
    考虑用伪随机吗?例如给用户手机尾号是 9 的发优惠券。发到完为止。就好啦。没这么多要操心的。
    ZSeptember
        23
    ZSeptember  
    OP
       214 天前
    @Habyss
    @mxT52CRuqR6o5

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

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

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

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

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

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

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

    比如:

    ```

    begin;

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

    update 成功则继续:

    insert into coupon_user ......

    insert 成功则表示分配成功

    commit ;


    ```
    ZSeptember
        39
    ZSeptember  
    OP
       214 天前
    @edward1987 @mango88 可以,直接不落数据库
    ZSeptember
        40
    ZSeptember  
    OP
       214 天前
    @giiiiiithub 忘记说明一个大限制,因为一些不可控的原因,创建 coupon 是有 rate limit 限制的 2 QPS ,40 RPM 。但是提供批量创建机制 每次 100 个。
    corningsun
        41
    corningsun  
       214 天前
    @ZSeptember

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

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

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

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

    另外,如果实例数是固定的,一致性 hash 就能把预生成好的直接匹配到每个实例上去。我觉得每次 load 几百条进来挺好的。。简单可依赖。。
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1227 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 179ms · UTC 17:55 · PVG 01:55 · LAX 10:55 · JFK 13:55
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.