UUID

UUID (Universally Unique Identifier) 是一个 128 位的标识符，用于在分布式系统中唯一地标识信息。UUID 的标准定义见 RFC 4122。

特点：

全局唯一性：理论上在不同时间、不同机器上生成的 UUID 都不会重复
固定长度：128 位，通常表示为 32 个十六进制数字，分为 5 组显示
无需中央管理机构：可以本地生成，不需要注册
多种生成算法：UUID 有 5 个版本，每个版本使用不同的生成方法

优点：

本地生成，无网络开销，性能高。
全球唯一。

缺点：

无序（作为主键时导致B+树频繁分裂，影响插入性能）。
字符串存储占用空间大（36字节），查询效率低。

适用场景：对唯一性要求高、无需有序且非DB主键的场景。

格式：标准 UUID 表示为 32 个十六进制数字，分为 5 组，形式为：8-4-4-4-12，例如 550e8400-e29b-41d4-a716-446655440000。

UUID 的版本：

版本 1 (基于时间和 MAC 地址)：使用当前时间戳和 MAC 地址生成
版本 2 (DCE 安全 UUID)：基于版本 1，但加入了本地域标识符
版本 3 (基于名称的 MD5 哈希)：使用命名空间和名称的 MD5 哈希生成
版本 4 (随机 UUID)：使用随机或伪随机数生成
版本 5 (基于名称的 SHA-1 哈希)：类似版本 3，但使用 SHA-1 哈希

Java 中的实现

在Java中，UUID（通用唯一标识符）是一个128位的值，通常表示为32个十六进制数字，由连字符分隔成5组（8-4-4-4-12格式）。

主要方法

生成随机 UUID (版本 4)：
```
UUID uuid = UUID.randomUUID();
```

从字符串创建 UUID：

// 用于序列化/反序列化
UUID uuid = UUID.fromString("550e8400-e29b-41d4-a716-446655440000");

获取 UUID 的各个部分：

// 获取 UUID 的高64位（前64位）
long mostSigBits = uuid.getMostSignificantBits();
// 获取 UUID 的低64位（后64位）
long leastSigBits = uuid.getLeastSignificantBits();

// 利用高低位重建 UUID
UUID newUuid = new UUID(mostSigBits, leastSigBits);

// 比较两个UUID时，先比较高64位，如果不相等就不需要比较低64位
int compare(UUID u1, UUID u2) {
    int cmp = Long.compare(u1.getMostSignificantBits(), u2.getMostSignificantBits());
    if (cmp != 0) return cmp;
    return Long.compare(u1.getLeastSignificantBits(), u2.getLeastSignificantBits());
}

// 基于UUID的高低位生成更短的唯一ID
public String generateShortId(UUID uuid) {
    return Long.toHexString(uuid.getMostSignificantBits()) + 
           Long.toHexString(uuid.getLeastSignificantBits());
}

getMostSignificantBits() 和 getLeastSignificantBits() 方法分别获取UUID 128位值的高低位，为两个long值（每个long是64位）
特殊场景中直接比较 long 值比比较字符串更高效
传输两个 long 比传输 UUID 字符串更节省带宽

比较 UUID：

int comparison = uuid1.compareTo(uuid2);

生成基于名称的 UUID (版本 3 或 5)：

// 版本 3 (MD5)
UUID uuid3 = UUID.nameUUIDFromBytes("name".getBytes());

// 版本 5 (SHA-1) - Java 标准库不直接支持，需要自己实现

import java.util.UUID;

public class UUIDExample {
    public static void main(String[] args) {
        // 生成随机 UUID (版本4)
        UUID randomUUID = UUID.randomUUID(); // 大多数情况下这是最佳选择
        System.out.println("随机 UUID: " + randomUUID);

        // 从字符串创建 UUID
        UUID fromString = UUID.fromString("550e8400-e29b-41d4-a716-446655440000");
        System.out.println("从字符串创建的 UUID: " + fromString);

        // 生成基于名称的 UUID (版本3)
        UUID nameBasedUUID = UUID.nameUUIDFromBytes("example".getBytes());
        System.out.println("基于名称的 UUID: " + nameBasedUUID);

        // 获取 UUID 的各个部分
        System.out.println("Most significant bits: " + randomUUID.getMostSignificantBits());
        System.out.println("Least significant bits: " + randomUUID.getLeastSignificantBits());
        System.out.println("版本号: " + randomUUID.version()); // 4 表示版本4
        System.out.println("变体: " + randomUUID.variant()); // 2 表示IETF变体
    }
}

UUID 版本3和4对比

	Java中的实现	特点	使用场景
版本3	`UUID.randomUUID()`	完全基于随机数 122位随机性 (其余6位用于版本和变体信息)	安全令牌、会话ID，等
版本4	`UUID.nameUUIDFromBytes()`	基于命名空间和名称的 MD5 哈希相同输入总是产生相同输出	基于内容生成唯一ID (如文件内容哈希)、需要跨系统一致生成的ID，等

数据库自增序列

利用数据库的自增特性：

单数据库：AUTO_INCREMENT(MySQL)或SEQUENCE(Oracle)
多数据库：设置不同步长（如DB1:1,4,7… DB2:2,5,8… DB3:3,6,9…）

优点：简单，递增有序。
缺点：

强依赖DB，存在单点风险。
分库分表时需额外配置步长，扩容困难。
暴露业务数据量（如用户ID可推测注册量）。

适用场景：小型非分布式系统。

单数据库实现

MySQL (AUTO_INCREMENT):

CREATE TABLE items (
    id BIGINT PRIMARY KEY AUTO_INCREMENT,
    name VARCHAR(100)
);

Oracle (SEQUENCE):

CREATE SEQUENCE item_seq START WITH 1 INCREMENT BY 1;

CREATE TABLE items (
    id NUMBER PRIMARY KEY,
    name VARCHAR2(100)
);

-- 插入时使用
INSERT INTO items (id, name) VALUES (item_seq.NEXTVAL, 'item1');

多数据库实现（步长设置）

在分布式系统中，通过设置不同数据库实例的自增步长和初始值来避免ID冲突：

DB1: 初始值=1，步长=3 → 1, 4, 7, 10...
DB2: 初始值=2，步长=3 → 2, 5, 8, 11...
DB3: 初始值=3，步长=3 → 3, 6, 9, 12...

Java实现

基于MySQL的实现

-- DB1配置
SET @@auto_increment_increment=3;
SET @@auto_increment_offset=1;

-- DB2配置
SET @@auto_increment_increment=3;
SET @@auto_increment_offset=2;

-- DB3配置
SET @@auto_increment_increment=3;
SET @@auto_increment_offset=3;

Redis生成ID

实现：利用Redis的 INCR 或 INCRBY 原子操作生成递增ID。

优点：

性能优于DB（单机可达10W+/秒）。
可生成有序ID。

缺点：

需引入Redis，增加系统复杂度。
持久化问题（AOF/RDB宕机可能导致ID重复）。

优化：

集群模式下分片生成（如每个实例预分配ID段）。

适用场景：需要高性能且允许少量ID不连续的场景。

代码实现

利用Redis的原子性操作：

// 使用INCR命令
Long id = redisTemplate.opsForValue().increment("global_id");

Snowflake算法

Snowflake 算法，雪花算法，是 Twitter 开源的分布式ID生成算法。生成后是一个 64bit 的 long 型的数值，组成部分引入了时间戳。

实现：64位ID = 1位符号位 + 41位时间戳 + 10位机器ID + 12位序列号。

优点：

本地生成，高性能（单机每秒26万+）。
趋势递增，适合作为DB主键。

缺点：

依赖系统时钟（时钟回拨会导致ID重复）。
需管理机器ID（如通过ZooKeeper）。

优化：

改进版（如美团Leaf）：解决时钟回拨问题。
缩短时间戳位数，扩展机器ID（如百度UidGenerator）。

适用场景：高并发分布式系统（如订单、日志系统）。

ID 的结构如下：

+--------------------------------------------------------------------------+
| 1 Bit Unused | 41 Bit Timestamp | 10 Bit Machine ID | 12 Bit Sequence ID |
+--------------------------------------------------------------------------+

1 位未使用的 bit：最高位是符号位，始终为 0，表示正数。
41 位时间戳：表示自定义起始时间（twepoch）以来的毫秒数，可以用来排序。
10 位机器 ID：用于表示生成 ID 的机器或数据中心，确保分布式系统中不同节点生成的 ID 唯一。通常由 5 位数据中心 ID 和 5 位机器 ID 组成。
12 位序列号：表示在同一毫秒内生成的不同 ID，解决高并发场景下的冲突问题。

实现步骤

获取当前时间戳：获取当前时间与自定义起始时间的差值（单位为毫秒）。
检查时钟回拨：确保当前时间戳不小于上一次生成 ID 的时间戳。如果发生回拨，通常会抛出异常。
生成序列号：
- 如果在同一毫秒内生成的 ID，将序列号加 1。
- 如果序列号达到最大值，等待到下一毫秒。
- 如果是新的毫秒，序列号重置为 0。
拼接 ID：将时间戳、机器 ID 和序列号左移并按位或组合成 64 位的 ID。

Java 实现

以下是 Snowflake 算法在 Java 中的完整实现代码：

public class SnowflakeIdGenerator {

    private final long sequenceBits = 12L;
    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 sequenceMask = -1L ^ (-1L << sequenceBits);

    private final long workerIdShift = sequenceBits;
    private final long dataCenterIdShift = sequenceBits + workerIdBits;
    private final long timestampLeftShift = sequenceBits + workerIdBits + dataCenterIdBits;

    private final long twepoch = 1587708854000L;

    private long workerId;
    private long dataCenterId;
    private long sequence = 0L;
    private long lastTimestamp = -1L;

    public SnowflakeIdGenerator(long workerId, long dataCenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("workerId can't be greater than %d or less than 0", maxWorkerId));
        }
        if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
            throw new IllegalArgumentException(String.format("dataCenterId can't be greater than %d or less than 0", maxDataCenterId));
        }
        this.workerId = workerId;
        this.dataCenterId = dataCenterId;
    }

    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 timeGen() {
        return System.currentTimeMillis();
    }

    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    public static void main(String[] args) {
        SnowflakeIdGenerator idGenerator = new SnowflakeIdGenerator(1, 1);
        for (int i = 0; i < 10; i++) {
            System.out.println(idGenerator.nextId());
        }
    }
}

Leaf

Leaf 是美团推出的一个分布式ID生成服务

Leaf的Leaf-segment号段模式和Leaf-snowflake模式

Leaf-segment号段模式

Leaf-segment号段模式是对直接用数据库自增ID充当分布式ID的一种优化，减少对数据库的频率操作。相当于从数据库批量的获取自增ID，每次从数据库取出一个号段范围，例如 (1,1000] 代表1000个ID，业务服务将号段在本地生成1~1000的自增ID并加载到内存

依赖于数据库：

CREATE TABLE `leaf_alloc` (
  `biz_tag` varchar(128) NOT NULL DEFAULT '' COMMENT '业务key',
  `max_id` bigint(20) NOT NULL DEFAULT '1' COMMENT '当前已经分配了的最大id',
  `step` int(11) NOT NULL COMMENT '初始步长，也是动态调整的最小步长',
  `description` varchar(256) DEFAULT NULL COMMENT '业务key的描述',
  `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '数据库维护的更新时间',
  PRIMARY KEY (`biz_tag`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

biz_tag：针对不同业务需求，用biz_tag字段来隔离，如果以后需要扩容时，只需对biz_tag分库分表即可
max_id：当前业务号段的最大值，用于计算下一个号段
- step：步长，也就是每次获取ID的数量

Leaf 在当前号段消费到某个点时，就异步的把下一个号段加载到内存中，不需要等到号段用尽的时候才去更新号段

采用双buffer Segment[] segments 存储两个号段缓存。当前号段消耗了10%时（segment.getIdle() < 0.9 * segment.getStep()）会开启异步线程更新下一个号段

// com.sankuai.inf.leaf.segment.SegmentIDGenImpl#getIdFromSegmentBuffer
if (!buffer.isNextReady() && (segment.getIdle() < 0.9 * segment.getStep()) && buffer.getThreadRunning().compareAndSet(false, true)) {
                service.execute(new Runnable() {
                    @Override
                    public void run() {
                        Segment next = buffer.getSegments()[buffer.nextPos()];
                        boolean updateOk = false;
                        try {
                            updateSegmentFromDb(buffer.getKey(), next);
                            updateOk = true;
                            logger.info("update segment {} from db {}", buffer.getKey(), next);
                        } catch (Exception e) {
                            logger.warn(buffer.getKey() + " updateSegmentFromDb exception", e);
                        } finally {
                            if (updateOk) {
                                buffer.wLock().lock();
                                buffer.setNextReady(true);
                                buffer.getThreadRunning().set(false);
                                buffer.wLock().unlock();
                            } else {
                                buffer.getThreadRunning().set(false);
                            }
                        }
                    }
                });
            }

// com.sankuai.inf.leaf.segment.model.Segment#getIdle
public long getIdle() {
    return this.getMax() - getValue().get();
}

比对

特性	数据库自增序列	UUID	Snowflake
有序性	是	否	是
分布式支持	需要特殊配置	原生支持	原生支持
性能	中等(依赖DB)	高	高
可读性	好	差	中等
扩展复杂度	高(需协调)	低	中等
依赖外部系统	是	否	部分依赖

分布式ID的几种生成方式