Snowflake id生成器

骑猪看日落 2022-05-29 09:39 377阅读 0赞

最下面代码是mybatisplus根据 [李景枫][Link 1] 的开源稍改写的id生成器，核心算法就： Snowflake算法

![这里写图片描述][Image 1]

### Snowflake算法核心 ###

把时间戳，工作机器id，序列号组合在一起。

### Snowflake算法核心 ###

除了最高位bit标记为不可用以外，其余三组bit占位均可浮动，看具体的业务需求而定。默认情况下41bit的时间戳可以支持该算法使用到2082年，10bit的工作机器id可以支持1023台机器，序列号支持1毫秒产生4095个自增序列id。下文会具体分析。

### Snowflake – 时间戳 ###

这里时间戳的细度是毫秒级，具体代码如下，建议使用64位linux系统机器，因为有vdso，gettimeofday()在用户态就可以完成操作，减少了进入内核态的损耗。

### Snowflake – 工作机器id ###

严格意义上来说这个bit段的使用可以是进程级，机器级的话你可以使用MAC地址来唯一标示工作机器，工作进程级可以使用IP+Path来区分工作进程。如果工作机器比较少，可以使用配置文件来设置这个id是一个不错的选择，如果机器过多配置文件的维护是一个灾难性的事情。

### Snowflake – 序列号 ###

序列号就是一系列的自增id（多线程建议使用atomic），为了处理在同一毫秒内需要给多条消息分配id，若同一毫秒把序列号用完了，则“等待至下一毫秒”。

### datacenterId是获取的机器网卡然后计算 ###

id = ((0x000000FF & (long) mac[mac.length - 1]) | (0x0000FF00 & (((long) mac[mac.length - 2]) << 8))) >> 6;
 id = id % (maxDatacenterId + 1);

### getMaxWorkerId ###

StringBuilder mpid = new StringBuilder();
            mpid.append(datacenterId);
            String name = ManagementFactory.getRuntimeMXBean().getName();
            if (StringUtils.isNotEmpty(name)) {
                /* * GET jvmPid */
                mpid.append(name.split("@")[0]);
            }
            /* * MAC + PID 的 hashcode 获取16个低位 */
            return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);

### 具体算法代码 ###

/** * Copy * right (c) 2011-2020, hubin (jobob@qq.com). * * Licensed under the Apache License, Version 2.0 (the "License"); you may not * use this file except in compliance with the License. You may obtain a copy of * the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the * License for the specific language governing permissions and limitations under * the License. */
 package com.baomidou.mybatisplus.toolkit;
 
 import java.lang.management.ManagementFactory;
 import java.net.InetAddress;
 import java.net.NetworkInterface;
 import java.util.concurrent.ThreadLocalRandom;
 
 import org.apache.ibatis.logging.Log;
 import org.apache.ibatis.logging.LogFactory;
 
 
 /** * * 分布式高效有序ID生产黑科技(sequence) * 优化开源项目：http://git.oschina.net/yu120/sequence * * * @author hubin * @date 2016-08-18 */
 public class Sequence { 
 
 private static final Log logger = LogFactory.getLog(Sequence.class);
 
 /* 时间起始标记点，作为基准，一般取系统的最近时间（一旦确定不能变动） */
 private final long twepoch = 1288834974657L;
 private final long workerIdBits = 5L;/* 机器标识位数 */
 private final long datacenterIdBits = 5L;
 private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
 private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
 private final long sequenceBits = 12L;/* 毫秒内自增位 */
 private final long workerIdShift = sequenceBits;
 private final long datacenterIdShift = sequenceBits + workerIdBits;
 /* 时间戳左移动位 */
 private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
 private final long sequenceMask = -1L ^ (-1L << sequenceBits);
 
 private long workerId;
 
 /* 数据标识id部分 */
 private long datacenterId;
 private long sequence = 0L;/* 0，并发控制 */
 private long lastTimestamp = -1L;/* 上次生产id时间戳 */
 
 public Sequence() {
 this.datacenterId = getDatacenterId(maxDatacenterId);
 this.workerId = getMaxWorkerId(datacenterId, maxWorkerId);
 }
 
 /** * @param workerId 工作机器ID * @param datacenterId 序列号 */
 public Sequence(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;
 }
 
 /** * * 获取 maxWorkerId * */
 protected static long getMaxWorkerId(long datacenterId, long maxWorkerId) {
 StringBuilder mpid = new StringBuilder();
 mpid.append(datacenterId);
 String name = ManagementFactory.getRuntimeMXBean().getName();
 if (StringUtils.isNotEmpty(name)) {
 /* * GET jvmPid */
 mpid.append(name.split("@")[0]);
 }
 /* * MAC + PID 的 hashcode 获取16个低位 */
 return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);
 }
 
 /** * * 数据标识id部分 * */
 protected static long getDatacenterId(long maxDatacenterId) {
 long id = 0L;
 try {
 InetAddress ip = InetAddress.getLocalHost();
 NetworkInterface network = NetworkInterface.getByInetAddress(ip);
 if (network == null) {
 id = 1L;
 } else {
 byte[] mac = network.getHardwareAddress();
 if (null != mac) {
 id = ((0x000000FF & (long) mac[mac.length - 1]) | (0x0000FF00 & (((long) mac[mac.length - 2]) << 8))) >> 6;
 id = id % (maxDatacenterId + 1);
 }
 }
 } catch (Exception e) {
 logger.warn(" getDatacenterId: " + e.getMessage());
 }
 return id;
 }
 
 /** * 获取下一个ID * * @return */
 public synchronized long nextId() {
 long timestamp = timeGen();
 if (timestamp < lastTimestamp) {
 //闰秒
 long offset = lastTimestamp - timestamp;
 if (offset <= 5) {
 try {
 wait(offset << 1);
 timestamp = timeGen();
 if (timestamp < lastTimestamp) {
 throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", offset));
 }
 } catch (Exception e) {
 throw new RuntimeException(e);
 }
 } else {
 throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", offset));
 }
 }
 
 if (lastTimestamp == timestamp) {
 // 相同毫秒内，序列号自增
 sequence = (sequence + 1) & sequenceMask;
 if (sequence == 0) {
 // 同一毫秒的序列数已经达到最大
 timestamp = tilNextMillis(lastTimestamp);
 }
 } else {
 // 不同毫秒内，序列号置为 1 - 3 随机数
 sequence = ThreadLocalRandom.current().nextLong(1, 3);
 }
 
 lastTimestamp = timestamp;
 
 return ((timestamp - twepoch) << timestampLeftShift) // 时间戳部分
 | (datacenterId << datacenterIdShift) // 数据中心部分
 | (workerId << workerIdShift) // 机器标识部分
 | sequence; // 序列号部分
 }
 
 protected long tilNextMillis(long lastTimestamp) {
 long timestamp = timeGen();
 while (timestamp <= lastTimestamp) {
 timestamp = timeGen();
 }
 return timestamp;
 }
 
 protected long timeGen() {
 return SystemClock.now();
 }
 
 }

/** * Copyright (c) 2011-2020, hubin (jobob@qq.com). * * Licensed under the Apache License, Version 2.0 (the "License"); you may not * use this file except in compliance with the License. You may obtain a copy of * the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the * License for the specific language governing permissions and limitations under * the License. */
 package com.baomidou.mybatisplus.toolkit;
 
 import java.sql.Timestamp;
 import java.util.concurrent.Executors;
 import java.util.concurrent.ScheduledExecutorService;
 import java.util.concurrent.ThreadFactory;
 import java.util.concurrent.TimeUnit;
 import java.util.concurrent.atomic.AtomicLong;
 
 /** * * 高并发场景下System.currentTimeMillis()的性能问题的优化 * * * System.currentTimeMillis()的调用比new一个普通对象要耗时的多（具体耗时高出多少我还没测试过，有人说是100倍左右） * System.currentTimeMillis()之所以慢是因为去跟系统打了一次交道 * 后台定时更新时钟，JVM退出时，线程自动回收 * 10亿：43410,206,210.72815533980582% * 1亿：4699,29,162.0344827586207% * 1000万：480,12,40.0% * 100万：50,10,5.0% * * * @author lry */
 public class SystemClock { 
 
 private final long period;
 private final AtomicLong now;
 
 private SystemClock(long period) {
 this.period = period;
 this.now = new AtomicLong(System.currentTimeMillis());
 scheduleClockUpdating();
 }
 
 private static SystemClock instance() {
 return InstanceHolder.INSTANCE;
 }
 
 public static long now() {
 return instance().currentTimeMillis();
 }
 
 public static String nowDate() {
 return new Timestamp(instance().currentTimeMillis()).toString();
 }
 
 private void scheduleClockUpdating() {
 ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor(new ThreadFactory() {
 
 @Override
 public Thread newThread(Runnable runnable) {
 Thread thread = new Thread(runnable, "System Clock");
 thread.setDaemon(true);
 return thread;
 }
 });
 scheduler.scheduleAtFixedRate(new Runnable() {
 
 @Override
 public void run() {
 now.set(System.currentTimeMillis());
 }
 }, period, period, TimeUnit.MILLISECONDS);
 }
 
 private long currentTimeMillis() {
 return now.get();
 }
 
 private static class InstanceHolder { 
 
 public static final SystemClock INSTANCE = new SystemClock(1);
 }
 
 }

[Link 1]: http://git.oschina.net/yu120/sequence
[Image 1]: