【数据结构与算法】Snowflake雪花算法Java实现

Snowflake产生的ID由 64 bit 的二进制数字组成，被分成了4个部分，每一部分存储的数据都有特定的含义：

• 第 0 位： 符号位（标识正负），始终为 0；
• 第 1~41 位 ：一共 41 位，用来表示时间戳，单位是毫秒，可以支撑2 ^41 毫秒（约 69 年）2^41/1000*60*60*24*365 = 69年
• 第 42~52 位 ：一共 10 位，工作机器id，一般用前 5 位表示机房ID，后 5 位表示机器ID，用于区分不同集群/机房的节点，10位的长度，可以表示1024个不同节点。
• 第 53~64 位 ：一共 12 位，用来表示序列号。 序列号为自增值，代表单台机器每毫秒能够产生的最大ID 数(2^12 = 4096)，也就是说单台机器每毫秒最多可以生成 4096 个 唯一 ID，最大可以支持400w左右的并发量。

/*** 雪花算法* @author CC* @version 1.0* @since2023/10/24*/
public class SnowFlake {// 机房(数据中心)IDprivate long datacenterId;// 机器IDprivate long workerId;// 同一时间的序列号private long sequence;// 开始时间戳private long twepoch = 1634393012000L;// 机房ID所占的位数： 5个bitprivate long datacenterIdBits = 5L;// 机器ID所占的位数：5个bitprivate long workerIdBits = 5L;// 最大机器ID：5bit最多只能有31个数字，就是说机器id最多只能是32以内// 最大:11111(2进制) --> 31(10进制)private long maxWorkerId = -1L ^ (-1L << workerIdBits);// 最大机房ID：5bit最多只能有31个数字，机房id最多只能是32以内// 最大:11111(2进制)--> 31(10进制)private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);// 同一时间的序列所占的位数:12个bit// 最大111111111111 = 4095  代表同一毫秒最多生成4096个private long sequenceBits = 12L;// workerId的偏移量12private long workerIdShift = sequenceBits;// datacenterId的偏移量12+5private long datacenterIdShift = sequenceBits + workerIdBits;// timestampLeft的偏移量12+5+5private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;// 序列号掩码 4095 (0b111111111111=0xfff=4095)// 用于序号的与运算，保证序号最大值在0-4095之间private long sequenceMask = -1L ^ (-1L << sequenceBits);// 最近一次时间戳private long lastTimestamp = -1L;// 按照机器ID和机房ID创建雪花算法对象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;}// 获取下一个随机的IDpublic 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 {// 如果是当前时间的第一次获取，那么就置为0sequence = 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);for (int i = 0; i < 100; i++) {System.out.println(worker.nextId());}System.out.println();worker = new SnowFlake(1, 2);for (int i = 0; i < 100; i++) {System.out.println(worker.nextId());}}
}