package AlgorithmProjects; /** * author:Yexin * create 2018-05-02 19:31 * Desc:该算法是用来生成全局唯一ID * SnowFlake所生成的ID一共分成四部分： * 1.第一位 * 占用1bit，其值始终是0，没有实际作用。 * 2.时间戳 * 占用41bit，精确到毫秒，总共可以容纳约140年的时间。 * 3.工作机器id * 占用10bit，其中高位5bit是数据中心ID（datacenterId），低位5bit是工作节点ID（workerId），做多可以容纳1024个节点。 * 4.序列号 * 占用12bit，这个值在同一毫秒同一节点上从0开始不断累加，最多可以累加到4095。 * SnowFlake算法在同一毫秒内最多可以生成多少个全局唯一ID呢？只需要做一个简单的乘法： * 同一毫秒的ID数量 = 1024 X 4096 = 4194304 * 这个数字在绝大多数并发场景下都是够用的。 * * SnowFlake算法的优点： * * 1.生成ID时不依赖于DB，完全在内存生成，高性能高可用。 * * 2.ID呈趋势递增，后续插入索引树的时候性能较好。 * * * SnowFlake算法的缺点： * * 依赖于系统时钟的一致性。如果某台机器的系统时钟回拨，有可能造成ID冲突，或者ID乱序。 **/ import java.lang.String; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; public class SnowFlask { //初始时间戳 private static final long INITIAL_TIME_STAMP = 1483200000000L; //机器ID所占的位数 private static final long WORK_ID_BITS = 5L;//5位 //数据标识ID所占的位数 private static final long DATACENTER_ID_BITS = 5L; //支持的最大机器ID，结果31，这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数 private static final long MAX_WORK_ID = ~(-1L << WORK_ID_BITS); //最大的数据标识ID，为31 private static final long MAX_DATACENTER_ID = ~(-1L << DATACENTER_ID_BITS); //序列在ID中所占的位数 private final long SEQUENCE_BITS = 12L; //机器ID的偏移量(12) private final long WORKERID_OFFSET = SEQUENCE_BITS; //数据中心ID的偏移量(12+5) private final long DATACENTERID_OFFSET = SEQUENCE_BITS + SEQUENCE_BITS; //时间截的偏移量(5+5+12) private final long TIMESTAMP_OFFSET = SEQUENCE_BITS + WORK_ID_BITS + DATACENTER_ID_BITS; //生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) private final long SEQUENCE_MASK = ~(-1L << SEQUENCE_BITS); //工作节点ID(0~31) private long workerId; //数据中心ID(0~31) private long datacenterId; //毫秒内序列(0~4095) private long sequence = 0L; //上次生成ID的时间截 private long lastTimestamp = -1L; /** * 构造函数 * * @param workerId 工作节点ID（0~31） * @param datacenterId 数据中心ID(0~31) */ public SnowFlask(long workerId,long datacenterId){ if(workerId > MAX_WORK_ID || workerId < 0){ //println("WorkerID 不能大于 %d 或者小于0",MAX_WORK_ID); } if(datacenterId > MAX_DATACENTER_ID || datacenterId < 0){ //println("DatacenterID 不能大于 %d 或者小于0",MAX_DATACENTER_ID); } this.workerId = workerId; this.datacenterId = datacenterId; } /** * 获得下一个ID（用同步锁保证线程安全） * @return SnowflakeId */ public synchronized long nestId(){ long timestamp = System.currentTimeMillis(); if(timestamp < lastTimestamp){ throw new RuntimeException("当前时间小于上一次的记录"); } //如果是同一时间生成的，则进行毫秒内序列 if(lastTimestamp == timestamp){ sequence = (sequence + 1) & SEQUENCE_MASK; //sequence等于0说明毫秒内序列已经增长到最大值 if(sequence == 0){ //阻塞到下一个毫秒,获得新的时间戳 timestamp = tilNextMillis(lastTimestamp); } } //时间戳改变，毫秒内序列重置 else { sequence = 0L; } //上次生成ID的时间截 lastTimestamp = timestamp; //移位并通过或运算拼到一起组成64位的ID.************************************************** //通过实例对象调用这个方法时，下面的变量workerId，datacenterId已经变成了对象的成员变量值了。 //num<<3 表示num左移三位，num>>4 表示num右移4位，溢出则截断，高位补符号位，低位补0 return ((timestamp - INITIAL_TIME_STAMP) << TIMESTAMP_OFFSET) | (datacenterId << DATACENTERID_OFFSET) | (workerId << WORKERID_OFFSET) | sequence; } /** * 阻塞到下一个毫秒，直到获得新的时间戳 * @param lastTimestamp * @return 当前的时间戳 */ protected long tilNextMillis(long lastTimestamp){ long timestamp = System.currentTimeMillis(); while(timestamp <= lastTimestamp){ timestamp = System.currentTimeMillis(); } return timestamp; } public static void main(String[] args){ final SnowFlask idGennerator = new SnowFlask(1,1);//直接通过构造方法得到对象 //线程池并行执行10000次ID生成 ExecutorService executorService = Executors.newCachedThreadPool(); for (int i = 0; i < 100; i++) { //用线程执行 executorService.execute(new Runnable() { @Override public void run() { long id = idGennerator.nestId(); System.out.println("当前的UUID为："+id+" 时间为："+(System.currentTimeMillis()-INITIAL_TIME_STAMP)); } }); } executorService.shutdown(); } }
