分布式系统中，我们经常需要对数据、消息等进行唯一标识，这个唯一标识就是分布式 ID，那么我们如何设计它呢？本文将详细讲述分布式 ID 及其生成方案。

为什么需要分布式 ID

目前大部分的系统都已是分布式系统，所以在这种场景的业务开发中，经常会需要唯一 ID 对数据进行标识，比如用户身份标识、消息标识等等。

并且在数据量达到一定规模后，大部分的系统也需要进行分库分表，这种场景下单库的自增 ID 已达不到我们的预期。所以我们需要分布式 ID 来对各种场景的数据进行唯一标识。

分布式 ID 的特性

主要特性：

全局唯一：分布式 ID 最基本要求，必须全局唯一。
高可用：高并发下要保证 ID 的生成效率，避免影响系统。
易用性：使用简单，可快速接入。

除此之外根据不同场景还有：

有序性：数据库场景下的主键 ID，有序性可便于数据写入和排序。
安全性：无规则 ID，一般用于避免业务信息泄露场景，如订单量。

分布式 ID 常见生成方案

UUID

UUID（Universally Unique Identifier），即通用唯一识别码。UUID 的目的是让分布式系统中的所有元素都能有唯一的识别信息。

UUID 是由128位二进制数组成，通常表示为32个十六进制字符，形如：

1	550e8400-e29b-41d4-a716-446655440000

这个字符串由五个部分组成，以连字符-分隔开，具体如下：

部分	大小	说明
时间戳	32 bits	UUID的前32位表示当前的时间戳。
时钟序列和随机数	16 bits	用于保证在同一时刻生成的UUID的唯一性。
变体标识	4 bits	标识 UUID 的变体，通常为固定值，表示是由 RFC 4122 定义。
版本号	4 bits	标识UUID的版本，常见版本有1、3、4和5
节点	48 bits	在版本 1 中，这部分包含生成 UUID 的计算机的唯一标识。

主要的 UUID 版本及其生成规则：

版本	场景	生成规则
版本 1	基于时间和节点	由当前的时间戳和节点信息生成。包括时间戳、时钟序列、节点标识。
版本 2	基于DCE安全标识符	类似版本 1，但在时间戳部分包含 POSIX UID/GID 信息。
版本 3	基于名字和散列值（MD5 版）	由命名空间和名字的MD5散列生成。
版本 4	完全随机生成	通过随机或伪随机生成128位数字。
版本 5	基于名字和散列值（SHA-1 版）	通过随机或伪随机生成128位数字。

Java中 UUID 对版本 4 进行了实现：

public static void main (String[] args) {
    // 默认版本 4
    System.out.println(UUID.randomUUID());

    // 版本 3，由命名空间和名字的MD5散列生成，相同命名空间结果相同
    // 如下，"fuxing"返回的UUID一直为8b9b6bc3-90c8-37ef-bbef-0ed0c552718f
    System.out.println(UUID.nameUUIDFromBytes("fuxing".getBytes()));
}

优点：本地生成，没有网络消耗，性能非常高。

缺点：

占用空间大，32 个字符串，128 位。
不安全：版本 1 可能会造成 mac 地址泄露。
无序，非自增。
机器时间不对，可能造成 UUID 重复。

数据库自增 ID

实现简单，解释通过数据库表中的主键 ID 自增来生成唯一标识。如下，维护一个 MySQL 表来生成 ID。

CREATE TABLE `unique_id` (
  `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `value` char(10) NOT NULL DEFAULT '',
  PRIMARY KEY (`id`),
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

当需要生成分布式 ID 时，向表中插入数据并返回主键 ID，这里 value 无含义，只是为了占位，方便插入数据。

优点：实现简单，基本满足业务需求，且天然有序。

缺点：

数据库自身的单点故障和数据一致性问题。
不安全，比如可根据自增来判断订单量。
高并发场景可能会受限于数据库瓶颈。

那么有没有办法解决数据库自增 ID 的缺点呢？

通过水平拆分的方案，将表设置到不同的数据库中，设置不同的起始值和步长，这样可以有效的生成集群中的唯一 ID，也大大降低 ID 生成数据库操作的负载，示例如下。

<font style="color:rgb(62, 62, 62);">unique_id_1</font>配置：

1 2	set @@auto_increment_offset = 1; -- 起始值 set @@auto_increment_increment = 2; -- 步长

<font style="color:rgb(62, 62, 62);">unique_id_2</font>配置：

1 2	set @@auto_increment_offset = 2; -- 起始值 set @@auto_increment_increment = 2; -- 步长

这个还是需要根据自己的业务需求来，水平扩展的集群数量要符合自己的数据量，因为当设置的集群数量不足以满足高并发时，再次进行扩容集群会很麻烦。多台机器的起始值和步长都需要重新配置。

数据库号段模式

号段模式是当下分布式 ID 生成器的主流实现方式之一，比如美团 Leaf-segment、滴滴 Tinyid、微信序列号等都使用的该方案，下面的大厂中间件中会展开说明。

号段模式也是基于数据库的自增 ID，数据库自增 ID 是一次性获取一个分布式 ID，**号段模式可以理解成从数据库批量获取 ID，然后将 ID 缓存在本地**，以此来提高业务获取 ID 的效率。

例如，每次从数据库获取 ID 时，获取一个号段，如(1,1000]，这个范围表示 1000 个 ID，业务应用在请求获取 ID 时，只需要在本地从 1 开始自增并返回，而不用每次去请求数据库，一直到本地自增到 1000 时，才去数据库重新获取新的号段，后续流程循环往复。

表结构可进行如下设计：

CREATE TABLE `id_generator` (
  `id` int(10) NOT NULL,
  `max_id` bigint(20) NOT NULL COMMENT '当前最大id',
  `step` int(10) NOT NULL COMMENT '号段的步长',
  `version` int(20) NOT NULL COMMENT '版本号',
  `biz_type` int(20) NOT NULL COMMENT '业务场景',
   PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

其中max_id和step用于获取批量的 ID，version是一个乐观锁，保证并发时数据的正确性。

比如，我们新增一条表数据如下。

id	max_id	step	version	biz_type
1	100	1000	0	001

然后我们可以使用该号段批量生成的 ID，当max_id = 1000，则执行 update 操作生成新的号段。新的号段的 SQL。

UPDATE 
id_generator 
SET 
max_id = #{max_id+ step}, 
version = version + 1 
WHERE 
version = #{version} AND biz_type = 001;

优点：ID 有序递增、存储消耗空间小。

缺点：

数据库自身的单点故障和数据一致性问题。
不安全，比如可根据自增来判断订单量。
高并发场景可能会受限于数据库瓶颈。

缺点同样可以通过集群的方式进行优化，也可以如Tinyid 采用双缓存进行优化，下面的大厂中间件中会展开说明。

基于Redis

当使用数据库来生成 ID 性能不够的时候，可以尝试使用 Redis 来生成 ID。原理则是利用 Redis 的原子操作 INCR 和 INCRBY 来实现。

命令示例：

命令	说明	示例
INCR	让一个整形的key自增1	:::tips redis> SET mykey “10” “OK” redis> INCR mykey (integer) 11 :::
INCRBY	让一个整形的key自增并指定步长	:::tips redis> SET mykey “10” “OK” redis> INCRBY mykey 5 (integer) 15 :::

优点：不依赖于数据库，使用灵活，支持高并发。

缺点：

系统须引入 Redis 数据库。
不安全，比如可根据自增来判断订单量。
Redis 出现单点故障问题，可能会丢数据导致 ID 重复。

雪花算法

雪花算法（Snowflake）是 twitter 公司内部分布式项目采用的 ID 生成算法。结果是一个 long 型的 ID。Snowflake 算法将 64bit 划分为多段，分开来标识机器、时间等信息，具体组成结构如下图所示：

结构说明：

结构	大小	说明
符号位	1 bit	0 表示正数，1 表示负数。
时间戳	41 bits	存储的是`当前时间戳 - 开始时间戳`，最长 69 年。
机器位	10 bits	前 5位 datacenterId，后 5 位 workerId ，最多表示 1024 台。
序列号	12 bits	毫秒内的流水号，意味着每个节点在每毫秒可以产生 4096 个 ID。

优点：

稳定性高，不依赖于数据库等第三方系统。

使用灵活方便，可以根据业务需求的特性来调整算法中的 bit 位。

单机上 ID 单调自增，毫秒数在高位，自增序列在低位，整体上按照时间自增排序。

缺点：

强依赖机器时钟，如果机器上时钟回拨，可能导致发号重复或者服务处于不可用状态。
ID 可能不是全局递增，虽然 ID 在单机上是递增的。
Redis 出现单点故障问题，可能会丢数据导致 ID 重复。

当我们选择了雪花算法可以参考shardingsphere的雪花算法，以此为例来写一个starter

定义接口

public class DefaultIdGenerator implements IdGenerator {

    @Override
    public long nextId() {
        Comparable<?> key=  IDUtils.generateKey();
        return (Long) key;
    }
}

定义雪花算法实现

package com.fbb.pomelo.id.utils;

import com.google.common.base.Preconditions;
import lombok.Getter;
import lombok.Setter;
import lombok.SneakyThrows;
import lombok.experimental.UtilityClass;
import lombok.extern.slf4j.Slf4j;

import java.net.NetworkInterface;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

@Slf4j
@UtilityClass
public final class IDUtils {
    public static final long EPOCH;

    private static final long SEQUENCE_BITS = 12L;

    private static final long WORKER_ID_BITS = 10L;

    private static final long SEQUENCE_MASK = (1 << SEQUENCE_BITS) - 1;

    private static final long WORKER_ID_LEFT_SHIFT_BITS = SEQUENCE_BITS;

    private static final long TIMESTAMP_LEFT_SHIFT_BITS = WORKER_ID_LEFT_SHIFT_BITS + WORKER_ID_BITS;

    private static final long WORKER_ID_MAX_VALUE = 1L << WORKER_ID_BITS;

    private static final long WORKER_ID = 0;

    private static final int DEFAULT_VIBRATION_VALUE = 1;

    private static final int MAX_TOLERATE_TIME_DIFFERENCE_MILLISECONDS = 10;

    @Setter
    private static TimeService timeService = new TimeService();

    @Getter
    @Setter
    private Properties properties = new Properties();

    private int sequenceOffset = -1;

    private long sequence;

    private long lastMilliseconds;

    static {
        Calendar calendar = Calendar.getInstance();
        calendar.set(2016, Calendar.NOVEMBER, 1);
        calendar.set(Calendar.HOUR_OF_DAY, 0);
        calendar.set(Calendar.MINUTE, 0);
        calendar.set(Calendar.SECOND, 0);
        calendar.set(Calendar.MILLISECOND, 0);
        EPOCH = calendar.getTimeInMillis();
    }

    public synchronized Comparable<?> generateKey() {
        long currentMilliseconds = timeService.getCurrentMillis();
        if (waitTolerateTimeDifferenceIfNeed(currentMilliseconds)) {
            currentMilliseconds = timeService.getCurrentMillis();
        }
        if (lastMilliseconds == currentMilliseconds) {
            if (0L == (sequence = (sequence + 1) & SEQUENCE_MASK)) {
                currentMilliseconds = waitUntilNextTime(currentMilliseconds);
            }
        } else {
            vibrateSequenceOffset();
            sequence = sequenceOffset;
        }
        lastMilliseconds = currentMilliseconds;
        return ((currentMilliseconds - EPOCH) << TIMESTAMP_LEFT_SHIFT_BITS) | (getWorkerId() << WORKER_ID_LEFT_SHIFT_BITS) | sequence;
    }

    @SneakyThrows
    private boolean waitTolerateTimeDifferenceIfNeed(final long currentMilliseconds) {
        if (lastMilliseconds <= currentMilliseconds) {
            return false;
        }
        long timeDifferenceMilliseconds = lastMilliseconds - currentMilliseconds;
        Preconditions.checkState(timeDifferenceMilliseconds < getMaxTolerateTimeDifferenceMilliseconds(),
                "Clock is moving backwards, last time is %d milliseconds, current time is %d milliseconds", lastMilliseconds, currentMilliseconds);
        Thread.sleep(timeDifferenceMilliseconds);
        return true;
    }

    private long getWorkerId() {
        long result = Long.valueOf(properties.getProperty("worker.id", String.valueOf(WORKER_ID)));
        if (result <= 0L){
            result = generateWorkerId();
        }
        Preconditions.checkArgument(result >= 0L && result < WORKER_ID_MAX_VALUE);
        return result;
    }

    private int getMaxVibrationOffset() {
        int result = Integer.parseInt(properties.getProperty("max.vibration.offset", String.valueOf(DEFAULT_VIBRATION_VALUE)));
        Preconditions.checkArgument(result >= 0 && result <= SEQUENCE_MASK, "Illegal max vibration offset");
        return result;
    }

    private int getMaxTolerateTimeDifferenceMilliseconds() {
        return Integer.valueOf(properties.getProperty("max.tolerate.time.difference.milliseconds", String.valueOf(MAX_TOLERATE_TIME_DIFFERENCE_MILLISECONDS)));
    }

    private long waitUntilNextTime(final long lastTime) {
        long result = timeService.getCurrentMillis();
        while (result <= lastTime) {
            result = timeService.getCurrentMillis();
        }
        return result;
    }

    private void vibrateSequenceOffset() {
        sequenceOffset = sequenceOffset >= getMaxVibrationOffset() ? 0 : sequenceOffset + 1;
    }

    private long generateWorkerId() {
        try {
            return generateWorkerIdBaseOnMac();
        } catch (Exception e) {
            return generateRandomWorkerId();
        }
    }
    /**
     * randomly generate one as workerId
     * @return workerId
     */
    private long generateRandomWorkerId() {
        return new Random().nextInt((int)WORKER_ID_MAX_VALUE + 1);
    }
    /**
     * use lowest 10 bit of available MAC as workerId
     * @return workerId
     * @throws Exception when there is no available mac found
     */
    private long generateWorkerIdBaseOnMac() throws Exception {
        Enumeration<NetworkInterface> all = NetworkInterface.getNetworkInterfaces();
        while (all.hasMoreElements()) {
            NetworkInterface networkInterface = all.nextElement();
            boolean loopBack = networkInterface.isLoopback();
            boolean isVirtual = networkInterface.isVirtual();
            if (loopBack || isVirtual) {
                continue;
            }
            byte[] mac = networkInterface.getHardwareAddress();
            return ((mac[4] & 0B11) << 8) | (mac[5] & 0xFF);
        }
        throw new RuntimeException("no available mac found");
    }
    /**
     * 获取随机ID
     * @return 随机ID用以替代传统的UUID
     */
    public String get32UUID() {
        ThreadLocalRandom random = ThreadLocalRandom.current();
        return (new UUID(random.nextLong(), random.nextLong())).toString().replace("-", "");
    }

}

public class TimeService {
    public long getCurrentMillis() {
        return System.currentTimeMillis();
    }
}

配置文件

@SpringBootConfiguration
public class IdAutoConfiguration {
    /**
     * 注入ID生成器实现
     * @return see {@link DefaultIdGenerator}
     */
    @Bean
    @ConditionalOnMissingBean
    public IdGenerator idGenerator() {
        return new DefaultIdGenerator();
    }
}

META-INF

1
2
3

org.springframework.boot.autoconfigure.EnableAutoConfiguration=\
     com.fbb.pomelo.id.configuration.IdAutoConfiguration

大厂中间件

美团 Leaf

Leaf 的官方文档，简介和特性可访问了解，这里我将对 Leaf 的两种方案，Leaf segment 和 Leaf-snowflake 进行。

Leaf segment

基于数据库号段模式的 ID 生成方案，上面我们介绍到普通的号段模式有一些缺点：

数据库自身的单点故障和数据一致性问题。
不安全，比如可根据自增来判断订单量。
高并发场景可能会受限于数据库瓶颈。

那么 Leaf 是如何做的呢？Leaf 采用了预分发的方式生成ID，也就是在 DB 之上挂 n 个 Leaf Server，每个Server启动时，都会去 DB 拿固定长度的 ID List。

这样就做到了完全基于分布式的架构，同时因为ID是由内存分发，所以也可以做到很高效，处理流程图如下：

其中：

Leaf Server 1：从 DB 加载号段[1，1000]。
Leaf Server 2：从 DB 加载号段[1001，2000]。
Leaf Server 3：从 DB 加载号段[2001，3000]。

用户**通过轮询的方式**调用 Leaf Server 的各个服务，所以某一个 Client 获取到的ID序列可能是：1，1001，2001，2，1002，2002。当某个 Leaf Server 号段用完之后，下一次请求就会从 DB 中加载新的号段，这样保证了每次加载的号段是递增的。

为了解决在更新DB号段的时出现的耗时和阻塞服务的问题，Leaf 采用了**异步更新**的策略，同时通过双缓存的方式，保证无论何时DB出现问题，都能有一个 Buffer 的号段可以正常对外提供服务，只要 DB 在一个 Buffer 的下发的周期内恢复，就不会影响整个 Leaf 的可用性。

除此之外，Leaf 还**通过动态调整步长**，解决由于步长固定导致的缓存中的 ID 被过快消耗问题，以及步长设置过大导致的号段 ID 跨度过大问题，具体公式可去官方文档中了解。

对于数据一致性问题，Leaf 目前是通过中间件 Zebra 加 MHA 做的主从切换。

Leaf Snowflake

Leaf-snowflake 方案沿用 Snowflake 方案的 bit 位设计。

对于 workerID 的分配：当服务集群较小时，通过配置即可；服务集群较大时，基于 zookeeper 持久顺序节点的特性引入 zookeeper 组件配置 workerID。架构如下图所示：

百度 UidGenerator

开源地址

UidGenerator 方案是基于 Snowflake 算法的 ID 生成器，其对雪花算法的 bit 位的分配做了微调。

结构说明（参数可在 Spring Bean 配置中进行配置）：

结构	大小	说明
符号位	1 bit	最高位始终是 0。
增量秒	28 bits	表示自客户纪元（2016-05-20）以来的增量秒。最大时间为 8.7 年。
工作节点	22 bits	表示工作节点 ID，最大值为 4.2 百万个。
序列号	13 bits	表示一秒钟内的序列，默认情况下每秒最多 8192 个。

UidGenerator 方案包含两种实现方式，DefaultUidGenerator 和 CachedUidGenerator ，性能要求高的情况下推荐 CachedUidGenerator。

滴滴 Tinyid

Tinyid 官方文档

Tinyid 方案是在 Leaf-segment 的算法基础上升级而来，不仅支持了数据库多主节点模式，还提供了 tinyid-client 客户端的接入方式，使用起来更加方便。

Tinyid 也是采用了异步加双缓存策略，首先可用号段加载到内存中，并在内存中生成 ID，可用号段在首次获取 ID 时加载，号段用到一定程度的时候，就去异步加载下一个号段，保证内存中始终有可用号段，则可避免性能波动。

实现原理如下所示：

结语

本文对分布式 ID 以及其场景的生成方案做了介绍，还针对一下大厂的中间件进行简单分析，中间件的接入代码本文并没有做详细介绍，但是官方文档的链接都帖子了每个子标题下，其中都有详细介绍。

文中还针对每个生成方案的优缺点作出了说明，具体的使用可针对优缺点加上业务需求来进行选型。

参考：

[1] 腾讯技术工程. 分布式唯一 ID 生成方案浅谈.

[2] 孟斯特. UUID 介绍.

[3] 文丑颜不良啊. 雪花算法（SnowFlake）.

进学阁

分布式ID总结

分布式系统中，我们经常需要对数据、消息等进行唯一标识，这个唯一标识就是分布式 ID，那么我们如何设计它呢？本文将详细讲述分布式 ID 及其生成方案。

为什么需要分布式 ID

分布式 ID 的特性

分布式 ID 常见生成方案

UUID

数据库自增 ID

数据库号段模式

基于Redis

雪花算法

大厂中间件

美团 Leaf

Leaf segment

Leaf Snowflake

百度 UidGenerator

滴滴 Tinyid

结语