description |
---|
关于通用型抽奖平台搭建 |
1. 不同的活动有不同的奖项配置,并且允许多活动并行
2. 抽奖类型可以分为:大转盘(九宫格、圆盘)、翻牌、刮刮卡、砸金蛋
2. 奖项:实物,现金红包,购物券,积分,再来一次等等;
3. 多奖项+等级区分,如一等奖:macbook pro,二等奖: ipad , iwatch,三等奖:小米手机,华为手机,魅族手机等,同等级中奖概率相同。
4. 在不同的活动中,每个用户每天有多少次的抽奖机会,分享可以增加抽奖次数;
5. 防作弊机制:访问限流、
1. 我们可以把每个活动抽象出一张表,有具体的活动标题,活动的开始时间,活动的结束时间,因为每个活动限制的用户抽取次数不同,所以有一个抽取次数的限制,还有活动的状态,那么活动表我们起名为t\_activity;
2. 活动的奖励我们可以抽象出一张表,奖励有奖励的类型,红包和积分的具体数额,实物的奖品名称,等等,奖品的等级,是一等奖,二等奖,三等奖,还是纪念奖,还有每个奖品获取的概率,那么物品的表我们起名为t\_prize;
3. 如果是实物奖励的话,需要用户填写一些信息,领取人的姓名,领取人的联系方式,领取人的收获地址t\_user;
4. 用户每次抽奖的记录,抽到了那个奖项,如果是红包的和积分的话,数额是多少,用户是否领取了奖励,如果是实物的话,抽到了那个实物,是否填写了实物的领取信息,还有抽奖时间t\_raffle;
1. t\_activity
| id | title | start_time | end_time | times | home_page_path | status | create_time | create_by | | --- | --- | | varchar | varchar | date | date | int | varchar | int | date | varchar |
2. t\_prize
| id | activity_id | type | name | counts | level | percentage | create_time | create_by | | --- | --- | | varchar | varchar | int | varchar | decimal(5,2) | int | decimal(2,2) | date | varchar |
3. t\_information
| id | prize_id | prize_name | account_id | user_name | user_mobile | user_address | status | create_time | | --- | --- | | varchar | varchar | varchar | varchar | varchar | varchar | varchar | int | date |
4. t\_raffle
| id | account_id | prize_id | prize_type | prize_name | status | raffle_time | | --- | --- | | varchar | varchar | varchar | int | varchar | int | date |
列子:例如游戏中打败一个boss,会掉落下面其中一个物品,而每个物品都有一定概率:
-
靴子 20%
-
披风 25%
-
饰品 10%
-
双手剑 5%
-
金币袋 40%
现在的问题就是如何根据概率掉落一个物品给玩家。- 随机数计算
生成一个列表,分成几个区间,例如列表长度100,1-20是靴子的区间,21-45是披风的区间等,然后随机从100取出一个数,看落在哪个区间。算法时间复杂度:预处理O(MN),随机数生成O(1),空间复杂度O(MN),其中N代表物品种类,M则由最低概率决定。
2. 离散算法
也就是上面的改进,竟然1-20都是靴子,21-45都是披风,那抽象成小于等于20的是靴子,大于20且小于等于45是披风,就变成几个点[20,45,55,60,100],然后也是从1到99随机取一个数R,按顺序在这些点进行比较,知道找到第一个比R大的数的下标,比一般算法减少占用空间,还可以采用二分法找出R,这样,预处理O(N),随机数生成O(logN),空间复杂度O(N)。
请点击查看详细:http://www.cnblogs.com/miloyip/archive/2010/04/21/1717109.html
3. Alias Method
Alias Method就不太好理解,实现很巧妙,推荐先看看这篇文章:http://www.keithschwarz.com/darts-dice-coins/
大致意思:把N种可能性拼装成一个方形(整体),分成N列,每列高度为1且最多两种可能性,可能性抽象为某种颜色,即每列最多有两种颜色,且第n列中必有第n种可能性,这里将第n种可能性称为原色。
想象抛出一个硬币,会落在其中一列,并且是落在列上的一种颜色。这样就得到两个数组:一个记录落在原色的概率是多少,记为Prob数组,另一个记录列上非原色的颜色名称,记为Alias数组,若该列只有原色则记为null。
之前的例子,为了便于演示换成分数
- 靴子 20% -> 1/4
- 披风 25% -> 1/5
- 饰品 10% -> 1/10
- 双手剑 5% -> 1/20
- 金币袋 40% -> 2/5
然后每个都乘以5(使每列高度为1),再拼凑成方形
拼凑原则:每次都从大于等于1的方块分出一小块,与小于1的方块合成高度为1
由上图方形可得到两个数组:
Prob: [3/4, 1/4, 1/2, 1/4, 1]
Alias: [4, 4, 0, 1, null] (记录非原色的下标)
之后就根据Prob和Alias获取其中一个物品
随机产生一列C,再随机产生一个数R,通过与Prob[C]比较,R较大则返回C,反之返回Alias[C]。
Alias Method 复杂度:预处理O(NlogN),随机数生成O(1),空间复杂度O(2N)
高并发是指通过设计保证系统能够同时并行处理很多请求,而解决高并发无非从两个方面入手:垂直扩展(Scale Up)与水平扩展(Scale Out)。
- 水平扩展 增加应用服务,数据库读写分离、分库分表,连接池,主要是利用多机水平扩容
- 垂直扩展 缩减和压缩数据传递,增加缓存,页面静态化,提高单机QPS,异步处理
- 负载均衡
- 限流
- 降级
- 隔离
- 超时与重试(补偿)
- 回滚
- 限流
- 限制IP
- 强制登录
- 限制用户
- 验证码(短信和图片验证码)
- 限制设备
- 微信登录(依赖第三方)