前面文章在谈论分布式唯一ID生成的时候，有提到雪花算法，这一次，我们详细点讲解，只讲它。
据国家大气研究中心的查尔斯·奈特称，一般的雪花大约由10^19个水分子组成。在雪花形成过程中，会形成不同的结构分支，所以说大自然中不存在两片完全一样的雪花，每一片雪花都拥有自己漂亮独特的形状。雪花算法表示生成的id如雪花般独一无二。
snowflake是Twitter开源的分布式ID生成算法，结果是一个long型的ID。其核心思想是：使用41bit作为毫秒数，10bit作为机器的ID（5个bit是数据中心，5个bit的机器ID），12bit作为毫秒内的流水号（意味着每个节点在每毫秒可以产生 4096 个 ID），最后还有一个符号位，永远是0。
核心思想：分布式，唯一。
雪花算法是 64 位 的二进制，一共包含了四部分：
由于41位是时间戳，我们的时间计算是从1970年开始的，只能使用69年，为了不浪费，其实我们可以用时间的相对值，也就是以项目开始的时间为基准时间，往后可以使用69年。获取唯一ID的服务，对处理速度要求比较高，所以我们全部使用位运算以及位移操作，获取当前时间可以使用System.currentTimeMillis()。
在获取时间的时候，可能会出现时间回拨的问题，什么是时间回拨问题呢？就是服务器上的时间突然倒退到之前的时间。
解决方案
由于时间回拨导致的生产重复的ID的问题，其实百度和美团都有自己的解决方案了，有兴趣可以去看看，下面不是它们官网文档的信息：
public class SnowFlake {
// 数据中心(机房) id
private long datacenterId;
// 机器ID
private long workerId;
// 同一时间的序列
private long sequence;
public SnowFlake(long workerId, long datacenterId) {
this(workerId, datacenterId, 0);
}
public 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;
}
// 开始时间戳（2021-10-16 22:03:32）
private long twepoch = 1634393012000L;
// 机房号，的ID所占的位数 5个bit 最大:11111(2进制)--> 31(10进制)
private long datacenterIdBits = 5L;
// 机器ID所占的位数 5个bit 最大:11111(2进制)--> 31(10进制)
private long workerIdBits = 5L;
// 5 bit最多只能有31个数字，就是说机器id最多只能是32以内
private long maxWorkerId = -1L ^ (-1L << workerIdBits);
// 5 bit最多只能有31个数字，机房id最多只能是32以内
private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
// 同一时间的序列所占的位数 12个bit 111111111111 = 4095 最多就是同一毫秒生成4096个
private long sequenceBits = 12L;
// workerId的偏移量
private long workerIdShift = sequenceBits;
// datacenterId的偏移量
private long datacenterIdShift = sequenceBits + workerIdBits;
// timestampLeft的偏移量
private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
// 序列号掩码 4095 (0b111111111111=0xfff=4095)
// 用于序号的与运算，保证序号最大值在0-4095之间
private long sequenceMask = -1L ^ (-1L << sequenceBits);
// 最近一次时间戳
private long lastTimestamp = -1L;
// 获取机器ID
public long getWorkerId() {
return workerId;
}
// 获取机房ID
public long getDatacenterId() {
return datacenterId;
}
// 获取最新一次获取的时间戳
public long getLastTimestamp() {
return lastTimestamp;
}
// 获取下一个随机的ID
public 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;
// sequence序列大于4095
if (sequence == 0) {
// 调用到下一个时间戳的方法
timestamp = tilNextMillis(lastTimestamp);
}
} else {
// 如果是当前时间的第一次获取，那么就置为0
sequence = 0;
}
// 记录上一次的时间戳
lastTimestamp = timestamp;
// 偏移计算
return ((timestamp - twepoch) << timestampLeftShift) |
(datacenterId << datacenterIdShift) |
(workerId << workerIdShift) |
sequence;
}
private long tilNextMillis(long lastTimestamp) {
// 获取最新时间戳
long timestamp = timeGen();
// 如果发现最新的时间戳小于或者等于序列号已经超4095的那个时间戳
while (timestamp <= lastTimestamp) {
// 不符合则继续
timestamp = timeGen();
}
return timestamp;
}
private long timeGen() {
return System.currentTimeMillis();
}
public static void main(String[] args) {
SnowFlake worker = new SnowFlake(1, 1);
long timer = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
worker.nextId();
}
System.out.println(System.currentTimeMillis());
System.out.println(System.currentTimeMillis() - timer);
}
}
在计算机的表示中，第一位是符号位，0表示整数，第一位如果是1则表示负数，我们用的ID默认就是正数，所以默认就是0，那么这一位默认就没有意义。
机器位或者机房位，一共10 bit，如果全部表示机器，那么可以表示1024台机器，如果拆分，5 bit 表示机房，5bit表示机房里面的机器，那么可以有32个机房，每个机房可以用32台机器。
由于时间戳只能用69年，我们的计时又是从1970年开始的，所以这个twepoch表示从项目开始的时间，用生成ID的时间减去twepoch作为时间戳，可以使用更久。
表示 x 位二进制可以表示多少个数值，假设x为3：
在计算机中，第一位是符号位，负数的反码是除了符号位，1变0，0变1, 而补码则是反码+1：
-1L 原码：1000 0001
-1L 反码：1111 1110
-1L 补码：1111 1111
从上面的结果可以知道，-1L其实在二进制里面其实就是全部为1,那么 -1L 左移动 3位，其实得到 1111 1000，也就是最后3位是0，再与-1L异或计算之后，其实得到的，就是后面3位全是1。-1L ^ (-1L << x) 表示的其实就是x位全是1的值，也就是x位的二进制能表示的最大数值。
在获取时间戳小于上一次获取的时间戳的时候，不能生成ID，而是继续循环，直到生成可用的ID，这里没有使用拓展位防止时钟回拨。
如果前端直接使用服务端生成的long 类型 id，会发生精度丢失的问题，因为 JS 中Number是16位的（指的是十进制的数字），而雪花算法计算出来最长的数字是19位的，这个时候需要用 String 作为中间转换，输出到前端即可。
雪花算法其实是依赖于时间的一致性的，如果时间回拨，就可能有问题，一般使用拓展位解决。而只能使用69年这个时间限制，其实可以根据自己的需要，把时间戳的位数设置得更多一点，比如42位可以用139年，但是很多公司首先得活下来。当然雪花算法也不是银弹，它也有缺点，在单机上递增，而多台机器只是大致递增趋势，并不是严格递增的。
没有最好的设计方案，只有合适和不合适的方案。
原文：
https://www.cnblogs.com/Damaer/p/15559201.html
京公网安备 11010802035086号