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

　　雪花算法（Snowflake），是由Twitter公司开源的分布式ID生成算法，通过以划分名称空间的方式将64位的数据分割成多个部分，并且每个部分来代表不同的含义。而在Java中64位的数据只有是Long类型的数据，所以在Java中对于雪花算法的实现都是以Long类型的数据来存储的。64Bit分别代表什么意思？
　　如图所示1、第1位，占用1个bit，但是其值始终是不变的，所以可以看做是一个符号位。2、第2位开始到第41位，是时间戳，41bit可以表示2的41次方个数据，这个数据代表是毫秒数，那么从这里就可以知道雪花算法的使用年限大概是（2的41次方1000360024365），大概的计算结果是69年。3、中间10位，表示机器数，也就是2的10次方台机器，但是在一般情况下，都用不了这么多的机器。所以这十个位置可以根据需求自己拟定。4、最后的12位，相当于一个自增排序，可以表示2的12次方的数据也就是4096个数据。
　　通过这样的划分之后，相当于在一个毫秒之内一个服务器上可以产生4096个不重复的ID值。其量级也是非常可观的。
　　从雪花算法的实现思想上来看，其ID呈现出一个递增的趋势，并且不依赖第三方的数据库，第三方的服务系统，我们可以将其以工具类，或者是以JavaBean的方式注入到容器中，使用非常方便，而且在生成ID方面也是比较高效的，同样也可以结合业务来对Bit位进行合理的分配从而生成出符合业务逻辑的全局唯一ID。
　　这里有读者会问了？
　　在中间的位置中我们引入了时间戳，那么我们如何避免时钟回拨的问题呢？也就是说如果时钟回拨了，就会导致以前恰巧生成的ID再次出现，也会出现重复ID的情况，那么我们如何去解决这个问题呢？下面是我来实现的一个雪花算法ID生成器ClassnameSnowflakeIdUtilsDescriptionTODO雪花算法ID生成器Date20208142：29PMCreatedbynihuiVersion1。0ComponentpublicclassSnowflakeIdUtils｛Fields开始时间截（20150101）privatefinallongtwepoch1420041600000L；机器id所占的位数privatefinallongworkerIdBits5L；数据标识id所占的位数privatefinallongdatacenterIdBits5L；支持的最大机器id，结果是31（这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数）privatefinallongmaxWorkerId1L（1LworkerIdBits）；支持的最大数据标识id，结果是31privatefinallongmaxDatacenterId1L（1LdatacenterIdBits）；序列在id中占的位数privatefinallongsequenceBits12L；机器ID向左移12位privatefinallongworkerIdShiftsequenceBits；数据标识id向左移17位（125）privatefinallongdatacenterIdShiftsequenceBitsworkerIdBits；时间截向左移22位（5512）privatefinallongtimestampLeftShiftsequenceBitsworkerIdBitsdatacenterIdBits；生成序列的掩码，这里为4095（0b1111111111110xfff4095）privatefinallongsequenceMask1L（1LsequenceBits）；工作机器ID（031）privatelongworkerId；数据中心ID（031）privatelongdatacenterId；毫秒内序列（04095）privatelongsequence0L；上次生成ID的时间截privatelonglastTimestamp1L；Constructors构造函数paramworkerId工作ID（031）paramdatacenterId数据中心ID（031）publicSnowflakeIdUtils（longworkerId，longdatacenterId）｛if（workerIdmaxWorkerIdworkerId0）｛thrownewIllegalArgumentException（String。format（workerIdcantbegreaterthandorlessthan0，maxWorkerId））；｝if（datacenterIdmaxDatacenterIddatacenterId0）｛thrownewIllegalArgumentException（String。format（datacenterIdcantbegreaterthandorlessthan0，maxDatacenterId））；｝this。workerIdworkerId；this。datacenterIddatacenterId；｝publicSnowflakeIdUtils（）｛this（1，1）；｝publicsynchronizedStringstringId（）｛returnString。valueOf（this。nextId（））；｝Methods获得下一个ID（该方法是线程安全的）returnSnowflakeIdpublicsynchronizedlongnextId（）｛longtimestamptimeGen（）；如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常if（timestamplastTimestamp）｛thrownewRuntimeException（String。format（Clockmovedbackwards。Refusingtogenerateidfordmilliseconds，lastTimestamptimestamp））；｝如果是同一时间生成的，则进行毫秒内序列if（lastTimestamptimestamp）｛sequence（sequence1）sequenceMask；毫秒内序列溢出if（sequence0）｛阻塞到下一个毫秒，获得新的时间戳timestamptilNextMillis（lastTimestamp）；｝｝时间戳改变，毫秒内序列重置else｛sequence0L；｝上次生成ID的时间截lastTimestamptimestamp；移位并通过或运算拼到一起组成64位的IDreturn（（timestamptwepoch）timestampLeftShift）（datacenterIddatacenterIdShift）（workerIdworkerIdShift）sequence；｝阻塞到下一个毫秒，直到获得新的时间戳paramlastTimestamp上次生成ID的时间截return当前时间戳protectedlongtilNextMillis（longlastTimestamp）｛longtimestamptimeGen（）；while（timestamplastTimestamp）｛timestamptimeGen（）；｝returntimestamp；｝返回以毫秒为单位的当前时间return当前时间（毫秒）protectedlongtimeGen（）｛returnSystem。currentTimeMillis（）；｝Test测试publicstaticvoidmain（String〔〕args）｛SnowflakeIdUtilsidWorkernewSnowflakeIdUtils（3，1）；System。out。println（idWorker。nextId（））；｝｝总结
　　由于官方也没有对时间回拨的情况给出明确的答案，这里笔者的处理结果就是将其以异常的方式进行抛出，后来也有很多的分布式ID算法都是基于雪花算法的思想进行升级，而且避免了雪花算法带来的各种缺陷。例如百度的UidGrnerator、美团的Leaf都是在雪花算法的基础上演变出来的。