全民夺宝重构细节:幸运码的生成

本文记录全民夺宝幸运码生成功能的重构优化。在全民夺宝项目中,每个商品上线会生成一期夺宝,一期夺宝完成之后生成新的一期供用户参与,系统需要自动为每一期生成幸运码。

原有情况

原来的幸运码实现是大于10w元(豪车等)的手动随机生成并放置在文件中不存入MySQL(幸运码太多太大),这类大额商品是手动发布期数的;小于10w元的自动生成并随机打乱,且不管最低参与价多少,都生成与商品售价相同数量的幸运码;生成的幸运码以JSON形式存储在商品期数表对应的一个字段中(MySQL)。

重构的目的是要实现:

  • 不考虑商品价格区间全自动生成幸运码
  • 根据最低参与价计算,减少幸运码数量
  • 幸运码不再存储到MySQL,而是另外存储到MongoDB
  • 幸运码的分配不再直接将号码与用户信息存储到MySQL表,而是以区间索引的方式记录到MongoDB

一个是改为自动化,一个是引入MongoDB存储幸运码,减少MySQL表数据量降低表读写压力。

需求梳理

对于售价为P的商品,最小参与金额为U,其中:P为正整数(单位为元),U为正整数且是P的因数(默认值为1);即用户参与夺宝时,花费n*U的金额参与夺宝,可获得n个幸运码(重构后)。

幸运码定义:定为8位(千万),取值范围为1000,0009999,9999。那么,如何生成幸运码呢?

问题分析

商品某一期在上线时就需要确定售价P和最小参与金额为U,在这个基础上幸运码的数量N是确定的:N=P/U,一旦幸运码售完,就进入开奖环节。N个幸运码不能重复,且符合幸运码定义。有两种实现方式:

  1. 用户参与夺宝时再即时生成幸运码并分配
    • 不容易保障幸运码唯一性
    • 增加用户出价参与时的接口的耗时
  2. 上线新期数时提前生成,用户参与时进行分配
    • 提前生成,随机打乱,用户参与时按顺序分配

很显然第一种并不可取,按第二种来实现:幸运码一旦生成就不再改变,为了在用户参与夺宝时提高幸运码的分配效率,幸运码串放置在一个数组中,按顺序分配给用户(只需要加锁控制并发分配即可),这就要求在生成幸运码时产生的号码是随机的而不是连续的。这个问题最终简化为:

随机生成 N 个从 1 到 N且不重复的正整数

很显然一次遍历就可以生成1NN个不重复的正整数,而剩下的问题就是如何高效地随机打乱它:只需要再一次遍历,将当前位置的号码随机与其他号码中的某一个进行调换,就可以实现随机打乱它,而随机生成某个范围内的下标,有现成的库可以使用,这样我们就得到一个实现算法:

  1. 根据售价P和最小参与金额U计算幸运码的数量N
  2. 一次遍历按顺序生成1到N这N个正整数,不足8位时加上1000,000
  3. 一次遍历随机交换元素位置,以实现打乱生成的幸运码顺序
  4. 得到打乱顺序的幸运码,用户出价参与夺宝时按顺序分配幸运码即可

程序实现

LuckyNumberBuilder.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package any; // 避免暴露项目敏感细节,此处我替换掉

import java.util.Random;

public class LuckyNumberBuilder {
public static final int LUCKY_NUMBER_MAX = 99999999;
public static final int LUCKY_NUMBER_BASE = 10000000; // 1千万

private static void verifyPrice(int price, int unit) {
if (unit <= 0 || unit > price || price > LUCKY_NUMBER_MAX || price%unit != 0) {
throw new IllegalArgumentException(
"售价(需为夺宝价的整数倍)或夺宝价无效,售价:" + price + ",夺宝价:" + unit
);
}
}

//该方法可以独立到公共包
public static void shuffle(int[] numbers) {
if (numbers.length <= 1) {
return;
}

Random random = new Random();

//random.nextInt(10)%2 == 0 增强随机性
if (numbers.length == 2 && random.nextInt(10)%2 == 0) {
numbers[0] ^= numbers[1];
numbers[1] ^= numbers[0];
numbers[0] ^= numbers[1];
return;
}

for (int i = 0; i < numbers.length; i++) {
//随机选择一个 [0, N) 之间不为i的下标,注意溢出的情况
int si = random.nextInt(numbers.length);
si = ((si == i) ? si + 1 : si) % numbers.length;

numbers[i] ^= numbers[si];
numbers[si] ^= numbers[i];
numbers[i] ^= numbers[si];
}
}

public static int[] build(int price) {
return build(price, 1);
}

public static int[] build(int price, int unit) {
verifyPrice(price, unit);

int luckyNumberCount = price / unit;
int[] luckyNumbers = new int[luckyNumberCount];

for(int i=0; i<luckyNumberCount; i++) {
luckyNumbers[i] = i + 1;

if (i+1 < LUCKY_NUMBER_BASE) {
luckyNumbers[i] += LUCKY_NUMBER_BASE;
}
}

shuffle(luckyNumbers);

return luckyNumbers;
}
}

效率分析

两个for遍历N次,时间复杂度为O(2N)亦即O(n)级别,已经可以接受。

显而易见的是,价格越高,生成的幸运码数量就可能越多,幸运码数量和占用空间的大小是随着价格的升高而线性增加的,所以空间的复杂度也在O(n)级别,而随着N越大,占用空间就越多:一个幸运码为一个数字,占用4个字节,考虑一下几种情况下生成幸运码的内存消耗情况:

  1. 考虑一个商品价格千万或百万级别的情况,这种情况下商品可能是豪宅别墅、普通商品房、或者豪车,这类商品吸引力大,一般最低参与价格为1元,以让所有人有最大的意愿参与,那么幸运码将会有千万个,为最低参与价格为1元的商品生成幸运码所需要的内存为:

    1
    2
    3
    (5000*10000 / 1) * 4 / 1000 / 1000 = 200 (MB)   // 5kw商品,一般没有(树大招风)
    (1000*10000 / 1) * 4 / 1000 / 1000 = 40 (MB) // 1kw商品,一般也不上(树大招风)
    (500*10000 / 1) * 4 / 1000 / 1000 = 20 (MB) // 500w,超跑豪车,基本上是最大价格的商品
  2. 而考虑大多数常见的商品价格情况,基本处在万元级别以下:

    1
    2
    3
    (10*10000 / 1) * 4 / 1000 = 400 (KB)            // 10w,一般没有这个价格的商品
    (5*10000 / 1) * 4 / 1000 = 200 (KB) // 5w,高级相机、手表等,高配苹果产品等
    (10000 / 1) * 4 / 1000 = 40 (KB) // 1w,绝大多数商品处在这个价格级别,及低于

也就是说按照这个实现方案,大多数商品的换期生成抽奖号码所消耗的CPU和内存资源都会比较平稳,资源耗用量不高,而少数情况下,豪车等顶级商品(500w级别)换期时会有一个小波峰,但处在可接受范围。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×