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

[adkudao]

目前帮客户在做一个类似网易一元夺宝的网站, 规则就是跟网易一元夺宝一样:
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 来做解决方案, 单纯看这个算法的话, 有没有更好的思路, 能更好地解决百万条号码随机分配的问题呢?

[am241]

找一个循环周期够长的伪随机函数，生成商品的时候初始化种子，然后记录夺宝的顺序，那么每个人的幸运号码就是可以根据种子和序号计算出来的。
夺宝的时候直接随机一个幸运序号，然后计算出来这个序号对应的幸运号码。

[am241]

如果怕生成的种子对应的循环周期不够长，可以用同一个种子，然后生成一个随机 key 和原始幸运号码做异或（举例），把运算结果作为给用户显示的幸运号码

[adkudao]

@am241

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

现在变为 1, 2, 3

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

然后 1 对应 1000001, 3 对应 1000003?

[am241]

@adkudao

是这个意思，上面主要描述的是快速生成唯一幸运序号的方法

[casparchen]

@am241 商品 id 加上楼上说的编号的字符串，用某种 hash 方法弄一下？

[casparchen]

@casparchen 理解错了，请忽略

[am241]

@adkudao
前面写的好像懵逼了
随机函数输出会冲突，保存在内部的种子可以在一定周期内保证唯一

@casparchen
hash 也是有几率冲突的吧，不知道在百万数量级下冲突的几率有多大

[debiann]

难道不是第一个人买给 1 号，第二个人买给 2 号。。。最后抽个数字就好了吗，为什么要搞那么复杂。。。

[pubby]

大件商品可以动态添加号码啊
一开始生成 1000 个号码
随着号码消耗，队列通知 号码生成器后台再添加更多号码，保证并发时足够用就行。

反正你等该商品夺宝结束后再确定谁中奖好了。

[adkudao]

@am241
用 @pubby 提到的方案, 是目前工作量最小, 最优的


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


@debiann
我倒是这么想, 问题是客户那里死活不同意, 因为目前所有的主流夺宝平台, 都是随机分配数字的, 他说别人可以, 为什么我不可以?

[lecher]

反过来不就好了，两种办法
1 、三个字段存，一个自增 ID 一个随机数一个标志位，一开始你就生成一组随机数，打乱之后插入到数据库中，用户来了请求执行 update saleorder set orderuser={uid} where orderstat=0;
这是个原子操作，性能也很不错，一旦更新成功说明用户成功预订一个随机数。再去取出来返回给用户就好了。
最后售尽就随机一个中奖号码出来。

2 、别用持久化存未分配数值，开个 Redis 存未分配的数据，业务就是如果 Redis 队列为空，去数据库取已分配的和一个序列化的原始队列求差集，差集随机塞到分配队列中，来一个取一个分配出去，这个分配也是原子操作。
这个只要商品销售前对分配队列做好预热，失效时间足够长，性能非常高。

[lecher]

第一种的 sql 应该是 update saleorder set orderuser={uid} where orderuser=0;
这个操作是之前 v2 上一个做电商的老鸟公布的，预先插入库存的数据，预留订单用户的字段，通过 update 这个原子操作锁表保证订单不会超售，同时这个只要建好 orderuser 这个索引，单凭数据库就可以扛很高的并发操作。

至于购买请求远远高出库存的瞬发请求，还是预分配，不过得用 Redis 来扛更高的并发业务和限流。

[gamexg]

内部使用自增 id ，显示时通过算法转换成一一对应的看似随机 id 即可。

[laoyuan]

其实一维变二维就好了

[tigerstudent]

用户 a 买了 2 份，就记权重 2 ，用户 b 买了 5 份就记权重 5 。等结束了再计算最后给谁，最后这部分计算可以异步执行。

[xenme]

@gamexg 我同意这个。
内部第一个给 1 号，第二个给 2 号，依此类推。
显示的时候进行变换： id*num1+num2 ，这样现实看起来随机
抽奖还是按照 1-N 的形式抽，简单方便

[adkudao]

@lecher
@gamexg
@tigerstudent
@laoyuan
@xenme

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


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

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

这样安全性更高, 而且性能相信可以得到解决

[lijinma]

你这做法太麻烦了，我给你个简单的思路，即简单又保证绝对公平，透明。

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

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

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

所以开奖的过程：

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

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


你需要考虑的问题是，如何正确随机，而不是提前生成号码。

[xurubin]

@am241 思路不错，只要把伪随机数换成伪随机置换就行了，最方便的就是常见的分组密码 DES AES 之类。服务器只需要存一个密钥 k ，第 i 号用户的号码就是 DES_k(i)。随用随算，根本不需要存进数据库里。

[am241]

@xurubin DES_k(i) 确实比伪随机好很多，多谢点评