前言

日常开发中，数据需要使用唯一的ID来标识，一般情况下使用自增主键作为数据ID。但是在大数量的情况下，往往会引入分库分表，这时自增ID已经无法满足需求了，就需要一个能够生成全局唯一ID的系统。

分布式ID

在分布式系统中，因为有多个计算节点，所以在生成唯一标识符（ID）时，不能依赖单点生成，需要保证在全局范围内每个ID是唯一的，这种全局唯一的ID就是所谓的分布式ID。

以下是一些典型的生成分布式ID的需求和原则：

1. 「全局唯一性」：无论ID在何处生成，都需要保证在全局范围内是唯一的。
2. 「趋势递增」：在MySQL InnoDB引擎中使用的是聚簇索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，所以在索引列上如果使用自增ID，那么每次插入新的记录，都是添加到当前索引节点的最右边，当一页满了以后，就会分裂出新的页，因此写操作（包括更新和删除）都不会触发结构调整，效率较高。这是为什么许多人推荐使用趋势递增的ID。
3. 「一定含义」：在某些场景下，我们希望ID能够携带一些信息，例如创建时间、业务类型等。
4. 「高效性能」：ID生成效率要高，不能存在严重的性能瓶颈。
5. 「可用性」：保证在服务宕机后，依然能够获取到ID。

一些常见的分布式ID生成策略有：UUID、雪花算法（Twitter的Snowflake）、数据库自增ID、基于Redis的ID生成方案等。具体选择哪种方案，需要根据系统的实际需求来决定。

常见方法

UUID

UUID 是由 128 位的数字组成，通常由 32 个字符表示，以特定的方式排列，例如：550e8400-e29b-41d4-a716-446655440000。这种方式生成的唯一标识符在全局范围内都是唯一的。

由于 UUID 是由 128 位的数生成的，所以 UUID 的总数是 2 的 128 次方，这是一个极其庞大的数字，大到在实际应用中，生成两个相同的 UUID 的概率可以忽略不计。

UUID 的主要目的是让信息的创建者能够创建唯一的标识符，而不需要通过中心数据库来保证其唯一性。因此，无论是在分布式系统还是在单个项目中，都可以使用 UUID 生成独特的键。

UUID 有多种生成版本，包括：

1. 基于时间和 MAC 地址的 UUID（Version 1）。
2. DCE 安全的 UUID（Version 2）。
3. 基于 MD5 散列和命名空间的 UUID（Version 3）。
4. 基于随机数的 UUID（Version 4）。
5. 基于 SHA-1 散列和命名空间的 UUID（Version 5）。

其中在java中我们用到的四Version4版本生成的。

UUID uuid = UUID.randomUUID();
System.out.println(uuid.toString());

「优缺点：」

优点：本地生成，没有网络消耗。

「缺点：」

不易存储，uuid太长了。如果用的Version1 MAC地址生成的，可能会导致MAC地址泄漏。

从Mysql索引角度思考：

mysql的主键尽量越短越好，一方面根据索引定位比较索引的时候，占用空间越小比较越快。另一方面排序，主键索引是排好序的，如果乱插入会导致之前排好序的叶子节点打破重组。

雪花算法

雪花算法（Snowflake Algorithm）是 Twitter 公司开源的一种生成全局唯一 ID 的方法，主要用来满足 Twitter 系统内高并发请求和分布式系统环境下生成全局唯一标识符的需求。

雪花算法

它是一个64位的二进制数，包括四部分：

1. 符号位：最高位，始终为0。
2. 时间戳：占用41位，精确到毫秒，总共可以容纳约69年的时间。
3. 工作机器id：占用10位，前 5 位表示机房 ID，后 5 位表示机器 ID，最多可以容纳1024个节点。
4. 序列号：一共 12 位，用来表示序列号。 序列号为自增值，代表单台机器每毫秒能够产生的最大 ID 数(2^12 = 4096),也就是说单台机器每毫秒最多可以生成 4096 个 唯一 ID。

雪花算法的QPS理论上约为409.6w/s。每个节点每毫秒从0开始不断累加，最多可以累加到4095，一共可以产生4096个ID。如果在同一毫秒内，单个节点的请求量超过了4096，那么雪花算法将无法生成更多的ID，直到下一个毫秒才能继续生成新的ID。

核心代码如下：

//注意这里加了synchronized关键字
protected synchronized long nextId() {
    //获取当前毫秒
    long timestamp = timeGen();
    
//如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
      if (timestamp < lastTimestamp) {
           throw new RuntimeException(
               String.format("Clock moved backwards"));
        }
 //同一毫秒，有两个线程先后进来
    if (lastTimestamp == timestamp) {
        // 当前毫秒内，则+1
        sequence = (sequence + 1) & sequenceMask;
        if (sequence == 0) {
            // 当前毫秒内计数满了，则等待下一秒
            //这里就是while循环拿当前毫秒，当前毫秒大于这个last就出来了
            timestamp = tilNextMillis(lastTimestamp);
        }
    } else {
        sequence = 0L;
    }
    lastTimestamp = timestamp;
    // ID偏移组合生成最终的ID，并返回ID
    // 就是组合64位
    long nextId = ((timestamp - twepoch) << timestampLeftShift)
            | (datacenterId << datacenterIdShift)
            | (workerId << workerIdShift) | sequence;

    return nextId;
}

「优缺点：」

优点：毫秒在高位，自增在底位，整个ID都是趋势递增的。不依赖第三方系统，分布式系统部署，稳定性高。可以根据自身业务分配组合bit位，灵活。

缺点：强依赖机器时钟，如果机器时钟回拨，会导致id重复。其他的那几位都是固定的只有这个时间戳和序列号是动态的，如果时间戳回到之前就会导致重复。

「美团解决雪花算法的时钟问题：」

首先在启动时，服务会进行检查：

1、新节点通过检查综合对比其余 Leaf 节点的系统时间来判断自身系统时间是否准确，具体做法是取所有运行中的 Leaf-snowflake 节点的服务 IP：Port，然后通过 RPC 请求得到所有节点的系统时间，计算 sum(time)/nodeSize，然后看本机时间与这个平均值是否在阈值之内来确定当前系统时间是否准确，准确正常启动服务，不准确认为本机系统时间发生大步长偏移，启动失败。

2、在 ZooKeeper 中登记过的老节点，同样会比较自身系统时间和 ZooKeeper 上本节点曾经的记录时间以及所有运行中的 Leaf-snowflake 节点的时间，不准确同样启动失败。

数据库生成

「mysql自动递增的id」

优点：非常简单，成本小，ID单调自增，存储空间小。

缺点：如果ID是自增的，会很容易的泄漏ID。支持的并发量不大、存在数据库单点问题。每次获取id都要读取一次数据库。

「Redis」

通过命令 incr来实现id的原子递增。

redis是基于内存的，速度快，但是如果出现redis故障，导致数据丢失，不管RDB还是AOD都有丢失数据的可能，那就意味着ID存在重复。

美团Leaf方案实现

世界上没有两片相同的树叶

「Leaf-segment数据库方案」：

这个有类似于JVM内存TLAB，JVM会提前为每个线程分配一块空间，这样线程就不用和其他的线程争抢内存。

说回来，上边说到了mysql每次生成id都需要访问一次数据库。那么我一次性多拿点，拿上个几千个id，用完了再回来拿，就可以大大减轻数据库的压力。

image-20230624102624144

biz_tag用来区分业务，max_id表示该biz_tag目前所被分配的ID号段的最大值，step表示每次分配的号段长度。

这种满足id递增，但是id不够随机，信息不安全，可以根据id算出来一天的订单量。并且强依赖数据库，如果数据库崩了，导致整个系统不可用(也不是立马不可用，会等系统取出来的值消耗完然后再去数据库取的时候系统崩了)。

TP999：表示在所有的请求中，有99.9%的请求的响应时间是在TP999以内的。举个例子，如果TP999是200毫秒，那么表示99.9%的请求在200毫秒内就能得到响应。"TP999数据波动大"意味着这个值在不同时间点可能会有较大的变化，这通常是由于系统负载、网络延迟等因素引起的。

这种设计还会导致TP999，只有用完的时候才会取id，导致波动。所以就有了双Buffer优化。

「双Buffer优化：」

双Buffer优化其实就是，不要在用完id的时候，再去数据库取id(我去突然想到一句歌词，不是因为寂寞才想你)，

当前号段已下发10%时，如果下一个号段未更新，则另启一个更新线程去更新下一个号段。当前号段全部下发完后，如果下个号段准备好了则切换到下个号段为当前segment接着下发，循环往复。通常号段的长度设置为高峰期QPS的600倍，这样当DB宕机，系统仍然能发号。

来看一个简易的实现。

static class LeafSegmentIdGenerator {
   //定义两个Buffer
   private SegmentIdBuffer buffer1 = new SegmentIdBuffer();
   private SegmentIdBuffer buffer2 = new SegmentIdBuffer();

   //当前使用的Buffer
   private volatile SegmentIdBuffer currentBuffer;

   //初始化方法
   public void init() {
      buffer1.load(leafAllocDao.updateMaxIdAndGetLeafAlloc(tag)); //预先加载号段
      currentBuffer = buffer1;
      buffer2.load(leafAllocDao.updateMaxIdAndGetLeafAlloc(tag)); //预先加载号段
   }

   public Long getId() {
      if (currentBuffer.canGetId()) { //如果当前Buffer还有ID可以使用
         return currentBuffer.getId();
      } else {
         //如果当前Buffer的ID已经用完，切换Buffer，并在另一线程中异步加载号段
         if (currentBuffer == buffer1) {
            currentBuffer = buffer2;
            new Thread(() -> buffer1.load(leafAllocDao.updateMaxIdAndGetLeafAlloc(tag))).start();
         } else {
            currentBuffer = buffer1;
            new Thread(() -> buffer2.load(leafAllocDao.updateMaxIdAndGetLeafAlloc(tag))).start();
         }
         return getId();
      }
   }
}

往期回顾

【15】TCP的三次握手和四次挥手，两次握手不行吗？

【14】Spring中Bean的实例化和初始化有什么区别？

【13】说一下SpringBoot自动装配流程

【12】详细聊一聊Synchronized关键字的实现原理