什么是分布式系统唯一ID

在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识。

如在金融、电商、支付、等产品的系统中，数据日渐增长，对数据分库分表后需要有一个唯一ID来标识一条数据或消息，数据库的自增ID显然不能满足需求，此时一个能够生成全局唯一ID的系统是非常必要的。

分布式系统唯一ID的特点

全局唯一性：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。
趋势递增：在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求。
信息安全：如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了。所以在一些应用场景下，会需要ID无规则、不规则。

同时除了对ID号码自身的要求，业务还对ID号生成系统的可用性要求极高，想象一下，如果ID生成系统瘫痪，这就会带来一场灾难。
由此总结下一个ID生成系统应该做到如下几点：

平均延迟和TP999延迟都要尽可能低；
可用性5个9；
高QPS。

分布式系统唯一ID实现方案

UUID

UUID是指在一台机器在同一时间中生成的数字在所有机器中都是唯一的。按照开放软件基金会(OSF)制定的标准计算，用到了以太网卡地址、纳秒级时间、芯片ID码和许多可能的数字
UUID由以下几部分的组合：

（1）当前日期和时间。
（2）时钟序列。
（3）全局唯一的IEEE机器识别号，如果有网卡，从网卡MAC地址获得，没有网卡以其他方式获得。
标准的UUID格式为：xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx (8-4-4-4-12)，以连字号分为五段形式的36个字符，示例：550e8400-e29b-41d4-a716-446655440000
Java标准类库中已经提供了UUID的API。

UUID.randomUUID();

优点

性能非常高：本地生成，没有网络消耗。

缺点

不易存储：UUID太长，16字节128位，通常以36长度的字符串表示，很多场景不适用。
信息不安全：基于MAC地址生成UUID的算法可能会造成MAC地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。
ID作为主键时在特定的环境会存在一些问题，比如做DB主键的场景下，UUID就非常不适用。

Twitter的snowflake

snowflake 是 Twitter 开源的分布式ID生成算法，是一种划分命名空间来生成ID的一种算法，结果是一个long型的ID。其核心思想是：把64-bit分别划分成多段。如下图所示：
snowflake id生成规则

1位标识符：始终是0，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0。
41位时间戳：41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截 )得到的值，这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的。
10位机器标识码：可以部署在1024个节点，如果机器分机房（IDC）部署，这10位可以由 5位机房ID + 5位机器ID 组成。
12位序列：毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号

优点

毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。
不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的。
可以根据自身业务特性分配bit位，非常灵活。

缺点

强依赖机器的时钟，如果服务器时钟回拨，会导致重复ID生成。
在分布式环境上，每个服务器的时钟不可能完全同步，有时会出现不是全局递增的情况。

snowflake Java实现

/**
 * Twitter_Snowflake<br>
 * SnowFlake的结构如下(每部分用-分开):<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
 * 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0<br>
 * 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)
 * 得到的值），这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序IdWorker类的startTime属性）。
 * 41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
 * 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId<br>
 * 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号<br>
 * 加起来刚好64位，为一个Long型。<br>
 * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，
 * 经测试，SnowFlake每秒能够产生26万ID左右。
 */
public class SnowflakeIdWorker {

    // ==============================Fields===========================================
    /** 开始时间截 (2015-01-01) */
    private final long twepoch = 1420041600000L;

    /** 机器id所占的位数 */
    private final long workerIdBits = 5L;

    /** 数据标识id所占的位数 */
    private final long datacenterIdBits = 5L;

    /** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /** 支持的最大数据标识id，结果是31 */
    private final long maxDatacenterId = -1L ^ (-1L << 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位(5+5+12) */
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    /** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /** 工作机器ID(0~31) */
    private long workerId;

    /** 数据中心ID(0~31) */
    private long datacenterId;

    /** 毫秒内序列(0~4095) */
    private long sequence = 0L;

    /** 上次生成ID的时间截 */
    private long lastTimestamp = -1L;

    //==============================Constructors=====================================
    /**
     * 构造函数
     * @param workerId 工作ID (0~31)
     * @param datacenterId 数据中心ID (0~31)
     */
    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;
    }

    // ==============================Methods==========================================
    /**
     * 获得下一个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 (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            //毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        //时间戳改变，毫秒内序列重置
        else {
            sequence = 0L;
        }

        //上次生成ID的时间截
        lastTimestamp = timestamp;

        //移位并通过或运算拼到一起组成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (datacenterId << datacenterIdShift) //
                | (workerId << workerIdShift) //
                | sequence;
    }

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

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

    //==============================Test=============================================
    /** 测试 */
    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(Long.toBinaryString(id));
            System.out.println(id);
        }
    }
}

数据库自增ID（Flicker）

主要思路是采用数据库自增ID + replace_into实现唯一ID的获取。

create table t_global_id(
    id bigint(20) unsigned not null auto_increment,
    stub char(1) not null default '',
    primary key (id),
    unique key stub (stub)
) engine=MyISAM;

# 每次业务可以使用以下SQL读写MySQL得到ID号
replace into t_golbal_id(stub) values('a');
select last_insert_id();

replace into跟insert功能类似，不同点在于：replace into首先尝试插入数据列表中，如果发现表中已经有此行数据（根据主键或唯一索引判断）则先删除，再插入。否则直接插入新数据。
当然为了避免数据库的单点故障，最少需要两个数据库实例，通过区分auto_increment的起始值和步长来生成奇偶数的ID。

比如有两台机器。设置步长step为2，Server1的初始值为1（1，3，5，7，9，11…）、Server2的初始值为2（2，4，6，8，10…）如下所示，为了实现上述方案分别设置两台机器对应的参数，Server1从1开始发号，Server2从2开始发号，两台机器每次发号之后都递增2。如下：

Server1：
auto-increment-increment = 2
auto-increment-offset = 1

Server2：
auto-increment-increment = 2
auto-increment-offset = 2

优点

简单。充分借助数据库的自增ID机制，可靠性高，生成有序的ID。

缺点

ID生成依赖数据库单机的读写性能。

依赖数据库，当数据库异常时整个系统不可用。

对于MySQL的性能问题，可以用如下方案解决：

在分布式环境中，我们可以部署N台数据库实例，每台设置成不同的初始值，自增步长为机器的台数。每台的初始值分别为1,2,3…N，步长为N。
MySQL数据库自增ID多机图

这种方案虽然解决了性能问题，但是也存在很大的局限性：

系统水平扩容困难：系统定义好步长之后，增加机器之后调整步长困难。如果要添加机器怎么办？假设现在只有一台机器发号是1,2,3,4,5（步长是1），这个时候需要扩容机器一台。可以这样做：把第二台机器的初始值设置得比第一台超过很多，比如14（假设在扩容时间之内第一台不可能发到14），同时设置步长为2，那么这台机器下发的号码都是14以后的偶数。然后摘掉第一台，把ID值保留为奇数，比如7，然后修改第一台的步长为2。让它符合我们定义的号段标准，对于这个例子来说就是让第一台以后只能产生奇数。扩容方案看起来复杂吗？貌似还好，现在想象一下如果我们线上有100台机器，这个时候要扩容该怎么做？简直是噩梦。
数据库压力大：每次获取一个ID都必须读写一次数据库。当然对于这种问题，也有相应的解决方案，就是每次获取ID时都批量获取一个区间的号段到内存中，用完之后再来获取。数据库的性能提高了几个量级。

美团的Leaf-segment

Leaf-segment 在使用数据库的方案上做了优化，利用proxy server批量获取，每次获取一段IDs(step决定大小)，然后把这段IDs作为id池缓存起来使用。用完之后再去数据库获取新的号段，从而大大的减轻数据库的压力。解决了原方案每次获取ID都得读写一次数据库，造成数据库压力大的问题。Leaf-segment的总体架构如下：

Leaf-segment

优点

Leaf服务可以很方便的线性扩展，性能完全能够支撑大多数业务场景。
ID号码是趋势递增的8byte的64位数字，满足上述数据库存储的主键要求。
容灾性高：Leaf服务内部有号段缓存，即使DB宕机，短时间内Leaf仍能正常对外提供服务。
可以自定义max_id的大小，非常方便业务从原有的ID方式上迁移过来。

缺点

ID号码不够随机，能够泄露发号数量的信息，不太安全。
TP999数据波动大，当号段使用完之后还是会hang在更新数据库的I/O上，tg999数据会出现偶尔的尖刺。
DB宕机会造成整个系统不可用。

Leaf-segment 后2点缺点，Leaf-segment做了双buffer优化，以及“一主两从”的高可用容灾。

美团的Leaf-snowflake

leaf-snowflake id生成规则

Leaf-snowflake 方案完全沿用snowflake方案的bit位设计，即是1+41+10+12的方式组装ID号。相比 snowflake，Leaf-snowflake做了以下2点优化：

使用Zookeeper持久顺序节点的特性自动对snowflake节点配置wokerID，一定程度的提高系统的伸缩性和容错性。
解决时钟回拨会可能导致生成重复的ID号的问题。

leaf-snowflake 架构图

Leaf-snowflake是按照下面几个步骤启动的：

启动Leaf-snowflake服务，连接Zookeeper，在leaf_forever父节点下检查自己是否已经注册过（是否有该顺序子节点）。
如果有注册过直接取回自己的workerID（zk顺序节点生成的int类型ID号），启动服务。
如果没有注册过，就在该父节点下面创建一个持久顺序节点，创建成功后取回顺序号当做自己的workerID号，启动服务。

微信的序列号生成器seqsvr

seqsvr 是微信的一个高可用、高可靠的序列号生成器，利用生成的序列号，实现终端与后台的数据增量同步机制。这套同步机制仍然在消息收发、朋友圈通知、好友数据更新等需要数据同步的地方发挥着核心的作用。seqsvr的架构可以分为两层，即StoreSvr和AllocSvr（存储层和缓存中间层）。架构如下图：

seqsvr序号生成器

从垂直方向看，AllocSvr负责直接为客户端分配sequence，而StoreSvr则负责当前最大sequence num的可靠存储（通过NRW实现）。这个角度看来，和美团点评的Leaf-segment是非常相似的。主要区别在于两点，第一是seqsvr产生的sequence是在UID（用户ID）之下的id，换言之——UID + sequence = 全局ID；第二点是seqsvr使用了NRW实现了数据存储的强一致性。

从水平方向看，seqsvr使用UID进行了水平切分，实现了负载均衡。对单一的一个set分析可知，AllocSvr可以完全以运行在内存中，而不用实现持久化。因为最恶劣的情况就是，AllocSvr中一部分id还没有被消费的情况下宕机了，重启之后又重新申请了一段id，所以有一部分id被跳过了。然而，微信的sequence num有64位，而且是位于UID之下的，所以跳过一段id完全可以接受。

所以，seqsvr的主要压力还是在StoreSvr，即使进行了Set切分，NRW存储模式依然还是要在吞吐量上付出代价。大概是经过了进一步的实验，seqsvr进行了进一步的优化——分段号共享存储。如下图所示，max_seq就是当前的最大序列号。一组用户共享一个max_seq，分组的方式依然是使用UID进行切分。这样一来，seqsvr中StoreSvr的压力变得更小了。举例来说，如果大家的操作频率是均等的，那么StoreSvr的写入压力降为切分之前的1 / N（N为分组内部用户的数目）。而且StoreSvr对数据的载入压力也降低为1 / N。

Redis生成唯一ID

Redis实现了一个原子操作INCR和INCRBY实现递增的操作。当使用数据库性能不够时，可以采用Redis来代替，同时使用Redis集群来提高吞吐量。

可以初始化每台Redis的初始值为1,2,3,4,5，然后步长为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

优点

不依赖于数据库，灵活方便，且性能优于数据库。
数字ID天然排序，对分页或者需要排序的结果很有帮助。

缺点

如果系统中没有Redis，还需要引入新的组件，增加系统复杂度。
需要编码和配置的工作量比较大。这个都不是最大的问题。

Zookeeper生成唯一ID

zookeeper主要通过其znode数据版本来生成序列号，可以生成32位和64位的数据版本号，客户端可以使用这个版本号来作为唯一的序列号。

很少会使用zookeeper来生成唯一ID。主要是由于需要依赖zookeeper，并且是多步调用API，如果在竞争较大的情况下，需要考虑使用分布式锁。因此，性能在高并发的分布式环境下，也不甚理想。