十进制、二进制表示法、位运算
什么是雪花算法关于雪花算法是啥网上到处都是，为了节省大家的流量和时间，一句话概括下：
能解决什么问题雪花算法是Twitter设计的根据时间戳、机器标识码和序列号生成的唯一长整型数
具有哪些特点确保在大规模高并发环境中，可以生成持续递增的唯一长整型数
- 唯一性
- 持续递增
- 结果为长整型数字
- 不依赖其他系统，无需引入数据库、Redis等系统
- 吞吐量大，12位序列号情况下，每毫秒可生成 4095个ID
一张非常经典的图
符号位：仅表示正、负数，0 - 正，1 - 负，雪花算法结果都为正，即符号位都为0
时间戳：系统 毫秒级 时间戳
工作机器ID：大规模集群中，标识唯一机器的机器码标识
序列号：当前时间戳内的递增编号
Java实现（关键代码）代码过长，此处仅粘贴帮助理解的关键代码，详细代码，及使用具体使用方法，请移步
public class Snowflake {
private long startTimestamp = 1380556800000L;
private final static long TOTAL_BITS = 63L;
private final static long STANDARD_TIMESTAMP_BITS = 41L;
private final static long STANDARD_DATA_CENTER_ID_BITS = 5L;
private final static long STANDARD_MACHINE_ID_BITS = 5L;
private final static long STANDARD_SEQUENCE_BITS = 12L;
private long timestampBits = 41L;
private long dataCenterIdBits = 5L;
private long machineIdBits = 5L;
private long sequenceBits = 12L;
private long maxDataCenterId = this.calcMaxValueByBits(this.dataCenterIdBits);
private long maxMachineId = this.calcMaxValueByBits(this.machineIdBits);
private long maxSequence = this.calcMaxValueByBits(this.sequenceBits);
private long timestampOffset = this.dataCenterIdBits + this.machineIdBits + this.sequenceBits;
private long dataCenterIdOffset = this.machineIdBits + this.sequenceBits;
private long machineIdOffset = this.sequenceBits;
private long lastTimestamp = 0L;
private long lastSequence = 0L;
private long dataCenterId = 1L;
private long machineId = 1L;
private long allowTimeBackwardMS = 5L;
public Snowflake() {
if(this.dataCenterId == 0L) {
this.dataCenterId = this.getDataCenterId(this.maxDataCenterId);
}
if(this.machineId == 0L){
this.machineId = this.getMachineId(this.maxMachineId);
}
}
public synchronized long nextId() {
if (this.hasCustomBits()) {
this.reCalcBitsMax(); // 重新计算各部分从左到右起始位数
this.reCalcBitsOffset(); // 重新计算各部分允许的最大值
}
long currentTimestamp = this.getCurrentTimestamp();
if (currentTimestamp < this.lastTimestamp) {
long timestampOffset = this.lastTimestamp - currentTimestamp;
if (timestampOffset > this.allowTimeBackwardMS) { // 如果时钟回拨范围大于允许的最大回拨范围，抛出异常
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", timestampOffset));
}
try {
wait(timestampOffset); // 如果回拨时间范围 小于 允许的最大回拨范围，程序等待
} catch (Exception e) {
throw new RuntimeException(e);
}
currentTimestamp = this.getCurrentTimestamp();
}
this.lastSequence = (this.lastSequence + 1) & maxSequence;
if (this.lastSequence == 0L) {
if (currentTimestamp == this.lastTimestamp) { // 相同时间戳改为下一个时间戳
currentTimestamp = this.getNextTimestamp(this.lastTimestamp);
}
this.lastSequence = ThreadLocalRandom.current().nextLong(0, 3);
}
this.lastTimestamp = currentTimestamp; // 记录当前所生成的时间戳，用于下一次生成进行比对
return ((currentTimestamp - this.startTimestamp) << this.timestampOffset)
| (this.dataCenterId << this.dataCenterIdOffset)
| (this.machineId << this.machineIdOffset)
| this.lastSequence;
}
protected long getDataCenterId(long maxDataCenterId) {
long id = 0L;
try {
InetAddress ip = InetAddress.getLocalHost();
NetworkInterface network = NetworkInterface.getByInetAddress(ip);
if (network == null) {
id = 1L;
} else {
byte[] mac = network.getHardwareAddress();
if (null != mac) {
id = ((0x000000FF & (long) mac[mac.length - 2]) | (0x0000FF00 & (((long) mac[mac.length - 1]) << 8))) >> 6;
id = id % (maxDataCenterId + 1);
}
}
} catch (Exception e) {
throw new RuntimeException(e);
}
return id;
}
protected long getMachineId(long maxMachineId) {
StringBuilder mPid = new StringBuilder();
mPid.append(dataCenterId);
String name = ManagementFactory.getRuntimeMXBean().getName();
if (this.isBlank(name)) {
mPid.append(name.split("@")[0]);
}
return (mPid.toString().hashCode() & 0xffff) % (maxMachineId + 1);
}
private long getNextTimestamp(long currentTimestamp) {
long nextTimestamp = getCurrentTimestamp();
while (nextTimestamp <= currentTimestamp) {
nextTimestamp = getCurrentTimestamp();
}
return nextTimestamp;
}
private long getCurrentTimestamp() {
return System.currentTimeMillis();
}
}
使用中可能存在的问题
- 机器时钟回拨可能会导致ID重复，解决办法：
参照
定义一定的回拨允许范围，比如： 5ms，程序等待5*2ms，后重新获取时间戳，进行ID生成
- 在集群环境中可能会受到工作机器ID大小的影响，生成的ID并非绝对递增
栗子：在1ms时，dataCenterId = 10;machineId=20的机器持续递增生成了id1；在2ms时，dataCenterId = 1;machineId=2的机器持续递增生成了id2，这时虽然id2在时间上先生成，但是并不能保证id2 > id1
-
相同的代码生成的id长度不一致，比较常见的有18位和19位
-
原因：代码中的时间戳虽然分配了41位，并且进行了左移，但是时间戳的十进制大小区别比较大，比如：
十进制1000 ，41位二进制表示为：00000000000000000000000000000001111101000
十进制1100000000000，41位二进制表示为：10000000000011101000110111111100000000000
由此可以看出，时间戳比较临近时，时间戳差值比较小。二进制即时都是41位，表示十进制的大小也是不一样的，雪花算法的64位二进制同理。
-
如何解决：
大佬的思路，请移步
在求证雪花算法最多生成的Id位数时，个人做的计算是：找生成19位Id的临界值。个人也就当玩一玩，极不推荐
雪花算法最大表示63位二进制为：111111111111111111111111111111111111111111111111111111111111111，十进制为9223372036854776000，不超过19位，可作为上边界；
计算下边界，先确定最小19位十进制数为1000000000000000000，转换成二进制00011011110000010110110101100111010011101 1001000000000000000000，但是后22位（机器标识码和序列号）处有1存在，万一机器标识码改变有可能导致十进制表示数变成18位。将后22位（机器标识码和序列号）全部置0为00011011110000010110110101100111010011101 1001000000000000000000，十进制表示为：999999999997640700为18位，但是将从右至左第24位置1，二进制表示为：00011011110000010110110101100111010011111 0000000000000000000000，即可表示19位十进制数1000000000006029300，并将此作为下边界。41位时间戳部分为：00011011110000010110110101100111010011111，转换为十进制为238418579103,也就是238418579103 ms ≈ 7.57年。与大佬算的基本一致。
-
结论，由此得出，设置的起始时间只要在当前时间7.57年前，生成的Id，永远都是19位。
-
-
定制更短雪花算法生成的ID长度，方法：
建议先考虑缩短机器标识码和序列号位数。毕竟有些项目，机器少、交易量小。
如果改变后，要确保生成Id为固定长度，可以参照大佬的思路，请移步
