这是一个创建于 3110 天前的主题，其中的信息可能已经有所发展或是发生改变。
目前帮客户在做一个类似网易一元夺宝的网站, 规则就是跟网易一元夺宝一样:
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 来做解决方案, 单纯看这个算法的话, 有没有更好的思路, 能更好地解决百万条号码随机分配的问题呢?
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 来做解决方案, 单纯看这个算法的话, 有没有更好的思路, 能更好地解决百万条号码随机分配的问题呢?
 |
1
am241 2016-06-24 00:30:45 +08:00
找一个循环周期够长的伪随机函数，生成商品的时候初始化种子，然后记录夺宝的顺序，那么每个人的幸运号码就是可以根据种子和序号计算出来的。
夺宝的时候直接随机一个幸运序号，然后计算出来这个序号对应的幸运号码。 |
|
2
am241 2016-06-24 00:35:24 +08:00
如果怕生成的种子对应的循环周期不够长，可以用同一个种子，然后生成一个随机 key 和原始幸运号码做异或（举例），把运算结果作为给用户显示的幸运号码
|
 |
3
adkudao OP @am241
我可否理解为, 原来的夺宝号码是 1000001, 1000003, 1000003.. 现在变为 1, 2, 3 用户从 1, 2, 3 中取号码 然后 1 对应 1000001, 3 对应 1000003? |
 |
5
casparchen 2016-06-24 00:51:08 +08:00 via iPad
@am241 商品 id 加上楼上说的编号的字符串，用某种 hash 方法弄一下？
|
|
6
casparchen 2016-06-24 00:52:56 +08:00 via iPad
@casparchen 理解错了，请忽略
|
|
7
am241 2016-06-24 00:55:18 +08:00
|
 |
8
debiann 2016-06-24 00:58:53 +08:00 via iPhone
难道不是第一个人买给 1 号，第二个人买给 2 号。。。最后抽个数字就好了吗，为什么要搞那么复杂。。。
|
 |
9
pubby 2016-06-24 00:59:33 +08:00
大件商品可以动态添加号码啊
一开始生成 1000 个号码 随着号码消耗，队列通知 号码生成器后台再添加更多号码，保证并发时足够用就行。 反正你等该商品夺宝结束后再确定谁中奖好了。 |
|
10
adkudao OP |
 |
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 队列为空，去数据库取已分配的和一个序列化的原始队列求差集，差集随机塞到分配队列中，来一个取一个分配出去，这个分配也是原子操作。 这个只要商品销售前对分配队列做好预热，失效时间足够长，性能非常高。 |
|
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 来扛更高的并发业务和限流。 |
 |
13
gamexg 2016-06-24 06:58:32 +08:00 via Android 1
内部使用自增 id ，显示时通过算法转换成一一对应的看似随机 id 即可。
|
 |
14
laoyuan 2016-06-24 07:01:16 +08:00
其实一维变二维就好了
|
 |
15
tigerstudent 2016-06-24 07:19:57 +08:00 via Android 1
用户 a 买了 2 份，就记权重 2 ，用户 b 买了 5 份就记权重 5 。等结束了再计算最后给谁，最后这部分计算可以异步执行。
|
 |
16
xenme 2016-06-24 08:29:16 +08:00 via iPhone 1
|
|
17
adkudao OP |
 |
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 的并发能撑个几万。 你需要考虑的问题是，如何正确随机，而不是提前生成号码。 |
Select Language