一种短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个订单已经不错了，测试代码如下：
public static void main(String[] args) {
final int batch = 100;
List<BigDecimal> statics = new ArrayList<>(batch);
int conflictSum = 0;
final int size = 100000;
for (int j = 0; j < batch; j++) {
Set<String> hashSet = new HashSet<>(size);
for (int i = 0; i < size; i++) {
String code = genVerifyCode();
hashSet.add(code);
}
int conflict = size - hashSet.size();
conflictSum += conflict;
statics.add(new BigDecimal(conflict).divide(new BigDecimal(size)));
}
System.out.println(batch + "轮测试，每轮随机生成" + size + "个核销码的平均冲突率为:" + new BigDecimal(conflictSum)
.divide(new BigDecimal(batch * size)));
statics.forEach(System.out::println);
}
d) 性能测试
经测试发现，如果redis服务跟应用服务在同一服务器下，单次生成耗时平均在0.2~0.8ms之间波动，用arthas监控如下：
三、附件
package com.shared.common.support.util;
import com.github.rxyor.common.util.lang2.RadixUtil;
import java.time.LocalDate;
import org.apache.commons.lang3.RandomUtils;
/**
*<p>
* 核销码生成工具类，目前核销码是8位，1位标识年份距2019年的偏移量，2位标识
* 当天是今天的第几天，5位可以由0~32^5-1的随机INT值转换为指定字符的32进制标识，
* 年份天数标识放在一起过于明显，分散到下标为1,3,5位置。经过测试，10W个核销码，
* 冲突率为150/10W, 1W个核销码冲突率几乎为0
*</p>
*
* @author
* @date 2019/12/10 周二 10:22:00
* @since 1.0.0
*/
public class VerifySaleCodeUtil {
/**
* 核销码表示字符，0~9,A~Z，去除0、O、I、L 4个易混淆的字符还是32位
*/
public final static char[] DIGITS = {
'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'};
/**
* 开始年份，用户计算年份偏移量
*/
public final static int BEGIN_YEAR = 2019;
/**
* 随机位由5位字符表示
*/
public final static int RANDOM_LEN = 5;
/**
* 5为32进制能表示的最大无符号整数为32^5-1
*/
private final static int MAX_RANDOM_INT = (int) (Math.pow(DIGITS.length, RANDOM_LEN) - 1);
private static final RadixUtil INSTANCE = RadixUtil.builder().digits(DIGITS).build();
/**
*<p>
*生成一个核销码
*</p>
*
* @author
* @date 2019-12-10 周二 10:35:16
* @return
*/
public static String genVerifySaleCode() {
LocalDate localDate = LocalDate.now();
//年份偏移量字符表示
char yearChar = DIGITS[Math.abs(localDate.getYear() - BEGIN_YEAR)];
//一年的第几天32进制字符表示
String dayOfYearString = INSTANCE.convert2String(localDate.getDayOfYear());
//32*32=1024>366, 2位即可表示天的偏移量, 不够2位补32进制第0位字符
if (dayOfYearString.length() == 1) {
dayOfYearString = DIGITS[0] + dayOfYearString;
}
String randomCode = genRandomCode();
StringBuilder verifyCode = new StringBuilder(randomCode);
//sb式混淆
//下标1位置插入年份偏移标识
verifyCode.insert(1, yearChar);
//下标3位置插入天偏移标识第1位
verifyCode.insert(3, dayOfYearString.charAt(0));
//下标5位置插入天偏移标识第2位
verifyCode.insert(5, dayOfYearString.charAt(1));
return verifyCode.toString();
}
/**
*生成（0~32^5-1）之间的随机整数，并转换为指定表示字符的32进制
* @return
*/
private static String genRandomCode() {
final int random = RandomUtils.nextInt(0, MAX_RANDOM_INT);
String randomCode = INSTANCE.convert2String(random);
StringBuilder sb = new StringBuilder();
//不足5位，补齐5位
for (int i = randomCode.length(); i < RANDOM_LEN; i++) {
sb.append(DIGITS[0]);
}
return sb.toString() + randomCode;
}
}
@Slf4j
@Component
public class VerifySaleGenerator implements InitializingBean {
private static final ExecutorService THREAD_POOL;
private static VerifySaleGenerator INSTANCE;
@Autowired
private RedissonClient redissonClient;
/**
* 创建线程池
*/
static {
//用于设置key过期的线程池，队列容量不需要那么长，多余的任务丢弃即可
THREAD_POOL = new ThreadPoolExecutor(
SystemConst.AVAILABLE_PROCESSORS, SystemConst.AVAILABLE_PROCESSORS,
0L, TimeUnit.SECONDS, new LinkedBlockingQueue<Runnable>(8),
new CarpThreadFactory(), new CarpDiscardPolicy());
}
private VerifySaleGenerator() {
}
public static VerifySaleGenerator instance() {
return INSTANCE;
}
/**
*<p>
*生成核销码
*</p>
*
* @author liuyang
* @date 2019-12-10 周二 11:21:44
* @return
*/
public String generate() {
final String key = genCurDayUsedCodeRedisKey();
RSet<String> set = redissonClient.getSet(key);
if (set == null) {
throw new RedisException("redisson client初始化失败");
}
boolean exist = true;
String verifySaleCode = null;
int count = 0;
try {
while (exist) {
verifySaleCode = VerifySaleCodeUtil.genVerifySaleCode();
exist = !set.add(verifySaleCode);
count++;
if (count > 10) {
throw new BizException("生成核销码冲突次数超过阈值");
}
}
} finally {
THREAD_POOL.submit(() -> {
if (set.isExists()) {
set.expire(25 - LocalDateTime.now().getHour(), TimeUnit.HOURS);
}
});
}
return verifySaleCode;
}
/**
*<p>
* 生成key
*</p>
*
* @author liuyang
* @date 2019-12-10 周二 11:22:27
* @return
*/
private String genCurDayUsedCodeRedisKey() {
final String randomPrefix = "0922VerifySaleCode::";
return RedisKeyPrefixUtil.warp(randomPrefix + getYearDayStr());
}
/**
* 拼接年份+天数，如2019344
* @return
*/
private String getYearDayStr() {
LocalDate localDate = LocalDate.now();
return localDate.getYear() + String.valueOf(localDate.getDayOfYear());
}
@Override
public void afterPropertiesSet() throws Exception {
VerifySaleGenerator.INSTANCE = this;
}
}
