怎样生成全局唯一流水号?UUID、自增主键,你已经Out啦,快来学习定制化雪花算法。

怎样生成全局唯一流水号?UUID、自增主键,你已经Out啦,快来学习定制化雪花算法。

敲得码黛 231 2021-06-10

前言

流水号是每个系统永远都绕不开的一个话题,如订单系统中的订单号,物流系统的运单号、银行系统的业务单号等等,不难发现这些单号虽然叫法不一样,但都有着一些相同的共性,那就是全局唯一性。除此之外,一个设计良好的流水号生成规则还应该包含如下特性:

  • 全局唯一性:在整个系统中唯一,可以通过单号直接定位到具体数据
  • 可读性:能够直接从单号上获取一些基本信息
  • 可扩展性:支持海量id,当应用扩展时可以做到平滑升级
  • 递增趋势:需要根据业务或时间呈递增趋势
  • 不可推测性:使用户无法猜测下一个或上一个订单号是什么
  • 高性能:流水号生成速度要快,不能成为业务瓶颈
  • 高可用:流水号生成必须要稳定,不能影响业务发展

背景

因为最近要做新的支付系统,而旧系统的订单号生成规则略有缺陷,所以老大让我设计一个新的订单号生成规则,于是我基于“内事不决问百度,外事不决问谷歌”的原则了解到目前常见的流水号生成方案有如下几种:数据库自增流水号、UUID流水号、雪花算法流水号。

数据库自增流水号、uuid流水号

数据库自增流水号、uuid流水号应该是最简单的两种实现方案了,根据之前提到的特性来简单分析一下这两方案的优缺点。

数据库自增流水号示例:1000001、1000002、1000003.

uuid流水号示例:59ced782-6000-4ca5-969d-ad99d11ccc54、fba05087-e6a0-4cb9-8bdc-7fa36ecadd92

全局唯一性可读性可扩展性递增趋势不可推测性高性能高可用
数据库自增流水号XXX
UUIDXX

数据库自增流水号解读:

数据库自增流水号由数据库生成,使用起来非常简单,递增趋势,性能及可用性都依赖于底层数据库,弊端也很明显:无可读性、扩展性差(指分库分表),而且最大的问题是可推测的,用户完全可以通过一个订单号推测出上一个订单号。(不推荐)

UUID流水号解读:

UUID也是一种算法,且具有很多个版本。在Java中通过UUID.randomUUID()就可以生成一个全局唯一的流水号,由于不需要依赖第三方类库,因此扩展性、性能、可用性都还可以,但是它也存在着致命的缺陷:如果在mysql中用UUID作为主键,由于它是无序的,所以在写入时可能会产生大量的随机IO及页分裂等问题,影响数据库性能。其次uuid是字符串类型的数据,也占用更大的储存空间 (不推荐)

优化建议:如果采用uuid建议删除中间的“-”减少字符长度,同时还可以将uuid转为hex进行使用

雪花算法流水号(SnowFlake )

SnowFlake 算法,是Twitter 开源的分布式id生成算法。其核心思想是:使用一个64bit的long 型数字作为全局唯一id,它将64bit的long类型划分为5个部分,每个部分表示不同的意义,最终合并成一个long类型全局唯一id,雪花算法划分规则如下

  • 因为计算机中规定了二进制数的第一位是符号位,0表示正数,1表示负数。很明显我们不需要负的流水号,因此64bit中的第一位表示为0
  • 第二个部分是由41bit的时间戳组成。(这也是雪花算法递增的原因)
  • 第三部分是一个5bit的机房标识,可以标识出这个id是由那个机房产生的
  • 第四部分是一个5bit的机器标识,可以标识出这个id是由那个机器产生的
  • 最后一部分是由12bit组成的序号,当一台机器上统一毫秒产生了多个id时,通过这个序号进行累加

雪花算法原本是Twitter用Scala写的,开源后网上也出现了很多Java的船新版本,具体实现随便去百度翻一翻就有了。

雪花算法流水号示例:1402972067925639168、1402972117498118144

全局唯一性可读性可扩展性递增趋势不可推测性高性能高可用
雪花算法X

雪花算法流水号解读:

雪花算法生成的是一个19位long类型流水号,除了可读性以外的其他特性基本都是可以满足的,我刚开始也是采用的雪花算法 (可以使用)

注意点1:单机环境服务器时钟发生倒退时,会存在流水号重复的风险

注意点2:集群环境时使用雪花算法需要为每一台机器设置不同的机器号,否则会存在单号重复的风险

定制化雪花算法

系统开发完成在测试环境跑了两天后,我觉得雪花算法生成的订单号还是不太理想,原因主要有两方面

  • 1、雪花算法生成的订单号不可读,单从订单号看不出任何有用的信息
  • 2、如果后期需要将应用扩展为集群环境,怎样在不更改代码的前提下为每一个应用设置不同的机器标识也是一个棘手的问题。

我拿出手机观察了一下早上买包子时的两个支付宝订单号:2021060222001434331413012752、2021060322001434331413013303,很明显前面的20210602是订单日期,我顿时心生一计:能不能仿照雪花算法的思想实现一套类似于支付宝的这种订单号呢?于是诞生了如下代码

import java.math.BigInteger;
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 基于雪花算法的思想定制化的一个id规则生成器
 *
 * 方案一:
 * 17位时间戳 + 3位序号 + 2位随机数 + 2位机器号  String类型  mysql存储用varchar     支持1000000QPS
 *
 * 方案二:
 * 14位时间戳 + 2位序号 + 2位随机数 + 1位机器号  Long类型  采用bigint类型存取      支持100QPS
 *
 * @author hcq
 * @date 2021/6/10 20:50
 */
public class IdGenerator {

    private final long workerId;

    private final int seqBit;

    private final int workBit;

    private final int randomBit;

    private long lastTimestamp = 0L;

    private long sequence = 0L;

    private static final BigInteger UNIT = new BigInteger("10");

    private final static DateTimeFormatter FORMAT = DateTimeFormatter.ofPattern("yyyyMMddHHmmssSSS");

    /**
     * @param workerId   机器序列号
     * @param workBit 机器序列号位数
     * @param seqBit 序列号位数
     * @param randomBit 随机数位数
     */
    public IdGenerator(long workerId, int seqBit, int workBit, int randomBit) {
        this.workerId = workerId;
        this.seqBit = seqBit;
        this.workBit = workBit;
        this.randomBit = randomBit;
        int maxValue = (UNIT.pow(workBit).intValue() - 1);
        if (workerId > maxValue || workerId < 0) {
            throw new IllegalArgumentException(String.format("workerId不能大于[%d],且不能小于0", maxValue));
        }
    }

    /**
     * 获取下一个ID
     */
    public synchronized String nextId() {
        long timestamp = now();

        if (timestamp < lastTimestamp) {
            throw new RuntimeException(String.format("时钟倒退[%s]ms", lastTimestamp - timestamp));
        }

        if (lastTimestamp == timestamp) {
            sequence = sequence + 1;
            // 当前毫秒内计数满了,则等待下一毫秒
            if (sequence >  (UNIT.pow(seqBit).intValue()-1)) {
                timestamp = nextMillis(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }
        lastTimestamp = timestamp;

        int random = ThreadLocalRandom.current().nextInt(0, UNIT.pow(randomBit).intValue());
        return String.format("%017d", timestamp) +
                String.format("%0"+seqBit+"d", sequence) +
                String.format("%0"+randomBit+"d", random) +
                String.format("%0"+workBit+"d", workerId) ;
    }

    private long nextMillis(final long lastTimestamp) {
        long timestamp = this.now();
        while (timestamp <= lastTimestamp) {
            timestamp = this.now();
        }
        return timestamp;
    }

    private long now() {
        LocalDateTime dateTime = LocalDateTime.now();
        return Long.parseLong(dateTime.format(FORMAT));
    }

    public static void main(String[] args) {
        // 方案一
        IdGenerator wo = new IdGenerator(1, 3, 2,2);
        System.out.println(wo.nextId());
    }
}

方案一:生成的Id流水号示例:202106102155286780008401、202106102158223300001801、202106102158281530004801

方案二:生成的Id流水号示例:2021061022021200331、2021061022021800971、2021061022022400441

定制化雪花算法解读:

虽然我这个定制化的雪花算法优化了雪花算法不可读的弊端,但是方案一生成的雪花ID有24位,这也就意味着在Java中只能用String或者BigInteger来存储,在Mysql中则需要用25个字节长度的varchar类型来存储,而mysql中bigint类型才只占用8个字节而已,因此才衍生出19位长度的第二种方案、如果系统业务量不是很大的情况下还是建议优先使用方案二。(推荐使用)

优化建议一:日期20210610可以优化为210610,节省的两个位置,随机数让出一位,然后将日期精确到毫秒

优化建议二:日期让出两位补给序号位

方案对比

全局唯一性可读性可扩展性递增趋势不可推测性
数据库自增流水号XXX
UUIDXX
雪花算法X
定制化雪花算法

自动注册机器号

回到刚才定制化雪花算法的第二个问题:如果后期需要将应用扩展为集群环境,怎样在不更改代码的前提下为每一个应用设置不同的机器标识?

我初步的想法是通过第三方的存储介质(mysql、redis、zk等等)来实现应用自动注册并获取机器号的方式,例如在应用启动的时候,向mysql中写入一条数据记录ip地址,同时借助mysql的自增id作为机器号来初始化雪花算法组件。

结尾

太晚了,明天还要搬砖,今天就先写到这里吧,后面准备写一个通用的SpringBootStart,这个功能后续应该也会集成进去,到时候再来填坑(下次一定)

img


# 雪花算法 # 分布式id生成规则