⭐⭐⭐ Spring Boot 项目实战	⭐⭐⭐ Spring Cloud 项目实战
《Dubbo 实现原理与源码解析 —— 精品合集》	《Netty 实现原理与源码解析 —— 精品合集》
《Spring 实现原理与源码解析 —— 精品合集》	《MyBatis 实现原理与源码解析 —— 精品合集》
《Spring MVC 实现原理与源码解析 —— 精品合集》	《数据库实体设计合集》
《Spring Boot 实现原理与源码解析 —— 精品合集》	《Java 面试题 + Java 学习指南》

摘要: 原创出处 juejin.cn/post/7324224387463823399 「侠客行0317」欢迎转载，保留摘要，谢谢！

🙂🙂🙂关注微信公众号：【芋道源码】有福利：

RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表

RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址

您对于源码的疑问每条留言都将得到认真回复。甚至不知道如何读源码也可以请教噢。

新的源码解析文章实时收到通知。每周更新一篇左右。

认真的源码交流微信群。

本文介绍了分布式ID的几种实现方式，及其优缺点。最后结合源码介绍了美团开源的Leaf组件，展示了它的实现亮点。

一、引入

1.1 为什么需要分布式ID

以数据库为例，业务数据量不大时，单库单表完全够用，或者搞个主从同步、读写分离来提高性能。当业务迅速扩张，需要对数据库进行分库分表时，ID生成就不能简单依靠数据库表主键自增了。因为这时需要保证数据库表ID全局唯一。

1.2 分布式ID需要满足的条件

全局唯一： 不能出现重复ID；
高性能、高可用： 生成ID速度快，接近于100%的可用，不会成为业务瓶颈；
趋势递增： 由于大多数数据库使用B-tree按索引有序存储数据，主键ID递增能保证新增记录时不会发生页分裂，保证写入性能；
信息安全： 如果ID连续或规则明显，恶意用户或竞争对手爬取信息就非常方便。因此一些场景比如订单，会要求ID不规则。

二、分布式ID的实现

2.1 UUID

UUID (Universally Unique IDentifier) 是一个128位数字的全球唯一标识，标准型式包含32个16进制数字，用连字号分为五段，形式为8-4-4-4-12。它生成时用到了网卡地址（即MAC address）、纳秒级时间等。

以Java语言为例，生成UUID使用java.util.UUID即可，使用非常简单。

import java.util.UUID;

public class UniqueId {
  public static void main(String[] args) {
    String uuid = UUID.randomUUID().toString();
    // 结果示例：2e55beed-6a65-47f8-b269-00b518d7da6a
    System.out.println(uuid);
    String uuid2 = uuid.replaceAll("-", "");
    // 结果示例：2e55beed6a6547f8b26900b518d7da6a
    System.out.println(uuid2);
  }
}

优点：

本地生成，性能非常高，使用简单

缺点：

太长不易存储：去掉连字号后的16进制有32字符，太长了，作为表主键应当越短越好；
信息不安全：可能会造成MAC地址泄漏；这个漏洞曾被用于寻找“梅丽莎病毒”的作者；
无序性：用UUID做表主键，在新增记录时页分裂更加频繁，严重影响写入性能。

2.2 数据库自增ID

用一个专门的表生成自增ID，提供给其他表使用。以MySQL为例，创建下面的这张表，当需要一个ID时，向表中插入一条记录返回主键id即可。

CREATE TABLE generate_id {
 id BIGINT(20) UNSIGNED NOT NULL AUTO_INCREMENT,
 content CHAR(1) NOT NULL DEFAULT '' COMMENT '无实际意义',
 PRIMARY KEY (id),
} ENGINE=INNODB;

缺点是依赖于数据库服务，存在单点故障，且性能瓶颈明显。

解决这个不足，通常有两种方式：一是使用数据库集群；二是采用号段模式。

2.2.1 数据库集群

还是以MySQL为例，我们可以搭建集群，提高可用性。给各个节点的auto_increment设置不同的起始值和自增步长。假设MySQL集群有3个节点，可以做下面的设置，这样每个节点都能生成唯一ID。

节点1生成的ID：1、4、7、10……
节点2生成的ID：2、5、8、11……
节点3生成的ID：3、6、9、12……

-- 对节点1
SET @auto_increment_offset = 1; -- 起始值
SET @auto_increment_increment =3; -- 步长

-- 对节点2
SET @auto_increment_offset = 2;
SET @auto_increment_increment =3;

-- 对节点3
SET @auto_increment_offset = 3;
SET @auto_increment_increment =3;

2.2.2 号段模式

号段模式下，一次请求将从数据库获取一批自增ID，减小访库次数，降低数据库读写压力。

CREATE TABLE `segment_id` (
  `biz_tag` VARCHAR(32) NOT NULL DEFAULT '' COMMENT '业务类型',
  `max_id` BIGINT(20) NOT NULL DEFAULT '1' COMMENT '当前最大id',
  `step` INT(11) NOT NULL COMMENT '号段步长',
  `version` INT(20) NOT NULL COMMENT '版本号',
  `update_time` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
  PRIMARY KEY (`biz_tag`)
) ENGINE=INNODB DEFAULT CHARSET=utf8;

比如使用下面的SQL，当需要ID时，先发起查询，然后更新max_id，更新成功则表示获取到新号段[max_id, max_id+step)。

UPDATE segment_id SET max_id=max_id+step, VERSION = VERSION + 1 WHERE VERSION = #{version} and biz_tag = #{biz_tag};

2.3 基于Redis生成唯一ID

利用Redis的 incr命令，实现ID的原子性自增。需注意Redis持久化对可靠性的影响。

RDB持久化方式：定时保存当前数据快照，假如ID自增但Redis没及时持久化就挂掉了，重启Redis后会出现ID重复；
AOF持久化方式：会对每条写命令进行持久化，即使Redis挂掉了也不会出现ID重复的情况，但是Redis重启恢复数据时间较长。

下面是一个简单实现。

import org.springframework.data.redis.core.StringRedisTemplate;

public class RedisIdWorker {
  private StringRedisTemplate stringRedisTemplate;

  public RedisIdWorker(StringRedisTemplate stringRedisTemplate) {
    this.stringRedisTemplate = stringRedisTemplate;
  }

  public long nextId(String bizTag) {
    return stringRedisTemplate.opsForValue().increment("id:" + bizTag);
  }
}

此外，我们还可以给ID加上毫秒级时间戳前缀，即使使用RDB持久化，Redis故障时也不会出现ID重复。下面是不考虑时钟回拨时的一个实现。

import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.stereotype.Component;

import java.time.LocalDateTime;
import java.time.ZoneOffset;
import java.time.format.DateTimeFormatter;

public class RedisIdWorker {
  // 开始时间戳
  private static final long BEGIN_TIMESTAMP = 1705221450434L;
  // id位数
  private static final int COUNT_BITS = 24;

  private StringRedisTemplate stringRedisTemplate;

  public RedisIdWorker(StringRedisTemplate stringRedisTemplate) {
    this.stringRedisTemplate = stringRedisTemplate;
  }

  public long nextId(String bizTag) {
    // 生成时间戳
    LocalDateTime now = LocalDateTime.now();
    long nowSecond = now.toEpochSecond(ZoneOffset.UTC);
    long timestamp = nowSecond - BEGIN_TIMESTAMP;

    // 2.2.自增长
    long count = stringRedisTemplate.opsForValue().increment("id:" + bizTag);
    return timestamp << COUNT_BITS | count;
  }
}

2.4 雪花算法

雪花算法（SnowFlake）是Twitter公司采用并开源的一种算法，能在分布式系统中产生全局唯一且趋势递增的ID。规则如下：

第一部分：占用1bit，其值始终是0，没有实际作用；
第二部分：时间戳，占用41bit，精确到毫秒，总共可以容纳约69年的时间；
第三部分：工作机器id，占用10bit；可以分配高位几个bit表示数据中心ID，剩余bit表示机器节点ID，最多可以容纳1024个节点；
第四部分：序列号，占用12bit，每个节点每毫秒从0开始累加，最大到4095。

理论上snowflake方案的QPS约为409.6w/s。网上有不少实现，不再赘述。

优点：生成的ID趋势递增；本地生成且不依赖第三方系统，性能极高。
缺点：强依赖于机器时钟，如果发生时钟回拨，将导致发号重复或服务不可用。

三、开源组件——美团Leaf

Leaf是美团基础研发平台推出的一个分布式ID生成服务，具备高可靠、低延迟、全局唯一等特点，支持号段、雪花算法两种模式。感兴趣的小伙伴，可以访问官网了解更多信息。

https://github.com/Meituan-Dianping/Leaf

3.1 号段模式

整体结构如图，强依赖于数据库，使用前先创建表。

CREATE DATABASE leaf;
CREATE TABLE `leaf_alloc` (
  `biz_tag` varchar(128)  NOT NULL DEFAULT '', -- 区分业务，如订单、商品等
  `max_id` bigint(20) NOT NULL DEFAULT '1', -- 号段的起始值
  `step` int(11) NOT NULL, -- 步长
  `description` varchar(256)  DEFAULT NULL,
  `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
  PRIMARY KEY (`biz_tag`)
) ENGINE=InnoDB;

核心接口com.sankuai.inf.leaf.IDGen有三个实现，号段模式实现是SegmentIDGenImpl，有两大特点：

 // key是biz_tag
 private Map<String, SegmentBuffer> cache = new ConcurrentHashMap<String, SegmentBuffer>();

 public boolean init() {
  logger.info("Init ...");
  // 首次加载所有biz_tag记录，并更新缓存
  updateCacheFromDb();
  initOK = true;
  // 启动定时任务，每分钟更新缓存
  updateCacheFromDbAtEveryMinute();
  return initOK;
}

@Override
public Result get(final String key) {
  if (!initOK) {
    return new Result(EXCEPTION_ID_IDCACHE_INIT_FALSE, Status.EXCEPTION);
  }
  if (cache.containsKey(key)) {
    SegmentBuffer buffer = cache.get(key);
    // 双重检查
    if (!buffer.isInitOk()) {
      synchronized (buffer) {
        if (!buffer.isInitOk()) {
          try {
            // 当前线程亲自加载第一个Segment
            updateSegmentFromDb(key, buffer.getCurrent());
            logger.info("Init buffer. Update leafkey {} {} from db", key, buffer.getCurrent());
            buffer.setInitOk(true);
          } catch (Exception e) {
            logger.warn("Init buffer {} exception", buffer.getCurrent(), e);
          }
        }
      }
    }
    // 获取ID
    return getIdFromSegmentBuffer(cache.get(key));
  }
  return new Result(EXCEPTION_ID_KEY_NOT_EXISTS, Status.EXCEPTION);
}

3.1.1 双buffer

当获取ID的并发很高时，如果在当前号段用完时，才去数据库获取下一个号段，此时耗时将明显增加。为此，Leaf采用了双Buffer异步更新的策略，保证无论何时，都能有一个Buffer的号段可以正常对外提供服务。

3.1.2 动态调整Step

假设服务QPS为Q，号段长度为L，号段更新周期为T，那么Q * T = L。如果L固定不变，QPS增长时，T会越来越小，即更新库表越来越频繁，且DB故障时缓存的号段能够支撑服务正常运行的时间更短了。

所以，Leaf每次更新号段的时候，会根据与上一次更新更新号段的间隔T和号段长度step，来决定这次的号段长度nextStep：

T < 15min，nextStep = step * 2，对应高QPS
15min < T < 30min，nextStep = step，对应正常QPS
T > 30min，nextStep = step / 2，对应低QPS

总之，QPS越高，号段长度将变大；QPS越低，号段长度将变小。（有上下限限制）

3.2 雪花算法

美团Leaf的雪花算法，ID构成与前面提到的一致，机器号占10个bit。使用时需要的配置如下：

leaf.name=unique-id
leaf.snowflake.enable=true
leaf.snowflake.zk.address=192.168.43.105:2181
# 不是服务端口或zk端口，是Leaf在zk上注册时的端口
leaf.snowflake.port=8870

现在，我们关注以下两个方面，并从源码中寻找答案：

如何高效分配workId？
如何解决时钟回拨导致ID重复？

3.2.1 workId分配

当分布式ID服务集群节点数量较小时，完全可以手动配置workId。Leaf中使用ZooKeeper发号。代码实现是com.sankuai.inf.leaf.snowflake.SnowflakeIDGenImpl。

// SnowflakeZookeeperHolder中
public boolean init() {
  try {
    CuratorFramework curator = createWithOptions(connectionString, new RetryUntilElapsed(1000, 4), 10000, 6000);
    curator.start();
    Stat stat = curator.checkExists().forPath(PATH_FOREVER);
    if (stat == null) {
      //不存在根节点,机器第一次启动,创建/snowflake/ip:port-000000000,并上传数据
      zk_AddressNode = createNode(curator);
      // 将workerID保存到本地文件
      updateLocalWorkerID(workerID);
      //定时上报本机时间给forever节点
      ScheduledUploadData(curator, zk_AddressNode);
      return true;
    } else {
      // ......省略
    } catch(Exception e){
      LOGGER.error("Start node ERROR {}", e);
      try {
        // 异常时（包括zooeeperk故障）从本地文件加载workId
        Properties properties = new Properties();
        properties.load(new FileInputStream(new File(PROP_PATH.replace("{port}", port + ""))));
        workerID = Integer.valueOf(properties.getProperty("workerID"));
        LOGGER.warn("START FAILED ,use local node file properties workerID-{}", workerID);
      } catch (Exception e1) {
        LOGGER.error("Read file error ", e1);
        return false;
      }
    }
    return true;
  }
}

可见，Leaf依靠zookeeper为各节点生成递增的workerId：

当Leaf节点首次启动时，连接zookeeper并在/snowflake/{leaf.name}/forever下创建永久有序节点，节点序号就是workId；key格式为ip:prot-序号，value格式如下;
不是首次启动时，连接zookeeper读取/snowflake/{leaf.name}/forever下所有节点，用ip:prot查找Leaf实例对应的key，从key中截取workId；
一旦获取到workId，将保存到本地文件中；当启动Leaf节点时zookeeper故障了，将会从本地文件读取workId。

{
  "ip" : "192.168.43.16",
  "port" : "8870",
  "timestamp" : 1705323905246
}

注意，所有Leaf实例，应该配置相同的leaf.name、leaf.snowflake.zk.address，否则Leaf集群中workId将出现重复。

3.2.2 应对时钟回拨

启动时检查

在Leaf实例启动后，会隔3秒更新zookeeper节点数据，上报当前服务器时间。该时间将被用于Leaf启动时，与机器本地时间进行比较。

假设Leaf节点宕机需要重启，此时将检查机器本地时间，是否小于zookeeper节点保存的时间戳；如果是则说明发生了时钟回拨，此时抛出异常、启动失败。

public boolean init() {
  // ......省略
  if (workerid != null) {
    //有自己的节点,zk_AddressNode=ip:port
    zk_AddressNode = PATH_FOREVER + "/" + realNode.get(listenAddress);
    workerID = workerid;
    // 比较本地时间与zk节点中的时间戳，如果本地时间更小，则抛出异常
    if (!checkInitTimeStamp(curator, zk_AddressNode)) {
      throw new CheckLastTimeException("init timestamp check error,forever node timestamp gt this node time");
    }
    // 启动定时任务，每隔3秒上报本地时间
    doService(curator);
    // 更新本地workerID文件
    updateLocalWorkerID(workerID);
    LOGGER.info("[Old NODE]find forever node have this endpoint ip-{} port-{} workid-{} childnode and start SUCCESS", ip, port, workerID);
  }
  // ......省略
}

此外，我们在官网（https://tech.meituan.com/2017/04/21/mt-leaf.html）上，看到了下面这张图。图中圈出的部分，在源码中并没有找到对应实现。猜测，开源版本和美团真正使用的版本间可能存在差异。

运行时检查

Leaf服务运行中，每生成一个id，会先比较当前时间与上一个id的timestamp；如果当前时间更小，说明发生了时钟回拨。回拨小于5毫秒时，则计时等待两倍的回拨时间；如果回拨超过5毫秒，则返回负数。

总结

虽然做了一些努力，但是Leaf并没有完全解决时钟回拨问题。我们看下面两个场景：

启动前，服务器时间进行了回拨；启动时连接Zookeeper失败，会使用本地文件中保存的workerId，此时跳过了时间检查将启动成功，可能会造成ID重复；

Leaf节点上报给zookeeper的时间戳是2024-01-16 08:15:00.000，最后一次生成的ID时间戳是2024-01-16 08:15:02.999，还没来得及再次上报zk本地时间，该节点宕机了。在启动之前，发生了时钟回拨，该节点重启时本地时间为2024-01-16 08:15:01.000；大于zookeeper中记录的时间戳，允许启动。但是，接下来两秒内生成的ID，都可能是之前已经生成过的。

Leaf运行中发现回拨超过5ms，会返回负数。

芋道源码 —— 纯源码解析博客

分布式ID，我用美团Leaf