SnowFlake 雪花算法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 |
package com.hanson.test; import com.hanson.emums.SnowflakeConfigEnum; import com.hanson.SnowflakeIdWorker; import java.net.InetAddress; import java.net.UnknownHostException; /** * Description： * * 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属性）。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型。<br> * * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。 * <p> * Author: Hanson * Mail: huhanlin@huhanlin.com * Created on 2020/3/19 */ public class SnowFlakeId { private final long twepoch;//雪花算法的起始时间 private final long workId = (long)(255 & this.getLastIP()); private final long workIdBits = 8L;//workId的二进制位数,8位可以支持256 个节点 private final long maxWorkerId = -1L ^ (-1L << workIdBits);// 支持的最大机器id，结果是255(这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) private final long transactionBits;//事务键的二进制位数 默认是0不需要 private final long sequenceBits;//序列的二进制位数 默认是 14位 同一时刻 最大支持 16384 个 id生成 private final long transactionShift;//事务的向左位移 sequence 14 private final long workIdShift;//workId的向左位移 14 sequence 14 + transactionBits 0 private final long timestampLeftShift;//时间戳的向左位移22位 workId 8 + sequence 14 private final long sequenceMask;//序列的MAX掩码,防止溢出 这里是14位的最大值 -1L ^ (-1L << 14) 16383 private long sequence = 0L;//序列号 private long lastTimestamp = -1L;//上一次的时间戳 public static final String LEFT_PADDING = "0000000000000000"; public SnowFlakeId(SnowflakeConfigEnum snowflakeConfigEnum) { this.twepoch = snowflakeConfigEnum.getTwepoch(); this.transactionBits = snowflakeConfigEnum.getTransactionBits(); this.sequenceBits = snowflakeConfigEnum.getSequenceBits(); this.transactionShift = this.sequenceBits; this.workIdShift = this.sequenceBits + this.transactionBits; this.timestampLeftShift = this.sequenceBits + this.transactionBits + 8L; this.sequenceMask = ~(-1L << (int)this.sequenceBits); } public synchronized long nextId() { long timestamp = this.timeGen(); //发生时间回拨，抛出异常 if (timestamp < this.lastTimestamp) { throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", this.lastTimestamp - timestamp)); } else { //同一时间生成id，需要序列区分 if (this.lastTimestamp == timestamp) { //每次步进1,利用掩码防止溢出，证计算的结果范围始终是0 - sequenceMask this.sequence = this.sequence + 1L & this.sequenceMask; //溢出为0 ，同一毫秒的序列已经到最大值，只能等待下一毫秒 if (this.sequence == 0L) { timestamp = this.tilNextMillis(this.lastTimestamp); } } else { //已经不再同一毫秒内了，把序列重置为0 ，可能会导致id取模不均匀 this.sequence = 0L; // //跨毫秒时，序列号总是归0，会导致序列号为0的ID比较多，导致生成的ID取模后不均匀，所以采用10以内的随机数 // sequence = random.nextInt(10) & sequenceMask; } this.lastTimestamp = timestamp; //组合 （当前时间戳 - 起始时间 ）相对毫秒数 | workId |序列 为一个64位的ID return timestamp - this.twepoch << (int)this.timestampLeftShift | this.workId << (int)this.workIdShift | this.sequence; } } public synchronized long nextId(long transactionId) { if (this.transactionBits <= 0L) { throw new RuntimeException("The current snowflakeIdWorker does not have transactionBits . "); } else { String binaryId = Long.toBinaryString(transactionId); binaryId = "0000000000000000" + binaryId; long processId = Long.parseLong(binaryId.substring((int)((long)binaryId.length() - this.transactionBits)), 2); long timestamp = this.timeGen(); if (timestamp < this.lastTimestamp) { throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", this.lastTimestamp - timestamp)); } else { if (this.lastTimestamp == timestamp) { this.sequence = this.sequence + 1L & this.sequenceMask; if (this.sequence == 0L) { timestamp = this.tilNextMillis(this.lastTimestamp); } } else { this.sequence = 0L; } this.lastTimestamp = timestamp; return timestamp - this.twepoch << (int)this.timestampLeftShift | this.workId << (int)this.workIdShift | processId << (int)this.transactionShift | this.sequence; } } } public long getTransactionId(long id) { if (this.transactionBits <= 0L) { throw new RuntimeException("The current ID does not have a transaction ID. "); } else { String binaryId = Long.toBinaryString(id >> (int)this.transactionShift); String transactionId = binaryId.substring((int)((long)binaryId.length() - this.transactionBits)); return Long.parseLong(transactionId, 2); } } //等待下一毫秒 protected long tilNextMillis(long lastTimestamp) { long timestamp; for(timestamp = this.timeGen(); timestamp <= lastTimestamp; timestamp = this.timeGen()) { } return timestamp; } protected long timeGen() { return System.currentTimeMillis(); } // protected byte getLastIP() { byte lastip = 0; try { InetAddress ip = InetAddress.getLocalHost(); byte[] ipByte = ip.getAddress(); lastip = ipByte[ipByte.length - 1]; } catch (UnknownHostException var4) { var4.printStackTrace(); } return lastip; } enum SnowflakeConfigEnum { SHOP_ID, MEMBER_ID, SELLER_ID, ADDRESS_ID, ORDER_ID, PAYMENT_NO, DISTRIBUTOR_ID, DISTRIBUTOR_WEAK_BIND_NO, REAL_NAME_AUTHENTICATION, SELLER_AUTHENTICATION, DEMO(1420041600000L, 8L, 6L); private long twepoch; private long transactionBits; private long sequenceBits; private SnowflakeConfigEnum() { this.twepoch = 1420041600000L;//默认值2015-01-01 this.transactionBits = 0L;// this.sequenceBits = 14L; } private SnowflakeConfigEnum(long twepoch, long transactionBits, long sequenceBits) { this.twepoch = twepoch; this.transactionBits = transactionBits; this.sequenceBits = sequenceBits; } public long getTwepoch() { return this.twepoch; } public long getTransactionBits() { return this.transactionBits; } public long getSequenceBits() { return this.sequenceBits; } } public static void main(String[] args) { // System.out.println(-1L ^ (-1L << 14)); // System.out.println(~(-1L << (int)14)); // long sequenceMask = ~(-1L << (int) 14); // long sequence = 0; // sequence = sequence + 1L & sequenceMask; // System.out.println(sequence); // sequence = sequence + 16383 & sequenceMask; // System.out.println(sequence); // sequence = sequence + 16383 & sequenceMask; // System.out.println(sequence); // // // // System.out.println(64 >> 3); // System.out.println(8 << 3); SnowFlakeId snowFlake = new SnowFlakeId(SnowflakeConfigEnum.SELLER_ID); Long id = snowFlake.nextId(); long start = System.currentTimeMillis(); for (int i = 0; i < 10 ; i++) { id = snowFlake.nextId(); System.out.println(id); System.out.println(Long.toBinaryString(id)); // System.out.println("datacenterid:"+ snowFlake.getDatacenterId() +" machineid:"+snowFlake.getMachineId()); // System.out.println("datacenterid:"+ snowFlake.getDatacenterById(id)+" machineid:"+snowFlake.getMachineIdById(id)); //System.out.println( id >> 12 & 0X1f); //System.out.println( id >> 12+5 & 0X1f); } System.out.println(System.currentTimeMillis() - start); } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
time:690272494547894272 bindary:100110010100010101110010110100110011110000000000000000000000 wrod:1802240 bindary:110111000000000000000 sequence:0 bindary:0 l4 bindary or :690272494549696512 bindary:100110010100010101110010110100110011110110111000000000000000 15 bindary or :690272494549696512 bindary:100110010100010101110010110100110011110110111000000000000000 16 bindary or :690272494549696512 bindary:100110010100010101110010110100110011110110111000000000000000 time:690273683473694720 bindary:100110010100010110000100001000000101010000000000000000000000 wrod:1802240 bindary:110111000000000000000 sequence:0 bindary:0 l4 bindary or :690273683475496960 bindary:100110010100010110000100001000000101010110111000000000000000 15 bindary or :690273683475496960 bindary:100110010100010110000100001000000101010110111000000000000000 16 bindary or :690273683475496960 bindary:100110010100010110000100001000000101010110111000000000000000 690273683475496960 100110010100010110000100001000000101010110111000000000000000 |
©版权声明：本文为【翰林小院】（huhanlin.com）原创文章，转载时请注明出处！
新冠快点结束吧!