6 种常见分布式唯一ID生成策略及它们的优缺点对比
Java之间
共 13030字，需浏览 27分钟
·
2021-04-20 17:45
往期热门文章：
1、面试被问事务注解 @Transactional 失效怎么解决？ 2、CTO 说了，用错 @Autowired 和 @Resource 的人可以领盒饭了 3、在项目中用了Arrays.asList、ArrayList的subList，被公开批评 4、这六个 MySQL 死锁案例，能让你理解死锁的原因！ 5、别总写代码，这130个网站比涨工资都重要
来源：blog.csdn.net/u010398771/article/details/79765836
简单分析一下需求
常见生成策略的优缺点对比
方法一: 用数据库的 auto_increment 来生成
方法二：单点批量ID生成服务
方法三：uuid / guid
方法四：取当前毫秒数
方法五：使用 Redis 来生成 id
方法六：Twitter 开源的 Snowflake 算法
简单分析一下需求
全局唯一 趋势有序
常见生成策略的优缺点对比
方法一: 用数据库的 auto_increment 来生成
此方法使用数据库原有的功能，所以相对简单 能够保证唯一性 能够保证递增性 id 之间的步长是固定且可自定义的
可用性难以保证：数据库常见架构是 一主多从 + 读写分离，生成自增ID是写请求 主库挂了就玩不转了 扩展性差，性能有上限：因为写入是单点，数据库主库的写性能决定ID的生成性能上限，并且 难以扩展
冗余主库，避免写入单点 数据水平切分，保证各主库生成的ID不重复
丧失了ID生成的“绝对递增性”：先访问DB 01生成0,3，再访问DB 02生成1，可能导致在非常短的时间内，ID生成不是绝对递增的（这个问题不大，目标是趋势递增，不是绝对递增 数据库的写压力依然很大，每次生成ID都要访问数据库
方法二：单点批量ID生成服务
保证了ID生成的绝对递增有序 大大的降低了数据库的压力，ID生成可以做到每秒生成几万几十万个
服务仍然是单点 如果服务挂了，服务重启起来之后，继续生成ID可能会不连续，中间出现空洞（服务内存是保存着0,1,2,3,4，数据库中max-id是4，分配到3时，服务重启了，下次会从5开始分配，3和4就成了空洞，不过这个问题也不大） 虽然每秒可以生成几万几十万个ID，但毕竟还是有性能上限，无法进行水平扩展
单点服务的常用高可用优化方案是“备用服务”，也叫“影子服务”，所以我们能用以下方法优化上述缺点：
方法三：uuid / guid
UUID uuid = UUID.randomUUID();
本地生成ID，不需要进行远程调用，时延低 扩展性好，基本可以认为没有性能上限
无法保证趋势递增 uuid过长，往往用字符串表示，作为主键建立索引查询效率低，常见优化方案为“转化为两个uint64整数存储”或者“折半存储”（折半后不能保证唯一性）
方法四：取当前毫秒数
本地生成ID，不需要进行远程调用，时延低 生成的ID趋势递增 生成的ID是整数，建立索引后查询效率高
如果并发量超过1000，会生成重复的ID 这个缺点要了命了，不能保证ID的唯一性。当然，使用微秒可以降低冲突概率，但每秒最多只能生成1000000个ID，再多的话就一定会冲突了，所以使用微秒并不从根本上解决问题。
方法五：使用 Redis 来生成 id
依赖于数据库，灵活方便，且性能优于数据库。 数字ID天然排序，对分页或者需要排序的结果很有帮助。
如果系统中没有Redis，还需要引入新的组件，增加系统复杂度。 需要编码和配置的工作量比较大。
方法六：Twitter 开源的 Snowflake 算法
41 bit 作为毫秒数 - 41位的长度可以使用69年 10 bit 作为机器编号 （5个bit是数据中心，5个bit的机器ID） - 10位的长度最多支持部署1024个节点 12 bit 作为毫秒内序列号 - 12位的计数顺序号支持每个节点每毫秒产生4096个ID序号
package com;
public class SnowflakeIdGenerator {
//================================================Algorithm's Parameter=============================================
// 系统开始时间截 (UTC 2017-06-28 00:00:00)
private final long startTime = 1498608000000L;
// 机器id所占的位数
private final long workerIdBits = 5L;
// 数据标识id所占的位数
private final long dataCenterIdBits = 5L;
// 支持的最大机器id(十进制)，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数)
// -1L 左移 5位 (worker id 所占位数) 即 5位二进制所能获得的最大十进制数 - 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 (即末 sequence 所占用的位数)
private final long workerIdMoveBits = sequenceBits;
// 数据标识id 左移位数 - 17(12+5)
private final long dataCenterIdMoveBits = sequenceBits + workerIdBits;
// 时间截向 左移位数 - 22(5+5+12)
private final long timestampMoveBits = sequenceBits + workerIdBits + dataCenterIdBits;
// 生成序列的掩码(12位所对应的最大整数值)，这里为4095 (0b111111111111=0xfff=4095)
private final long sequenceMask = -1L ^ (-1L << sequenceBits);
//=================================================Works's Parameter================================================
/**
* 工作机器ID(0~31)
*/
private long workerId;
/**
* 数据中心ID(0~31)
*/
private long dataCenterId;
/**
* 毫秒内序列(0~4095)
*/
private long sequence = 0L;
/**
* 上次生成ID的时间截
*/
private long lastTimestamp = -1L;
//===============================================Constructors=======================================================
/**
* 构造函数
*
* @param workerId 工作ID (0~31)
* @param dataCenterId 数据中心ID (0~31)
*/
public SnowflakeIdGenerator(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 的方法
public synchronized long nextId() {
long timestamp = currentTime();
//如果当前时间小于上一次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;
//毫秒内序列溢出 即 序列 > 4095
if (sequence == 0) {
//阻塞到下一个毫秒,获得新的时间戳
timestamp = blockTillNextMillis(lastTimestamp);
}
}
//时间戳改变，毫秒内序列重置
else {
sequence = 0L;
}
//上次生成ID的时间截
lastTimestamp = timestamp;
//移位并通过或运算拼到一起组成64位的ID
return ((timestamp - startTime) << timestampMoveBits) //
| (dataCenterId << dataCenterIdMoveBits) //
| (workerId << workerIdMoveBits) //
| sequence;
}
// 阻塞到下一个毫秒 即 直到获得新的时间戳
protected long blockTillNextMillis(long lastTimestamp) {
long timestamp = currentTime();
while (timestamp <= lastTimestamp) {
timestamp = currentTime();
}
return timestamp;
}
// 获得以毫秒为单位的当前时间
protected long currentTime() {
return System.currentTimeMillis();
}
//====================================================Test Case=====================================================
public static void main(String[] args) {
SnowflakeIdGenerator idWorker = new SnowflakeIdGenerator(0, 0);
for (int i = 0; i < 100; i++) {
long id = idWorker.nextId();
//System.out.println(Long.toBinaryString(id));
System.out.println(id);
}
}
}
最近热文阅读：
1、终于来了，IDEA 2021.1版本正式发布，完美支持WSL 2 2、面试被问事务注解 @Transactional 失效怎么解决？ 3、CTO 说了，用错 @Autowired 和 @Resource 的人可以领盒饭了 4、在项目中用了Arrays.asList、ArrayList的subList，被公开批评 5、别总写代码，这130个网站比涨工资都重要 6、哇！IntelliJ IDEA 2021.1 中竟然有这么多牛逼的插件~ 7、能挣钱的，开源 SpringBoot 商城系统，功能超全，超漂亮，真TMD香！ 8、放弃 Notepad++，事实证明，还有 5 款更牛逼…… 9、公司这套架构统一处理 try...catch 这么香，求求你不要再满屏写了，再发现扣绩效！ 10、Spring 中经典的 9 种设计模式！收藏了 关注公众号，你想要的Java都在这里
评论