# 分布式ID生成策略总结

## 使用序列（数据库）

选择或者创建单独的一台数据库服务器，作为序列生成器，并提供主键获取服务。

## 序列与步长（数据库）

假设有两个分片，A分片可以设置步长为2，从1开始，B分片可以设置步长为2，从0开始，这样两台的主键就可以错开了。

> 这种方式的扩展性很差。

## 号段模式（数据库）

号段模式是当下分布式ID生成器的主流实现方式之一，号段模式可以理解为从数据库批量的获取自增ID，每次从数据库取出一个号段范围，例如 `(1,1000]` 代表1000个ID，具体的业务服务将本号段，生成`1~1000`的自增ID并加载到内存。表结构如下：

```sql
CREATE TABLE id_generator (
  id int(10) NOT NULL,
  max_id bigint(20) NOT NULL COMMENT '当前最大id',
  step int(20) NOT NULL COMMENT '号段的布长',
  biz_type    int(20) NOT NULL COMMENT '业务类型',
  version int(20) NOT NULL COMMENT '版本号',
  PRIMARY KEY (`id`)
) ;
```

字段说明：

* `biz_type` ：代表不同业务类型
* `max_id` ：当前最大的可用id
* `step` ：代表号段的长度
* `version` ：是一个乐观锁，每次都更新version，保证并发时数据的正确性

等这批号段ID用完，再次向数据库申请新号段，对`max_id`字段做一次`update`操作，`update max_id= max_id + step`，`update`成功则说明新号段获取成功，新的号段范围是`(max_id ,max_id +step]`。

优势：

1. 分布式id生成方式不强依赖于数据库，不会频繁的访问数据库，对数据库的压力小很多

缺点：

1. 服务器重启，单点故障可能会造成ID不连续

## 号段加双Buff（数据库）

每次从DB获取数据，采用每次获取一个范围，放到内存中，获取完再更新DB。

优点：

* 对DB压力小

缺点：

* 处理方式需要单独开发
* 性能不是很高：数据批量获取完毕后，再次获取有阻塞问题

## 使用序列（Redis incr）

使用redis incr命令，可以保证：

1. 全局唯一性
2. 原子性

优点：

1. 不依赖于数据库，灵活方便，且性能优于数据库
2. 数字ID有序，对分页处理和排序都很友好
3. 防止了Redis的单机故障

缺点：

1. 持久化问题
   1. AOF持久化可解决，但是会损失性能
   2. 搭建Redis集群，配置复杂，集群节点扩容也困难
2. 服务节点与Redis强绑定，服务间耦合较高，没有Redis就无法继续推进业务

## 号段加双Buff（Redis）

可能使用号段模式和Redis结合，一次获取200个id放入到缓存的有序集合中，然后从小到大依次取出使用。

## UUID

UUID 是由一组32位数的16进制数字所构成，以连字号分隔的五组来显示，形式为 `8-4-4-4-12`，总共有 36个字符（即三十二个英数字母和四个连字号），共计`2^128`次方种可能，基本不可能重复。例如：

```txt
aefbbd3a-9cc5-4655-8363-a2a43e6e6c80
xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx
```

UUID的组成，有前后顺序：

1. 当前时间戳
2. 时钟序列，当时间戳发生变化时，时钟序列重新计数
3. 机器/节点标识符，计算机网络接口卡（NIC）的MAC地址或其他能够提供唯一性的硬件信息生成的，用来区分不同的物理或逻辑设备

> 在UUID的不同版本中，可能有不同的变体，组成部分可能会有所不同，但是都可以保证很好的唯一性。

UUID的优点：

1. 简单，使用方便
2. 性能高
3. 唯一性强

UUID的缺点：

1. 没有排序，无法保证单调性。
2. mysql的索引是通过b+树来实现的，每一次新的UUID数据的插入，为了查询的优化，都会对索引底层的b+树进行修改，因为UUID数据是无序的，所以每一次UUID数据的插入都会对主键生成的b+树进行很大的修改
3. 字符串存储，查询效率比较低
4. 占用空间过大，传输效率低
5. 基于MAC地址生成UUID的算法可能会造成MAC地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置

> UUID输在存储以及单调性上，但是UUID用作产品唯一序列号这种唯一的编号上还是很适合的。

## ULID

格式规范：

```txt
01AN4Z07BY      79KA1307SR9X4MV3
 
|----------|    |----------------|
 Timestamp          Randomness
  10chars            16chars
   48bits             80bits
```

与UUID的差异：

* 长度：UUID 是一个 128 位的二进制值，通常表示为 32 个十六进制数字，分为 5 个组。ULID 是一个 128 位的二进制值，但表示为 26 个字符的十六进制字符串和 10 个字符的时间戳。因此，ULID 的长度比 UUID 短。
* 唯一性：UUID 和 ULID 都具有很高的唯一性。UUID 的生成算法保证了在全球范围内的唯一性。ULID 的生成算法在相同的时间戳下具有极低的冲突概率，但在不同时间戳下的唯一性取决于生成器的实现。
* 有序性：UUID 是无序的，因为它们是一个二进制值。ULID 是有序的，因为它们包含一个时间戳部分，可以按照生成时间进行字母排序。
* 可读性：UUID 通常表示为 32 个十六进制数字，没有明确的格式或结构。ULID 由 26 个字符的十六进制字符串和 10 个字符的时间戳组成，易于阅读和识别。
* 性能：由于 ULID 的长度较短，生成和比较 ULID 的性能通常优于 UUID。

适用场景：

* UUID 更适合在不需要排序或具有明确时间上下文的场景中使用，如分布式系统中的实体标识、数据库主键等。
* ULID 更适合在需要排序或具有时间上下文的场景中使用，如时间序列数据、日志记录等。

## Twitter 雪花算法

Snowflake，雪花算法是有Twitter开源的分布式ID生成算法，以划分命名空间的方式将64bit位分割成了多个部分，每个部分都有具体的不同含义，在Java中64Bit位的整数是Long类型，所以在Java中Snowflake算法生成的ID就是long来存储的。具体如下：

![](/files/zFCGq6f0GD1DVbh5aQEa)

* 第一部分：占用1bit,第一位为符号位，不适用
* 第二部分：41位的时间戳，41bit位可以表示`2^41`个数，每个数代表的是毫秒，那么雪花算法的时间年限是`(2^41)/(1000×60×60×24×365)`=69年
* 第三部分:10bit表示是机器数，即 `2^ 10 = 1024`台机器，通常不会部署这么多机器。注意，这个机器id，是由调用方传入的，而不是自己计算的
* 第四部分:12bit位是自增序列，可以表示`2^12=4096`个数，单个时间戳内可以生成4096个ID

### 生产系统中如何使用雪花算法？

* ![](/files/SfvQS61LX2S5UlPuNfMK)
* 每个服务依赖一个通用的common包，在common包中生成雪花算法
* 雪花算法所需要的机器id将交由yaml配置文件配置，每个集群节点的机器id配置都不同

方式二，将雪花算法部署位单独的服务，调用接口获ID，可以提供不同的语言使用

1. ![](/files/RBFK9AnPQeAgEDUopjOk)
2. 提供雪花算法服务并注册到Nacos中，每个服务集群对应一个雪花算法服务（也可以使用一个服务，通过服务名称区分），每个雪花算法服务都有自己的工作节点id
3. 其他服务集群调用自己的id生成服务，获取服务id
4. 扩展性强，但是会产生IO性能问题
5. 单独部署id生成器，可以有效防止时钟回拨的问题，即使发生回拨，直接将时间调大就可以了，不需要与真实的时间同步。注意，这台服务器不需要时钟同步。

### 如何解决时钟回拨问题？

* ![](/files/epp2ERd2drauKDxoXkSR)
* 雪花算法是如何发现时钟回拨的问题的？ 它内部会记录上次生成ID的时间戳。

### 如何动态分配与回收机器id？

#### 使用redis的zset集合来实现（[参考](https://juejin.cn/post/7280747572695679036)）：

1. 提前插入机器id序号范围的元素，比如 `0~1023`，`EVAL "for i=1,1023 do redis.call('SADD', 'worker_id_pool', i) end" 0`。
2. 启动SpringBoot应用程序后，每隔一段时间向Redis发送心跳，获取所有的可用的 机器id。
3. 循环所有机器ID，找到不在 `worker_id_used_*`开头的所有锁定标记下的机器ID。
4. 将取到的未使用的机器ID设置锁定标记：`setIfAbsent("worker_id_used_机器id")`，并设置过期时间为心跳时间+一小段时间。
5. 如果设置锁定失败，继续循环上述的操作，直到成功为止。
6. 如果设置锁定成功，说明机器ID已经设置成功，分片算法可以使用了。
7. 当当前机器宕机，他不会向Redis发送心跳，超过key的过期时间后，机器id将会被自动释放。
8. 当下一次心跳发生时，如果当前服务有机器ID，会刷新锁的时间，保证当前机器可以一直持有这个ID。

#### 使用Zookeeper的临时节点实现：

// todo 待处理

### 机器ID上限问题？

需要使用其他方案替代，尽量按照业务细分ID，不要多个业务共用一个生成策略。

### 超高并发的序列的上限问题？

1. 使用未来时间，当序列超过最大值时，自动提升时间戳

### 源码解析

```java
/**
 * Twitter_Snowflake
 * SnowFlake的结构如下(每部分用-分开):
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
 * 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0
 * 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)
 * 得到的值），这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69
 * 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId
 * 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号
 * 加起来刚好64位，为一个Long型。
 * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。
 */
public class SnowflakeIdWorker {

    // ==============================Fields===========================================
    /**
     * 开始时间截 (2020-11-03，一旦确定不可更改，否则时间被回调，或者改变，可能会造成id重复或冲突)
     */
    private final long twepoch = 1604374294980L;

    /**
     * 机器id所占的位数
     */
    private final long workerIdBits = 5L;

    /**
     * 数据标识id所占的位数
     */
    private final long datacenterIdBits = 5L;

    /**
     * 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数)
     */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /**
     * 支持的最大数据标识id，结果是31
     */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    /**
     * 序列在id中占的位数
     */
    private final long sequenceBits = 12L;

    /**
     * 机器ID向左移12位
     */
    private final long workerIdShift = sequenceBits;

    /**
     * 数据标识id向左移17位(12+5)
     */
    private final long datacenterIdShift = sequenceBits + workerIdBits;

    /**
     * 时间截向左移22位(5+5+12)
     */
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    /**
     * 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095)
     */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /**
     * 工作机器ID(0~31)
     */
    private long workerId;

    /**
     * 数据中心ID(0~31)
     */
    private long datacenterId;

    /**
     * 毫秒内序列(0~4095)
     */
    private long sequence = 0L;

    /**
     * 上次生成ID的时间截
     */
    private long lastTimestamp = -1L;

    //==============================Constructors=====================================

    /**
     * 构造函数
     *
     */
    public SnowflakeIdWorker() {
        this.workerId = 0L;
        this.datacenterId = 0L;
    }

    /**
     * 构造函数
     *
     * @param workerId     工作ID (0~31)
     * @param datacenterId 数据中心ID (0~31)
     */
    public SnowflakeIdWorker(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }

    // ==============================Methods==========================================

    /**
     * 获得下一个ID (该方法是线程安全的)
     *
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();

        //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
        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;
        }

        //上次生成ID的时间截
        lastTimestamp = timestamp;

        //移位并通过或运算拼到一起组成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (datacenterId << datacenterIdShift) //
                | (workerId << workerIdShift) //
                | sequence;
    }

    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     *
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 返回以毫秒为单位的当前时间
     *
     * @return 当前时间(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }

    /**
     * 随机id生成，使用雪花算法
     *
     * @return
     */
    public static String getSnowId() {
        SnowflakeIdWorker sf = new SnowflakeIdWorker();
        String id = String.valueOf(sf.nextId());
        return id;
    }

    //=========================================Test=========================================

    /**
     * 测试
     */
    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);
        }
    }
}
```

## [百度 Uidgenerator](https://github.com/baidu/uid-generator)（雪花算法优化）

UidGenerator是百度开源的Java语言实现，基于Snowflake算法的唯一ID生成器。它是分布式的，并克服了雪花算法的并发限制。单个实例的QPS能超过`6000000`。需要的环境：`JDK8+`，`MySQL`（用于分配`WorkerId`）。

![](/files/hOl4OoLn2tTC9srC88P6)

Uidgenerator 改变时间部分只有28位，这就意味着UidGenerator默认只能承受8.5年（2^28-1/86400/365）。也可以根据你业务的需求，UidGenerator可以适当调整`delta seconds`、`worker node id`和`sequence`占用位数。

* `sign(1bit)`：固定1bit符号标识，即生成的UID为正数。
* `delta seconds (28 bits)`：当前时间，相对于时间基点"2016-05-20"的增量值，单位：秒，最多可支持约8.7年
* `worker id (22 bits)`：机器id，最多可支持约420w次机器启动。内置实现为在启动时由数据库分配，默认分配策略为用后即弃，后续可提供复用策略。
* `sequence (13 bits)`：每秒下的并发序列，13 bits可支持每秒8192个并发。

上述字段长度都可进行配置，如果应用程序期望运行时间较长，比如对于并发数要求不高、期望长期使用的应用, 可增加`timeBits`位数, 减少`seqBits`位数：

```json
{"timeBits":31,"workerBits":23,"seqBits":9}
```

### 如何解决时钟回拨问题？

如果秒级别发生偏移，直接抛出异常，相当于没有处理！

```java
// 当前秒数小于上次生成id的秒数，说明发生了时钟偏移，直接抛出异常  
// 这里处理的不是很好，太粗暴了  
// Clock moved backwards, refuse to generate uid  
if (currentSecond < lastSecond) {  
    long refusedSeconds = lastSecond - currentSecond;  
    throw new UidGenerateException("Clock moved backwards. Refusing for %d seconds", refusedSeconds);  
}  
  
// At the same second, increase sequence  
// 如果当前秒数相同，开始生成序列  
if (currentSecond == lastSecond) {  
    sequence = (sequence + 1) & bitsAllocator.getMaxSequence();  
    // Exceed the max sequence, we wait the next second to generate uid  
    if (sequence == 0) {  
        currentSecond = getNextSecond(lastSecond);  
    }  
  
// At the different second, sequence restart from zero  
} else {  
    sequence = 0L;  
}
```

### 如何动态分配与回收机器id？

## [Butterfly](https://github.com/simonalong/Butterfly)（雪花算法优化）

参考文章：<https://www.yuque.com/simonalong/butterfly>

## [美团 Leaf](https://github.com/Meituan-Dianping/Leaf)

[官方文档](https://tech.meituan.com/2017/04/21/mt-leaf.html)

### Leaf-segment（数据库+号段）

![](/files/lS8TJxxI9BltO9vU92Y8)

### Leaf-snowflak（雪花算法优化）

1. 时钟回拨问题方案（周期性上传zk，然后校验当前时间是否可在可承受的阈值内）： ![](/files/gUQ7GpxVCCBy6qKNxPEx)
2. workId分配是有zk的临时节点完成的，并且在本地磁盘存储workId的缓存，防止机器重启时，zk服务不可用的问题

## [滴滴 TinyID](https://github.com/didi/tinyid)（数据库+号段）

他是基于 Leaf-segment 的进一步的优化，提供jar以及http的访问方式。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yangsx95.gitbook.io/notes/distributed/fen-bu-shi-id/fen-bu-shi-id-sheng-cheng-ce-le-zong-jie.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.