大家好，又见面了，我是你们的朋友全栈君。
一、分布式ID发号器
要求很明确：不同机器同一时间生成不同ip；同一机器不同时间生成不同IP;
所以根据需求，可选变量有： 机器（网卡、IP） 时间，随机数
二、Why not UUID？
UUID的实现：算法的核心思想是结合机器的网卡、当地时间、一个随机数来生成UUID。
优势：保证唯一性；本地调用，不需要rpc
UUID的缺陷：
1.UUID较长，占用内存空间；往往用字符串表示，作为主键建立索引查询效率低，常见优化方案为“转化为两个uint64整数存储”或者“折半存储”（折半后不能保证唯一性）
2.不具有有序性，无法保证趋势递增
三、依赖DB自增可行么？
实现：自增 设定步长；8个服务节点8个实例（类似取模）；
缺陷：
1.不利于服务节点扩充；服务节点固定，步长固定，难以进行水平服务节点的扩展。
2.依赖DB，对数据库造成额外压力
四.全局唯一ID生成器如何设计？考量因素有哪些
1.全局唯一；有序性（不一定连续，但趋势递增）；可反解信息；
2.业务性能要求：高性能、高可用
3.接入方式：嵌入式、中心服务发布、rest发布模式
设计一 ：ID数据结构
64位
1.机器ID 10位；2的10次方最多可支持1k 台机器；如果每台机器TPS为1W/s,10台服务器则可以有10W/s的TPS，基本满足大部分业务要求。
2.序列号 10位或20位；同理，计算2的20次方，每秒平均可产生百万个ID
3.时间戳 30或40位（分别对应秒级、毫秒级）-时间保证趋势递增
其他可根据业务特点，加上定制的不同生产方式（pom、rest）或版本信息
设计二 并发
为支持大量并发的网络请求，ID生成服务一般采用多线程支持，对于竞争时间和序列（time sequence）采用juc中ReentrantLock或synchronized或atomic变量支持（推荐）。
实现
1.定义id实体结构（机器 时间 种子（生成随机数））
代码语言：javascript复制//时间戳
private Long time;
//序列号
private Integer sequence;
//生成随机数的种子
private Integer seed;
//机器ip
private Integer clusterIp;2.根据结构获取对应请求数据，组装实体数据（获取时间戳（毫秒或秒级）os获取本机ip、mac等数据），生成一个不重复的id
代码语言：javascript复制//synch保证线程安全
public synchronized long getId()计算（左移拼装，）【时间戳-初始时间】左移两位集群ip-sequence
3.解析ip，获取对应机器ip、时间戳等信息，则右移取指定位即可
五、Twitter的snowflake算法
Twitter 利用 zookeeper 实现了一个全局ID生成的服务 Snowflake：https://github.com/twitter-archive/snowflake
- 1位符号位：
由于 long 类型在 java 中带符号的，最高位为符号位，正数为 0，负数为 1，且实际系统中所使用的ID一般都是正数，所以最高位为 0。
- 41位时间戳（毫秒级）：
需要注意的是此处的 41 位时间戳并非存储当前时间的时间戳，而是存储时间戳的差值（当前时间戳 – 起始时间戳），这里的起始时间戳一般是ID生成器开始使用的时间戳，由程序来指定，所以41位毫秒时间戳最多可以使用 (1 << 41) / (1000x60x60x24x365) = 69年。
- 10位数据机器位：
包括5位数据标识位和5位机器标识位，这10位决定了分布式系统中最多可以部署 1 << 10 = 1024 s个节点。超过这个数量，生成的ID就有可能会冲突。
- 12位毫秒内的序列：
这 12 位计数支持每个节点每毫秒（同一台机器，同一时刻）最多生成 1 << 12 = 4096个ID
加起来刚好64位，为一个Long型。
- 优点：高性能，低延迟，按时间有序，一般不会造成ID碰撞
- 缺点：需要独立的开发和部署，依赖于机器的时钟
实现：
代码语言：javascript复制public class IdWorker {
/**
* 起始时间戳 2017-04-01
*/
private final long epoch = 1491004800000L;
/**
* 机器ID所占的位数
*/
private final long workerIdBits = 5L;
/**
* 数据标识ID所占的位数
*/
private final long dataCenterIdBits = 5L;
/**
* 支持的最大机器ID,结果是31
*/
private final long maxWorkerId = ~(-1L << workerIdBits);
/**
* 支持的最大数据标识ID,结果是31
*/
private final long maxDataCenterId = ~(-1 << dataCenterIdBits);
/**
* 毫秒内序列在id中所占的位数
*/
private final long sequenceBits = 12L;
/**
* 机器ID向左移12位
*/
private final long workerIdShift = sequenceBits;
/**
* 数据标识ID向左移17(12 5)位
*/
private final long dataCenterIdShift = sequenceBits workerIdBits;
/**
* 时间戳向左移22(12 5 5)位
*/
private final long timestampShift = sequenceBits workerIdBits dataCenterIdBits;
/**
* 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095)
*/
private final long sequenceMask = ~(-1L << sequenceBits);
/**
* 数据标识ID（0～31）
*/
private long dataCenterId;
/**
* 机器ID（0～31）
*/
private long workerId;
/**
* 毫秒内序列（0～4095）
*/
private long sequence;
/**
* 上次生成ID的时间戳
*/
private long lastTimestamp = -1L;
public IdWorker(long dataCenterId, long workerId) {
if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
throw new IllegalArgumentException(String.format("dataCenterId can't be greater than %d or less than 0", maxDataCenterId));
}
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
}
this.dataCenterId = dataCenterId;
this.workerId = workerId;
}
/**
* 获得下一个ID (该方法是线程安全的)
* @return snowflakeId
*/
public synchronized long nextId() {
long timestamp = timeGen();
//如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过,这个时候应当抛出异常
if (timestamp < lastTimestamp) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
//如果是同一时间生成的，则进行毫秒内序列
if (timestamp == lastTimestamp) {
sequence = (sequence 1) & sequenceMask;
//毫秒内序列溢出
if (sequence == 0) {
//阻塞到下一个毫秒,获得新的时间戳
timestamp = nextMillis(lastTimestamp);
}
} else {//时间戳改变，毫秒内序列重置
sequence = 0L;
}
lastTimestamp = timestamp;
//移位并通过按位或运算拼到一起组成64位的ID
return ((timestamp - epoch) << timestampShift) |
(dataCenterId << dataCenterIdShift) |
(workerId << workerIdShift) |
sequence;
}
/**
* 返回以毫秒为单位的当前时间
* @return 当前时间(毫秒)
*/
protected long timeGen() {
return System.currentTimeMillis();
}
/**
* 阻塞到下一个毫秒，直到获得新的时间戳
* @param lastTimestamp 上次生成ID的时间截
* @return 当前时间戳
*/
protected long nextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = lastTimestamp;
}
return timestamp;
}
}实现注意点：
1.由于存在对时进行修改，snowflake算法应对时钟回拨的做法是直接抛出异常。
2.其次是12位序列号溢出的问题，即1ms内请求生成的ID个数超过了2的12次方=4096个id。snowflake算法对此的做法是，等到下一ms再生成ID。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/148260.html原文链接：https://javaforall.cn
