开源地址:https://gitee.com/yu120/sequence
欢迎关注个人公众号查看原文:

1 简介
基于Twitter的Snowflake算法(俗称雪花算法)实现64位自增ID算法。为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的ID,这些ID还需要一些大致的顺序(即时序性),并且在分布式系统中不同机器产生的ID必须不同。
2 标准Snowflake算法
Twitter的Snowflake算法数据划分如下:

Snowflake算法
信息说明:
SnowFlake优势:
3 Java实现代码
由于在Java中64bit的整数是Long类型,所以在Java中Snowflake算法生成的ID就是Long来存储的。以下是基于JAVA代码实现的标准Snowflake算法(https://gitee.com/yu120/sequence):
1/** 2 * 基于Twitter的Snowflake算法实现分布式高效有序ID生产黑科技(sequence) 3 * 4 * <br> 5 * SnowFlake的结构如下(每部分用-分开):<br> 6 * <br> 7 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br> 8 * <br> 9 * 1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0<br> 10 * <br> 11 * 41位时间截(毫秒级),注意,41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截 - 开始时间截) 12 * 得到的值),这里的的开始时间截,一般是我们的id生成器开始使用的时间,由我们程序来指定的(如下下面程序IdWorker类的startTime属性)。41位的时间截,可以使用69年,年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br> 13 * <br> 14 * 10位的数据机器位,可以部署在1024个节点,包括5位datacenterId和5位workerId<br> 15 * <br> 16 * 12位序列,毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号<br> 17 * <br> 18 * <br> 19 * 加起来刚好64位,为一个Long型。<br> 20 * SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分),并且效率较高,经测试,SnowFlake每秒能够产生26万ID左右。 21 * 22 * @author lry 23 */ 24public class Sequence { 25 26 /** 起始时间戳,用于用当前时间戳减去这个时间戳,算出偏移量 **/ 27 private final long startTime = 1519740777809L; 28 29 /** workerId占用的位数5(表示只允许workId的范围为:0-1023)**/ 30 private final long workerIdBits = 5L; 31 /** dataCenterId占用的位数:5 **/ 32 private final long dataCenterIdBits = 5L; 33 /** 序列号占用的位数:12(表示只允许workId的范围为:0-4095)**/ 34 private final long sequenceBits = 12L; 35 36 /** workerId可以使用的最大数值:31 **/ 37 private final long maxWorkerId = -1L ^ (-1L << workerIdBits); 38 /** dataCenterId可以使用的最大数值:31 **/ 39 private final long maxDataCenterId = -1L ^ (-1L << dataCenterIdBits); 40 41 private final long workerIdShift = sequenceBits; 42 private final long dataCenterIdShift = sequenceBits + workerIdBits; 43 private final long timestampLeftShift = sequenceBits + workerIdBits + dataCenterIdBits; 44 45 /** 用mask防止溢出:位与运算保证计算的结果范围始终是 0-4095 **/ 46 private final long sequenceMask = -1L ^ (-1L << sequenceBits); 47 48 private long workerId; 49 private long dataCenterId; 50 private long sequence = 0L; 51 private long lastTimestamp = -1L; 52 private boolean isClock = false; 53 54 /** 55 * 基于Snowflake创建分布式ID生成器 56 * <p> 57 * 注:sequence 58 * 59 * @param workerId 工作机器ID,数据范围为0~31 60 * @param dataCenterId 数据中心ID,数据范围为0~31 61 */ 62 public Sequence(long workerId, long dataCenterId) { 63 if (workerId > maxWorkerId || workerId < 0) { 64 throw new IllegalArgumentException(String.format("worker Id can\'t be greater than %d or less than 0", maxWorkerId)); 65 } 66 if (dataCenterId > maxDataCenterId || dataCenterId < 0) { 67 throw new IllegalArgumentException(String.format("dataCenter Id can\'t be greater than %d or less than 0", maxDataCenterId)); 68 } 69 70 this.workerId = workerId; 71 this.dataCenterId = dataCenterId; 72 } 73 74 public void setClock(boolean clock) { 75 isClock = clock; 76 } 77 78 /** 79 * 获取ID 80 * 81 * @return 82 */ 83 public synchronized Long nextId() { 84 long timestamp = this.timeGen(); 85 86 // 闰秒:如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过这个时候应当抛出异常 87 if (timestamp < lastTimestamp) { 88 long offset = lastTimestamp - timestamp; 89 if (offset <= 5) { 90 try { 91 this.wait(offset << 1); 92 timestamp = this.timeGen(); 93 if (timestamp < lastTimestamp) { 94 throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", offset)); 95 } 96 } catch (Exception e) { 97 throw new RuntimeException(e); 98 } 99 } else { 100 throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", offset)); 101 } 102 } 103 104 // 解决跨毫秒生成ID序列号始终为偶数的缺陷:如果是同一时间生成的,则进行毫秒内序列 105 if (lastTimestamp == timestamp) { 106 // 通过位与运算保证计算的结果范围始终是 0-4095 107 sequence = (sequence + 1) & sequenceMask; 108 if (sequence == 0) { 109 timestamp = this.tilNextMillis(lastTimestamp); 110 } 111 } else { 112 // 时间戳改变,毫秒内序列重置 113 sequence = 0L; 114 } 115 116 lastTimestamp = timestamp; 117 118 /* 119 * 1.左移运算是为了将数值移动到对应的段(41、5、5,12那段因为本来就在最右,因此不用左移) 120 * 2.然后对每个左移后的值(la、lb、lc、sequence)做位或运算,是为了把各个短的数据合并起来,合并成一个二进制数 121 * 3.最后转换成10进制,就是最终生成的id 122 */ 123 return ((timestamp - startTime) << timestampLeftShift) | 124 (dataCenterId << dataCenterIdShift) | 125 (workerId << workerIdShift) | 126 sequence; 127 } 128 129 /** 130 * 保证返回的毫秒数在参数之后(阻塞到下一个毫秒,直到获得新的时间戳) 131 * 132 * @param lastTimestamp 133 * @return 134 */ 135 private long tilNextMillis(long lastTimestamp) { 136 long timestamp = this.timeGen(); 137 while (timestamp <= lastTimestamp) { 138 timestamp = this.timeGen(); 139 } 140 141 return timestamp; 142 } 143 144 /** 145 * 获得系统当前毫秒数 146 * 147 * @return timestamp 148 */ 149 private long timeGen() { 150 if (isClock) { 151 // 解决高并发下获取时间戳的性能问题 152 return SystemClock.now(); 153 } else { 154 return System.currentTimeMillis(); 155 } 156 } 157 158}
以下是解决大并发场景中获取时间戳的性能问题:
1import java.sql.Timestamp; 2import java.util.concurrent.Executors; 3import java.util.concurrent.ScheduledExecutorService; 4import java.util.concurrent.ThreadFactory; 5import java.util.concurrent.TimeUnit; 6import java.util.concurrent.atomic.AtomicLong; 7 8/** 9 * 高并发场景下System.currentTimeMillis()的性能问题的优化 10 * <p><p> 11 * System.currentTimeMillis()的调用比new一个普通对象要耗时的多(具体耗时高出多少我还没测试过,有人说是100倍左右)<p> 12 * System.currentTimeMillis()之所以慢是因为去跟系统打了一次交道<p> 13 * 后台定时更新时钟,JVM退出时,线程自动回收<p> 14 * 10亿:43410,206,210.72815533980582%<p> 15 * 1亿:4699,29,162.0344827586207%<p> 16 * 1000万:480,12,40.0%<p> 17 * 100万:50,10,5.0%<p> 18 * @author lry 19 */ 20public class SystemClock { 21 22 private final long period; 23 private final AtomicLong now; 24 25 private SystemClock(long period) { 26 this.period = period; 27 this.now = new AtomicLong(System.currentTimeMillis()); 28 scheduleClockUpdating(); 29 } 30 31 private static class InstanceHolder { 32 public static final SystemClock INSTANCE = new SystemClock(1); 33 } 34 35 private static SystemClock instance() { 36 return InstanceHolder.INSTANCE; 37 } 38 39 private void scheduleClockUpdating() { 40 ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor(new ThreadFactory() { 41 public Thread newThread(Runnable runnable) { 42 Thread thread = new Thread(runnable, "System Clock"); 43 thread.setDaemon(true); 44 return thread; 45 } 46 }); 47 scheduler.scheduleAtFixedRate(new Runnable() { 48 public void run() { 49 now.set(System.currentTimeMillis()); 50 } 51 }, period, period, TimeUnit.MILLISECONDS); 52 } 53 54 private long currentTimeMillis() { 55 return now.get(); 56 } 57 58 public static long now() { 59 return instance().currentTimeMillis(); 60 } 61 62 public static String nowDate() { 63 return new Timestamp(instance().currentTimeMillis()).toString(); 64 } 65 66}
4 性能测试数据
性能测试数据结果发现,QPS>400w/s(Mac Pro 4C/8GB)

性能测试结果数据
5 缺点分析
5.1 时间回拨
产生原因
分布式环境,每台机器上的时钟不可能完全同步。由于机器时间不一致,需要同步各个服务器的时间而导致时间回拨的产生。
解决方案
-
在流量最低的时间段进行时间回拨,如半夜没有流量或流量很低时
-
每次批量获取一批ID(至少这批ID用完前,即可完成时间回拨)
-
调整ID存储的数据结构
-
回拨时间小于timeout时间,则通过自旋的方式进行生成
-
回拨时间大于timeout时间,则通过更换workid来生成(精度有所降低,如可从400w降低至100w,但也完全足够了)
5.2 大量偶数
产生原因
根据上述算法可知,在同一毫秒内是通过一个自增序列号进行区分不同ID,当时间跳至下一毫秒时,自增ID就会被重置为0。因此,如果线上的交易并发量不是很大时(即都是夸毫秒产生时),生成的所有ID的尾号基本都是0,即基本都是偶数。如果直接应用该ID来做分库分表,则极有可能出现数据不均匀的情况。
解决办法
6 Snowflake扩展
Snowflake算法并没有什么难度,其存放的数据区总长为64位,以上的数据区划分方式是Twitter给出的标准版,而算法是通用的。因此我们可以根据自己实际的需求,来制定属于我们自己的数据区(业界改造其数据存储结构的大牛也是不少的)。其次,以上算法生成的ID中存有一定是数据信息,因此我们可以解读这个ID来做更多的事,如获取出ID生成的时间、ID生成的数据中心、ID生成的机器ID等信息。