V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
adkudao
V2EX  ›  问与答

请教各位 V 友一个神奇的夺宝算法

  •  
  •   adkudao · 2016-06-24 00:23:12 +08:00 · 4223 次点击
    这是一个创建于 3059 天前的主题,其中的信息可能已经有所发展或是发生改变。
    目前帮客户在做一个类似网易一元夺宝的网站, 规则就是跟网易一元夺宝一样:
    1. 一个 10 块钱的商品, 分别对应 10 个号码
    2. 用户花一块钱, 可以随机抽取一个号码
    3. 10 个号码抽完后, 得出一个幸运号码, 谁拥有这个号码, 谁就可以获得商品


    其他的都很简单, 就是随机抽取号码这里遇到了问题


    我之前的算法是参考的这篇文章:
    http://my.oschina.net/crazymus/blog/509107

    算法大致为:
    1. 一个商品有 10 个号码, 那么先生成数组, 数组包含 10 个号码, 将数组转化为字符串, 存入数据库
    2. 用户抽取号码时, 将字符串从数据库中读出来, 转化为数组, 从数组中随机取一个号码, 分配给用户
    3. 再次将数组转化为字符串, 存入数据库
    4. 反复 10 次,即可将所有号码随机分配出去



    目前这个算法用在小商品上是可以的, 因为一个小商品撑死了就几千个号码, 数据库的读写, php 的类型转化, 都不存在性能上的问题
    可是当遇到大件商品时, 性能问题就变得极其严重了
    比如一个房产, 价值几百万, 按照原有算法, 必须要生成几百万个号码, 并且存入数据库中,这每次存入数据库的数据不仅恐怖(10M 以上), 并且 PHP 直接报出内存不足的提示, 根本没法分配了

    通过修改 php.ini 可以加大 php 线程可使用的内存空间, 但这显然不是办法, 万一遇到几百上千个会员同时夺宝房产类商品, 这动辄一二十 M 的数据这么从 MySQL 中读来读去, 不仅数据库负担不起, 服务器也负担不起;



    原作者有提到过用 Redis 来存储数据, 所有号码存入内存中, 可以解决这个问题, 这当然是可行的

    但是就算用 Redis 来做解决方案, 单纯看这个算法的话, 有没有更好的思路, 能更好地解决百万条号码随机分配的问题呢?
    20 条回复    2016-07-05 20:45:16 +08:00
    am241
        1
    am241  
       2016-06-24 00:30:45 +08:00
    找一个循环周期够长的伪随机函数,生成商品的时候初始化种子,然后记录夺宝的顺序,那么每个人的幸运号码就是可以根据种子和序号计算出来的。
    夺宝的时候直接随机一个幸运序号,然后计算出来这个序号对应的幸运号码。
    am241
        2
    am241  
       2016-06-24 00:35:24 +08:00
    如果怕生成的种子对应的循环周期不够长,可以用同一个种子,然后生成一个随机 key 和原始幸运号码做异或(举例),把运算结果作为给用户显示的幸运号码
    adkudao
        3
    adkudao  
    OP
       2016-06-24 00:45:52 +08:00
    @am241

    我可否理解为, 原来的夺宝号码是 1000001, 1000003, 1000003..

    现在变为 1, 2, 3

    用户从 1, 2, 3 中取号码

    然后 1 对应 1000001, 3 对应 1000003?
    am241
        4
    am241  
       2016-06-24 00:48:46 +08:00
    @adkudao

    是这个意思,上面主要描述的是快速生成唯一幸运序号的方法
    casparchen
        5
    casparchen  
       2016-06-24 00:51:08 +08:00 via iPad
    @am241 商品 id 加上楼上说的编号的字符串,用某种 hash 方法弄一下?
    casparchen
        6
    casparchen  
       2016-06-24 00:52:56 +08:00 via iPad
    @casparchen 理解错了,请忽略
    am241
        7
    am241  
       2016-06-24 00:55:18 +08:00
    @adkudao
    前面写的好像懵逼了
    随机函数输出会冲突,保存在内部的种子可以在一定周期内保证唯一

    @casparchen
    hash 也是有几率冲突的吧,不知道在百万数量级下冲突的几率有多大
    debiann
        8
    debiann  
       2016-06-24 00:58:53 +08:00 via iPhone
    难道不是第一个人买给 1 号,第二个人买给 2 号。。。最后抽个数字就好了吗,为什么要搞那么复杂。。。
    pubby
        9
    pubby  
       2016-06-24 00:59:33 +08:00
    大件商品可以动态添加号码啊
    一开始生成 1000 个号码
    随着号码消耗,队列通知 号码生成器后台再添加更多号码,保证并发时足够用就行。

    反正你等该商品夺宝结束后再确定谁中奖好了。
    adkudao
        10
    adkudao  
    OP
       2016-06-24 01:13:46 +08:00
    @am241
    用 @pubby 提到的方案, 是目前工作量最小, 最优的


    @pubby
    非常感谢, 这个思路很好


    @debiann
    我倒是这么想, 问题是客户那里死活不同意, 因为目前所有的主流夺宝平台, 都是随机分配数字的, 他说别人可以, 为什么我不可以?
    lecher
        11
    lecher  
       2016-06-24 05:38:01 +08:00 via Android   ❤️ 1
    反过来不就好了,两种办法
    1 、三个字段存,一个自增 ID 一个随机数一个标志位,一开始你就生成一组随机数,打乱之后插入到数据库中,用户来了请求执行 update saleorder set orderuser={uid} where orderstat=0;
    这是个原子操作,性能也很不错,一旦更新成功说明用户成功预订一个随机数。再去取出来返回给用户就好了。
    最后售尽就随机一个中奖号码出来。

    2 、别用持久化存未分配数值,开个 Redis 存未分配的数据,业务就是如果 Redis 队列为空,去数据库取已分配的和一个序列化的原始队列求差集,差集随机塞到分配队列中,来一个取一个分配出去,这个分配也是原子操作。
    这个只要商品销售前对分配队列做好预热,失效时间足够长,性能非常高。
    lecher
        12
    lecher  
       2016-06-24 05:45:39 +08:00 via Android   ❤️ 1
    第一种的 sql 应该是 update saleorder set orderuser={uid} where orderuser=0;
    这个操作是之前 v2 上一个做电商的老鸟公布的,预先插入库存的数据,预留订单用户的字段,通过 update 这个原子操作锁表保证订单不会超售,同时这个只要建好 orderuser 这个索引,单凭数据库就可以扛很高的并发操作。

    至于购买请求远远高出库存的瞬发请求,还是预分配,不过得用 Redis 来扛更高的并发业务和限流。
    gamexg
        13
    gamexg  
       2016-06-24 06:58:32 +08:00 via Android   ❤️ 1
    内部使用自增 id ,显示时通过算法转换成一一对应的看似随机 id 即可。
    laoyuan
        14
    laoyuan  
       2016-06-24 07:01:16 +08:00
    其实一维变二维就好了
    tigerstudent
        15
    tigerstudent  
       2016-06-24 07:19:57 +08:00 via Android   ❤️ 1
    用户 a 买了 2 份,就记权重 2 ,用户 b 买了 5 份就记权重 5 。等结束了再计算最后给谁,最后这部分计算可以异步执行。
    xenme
        16
    xenme  
       2016-06-24 08:29:16 +08:00 via iPhone   ❤️ 1
    @gamexg 我同意这个。
    内部第一个给 1 号,第二个给 2 号,依此类推。
    显示的时候进行变换: id*num1+num2 ,这样现实看起来随机
    抽奖还是按照 1-N 的形式抽,简单方便
    adkudao
        17
    adkudao  
    OP
       2016-06-27 18:39:36 +08:00
    @lecher
    @gamexg
    @tigerstudent
    @laoyuan
    @xenme

    非常感谢, 这几天黑白颠倒, 没顾得上上 V 站, 谢谢了


    @xenme 你提到的这个方案, 请问方便提供案例教程吗?

    @lecher 非常好, 我目前的方案,准备把你的和 Redis 结合, 事先在 Redis 里生成几百万夺宝号码, 然后夺宝一个, 就从 Redis 中读取一个, 存入 MySQL

    这样安全性更高, 而且性能相信可以得到解决
    lijinma
        18
    lijinma  
       2016-07-05 15:01:57 +08:00
    你这做法太麻烦了,我给你个简单的思路,即简单又保证绝对公平,透明。

    只需要在 Redis 中记录每个商品的自增值,初始化为 1

    比如一个商品有 10 个人参与,那每个人分配一个号: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10

    你现在要做的是在这 1-10 个号中随机选取一个人,对吗?

    所以开奖的过程:

    调用: https://www.random.org/ 随机的函数,获取 1-10 的随机数,这是真随机,不是伪随机,获取到谁就是谁。

    如果是 100 万人参加?那也不用担心啊,没任何压力,而且 Redis 的并发能撑个几万。


    你需要考虑的问题是,如何正确随机,而不是提前生成号码。
    xurubin
        19
    xurubin  
       2016-07-05 20:18:32 +08:00
    @am241 思路不错,只要把伪随机数换成伪随机置换就行了,最方便的就是常见的分组密码 DES AES 之类。服务器只需要存一个密钥 k ,第 i 号用户的号码就是 DES_k(i)。随用随算,根本不需要存进数据库里。
    am241
        20
    am241  
       2016-07-05 20:45:16 +08:00
    @xurubin DES_k(i) 确实比伪随机好很多,多谢点评
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2336 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 15:55 · PVG 23:55 · LAX 07:55 · JFK 10:55
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.