一种短ID生成策略
一、背景
最近公司一个项目中存在一个业务场景，类似在美团上下单，去商户消费确认消费时，用户需要向商家提供一串编码来作为用户到店消费凭证，这个码我们称之为“核销码”。这个核销码需要具有这样特性：1.不能太长；2.具有一定随机性；3.具有一定的复杂度以免被太容易被伪造 4.不能重复。Snowflake算法可以在分布式环境下生成不重复的ID，百度改造后的Snowflake生成的Long型ID，转化为（[0-9A-Z]数据一般不区分大小写，因此去除[a-z]26个字符）36个字符表示也需要11位，而我们要求是8位，因此Snowflake被排除在外。
二、算法设计
1. 初步设计
a）编码字符
数据库存储环境采用mysql，mysql默认是不区分大小写的，为了保证编码唯一性，采用[0-9A-Z]编码，但是核销码除了扫码识别外，还存在商户手动输入的情况，0、O、I、L四个易被输错或混淆的字符去除，共剩余32位字符，分别是：{ '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A','B', 'C', 'D', 'E', 'F', 'G', 'H', 'J', 'K', 'M','N', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'}。
b) 数据容量
8位32进制的数字，最大值为32^8-1=1,0995,1162,7775约等于1万亿。理想情况下，我们的核销码是在上述32位随机生成8个字符，我们可以生成约1万亿个核销码。
c) 重复与冲撞
我们常用的不重复ID生成策略有数据库自增、Redis自增、Snowflake算法等，这些ID编码都是自增生长的。我们的随机生成的8位字符，要保证不重复，必须保存已生成的核销码，我们可能放到redis的HashSet数据结构里。随着业务量的增长，生成的核销码数量有可能1K->1W->10W->100W, redis存储这样一批核销也有一定的空间成本，并且随着set集合数量的增大，往集合中放元素时HashSet的hash函数hash冲突的概率也随之增大，当然与原有编码冲撞概率也随之增大。因此，该方案需要优化。
2. 优化设计
a) 划分标识位与随机位
我们可以将8位划分成3位标识位与5位随机位，如下所示：
- 第1位标识当前年份偏移值，比如从2019开始，今年也是2019年，偏移量为0，由于0被排除，32位字符中第1位为1(看成0就好)，因此第1位为1
- 第2、3位标识当年天数偏移量，32^2=1024，远大于366，用2位表示即可。比如今天是2019-12-10，是今年的第344天，转换为指定字符的32进制为BS
- 第4~8位是随机字符位，32^5-1=3355,4431, 我们可以通过生成一个0~3355,4431随机整数，转换为指定字符的32进制
理想情况下，这样的设计我们可以用31年，保证每天可以生成3000W左右的核销码。每天的当年天数偏移量是不一样的，因此，每天生成的核销码也都不一样，这样我们Redis的HashSet只需要保存当天已生成的核销码，来做重复判断即可，大大减轻了redis的存储负担。
b) 简单混淆
我们前3位是基本不变的，放到一起太容易看出规律。因此，我把3个标识位分别放置到第2、4、6位，混淆后如下：
c) 冲突率测试
- 100轮测试，每轮随机生成1000个核销码的平均冲突率为:0.00001
- 100轮测试，每轮随机生成10000个核销码的平均冲突率为:0.000136
- 100轮测试，每轮随机生成100000个核销码的平均冲突率为:0.001492
从以上测试结果来看，加入我们每天生成10W个核销码，则冲突的核销码约为150个左右，万分之15的概率。我实际的业务量一天有1000个订单已经不错了，测试代码如下：
1 public static void main(String[] args) {
2
3 final int batch = 100;
4 List<BigDecimal> statics = new ArrayList<>(batch);
5 int conflictSum = 0;
6 final int size = 100000;
7
8 for (int j = 0; j < batch; j++) {
9 Set<String> hashSet = new HashSet<>(size);
10 for (int i = 0; i < size; i++) {
11 String code = genVerifyCode();
12 hashSet.add(code);
13 }
14 int conflict = size - hashSet.size();
15 conflictSum += conflict;
16 statics.add(new BigDecimal(conflict).divide(new BigDecimal(size)));
17 }
18 System.out.println(batch + "轮测试，每轮随机生成" + size + "个核销码的平均冲突率为:" + new BigDecimal(conflictSum)
19 .divide(new BigDecimal(batch * size)));
20 statics.forEach(System.out::println);
21 }
d) 性能测试
经测试发现，如果redis服务跟应用服务在同一服务器下，单次生成耗时平均在0.2~0.8ms之间波动，用arthas监控如下：
三、附件
1 package com.shared.common.support.util;
2
3 import com.github.rxyor.common.util.lang2.RadixUtil;
4 import java.time.LocalDate;
5 import org.apache.commons.lang3.RandomUtils;
6
7 /**
8 *<p>
9 * 核销码生成工具类，目前核销码是8位，1位标识年份距2019年的偏移量，2位标识
10 * 当天是今天的第几天，5位可以由0~32^5-1的随机INT值转换为指定字符的32进制标识，
11 * 年份天数标识放在一起过于明显，分散到下标为1,3,5位置。经过测试，10W个核销码，
12 * 冲突率为150/10W, 1W个核销码冲突率几乎为0
13 *</p>
14 *
15 * @author
16 * @date 2019/12/10 周二 10:22:00
17 * @since 1.0.0
18 */
19 public class VerifySaleCodeUtil {
20
21 /**
22 * 核销码表示字符，0~9,A~Z，去除0、O、I、L 4个易混淆的字符还是32位
23 */
24 public final static char[] DIGITS = {
25 '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A',
26 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'J', 'K', 'M',
27 'N', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
28 'Y', 'Z'};
29
30 /**
31 * 开始年份，用户计算年份偏移量
32 */
33 public final static int BEGIN_YEAR = 2019;
34
35 /**
36 * 随机位由5位字符表示
37 */
38 public final static int RANDOM_LEN = 5;
39
40 /**
41 * 5为32进制能表示的最大无符号整数为32^5-1
42 */
43 private final static int MAX_RANDOM_INT = (int) (Math.pow(DIGITS.length, RANDOM_LEN) - 1);
44
45 private static final RadixUtil INSTANCE = RadixUtil.builder().digits(DIGITS).build();
46
47 /**
48 *<p>
49 *生成一个核销码
50 *</p>
51 *
52 * @author
53 * @date 2019-12-10 周二 10:35:16
54 * @return
55 */
56 public static String genVerifySaleCode() {
57 LocalDate localDate = LocalDate.now();
58
59 //年份偏移量字符表示
60 char yearChar = DIGITS[Math.abs(localDate.getYear() - BEGIN_YEAR)];
61 //一年的第几天32进制字符表示
62 String dayOfYearString = INSTANCE.convert2String(localDate.getDayOfYear());
63 //32*32=1024>366, 2位即可表示天的偏移量, 不够2位补32进制第0位字符
64 if (dayOfYearString.length() == 1) {
65 dayOfYearString = DIGITS[0] + dayOfYearString;
66 }
67
68 String randomCode = genRandomCode();
69
70 StringBuilder verifyCode = new StringBuilder(randomCode);
71
72 //sb式混淆
73 //下标1位置插入年份偏移标识
74 verifyCode.insert(1, yearChar);
75 //下标3位置插入天偏移标识第1位
76 verifyCode.insert(3, dayOfYearString.charAt(0));
77 //下标5位置插入天偏移标识第2位
78 verifyCode.insert(5, dayOfYearString.charAt(1));
79
80 return verifyCode.toString();
81 }
82
83 /**
84 *生成（0~32^5-1）之间的随机整数，并转换为指定表示字符的32进制
85 * @return
86 */
87 private static String genRandomCode() {
88 final int random = RandomUtils.nextInt(0, MAX_RANDOM_INT);
89 String randomCode = INSTANCE.convert2String(random);
90 StringBuilder sb = new StringBuilder();
91 //不足5位，补齐5位
92 for (int i = randomCode.length(); i < RANDOM_LEN; i++) {
93 sb.append(DIGITS[0]);
94 }
95 return sb.toString() + randomCode;
96 }
97
98 }
1 @Slf4j
2 @Component
3 public class VerifySaleGenerator implements InitializingBean {
4
5 private static final ExecutorService THREAD_POOL;
6 private static VerifySaleGenerator INSTANCE;
7
8 @Autowired
9 private RedissonClient redissonClient;
10
11 /**
12 * 创建线程池
13 */
14 static {
15 //用于设置key过期的线程池，队列容量不需要那么长，多余的任务丢弃即可
16 THREAD_POOL = new ThreadPoolExecutor(
17 SystemConst.AVAILABLE_PROCESSORS, SystemConst.AVAILABLE_PROCESSORS,
18 0L, TimeUnit.SECONDS, new LinkedBlockingQueue<Runnable>(8),
19 new CarpThreadFactory(), new CarpDiscardPolicy());
20 }
21
22 private VerifySaleGenerator() {
23 }
24
25 public static VerifySaleGenerator instance() {
26 return INSTANCE;
27 }
28
29 /**
30 *<p>
31 *生成核销码
32 *</p>
33 *
34 * @author liuyang
35 * @date 2019-12-10 周二 11:21:44
36 * @return
37 */
38 public String generate() {
39 final String key = genCurDayUsedCodeRedisKey();
40 RSet<String> set = redissonClient.getSet(key);
41 if (set == null) {
42 throw new RedisException("redisson client初始化失败");
43 }
44
45 boolean exist = true;
46 String verifySaleCode = null;
47 int count = 0;
48 try {
49 while (exist) {
50 verifySaleCode = VerifySaleCodeUtil.genVerifySaleCode();
51 exist = !set.add(verifySaleCode);
52 count++;
53 if (count > 10) {
54 throw new BizException("生成核销码冲突次数超过阈值");
55 }
56 }
57 } finally {
58 THREAD_POOL.submit(() -> {
59 if (set.isExists()) {
60 set.expire(25 - LocalDateTime.now().getHour(), TimeUnit.HOURS);
61 }
62 });
63 }
64 return verifySaleCode;
65 }
66
67 /**
68 *<p>
69 * 生成key
70 *</p>
71 *
72 * @author liuyang
73 * @date 2019-12-10 周二 11:22:27
74 * @return
75 */
76 private String genCurDayUsedCodeRedisKey() {
77 final String randomPrefix = "0922VerifySaleCode::";
78 return RedisKeyPrefixUtil.warp(randomPrefix + getYearDayStr());
79 }
80
81 /**
82 * 拼接年份+天数，如2019344
83 * @return
84 */
85 private String getYearDayStr() {
86 LocalDate localDate = LocalDate.now();
87 return localDate.getYear() + String.valueOf(localDate.getDayOfYear());
88 }
89
90 @Override
91 public void afterPropertiesSet() throws Exception {
92 VerifySaleGenerator.INSTANCE = this;
93 }
94 }
作者：LY不想说话74096链接：https://juejin.cn/post/6844904018355945485
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 标签：策略,int,32,核销,生成,new,ID,String From： https://www.cnblogs.com/h2285409/p/16908393.html