当前位置：首页 > news >正文

分布式ID之雪花算法

news 2026/3/26 22:31:00

分布式ID

分布式ID：distributed id，在分布式系统中生成的全局唯一标识符。

使用场景：订单号、分库分表环境下的数据库主键等

分布式ID常见的实现方式：

UUID：例如，UUID.randomUUID().toString()，优点是本地生成，无网络开销，缺点是生成的id太大，导致存储空间大，查询效率低，不适合作为数据库主键
号段模式：每次获取一个号段，然后在内存中分配这个号段，分配完成后再次从数据库中获取。优点是可以减少数据库的访问
雪花算法：snow flake algorithm，由推特开源的分布式ID生成算法，生成一个64位的ID，它的结构是 1位符号位 + 41位时间戳 + 10位机器ID + 12位序列号。它的优点是本地生成、性能高、趋势递增，缺点是依赖机器时钟，如果时钟回拨，可能会生成重复的ID
基于redis的原子操作：基于redis提供的操作，incr、incrby，来生成分布式id，优点是性能较好，id可以保证全局递增，缺点是每次生成都依赖redis

在实际生产中，雪花算法估计是使用最多的，虽然它依赖机器时钟，但生产环境下通常不会出现时钟不准、时钟回拨等情况，推荐使用ntp服务来维护机器时间

雪花算法

雪花算法的原理：

1、雪花算法使用41比特位来存储时间戳，使用如下案例来计算，41比特位可以存储的时间戳，在约80年左右后才会满

@Testpublicvoidtest1(){longlimit=(1L<<42)-1;longsub=limit-System.currentTimeMillis();// 当前2025年System.out.println("支持"+(sub/1000/60/60/24/365)+"年");// 83}

2、雪花算法使用10比特位来存储机器id，这支持1024个机器id，通常，单个服务最多不会部署超过100台机器，尤其是在分布式、微服务的背景下，所以1024个机器预计完全够用。

3、雪花算法使用12比特位序列号，也就是说，1毫秒内，支持生成4096个序列号，在单台机器上，预计完全够用。

雪花算法的实现

/** * 使用雪花算法生成分布式id，线程安全 */publicclassSnowFlakeIdGeneratorimplementsIdGenerator{/** * 时间戳的位数，二进制的 */privatestaticfinalintTS_BIT_SIZE=41;/** * 机器id的位数 */privatestaticfinalintWORKER_BIT_SIZE=10;/** * 序列号的位数 */privatestaticfinalintSEQUENCE_BIT_SIZE=12;/** * workId的最大值 */privatestaticfinallongMAX_WORK_ID=(1L<<WORKER_BIT_SIZE)-1;/** * 序列号的最大值 */privatestaticfinalintMAX_SEQUENCE_ID=(1<<SEQUENCE_BIT_SIZE)-1;/** * 基础时间，用于减少分布式ID的大小 */privatestaticfinallongBASE_TIME=getBaseTime();/** * 机器id */privatefinallongworkId;/** * 序列号，在同一毫秒内递增 */privateintsequence;/** * 上一次生成分布式ID时的时间戳 */privatelonglastTime;privatefinalReentrantLockLOCK=newReentrantLock();/* 提供两个构造方法，1个使用默认方式获取workId，一个由外部传入workId */publicSnowFlakeIdGenerator(){workId=defaultWorkId();}publicSnowFlakeIdGenerator(LongworkId){if(workId==null||workId<0||workId>MAX_WORK_ID){thrownewRuntimeException("workId不符合规范");}this.workId=workId;}@OverridepubliclonggenerateId(){LOCK.lock();try{longtime=System.currentTimeMillis();if(time<lastTime){thrownewRuntimeException("发生时钟回拨");}if(lastTime==time){if(sequence==MAX_SEQUENCE_ID){time=waitNextTime(time);lastTime=time;sequence=0;}else{sequence++;}}else{lastTime=time;sequence=0;}return((time-BASE_TIME)<<(SEQUENCE_BIT_SIZE+WORKER_BIT_SIZE))|(workId<<SEQUENCE_BIT_SIZE)|sequence;}finally{LOCK.unlock();}}privatelongwaitNextTime(finallongtime){longt=System.currentTimeMillis();while(t<=time){t=System.currentTimeMillis();}returnt;}/** * 根据IP地址，获取默认的workId */privateLongdefaultWorkId(){// 根据ip地址生成一个workIdtry{Stringaddress=getLocalIp();longcurrentPid=getCurrentPid();return(address.hashCode()+currentPid)*31%(MAX_WORK_ID+1);}catch(UnknownHostExceptione){e.printStackTrace();thrownewRuntimeException("机器ID生成失败");}}/** * 获取本机的IP地址 */privateStringgetLocalIp()throwsUnknownHostException{returnInetAddress.getLocalHost().getHostAddress();}/** * 获取当前进程ID * @return 当前进程ID，获取失败返回-1 */privatelonggetCurrentPid(){try{StringruntimeName=ManagementFactory.getRuntimeMXBean().getName();if(runtimeName==null||!runtimeName.contains("@")){return-1;}returnLong.parseLong(runtimeName.split("@")[0]);}catch(Exceptione){// 捕获解析失败/空指针等异常System.err.println("获取PID失败："+e.getMessage());return-1;}}privatestaticlonggetBaseTime(){finalStringS="2016-01-01 00:00:00";SimpleDateFormatformatter=newSimpleDateFormat("yyyy-MM-dd HH:mm:ss");Datedate;try{date=formatter.parse(S);}catch(ParseExceptione){e.printStackTrace();thrownewRuntimeException("解析基础时间失败");}returndate.getTime();}/** * 解析ID获取详细信息（调试用） */publicDataparseId(longid){longtimestamp=(id>>(SEQUENCE_BIT_SIZE+WORKER_BIT_SIZE))+BASE_TIME;longworkerId=(id>>SEQUENCE_BIT_SIZE)&MAX_WORK_ID;longsequence=id&MAX_SEQUENCE_ID;returnnewData(timestamp,workerId,sequence);}publicstaticclassData{publiclongtimestamp;publiclongworkerId;publiclongsequence;publicData(longtimestamp,longworkerId,longsequence){this.timestamp=timestamp;this.workerId=workerId;this.sequence=sequence;}}}

测试：

publicclassSnowFlakeIdGeneratorTest{/** * 测试，验证生成的序列化id，后一个一定大于前一个。单线程 */@Testpublicvoidtest1(){IdGeneratoridGenerator=newSnowFlakeIdGenerator();longlastId=0;for(inti=0;i<300000;i++){longid=idGenerator.generateId();if(id<=lastId){System.out.println(lastId+" "+id);thrownewRuntimeException("id重复");}lastId=id;}}/** * 测试，验证生成的序列化id，后一个一定大于前一个。多线程 */@Testpublicvoidtest2(){IdGeneratoridGenerator=newSnowFlakeIdGenerator(10L);List<List<Long>>lists=newArrayList<>();for(inti=0;i<10;i++){lists.add(newArrayList<>());}List<Thread>threadList=newArrayList<>();for(inti=0;i<10;i++){intfinalI=i;threadList.add(newThread(()->{List<Long>list=lists.get(finalI);longlastId=0;for(intj=0;j<30000;j++){longid=idGenerator.generateId();list.add(id);if(id<=lastId){System.out.println(lastId+" "+id);thrownewRuntimeException("id重复");}lastId=id;}}));}for(Threadthread:threadList){thread.start();}for(Threadthread:threadList){try{thread.join();}catch(InterruptedExceptione){thrownewRuntimeException(e);}}SimpleDateFormatformatter=newSimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");Set<Long>set=newHashSet<>();for(List<Long>list:lists){for(Longid:list){if(set.contains(id)){thrownewRuntimeException("重复id");}else{set.add(id);}}}ArrayList<Long>list=newArrayList<>(set);list.sort(Long::compareTo);inti=0;for(Longl:list){SnowFlakeIdGeneratorsnowFlakeIdGenerator=newSnowFlakeIdGenerator();SnowFlakeIdGenerator.Datadata=snowFlakeIdGenerator.parseId(l);System.out.println(l+" "+"data.timestamp = "+data.timestamp+" "+formatter.format(newDate(data.timestamp))+" "+"data.workerId = "+data.workerId+" "+"data.sequence = "+data.sequence);i++;if(i==20000){break;}}}@Testpublicvoidtest3(){System.out.println(Long.MAX_VALUE);}}

性能测试：

@State(Scope.Benchmark)@BenchmarkMode(Mode.Throughput)// 测试吞吐量@OutputTimeUnit(TimeUnit.SECONDS)@Warmup(iterations=3,time=1)// 预热3轮，每轮1秒@Measurement(iterations=5,time=2)// 测试5轮，每轮2秒@Threads(100)// 100个线程并发@Fork(1)publicclassSnowflakeJMHTest{privateIdGeneratoridGenerator;privateConcurrentHashMap<Long,Boolean>idSet;privateAtomicLongduplicateCount;@Setuppublicvoidsetup(){idGenerator=newSnowFlakeIdGenerator(10L);idSet=newConcurrentHashMap<>();duplicateCount=newAtomicLong(0);}@BenchmarkpublicvoidtestConcurrentGeneration(){longid=idGenerator.generateId();// 检查重复Booleanexisted=idSet.putIfAbsent(id,Boolean.TRUE);if(existed!=null){duplicateCount.incrementAndGet();}}@TearDownpublicvoidtearDown(){longduplicates=duplicateCount.get();if(duplicates>0){System.err.println("警告：发现 "+duplicates+" 个重复ID！");}}publicstaticvoidmain(String[]args)throwsRunnerException{Optionsopt=newOptionsBuilder().include(SnowflakeJMHTest.class.getSimpleName()).build();newRunner(opt).run();}}

测试结果：

Benchmark Mode Cnt Score Error Units SnowflakeJMHTest.testConcurrentGeneration sample 12648265 3859.767 ± 69.740 ns/op SnowflakeJMHTest.testConcurrentGeneration:p0.00 sample ≈ 0 ns/op SnowflakeJMHTest.testConcurrentGeneration:p0.50 sample ≈ 0 ns/op SnowflakeJMHTest.testConcurrentGeneration:p0.90 sample 100.000 ns/op SnowflakeJMHTest.testConcurrentGeneration:p0.95 sample 100.000 ns/op SnowflakeJMHTest.testConcurrentGeneration:p0.99 sample 1200.000 ns/op SnowflakeJMHTest.testConcurrentGeneration:p0.999 sample 971776.000 ns/op SnowflakeJMHTest.testConcurrentGeneration:p0.9999 sample 2025472.000 ns/op SnowflakeJMHTest.testConcurrentGeneration:p1.00 sample 30212096.000 ns/op

性能统计分析，最快的，0秒就可以返回，最慢的，要30毫秒，TP99在9微妙左右。

雪花算法相关问题

时钟回拨问题

时钟回拨：系统时间向后跳变，例如NTP服务同步时间，或者手动设置时间。据统计，在使用ntp服务的情况下，物理服务器大约每月会发生0到3次轻微时钟回拨，回拨范围在100ms以内。（来自deepseek的数据）

如何处理时钟回拨：这里的方案是抛异常，业界成熟的方案：轻微时钟回拨，通常是200毫秒以内，等待，其它程度的时间回拨，抛异常。

workId重复问题

当前代码中，使用IP地址的哈希值 + 进程号，然后和1024取模，来生成workId，有小概率情况下，会发生哈希冲突，想要避免这种情况，可以使用redis，来为当前进程分配一个唯一id，这个id记录在redis中，不过这种方式存在回收id比较困难的情况，可以写一个扫描程序，检测指定服务器上是否有该进程id，如果没有，回收workId。

查看全文

http://www.jsqmd.com/news/145084/