JAVA 分布式系统全局唯一 ID 实现：雪花算法与 Redis 实战
大家好，今天我们来聊聊分布式系统中的一个重要话题：全局唯一 ID 的生成。在单体应用中，我们通常依赖数据库的自增 ID 来保证唯一性。但在分布式环境下，各个服务拥有独立的数据库，自增 ID 机制不再适用。我们需要一种能在分布式环境下也能保证全局唯一性的 ID 生成方案。
为什么需要全局唯一 ID？
全局唯一 ID 在分布式系统中至关重要，它能解决以下问题：
- 数据分片/分库分表： 将数据分散到多个数据库或表中，需要一个全局唯一的 ID 来标识每条记录。
- 分布式事务： 跨多个服务的事务需要一个唯一的 ID 来跟踪整个事务流程。
- 消息队列： 消息需要一个唯一的 ID 来防止重复消费。
- 唯一性约束： 在不同服务间需要保证某些数据的唯一性，例如用户 ID、订单 ID 等。
- 数据分析和聚合： 在不同服务产生的数据需要聚合分析时，需要一个全局唯一的 ID 来关联不同来源的数据。
全局唯一 ID 的常见方案
有很多种生成全局唯一 ID 的方案，常见的包括：
- UUID： Universally Unique Identifier，通用唯一识别码。
- 数据库自增 ID： 使用单独的数据库实例生成自增 ID。
- 雪花算法 (Snowflake Algorithm)： Twitter 开源的分布式 ID 生成算法。
- Redis 自增： 利用 Redis 的原子自增特性生成 ID。
- Zookeeper： 利用 Zookeeper 的有序节点特性生成 ID。
- Leaf： 美团点评开源的分布式 ID 生成系统。
每种方案都有其优缺点，我们需要根据实际业务场景选择合适的方案。
UUID 的优缺点
优点：
- 简单易用，生成 ID 不需要依赖任何外部系统。
- 能够生成大量的 ID，重复概率极低。
缺点：
- 长度较长，通常为 36 个字符（包含连字符）。
- 无序，不利于数据库索引，可能导致性能问题。
- 可读性差。
由于 UUID 的无序性，在面对大量数据写入时，会导致 B+ 树索引频繁分裂，影响数据库性能。因此，在对性能有较高要求的场景下，不建议使用 UUID 作为主键。
数据库自增 ID 的优缺点
优点：
- 简单易用，利用数据库的自增机制。
- ID 是有序的，有利于数据库索引。
缺点：
- 存在单点故障风险。
- 横向扩展困难。
- ID 生成性能受限于数据库性能。
如果使用数据库自增 ID，需要考虑高可用性和扩展性问题。可以采用主备数据库方案，或者使用多个数据库实例生成不同范围的 ID，但实现起来比较复杂。
雪花算法 (Snowflake Algorithm)
雪花算法是一种经典的分布式 ID 生成算法，由 Twitter 开源。它能够生成 64 位的 Long 型 ID，保证全局唯一和趋势递增。
雪花算法的结构：
0 | 41 位时间戳 (timestamp) | 5 位数据中心 ID (datacenterId) | 5 位机器 ID (workerId) | 12 位序列号 (sequence)- 1 位符号位： 始终为 0，表示正数。
- 41 位时间戳： 存储的是从某个固定时间点（epoch）开始的毫秒数。可以使用
System.currentTimeMillis()获取。41 位时间戳可以使用 69 年（(1L << 41) / (1000 60 60 24 365) = 69）。 - 5 位数据中心 ID： 用于标识不同的数据中心。最多支持 32 个数据中心。
- 5 位机器 ID： 用于标识同一数据中心下的不同机器。最多支持 32 台机器。
- 12 位序列号： 用于在同一毫秒内生成不同的 ID。最多支持 4096 个 ID。
雪花算法的优点：
- 高性能： 能够在单机上生成大量的 ID。
- 全局唯一： 保证生成的 ID 在分布式环境中是唯一的。
- 趋势递增： 生成的 ID 基本上是递增的，有利于数据库索引。
- 可配置： 可以根据实际需要调整数据中心 ID 和机器 ID 的位数。
- 不依赖外部系统： 除了初始配置，不依赖于外部系统，降低了系统的复杂度。
雪花算法的缺点：
- 依赖时钟，如果发生时钟回拨，可能会生成重复的 ID。
- 需要提前配置数据中心 ID 和机器 ID。
雪花算法的代码实现 (Java)
public class SnowflakeIdWorker {
private final long epoch = 1609459200000L; // 设置起始时间 (2021-01-01 00:00:00)
private final long workerIdBits = 5L;
private final long datacenterIdBits = 5L;
private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
private final long sequenceBits = 12L;
private final long workerIdShift = sequenceBits;
private final long datacenterIdShift = sequenceBits + workerIdBits;
private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
private final long sequenceMask = -1L ^ (-1L << sequenceBits);
private long datacenterId;
private long workerId;
private long sequence = 0L;
private long lastTimestamp = -1L;
public SnowflakeIdWorker(long datacenterId, long workerId) {
if (datacenterId > maxDatacenterId || datacenterId < 0) {
throw new IllegalArgumentException(String.format("DatacenterId can't be greater than %d or less than 0", maxDatacenterId));
}
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("WorkerId can't be greater than %d or less than 0", maxWorkerId));
}
this.datacenterId = datacenterId;
this.workerId = workerId;
}
public synchronized long nextId() {
long timestamp = timeGen();
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;
}
lastTimestamp = timestamp;
return ((timestamp - epoch) << timestampLeftShift)
| (datacenterId << datacenterIdShift)
| (workerId << workerIdShift)
| sequence;
}
protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
protected long timeGen() {
return System.currentTimeMillis();
}
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(id);
}
}
}代码解释：
epoch: 起始时间戳，用于计算时间差。workerIdBits和datacenterIdBits: 定义了 workerId 和 datacenterId 的位数。maxWorkerId和maxDatacenterId: 计算了 workerId 和 datacenterId 的最大值。sequenceBits: 定义了序列号的位数。workerIdShift,datacenterIdShift,timestampLeftShift: 定义了各个部分的偏移量，用于将它们组合成一个 64 位的 ID。sequenceMask: 用于生成序列号的掩码。datacenterId和workerId: 实际的数据中心 ID 和机器 ID。sequence: 当前序列号。lastTimestamp: 上一次生成 ID 的时间戳。nextId(): 生成下一个 ID 的方法，使用了synchronized关键字来保证线程安全。timeGen(): 获取当前时间戳的方法。tilNextMillis(): 如果当前时间戳小于等于上一次的时间戳，则等待下一毫秒。
时钟回拨问题的处理：
代码中检测到了时钟回拨的情况 (timestamp < lastTimestamp)，并抛出了异常。 实际应用中，可以采用以下策略处理时钟回拨：
- 拒绝服务： 直接抛出异常，停止生成 ID。这是最简单的处理方式，但可能会影响系统的可用性。
- 等待时钟追赶： 等待时钟追赶到上一次的时间戳之后再生成 ID。这种方式可能会导致 ID 生成的延迟。
- 使用备用时间源： 使用 NTP 服务器等备用时间源来校准时钟。
- 记录回拨事件： 记录时钟回拨事件，并人工介入处理。
- 扩展时间戳位数： 如果对ID长度要求不高，可以牺牲一部分datacenterId或者workerId的位数，来扩展时间戳的位数，从而容忍一定范围内的时钟回拨。
选择哪种处理方式取决于业务对可用性和一致性的要求。
数据中心 ID 和机器 ID 的配置
数据中心 ID 和机器 ID 需要在系统启动时进行配置。 可以采用以下方式配置：
- 配置文件： 将数据中心 ID 和机器 ID 配置在配置文件中。
- 环境变量： 将数据中心 ID 和机器 ID 设置为环境变量。
- 数据库： 将数据中心 ID 和机器 ID 存储在数据库中。
- Zookeeper： 使用 Zookeeper 来动态分配数据中心 ID 和机器 ID。
推荐使用 Zookeeper 来动态分配数据中心 ID 和机器 ID，可以避免手动配置的麻烦，并提高系统的灵活性。
Redis 自增
Redis 是一种高性能的内存数据库，它提供了原子自增 (INCR) 命令，可以用来生成全局唯一的 ID。
Redis 自增的优点：
- 高性能： Redis 的自增操作非常快。
- 简单易用： 只需要调用 Redis 的 INCR 命令即可。
- 高可用： Redis 可以通过主从复制和 Sentinel 来实现高可用。
Redis 自增的缺点：
- 依赖外部系统： 需要依赖 Redis 集群。
- 非趋势递增： ID 不是趋势递增的，不利于数据库索引。
- 可能存在空洞： 如果 Redis 发生故障，可能会导致 ID 出现空洞。
Redis 自增的代码实现 (Java)
import redis.clients.jedis.Jedis;
public class RedisIdWorker {
private String redisHost;
private int redisPort;
private String idKey;
public RedisIdWorker(String redisHost, int redisPort, String idKey) {
this.redisHost = redisHost;
this.redisPort = redisPort;
this.idKey = idKey;
}
public long nextId() {
try (Jedis jedis = new Jedis(redisHost, redisPort)) {
return jedis.incr(idKey);
} catch (Exception e) {
throw new RuntimeException("Failed to generate ID from Redis", e);
}
}
public static void main(String[] args) {
RedisIdWorker idWorker = new RedisIdWorker("localhost", 6379, "order_id");
for (int i = 0; i < 1000; i++) {
long id = idWorker.nextId();
System.out.println(id);
}
}
}代码解释：
redisHost和redisPort: Redis 服务器的地址和端口。idKey: Redis 中用于存储 ID 的 key。nextId(): 从 Redis 中获取下一个 ID 的方法。- 使用
Jedis连接 Redis 服务器。 - 调用
jedis.incr(idKey)命令来原子自增idKey对应的 value，并返回自增后的值。
Redis 自增的优化
为了提高 Redis 自增的性能，可以采用以下优化策略：
- 批量获取 ID： 一次性从 Redis 中获取多个 ID，减少网络开销。
- 使用 Redis 集群： 使用 Redis 集群来提高 Redis 的可用性和扩展性。
- Key 的选择： 使用不同的 Key 来生成不同类型的 ID，例如订单 ID、用户 ID 等。
- 设置 Key 的过期时间： 为 Key 设置过期时间，防止 Redis 中存储过多的 ID。
Redis 自增的空洞问题
Redis 自增可能会出现空洞，例如 Redis 发生故障重启后，ID 可能会从一个较大的值开始，导致之前的 ID 没有被使用。 为了解决这个问题，可以采用以下策略：
- 预分配 ID： 提前从 Redis 中获取一批 ID，并存储在本地。
- 记录已分配的 ID： 使用数据库或其他存储介质记录已分配的 ID，并在生成 ID 时进行检查。
- 接受空洞： 如果业务对 ID 的连续性没有严格要求，可以接受空洞。
雪花算法与 Redis 的结合
可以将雪花算法和 Redis 结合起来，利用 Redis 来存储 workerId 和 datacenterId。 在系统启动时，从 Redis 中获取 workerId 和 datacenterId，然后使用雪花算法生成 ID。 这样可以避免手动配置 workerId 和 datacenterId 的麻烦，并提高系统的灵活性。
实现步骤：
- 在 Redis 中存储 workerId 和 datacenterId，可以使用 Hash 数据结构。
- 在系统启动时，从 Redis 中获取 workerId 和 datacenterId。如果 Redis 中不存在 workerId 和 datacenterId，则生成一个新的 workerId 和 datacenterId，并存储到 Redis 中。可以使用 Redis 的 INCR 命令来生成新的 workerId 和 datacenterId。
- 使用获取到的 workerId 和 datacenterId 初始化 SnowflakeIdWorker。
- 使用 SnowflakeIdWorker 生成 ID。
代码示例 (仅展示关键部分):
import redis.clients.jedis.Jedis;
public class RedisSnowflakeIdWorker {
private String redisHost;
private int redisPort;
private String workerIdKey;
private String datacenterIdKey;
private SnowflakeIdWorker idWorker;
public RedisSnowflakeIdWorker(String redisHost, int redisPort, String workerIdKey, String datacenterIdKey) {
this.redisHost = redisHost;
this.redisPort = redisPort;
this.workerIdKey = workerIdKey;
this.datacenterIdKey = datacenterIdKey;
init();
}
private void init() {
try (Jedis jedis = new Jedis(redisHost, redisPort)) {
long workerId = getOrGenerateId(jedis, workerIdKey, 0, 31); //假设 workerId 范围是 0-31
long datacenterId = getOrGenerateId(jedis, datacenterIdKey, 0, 31); //假设 datacenterId 范围是 0-31
this.idWorker = new SnowflakeIdWorker(datacenterId, workerId);
} catch (Exception e) {
throw new RuntimeException("Failed to initialize RedisSnowflakeIdWorker", e);
}
}
private long getOrGenerateId(Jedis jedis, String key, long min, long max) {
String idStr = jedis.get(key);
if (idStr == null) {
// 利用 Redis 的原子自增，保证分配的 ID 唯一
long newId = jedis.incr(key + "_seq"); // 使用一个单独的 key 来记录序列号
if (newId > max) {
throw new RuntimeException("Reached maximum ID for key: " + key);
}
jedis.set(key, String.valueOf(newId));
return newId;
} else {
return Long.parseLong(idStr);
}
}
public long nextId() {
return idWorker.nextId();
}
public static void main(String[] args) {
RedisSnowflakeIdWorker idWorker = new RedisSnowflakeIdWorker("localhost", 6379, "worker_id", "datacenter_id");
for (int i = 0; i < 1000; i++) {
long id = idWorker.nextId();
System.out.println(id);
}
}
}代码解释：
getOrGenerateId(): 从 Redis 中获取或生成 ID。 如果 Redis 中不存在 ID，则使用jedis.incr()命令生成一个新的 ID，并存储到 Redis 中。 为了保证 ID 的唯一性，使用了 Redis 的原子自增特性。workerIdKey和datacenterIdKey用于存储 workerId 和 datacenterId 的 Redis key。- 通过将 workerId 和 datacenterId 存储到 Redis 中，可以实现动态分配，避免了手动配置的麻烦。
总结：选择合适的 ID 生成方案
全局唯一 ID 的生成方案有很多种，选择哪种方案取决于实际业务场景。
| 方案 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| UUID | 简单易用，无需依赖外部系统 | 长度较长，无序，不利于数据库索引 | 对性能要求不高，不需要保证 ID 有序的场景 |
| 数据库自增 ID | 简单易用，ID 有序 | 存在单点故障风险，横向扩展困难，ID 生成性能受限于数据库性能 | 单体应用，或者对性能要求不高，且可以容忍单点故障的场景 |
| 雪花算法 | 高性能，全局唯一，趋势递增，可配置，不依赖外部系统 | 依赖时钟，需要提前配置数据中心 ID 和机器 ID | 对性能有较高要求，需要保证 ID 全局唯一和趋势递增的场景 |
| Redis 自增 | 高性能，简单易用，高可用 | 依赖外部系统，非趋势递增，可能存在空洞 | 对性能有较高要求，可以容忍 ID 非趋势递增和存在空洞的场景 |
| 雪花算法 + Redis | 结合了雪花算法和 Redis 的优点 | 增加了系统的复杂度，需要同时维护 Redis 和雪花算法的配置 | 对性能有较高要求，需要保证 ID 全局唯一和趋势递增，且需要动态分配数据中心 ID 和机器 ID 的场景 |
最后的建议
在选择全局唯一 ID 生成方案时，需要综合考虑以下因素：
- 性能： ID 生成的速度是否满足业务需求。
- 唯一性： 是否能够保证 ID 在分布式环境下的全局唯一性。
- 有序性： 是否需要保证 ID 的有序性，有利于数据库索引。
- 可用性： 系统是否能够容忍单点故障。
- 可维护性： 系统的复杂度是否可控。
- 成本： 系统的部署和维护成本。
希望今天的分享对大家有所帮助，谢谢！