雪花算法（Snowflake）是由 Twitter 开发的一种分布式唯一 ID 生成算法，能够生成全局唯一的 64 位整数 ID，具有高效、有序和唯一的特点。生成的 ID 具备时间戳信息，并且能够保证在分布式环境下的唯一性。
雪花算法的生成 ID 结构是一个 64 位的整数，具体格式如下：
| 符号位 (1 bit) | 时间戳 (41 bit) | 数据中心 ID (5 bit) | 机器 ID (5 bit) | 序列号 (12 bit) |
|---|---|---|---|---|
| 0 | 41 位时间戳 | 5 位数据中心 | ID 5 位机器 | ID 12 位序列号 |
- 1 bit 符号位：最高位为符号位，始终为 0，表示正数。
- 41 bit 时间戳：使用自定义起始时间开始的毫秒级时间戳，41 位可以表示 69 年的时间。
- 5 bit 数据中心 ID：支持最多 32 个数据中心节点。
- 5 bit 机器 ID：支持每个数据中心最多 32 台机器。
- 12 bit 序列号：支持同一台机器每毫秒生成 4096 个唯一 ID。
- 时间排序：生成的 ID 基于时间戳递增，有序性非常好。
- 分布式支持：通过数据中心 ID 和机器 ID 可以在分布式环境中保证唯一性。
- 高性能：每个节点每毫秒可以生成最多 4096 个唯一 ID，性能高效。
- 稳定性高：算法非常简单，不依赖于数据库等外部系统，可以在分布式场景下大规模部署。
在分布式系统中，多个服务实例需要生成唯一的 ID。使用雪花算法可以设计一个分布式 UUID 服务，通过以下方式来保证全局唯一性和高效性：
- 时间戳：使用相对时间戳确保 ID 的时间有序。
- 数据中心 ID 和机器 ID：确保在分布式环境中，每个实例都有唯一的标识符，用以生成唯一 ID。
- 序列号：在同一毫秒内，序列号递增，避免 ID 冲突。
public class SnowflakeIdGenerator {
// 常量定义
private final long twepoch = 1288834974657L; // Twitter 的起始时间戳
private final long workerIdBits = 5L; // 机器 ID 的位数
private final long datacenterIdBits = 5L; // 数据中心 ID 的位数
private final long maxWorkerId = -1L ^ (-1L << workerIdBits); // 最大机器 ID
private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); // 最大数据中心 ID
private final long sequenceBits = 12L; // 序列号的位数
private final long workerIdShift = sequenceBits; // 机器 ID 左移的位数
private final long datacenterIdShift = sequenceBits + workerIdBits; // 数据中心 ID 左移的位数
private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; // 时间戳左移的位数
private final long sequenceMask = -1L ^ (-1L << sequenceBits); // 序列号掩码
// 工作节点参数
private long workerId; // 机器 ID
private long datacenterId; // 数据中心 ID
private long sequence = 0L; // 序列号
private long lastTimestamp = -1L; // 上次生成 ID 的时间戳
public SnowflakeIdGenerator(long workerId, long datacenterId) {
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException("Worker ID 超出范围");
}
if (datacenterId > maxDatacenterId || datacenterId < 0) {
throw new IllegalArgumentException("数据中心 ID 超出范围");
}
this.workerId = workerId;
this.datacenterId = datacenterId;
}
// 获取下一个 ID
public synchronized long nextId() {
long timestamp = timeGen(); // 获取当前时间戳
if (timestamp < lastTimestamp) {
throw new RuntimeException("系统时间倒退异常");
}
if (lastTimestamp == timestamp) {
// 如果同一毫秒内，则增加序列号
sequence = (sequence + 1) & sequenceMask;
if (sequence == 0) {
// 如果序列号超过 4096，则阻塞到下一毫秒
timestamp = tilNextMillis(lastTimestamp);
}
} else {
// 如果时间戳变化了，则序列号重置
sequence = 0L;
}
lastTimestamp = timestamp;
// 生成唯一 ID，拼接时间戳、数据中心 ID、机器 ID 和序列号
return ((timestamp - twepoch) << timestampLeftShift)
| (datacenterId << datacenterIdShift)
| (workerId << workerIdShift)
| sequence;
}
// 等待到下一毫秒
private long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
// 获取当前时间戳
private long timeGen() {
return System.currentTimeMillis();
}
}-
系统架构
- 每个服务实例运行一个 SnowflakeIdGenerator 对象，用于生成唯一 ID。服务实例会被分配一个唯一的 数据中心 ID 和 机器 ID，通过配置或注册中心管理。
- 通过负载均衡器，客户端请求 UUID 时会被分发到任意服务实例，服务实例会调用 nextId() 生成唯一 ID。
-
实例化雪花算法
// 在启动时，指定数据中心 ID 和机器 ID SnowflakeIdGenerator idGenerator = new SnowflakeIdGenerator(1L, 2L); // 生成唯一 ID long uniqueId = idGenerator.nextId(); System.out.println("生成的唯一ID: " + uniqueId);
-
高可用设计
- 数据中心和机器 ID 分配：使用配置中心或服务注册与发现工具（如 ZooKeeper、Consul）分配 数据中心 ID 和 机器 ID，确保每个实例的 ID 唯一。
- 容错：如果某个服务实例发生故障，可以通过重新分配 数据中心 ID 和 机器 ID 来确保继续生成唯一 ID。
- 负载均衡：通过负载均衡器（如 Nginx 或 Kubernetes Ingress）将生成 ID 的请求均衡分发给多个服务实例，确保负载均衡和高可用。
优点：
- 高性能：生成 ID 的过程只需简单的位操作，每毫秒可生成 4096 个 ID，性能非常高。
- 全局唯一：雪花算法能够在分布式环境中生成全局唯一的 ID，避免冲突。
- 有序性：生成的 ID 包含时间戳信息，因此具有有序性，在某些场景下可以按时间顺序排列。
- 无中心化：不需要依赖数据库或其他外部服务，完全在本地生成 ID。
缺点：
- 时间依赖性：如果服务器的时间被调整回退，可能会导致生成重复 ID，因此时间必须被严格控制。
- 数据中心和机器 ID 的限制：雪花算法中数据中心 ID 和机器 ID 各占 5 位，最大支持 32 个数据中心和 32 台机器。如果分布式系统规模更大，可能需要调整位数。
ZooKeeper 是一个分布式协调服务，适合用来在多个节点之间动态分配 ID。可以为每个节点创建一个唯一的 ZNode 来分配和存储它的 WORKER_ID 和 DATACENTER_ID。当某个应用启动时，可以向 ZooKeeper 注册并获取唯一的 ID。
- root/worker-nodes：根路径用于存储所有工作节点。
- worker-node-1：节点 1 的唯一标识符，存储 WORKER_ID 和 DATACENTER_ID。
- worker-node-2：节点 2 的唯一标识符。
每个节点启动时会在 worker-nodes 下创建一个临时节点（Ephemeral ZNode），这样当节点宕机时 ZooKeeper 会自动删除它，保证 ID 唯一性和动态性 。
我们需要在 Java 应用中通过 ZooKeeper 获取 WORKER_ID 和 DATACENTER_ID。可以使用 Apache Curator 框架，它提供了一个简化的 ZooKeeper 客户端 API。
-
添加依赖:
<dependency> <groupId>org.apache.curator</groupId> <artifactId>curator-recipes</artifactId> <version>5.2.0</version> </dependency>
-
示例：通过 ZooKeeper 动态分配 ID
import org.apache.curator.framework.CuratorFramework; import org.apache.curator.framework.CuratorFrameworkFactory; import org.apache.curator.retry.ExponentialBackoffRetry; import org.apache.curator.framework.recipes.nodes.PersistentNode; import org.apache.zookeeper.CreateMode; public class ZookeeperWorkerIdProvider { private static final String ZK_ADDRESS = "zookeeper:2181"; // ZooKeeper 的地址 private static final String WORKER_NODE_PATH = "/worker-nodes"; // 节点路径 private CuratorFramework client; public ZookeeperWorkerIdProvider() { client = CuratorFrameworkFactory.newClient(ZK_ADDRESS, new ExponentialBackoffRetry(1000, 3)); client.start(); } public long[] registerWorker() throws Exception { // 确保根路径存在 if (client.checkExists().forPath(WORKER_NODE_PATH) == null) { client.create().forPath(WORKER_NODE_PATH); } // 创建一个临时顺序节点，为每个启动的工作节点分配唯一的 WORKER_ID 和 DATACENTER_ID String path = client.create() .withMode(CreateMode.EPHEMERAL_SEQUENTIAL) .forPath(WORKER_NODE_PATH + "/worker-node-", new byte[0]); // 从创建的路径获取 WORKER_ID 和 DATACENTER_ID String[] splitPath = path.split("-"); long workerId = Long.parseLong(splitPath[splitPath.length - 1]) % 32; // 取最后的数字作为 WORKER_ID，32 是最大节点数 long datacenterId = (Long.parseLong(splitPath[splitPath.length - 1]) / 32) % 32; // 计算 DATACENTER_ID return new long[] { workerId, datacenterId }; } public void close() { if (client != null) { client.close(); } } }
此代码会通过 ZooKeeper 分配 WORKER_ID 和 DATACENTER_ID，并确保在应用程序重新启动或 ZooKeeper 节点发生故障时可以自动恢复 ID 分配。
-
在启动雪花算法应用时调用该类：
public class SnowflakeApplication { public static void main(String[] args) throws Exception { ZookeeperWorkerIdProvider zkProvider = new ZookeeperWorkerIdProvider(); long[] ids = zkProvider.registerWorker(); long workerId = ids[0]; long datacenterId = ids[1]; SnowflakeIdGenerator idGenerator = new SnowflakeIdGenerator(workerId, datacenterId); // 启动应用并使用 idGenerator 来生成 UUID } }
雪花算法的核心问题之一是它对系统时钟的依赖，特别是在时钟回拨（Clock Drift）或者系统时间不准确的情况下，会导致生成重复的 ID 或系统异常。为了应对雪花算法的时间依赖性问题，常见的解决方法包括以下几种：
-
时钟回拨检测与等待（Clock Backward Detection & Waiting）
问题描述：
当系统时钟回拨时，生成的时间戳会比之前的时间戳小，这样可能导致 ID 冲突，因为雪花算法依赖递增的时间戳来确保唯一性。
解决方案：
- 在检测到时钟回拨时，等待系统时间赶上上次生成 ID 的时间戳，直到时钟恢复正常为止。
- 这种方法通过强制等待，避免在时钟回拨期间生成重复的 ID。
代码实现示例：
public synchronized long nextId() { long timestamp = timeGen(); if (timestamp < lastTimestamp) { long offset = lastTimestamp - timestamp; if (offset <= 5) { // 如果时钟回拨幅度小于 5 毫秒，等待时钟追赶 try { Thread.sleep(offset); timestamp = timeGen(); if (timestamp < lastTimestamp) { throw new RuntimeException("Clock moved backwards, refusing to generate id"); } } catch (InterruptedException e) { throw new RuntimeException(e); } } else { throw new RuntimeException("Clock moved backwards, refusing to generate id for " + offset + " milliseconds"); } } // 其他逻辑与正常的 Snowflake 算法相同 return generateId(timestamp); }
- 优势：简单有效，避免在回拨期间生成重复的 ID。
- 劣势：在时钟回拨时需要等待，系统在此期间无法生成 ID，影响高可用性。
-
借助外部时间源（External Time Source）
问题描述：
本地系统时间可能因为配置问题、系统负载或电池损耗而出现时间不准确，导致雪花算法依赖的时间戳错误。
解决方案：
- 使用高精度的外部时间源来替代本地系统时钟，例如 NTP（Network Time Protocol）或 GPS。
- 定期校正系统时钟，确保本地时间与标准时间保持一致，降低时钟回拨的几率。
通过集成 NTP 协议，确保时钟不会严重漂移。例如：
# 安装并启用 ntpd sudo apt-get install ntp sudo service ntp start- 优势：系统时间保持同步，极大减少时钟漂移问题。
- 劣势：增加了对外部网络和时间源的依赖，且实时更新可能增加额外的系统开销。
-
使用逻辑时钟（Logical Clock / Hybrid Clock）
问题描述：
完全依赖物理时钟时，容易受到系统时钟变化的影响。
解决方案：
- 引入逻辑时钟，基于本地生成 ID 的速率来模拟递增的时间戳，确保系统生成的 ID 是有序的。
- 当检测到系统时钟回拨时，逻辑时钟会继续递增，避免 ID 重复或错误。
一种常见的实现方式是使用混合时钟（Hybrid Logical Clock），它结合了物理时钟和逻辑时钟，确保在物理时钟漂移时逻辑时钟能维持递增。
private long logicalClock = 0; private synchronized long nextId() { long timestamp = timeGen(); if (timestamp < lastTimestamp) { // 如果检测到时钟回拨，使用逻辑时钟 logicalClock++; timestamp = lastTimestamp; // 使用上次的时间戳 } else { logicalClock = 0; // 重置逻辑时钟 } return generateId(timestamp); }
- 优势：降低对物理时钟的依赖，在时钟回拨时仍能维持递增顺序。
- 劣势：引入逻辑时钟的复杂性，可能在高并发场景下出现瓶颈。
-
调整生成 ID 的粒度
问题描述：
雪花算法在同一毫秒内生成 ID 时，依赖时间戳 + 序列号（sequence）来确保唯一性。但当时间出现回拨问题时，生成 ID 会发生冲突。
解决方案：
- 可以调整 ID 生成的粒度，比如使用纳秒级时间戳，而不是毫秒级时间戳。这样可以进一步减少冲突的可能性，尤其是在系统负载较高的情况下。
- 此外，可以增加 sequence 位数以支持在同一毫秒内生成更多的 ID，减少时钟依赖带来的问题。
private long timeGen() { return System.nanoTime() / 1000; // 转换为微秒级时间戳 }
- 优势：提高生成 ID 的精度，减少在并发生成时冲突的概率。
- 劣势：时间粒度越高，系统时钟回拨造成的影响仍然存在，只是减少了冲突。
-
分布式锁方案
问题描述：
如果多台服务器在时钟回拨的情况下生成 ID，可能导致不同服务器生成的 ID 冲突。
解决方案：
- 通过引入分布式锁（如 Redis 锁、ZooKeeper 锁）来协调多个节点之间的 ID 生成顺序，避免 ID 冲突。
- 每次生成 ID 时，通过锁机制确保只有一个节点在特定时间段内生成 ID，其他节点需要等待。
虽然这种方法能够解决时钟回拨引发的冲突问题，但牺牲了一定的性能和效率，尤其是在高并发场景下，锁机制可能成为瓶颈。
// 使用 Redis 分布式锁来同步多个节点的 ID 生成 public synchronized long nextIdWithLock() { String lockKey = "snowflake-lock"; boolean acquired = redisLock.tryLock(lockKey, 10); // 尝试获取锁 if (!acquired) { throw new RuntimeException("Failed to acquire lock"); } try { // ID 生成逻辑 return nextId(); } finally { redisLock.release(lockKey); } }
- 优势：确保分布式环境下 ID 唯一性，防止多节点产生冲突。
- 劣势：引入了分布式锁，会导致系统性能下降，尤其是在高并发场景下。
-
避免依赖时间戳的唯一性
问题描述：
雪花算法依赖时间戳的唯一性，当时间戳出现回拨时，系统会出错。
解决方案：
- 如果场景允许，可以将 ID 的唯一性设计为基于其他因子，如增加随机性或引入更多节点信息（如 IP 地址、进程 ID 等）。
- 虽然这样会牺牲一定的有序性，但可以减少对时间戳的依赖，特别是对于不需要严格顺序的业务场景。
ZooKeeper 分布式锁是一种基于 ZooKeeper 的原子操作和一致性保障机制实现的分布式协调工具。它通过 ZooKeeper 的 临时节点 和 顺序节点 特性，实现多个客户端在分布式环境中的互斥访问，从而避免竞争条件和并发冲突。
ZooKeeper 的分布式锁利用其以下几个特性：
- 临时节点（Ephemeral Node）：在客户端断开连接或失效时，临时节点会自动删除。通过这个特性，ZooKeeper 可以检测到某个客户端失效并自动释放锁。
- 顺序节点（Sequential Node）：每当一个节点创建时，它会在节点名称后附加一个单调递增的序号。ZooKeeper 利用这个特性来保证顺序性。
- 每个客户端尝试获取锁时，都会在 ZooKeeper 的某个锁目录（如 /locks）下创建一个临时顺序节点。
- 例如，客户端 A 创建 /locks/lock-0001，客户端 B 创建 /locks/lock-0002。
- 判断当前客户端创建的节点是否是最小的节点。
- 如果当前客户端创建的节点是最小的节点，则获得锁。
- 如果不是最小节点，则监听比它小的那个节点（例如，客户端 B 创建 /locks/lock-0002 时，会监听 /locks/lock-0001）。
- 等待锁：
- 当监听的节点（即比它小的那个节点）被删除时，说明持有锁的客户端释放了锁，此时当前客户端会被通知并尝试获取锁。
- 释放锁：
- 客户端释放锁时，删除自己创建的临时顺序节点。
- 删除节点后，ZooKeeper 会通知正在监听这个节点的下一个客户端，从而触发它去获得锁。
1. /locks
├── lock-0001 (Client A 创建)
├── lock-0002 (Client B 创建)
└── lock-0003 (Client C 创建)
2. 竞争锁：
- Client A 拥有最小的顺序号 lock-0001，所以获得锁。
- Client B 监听 lock-0001，Client C 监听 lock-0002。
3. Client A 释放锁：
- Client B 收到 lock-0001 被删除的通知，获得锁。
- Client C 开始监听 lock-0002。
- 创建锁节点： 每个客户端尝试加锁时，会在 ZooKeeper 上的
/locks目录下创建一个带序号的临时节点，例如lock-00000001。 - 判断最小节点： 客户端读取
/locks目录下所有节点，判断自己创建的节点是不是最小的。- 如果是最小的，说明它获得了锁。
- 如果不是最小的，监听比它小的那个节点。
- 监听节点： 如果当前客户端没有获得锁，它会监听比它小的那个节点。当比它小的节点被删除时，它会被通知去检查自己是否是最小节点，从而尝试获取锁。
- 删除节点释放锁： 持有锁的客户端在完成任务后，删除自己创建的临时节点，释放锁。
- 其他等待的客户端尝试获取锁： ZooKeeper 会通知下一个顺序节点，让它去尝试获取锁。
-
依赖引入（Maven）
<dependency> <groupId>org.apache.curator</groupId> <artifactId>curator-recipes</artifactId> <version>5.2.0</version> </dependency> <dependency> <groupId>org.apache.curator</groupId> <artifactId>curator-framework</artifactId> <version>5.2.0</version> </dependency> <dependency> <groupId>org.apache.curator</groupId> <artifactId>curator-client</artifactId> <version>5.2.0</version> </dependency>
-
ZooKeeper 分布式锁实现
import org.apache.curator.framework.CuratorFramework; import org.apache.curator.framework.CuratorFrameworkFactory; import org.apache.curator.framework.recipes.locks.InterProcessMutex; import org.apache.curator.retry.ExponentialBackoffRetry; public class DistributedLockExample { private static final String ZK_ADDRESS = "localhost:2181"; private static final String LOCK_PATH = "/distributed-lock"; public static void main(String[] args) { // 创建 ZooKeeper 客户端 CuratorFramework client = CuratorFrameworkFactory.newClient(ZK_ADDRESS, new ExponentialBackoffRetry(1000, 3)); client.start(); // 创建分布式锁 InterProcessMutex lock = new InterProcessMutex(client, LOCK_PATH); try { // 尝试获取锁 if (lock.acquire(5, TimeUnit.SECONDS)) { System.out.println("Lock acquired!"); try { // 执行业务逻辑 performBusinessLogic(); } finally { // 释放锁 lock.release(); System.out.println("Lock released!"); } } else { System.out.println("Failed to acquire lock"); } } catch (Exception e) { e.printStackTrace(); } finally { client.close(); } } private static void performBusinessLogic() { System.out.println("Performing business logic..."); // 模拟业务操作的时间消耗 try { Thread.sleep(3000); } catch (InterruptedException e) { e.printStackTrace(); } } }
关键步骤说明：
- Curator 框架：使用 Curator 是因为它封装了 ZooKeeper 的复杂 API，并提供了更简单的分布式锁实现（如 InterProcessMutex 类）。
- InterProcessMutex：这是 Curator 提供的分布式可重入锁实现，内部使用 ZooKeeper 创建临时顺序节点来协调多个客户端的锁竞争。
- 锁的获取和释放：客户端通过
lock.acquire()获取锁，并在操作完成后通过lock.release()释放锁
优点：
- 高可靠性：ZooKeeper 提供了强一致性保证，确保分布式锁的正确性和可靠性。
- 自动故障处理：通过临时节点机制，ZooKeeper 能自动检测到客户端失效，并自动释放锁。
- 支持可重入锁：Curator 实现提供了可重入锁的支持，多个线程可以递归获取同一个锁。
缺点：
- 性能开销：ZooKeeper 的强一致性特性会带来一定的性能开销，尤其是在高并发下，创建和删除节点的操作可能成为瓶颈。
- 单点故障问题：虽然 ZooKeeper 本身是一个分布式系统，但在集群不可用时，所有锁的获取和释放都将失败。
- 锁的粒度和吞吐量：ZooKeeper 的锁机制适用于粗粒度的分布式锁，不太适合细粒度、高吞吐量的场景。
- 分布式任务调度：在集群中确保只有一个节点执行某些任务。
- 共享资源访问控制：防止多个节点同时修改共享资源，确保数据的一致性。
- 分布式事务：在分布式系统中锁住某些资源，确保事务的原子性。