很多业务有生成唯一 ID 并作为数据库主键的需求。数据库会在这个字段上建立聚集索引（参考 MySQL InnoDB），即该字段会影响各条数据再物理存储上的顺序。
ID还要尽可能短，节省内存，让数据库索引效率更高。基本上64位整数能够满足绝大多数的场景，但是如果能做到比64位更短那就更好了。需要根据具体业务进行分析，预估出ID的最大值，这个最大值通常比64位整数的上限小很多，于是我们可以用更少的bit表示这个ID。
查询的时候，往往有分页或者排序的需求，所以需要给每条数据添加一个时间字段，并在其上建立普通索引(Secondary Index)。但是普通索引的访问效率比聚集索引慢，如果能够让ID按照时间粗略有序，则可以省去这个时间字段。为什么不是按照时间精确有序呢？因为按照时间精确有序是做不到的，除非用一个单机算法，在分布式场景下做到精确有序性能一般很差。
这就引出了 ID 生成的三大核心需求：
下面介绍一些常用的生成 ID 的方法。
UUID#
UUID 是一类算法的统称，具体有不同的实现。UUID 的优点是每台机器可以独立产生 ID，理论上保证不会重复，所以天然是分布式的；缺点是生成的 ID 太长，不仅占用内存，而且索引查询效率低。
MongoDB 的 ObjectId 使用的就是 UUID 算法。生成的 ObjectId 占 12 个字节，由以下几个部分组成，
- 4 个字节表示的 Unix timestamp
- 3 个字节表示的机器的 ID
- 2 个字节表示的进程 ID
- 3 个字节表示的计数器
使用数据库#
可以使用数据库中的自增主键来生成ID。将ID生成的过程交给数据库管理，每个节点向数据库插入记录时，数据库会自动分配一个唯一的ID。通过使用数据库的自动递增功能，可以保证ID的唯一性和粗略有序性。
在分布式环境下，可以使用多台数据库协同工作生成 ID。假设用 8 台MySQL服务器协同工作，第一台 MySQL 初始值是 1，每次自增 8，第二台 MySQL 初始值是 2，每次自增 8，依次类推。在数据库前面添加一个负载均衡，每来一个请求，由负载均衡随机地将请求发给 8 台 MySQL 中的任意一个，然后返回一个ID。
Flickr就是这么做的，仅仅使用了两台 MySQL 服务器。可见这个方法虽然简单无脑，但是性能足够好。不过要注意，在 MySQL 中，不需要把所有 ID 都存下来，每台机器只需要存一个 MAX_ID 就可以了。这需要用到 MySQL 的一个 REPLACE INTO 特性。
Flickr 的实现方式如下。
Tickets64 表结构如下：
1
2
3
4
5
6
| 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=InnoDB
|
SELECT * from Tickets64 返回一行，如下所示：
1
2
3
4
5
| +-------------------+------+
| id | stub |
+-------------------+------+
| 72157623227190423 | a |
+-------------------+------+
|
当我需要一个新的全局唯一 64 位 ID 时，我发出以下 SQL：
1
2
| REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();
|
对于两台数据库服务器，分别设置表的自增值（auto_increment_increment）和偏移值（auto_increment_offset）。
1
2
3
4
5
6
7
| TicketServer1:
auto_increment_increment = 2
auto_increment_offset = 1
TicketServer2:
auto_increment_increment = 2
auto_increment_offset = 2
|
举例：一个数据库服务器设置：自增值为 2，起始值为 1，生成的 ID 为奇数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| SET auto_increment_increment=2;
SET auto_increment_offset=1;
drop table Tickets64;
CREATE TABLE `Tickets64` (
`id` bigint(20) unsigned NOT NULL auto_increment,
`stub` char(1) NOT NULL default '',
PRIMARY KEY (`id`),
UNIQUE KEY `stub` (`stub`)
);
SELECT AUTO_INCREMENT FROM information_schema.tables WHERE table_name="Tickets64";
REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();
|
另一个数据库服务器如何设置？：自增值为 2，起始值为 2，生成的 ID 为偶数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| SET auto_increment_increment=2;
SET auto_increment_offset=2;
drop table Tickets64;
CREATE TABLE `Tickets64` (
`id` bigint(20) unsigned NOT NULL auto_increment,
`stub` char(1) NOT NULL default '',
PRIMARY KEY (`id`),
UNIQUE KEY `stub` (`stub`)
);
SELECT AUTO_INCREMENT FROM information_schema.tables WHERE table_name="Tickets64";
REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();
|
这个方法跟单台数据库比，缺点是 ID 不是严格递增的，只是粗略递增的。不过这个问题不大，我们的目标是粗略有序，不需要严格递增。
Snowflake算法#
Twitter 开源的 Snowflake 算法。Snowflake是一种经典的分布式ID生成算法，由Twitter开发。它将64位的ID划分为不同的部分，包括时间戳、数据中心ID、机器ID和序列号。通过在不同的部分分配不同的位数，可以在分布式环境中生成唯一的ID，并且保证了ID的时间粗略有序性。
Instagram 用了类似的方案，41 位表示时间戳，13 位表示 shard Id（一个shard Id对应一台PostgreSQL机器），最低10位表示自增 ID。这个方案用一个 PostgreSQL 集群代替了 Twitter Snowflake 集群，优点是利用了现成的 PostgreSQL。
使用分布式锁#
可以使用分布式锁来保证在生成 ID 时的互斥性，从而保证 ID 的有序性。可以使用一些分布式锁的实现，如 ZooKeeper、Redis 等，来协调各个节点的 ID 生成过程。每个节点在生成 ID 之前，首先获取分布式锁，然后按照一定规则生成 ID，释放锁后，下一个节点再获取锁生成ID。
下面是一个基本的使用 ZooKeeper 锁生成分布式 ID 的示例：
- 创建ZooKeeper客户端连接：
1
2
| CuratorFramework client = CuratorFrameworkFactory.newClient("localhost:2181", new ExponentialBackoffRetry(1000, 3));
client.start();
|
- 创建分布式锁：
1
| InterProcessMutex lock = new InterProcessMutex(client, "/id_lock");
|
- 获取锁并生成ID：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| int timeoutSeconds = 10; // 设置锁超时时间为10秒
try {
if (lock.acquire(timeoutSeconds, TimeUnit.SECONDS)) {
// 成功获取锁
String distributedID = generateID();
// 使用生成的ID进行业务操作
// ...
} else {
// 未能在超时时间内获取到锁，进行相应处理
// ...
}
} catch (Exception e) {
// 处理异常
} finally {
try {
lock.release(); // 释放锁
} catch (Exception e) {
// 处理异常
}
}
|
在这个示例中，使用 Curator 框架创建了一个 ZooKeeper 客户端连接，然后创建了一个 InterProcessMutex 对象，该对象表示一个分布式锁。在获取锁之前，节点会尝试获取并持有该锁。只有一个节点可以成功获取到锁，其他节点会阻塞等待。
获取到锁后，可以执行生成 ID 的逻辑，生成唯一的分布式 ID。
在业务操作完成后，通过 release()方法释放锁，使其他节点可以继续获取锁并生成 ID。
通过使用 ZooKeeper 锁，我们可以确保在分布式环境下生成的 ID 是互斥的，并且按照获取锁的顺序生成。这样可以保证生成的 ID 是有序的，并且避免了并发冲突的问题。
Redis 本身并没有提供原生的分布式锁功能，但可以借助 Redis 的原子性操作和过期时间来实现一个简单的分布式锁，并在获取锁时生成分布式 ID。下面是一个使用 Redis 锁生成分布式 ID 的示例代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| import redis.clients.jedis.Jedis;
public class DistributedIdGenerator {
private static final String LOCK_KEY = "id_lock";
private static final int LOCK_EXPIRATION = 10; // 锁的过期时间，单位为秒
private static final String REDIS_HOST = "localhost";
private static final int REDIS_PORT = 6379;
private Jedis jedis;
public DistributedIdGenerator() {
jedis = new Jedis(REDIS_HOST, REDIS_PORT);
}
public String generateDistributedId() {
// 获取分布式锁
boolean lockAcquired = acquireLock(LOCK_KEY, LOCK_EXPIRATION);
if (lockAcquired) {
try {
// 生成ID的逻辑
String distributedId = generateId();
// 使用生成的ID进行业务操作
// ...
return distributedId;
} finally {
// 释放分布式锁
releaseLock(LOCK_KEY);
}
} else {
// 未能获取到分布式锁，进行相应处理
// ...
return null;
}
}
private boolean acquireLock(String lockKey, int expiration) {
String result = jedis.set(lockKey, "locked", "NX", "EX", expiration);
return "OK".equals(result);
}
private void releaseLock(String lockKey) {
jedis.del(lockKey);
}
private String generateId() {
// 生成ID的逻辑
// ...
return "your_generated_id";
}
}
|
在上述示例代码中，我们使用 Jedis 客户端连接 Redis，并定义了获取锁和释放锁的方法 acquireLock() 和 releaseLock()。在 generateDistributedId() 方法中，我们首先尝试获取分布式锁，如果成功获取到锁，则执行生成 ID 的逻辑和业务操作，并在最后释放锁。如果无法获取到锁，则可以根据实际需求进行相应处理。
请注意，上述示例代码是一个简单的实现，仅供参考。在实际使用中，还需要考虑异常处理、分布式锁的可重入性、处理锁超时等情况，以及根据具体的需求和系统架构进行适当的调整。
参考资料#