美团的Leaf以及滴滴的TinyId等
发布时间：2025-06-24 18:00:34 作者：北方职教升学中心 阅读量：870
雪花算法提供了高度的灵活性，允许根据实际需求自定义各个组成部分的bit位数，若需提升QPS（每秒查询率），可适当增加序列号所占的bit位数。美团的Leaf以及滴滴的TinyId等。
这样，外部系统可以直接从缓存中获取ID，而无需等待ID的生成过程，从而大大提高了性能。41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br> * 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId<br> * 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号<br> * 加起来刚好64位，为一个Long型。该时间戳用于与twepoch（一个预设的常量值，表示时间起点）相减，从而得到一个相对时间差，这个相对时间差与序列号结合使用，通过allocate()方法生成最终的唯一ID。
3、序列号）移到对应位置，然后相加，如下：
longid =(deltaTime <<TIMESTAMP_LEFT_SHIFT)|(this.dataCenterId <<DATA_CENTER_ID_SHIFT)|(this.workerId <<WORKER_ID_SHIFT)|this.sequence;- deltaTime向左移22位（IDC-bit+机器bit+序列号bit）。
Java代码实现snowflake
1、考虑时间戳回拨
/** * Twitter_Snowflake<br> * SnowFlake的结构如下(每部分用-分开):<br> * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br> * 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0<br> * 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截) * 得到的值），这里的的开始时间截，一般是的id生成器开始使用的时间，由程序来指定的（如下下面程序IdWorker类的startTime属性）。同时，由于时间戳的自增是由程序自己控制的，因此可以充分利用未来时间，预先生成一些ID并存储在缓存中。清除或翻转二进制位。*常见的方法包括使时间戳自增以摆脱对机器时钟的依赖、
2、利用缓存来存储序列号，或等待时钟自行校正等。通过每次获取一个号段的值，可以大大减少与数据库的交互次数，从而显著降低数据库的压力。
snowflake优缺点
优点：
- 毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。尽管雪花算法具有诸多优点，但它对机器时钟的强依赖性也带来了时钟回拨问题，为应对这一问题，开发者们提出了多种解决方案，主要分为避免和缓解两大类。
*然而，这种方法也存在一个明显的缺点，即生成的ID中的时间戳并不是真实的时间。41位的时间戳、机器和序列号：
publiclonggetSequence(longid){returnid &~(-1L<<SEQUENCE_BITS);}publiclonggetWorkerId(longid){returnid >>WORKER_ID_SHIFT&~(-1L<<WORKER_ID_BITS);}publiclonggetDataCenterId(longid){returnid >>DATA_CENTER_ID_SHIFT&~(-1L<<DATA_CENTER_ID_BITS);}publiclonggetGenerateDateTime(longid){return(id >>TIMESTAMP_LEFT_SHIFT&~(-1L<<41L))+twepoch;}
因为sequence本身就在低位，所以不需要移动，其他机器和时间都是需要将id向右移动，使得自己的有效位置在低位，至于和自己的最大值做&运算，是为了让不属于自己bit的位置无效，即都转为0。此外，如果流量不大，可以考虑缓存前几百毫秒或几秒的序列号。
比如回拨时长小于500ms，那就睡眠500ms，等时间恢复到正常，如果这个过程中又发生了时钟回拨，不可能一直等它校正，实际生产中可限定校正的次数，超过最大校正次数，那就抛异常吧，这属于极端情况。
运算符<<
运算符“<<”表示左移运算，也被称为位移左移运算符或左移位运算符。
- 极端情况下，获取很多次缓存sequence+1都超过了最大值，就会一直循环获取，这样可能会影响性能，所以实际生产中可以限定重新获取次数。逻辑实现流程
组装生成id
生成id的过程，就是把每一种标识（时间、在每次生成ID时，sequence会自增，并通过与SEQUENCE_MASK进行位与操作来确保其在有效范围内循环。以下是两种可能的解决思路：
1、
除了整数类型，按位异或运算符也可以应用于布尔类型。出现时钟回拨问题，如果回拨幅度不大，等待时钟自己校正
if(timestamp <lastTimestamp){intsleepCntMax =2;intsleepCnt =0;do{longsleepTime =lastTimestamp -timestamp;if(sleepCnt >sleepCntMax){// 可自定义异常类thrownewUnsupportedOperationException(String.format("Clock moved backwards. Refusing for %d seconds",sleepTime));}if(sleepTime <=500){try{Thread.sleep(sleepTime);}catch(InterruptedExceptione){e.printStackTrace();}finally{sleepCnt++;timestamp =tilNextMillis(lastTimestamp);}}else{// 可自定义异常类thrownewUnsupportedOperationException(String.format("Clock moved backwards. Refusing for %d seconds",sleepTime));}}while(timestamp <lastTimestamp);}// 2、因此，需要探索有效的解决方案来最小化时钟回拨带来的影响。当时钟回拨发生时，可以从缓存中获取并自增序列号，从而有效地应对时钟回拨问题。但是，为了确保生成的ID具有全局唯一性，需要依赖机器ID来进行区分。3、
雪花算法snowflake
snowflake定义
Snowflake算法的原理相对直观，它负责生成一个64位（long型）的全局唯一ID，这个ID的构成包括：1位无用的符号位、*如果系统的流量较小，那么时间戳可能会滞后很多。
按位异或运算符“^”通常用于处理整数的位级操作，当对两个整数进行异或运算时，它们的每一个二进制位都会根据异或规则进行运算，生成一个新的整数作为结果。
由于各种潜在因素，机器的本地时钟可能会变得不准确。 */publicclassSnowflakeIdWorkerV1{// ==============================Fields===========================================/** 开始时间截 (2015-01-01) */privatefinallongtwepoch =1420041600000L;/** 机器id所占的位数 */privatefinallongworkerIdBits =5L;/** 数据标识id所占的位数 */privatefinallongdatacenterIdBits =5L;/** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */privatefinallongmaxWorkerId =-1L^(-1L<<workerIdBits);/** 支持的最大数据标识id，结果是31 */privatefinallongmaxDatacenterId =-1L^(-1L<<datacenterIdBits);/** 序列在id中占的位数 */privatefinallongsequenceBits =12L;/** 机器ID向左移12位 */privatefinallongworkerIdShift =sequenceBits;/** 数据标识id向左移17位(12+5) */privatefinallongdatacenterIdShift =sequenceBits +workerIdBits;/** 时间截向左移22位(5+5+12) */privatefinallongtimestampLeftShift =sequenceBits +workerIdBits +datacenterIdBits;/** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */privatefinallongsequenceMask =-1L^(-1L<<sequenceBits);/** 工作机器ID(0~31) */privatelongworkerId;/** 数据中心ID(0~31) */privatelongdatacenterId;/** 毫秒内序列(0~4095) */privatelongsequence =0L;/** 上次生成ID的时间截 */privatelonglastTimestamp =-1L;//==============================Constructors=====================================/** * 构造函数 * @param workerId 工作ID (0~31) * @param datacenterId 数据中心ID (0~31) */publicSnowflakeIdWorkerV1(longworkerId,longdatacenterId){if(workerId >maxWorkerId ||workerId <0){thrownewIllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0",maxWorkerId));}if(datacenterId >maxDatacenterId ||datacenterId <0){thrownewIllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0",maxDatacenterId));}this.workerId =workerId;this.datacenterId =datacenterId;}// ==============================Methods==========================================/** * 获得下一个ID (该方法是线程安全的) * @return SnowflakeId */publicsynchronizedlongnextId(){longtimestamp =timeGen();//如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常if(timestamp <lastTimestamp){thrownewRuntimeException(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位的IDreturn((timestamp -twepoch)<<timestampLeftShift)//|(datacenterId <<datacenterIdShift)//|(workerId <<workerIdShift)//|sequence;}/** * 阻塞到下一个毫秒，直到获得新的时间戳 * @param lastTimestamp 上次生成ID的时间截 * @return 当前时间戳 */protectedlongtilNextMillis(longlastTimestamp){longtimestamp =timeGen();while(timestamp <=lastTimestamp){timestamp =timeGen();}returntimestamp;}/** * 返回以毫秒为单位的当前时间 * @return 当前时间(毫秒) */protectedlongtimeGen(){returnSystem.currentTimeMillis();}//==============================Test=============================================/** 测试 */publicstaticvoidmain(String[]args){SnowflakeIdWorkerV1idWorker =newSnowflakeIdWorkerV1(0,0);for(inti =0;i <1000;i++){longid =idWorker.nextId();System.out.println(Long.toBinaryString(id));System.out.println(id);}}} 2、 因此，如果对从ID中解析出来的时间戳有特定的利用需求（例如用于记录事件发生的时间），那么这个缺点可能会成为问题。MySQL官方建议主键应尽可能短，而对于InnoDB引擎来说，索引的无序性可能会导致数据位置频繁变动，从而严重影响性能。
雪花算法由于其强烈依赖于机器时钟，因此难以避免受到时钟回拨的影响，这可能导致生成重复的ID。<br> * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。
时间戳自增彻底解决时钟回拨问题
privatelongsequence =-1L;privatelongstartTimestamp =1623947387000L;privatesynchronizedlongnextId2(){longsequenceTmp =sequence;sequence =(sequence +1)&SEQUENCE_MASK;// sequence =0 有可能是初始+1=0，也可能是超过了最大值等于0// 所以把 初始+1=0排除掉if(sequence ==0&&sequenceTmp >=0){// sequence自增到最大了，时间戳自增1startTimestamp +=1;}// 生成idreturnallocate(startTimestamp -twepoch);}这段Java代码定义了一个用于生成唯一ID的方法nextId2()，该方法不依赖于机器时钟，从而彻底解决了时钟回拨问题。例如，如果你有一个整数8（在二进制中表示为1000），将其左移两位，结果将是32（在二进制中表示为100000），这是因为8乘以2的2次方等于32。41位的时间截，可以使用69年，年T = * (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br> * 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId<br> * 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号<br> * 加起来刚好64位，为一个Long型。
但是，由于ID的获取涉及到远程请求，因此会受到网络波动的影响，其性能自然无法与直接从本地生成相比，同时，发号器服务的稳定性至关重要，一旦服务出现故障，将影响到许多依赖其的外部服务。0000000000001001110100000110100110111010100111101010001000001和11111做&运算得到1（左边都是0可以省掉）。<br> * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。不考虑时间戳回拨
/** * Twitter_Snowflake<br> * SnowFlake的结构如下(每部分用-分开):<br> * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br> * 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0<br> * 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截) * 得到的值），这里的的开始时间截，一般是的id生成器开始使用的时间，由程序来指定的（如下下面程序IdWorker类的startTime属性）。美团的Leaf和滴滴的TinyId就是采用这种算法的典型例子。然而，这种处理方式在实际生产环境中是不可接受的。
2、
2、
3、
inta =15;// 二进制表示为 0000 1111 intb =8;// 二进制表示为 0000 1000 intc =a ^b;// 进行按位异或运算 System.out.println("Result: "+c);// 输出结果为 7（二进制表示为 0000 0111）
在这个示例中，整数a和b的二进制表示分别为0000 1111和0000 1000，对它们进行按位异或运算后，得到的结果为0000 0111，即十进制数7。10位机器ID：可以唯一标识最多1024台机器，如果需要对互联网数据中心（IDC）进行划分，可以将这10位拆分为两部分，例如各5位，这样，系统就能够表示最多32个IDC，且每个IDC下可以容纳32台机器。
尽管可以通过部署数据库集群来提高可用性，但问题并未从根本上解决。
4、
thrownewUnsupportedOperationException("The timeback range is too large and exceeds 2000ms caches");}longpreSequence =sequenceCycle[index];sequence =(preSequence +1)&SEQUENCE_MASK;if(sequence ==0){// 如果取出的历史序列号+1后已经达到超过最大值，// 则重新获取timestamp,重新拿其他位置的缓存timestamp =tilNextMillis(lastTimestamp);index =(int)(timestamp %LENGTH);}else{// 更新缓存sequenceCycle[index]=this.sequence;returnallocate((timestamp -this.twepoch),sequence);}}while(timestamp <lastTimestamp);// 如果在获取缓存的过程中timestamp恢复正常了，就走正常流程}// 2、2、本地生成方案
在此方案中，ID是在本地直接生成的，因此不存在网络延迟问题，性能极高。雪花算法以其简单高效而著称，其核心在于结合时间戳、然而，由于它强烈依赖于机器时钟，因此需要考虑时钟回拨问题。
- 若获取的历史sequence+1之后超过了最大值，则重新获取时间戳，重新获取缓存sequence。
小结
解决时钟回拨问题的方法还有很多，无非就是避免和缓解。UDDI之间的关系
Spring揭秘：@import注解应用场景及实现原理！
Java并发基础：原子类之AtomicMarkableReference全面解析！
Java并发基础：concurrent Flow API全面解析
Java并发基础：CopyOnWriteArraySet全面解析
