互联网大厂面试雪花算法（Snowflake）实现

　　雪花算法(Snowflake)，是由Twitter公司开源的分布式ID生成算法，通过以划分名称空间的方式将64位的数据分割成多个部分，并且每个部分来代表不同的含义。而在Java中64位的数据只有是Long类型的数据，所以在Java中对于雪花算法的实现都是以Long类型的数据来存储的。64Bit分别代表什么意思？
　　如图所示1、第1位，占用1个bit，但是其值始终是不变的，所以可以看做是一个符号位。 2、第2位开始到第41位，是时间戳，41bit可以表示2的41次方个数据，这个数据代表是毫秒数， 那么从这里就可以知道雪花算法的使用年限大概是(2的41次方/1000*3600*24*365) ,大概的 计算结果是69年。 3、中间10位，表示机器数，也就是2的10次方台机器，但是在一般情况下，都用不了这么多的机 器。所以这十个位置可以根据需求自己拟定。 4、最后的12位，相当于一个自增排序，可以表示2的12次方的数据也就是4096个数据。
　　通过这样的划分之后，相当于在一个毫秒之内一个服务器上可以产生4096个不重复的ID值。其量级也是非常可观的。
　　从雪花算法的实现思想上来看，其ID呈现出一个递增的趋势，并且不依赖第三方的数据库，第三方的服务系统，我们可以将其以工具类，或者是以JavaBean的方式注入到容器中，使用非常方便，而且在生成ID方面也是比较高效的，同样也可以结合业务来对Bit位进行合理的分配从而生成出符合业务逻辑的全局唯一ID。
　　这里有读者会问了？
　　在中间的位置中我们引入了时间戳，那么我们如何避免时钟回拨的问题呢？也就是说如果时钟回拨了，就会导致以前恰巧生成的ID再次出现，也会出现重复ID的情况，那么我们如何去解决这个问题呢？下面是我来实现的一个雪花算法ID生成器/**  * @Classname SnowflakeIdUtils  * @Description TODO 雪花算法ID生成器  * @Date 2020/8/14 2:29 PM  * @Created by nihui  * @Version 1.0  */ @Component public class SnowflakeIdUtils {     // ==============================Fields===========================================     /** 开始时间截 (2015-01-01) */     private final long twepoch = 1420041600000L;       /** 机器id所占的位数 */     private final long workerIdBits = 5L;       /** 数据标识id所占的位数 */     private final long datacenterIdBits = 5L;       /** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */     private final long maxWorkerId = -1L ^ (-1L << workerIdBits);       /** 支持的最大数据标识id，结果是31 */     private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);       /** 序列在id中占的位数 */     private final long sequenceBits = 12L;       /** 机器ID向左移12位 */     private final long workerIdShift = sequenceBits;       /** 数据标识id向左移17位(12+5) */     private final long datacenterIdShift = sequenceBits + workerIdBits;       /** 时间截向左移22位(5+5+12) */     private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;       /** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */     private final long sequenceMask = -1L ^ (-1L << sequenceBits);       /** 工作机器ID(0~31) */     private long workerId;       /** 数据中心ID(0~31) */     private long datacenterId;       /** 毫秒内序列(0~4095) */     private long sequence = 0L;       /** 上次生成ID的时间截 */     private long lastTimestamp = -1L;       //==============================Constructors=====================================     /**      * 构造函数      * @param workerId 工作ID (0~31)      * @param datacenterId 数据中心ID (0~31)      */     public SnowflakeIdUtils(long workerId, long datacenterId) {         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));         }         this.workerId = workerId;         this.datacenterId = datacenterId;     }      public SnowflakeIdUtils(){         this(1,1);     }      public synchronized String stringId(){         return String.valueOf(this.nextId());     }     // ==============================Methods==========================================     /**      * 获得下一个ID (该方法是线程安全的)      * @return SnowflakeId      */     public synchronized long nextId() {         long timestamp = timeGen();           //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常         if (timestamp < 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;             //毫秒内序列溢出             if (sequence == 0) {                 //阻塞到下一个毫秒,获得新的时间戳                 timestamp = tilNextMillis(lastTimestamp);             }         }         //时间戳改变，毫秒内序列重置         else {             sequence = 0L;         }           //上次生成ID的时间截         lastTimestamp = timestamp;           //移位并通过或运算拼到一起组成64位的ID         return ((timestamp - twepoch) << timestampLeftShift) //                 | (datacenterId << datacenterIdShift) //                 | (workerId << workerIdShift) //                 | sequence;     }       /**      * 阻塞到下一个毫秒，直到获得新的时间戳      * @param lastTimestamp 上次生成ID的时间截      * @return 当前时间戳      */     protected long tilNextMillis(long lastTimestamp) {         long timestamp = timeGen();         while (timestamp <= lastTimestamp) {             timestamp = timeGen();         }         return timestamp;     }       /**      * 返回以毫秒为单位的当前时间      * @return 当前时间(毫秒)      */     protected long timeGen() {         return System.currentTimeMillis();     }   //    //==============================Test============================================= //    /** 测试 */ //    public static void main(String[] args) { //        SnowflakeIdUtils idWorker = new SnowflakeIdUtils(3, 1); //        System.out.println(idWorker.nextId()); //    } }总结
　　由于官方也没有对时间回拨的情况给出明确的答案，这里笔者的处理结果就是将其以异常的方式进行抛出，后来也有很多的分布式ID算法都是基于雪花算法的思想进行升级，而且避免了雪花算法带来的各种缺陷。例如百度的UidGrnerator、美团的Leaf都是在雪花算法的基础上演变出来的。