分布式ID生成器-雪花算法（2022冬奥雪花生成器）

1. 雪花算法(Snowflake)

Twitter的Snowflake算法是在分布式系统中一种自增ID的算法，ID能够按照时间有序生成并且可以做到全局唯一。Twitter对雪花算法的需求：

性能

每个进程每秒至少10k个id
响应速率2ms(包括网络延迟)

协调

对于数据中心内部和跨数据中心的高可用性，生成id的机器无需进行集群协调。也就是说无需再每个服务之间进行通讯进行协调。

直接排序

无需加载整个对象ID就能排序(时间戳)

紧凑

生成的ID要紧凑，换句话说就是ID所占的长度需要适中在完成业务需要的基础上。

高可用

ID生成服务要高可用,例如：存储服务

Tips: Twitter的雪花算法的说明https://github.com/twitter-archive/snowflake/tree/scala_28

1.1 雪花算法的数据结构

雪花算法生产的ID所占8个字节64位，也就是长整型 long 的长度。

首位bit位表示符号位，生成ID都是正数所以最高位就是0
时间戳(41bit),毫秒级别时间戳。但是实际开发过程中使用的时间戳使用的是时间戳的差值。这个差值=当前时间戳 - 开发者设置的固定时间戳 ，那么41位的时间戳可以使用69年
(1L << 41) / (1000L * 60 * 60 * 24 * 365) 算出来差不多69年
机器ID(10bit),一共可以配置1024台机器，如果有多个机房在10bit进行机房和机器好进行组合
序列号(12bit),每一台机器1ms可以生成4096(如果一台机器一毫秒内生成超过4096需要进行保护)

1.2 系统时钟依赖

应该使用NTP来保持系统时钟的准确性。Snowflake 可以防止非单调时钟的影响，也就是时钟倒走。如果您的时钟运行得很快，并且NTP告诉它重复几毫秒，那么 Snowflake 将拒绝生成id，直到上次我们生成id之后的某个时间。在ntp不会让时钟倒转的模式下运行。

如果时间进行回拨那么生成的ID就有可能出现重复的情况。

2. 雪花算法Java实现

/** * @author mxsm * @date 2022/4/9 21:17 * @Since 1.0.0 */ public class SnowflakeGenerator { private static final long FIXED_TIMESTAMP = 1649491204306L; private int machineId; private int sequenceNumber = 0; //最后一次生成ID时间 private volatile long lastTimestamp = -1L; public SnowflakeGenerator(int machineId) { this.machineId = machineId; } public synchronized long nextId() { //获取当前时间 long currentTimestamp = System.currentTimeMillis(); //同一个毫秒内生成ID if(currentTimestamp == lastTimestamp){ sequenceNumber = 1; //处理一秒超过4096个 if(sequenceNumber > 4096){ while (currentTimestamp <= lastTimestamp){ currentTimestamp = System.currentTimeMillis(); } sequenceNumber = 0; } }else { //重置序列号 sequenceNumber = 0; } lastTimestamp = currentTimestamp; return ( (currentTimestamp - FIXED_TIMESTAMP) << 22) | (machineId << 12) | sequenceNumber; } }