高性能分布式发号器(ID生成器)

分表分库的分布式应用通常需要用到 ID 生成器生成流水号（支付流水号，订单号等），又称为发号器，以标识数据的全局唯一，ID 全局不可重复。

需要特别注意的是发号器服务的高可用性和高性能。当业务严重依赖发号器服务时，发号器服务有可能成为整个系统的短板。

所以发号器服务需要高可用集群部署来保障高可用性，需要高性能以满足高并发的场景。

在分布式高并发环境，还需要使用全局唯一ID来实现数据的幂等性。一些大厂也有对发号器的描述，如 Meituan-Dianping / Leaf，baidu / uid-generator，twitter / snowflake。

基本特性

• 全局唯一：这是分布式环境下必须要保证的。
• 趋势递增：在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
• 单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求。
• 信息安全：若是ID连续，容易被恶意扒取；一些场景下需要无规则，不规则。
• 可反解：可直接从ID中识别出某些业务信息。例如 时间，业务类型等。
• 高性能：满足高并发环境下高性能要求。通过是多节点集群部署下的负载均衡实现。
• 高可用：满足高并发环境下的高可用。通常采用多节点分布式部署，而不是单点结构。
• 可伸缩：发号器部署可随着业务量的增减可灵活扩展或减少分布式节点。

可选方案

UUID

优点

• UUID 可以保证 ID 的唯一性，使用简单。
• 在内存中生成 ID，无网络消耗，性能非常好。
• 可以满足数据库变更情况下的数据迁移。

缺点

• UUID 比较长，占用空间大，会导致数据库性能下降；

• UUID 是无序字符串存储，会导致 B+树索引在写的时间有过多随机操作（连续的ID会产生部分顺序写）；由于写的时间不能产生有顺序的 append 操作，需要是行 insert 操作，将读取整个 B+ 树节点到内存，在插入这条记录后将整个节点写回磁盘，这种操作在记录占用空间比较大的性况下，性能下降明显。

• UUID 作为 DB 主键的场景下就非常不适用。

  例如：MySQL 官方明确建议主键要尽量越短越好，36字符长度的UUID不符合要求。

Snowflake

有这么一种说法，自然界中并会存在两片完全一样的雪花的。每一片雪花都拥有自己漂亮独特的形状、独一无二。雪花算法也表示生成的ID如雪花般独一无二，具有全局唯一性。

概述

Snowflake （雪花算法）是 Twitter 开源的自增 ID 算法。

Snowflake 整个结构是 64 位，在 Java 中可以使用 Long 型来接收。该算法实现基本就是二进制操作，单机每秒理论上最多可以生成 1024 * (2 ^ 12) ，也就是 419.4304‬ 万个 ID。

整体上按照时间自增排序。分布式环境下，不同机器，利用机器ID进行区分；同一台机器，获取ID 的方法加同步锁（synchronized）解决并发，且有时间戳比较，所以整个分布式系统内不会产生 ID 碰撞，内存生成效率高。

• 第一位：占 1bit ，最高位，始终是 0 表示正数。

• 时间戳：占 41bit，精确到毫秒，时间戳实际是自 1970/1/1 00:00:01 到 当前时间的时间戳差值，41位的时间戳可以使用 69 年（2^41 - 1 / (1000 x 60 x 60 x 24 x 365)）。

  String binaryString = Long.toBinaryString(System.currentTimeMillis());
  System.out.println(binaryString);
  System.out.println(binaryString.length());
  
  # 输出结果
  10111001010001101011001110111111100100000
  41

• 工作机器ID：占 10bit，分两段，5位 表示数据中心ID，5位表示工作节点ID，共可使用 1024 个节点。

• 最后12位：毫秒内的计数，（2^12，每个节点每毫秒可 产生4096个序列号）。

优点

• 在内存生成，高性能高可用，低延迟，全局唯一不重复。
• 按时间递增有序，插入索引树时性能较好。
• 纯数字组成，查询效率高，不依赖于数据库。

缺点

• 需要独立的开发和部署；强依赖于时钟，如果物理服务器异常出现时钟回拨（例如，物理服务器长时间运行，主板时时钟晶振异常），可能会出现重复ID。

• 雪花算法在单机系统上ID是递增的，但是在分布式系统多节点的情况下，所有节点的时钟并不能保证完全同步，所以有可能会出现不是全局递增的情况。

• 在分布式部署 + 配置中心统一管理配置文件的微服务架构中存在局限制，所有的实例共用同一份配置中心的配置文件，所以，机器码就不能在配置文件，如果放在启动引导配置文件 bootstrap.properties 中，则每部署一个实例，就要修改该配置文件中的机器码，就非常不灵活。

  可通过注册 Zookeeper 判断节点取出 workerID，并在本机文件系系统上缓存一个 workerID文件。

Java实现

可以参考 Twitter 原生的 scala 语言实现，以下是 Java 实现。

package com.springboot.demo.util;

public class SnowflakeIdWorker {

    /*开始时间戳*/
    private static final long twepoch = 1591532614070L;
    /*机器ID所占的位数*/
    private static final long workerIdBits = 5L;
    /*数据中心ID所占的位数*/
    private static final long datacenterIdBits = 5L;
    /*ID序列所占的位数*/
    private static final long sequenceBits = 12L;

    /*支持的最大机器ID,值为 31(负数以补码表示:最高位1表示负数,其余位取反码,再加1得到补码)*/
    private static final long maxWorkerId = -1L ^ (-1L << workerIdBits);
    /*支持的数据标识ID,值为 31*/
    private static final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
    /*生成序列的掩码,这里为 4095((0b111111111111=0xfff=4095))*/
    private static final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /*机器ID向左移12位*/
    private final long workerIdShift = sequenceBits;
    /*数据标识ID向左移17(12+5)位*/
    private final long datacenterIdShift = sequenceBits + workerIdBits;
    /*时间戳向左移22位(12+5+5)*/
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    /*工作机器ID(0-31)*/
    private long workerId;
    /*数据中心ID(0-31)*/
    private long datacenterId;
    /*毫秒内序列(0-4095)*/
    private long sequence = 0L;
    /*上次ID生成的时间戳*/
    private long lastTimeStamp = -1L;

    /*-------------------构造方法--------------------------------------------*/
    public SnowflakeIdWorker(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }

        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter id can't be greater than %d or less than 0", maxDatacenterId));
        }

        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }

    /*-------------------执行方法--------------------------------------------*/
    public synchronized long nextId() {
        long nowTimeStamp = nowTimeStamp();

        // 如果当前时间小于上一次ID生成的时间戳,说明存在时回退的问题,抛出异常
        if (nowTimeStamp < lastTimeStamp) {
            throw new RuntimeException(String.format("clock moved backwards.  refusing to generate id for %d milliseconds", lastTimeStamp - nowTimeStamp));
        }

        // 如果是同一时间生成,则进行毫秒内序列
        if (nowTimeStamp == lastTimeStamp) {

            /**
             * 序列+1,判断是否会超过最大值 4095 (位运算)
             * 4095 的二进制:0000 1111 1111 1111
             * 4096 的二进制:‭0001 0000 0000 0000‬
             * 二者进行 与 运算, 结果为 0
             * */
            sequence = (sequence + 1) & sequenceMask;

            // 毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一毫秒,获得新的时间戳
                nowTimeStamp = getNextMillis(lastTimeStamp);
            }
        } else {
            // 时间戳改变,毫秒内的序列重置
            sequence = 0L;
        }
        // 最近一次生成ID的时间戳
        lastTimeStamp = nowTimeStamp;
        // 使用毫秒差值,数据中心ID,工作机器ID,自增序列号拼接,移位运算得到一个 64 位的 ID
        return ((nowTimeStamp - twepoch)  << timestampLeftShift) |
                (datacenterId << datacenterIdShift) |
                (workerId << workerIdShift) |
                sequence;
    }

    /**
     * 阻塞到下一毫秒,直到获得新的时间戳
     *
     * @param lastTimeStamp
     * @return 当前时间戳
     */
    private long getNextMillis(long lastTimeStamp) {
        long nowTimeStamp = nowTimeStamp();
        // 循环等待下一秒
        while (nowTimeStamp <= lastTimeStamp) {
            nowTimeStamp = nowTimeStamp();
        }
        return nowTimeStamp;
    }

    /**
     * 返回以毫秒为单位的当前时间戳
     * @return
     */
    private long nowTimeStamp() {
        return System.currentTimeMillis();
    } 

    public static void main(String[] args) {
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
        for (int i = 0; i < 1000; i++) {
            long id = idWorker.nextId();
            System.out.println(id);
            //System.out.println(Long.toBinaryString(id));
        }
    }
}

时间戳+随机数

优点

1. 使用简单。
2. 内存生成，性能高。
3. 具有粗略的顺序。

缺点

1. 不能完全排除重复，不适用于超高并发的环境。

   通常是定义略有些复杂的规则来尽可能降低碰撞的概念，但又可能导致长度过长。

备注：经本地工作电脑测试，4核8线程，16G内存，单线程每毫秒平均可生成 600 个左右ID，每毫秒平均生成不重复的 ID 在 300 个左右。

数据库自增序列

用数据库自增字段生成的值做 ID，严重依赖数据库的支持。

优点

1. 使用简单，只要数据库支持，不需要额外开发，成本小。
2. 数字ID天然排序，数据库查询性能高，对分页或排序有帮助。
3. 主键字段类型通常使用 Long，无符号长整型最大值可达到 2 ^ 64 - 1 的值，基本可以满足常规系统的使用。

缺点

1. 不利于分表分库。
2. 在高并发环境下，存在数据库瓶颈且难于扩展。
3. 不同数据库的自增序列算法和实现不同，不利于数据库变更时的数据迁移。

集群方案

数据库集群部署情况下采用数据库自增序列生成ID，需要考虑自增的唯一性。

默认情况下，都是从 1 开始自增，多节点集群部署就会存在重复的问题，应该设置每个节点不同的自增步长。例如自增初始值和步长与机器数相等。

-- 查询自增的步长
SHOW VARIABLES LIKE 'auto_inc%'
-- 修改自增的步长
SET @@auto_increment_increment=10;    
-- 修改起始值
SET @@auto_increment_offset=5;

假设有 2 台 MySQL 数据库服务器节点，步长为 2：

• 节点 1 自增：1，3，5，7，9 …….
• 节点 2 自增：2，4，6，8，10 ……..

缺点：在最开始确定好集群数量，设置好每个节点的起始值和自增步长后，后面再想扩展扩节就极其不方便了，所有的节点的生成步长都得发生改变。

Redis 自增数字

Redis 提供的 INCR 和 INCRBY命令支持原子性，Redis 的单线程模式天然就是线程安全的，所以可以使用这两个命令实现递增数字。通常是自定义规则的数字拼接递增数字组成最终的 ID 或序列号。

优点

优点

1. Redis 单线程模式，具有并发安全性。
2. Redis 内存存储，高性能。
3. 不依赖于数据库，灵活方便。
4. 数字 ID 递增顺序，满足数据库查询、分页、排序对性能的要求。

缺点

1. 需要引入 Redis 组件，增加了系统复杂度。
2. 需要对的 ID 生成规则编码。
3. 支持过期时间，非常适合每天重新计数的流水号。
4. 连接和访问 Redis 服务产生了网络消耗。

开源方案

1. Leaf-美团点评分布式ID生成系统
2. 百度：uid-generator
3. 基于百度Uid-Generator改造使用Zookeeper生成机器码
4. vesta-id-generator
5. 基础美团Leaf，百度Uid-Generator，原生snowflake 整合：ecp-uid

相关参考

1. 美团技术团队官网
2. 雪花算法(snowflake) ：分布式环境，生成全局唯一的订单号
3. Twitter的分布式自增ID算法snowflake (Java版)
4. Snowflake算法实现详解
5. Shardingsphere > 分布式主键
6. 百度 Uid-Generator实现详解
7. 如何做一个靠谱的发号器
8. 分布式id生成器
9. 细聊分布式ID生成方法