阅读 213

一种短ID生成策略

一种短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监控如下:

image.png
批量生成一批(1000、10000)核销码,计算的平均时间约为0.5ms,这里不再截图了。特别注意的是,如果redis服务和应用服务不在同一服务器或网段,主要瓶颈为网络传输和抖动。

三、附件

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;
    }
}

复制代码
关注下面的标签,发现更多相似文章
评论