背景
使用雪花算法生成的主鍵蹬屹，二進制表示形式包含4部分，從高位到低位分表為：1bit符號位白华、41bit時間戳位慨默、10bit工作進程位（也可以區(qū)分5bit數(shù)據(jù)中心、5bit機器ID）以及12bit序列號位弧腥。
符號位(1bit)
預(yù)留的符號位厦取，恒為零。時間戳位(41bit)
41位的時間戳可以容納的毫秒數(shù)是2的41次方減1管搪，一年所使用的毫秒數(shù)是：365 * 24 * 60 * 60 * 1000虾攻。通過計算可知：
(Math.pow(2, 41) -1) / (365 * 24 * 60 * 60 * 1000L);
結(jié)果約等于69年。Sharding-Sphere的雪花算法的時間紀(jì)元從2016年11月1日零點開始更鲁，可以使用到2085年霎箍，相信能滿足絕大部分系統(tǒng)的要求。工作進程位(10bit)
該標(biāo)志在Java進程內(nèi)是唯一的澡为，如果是分布式應(yīng)用部署應(yīng)保證每個工作進程的id是不同的朋沮。該值默認(rèn)為0，可通過調(diào)用靜態(tài)方法DefaultKeyGenerator.setWorkerId(“xxxx”)設(shè)置缀壤。序列號位(12bit)
該序列是用來在同一個毫秒內(nèi)生成不同的ID樊拓。如果在這個毫秒內(nèi)生成的數(shù)量超過4096(2的12次方)，那么生成器會等待到下個毫秒繼續(xù)生成塘慕。
代碼樣例
public final class DefaultKeyGenerator {
public static final long EPOCH;
private static final long SEQUENCE_BITS = 12L;
private static final long WORKER_ID_BITS = 10L;
private static final long SEQUENCE_MASK = (1 << SEQUENCE_BITS) - 1;
private static final long WORKER_ID_LEFT_SHIFT_BITS = SEQUENCE_BITS;
private static final long TIMESTAMP_LEFT_SHIFT_BITS = WORKER_ID_LEFT_SHIFT_BITS + WORKER_ID_BITS;
private static final long WORKER_ID_MAX_VALUE = 1L << WORKER_ID_BITS;
private static long workerId;
private static int maxTolerateTimeDifferenceMilliseconds = 10;
static {
//也可指定開始年份
Calendar calendar = Calendar.getInstance();
calendar.set(2016, Calendar.NOVEMBER, 1);
calendar.set(Calendar.HOUR_OF_DAY, 0);
calendar.set(Calendar.MINUTE, 0);
calendar.set(Calendar.SECOND, 0);
calendar.set(Calendar.MILLISECOND, 0);
EPOCH = calendar.getTimeInMillis();
}
private byte sequenceOffset;
private long sequence;
private long lastMilliseconds;
/**
* Set work process id.
*
* @param workerId work process id
*/
public static void setWorkerId(final long workerId) {
Preconditions.checkArgument(workerId >= 0L && workerId < WORKER_ID_MAX_VALUE);
DefaultKeyGenerator.workerId = workerId;
}
/**
* Set max tolerate time difference milliseconds.
*
* @param maxTolerateTimeDifferenceMilliseconds max tolerate time difference milliseconds
*/
public static void setMaxTolerateTimeDifferenceMilliseconds(final int maxTolerateTimeDifferenceMilliseconds) {
DefaultKeyGenerator.maxTolerateTimeDifferenceMilliseconds = maxTolerateTimeDifferenceMilliseconds;
}
/**
* Generate key.
*
* @return key type is @{@link Long}.
*/
public synchronized Number generateKey() {
long currentMilliseconds = System.currentTimeMillis();
if (waitTolerateTimeDifferenceIfNeed(currentMilliseconds)) {
currentMilliseconds = System.currentTimeMillis();
}
if (lastMilliseconds == currentMilliseconds) {
//如果在這個毫秒內(nèi)生成的數(shù)量超過4096(2的12次方)筋夏，那么生成器會等待到下個毫秒繼續(xù)生成
if (0L == (sequence = (sequence + 1) & SEQUENCE_MASK)) {
currentMilliseconds = waitUntilNextTime(currentMilliseconds);
}
} else {
//下面方法的sequence只能為0或1，也可以隨機一個值如sequence = RandomUtils.nextLong(0L, 60L) * 60L;
vibrateSequenceOffset();
sequence = sequenceOffset;
}
lastMilliseconds = currentMilliseconds;
return ((currentMilliseconds - EPOCH) << TIMESTAMP_LEFT_SHIFT_BITS) | (workerId << WORKER_ID_LEFT_SHIFT_BITS) | sequence;
}
@SneakyThrows
private boolean waitTolerateTimeDifferenceIfNeed(final long currentMilliseconds) {
if (lastMilliseconds <= currentMilliseconds) {
return false;
}
long timeDifferenceMilliseconds = lastMilliseconds - currentMilliseconds;
Preconditions.checkState(timeDifferenceMilliseconds < maxTolerateTimeDifferenceMilliseconds,
"Clock is moving backwards, last time is %d milliseconds, current time is %d milliseconds", lastMilliseconds, currentMilliseconds);
Thread.sleep(timeDifferenceMilliseconds);
return true;
}
private long waitUntilNextTime(final long lastTime) {
long result = System.currentTimeMillis();
while (result <= lastTime) {
result = System.currentTimeMillis();
}
return result;
}
private void vibrateSequenceOffset() {
sequenceOffset = (byte) (~sequenceOffset & 1);
}
}
單元測試
public class KeyGeneratorTest {
@Test
public void test() {
//工作進程位10位 取值1-1024 默認(rèn)0
DefaultKeyGenerator.setWorkerId(1000);
//時鐘回?fù)芡寄兀畲笤试S容忍差異毫秒數(shù)条篷，超過這個時間將返回異常骗随，默認(rèn)10ms
DefaultKeyGenerator.setMaxTolerateTimeDifferenceMilliseconds(10);
DefaultKeyGenerator keyGenerator = new DefaultKeyGenerator();
for(int i=0;i<1000;i++){
System.out.println(keyGenerator.generateKey());
}
}
}
優(yōu)化
為避免需要手動設(shè)置workerId，可通過使用IP地址計算得出workId
public class IPSectionKeyGenerator {
private final SnowflakeKeyGenerator snowflakeKeyGenerator = new SnowflakeKeyGenerator();
static {
InetAddress address;
try {
address = InetAddress.getLocalHost();
} catch (UnknownHostException var8) {
throw new IllegalStateException("Cannot get LocalHost InetAddress, please check your network!");
}
long workerId = 0L;
byte[] ipAddressByteArray = address.getAddress();
int ipLength = ipAddressByteArray.length;
int count = 0;
flag:
switch(ipLength) {
case 4:
while(true) {
if (count >= ipLength) {
break flag;
}
byte byteNum = ipAddressByteArray[count];
workerId += byteNum & 255;
++count;
}
case 16:
while(true) {
if (count >= ipLength) {
break flag;
}
byte byteNum = ipAddressByteArray[count];
workerId += byteNum & 63;
++count;
}
default:
throw new IllegalStateException("Bad LocalHost InetAddress, please check your network!");
}
SnowflakeKeyGenerator.setWorkerId(workerId);
}
public long generateKey() {
return this.snowflakeKeyGenerator.generateKey();
}
}
總結(jié)
雪花算法是由Twitter公布的分布式主鍵生成算法赴叹，它能夠保證不同進程主鍵的不重復(fù)性鸿染，以及相同進程主鍵的有序性。
在同一個進程中乞巧，它首先是通過時間位保證不重復(fù)涨椒，如果時間相同則是通過序列位保證。
同時由于時間位是單調(diào)遞增的绽媒，且各個服務(wù)器如果大體做了時間同步蚕冬，那么生成的主鍵在分布式環(huán)境可以認(rèn)為是總體有序的。同時代碼對于時鐘回?fù)軉栴}也做了相應(yīng)的處理是辕。
