本文介绍了分布式ID的几种实现方式，及其优缺点。最后结合源码介绍了美团开源的Leaf组件，展示了它的实现亮点。
以数据库为例，业务数据量不大时，单库单表完全够用，或者搞个主从同步、读写分离来提高性能。当业务迅速扩张，需要对数据库进行分库分表时，ID生成就不能简单依靠数据库表主键自增了。因为这时需要保证数据库表ID全局唯一。
- 高性能、高可用： 生成ID速度快，接近于100%的可用，不会成为业务瓶颈；
- 趋势递增： 由于大多数数据库使用B-tree按索引有序存储数据，主键ID递增能保证新增记录时不会发生页分裂，保证写入性能；
- 信息安全： 如果ID连续或规则明显，恶意用户或竞争对手爬取信息就非常方便。因此一些场景比如订单，会要求ID不规则。
基于 Spring Boot + MyBatis Plus + Vue & Element 实现的后台管理系统 + 用户小程序，支持 RBAC 动态权限、多租户、数据权限、工作流、三方登录、支付、短信、商城等功能
- 项目地址：https://github.com/YunaiV/ruoyi-vue-pro
- 视频教程：https://doc.iocoder.cn/video/
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做表主键，在新增记录时页分裂更加频繁，严重影响写入性能。
用一个专门的表生成自增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;
缺点是依赖于数据库服务，存在单点故障，且性能瓶颈明显。
解决这个不足，通常有两种方式：一是使用数据库集群；二是采用号段模式。
还是以MySQL为例，我们可以搭建集群，提高可用性。给各个节点的auto_increment设置不同的起始值和自增步长。假设MySQL集群有3个节点，可以做下面的设置，这样每个节点都能生成唯一ID。
-- 对节点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;
号段模式下，一次请求将从数据库获取一批自增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};
利用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 < }
}
雪花算法（SnowFlake）是Twitter公司采用并开源的一种算法，能在分布式系统中产生全局唯一且趋势递增的ID。规则如下：
- 第一部分：占用1bit，其值始终是0，没有实际作用；
- 第二部分：时间戳，占用41bit，精确到毫秒，总共可以容纳约69年的时间；
- 第三部分：工作机器id，占用10bit；可以分配高位几个bit表示数据中心ID，剩余bit表示机器节点ID，最多可以容纳1024个节点；
- 第四部分：序列号，占用12bit，每个节点每毫秒从0开始累加，最大到4095。
理论上snowflake方案的QPS约为409.6w/s。网上有不少实现，不再赘述。
- 优点：生成的ID趋势递增；本地生成且不依赖第三方系统，性能极高。
- 缺点：强依赖于机器时钟，如果发生时钟回拨，将导致发号重复或服务不可用。
基于 Spring Cloud Alibaba + Gateway + Nacos + RocketMQ + Vue & Element 实现的后台管理系统 + 用户小程序，支持 RBAC 动态权限、多租户、数据权限、工作流、三方登录、支付、短信、商城等功能
- 项目地址：https://github.com/YunaiV/yudao-cloud
- 视频教程：https://doc.iocoder.cn/video/
Leaf是美团基础研发平台推出的一个分布式ID生成服务，具备高可靠、低延迟、全局唯一等特点，支持号段、雪花算法两种模式。感兴趣的小伙伴，可以访问官网了解更多信息。
https://github.com/Meituan-Dianping/Leaf
整体结构如图，强依赖于数据库，使用前先创建表。
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 cache = new ConcurrentHashMap();
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);
}
当获取ID的并发很高时，如果在当前号段用完时，才去数据库获取下一个号段，此时耗时将明显增加。为此，Leaf采用了双Buffer异步更新的策略，保证无论何时，都能有一个Buffer的号段可以正常对外提供服务。
假设服务QPS为Q，号段长度为L，号段更新周期为T，那么Q * T = L。如果L固定不变，QPS增长时，T会越来越小，即更新库表越来越频繁，且DB故障时缓存的号段能够支撑服务正常运行的时间更短了。
所以，Leaf每次更新号段的时候，会根据与上一次更新更新号段的间隔T和号段长度step，来决定这次的号段长度nextStep：
T < 15min，nextStep = step * 2，对应高QPS15min < T < 30min，nextStep = step，对应正常QPST > 30min，nextStep = step / 2，对应低QPS
总之，QPS越高，号段长度将变大；QPS越低，号段长度将变小。（有上下限限制）
美团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
现在，我们关注以下两个方面，并从源码中寻找答案：
当分布式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将出现重复。
启动时检查
在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，会返回负数。
