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

SueWakeup

                                                      个人中心：SueWakeup

                                                      系列专栏：学习Java框架

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

本文封面由 凯楠📷 友情赞助播出!

目录

1. 什么是分布式 ID

2. 分布式 ID 基本要求

3. 数据库主键自增

4. UUID

5. Snowflake 雪花算法

5.1 开源的雪花算法

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

---

1. 什么是分布式 ID

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

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

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

---

2. 分布式 ID 基本要求

基本要求	描述
全局唯一	在整个分布式系统中全局唯一，不能出现重复 ID
高性能高可用	分布式 ID 的生成速度要快，生成分布式 ID 的服务要保证可用性无限接近于 100%
趋势递增	在 MySQL InnoDB 引擎中使用的是聚焦索引，由于多数 RDBMS 使用 B-tree 的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能
单调递增	保证下一个 ID 一定大于上一个 ID
具体的业务含义	生成的 ID 拥有具体的业务含义，可以让定位问题以及开发更透明化
独立部署	在分布式系统单独有一个发号器服务，专门用来生成分布式 ID，生成的 ID 的服务和业务相关的服务解耦，但会带来服务之间网络调用消耗增加
信息安全	ID 中不能包含敏感信息，如果 ID 是连续的，恶意用户的扒取工作就非常容易做，订单号就更危险了，竞争对手可以获取到我们一天的订单信息，所以一些应用场景下，ID 需要呈现无规则状态

---

3. 数据库主键自增

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

优点	缺点
实现简单、ID 有序递增、存储空间消耗小	单击模式下并发量不大，性能瓶颈限制在单台 MySQL 的读写性能 数据库服务器不可用时，整个系统瘫痪 ID 没有具体业务含义 安全问题 每次获取 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();

优点	缺点
性能非常高，本地生成，没有网络消耗	不易于存储：16 字节 128 位，通常以长度为 36 的字符串表示，很多场景不适用 信息不安全：基于 MAC 地址生成 UUID 的算法可能会造成 MAC 地址泄露 不满足 MySQL 主键要求：MySQL 官方有明确的建议主键要尽量越短越好 对 MySQL 索引不利：作为数据库主键，在 InnoDB 引擎下，UUID 的无序性可能会引起数据位置频繁变动，影响性能

---

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();}