分布式全局唯一ID生成策略

一、背景

分布式系统中我们会对一些数据量大的业务进行分拆，如：用户表，订单表。因为数据量巨大一张表无法承接，就会对其进行分库分表。但一旦涉及到分库分表，就会引申出分布式系统中唯一主键ID的生成问题。

1.1 唯一`ID`的特性

全局唯一：整个系统ID唯一;
趋势有序： ID是数字类型，而且是趋势递增;ID简短，查询效率快。
高可用：ID是一条数据的唯一标识，如果ID生成失败，则影响很大，业务执行不下去；
信息安全：ID虽然趋势有序，但是不可以被看出规则，免得被爬取信息。

1.2 递增与趋势递增

种类	递增	趋势递增
区别	第一次生成的`ID`为`12`，下一次生成的`ID`是`13`，再下一次生成的`ID`是`14`。	在一段时间内，生成的`ID`是递增的趋势，如：在`【0-1000】`区间内的时候，`ID`生成有可能第一次是`12`，第二次是`10`，第三次是`14`。

二、方案

2.1 `UUID`

UUID全称:Universally Unique Identifier。标准型式包含32个16进制数字，以连字号分为五段，形式为8-4-4-4-12的36个字符，示例：9628f6e9-70ca-45aa-9f7c-77afe0d26e05。

优点：

代码实现简单;
本机生成，没有性能问题;
全球唯一的ID，所以迁移数据容易。

缺点：

每次生成的ID是无序的，无法保证趋势递增;
UUID的字符串存储，查询效率慢;
存储空间大;
ID本身无业务含义，不可读。

应用场景：

类似生成token令牌的场景;
不适用一些要求有趋势递增的ID场景,不适合作为高性能需求的场景下的数据库主键。

也有在线生成UUID的网站，如果你的项目上用到了UUID，可以用来生成临时的测试数据。www.uuidgenerator.net

2.2 `MySQL` 主键自增

利用了MySQL的主键自增auto_increment，默认每次ID加1。

优点：

数字化，ID递增;
查询效率高;
具有一定的业务可读。

缺点：

存在单点问题，如果MySQL挂了，就没法生成ID了;
数据库压力大，高并发抗不住。

2.3 `MySQL`多实例主键自增

这个方案就是解决MySQL的单点问题，在auto_increment基本上面，设置step步长

如上，每台的初始值分别为1,2,3...N，步长为N（这个案例步长为4）

优点：解决了单点问题;
缺点：一旦把步长定好后，就无法扩容；而且单个数据库的压力大，数据库自身性能无法满足高并发。
应用场景：数据不需要扩容的场景。

2.4 基于`Redis`实现

单机：Redis的incr函数在单机上是原子操作，可以保证唯一且递增。
集群：单机Redis可能无法支撑高并发。集群情况下，可以使用步长的方式。比如有5个Redis节点组成的集群，它们生成的ID分别为：

A: 1,6,11,16,21
B: 2,7,12,17,22
C: 3,8,13,18,23
D: 4,9,14,19,24
E: 5,10,15,20,25

优点：有序递增，可读性强。
缺点：占用带宽，每次要向Redis进行请求。

2.5 `SnowFlake` 方案

SnowFlake是twitter开源的分布式ID生成算法。

雪花ID结构

SnowFlake算法生成ID固定是一个long型的数字，一个long型占8个字节，也就是64个bit，原始SnowFlake算法中对于bit的分配如下图：

第一个bit位是标识部分，在Java中由于long的最高位是符号位，正数是0，负数是1，一般生成的ID为正数，所以固定为0。
时间戳部分占41bit，这个是毫秒级的时间，一般实现上不会存储当前的时间戳，而是时间戳的差值（当前时间-固定的开始时间），这样可以使产生的ID从更小值开始；41位的时间戳可以使用69年；
工作机器id占10bit，这里比较灵活，比如，可以使用前5位作为数据中心机房标识，后5位作为单机房机器标识，可以部署1024个节点。
序列号部分占12bit，支持同一毫秒内同一个节点可以生成4096个ID。

优点

毫秒数在高位，自增序列在低位，ID趋势递增。
以服务方式部署，可以做高可用。
根据业务分配bit位，灵活。

缺点

每台机器的时钟不同，当时钟回拨可能会发生重复ID；
当数据量大时，需要对ID取模分库分表，在跨毫秒时，序列号总是归0，会发生取模后分布不均衡。

三、优化方案之数据库自增方案

3.1、改造数据库主键自增

数据库的自增主键的特性，可以实现分布式ID，适合做userId，正好符合如何永不迁移数据和避免热点? 但这个方案有严重的问题：

一旦步长定下来，不容易扩容;
数据库压力山大。

为什么压力大？

因为我们每次获取ID的时候，都要去数据库请求一次。那我们可以不可以不要每次去取？

可以请求数据库得到ID的时候，可设计成获得的ID是一个ID区间段。

上图ID规则表含义：

id表示为主键，无业务含义;
biz_tag为了表示业务，因为整体系统中会有很多业务需要生成ID，这样可以共用一张表维护;
max_id表示现在整体系统中已经分配的最大ID;
desc描述;
update_time表示每次取的ID时间;

整体流程：

【用户服务】在注册一个用户时，需要一个用户ID；会请求【生成ID服务(是独立的应用)】的接口;
【生成ID服务】会去查询数据库，找到user_tag的id，现在的max_id为0，step=1000;
【生成ID服务】把max_id和step返回给【用户服务】；并且把max_id更新为max_id = max_id + step，即更新为1000;
【用户服务】获得max_id=0，step=1000;
这个用户服务可以用ID=【max_id + 1，max_id+step】区间的ID，即为【1，1000】;
【用户服务】会把这个区间保存到jvm中;
【用户服务】需要用到ID的时候，在区间【1，1000】中依次获取ID，可采用AtomicLong中的getAndIncrement方法;
如果把区间的值用完了，再去请求【生产ID服务】接口，获取到max_id为1000，即可以用【max_id + 1，max_id+step】区间的ID，即为【1001，2000】。
该方案就非常完美的解决了数据库自增的问题，而且可以自行定义max_id的起点，和step步长，非常方便扩容；
也解决了数据库压力的问题，因为在一段区间内，是在jvm内存中获取的，而不需要每次请求数据库。即使数据库宕机了，系统也不受影响，ID还能维持一段时间。

3.2 竞争问题

以上方案中，如果是多个用户服务，同时获取ID，同时去请求【ID服务】，在获取max_id的时候会存在并发问题。如:

用户服务A，取到的max_id=1000 ;用户服务B取到的也是max_id=1000，那就出现了问题，ID重复了。

解决方案是：加分布式锁，保证同一时刻只有一个用户服务获取max_id。

3.3 突发阻塞问题

因为竞争问题，所有只有一个用户服务去操作数据库，其他二个会被阻塞。出现的现象就是一会儿突然系统耗时变长，怎么去解决？

双buffer方案

流程如下：

当前获取ID在buffer1中，每次获取ID在buffer1中获取;
当buffer1中的ID已经使用到了100，也就是达到区间的10%;
达到了10%，先判断buffer2中有没有去获取过，如果没有就立即发起请求获取ID线程，此线程把获取到的ID，设置到buffer2中;
如果buffer1用完了，会自动切换到buffer2;
buffer2用到10%了，也会启动线程再次获取，设置到buffer1中;
依次往返。

3.4 小结

双buffer的方案就达到了业务场景用的ID，都是在jvm内存中获得的，从此不需要到数据库中获取了,数据库宕机时长长点儿也没太大影响了。
因为会有一个线程，会观察什么时候去自动获取。两个buffer之间自行切换使用，就解决了突发阻塞的问题。

四、雪花`ID`实现

在大厂里，其实并没有直接使用SnowFlake，而是进行了改造，因为SnowFlake算法中最难实践的就是工作机器id，原始的SnowFlake算法需要人工去为每台机器去指定一个机器id，并配置在某个地方从而让SnowFlake从此处获取机器id。但是在大厂里，机器是很多的，人力成本太大且容易出错，所以大厂对SnowFlake进行了改造。

4.1 美团（`Leaf`）

美团的Leaf就是一个分布式ID生成框架。它非常全面，即支持号段模式，也支持SnowFlake模式。Leaf 提供两种生成的ID的方式，你可以同时开启两种方式，也可以指定开启某种方式（默认两种方式为关闭状态）。

详见：Leaf 使用说明

4.2 我的实现

根据这个算法的逻辑，只需要将这个算法用Java语言实现出来，封装为一个工具方法，我们自己在各个业务应用可以直接使用该工具方法来获取分布式ID，只需保证每个业务应用有自己的工作机器ID即可，而不需要单独去搭建一个获取分布式ID的应用。

雪花ID工具类

public class SnowFlakeUtil {
    /**
     * 起始的时间戳:这个时间戳自己随意获取，比如自己代码的时间戳
     */
    private final static long START_TIMESTAMP = 1288834974657L;

    // 每一部分占用的位数
    /**
     * 序列号占用的位数
     */
    private final static long SEQUENCE_BIT = 12;
    /**
     * 机器标识占用的位数
     */
    private final static long MACHINE_BIT = 5;
    /**
     * 数据中心占用的位数
     */
    private final static long DATA_CENTER_BIT = 5;

    // 每一部分的最大值：先进行左移运算，再同-1进行异或运算；异或：相同位置相同结果为0，不同结果为1
    /**
     * 用位运算计算出最大支持的数据中心数量：31
     */
    private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATA_CENTER_BIT);

    /**
     * 用位运算计算出最大支持的机器数量：31
     */
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);

    /**
     * 用位运算计算出12位能存储的最大正整数：4095
     */
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);

    // 每一部分向左的位移
    /**
     * 机器标志较序列号的偏移量
     */
    private final static long MACHINE_LEFT = SEQUENCE_BIT;

    /**
     * 数据中心较机器标志的偏移量
     */
    private final static long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;

    /**
     * 时间戳较数据中心的偏移量
     */
    private final static long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT;

    /**
     * 数据中心
     */
    private static long datacenterId;
    /**
     * 机器标识
     */
    private static long machineId;
    /**
     * 序列号
     */
    private static long sequence = 0L;
    /**
     * 上一次时间戳
     */
    private static long lastStamp = -1L;

    /**
     * 此处无参构造私有，同时没有给出有参构造，在于避免以下两点问题：
     * 1、私有化避免了通过new的方式进行调用，主要是解决了在for循环中通过new的方式调用产生的id不一定唯一问题问题，因为用于			 记录上一次时间戳的lastStmp永远无法得到比对；
     * 2、没有给出有参构造在第一点的基础上考虑了一套分布式系统产生的唯一序列号应该是基于相同的参数
     */
    private SnowFlakeUtil() {

    }

    /**
     * 获得下一个ID(该方法是线程安全的)
     *
     * @return
     */
    public static synchronized long nextId() {
        /** 获取当前时间戳 */
        long currStamp = timeGen();

        /** 如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过，这时候应当抛出异常 */
         if (currStamp < lastStamp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }
        /** 如果是同一时间（相同毫秒内）生成的，则进行毫秒内序列 */
        if (currStamp == lastStamp) {
            //相同毫秒内，序列号自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //同一毫秒的序列数已经达到最大
            if (sequence == 0L) {
                /** 阻塞到下一个毫秒,获得新的时间戳赋值给当前时间戳 */
                currStamp = tilNextMillis();
            }
        } else {
            //时间戳改变，毫秒内序列号置为0
            sequence = 0L;
        }
        /** 当前时间戳存档记录，用于下次产生id时对比是否为相同时间戳 */
        lastStamp = currStamp;

        // 移位并通过或运算拼到一起组成64位的ID
        //时间戳部分
        return (currStamp - START_TIMESTAMP) << TIMESTAMP_LEFT
                // 数据中心部分
                | datacenterId << DATA_CENTER_LEFT
                // 机器标识部分
                | machineId << MACHINE_LEFT
                // 序列号部分
                | sequence;
    }

    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     *
     * @return 当前时间戳
     */
    private static long tilNextMillis() {
        long timestamp = timeGen();
        while (timestamp <= lastStamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    private static long timeGen() {
        return System.currentTimeMillis();
    }

}

**注意：**此处无参构造私有，同时没有给出有参构造，在于避免以下两点问题：

私有化避免了通过new的方式进行调用，主要是解决了在for循环中通过new的方式调用产生的ID不一定唯一问题问题，因为用于记录上一次时间戳的lastStamp永远无法得到比对；
没有给出有参构造在第一点的基础上考虑了一套分布式系统产生的唯一序列号应该是基于相同的参数。

测试方法

@Test
public void snowFlakeID() {
    Long uniqueId = SnowFlakeUtil.nextId();
    log.info("uniqueId:{}", uniqueId);
}

结果

20:39:02.121 [main] INFO cn.van.unique.id.UniqueIdTest - uniqueId:1203217335414947840

五、总结

5.1 其他实现方式

还有一些其他的ID生成方案，比如：

滴滴：时间+起点编号+车牌号;
淘宝订单：时间戳+用户ID
其他电商：时间戳+下单渠道+用户ID，有的会加上订单第一个商品的ID;
MongoDB 的ID：通过时间+机器码+pid+inc共12个字节，4+3+2+3的方式最终标识成一个24长度的十六进制字符。

5.2 示例源码

Gihub 示例源码

分布式全局唯一ID生成策略

一、背景

1.1 唯一`ID`的特性

1.2 递增与趋势递增

二、方案

2.1 `UUID`

2.2 `MySQL` 主键自增

2.3 `MySQL`多实例主键自增

2.4 基于`Redis`实现

2.5 `SnowFlake` 方案

三、优化方案之数据库自增方案

3.1、改造数据库主键自增

3.2 竞争问题

3.3 突发阻塞问题

3.4 小结

四、雪花`ID`实现

4.1 美团（`Leaf`）

4.2 我的实现

五、总结

5.1 其他实现方式

5.2 示例源码

5.3 参考文章

5.4 技术交流

分布式全局唯一ID生成策略

一、背景

1.1 唯一ID的特性

1.2 递增与趋势递增

二、方案

2.1 UUID

2.2 MySQL 主键自增

2.3 MySQL多实例主键自增

2.4 基于Redis实现

2.5 SnowFlake 方案

三、优化方案之数据库自增方案

3.1、改造数据库主键自增

3.2 竞争问题

3.3 突发阻塞问题

3.4 小结

四、雪花ID实现

4.1 美团（Leaf）

4.2 我的实现

五、总结

5.1 其他实现方式

5.2 示例源码

5.3 参考文章

5.4 技术交流

1.1 唯一`ID`的特性

2.1 `UUID`

2.2 `MySQL` 主键自增

2.3 `MySQL`多实例主键自增

2.4 基于`Redis`实现

2.5 `SnowFlake` 方案

四、雪花`ID`实现

4.1 美团（`Leaf`）