架构设计——ID生成器「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

一、分布式ID发号器 

要求很明确：不同机器同一时间生成不同ip；同一机器不同时间生成不同IP;

所以根据需求，可选变量有： 机器（网卡、IP）+时间，随机数

二、Why not UUID？

UUID的实现：算法的核心思想是结合机器的网卡、当地时间、一个随机数来生成UUID。

优势：保证唯一性；本地调用，不需要rpc

UUID的缺陷：

1.UUID较长，占用内存空间；往往用字符串表示，作为主键建立索引查询效率低，常见优化方案为“转化为两个uint64整数存储”或者“折半存储”（折半后不能保证唯一性）

2.不具有有序性，无法保证趋势递增

三、依赖DB自增可行么？

实现：自增+设定步长；8个服务节点8个实例（类似取模）；

缺陷：

1.不利于服务节点扩充；服务节点固定，步长固定，难以进行水平服务节点的扩展。

2.依赖DB，对数据库造成额外压力

四.全局唯一ID生成器如何设计？考量因素有哪些

1.全局唯一；有序性（不一定连续，但趋势递增）；可反解信息；

2.业务性能要求：高性能、高可用

3.接入方式：嵌入式、中心服务发布、rest发布模式

设计一 ：ID数据结构

64位

1.机器ID 10位；2的10次方最多可支持1k+台机器；如果每台机器TPS为1W/s,10台服务器则可以有10W/s的TPS，基本满足大部分业务要求。

2.序列号 10位或20位；同理，计算2的20次方，每秒平均可产生百万个ID

3.时间戳 30或40位（分别对应秒级、毫秒级）-时间保证趋势递增

其他可根据业务特点，加上定制的不同生产方式（pom、rest）或版本信息

设计二 并发

为支持大量并发的网络请求，ID生成服务一般采用多线程支持，对于竞争时间和序列（time sequence）采用juc中ReentrantLock或synchronized或atomic变量支持（推荐）。

实现

1.定义id实体结构（机器+时间+种子（生成随机数））

//时间戳
private Long time;
//序列号
private Integer sequence;
//生成随机数的种子
private Integer seed;
//机器ip
private Integer clusterIp;

2.根据结构获取对应请求数据，组装实体数据（获取时间戳（毫秒或秒级）os获取本机ip、mac等数据），生成一个不重复的id

//synch保证线程安全
public synchronized long getId()

计算（左移拼装，）【时间戳-初始时间】左移两位集群ip-sequence

3.解析ip，获取对应机器ip、时间戳等信息，则右移取指定位即可

五、Twitter的snowflake算法

Twitter 利用 zookeeper 实现了一个全局ID生成的服务 Snowflake：https://github.com/twitter-archive/snowflake

ID组成：

• 1位符号位：

由于 long 类型在 java 中带符号的，最高位为符号位，正数为 0，负数为 1，且实际系统中所使用的ID一般都是正数，所以最高位为 0。

• 41位时间戳（毫秒级）：

需要注意的是此处的 41 位时间戳并非存储当前时间的时间戳，而是存储时间戳的差值（当前时间戳 – 起始时间戳），这里的起始时间戳一般是ID生成器开始使用的时间戳，由程序来指定，所以41位毫秒时间戳最多可以使用 (1 << 41) / (1000x60x60x24x365) = 69年。

• 10位数据机器位：

包括5位数据标识位和5位机器标识位，这10位决定了分布式系统中最多可以部署 1 << 10 = 1024 s个节点。超过这个数量，生成的ID就有可能会冲突。

• 12位毫秒内的序列：

这 12 位计数支持每个节点每毫秒（同一台机器，同一时刻）最多生成 1 << 12 = 4096个ID

加起来刚好64位，为一个Long型。

• 优点：高性能，低延迟，按时间有序，一般不会造成ID碰撞
• 缺点：需要独立的开发和部署，依赖于机器的时钟

实现：

public class IdWorker {
    /**
     * 起始时间戳 2017-04-01
     */
    private final long epoch = 1491004800000L;
    /**
     * 机器ID所占的位数
     */
    private final long workerIdBits = 5L;
    /**
     * 数据标识ID所占的位数
     */
    private final long dataCenterIdBits = 5L;
    /**
     * 支持的最大机器ID,结果是31
     */
    private final long maxWorkerId = ~(-1L << workerIdBits);
    /**
     * 支持的最大数据标识ID,结果是31
     */
    private final long maxDataCenterId = ~(-1 << dataCenterIdBits);
    /**
     * 毫秒内序列在id中所占的位数
     */
    private final long sequenceBits = 12L;
    /**
     * 机器ID向左移12位
     */
    private final long workerIdShift = sequenceBits;
    /**
     * 数据标识ID向左移17(12+5)位
     */
    private final long dataCenterIdShift = sequenceBits + workerIdBits;
    /**
     * 时间戳向左移22(12+5+5)位
     */
    private final long timestampShift = sequenceBits + workerIdBits + dataCenterIdBits;
    /**
     * 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095)
     */
    private final long sequenceMask = ~(-1L << sequenceBits);
    /**
     * 数据标识ID（0～31）
     */
    private long dataCenterId;
    /**
     * 机器ID（0～31）
     */
    private long workerId;
    /**
     * 毫秒内序列（0～4095）
     */
    private long sequence;
    /**
     * 上次生成ID的时间戳
     */
    private long lastTimestamp = -1L;

    public IdWorker(long dataCenterId, long workerId) {
        if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
            throw new IllegalArgumentException(String.format("dataCenterId can't be greater than %d or less than 0", maxDataCenterId));
        }
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        this.dataCenterId = dataCenterId;
        this.workerId = workerId;
    }

    /**
     * 获得下一个ID (该方法是线程安全的)
     * @return snowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();
        //如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过,这个时候应当抛出异常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }
        //如果是同一时间生成的，则进行毫秒内序列
        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & sequenceMask;
            //毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一个毫秒,获得新的时间戳
                timestamp = nextMillis(lastTimestamp);
            }
        } else {//时间戳改变，毫秒内序列重置
            sequence = 0L;
        }
        lastTimestamp = timestamp;
        //移位并通过按位或运算拼到一起组成64位的ID
        return ((timestamp - epoch) << timestampShift) |
                (dataCenterId << dataCenterIdShift) |
                (workerId << workerIdShift) |
                sequence;
    }

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

    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    protected long nextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = lastTimestamp;
        }
        return timestamp;
    } 
}

实现注意点：

1.由于存在对时进行修改，snowflake算法应对时钟回拨的做法是直接抛出异常。

2.其次是12位序列号溢出的问题，即1ms内请求生成的ID个数超过了2的12次方=4096个id。snowflake算法对此的做法是，等到下一ms再生成ID。