前言

全局唯一ID，用于唯一标识一个实体（用户、产品等）。在传统的单机架构下，一种常用的做法是使用数据库自增ID来作为主键，唯一标识一个实体。但是在分布式架构下，虽然可以设置自增起始值和自增步长来实现但是受限于业务规模，难以扩展，且受限于DB性能瓶颈。

现有的分布式全局唯一ID可大致分为如下三类：

UUID
基于DB
基于雪花ID(Snowflake)方案

需满足的条件

全局唯一：必须保证ID是全局性唯一的，基本要求
高性能：高可用低延时，ID生成响应要块，否则反倒会成为业务瓶颈
高可用：100%的可用性是骗人的，但是也要无限接近于100%的可用性
好接入：要秉着拿来即用的设计原则，在系统设计和实现上要尽可能的简单
趋势递增：最好趋势递增，这个要求就得看具体业务场景了，一般不严格要求

1.UUID

UUID （Universally Unique Identifier），通用唯一识别码的缩写。UUID是由一组32位数的16进制数字所构成，所以UUID理论上的总数为 16³²⁼²128，约等于 3.4 x 10^38。也就是说若每纳秒产生1兆个UUID，要花100亿年才会将所有UUID用完。

生成的UUID是由 8-4-4-4-12格式的数据组成，其中32个字符和4个连字符’ - '，一般我们使用的时候会将连字符删除。

优点

本地生成，无网络消耗

缺点

占用空间较大，不易存储，通常用varchar存储
无业务意义，完全是一串随机字符串
不是趋势自增，插入DB会引起B+树页分裂和节点分裂

2.MySQL自增ID

使用MySQL自增ID来作为全局唯一ID是一种常用做法

单机

单机下，直接设置从1开始自增auto_increment_offset=1，增量为1 auto_increment_increment=1，每次发号时，向DB插入一条数据，将主键作为ID

优点

实现简单

缺点

不满足高可用，DB有宕机风险

集群

既然单机存在宕机风险，那么部署一个MySQL集群呗，设置双主集群，两个节点都能发号。

MySQL A配置-发单号

auto_increment_offset=1
auto_increment_increment=2

MySQL B配置-发双号

auto_increment_offset=2
auto_increment_increment=2

如果后续还是扛不住并发，需要继续扩展，那就比较麻烦了。。。并且还存在着集群同步问题。

优点

解决DB单点问题

缺点

存在集群同步问题
不易扩展

3.基于Redis实现

Redis实现分布式唯一ID主要是通过提供像 INCR 和 INCRBY 这样的自增原子命令，由于Redis自身的单线程的特点所以能保证生成的 ID 是唯一有序的。但是单机存在性能瓶颈，无法满足高并发的业务需求，可以采用集群的方式来实现。

此外，高并发场景下，最好使用Lua脚本来进行编码，保证完全的原子性操作。

优点

ID自增，利于B+树索引
实现简单，性能较高

缺点

需引入Redis，提高系统复杂性

4.雪花算法

雪花算法是Twitter开源的基于系统时间戳的分布式ID方案，以划分命名空间的方式将64bit分割为多个部分。

第1位占用1bit，其值始终是0，可看做是符号位不使用
第2位开始的41位是时间戳，41-bit位可表示2^41个数，每个数代表毫秒，那么雪花算法可用的时间年限是(1L<<41)/(1000L360024*365)=69 年的时间
中间的10-bit位可表示机器数，即2^10 = 1024台机器，但是一般情况下我们不会部署这么台机器。如果我们对IDC（互联网数据中心）有需求，还可以将 10-bit 分 5-bit 给 IDC，分5-bit给工作机器。这样就可以表示32个IDC，每个IDC下可以有32台机器，具体的划分可以根据自身需求定义
最后12-bit位是自增序列，可表示2^12 = 4096个数。

以下是Java实现。其中nextId()是使用synchronized加锁的，虽然synchronized只在单实例下有效，在集群部署下，通过设置不同的worker id，也可以保证ID的全局唯一性。

/**
 * twitter的snowflake算法 -- java实现
 * https://github.com/beyondfengyu/SnowFlake/blob/master/SnowFlake.java
 * @author beyond
 * @date 2016/11/26
 */
public class SnowFlake {

    /**
     * 起始的时间戳
     */
    private final static long START_STMP = 1480166465631L;

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

    /**
     * 每一部分的最大值
     */
    private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);

    /**
     * 每一部分向左的位移
     */
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;

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

    public SnowFlake(long datacenterId, long machineId) {
        if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
            throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
        }
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0");
        }
        this.datacenterId = datacenterId;
        this.machineId = machineId;
    }

    /**
     * 产生下一个ID
     *
     * @return
     */
    public synchronized long nextId() {
        long currStmp = getNewstmp();
        if (currStmp < lastStmp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }

        if (currStmp == lastStmp) {
            //相同毫秒内，序列号自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //同一毫秒的序列数已经达到最大
            if (sequence == 0L) {
                currStmp = getNextMill();
            }
        } else {
            //不同毫秒内，序列号置为0
            sequence = 0L;
        }

        lastStmp = currStmp;

        return (currStmp - START_STMP) << TIMESTMP_LEFT //时间戳部分
                | datacenterId << DATACENTER_LEFT       //数据中心部分
                | machineId << MACHINE_LEFT             //机器标识部分
                | sequence;                             //序列号部分
    }

    private long getNextMill() {
        long mill = getNewstmp();
        while (mill <= lastStmp) {
            mill = getNewstmp();
        }
        return mill;
    }

    private long getNewstmp() {
        return System.currentTimeMillis();
    }

    public static void main(String[] args) {
        SnowFlake snowFlake = new SnowFlake(2, 3);

        for (int i = 0; i < (1 << 12); i++) {
            System.out.println(snowFlake.nextId());
        }

    }
}

优点

独立部署，不依赖其他组件
趋势递增
高性能
字段定义灵活

缺点

时钟回拨问题，会导致发号重复或者服务会处于不可用状态
ID字段结构暴露，容易暴露业务规模

针对时钟回拨问题的解决方案

抛出异常（时间被追回之前的这段时间服务不可用）
关闭机器时钟同步
保存过去一段时间内每台机器在当前这一毫秒产生的最大ID（max_id），如果发生回拨，则max_id+1即可
每次生成时，预留一些ID号段，发生回拨，将这些ID分配出去

实战应用

在之前神州信息分布式赛道中，我跟刘哥使用了雪花ID作为分布式ID方案。赛题给定的主键字段是20位字符型，由于设计之初考虑到了单表容量过大的问题，采用了分库分表策略，将2位库标识+4位表标识设计到ID前六位，还剩下14位可用。因此，我们提出了一种基于雪花算法的分布式ID方案。

ID设计

2位库标识+4位表标识+14位IceFlake ID

基于SnowFlake的IceFlake ID设计

64位long类型存储
低6位：序列号，可标识2^6=64个id
次低4位：实例id标识位，可标识2^4=16个实例
中间41位：毫秒级时间戳，可标识时间范围：2^41/1000/60/60/24/365=69年
剩余高位：0填充

最后，截取低52位，转为14位16进制比特位字符串（高位填充1个“0”），组成14位 Iceflake id

代码实现：

@Component
public class SnowFlakeIdUtils {

    // 2015-01-01
    private final long START_DATE = 1420041600000L;
    private final long NUM_WORKER_ID_BITS = 4L;
    // 序列号位数：6， 一个毫秒单位内可单个实例承受并发64个ID
    private final long NUM_SEQUENCE_ID_BITS = 6L;

    private final long NUM_WORKER_ID_SHIFTS = NUM_SEQUENCE_ID_BITS;
    private final long NUM_TIMESTAMP_ID_SHIFTS = NUM_SEQUENCE_ID_BITS + NUM_WORKER_ID_BITS;
    private final long SEQUENCE_MASK = ~(-1L << NUM_SEQUENCE_ID_BITS);

    // 集群部署，配置worker-id
    @Value("${worker-id}")
    private long workerId;
    private long sequenceId=0L;
    private long lastTimestamp=-1L;

    public synchronized String getSnowflakeId() {
        long time_stamp = getCurrentTimestamp();
        // TODO: 优化时钟回拨错误
        if ( time_stamp < lastTimestamp ) {
            throw new RuntimeException(
                    String.format("clock moved backward! Failed to generate Snowflake ID for %d millisecond...", lastTimestamp - time_stamp)
            );
        }
        // 如果是同一时间生成，则序列号+1
        if ( lastTimestamp == time_stamp ) {
            sequenceId = (sequenceId + 1) & SEQUENCE_MASK;
            // 序列溢出
            if ( sequenceId == 0 ) {
                time_stamp = tilNextMillis(lastTimestamp);
            }
        } else {
            // 否则，从0开始
            sequenceId = 0L;
        }
        lastTimestamp = time_stamp;
        // 往14位填充
        return String.format("%14s", Long.toHexString(
                ((time_stamp - START_DATE) << NUM_TIMESTAMP_ID_SHIFTS)
                        | (workerId << NUM_WORKER_ID_SHIFTS)
                        | sequenceId)
        ).replace(" ", "0");
    }

    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     * @param lastTimestamp
     * @return
     */
    protected long tilNextMillis(long lastTimestamp) {
        long time_stamp = getCurrentTimestamp();
        while ( time_stamp <= lastTimestamp ) {
            time_stamp = getCurrentTimestamp();
        }
        return time_stamp;
    }

    protected long getCurrentTimestamp() {
        return System.currentTimeMillis();
    }
}

分布式系统

分布式ID

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

MySQL中的「锁」与「事务」上一篇

「TOP K」问题的几种解法下一篇

「分布式ID」生成方案

前言