分布式全局唯一ID生成方案

在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识。对数据分库分表后需要有一个唯一ID来标识一条数据或消息，数据库的自增ID显然不能满足需求此时一个能够生成全局唯一ID的系统是非常必要的。概括下来，那业务系统对ID号的要求有哪些呢？

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

以业务端对订单号的需求为例：

• 订单号不能重复
• 订单号没有规则，即编码规则不能加入任何和公司运营相关的数据，外部人员无法通过订单ID猜测到订单量。不能被遍历。
• 订单号长度固定，且不能太长
• 易读，易沟通，不要出现数字字母换乱现象
• 能够快速生成

常见全局唯一ID方案：

数据库自增长ID

优点：

• 无需编码

缺点：

• 大表不能做水平分表，否则插入删除时容易出现问题
• 高并发下插入数据需要加入事务机制
• 在业务操作父、子表（关联表）插入时，先要插入父表，再插入子表

Redis自增长ID

Redis来生成分布式ID，其实和利用Mysql自增ID类似，可以利用Redis中的incr命令来实现原子性的自增与返回，比如：

127.0.0.1:6379> set seq_id 1     // 初始化自增ID为1
OK
127.0.0.1:6379> incr seq_id      // 增加1，并返回
(integer) 2
127.0.0.1:6379> incr seq_id      // 增加1，并返回
(integer) 3

使用Redis的效率是非常高的，但是要考虑持久化的问题。Redis支持RDB和AOF两种持久化的方式。

• RDB持久化相当于定时打一个快照进行持久化，如果打完快照后，连续自增了几次，还没来得及做下一次快照持久化，这个时候Redis挂掉了，重启Redis后会出现ID重复。
• AOF持久化相当于对每条写命令进行持久化，如果Redis挂掉了，不会出现ID重复的现象，但是会由于incr命令过得，导致重启恢复数据时间过长。

优点：

• 有序递增，可读性强。

缺点：

• 占用带宽，每次要向Redis进行请求。

时间戳+随机数

优点：

• 编码简单

缺点：

• 随机数存在重复问题，即使在相同的时间戳下。每次插入数据库前需要校验下是否已经存在相同的数值。

时间戳+会员ID

优点：

• 同一时间，一个用户不会存在两张订单

缺点：

• 会员ID也会透露运营数据，鸡生蛋，蛋生鸡的问题

UUID/GUID

UUID(Universally Unique Identifier)的标准型式包含32个16进制数字，以连字号分为五段，形式为8-4-4-4-12的36个字符，示例：550e8400-e29b-41d4-a716-446655440000，到目前为止业界一共有5种方式生成UUID，详情见IETF发布的UUID规范 A Universally Unique IDentifier (UUID) URN Namespace。

优点：

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

缺点：

• 用户不友好
• 不易于存储：UUID太长，16字节128位，通常以36长度的字符串表示，很多场景不适用。
• 信息不安全：基于MAC地址生成UUID的算法可能会造成MAC地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。
• ID作为主键时在特定的环境会存在一些问题，比如做DB主键的场景下，UUID就非常不适用：
  • MySQL官方有明确的建议主键要尽量越短越好，36个字符长度的UUID不符合要求。
  • 对MySQL索引不利：如果作为数据库主键，在InnoDB引擎下，UUID的无序性可能会引起数据位置频繁变动，严重影响性能。

UUID变种

UUID变种比较流行的是基于MySQL UUID的变种：timestamp + machine number + random，具体介绍见：GUID/UUID Performance Breakthrough

优点：

• 开发成本较低

缺点：

• 基于MySQL的存储过程，性能较差

另外，随着UUID_TO_BIN(str, swap_flag)方法的出现，以上实现方式已不太适用。

Snowflake

Snowflake是由Twitter开源的全局唯一ID生成方案。Twitter-Snowflake算法产生的背景相当简单，为了满足Twitter每秒上万条消息的请求，每条消息都必须分配一条唯一的id，这些id还需要一些大致的顺序（方便客户端排序），并且在分布式系统中不同机器产生的id必须不同。Snowflake算法核心把时间戳，工作机器id，序列号(毫秒级时间41位+机器ID 10位+毫秒内序列12位)组合在一起。

在上面的字符串中，第一位为未使用（实际上也可作为long的符号位），接下来的41位为毫秒级时间，然后5位datacenter标识位，5位机器ID（并不算标识符，实际是为线程标识），然后12位该毫秒内的当前毫秒内的计数，加起来刚好64位，为一个Long型。

除了最高位bit标记为不可用以外，其余三组bit占位均可浮动，看具体的业务需求而定。默认情况下41bit的时间戳可以支持该算法使用到2082年，10bit的工作机器id可以支持1023台机器，序列号支持1毫秒产生4095个自增序列id。下文会具体分析。

严格意义上来说工作机器id这个bit段的使用可以是进程级，机器级的话你可以使用MAC地址来唯一标示工作机器，工作进程级可以使用IP+Path来区分工作进程。如果工作机器比较少，可以使用配置文件来设置这个id是一个不错的选择，如果机器过多配置文件的维护是一个灾难性的事情。

这里的解决方案是需要一个工作id分配的进程，可以使用自己编写一个简单进程来记录分配id。

工作进程与工作id分配器只是在工作进程启动的时候交互一次，然后工作进程可以自行将分配的id数据落文件，下一次启动直接读取文件里的id使用。这个工作机器id的bit段也可以进一步拆分，比如用前5个bit标记进程id，后5个bit标记线程id之类。

序列号就是一系列的自增id（多线程建议使用atomic），为了处理在同一毫秒内需要给多条消息分配id，若同一毫秒把序列号用完了，则“等待至下一毫秒”。

Snowflake大致来说是一种以划分命名空间（UUID也算，由于比较常见，所以单独分析）来生成ID的一种算法，这种方案把64-bit分别划分成多段：timestamp + work number + seq number，分开来标示机器、时间等。

优点：

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

缺点：

• 强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。
• 需要引入zookeeper 和独立的snowflake专用服务器

具体实现除了官方的Scala版本外，还有以下选择：

• Java版：https://github.com/sumory/uc/blob/master/src/com/sumory/uc/id/IdWorker.java
• Go语言版：https://github.com/sumory/idgen
• Python语言版：https://github.com/erans/pysnowflake

Snowflake变种

snowflake的算法还是不错的，其实本身不复杂，复杂的是你客户端怎么用。遇到的问题如下：

• 代码部署在不同的服务器上，中间的机器ID如何设置，有没有更方便的获取机器ID的方式？
• 整个算法依赖时间的连续性，但是显示环境是线上服务器都开启了ntp，ntp情况下会出现时间倒退的问题。

Snowflake 生成的 unique ID 过程：

• 10 bits 的机器号, 在 ID 分配 Worker 启动的时候, 从一个 Zookeeper 集群获取 (保证所有的 Worker 不会有重复的机器号)
• 41 bits 的 Timestamp: 每次要生成一个新 ID 的时候, 都会获取一下当前的 Timestamp, 然后分两种情况生成 sequence number:
• 如果当前的 Timestamp 和前一个已生成 ID 的 Timestamp 相同 (在同一毫秒中), 就用前一个 ID 的 sequence number + 1 作为新的 sequence number (12 bits); 如果本毫秒内的所有 ID 用完, 等到下一毫秒继续 (这个等待过程中, 不能分配出新的 ID)
• 如果当前的 Timestamp 比前一个 ID 的 Timestamp 大, 随机生成一个初始 sequence number (12 bits) 作为本毫秒内的第一个 sequence number

整个过程中, 只是在 Worker 启动的时候会对外部有依赖 (需要从 Zookeeper 获取 Worker 号), 之后就可以独立工作了, 做到了去中心化.

异常情况讨论:

• 在获取当前 Timestamp 时, 如果获取到的时间戳比前一个已生成 ID 的 Timestamp 还要小怎么办? Snowflake 的做法是继续获取当前机器的时间, 直到获取到更大的 Timestamp 才能继续工作 (在这个等待过程中, 不能分配出新的 ID)

从这个异常情况可以看出, 如果 Snowflake 所运行的那些机器时钟有大的偏差时, 整个 Snowflake 系统不能正常工作 (偏差得越多, 分配新 ID 时等待的时间越久)。从 Snowflake 的官方文档 (https://github.com/twitter/snowflake/#system-clock-dependency) 中也可以看到, 它明确要求 “You should use NTP to keep your system clock accurate”. 而且最好把 NTP 配置成不会向后调整的模式. 也就是说, NTP 纠正时间时, 不会向后回拨机器时钟。

解决时间同步问题

为了解决上述的时间问题，可以采取的方案：

import java.security.SecureRandom;
 
/**
 * 自定义 ID 生成器
 * ID 生成规则: ID长达 64 bits
 * 
 * | 41 bits: Timestamp (毫秒) | 3 bits: 区域（机房） | 10 bits: 机器编号 | 10 bits: 序列号 |
 */
public class CustomUUID {
    // 基准时间
    private long twepoch = 1288834974657L; //Thu, 04 Nov 2010 01:42:54 GMT
    // 区域标志位数
    private final static long regionIdBits = 3L;
    // 机器标识位数
    private final static long workerIdBits = 10L;
    // 序列号识位数
    private final static long sequenceBits = 10L;
 
    // 区域标志ID最大值
    private final static long maxRegionId = -1L ^ (-1L << regionIdBits);
    // 机器ID最大值
    private final static long maxWorkerId = -1L ^ (-1L << workerIdBits);
    // 序列号ID最大值
    private final static long sequenceMask = -1L ^ (-1L << sequenceBits);
 
    // 机器ID偏左移10位
    private final static long workerIdShift = sequenceBits;
    // 业务ID偏左移20位
    private final static long regionIdShift = sequenceBits + workerIdBits;
    // 时间毫秒左移23位
    private final static long timestampLeftShift = sequenceBits + workerIdBits + regionIdBits;
 
    private static long lastTimestamp = -1L;
 
    private long sequence = 0L;
    private final long workerId;
    private final long regionId;
 
    public CustomUUID(long workerId, long regionId) {
 
        // 如果超出范围就抛出异常
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0");
        }
        if (regionId > maxRegionId || regionId < 0) {
            throw new IllegalArgumentException("datacenter Id can't be greater than %d or less than 0");
        }
 
        this.workerId = workerId;
        this.regionId = regionId;
    }
 
    public CustomUUID(long workerId) {
        // 如果超出范围就抛出异常
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0");
        }
        this.workerId = workerId;
        this.regionId = 0;
    }
 
    public long generate() {
        return this.nextId(false, 0);
    }
 
    /**
     * 实际产生代码的
     *
     * @param isPadding
     * @param busId
     * @return
     */
    private synchronized long nextId(boolean isPadding, long busId) {
 
        long timestamp = timeGen();
        long paddingnum = regionId;
 
        if (isPadding) {
            paddingnum = busId;
        }
 
        if (timestamp < lastTimestamp) {
            try {
                throw new Exception("Clock moved backwards.  Refusing to generate id for " + (lastTimestamp - timestamp) + " milliseconds");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
 
        //如果上次生成时间和当前时间相同,在同一毫秒内
        if (lastTimestamp == timestamp) {
            //sequence自增，因为sequence只有10bit，所以和sequenceMask相与一下，去掉高位
            sequence = (sequence + 1) & sequenceMask;
            //判断是否溢出,也就是每毫秒内超过1024，当为1024时，与sequenceMask相与，sequence就等于0
            if (sequence == 0) {
                //自旋等待到下一毫秒
                timestamp = tailNextMillis(lastTimestamp);
            }
        } else {
            // 如果和上次生成时间不同,重置sequence，就是下一毫秒开始，sequence计数重新从0开始累加,
            // 为了保证尾数随机性更大一些,最后一位设置一个随机数
            sequence = new SecureRandom().nextInt(10);
        }
 
        lastTimestamp = timestamp;
 
        return ((timestamp - twepoch) << timestampLeftShift) | (paddingnum << regionIdShift) | (workerId << workerIdShift) | sequence;
    }
 
    // 防止产生的时间比之前的时间还要小（由于NTP回拨等问题）,保持增量的趋势.
    private long tailNextMillis(final long lastTimestamp) {
        long timestamp = this.timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = this.timeGen();
        }
        return timestamp;
    }
 
    // 获取当前的时间戳
    protected long timeGen() {
        return System.currentTimeMillis();
    }
}

使用这种方法需要注意：

• 为了保持增长的趋势，要避免有些服务器的时间早，有些服务器的时间晚，需要控制好所有服务器的时间，而且要避免NTP时间服务器回拨服务器的时间。
• 在跨毫秒时，序列号总是归0，会使得序列号为0的ID比较多，导致生成的ID取模后不均匀，所以序列号不是每次都归0，而是归一个0到9的随机数。
• 使用这个CustomUUID类，最好在一个系统中能保持单例模式运行。

解决分布式部署

Snowflake 有一些变种，各个应用结合自己的实际场景对 Snowflake 做了一些改动。

Boundary flake

变化:

• ID 长度扩展到 128 bits
• 最高 64 bits 时间戳
• 然后是 48 bits 的 Worker 号 (和 Mac 地址一样长)
• 最后是 16 bits 的 Seq Number
• 由于它用 48 bits 作为 Worker ID，和 Mac 地址的长度一样，这样启动时不需要和 Zookeeper 通讯获取 Worker ID。做到了完全的去中心化。
• 基于 Erlang

它这样做的目的是用更多的 bits 实现更小的冲突概率, 这样就支持更多的 Worker 同时工作。同时每毫秒能分配出更多的 ID。

Simpleflake

Simpleflake 的思路是取消 Worker 号, 保留 41 bits 的 Timestamp, 同时把 sequence number 扩展到 22 bits。

Simpleflake 的特点：

• sequence number 完全靠随机产生 (这样也导致了生成的 ID 可能出现重复)
• 没有 Worker 号, 也就不需要和 Zookeeper 通讯, 实现了完全去中心化
• Timestamp 保持和 Snowflake 一致, 今后可以无缝升级到 Snowflake

Simpleflake 的问题就是 sequence number 完全随机生成, 会导致生成的 ID 重复的可能. 这个生成 ID 重复的概率随着每秒生成的 ID 数的增长而增长。

所以Simpleflake 的限制就是每秒生成的 ID 不能太多（最好小于 100次/秒, 如果大于 100次/秒的场景, Simpleflake 就不适用了，建议切换回 Snowflake）。

MongoDB ObjectID

MongoDB官方文档 ObjectID可以算作是和snowflake类似方法，通过“时间+机器码+pid+inc”共12个字节，通过4+3+2+3的方式最终标识成一个24长度的十六进制字符。相比snowflake长度及可读性要差一些。

百度 uid-generator

uid-generator使用的就是snowflake，只是在生产机器id，也叫做workId时有所不同。uid-generator中的workId是由uid-generator自动生成的，并且考虑到了应用部署在docker上的情况，在uid-generator中用户可以自己去定义workId的生成策略，默认提供的策略是：应用启动时由数据库分配。说的简单一点就是：应用在启动时会往数据库表(uid-generator需要新增一个WORKER_NODE表)中去插入一条数据，数据插入成功后返回的该数据对应的自增唯一id就是该机器的workId，而数据由host，port组成。对于uid-generator中的workId，占用了22个bit位，时间占用了28个bit位，序列化占用了13个bit位，需要注意的是，和原始的snowflake不太一样，时间的单位是秒，而不是毫秒，workId也不一样，同一个应用每重启一次就会消费一个workId。

美团 Leaf

美团的Leaf也是一个分布式ID生成框架。它非常全面，即支持号段模式，也支持snowflake模式。

号段模式可以理解成批量获取，比如DistributIdService从数据库获取ID时，如果能批量获取多个ID并缓存在本地的话，那样将大大提供业务应用获取ID的效率。比如DistributIdService每次从数据库获取ID时，就获取一个号段，比如(1,1000]，这个范围表示了1000个ID，业务应用在请求DistributIdService提供ID时，DistributIdService只需要在本地从1开始自增并返回即可，而不需要每次都请求数据库，一直到本地自增到1000时，也就是当前号段已经被用完时，才去数据库重新获取下一号段。

Leaf中的snowflake模式和原始snowflake算法的不同点，也主要在workId的生成，Leaf中workId是基于ZooKeeper的顺序Id来生成的，每个应用在使用Leaf-snowflake时，在启动时都会都在Zookeeper中生成一个顺序Id，相当于一台机器对应一个顺序节点，也就是一个workId。

Flickr的数据库自增

Flickr是用的一个叫做Ticket Servers的玩意，使用纯MySQL来实现的。

CREATE TABLE `Tickets64` (
  `id` bigint(20) unsigned NOT NULL auto_increment,
  `stub` char(1) NOT NULL default '',
  PRIMARY KEY  (`id`),
  UNIQUE KEY `stub` (`stub`)
) ENGINE=MyISAM

先插入一条记录，然后再用replace去获取这个id

REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();

优点：

• 非常简单，利用现有数据库系统的功能实现，成本小，有DBA专业维护。
• ID号单调自增，可以实现一些对ID有特殊要求的业务。

缺点：

• 强依赖DB，当DB异常时整个系统不可用，属于致命问题。配置主从复制可以尽可能的增加可用性，但是数据一致性在特殊情况下难以保证。主从切换时的不一致可能会导致重复发号。
• ID发号性能瓶颈限制在单台MySQL的读写性能。

对于MySQL性能问题，可用如下方案解决：在分布式系统中我们可以多部署几台机器，每台机器设置不同的初始值，且步长和机器数相等。比如有两台机器。设置步长step为2，TicketServer1的初始值为1（1，3，5，7，9，11…）、TicketServer2的初始值为2（2，4，6，8，10…）

Instagram的存储过程

Instagram的ID生成方式简单的描述为：41b ts + 13b shard id + 10b increment seq，

• 41 bits：Timestamp (毫秒)
• 13 bits：每个 logic Shard 的代号 (最大支持8 * 1024个logic Shards)
• 10 bits：sequence number，每个 Shard 每毫秒最多可以生成1024个ID

具体实现方式如下：

• 先把每个 Table 划分为多个逻辑分片（logic Shard），逻辑分片的数量可以很大，例如2000个逻辑分片
• 然后制定一个规则，规定每个逻辑分片被存储到哪个数据库实例上面；数据库实例不需要很多，例如对有 2 个 PostgreSQL 实例的系统（instagram 使用 PostgreSQL）可以使用奇数逻辑分片存放到第一个数据库实例，偶数逻辑分片存放到第二个数据库实例的规则
• 每个 Table 指定一个字段作为分片字段（例如对用户表可以指定 uid 作为分片字段）
• 插入一个新的数据时先根据分片字段的值,决定数据被分配到哪个逻辑分（logic Shard）
• 然后再根据 logic Shard 和 PostgreSQL 实例的对应关系, 确定这条数据应该被存放到哪台 PostgreSQL 实例上

生成 unique ID 时41 bits 的 Timestamp 和 Snowflake 类似，这哭主要介绍一下 13 bits 的 logic Shard 代号 和 10 bits 的 sequence number 怎么生成。

logic Shard 代号：

• 假设插入一条新的用户记录, 插入时, 根据 uid 来判断这条记录应该被插入到哪个 logic Shard 中.
• 假设当前要插入的记录会被插入到第 1341 号 logic Shard 中 (假设当前的这个 Table 一共有 2000 个logic Shard)
• 新生成 ID 的 13 bits 段要填的就是 1341 这个数字

sequence number 利用 PostgreSQL 每个 Table 上的 auto-increment sequence 来生成：

• 如果当前表上已经有 5000 条记录, 那么这个表的下一个 auto-increment sequence 就是 5001 (直接调用 PL/PGSQL 提供的方法可以获取到)
• 然后把这个 5001 对 1024 取模就得到了 10 bits 的 sequence number

Instagram 这个方案的优势在于：

• 利用 logic Shard 号来替换 Snowflake 使用的 Worker 号就不需要到中心节点获取 Worker 号，做到了完全去中心化
• 可以通过 ID 直接知道这条记录被存放在哪个 logic Shard 上
• 今后做数据迁移的时候, 也是按 logic Shard 为单位做数据迁移的,也不会影响到今后的数据迁移

详细介绍见：Sharding & IDs at Instagram

优点：

• 开发成本低

缺点：

• 基于postgreSQL的存储过程，通用性差