java实现雪花算法，不使用synchronized，无锁实现

Z时代
2024-01-10
分类：综合
package com.sudytech.orm2.surpport.util.seq;
import java.util.Date;
import java.util.concurrent.atomic.AtomicStampedReference;
/**
 *  雪花算法生成唯一id，线程安全，使用元字库，无同步锁实现
 * <pre>
 *  0-00000000000000000000000000000000000000000-0000000000-000000000000
 *  x-yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy-zzzzzzzzzz-dddddddddddd
 * (x) 1bit，不用，二进制中最高位是符号位，1表示负数，0表示正数。生成的id一般都是用整数，所以最高位固定为0。
 * 
 * (y) 41bit-时间戳，用来记录时间戳，毫秒级。 - 41位最大值，换算成"年"最大可以表示约69年
 * 
 * (z) 10bit-工作机器id，用来记录工作机器id。 - 可以部署在个多个节点，包括5位datacenterId和5位workerId
 *     5位（bit）可以表示的最大正整数是，即可以用0、1、2、3、....31这32个数字，来表示不同的datecenterId或workerId
 * 
 * (d) 12bit-序列号，序列号，用来记录同毫秒内产生的不同id。 -
 *     12位（bit）可以表示的最大正整数是，即可以用0、1、2、3、....4094这4095个数字，来表示同一机器同一时间截（毫秒)内产生的4095个ID序号。
 * </pre>
 */
public class SnowFlower {
	// 最大序列，12位
	private static final int MAX_SEQUENCE = (1 << 12) - 1;
	// 起始时间, 2016-01-01
	private static final long START_TIME = 1451577600000L;
	//最大时间戳， 41位
	private static final long MAX_TIME = (1L << 41) -1;
	// 带时间的序列，原子操作
	private AtomicStampedReference<StampedSequence> current;
	// 数据中心id
	private long datacenterId;
	// 工作id
	private long workerId;
	//提前计算好的机器id
	private long machineId;
	public SnowFlower(int datacenterId, int workerId) {
		StampedSequence dt = new StampedSequence(START_TIME, 0);
		current = new AtomicStampedReference<SnowFlower.StampedSequence>(dt, 0);
		int maxId = (1 << 5) -1;
		if(datacenterId < 0 || datacenterId > maxId) {
			throw new IllegalArgumentException(
					String.format("datacenterId can"t be greater than %d or less than 0", maxId));
		}
		if(workerId < 0 || workerId > maxId) {
			throw new IllegalArgumentException(
					String.format("workerId can"t be greater than %d or less than 0", maxId));
		}
		this.datacenterId = datacenterId;
		this.workerId = workerId;
		//初始化机器id
		machineId = ((this.datacenterId << 5) | this.workerId) << 12;
	}
	public long nextId() {
		StampedSequence seq = nextSequence();
		long time = seq.timestamp - START_TIME;
		if( time > MAX_TIME) {
			throw new RuntimeException("Timestamp overflow! " + new Date(seq.timestamp));
		}
		long value = (time << 22) | machineId | seq.sequence;
		return value;
	}
	StampedSequence nextSequence() {
		//下一个时间戳序列
		StampedSequence nextSequence = new StampedSequence(0, 0);
		//版本
		int[] versionHolder = new int[1];
		while (true) {
			long now = System.currentTimeMillis();
			StampedSequence curSequence = current.get(versionHolder);
			if (now < curSequence.timestamp) {
				throw new RuntimeException("Clock moved backwards!");
			}else if (curSequence.timestamp == now) {
				if (curSequence.sequence >= MAX_SEQUENCE) {
					//满序列等待下一毫秒
					continue;
				}
				nextSequence.timestamp = curSequence.timestamp;
				nextSequence.sequence = curSequence.sequence + 1;
				boolean set = current.compareAndSet(curSequence, nextSequence, versionHolder[0], versionHolder[0] + 1);
				if (!set) {
					// 无锁更新失败，重新获取
					continue;
				}
				break;
			} else {
				nextSequence.timestamp = now;
				nextSequence.sequence = 0;
				boolean set = current.compareAndSet(curSequence, nextSequence, versionHolder[0], versionHolder[0] + 1);
				if (!set) {
					// 无锁更新失败，重新获取
					continue;
				}
				break;
			}
		}
		return nextSequence;
	}
	/**
	 * 带时间戳的序列
	 */
	static class StampedSequence {
		private long timestamp; // 时间戳
		private long sequence; // 序列
		public StampedSequence(long stamp, long sequence) {
			super();
			this.timestamp = stamp;
			this.sequence = sequence;
		}
	}
	/* 测试 */
	public static void main(String[] args) {
		SnowFlower snow = new SnowFlower(1, 1);
		for (int i = 0; i < 300; i++) {
			long seq = snow.nextId();
			System.out.println(Long.toString(seq, 2));
		}
	}}