JAVA 服务 ID 生成冲突？雪花算法时钟回拨与 workerId 策略

JAVA 服务 ID 生成冲突？雪花算法时钟回拨与 workerId 策略

大家好，今天我们来聊聊分布式系统中 ID 生成的问题，特别是雪花算法在 Java 服务中应用时可能遇到的冲突，以及如何处理时钟回拨和设计合理的 workerId 策略。

在分布式系统中，我们需要一个全局唯一的 ID 来标识不同的数据记录。这个 ID 需要满足一些基本要求：

• 全局唯一性: 在整个系统中，ID 必须是唯一的。
• 趋势递增: 方便数据库索引，提高写入效率。
• 高性能: 能够快速生成 ID。
• 可排序性: 方便进行时间范围查询。
• 可回溯性: 可以从中解析出生成 ID 的一些信息。

雪花算法（Snowflake Algorithm）是一个经典且常用的分布式 ID 生成方案，它能够很好地满足上述需求。

雪花算法原理

雪花算法生成的 ID 是一个 64 位的 long 型整数，通常由以下几部分组成：

位数	组成部分	说明
1	符号位	始终为 0，因为 ID 是正整数。
41	时间戳	记录 ID 生成的时间，通常是相对于某个起始时间的时间戳差值，单位可以是毫秒。 使用41位，理论上可以支撑 69 年 ( (1L << 41) / (1000L 60 60 24 365) = 69.73 年 )，如果起始时间设置合理，足以满足大多数场景的需求。
10	工作机器 ID (workerId)	用于标识生成 ID 的机器，通常由数据中心 ID (datacenterId) 和机器 ID (workerId) 组成。 10 位可以支持 2^10 = 1024 个节点。 可以将这10位拆分为 5 位 datacenterId 和 5 位 workerId，分别支持 32 个数据中心和每个数据中心 32 个节点。这是一种常见的配置，可以根据实际需求进行调整。
12	序列号	用于在同一毫秒内区分不同的 ID。 12 位可以支持 2^12 = 4096 个序列号，意味着同一节点同一毫秒内最多可以生成 4096 个 ID。

雪花算法的核心思想是：将 64 位的 ID 划分为不同的段，每一段代表不同的含义，利用时间戳和机器 ID 来保证全局唯一性，利用序列号来解决同一毫秒内的 ID 冲突。

Java 实现一个简单的雪花算法

下面是一个简单的 Java 雪花算法实现：

public class SnowflakeIdWorker {

    private final long twepoch = 1288834974657L; // 起始时间戳 (2010-11-04 09:42:54.657)
    private final long workerIdBits = 5L; // 机器 ID 所占位数
    private final long datacenterIdBits = 5L; // 数据中心 ID 所占位数
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits); // 最大机器 ID (31)
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); // 最大数据中心 ID (31)
    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 datacenterId; // 数据中心 ID
    private long workerId; // 机器 ID
    private long sequence = 0L; // 序列号
    private long lastTimestamp = -1L; // 上次生成 ID 的时间戳

    public SnowflakeIdWorker(long datacenterId, long workerId) {
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
        }
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id 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 - twepoch) << 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);
        }
    }
}

这段代码实现了一个基本的雪花算法。需要注意的是，datacenterId 和 workerId 需要根据实际部署环境进行配置。

时钟回拨问题

雪花算法依赖于系统时间，如果系统时间发生回拨，可能会导致生成重复的 ID。例如，如果当前时间已经生成了某个 ID，然后系统时间回拨到之前的时间，再次生成 ID 时，就有可能生成重复的 ID。

在上面的代码中，我们通过以下代码来检测时钟回拨：

if (timestamp < lastTimestamp) {
    throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}

如果检测到当前时间小于上次生成 ID 的时间，就抛出一个异常。这是一种简单的处理方式，可以避免生成重复的 ID，但是会中断服务的正常运行。

那么，如何更好地处理时钟回拨问题呢？

1. 拒绝服务

这是最简单粗暴的方式，一旦检测到时钟回拨，就直接拒绝生成 ID。这种方式可以保证 ID 的绝对唯一性，但是会影响服务的可用性。上面的代码示例就采用了这种方式。

2. 等待时间追赶

当发生时钟回拨时，不立即抛出异常，而是等待系统时间追赶上来。例如，如果时钟回拨了 5 毫秒，就等待 5 毫秒，直到系统时间大于上次生成 ID 的时间。

public synchronized long nextId() {
    long timestamp = timeGen();

    if (timestamp < lastTimestamp) {
        long offset = lastTimestamp - timestamp;
        if (offset <= 5) { // 可以容忍的回拨时间，单位：毫秒
            try {
                wait(offset << 1); // 等待双倍的回拨时间
                timestamp = timeGen();
                if (timestamp < lastTimestamp) {
                   throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
                }
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
        } else {
             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 - twepoch) << timestampLeftShift)
            | (datacenterId << datacenterIdShift)
            | (workerId << workerIdShift)
            | sequence;
}

这种方式可以在一定程度上提高服务的可用性，但是仍然存在风险：

• 等待时间过长： 如果时钟回拨的时间较长，等待的时间也会相应增加，会影响 ID 的生成速度。
• 并发问题： 在高并发场景下，多个线程同时等待时间追赶，可能会导致线程阻塞。

3. 使用 NTP 协议同步时间

使用网络时间协议（NTP）来同步系统时间，可以减少时钟回拨的概率。但是，NTP 协议并不能完全消除时钟回拨，因为网络延迟等因素可能会导致时间同步不准确。

4. 使用 Redis 或 ZooKeeper 记录时间戳

可以将上次生成 ID 的时间戳记录在 Redis 或 ZooKeeper 中，当发生时钟回拨时，可以从 Redis 或 ZooKeeper 中获取正确的时间戳。这种方式可以有效地解决时钟回拨问题，但是会增加系统的复杂性。

workerId 策略

workerId 用于标识生成 ID 的机器，如果 workerId 配置不当，可能会导致 ID 冲突。

1. 手动配置

最简单的 workerId 策略是手动配置。例如，可以在配置文件中指定每个机器的 workerId。这种方式简单易懂，但是需要人工维护，容易出错。

2. 使用机器 IP 地址

可以使用机器的 IP 地址作为 workerId。例如，可以将 IP 地址转换为一个整数作为 workerId。这种方式可以自动生成 workerId，但是存在以下问题：

• IP 地址可能发生变化： 如果机器的 IP 地址发生变化，workerId 也会发生变化，可能会导致 ID 冲突。
• IP 地址冲突： 在某些情况下，不同的机器可能会使用相同的 IP 地址，例如在 NAT 环境下。

3. 使用 ZooKeeper 或 Redis 自动分配

可以使用 ZooKeeper 或 Redis 来自动分配 workerId。例如，可以在 ZooKeeper 或 Redis 中创建一个节点，每个机器启动时，尝试获取该节点的锁，如果获取成功，就将自己的 IP 地址作为 workerId 写入该节点。如果获取失败，则说明该 workerId 已经被其他机器占用，需要重新获取。

下面是一个使用 ZooKeeper 自动分配 workerId 的示例：

import org.apache.zookeeper.*;
import org.apache.zookeeper.data.Stat;

import java.io.IOException;
import java.util.Random;

public class ZookeeperWorkerIdGenerator {

    private static final String ZK_ADDRESS = "localhost:2181";
    private static final String ROOT_NODE = "/snowflake";
    private static final String WORKER_ID_NODE = ROOT_NODE + "/worker-";
    private ZooKeeper zk;
    private long workerId;

    public ZookeeperWorkerIdGenerator() throws IOException, InterruptedException, KeeperException {
        zk = new ZooKeeper(ZK_ADDRESS, 5000, null);
        ensureRootNodeExists();
        this.workerId = generateWorkerId();
    }

    private void ensureRootNodeExists() throws KeeperException, InterruptedException {
        Stat stat = zk.exists(ROOT_NODE, false);
        if (stat == null) {
            zk.create(ROOT_NODE, new byte[0], ZooDefs.Ids.OPEN_ACL_UNSAFE, CreateMode.PERSISTENT);
        }
    }

    private long generateWorkerId() throws KeeperException, InterruptedException {
        String createdNode = zk.create(WORKER_ID_NODE, new byte[0], ZooDefs.Ids.OPEN_ACL_UNSAFE, CreateMode.EPHEMERAL_SEQUENTIAL);
        // Extract sequence number from node name
        String sequenceStr = createdNode.substring(ROOT_NODE.length() + "/worker-".length());
        return Long.parseLong(sequenceStr);
    }

    public long getWorkerId() {
        return workerId;
    }

    public void close() throws InterruptedException {
        zk.close();
    }

    public static void main(String[] args) throws IOException, InterruptedException, KeeperException {
        ZookeeperWorkerIdGenerator generator = new ZookeeperWorkerIdGenerator();
        long workerId = generator.getWorkerId();
        System.out.println("Generated Worker ID: " + workerId);
        generator.close();
    }
}

这段代码使用 ZooKeeper 创建一个临时顺序节点，节点的序号作为 workerId。由于 ZooKeeper 保证了节点名称的唯一性，因此可以保证 workerId 的唯一性。

这种方式可以自动分配 workerId，并且可以保证 workerId 的唯一性。但是，需要依赖 ZooKeeper，会增加系统的复杂性。

4. 使用数据库自增 ID

可以使用数据库的自增 ID 作为 workerId。例如，可以创建一个表，包含一个自增 ID 字段和一个机器 IP 地址字段。每次机器启动时，向该表中插入一条记录，并将自增 ID 作为 workerId。

这种方式可以自动分配 workerId，并且可以保证 workerId 的唯一性。但是，需要依赖数据库，会增加系统的复杂性。

如何选择合适的 workerId 策略

选择合适的 workerId 策略需要根据实际情况进行考虑。以下是一些建议：

• 简单性： 优先选择简单的策略，例如手动配置或使用机器 IP 地址。
• 可靠性： 如果对 workerId 的唯一性要求较高，可以选择使用 ZooKeeper 或 Redis 自动分配。
• 可维护性： 选择易于维护的策略，例如使用数据库自增 ID。
• 性能： 考虑 workerId 生成的性能，避免影响 ID 的生成速度。

总结

今天我们讨论了雪花算法在 Java 服务中应用时可能遇到的 ID 冲突问题，以及如何处理时钟回拨和设计合理的 workerId 策略。希望通过今天的分享，能够帮助大家更好地理解和应用雪花算法。

• 雪花算法是一个常用的分布式 ID 生成方案，可以满足全局唯一性、趋势递增、高性能等需求。
• 时钟回拨是雪花算法可能遇到的问题，需要采取相应的措施来解决。
• workerId 的选择需要根据实际情况进行考虑，需要保证其唯一性。