什么是分布式ID？

发表于 2024-03-28 更新于 2024-05-31 分类于架构阅读次数：本文字数： 8.1k 阅读时长 ≈ 7 分钟

你好，我是猿java

最近，今天，我们一起来聊聊几种常见的分布式ID 生成的几种方式。

为什么需要分布式ID？

在复杂的分布式系统中，常常需要一个全局唯一的 ID来标识数据，消息或者请求，比如：订单号，消息的唯一标识，接口的幂等ID 等等。

分布式 ID需要具备什么条件

作为分布式 ID，通常建议需要具备以下 4个要求：

1.全局唯一

全局唯一，是指在支撑的业务范围内能保持全局唯一，这里的全局范围可大可小，大到成千上万部门的集团，小到某个团队内的几个系统，
所以在设计分布式 ID的时候，一定要清晰地定位受众范围。

2.数量够用

既然是分布式ID，那就一定要保证数量够用，需要根据公司具体业务来评估，在一定时间范围内会消耗多个ID，
比如，用于订单号，需要预估每年会产生多少订单，消耗需要多少个订单号，需要支持几年。

3.安全性

分布式 ID生成的算法应该是安全的，防止恶意用户预测或推断出其他ID，甚至恶意篡改。

4.有序性

通常建议分布式ID具备有序性，不过需要根据实际的业务来。

生成算法

UUID

UUID，Universally Unique Identifier（通用唯一识别码），由 128位（理论上限是 2^128个，绝对够用），通常表示成 32个十六进制数字，并且以“-”分隔成五组（8位-4位-4位-4位-12位），
比如：62f77d2d-aefe-41ba-b0f8-4c4c39ab670e。

UUID有 5种常见的生成方式，这里总结了构成，用途和特点：

1.基于时间戳和 MAC地址

构成：基于当前时间戳、时钟序列和机器的MAC地址。
用途：可以确保跨空间（不同机器）和时间的唯一性。
特点：可能会暴露生成 UUID的机器地址和时间。

Java的实现代码示例：

// gradle 依赖： implementation 'com.fasterxml.uuid:java-uuid-generator:5.0.0'
/** maven依赖
 <dependency>
    <groupId>com.fasterxml.uuid</groupId>
    <artifactId>java-uuid-generator</artifactId>
    <version>5.0.0</version>
 </dependency>
 */
import com.fasterxml.uuid.Generators;
public static void generateUUID() {
  UUID uuid = Generators.timeBasedGenerator().generate();
  System.out.println(uuid); // 比如：de02864c-eda8-11ee-a793-dd2f40a50976
}

2.DCE安全的UUID

构成：与方法1类似，但将一部分空间用于包含 POSIX的 UID或 GID。
用途：用于DCE（分布式计算环境）的安全性。
特点：并不常用，和方法1相似，但提供了额外的用户或组识别信息。

3.基于名字的MD5散列

构成：使用名字空间（Namespace）和特定名字生成 MD5散列。java.util.UUID 提供了这种方式，需要传入指，使用比较少。
用途：为相同名字生成相同的 UUID，但不同名字空间下的相同名字将生成不同的 UUID。
特点：相同输入产生相同输出，但由于 MD5容易被破解，不安全，因此现在使用较少。

Java的实现代码示例：


import java.util.UUID;
public static void generateUUID() {
  String key = "xxxxx"; // 自己指定的key
  UUID uuid3 = UUID.nameUUIDFromBytes(key.getBytes()).toString();
  System.out.println(uuid); // 比如：ea416ed0-759d-36a8-9e58-f63a59077499
}

4.随机生成

构成：使用随机数或伪随机数生成，java.util.UUID 是基于这种方式，使用比较多。
用途：不需要基于时间或名字，仅需要快速生成UUID。
特点：简单，没有时间顺序，不具备可预测性。

Java的实现代码示例：

import java.util.UUID;
public static void main(String[] args) {
  String uuid = UUID.randomUUID().toString();
  System.out.println(uuid); //比如：ea416ed0-759d-36a8-9e58-f63a59077499
}

5.基于名字的 SHA-1散列

构成：与方法3类似，使用 SHA-1散列算法代替 MD5。
用途：为相同名字生成相同的UUID，通常用于避免 MD5弱点的场景。
特点：比方法3的 MD5更安全，但SHA-1目前也已被认为不够安全，比较少使用。

Java的实现代码示例：

import java.security.MessageDigest;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.util.UUID;

public static UUID generateUUID(String namespace, String name) {
    try {
        MessageDigest sha1 = MessageDigest.getInstance("SHA-1");
        sha1.update(namespace.getBytes());
        byte[] result = sha1.digest(name.getBytes());

        // Set the version to 5
        result[6] &= 0x0f; // clear version
        result[6] |= 0x50; // set to version 5

        // Set the variant to 2
        result[8] &= 0x3f; // clear variant
        result[8] |= 0x80; // set to IETF variant

        ByteBuffer buffer = ByteBuffer.wrap(result);
        buffer.order(ByteOrder.BIG_ENDIAN);
        return new UUID(buffer.getLong(), buffer.getLong());
    } catch (Exception e) {
        throw new RuntimeException("Unable to generate Version 5 UUID", e);
    }
}
// 使用namespace和name生成Version 5 UUID
UUID uuid5 = generateType5UUID("namespace", "name"); // 比如：c717c842-f1d0-5079-a123-4a86d058c64f

到此，我们对 UUID有了一个全面的认识，最后，总结下 UUID的优缺点以及一些使用建议：

优点

生成方式简单，各种语言都有成熟的类库
本地生成，性能高，不依赖网络
随机机行强，不容被预测

缺点

无序，不利于排序，用于 MySQL主键时对索引不够友好
32位，字符串太长，存储需要消耗更多的空间
具体生成 UUID算法的缺点

使用建议

日常工作为了使用更美观，一般会把 UUID中的 “-”去掉
如果对 UUID的缺点没有任何要求，完全可以采用这种方式来生成分布式 ID，比如，作为接口的幂等ID
UUID有重复的概率，但是几乎可以忽略不计

ULID

ULID 是 Universally Unique Lexicographically Sortable Identifier的缩写，它是一种全局唯一、按字典序可排序的标识符。

ULID 由 48-bit的时间戳 + 80-bit 的随机数组成，时间戳表示自 1970 年 1 月 1 日 UTC 起的毫秒数，可以支持大约 280 年的时间范围。

下面借助三方库 Sulky ULID 演示如何使用 Java 生成 ULID：

import de.huxhorn.sulky.ulid.ULID;
public class ULIDTest {
    public static void main(String[] args) {
        ULID ulid = new ULID();
        String id = ulid.nextULID();
        System.out.println("ULID: " + id); // 01HTBBBDYK0YMQ8X1Z50QGDH9E
    }
}

最后总结下 ULID 的优缺点：

优点：

可排序：ULID 由 48-bit 时间戳开头，可以按照生成时间进行排序
高性能：由于 ULID 使用时间戳和随机数，生成速度较快。

缺点：

ULID 依赖于时间戳，极端情况可能会出现时间回拨导致 ID冲突

基于 Redis

在 Redis中，可以通过 INCR 和 INCRBY 等自增原子命令，来实现有序的分布式ID

下面总结下 Redis的优缺点：

优点

高性能
生成的ID有序

缺点

需要增加 Redis的成本
强依赖 Redis，因此需要保证 Redis服务的稳定性
生成的ID 有序，对于敏感业务，ID容易被预测

基于MySQL数据库

通过 MySQL数据表的主键（int 或 bigint）自增来生成 ID。

int（或 integer）

无符号的范围是 0 到 4294967295（42亿多）
有符号的范围是 -2147483648 到 2147483647

bigint

无符号的范围是 0 到 18446744073709551615
有符号的范围是 -9223372036854775808 到 9223372036854775807

假如每天消耗 1亿个，使用的总年数：18446744073709551615 / 100,000,000 / 365 ≈ 505061753 年。

假如每天消耗 1万亿个，使用的总年数：18446744073709551615 / 100,000,000,000,0 / 365 ≈ 50506 年（5万年）。

使用 MySQL的 bigint，就算业务体量每天消耗一万亿个 ID，需要 5万年才能消耗完，绝对够用。

接下来分析基于MySQL 的2种实现方式：

乞丐版

首先，创建一张 distributed_ids表，用于记录已经生成的 ID（如果 ID不想从 1开始，可以在创建表时给主键 ID设置一个起始值），表设计如下：

CREATE TABLE `distributed_ids` (
  `id` BIGINT(20) NOT NULL AUTO_INCREMENT,
  `created_at` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;
-- 或者
CREATE TABLE `distributed_ids` (
  `id` BIGINT(20) NOT NULL AUTO_INCREMENT,
  `created_at` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT 1000000; -- 1000000可以设置成具体的起始值

接着，我们需要包装一个 ID生成的服务对外提供给业务使用，整体架构思路图如下：

下面为对外提供服务核心步骤的 java伪代码：

@Controller
public class IdGeneratorController {
    @GetMapping("/generateId")
    public Long generateId() {
        Long id = null;
        synchronized (this) {
             // generate id;  sql: UPDATE distributed_ids SET id = id + 1(step);
            // select max id;  sql: SELECT id FROM distributed_ids ORDER BY id desc limit 1;
        }
        return id;
    }
}

到此，一个简单的 ID生成系统就完成了，总结下该方案的优缺点：

优点

实现简单，维护成本低
ID单调递增
可以用较少的成本实现体量较小的业务需求

缺点

每次获取 ID时候需要进行两次 DB操作
强依赖于 DB，DB性能以及稳定性直接影响 ID生成系统的稳定性，而且这里有 DB单节点的风险

对于缺点中单台 MySQL存在性能问题，我们自然会想到增加一台 MySQL，一台使用奇数自增（1,3,5,7,2n-1），一台使用偶数自增(2,4,6,8,2n)，这样是不是就可以分摊压力了？
如果 2台 MySQL还不够用，那我们可以使用 N台，每台的初始值依次为 1, 2, 3 … N-1，步长是N（机器的数量），整个架构思路图如下：

仔细观察上述架构图可以发现，对于 MySQL节点选择其实本质上是一个 Hash算法，因此，该方案存在 Hash算法典型的缺点：水平扩容困难，扩容时，需要涉及到大量的数据迁移。

那么，有没有一个更优的设计方案，既能减少对 DB的操作，又能避免 DB的性能瓶颈？

号段版

号段版是指每次获取一批 ID（比如 1000，10000），而不是一个 ID，然后在内存中去分发号段内的号码。对此，表结构该如何设计呢？

这里我们引入了号段最大值（max_id）和步长（step）两个概念，max_id是指表中末次获取号段时的最大 ID号，step是指每次获取多少个 ID。
比如，初始值是 1，第一次获取 1000个ID，那 max_id=1000， step=1000，第二获取 1000个ID，那么 max_id=2000， step=1000，表结构设计如下：

-- 号段 + 步长step
CREATE TABLE `distributed_ids` (
  `max_id` BIGINT(20) NOT NULL AUTO_INCREMENT,
  `step` INT(11) NOT NULL,
  `created_at` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT 1; -- 1可以设置成具体的起始值

整体架构思路图：

对于这个方案中的 step设置多大比较合理，一般会参考流量高峰期的是QPS/TPS，假设高峰期的 QPS是 1000（1s会消耗 1000个ID），
如果想取用一次号段持续使用 10分钟，那么 step=1000 * 60 * 10，即 step是 QPS的 600倍，以此类推，
也可以参考以往业务流量分布，确认峰值一般会维持多长时间，根据这个时间来设定一个合理的 step，这样就可以避免业务高峰期频繁去操作 DB获取号段。

总结下方案的优缺点

优点

一次批量获取 ID，大大降低了对 MySQL的压力，比如QPS是 1万，如果 step设置为1000，那么对 MySQL的压力就从 10000降到 10
step可以更具业务压力灵活调整，可以将此参数设置为配置变量

缺点

DB不可用导致整个ID生成系统不可用
ID规律性太强，很容易识别语义，比如，用于订单号时，可以根据某一个订单号轻易地猜测出其他订单号

对于缺点1，可以采用高可用容灾方案：主从（一主多从） + 多活（2地3活），当主节点挂了，可以切换到从节点，当机房A 出现问题，
可以切换到机房B，这样充分保证服服务器的高可用，思路看起来简单，但是实施起来比较困难，特别是主从切换的时候，如何保证数据一致性是一个比较大的挑战。

对于缺点2，可以采用雪花算法等方案来生成随机且递增的 ID，这部分内容会在其他的文章中分享。

整个高可用容灾方案如下图：

雪花算法

Snowflake，雪花算法是由 Twitter开源的分布式 ID生成算法，整个 ID保含有 64 bit，对表 Java的 Long类型，如下图：

以划分命名空间的方式将 64-bit位分割成多个部分，每个部分代表不同的含义。而 Java中64bit的整数是Long类型，所以在 Java 中 SnowFlake 算法生成的 ID 就是 long 来存储的。

为了更好的说明，我将 64bit 分成A,B,C,D 4部分：

A部分，占用 1-bit，代表符号位，其值始终是0
B部分，占用 41-bit，代表时间戳，可表示 2^41 个数，每个数代表毫秒，那么雪花算法可用的时间年限是(1L<<41)/(1000L360024*365)=69 年的时间。
C部分，占用 10-bit，代表机器数或者 IDC（数据中心）+机器数，如果是机器数，即 2^10 = 1024 台机器，如果是 IDC+机器数，一般会将它分成 5-bit 给 ID（最大 32个IDC）C，分5-bit给工作机器（最大 32太机器），这里可以根据自身业务特性看来灵活使用。
D部分，占用 12-bit，代表自增序列，可表示2^12 = 4096个数。

因此，基于上述的划分可以看出，每豪秒能产生 1024 * 4096个有序的不重复的ID。

总结下雪花算法的优缺点：

优点

本地生成，不依赖数据库等第三方系统，稳定性高
ID是趋势递增，对于敏感，不具备可预测性
可以根据自身业务特性灵活分配 bit位

缺点

强依赖机器时钟，如果时钟回拨，可能会导致 ID重复

三方工具

1.美团的 Leaf

Leaf是美团开源的分布式 ID生成工具，它包含 Leaf-segment 和 Leaf-snowflake两种方案， Leaf-segment是基于 MySQL数据库，它是针对上述 MySQL方案的更优秀设计，Leaf-snowflake 是基于雪花算法，并且解决雪花算法中时钟回拨的问题。

详情参考美团官方 Leaf文档：https://tech.meituan.com/2017/04/21/mt-leaf.html

2.百度-UidGenerator

UidGenerator 百度开源的一款用 Java语言实现，基于 Snowflake算法的唯一ID生成器。
包含 DefaultUidGenerator 和 CachedUidGenerator 2种实现方式：

DefaultUidGenerator 是基于时间戳和机器位还有序列号的生成方式，和雪花算法很相似，对于时钟回拨也只是抛异常处理。仅有一些不同，如以秒为为单位而不再是毫秒和支持Docker等虚拟化环境。
CachedUidGenerator 是使用 RingBuffer 缓存生成的id。数组每个元素成为一个slot。RingBuffer容量，默认为Snowflake算法中sequence最大值（2^13 = 8192）。可通过 boostPower 配置进行扩容，以提高 RingBuffer 读写吞吐量。

详情参考百度 UidGenerator文档：https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

总结

上述我们分析了几种常见的分布式 ID生成方式，具体选用哪种可以根据自身业务：

UUID，简单高校，但是无序，作为ID主键不友好；
MySQL 乞丐版，相对简单，但是不适合大流量的场景
MySQL 号段版，适合大流量的场景，当MySQL故障需要主从切换时需要保持数据的一致性
三方工具，经过生产环境的考验，是很不错的方式，如果不想重复造轮子，可以三方工具

交流学习

如果文章存在缺点和错误，欢迎批评指正。更多干货和面试经，关注公众号：猿java。