分布式ID生成之雪花算法详解
分布式ID生成之雪花算法
分布式ID生成方案
唯一ID可以标识数据的唯一性，在分布式系统中生成唯一ID的方案有很多，常见的方式大概有以下几种方式：
UUID 随机数
数据库特性
Redis 生成 ID
snowflake 雪花算法
关于雪花算法
有这样一种说法，自然界中并不存在两片完全一样的雪花(世界上没有两片相同的树叶)，每一片雪花都拥有自己漂亮独特的形状且是独一无二。
雪花算法也表示生成的 ID 如雪花般独一无二，SnowFlake 算法，是 Twitter 开源的分布式 ID 生成算法。
雪花算法概述
雪花算法生成的 ID 是纯数字且具有时间顺序的。其原始版本是 scala 版，后面出现了许多其他语言的版本如Java、C++等。
组成结构
雪花算法-组成结构
大致是由：首位无效符、时间戳差值，机器(进程)编码，序列号四部分组成。
1 bit：首位无效，为啥呢？
因为二进制里第一个 bit 为如果是 1，那么都是负数，但是我们生成的 id 都是正数，所以第一个 bit 统一都是 0。
41 bit：表示的是时间戳，单位是毫秒
41 bit 可以表示的数字多达 2^41 - 1，也就是可以标识 2 ^ 41 - 1 个毫秒值，换算成年就是表示 69 年的时间。
10 bit：记录工作机器 id，代表的是这个服务最多可以部署在 2^10 台机器上，也就是 1024 台机器
10 bit 里 5 个 bit 代表机房 id，5 个 bit 代表机器 id。意思就是最多代表 2 ^ 5 个机房（32 个机房），每个机房里可以代表 2 ^ 5 个机器（32 台机器），也可以根据自己公司的实际情况确定。
12 bit：这个是用来记录同一个毫秒内产生的不同 id
12 bit 可以代表的最大正整数是 2 ^ 12 - 1 = 4096，也就是说可以用这个 12 bit 代表的数字来区分同一个毫秒内的 4096 个不同的 id。
雪花算法优点
自增、有序、适合分布式场景，生成时不依赖于数据库，完全在内存中生成，每秒能生成数百万的自增 ID，存入数据库中，索引效率高。
时间位：可以根据时间进行排序，有助于提高查询速度。
机器 ID 位：适用于分布式环境下对多节点的各个节点进行标识，可以具体根据节点数和部署情况设计划分机器位 10 位长度，如划分5位表示进程位等。
序列号位：是一系列的自增id，可以支持同一节点同一毫秒生成多个 ID 序号，12 位的计数序列号支持每个节点每毫秒产生 4096 个 ID 序号
snowflake 算法可以根据项目情况以及自身需要进行一定的修改。
基于 Snowflake 算法的其他开源方案 百度 uid-generator 、滴滴 Tinyid 、美团leaf
Java实现雪花雪花系统
使用Java语言实现雪花算法的ID生成器，可以参考以下代码。这个实现同样遵循了雪花算法的基本结构，包括1位符号位、41位时间戳、10位机器标识（5位数据中心ID和5位工作机器ID）以及12位序列号。我们将这些位数放在了配置文件中，家人们可以根据实际情况进行调整。在这个代码中，我们提供了单id生成接口和批量id生成接口。代码如下：
配置信息 application.yml
server:
port: 8000
snowflake:
#数据中心id位数
datacenterBits: 5
# 机器id位数
workerBits: 5
# 序列id所占位数
sequenceBits: 12
# 数据中心id,范围0-2^5-1
datacenterId: 1
# 机器id,范围0-2^5-1
workerId: 1
# 时间戳起始点（2024-01-01 00::00:00 的毫秒数）
twepoch: 1704038400000
#单次批量生成id的最大数量 默认10万
maxBatchCount: 100000
SnowflakeProperties
import lombok.Data;
import org.springframework.boot.context.properties.ConfigurationProperties;
import org.springframework.stereotype.Component;
@Component
@ConfigurationProperties(prefix ="snowflake")
@Data
public class SnowflakeProperties {
//数据中心id
private Long datacenterId;
//数据中心id位数
private Long datacenterBits;
//机器id
private Long workerId;
//机器id位数
private Long workerBits;
//序列id所占位数
private Long sequenceBits;
// 时间戳起始点（毫秒）
private Long twepoch;
//单次批量生成id的最大数量
private Integer maxBatchCount;
}
SnowflakeIdGenerator
package cn.xj.snowflake.generator;
import cn.xj.snowflake.config.SnowflakeProperties;
import org.springframework.stereotype.Component;
import java.util.ArrayList;
import java.util.List;
@Component
public class SnowflakeIdGenerator {
//数据中心id
private final long datacenterId;
//数据中心id位数
private final long datacenterBits;
//机器id
private final long workerId;
//机器id位数
private final long workerBits;
//序列id所占位数
private final long sequenceBits;
// 时间戳起始点（毫秒）
private final long twepoch;
//数据中心最大id
private final long maxDatacenterId;
//机器最大id
private final long maxWorkerId;
//最大序列号
private final long maxSequence;
//机器id左移位数
private final long workerIdShift;
//数据中心id左移位数
private final long datacenterIdShift;
//毫秒数左移位数
private final long timestampLeftShift;
//单次批量生成id的最大数量
private final int maxBatchCount;
// 序列号
private long sequence = 0L;
// 上一次时间戳
private long lastTimestamp = -1L;
public SnowflakeIdGenerator(SnowflakeProperties properties) {
//数据中心id
this.datacenterId = properties.getDatacenterId();
//数据中心id位数
this.datacenterBits = properties.getDatacenterBits();
//机器id
this.workerId = properties.getWorkerId();
//机器id位数
this.workerBits = properties.getWorkerBits();
//序列id所占位数
this.sequenceBits = properties.getSequenceBits();
// 时间戳起始点（毫秒）
this.twepoch = properties.getTwepoch();
//数据中心最大id
this.maxDatacenterId = -1L ^ (-1L << properties.getDatacenterBits());
//机器最大id
this.maxWorkerId = -1L ^ (-1L << properties.getWorkerBits());
//最大序列号
this.maxSequence = -1L ^ (-1L << properties.getSequenceBits());
this.workerIdShift = properties.getSequenceBits();
//数据中心id左移位数
this.datacenterIdShift = properties.getSequenceBits() + properties.getWorkerBits();
//毫秒数左移位数
this.timestampLeftShift = properties.getSequenceBits() + properties.getWorkerBits() + properties.getSequenceBits();
//单次批量生成id的最大数量
this.maxBatchCount = properties.getMaxBatchCount();
// 校验datacenterId和workerId是否超出最大值
if (datacenterId > maxDatacenterId || datacenterId < 0) {
throw new IllegalArgumentException(String.format("数据中心Id不能大于%d或小于0", maxDatacenterId));
}
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("机器Id不能大于%d或小于0", maxWorkerId));
}
}
/**
* id生成方法(单个)
* @return
*/
public synchronized long nextId() {
//获取当前时间的毫秒数
long timestamp = currentTime();
//判断时钟是否回拨
if (timestamp < lastTimestamp) {
throw new RuntimeException(String.format("时钟回拨，回拨毫秒数：%d", lastTimestamp - timestamp));
}
//设置序列号
if (lastTimestamp == timestamp) {
//设置序列号递增，如果当前毫秒内序列号已经达到最大值，则直到下一毫秒在重新从0开始计算序列号
sequence = (sequence + 1) & maxSequence;
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0L;
}
lastTimestamp = timestamp;
//计算id
return ((timestamp - twepoch) << timestampLeftShift) |
(datacenterId << datacenterIdShift) |
(workerId << workerIdShift) |
sequence;
}
/**
* id生成方法(批量)
* @return
*/
public synchronized List<Long> nextIds(int count) {
if (count > maxBatchCount || count < 0) {
throw new IllegalArgumentException(String.format("批量生成id的数量不能大于%d或小于0", maxBatchCount));
}
List<Long> ids = new ArrayList<>(count);
for (int i = 0; i < count; i++) {
ids.add(nextId());
}
return ids;
}
/**
* 循环等待直至获取到新的毫秒时间戳
* 确保生成的时间戳总是向前移动的，即使在相同的毫秒内请求多个ID时也能保持唯一性。
*/
private long tilNextMillis(long lastTimestamp) {
long timestamp = currentTime();
// 循环等待直至获取到新的毫秒时间戳
while (timestamp <= lastTimestamp) {
timestamp = currentTime();
}
return timestamp;
}
/**
* 获取当前时间的毫秒数
*/
private long currentTime() {
return System.currentTimeMillis();
}
}
这个Java类SnowflakeIdWorker封装了雪花算法的核心逻辑。它允许通过构造函数指定数据中心ID和机器ID，并提供了nextId()和nextIds()方法用于生成唯一的ID。该方法通过同步关键字synchronized保证了线程安全。
SnowflakeApi
import cn.xj.snowflake.generator.SnowflakeIdGenerator;
import jakarta.annotation.Resource;
import org.springframework.web.bind.annotation.PostMapping;
import org.springframework.web.bind.annotation.RequestBody;
import org.springframework.web.bind.annotation.RestController;
import java.util.List;
@RestController
public class SnowflakeApi {
@Resource
private SnowflakeIdGenerator snowflakeIdGenerator;
@PostMapping("/snowflake/api/nextId")
public Long nextId(){
return snowflakeIdGenerator.nextId();
}
@PostMapping("/snowflake/api/nextIds")
public List<Long> nextIds(@RequestBody int count){
return snowflakeIdGenerator.nextIds(count);
}
}
接口调用详情
单个id生成接口nextId:
批量id生成接口nextIds:我们此处生成了10万条id,响应时长不到1s
雪花算法的开源代码或者优秀代码示例有很多，但思想基本是一样的。
雪花算法的缺点
雪花算法在单机系统上 ID 是递增的，但强依赖与系统时间的一致性，如果系统时间被回拨或者改变，可能会造成 ID 冲突或者重复。在分布式系统多节点的情况下，所有节点的时钟并不能保证不完全同步，所以有可能会出现不是全局递增的情况。
总结
分布式唯一 ID 的方案有很多，本文主要讨论了雪花算法，组成结构大致分为了无效位、时间位、机器位和序列号位。其特点是自增、有序、纯数字组成查询效率高且不依赖于数据库。
