前言
零碎惟一 ID 是咱们在设计一个零碎的时候经常会遇见的问题，也经常为这个问题而纠结。
这篇文章就是给各位看官提供一个生成分布式惟一全局 id 生成计划的思路，心愿能帮忙到大家。
不足之处，请多多指教！！
问题
为什么须要分布式全局惟一 ID 以及分布式 ID 的业务需要
在简单分布式系统中，往往须要对大量的数据和音讯进行惟一标识，如在美团点评的金融、领取、餐饮、酒店
猫眼电影等产品的零碎中数据逐步增长，对数据库分库分表后须要有一个惟一 ID 来标识一条数据或信息；
特地 Ian 的订单、骑手、优惠券都须要有惟一 ID 做标识
此时一个可能生成全局惟一 ID 的零碎是十分必要的
ID 生成规定局部硬性要求
- 全局惟一
- 趋势递增
- 在 MySQL 的 InnoDB 引擎中应用的是汇集索引，因为少数 RDBMS 应用 Btree 的数据结构来存储索引，在主键的抉择下面咱们应该尽量应用有序的主键保障写入性能
- 枯燥递增
- 保障下一个 ID 肯定大于上一个 ID，例如事务版本号、IM 增量音讯、排序等非凡需要
- 信息安全
- 如果 ID 是间断，歹意用户的爬取工作就非常容易做了，间接依照程序下载指定 URL 即可，如果是订单号就危险了，竞争对手能够间接晓得咱们一天的单量，所以在一些利用场景下，须要 ID 无规则不规则，让竞争对手不好猜
- 含工夫戳
- 一样可能疾速在开发中理解这个分布式 ID 什么时候生成的
ID 号生成零碎的可用性要求
- 高可用
- 公布一个获取分布式 ID 申请，服务器就要保障 99.999% 的状况下给我创立一个惟一分布式 ID
- 低提早
- 发一个获取分布式 ID 的申请，服务器就要快，极速
- 高 QPS
- 例如并发一口气 10 万个创立分布式 ID 申请同时杀过来，服务器要顶得住且一下子胜利创立 10 万个分布式 ID
个别通用解决方案
UUID
UUID.randomUUID(), UUID 的标准型蕴含 32 个 16 进制数字，以连字号分为五段，模式为 8-4-4-4-12 的 36 个字符，性能十分高，本地生成，没有网络耗费。
存在问题
入数据库性能差，因为 UUID 是无序的
无序，无奈预测他的生成程序，不能生成递增有序的数字
首先分布式 id 个别都会作为逐步，然而依照 mysql 官网举荐主键尽量越短越好，UUID 每一个都很长，所以不是很举荐。
主键，ID 作为主键时，在特定的环境下会存在一些问题
比方做 DB 主键的场景下，UUID 就十分不实用 MySQL 官网有明确的阐明
索引，B+ 树索引的决裂
既然分布式 ID 是主键，而后主键是蕴含索引的，而 mysql 的索引是通过 B + 树来实现的，每一次新的 UUID 数据的插入，为了查问的优化，都会对索引底层的 B + 树进行批改，因为 UUID 数据是无序的，所以每一次 UUID 数据的插入都会对主键的 B + 树进行很大的批改，这一点很不好，插入齐全无序，岂但会导致一些两头节点产生决裂，也会白白发明出很多不饱和的节点，这样大大降低了数据库插入的性能。
UUID 只能保障全局唯一性，不满足前面的趋势递增，枯燥递增
数据库自增主键
单机
在分布式外面，数据库的自增 ID 机制的次要原理是：数据库自增 ID 和 mysql 数据库的 replace into 实现的，这里的 replace into 跟 insert 性能 相似，不同点在于：replace into首先尝试插入数据列表中，如果发现表中曾经有此行数据（依据主键或惟一索引判断）则先删除，在插入，否则直接插入新数据。
REPLACE INTO的含意是插入一条记录，如果表中惟一索引的值遇到抵触，则替换老数据
REPLACE into t_test(stub) values('b');
select LAST_INSERT_ID();
咱们每次插入的时候，发现都会把原来的数据给替换，并且 ID 也会减少
这就满足了
- 递增性
- 枯燥性
- 唯一性
在分布式状况下，并且并发量不多的状况，能够应用这种计划来解决，取得一个全局的惟一 ID
集群分布式集群
那数据库自增 ID 机制适宜做分布式 ID 吗？答案是不太适宜
零碎程度扩大比拟艰难，比方定义好步长和机器台数之后，如果要增加机器该怎么办，假如当初有一台机器发号是：1,2,3,4,5,（步长是 1），这个时候须要扩容机器一台，能够这样做：把第二胎机器的初始值设置得比第一台超过很多，貌似还好，然而假如线上如果有 100 台机器，这个时候扩容要怎么做，几乎是噩梦，所以零碎程度扩大计划简单难以实现。
数据库压力还是很大，每次获取 ID 都得读写一次数据库，十分影响性能，不合乎分布式 ID 外面的提早低和高 QPS 的规定（在高并发下，如果都去数据库外面获取 ID，那是十分影响性能的）
基于 Redis 生成全局 ID 策略
单机版
因为 Redis 是单线程，天生保障原子性，能够应用原子操作 INCR 和 INCRBY 来实现
INCRBY：设置增长步长
集群分布式
留神：在 Redis 集群状况下，同样和 MySQL 一样须要设置不同的增长步长，同时 key 肯定要设置有效期，能够应用 Redis 集群来获取更高的吞吐量。
假如一个集群中有 5 台 Redis，能够初始化每台 Redis 的值别离是 1,2,3,4,5，而后设置步长都是 5
各个 Redis 生成的 ID 为：
A：1 6 11 16 21
B：2 7 12 17 22
C：3 8 13 18 23
D：4 9 14 19 24
E：5 10 15 20 25
然而存在的问题是，就是 Redis 集群的保护和颐养比拟麻烦，配置麻烦。因为要设置单点故障，哨兵值守
然而次要是的问题就是，为了一个 ID，却须要引入整个 Redis 集群，有种杀鸡焉用牛刀的感觉
雪花算法
是什么
Twitter 的分布式自增 ID 算法，Snowflake
最后 Twitter 把存储系统从 MySQL 迁徙到 Cassandra（由 Facebook 开发一套开源分布式 NoSQL 数据库系统）因为 Cassandra 没有程序 ID 生成机制，所有开发了这样一套全局惟一 ID 生成服务。
Twitter 的分布式雪花算法 SnowFlake，经测试 SnowFlake 每秒能够产生 26 万个自增可排序的 ID
- twitter 的 SnowFlake 生成 ID 可能依照工夫有序生成
- SnowFlake 算法生成 ID 的后果是一个 64Bit 大小的整数，为一个 Long 型（转换成字符串后长度最多 19）
- 分布式系统内不会产生 ID 碰撞（由 datacenter 和 workerID 做辨别）并且效率较高
分布式系统中，有一些须要全局惟一 ID 的场景，生成 ID 的根本要求
- 在分布式环境下，必须全局唯一性
- 个别都须要枯燥递增，因为个别惟一 ID 都会存在数据库，而 InnoDB 的个性就是将内容存储在主键索引上的叶子节点，而且是从左往右递增的，所有思考到数据库性能，个别生成 ID 也最好是枯燥递增的。为了避免 ID 抵触能够应用 36 位 UUID，然而 UUID 有一些毛病，首先是它绝对比拟长，并且另外 UUID 个别是无序的
- 可能还会须要无规则，因为如果应用惟一 ID 作为订单号这种，为了不让他人晓得一天的订单量多少，就须要这种规定
构造
雪花算法的几个外围组成部分
在 Java 中 64bit 的证书是 long 类型，所以在 SnowFlake 算法生成的 ID 就是 long 类存储的
第一局部
二进制中最高位是符号位，1 示意正数，0 示意负数。生成的 ID 个别都是用整数，所以最高位固定为 0。
第二局部
第二局部是 41bit 工夫戳位，用来记录时间戳，毫秒级
41 位能够示意 2^41 -1 个数字
如果只用来示意正整数，能够示意的范畴是：0 – 2^41 -1，减 1 是因为能够示意的数值范畴是从 0 开始计算的，而不是从 1。
也就是说 41 位能够示意 2^41 – 1 毫秒的值，转换成单位年则是 69.73 年
第三局部
第三局部为工作机器 ID，10Bit 用来记录工作机器 ID
能够部署在 2^10 = 1024 个节点，包含 5 位 datacenterId（数据中心，机房）和 5 位 workerID（机器码）
5 位能够示意的最大正整数是 2 ^ 5 = 31 个数字，来示意不同的数据中心 和 机器码
第四局部
12 位 bit 能够用来示意的正整数是 2^12 = 4095，即能够用 0 1 2 … 4094 来示意同一个机器同一个工夫戳内产生的 4095 个 ID 序号。
SnowFlake 能够保障
所有生成的 ID 按工夫趋势递增
整个分布式系统内不会产生反复 ID，因为有 datacenterId 和 workerId 来做辨别
实现
雪花算法是由 scala 算法编写的，有人应用 java 实现，github 地址
https://github.com/beyondfeng…
/**
* twitter 的 snowflake 算法 -- java 实现
*
* @author beyond
*/
public class SnowFlake {
/**
* 起始的工夫戳
*/
private final static long START_STMP = 1480166465631L;
/**
* 每一部分占用的位数
*/
private final static long SEQUENCE_BIT = 12; // 序列号占用的位数
private final static long MACHINE_BIT = 5; // 机器标识占用的位数
private final static long DATACENTER_BIT = 5;// 数据中心占用的位数
/**
* 每一部分的最大值
*/
private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
/**
* 每一部分向左的位移
*/
private final static long MACHINE_LEFT = SEQUENCE_BIT;
private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;
private long datacenterId; // 数据中心
private long machineId; // 机器标识
private long sequence = 0L; // 序列号
private long lastStmp = -1L;// 上一次工夫戳
public SnowFlake(long datacenterId, long machineId) {if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
}
if (machineId > MAX_MACHINE_NUM || machineId < 0) {throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0");
}
this.datacenterId = datacenterId;
this.machineId = machineId;
}
/**
* 产生下一个 ID
*
* @return
*/
public synchronized long nextId() {long currStmp = getNewstmp();
if (currStmp < lastStmp) {throw new RuntimeException("Clock moved backwards. Refusing to generate id");
}
if (currStmp == lastStmp) {
// 雷同毫秒内，序列号自增
sequence = (sequence + 1) & MAX_SEQUENCE;
// 同一毫秒的序列数曾经达到最大
if (sequence == 0L) {currStmp = getNextMill();
}
} else {
// 不同毫秒内，序列号置为 0
sequence = 0L;
}
lastStmp = currStmp;
return (currStmp - START_STMP) << TIMESTMP_LEFT // 工夫戳局部
| datacenterId << DATACENTER_LEFT // 数据中心局部
| machineId << MACHINE_LEFT // 机器标识局部
| sequence; // 序列号局部
}
private long getNextMill() {long mill = getNewstmp();
while (mill <= lastStmp) {mill = getNewstmp();
}
return mill;
}
private long getNewstmp() {return System.currentTimeMillis();
}
public static void main(String[] args) {SnowFlake snowFlake = new SnowFlake(2, 3);
for (int i = 0; i < (1 << 12); i++) {System.out.println(snowFlake.nextId());
}
}
}
工程落地教训
hutools 工具包
地址：https://github.com/looly/hutool
SpringBoot 整合雪花算法
引入 hutool 工具类
<dependency>
<groupId>cn.hutool</groupId>
<artifactId>hutool-all</artifactId>
<version>5.3.1</version>
</dependency>
整合
/**
* 雪花算法
*
* @author: 陌溪
*/
public class SnowFlakeDemo {
private long workerId = 0;
private long datacenterId = 1;
private Snowflake snowFlake = IdUtil.createSnowflake(workerId, datacenterId);
@PostConstruct
public void init() {
try {
// 将网络 ip 转换成 long
workerId = NetUtil.ipv4ToLong(NetUtil.getLocalhostStr());
} catch (Exception e) {e.printStackTrace();
}
}
/**
* 获取雪花 ID
* @return
*/
public synchronized long snowflakeId() {return this.snowFlake.nextId();
}
public synchronized long snowflakeId(long workerId, long datacenterId) {Snowflake snowflake = IdUtil.createSnowflake(workerId, datacenterId);
return snowflake.nextId();}
public static void main(String[] args) {SnowFlakeDemo snowFlakeDemo = new SnowFlakeDemo();
for (int i = 0; i < 20; i++) {new Thread(() -> {System.out.println(snowFlakeDemo.snowflakeId());
}, String.valueOf(i)).start();}
}
}
失去后果
1251350711346790400
1251350711346790402
1251350711346790401
1251350711346790403
1251350711346790405
1251350711346790404
1251350711346790406
1251350711346790407
1251350711350984704
1251350711350984706
1251350711350984705
1251350711350984707
1251350711350984708
1251350711350984709
1251350711350984710
1251350711350984711
1251350711350984712
1251350711355179008
1251350711355179009
1251350711355179010
优缺点
长处
- 毫秒数在高维，自增序列在低位，整个 ID 都是趋势递增的
- 不依赖数据库等第三方零碎，以服务的形式部署，稳定性更高，生成 ID 的性能也是十分高的
- 能够依据本身业务个性调配 bit 位，非常灵活
毛病
- 依赖机器时钟，如果机器时钟回拨，会导致反复 ID 生成
- 在单机上是递增的，但因为波及到分布式环境，每台机器上的时钟不可能齐全同步，有时候会呈现不是全局递增的状况，此毛病能够认为无所谓，个别分布式 ID 只要求趋势递增，并不会严格要求递增，90% 的需要只要求趋势递增。
其它补充
- 为了解决时钟回拨问题，导致 ID 反复，前面有人专门提出了解决的计划
- 百度开源的分布式惟一 ID 生成器 UidGenerator
- Leaf – 美团点评分布式 ID 生成零碎