分布式全局唯一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 + worknumber + seqnumber，分开来标示机器、时间等。

优点：

• 毫秒数在高位，自增序列在低位，整个 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 过程：

• 10bits 的机器号, 在 ID 分配 Worker 启动的时候, 从一个 Zookeeper 集群获取(保证所有的 Worker 不会有重复的机器号)
• 41bits 的 Timestamp: 每次要生成一个新 ID 的时候, 都会获取一下当前的 Timestamp, 然后分两种情况生成 sequence number:
• 如果当前的 Timestamp 和前一个已生成 ID 的 Timestamp 相同(在同一毫秒中), 就用前一个 ID 的 sequence number +1 作为新的 sequence number(12bits); 如果本毫秒内的所有 ID 用完, 等到下一毫秒继续(这个等待过程中, 不能分配出新的 ID)
• 如果当前的 Timestamp 比前一个 ID 的 Timestamp 大, 随机生成一个初始 sequence number(12bits) 作为本毫秒内的第一个 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长达64bits
*
* |41bits: Timestamp(毫秒)|3bits: 区域（机房）|10bits: 机器编号|10bits: 序列号|
*/
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("workerId can't be greater than %d or less than 0");
}
if (regionId > maxRegionId || regionId< 0) {
throw new IllegalArgumentException("datacenterId 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("workerId 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长度扩展到128bits
• 最高64bits时间戳
• 然后是48bits的Worker号(和Mac地址一样长)
• 最后是16bits的SeqNumber
• 由于它用48bits作为WorkerID，和Mac地址的长度一样，这样启动时不需要和Zookeeper通讯获取WorkerID。做到了完全的去中心化。
• 基于Erlang

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

Simpleflake

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

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 是用的一个叫做TicketServers的玩意，使用纯 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 生成方式简单的描述为：41bts + 13bshardid + 10bincrementseq，

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

具体实现方式如下：

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

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

logicShard 代号：

• 假设插入一条新的用户记录, 插入时, 根据 uid 来判断这条记录应该被插入到哪个 logicShard 中.
• 假设当前要插入的记录会被插入到第 1341 号 logicShard 中(假设当前的这个 Table 一共有 2000 个 logicShard)
• 新生成 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 这个方案的优势在于：

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

详细介绍见：Sharding & IDs at Instagram

优点：

• 开发成本低

缺点：

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