【算法】雪花算法生成分布式 ID

                                                      个人中心：SueWakeup

                                                      系列专栏：学习Java框架

                                                      个性签名：人生乏味啊，我欲令之光怪陆离

目录

1. 什么是分布式 ID

2. 分布式 ID 基本要求

3. 数据库主键自增

4. UUID

5. Snowflake 雪花算法

5.1 开源的雪花算法

注：手机端浏览本文章可能会出现 “目录”无法有效展示的情况，请谅解，点击侧栏目录进行跳转   

1. 什么是分布式 ID

在理解分布式 ID 之前请先阅读：【概念】神马是分布式？

分布式 ID 是指在分布式系统中，数据库的自增 ID 不能满足需求，需要在不同的节点之间通过一个唯一 ID 来进行标识。

个人理解：在分布式微服务项目中，多个线程同时对一张表新增数据，且这张表的主键 ID 存在唯一性 

2. 分布式 ID 基本要求

3. 数据库主键自增

通过关系型数据库的主键自增的方式，产生唯一的 ID

解决方案：

         在分布式系统中多部署几台及其，每台机器设置不同的初始值，且步长和机器数相等

如：两台机器，设置步长 step 为 2， TicketServer1 的初始值为 1（1，3，5，7，9...）、TicketServer2 的初始值为 2（2，4，6，8，10...）

4. UUID

Universally Unique Identifier（通用唯一标识符）的缩写

UUID 包含 32 个 16 进制数字（8-4-4-4-12）

生成规则：包括 MAC 地址、时间戳、命名空间（Namespace）、随机或伪随机数、时序等元素，基于这些规则生成的 UUID 不会重复

UUID.randomUUID();

5. Snowflake 雪花算法

Snowflake 产生的 ID 由 64位 二进制数字组成，被拆分成 4 个部分：

• 符号位：标识正负，始终为0
• 时间戳：单位 ms（毫秒），可以支持 2^41 毫秒（约 69 年）
• 工作时间 ID：一般前 5 位表示机房 ID，后 5 位表示机器ID，用于区分不同集群/机房的节点，10 位的长度，可以表示 1024 个不同节点。
• 序列号：序列号为自增值，代表单台机器每毫秒能够产生的最大 ID 数，也就是说单台机器每毫秒最多可以生成 4096 个唯一ID，最大支持 400W 左右的并发量。

5.1 开源的雪花算法

public class SnowFlake {// 机房（数据中心）IDprivate long datacenterId;// 机器 IDprivate long workerId;// 同一时间的序列号private long sequence;// 开始时间戳private long twepoch = 1634393012000L;  // 时间起点，这里设置为"2021-10-17 00:00:00"// 机房ID所占的位数：5个 bitprivate long datacenterIdBits = 5L;// 机器ID所占的位数：5个 bitprivate long workerIdBits = 5L;// 最大机器ID：5 bit 最多只能有31个数字，就是说机器id最多只能是32以内// 最大：11111（2进制） --> 31（10进制）private long maxWorkerId = -1L ^ (-1L << workerIdBits);  // 最大机器ID值// 最大数据中心ID：5 bit 最多只能有31个数字，就是说数据中心id最多只能是32以内private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);  // 最大数据中心ID值// 同一毫秒内的序列号位数：12 bitprivate long sequenceBits = 12L;// workerId左移位数：12private long workerIdShift = sequenceBits;// datacenterId左移位数：12+5private long datacenterIdShift = sequenceBits + workerIdBits;// timestamp左移位数：12+5+5private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;// 序列号掩码：4095 (0b111111111111=0xfff=4095)private long sequenceMask = -1L ^ (-1L << sequenceBits);// 上次时间戳private long lastTimestamp = -1L;// 构造函数，传入workerId和datacenterIdpublic SnowFlake(long workerId, long datacenterId) {this(workerId, datacenterId, 0);}// 构造函数，传入workerId、datacenterId和sequencepublic SnowFlake(long workerId, long datacenterId, long sequence) {// 参数校验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));}// 输出信息System.out.printf("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);// 初始化参数this.workerId = workerId;this.datacenterId = datacenterId;this.sequence = sequence;}// 生成下一个IDpublic synchronized long nextId() {// 获取当前时间戳long timestamp = timeGen();// 检查时间回拨if (timestamp < lastTimestamp) {System.err.printf("clock is moving backwards.  Rejecting requests until %d.", 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;if (sequence == 0) {// 如果同一毫秒内的序列号超出范围，等待下一毫秒timestamp = tilNextMillis(lastTimestamp);}} else {// 不同毫秒内，序列号重置为0sequence = 0;}// 更新上次时间戳lastTimestamp = timestamp;// 生成IDreturn ((timestamp - twepoch) << timestampLeftShift) |(datacenterId << datacenterIdShift) |(workerId << workerIdShift) |sequence;}// 等待下一毫秒private long tilNextMillis(long lastTimestamp) {long timestamp = timeGen();while (timestamp <= lastTimestamp) {timestamp = timeGen();}return timestamp;}// 获取当前时间戳private long timeGen() {return System.currentTimeMillis();}// 主函数，测试生成IDpublic static void main(String[] args) {SnowFlake worker = new SnowFlake(1, 1);for (int i = 0; i < 100; i++) {System.out.println(worker.nextId());}System.out.println();worker = new SnowFlake(1, 2);for (int i = 0; i < 100; i++) {System.out.println(worker.nextId());}}}

测试用例

  SnowFlake flake1 = new SnowFlake(1, 12);SnowFlake flake2 = new SnowFlake(1, 12);Thread t1 = new Thread(){@Overridepublic void run() {for(int i=0;i<10;i++){System.out.println("t1-"+flake1.nextId());}}};Thread t2 =new Thread(){@Overridepublic void run(){for(int i=0;i<10;i++){System.out.println("t2-"+flake2.nextId());}}};t1.start();t2.start();try {t1.join();t2.join();} catch (InterruptedException e) {e.printStackTrace();}