雪花算法
SnowFlake 算法，是 Twitter 開源的分布式 id 生成算法。其核心思想就是：使用一個 64 bit 的 long 型的數(shù)字作為全局唯一 id。在分布式系統(tǒng)中的應用十分廣泛，且ID 引入了時間戳，基本上保持自增的。本文主要是是實現(xiàn)了單機版本的算法，使用多臺計算機構成分布式的ID生成服務也是可以的，預留了相關的方法參數(shù)。
應用范圍
1、在jdk中自帶的uuid算法可以來生成唯一性的32位字符串【拼接上‘-’之后，是36位，如：’
4211210a-ba56-41b4-b055-6262411970a4’】，uuid算法得到的id是無序的，而且是字符串，數(shù)據表記錄多時，查詢效率不高
2、基于數(shù)據庫的sequnce【通過表也可以模擬sequence】來生成，在分布式系統(tǒng)中更新記錄不方便，只能操作主表的更新。
3、雪花算法在分布式系統(tǒng)中可以較好地使用。
原理
把64位進行拆分，分為如下幾個部份
第1部份只占1位，而且必需為0，因為最高位0表示正數(shù)。
第2部份是時間戳，占41位【為什么是41位，后面會介紹】，最多可以表示2^41，大約是69年
第3部份是產生的機器號，占10位【也可以是其它位數(shù)，不一定非得是10位，官方約定是10位】，最多可以表示2^10，相當于1024臺機器，這部分可以劃成兩個維度，如下：
3.1 拿5位出來做為機房號，最多可以表示 2^5個機房號，也就是最多32個機房編號
3.2 拿5位出來做為機器號，最多可以表示 2^5臺電腦，也就是最多32臺電腦編號
第4部份是時間戳，占12位，相當于在同一個毫秒內，可以最大支持2^12，也就是4096個序號【普通的計算機根本達不到】
代碼實現(xiàn)
public class IdGenerator {
//定義屬性 [機器碼10位，如何分配成 機房碼和電腦碼，做為屬性，這里默認都是5]
private final long dataCenterBits = 5L; //機房碼的位數(shù)
private final long computerBits = 5L; //電腦碼的位數(shù)
//最后的序列碼，默認從0開始
private long sequence = 0L;
//記錄執(zhí)行的最后時間，以毫秒為單位，默認初始化為-1L
private long lastTimeStamp = -1L;
//因為要做二進制運算，我們需要定義如下屬性來記錄每個部份所在的位置的偏移量
private final long sequenceBits = 12; //序號占用12位
private final long computerIdShift = sequenceBits; //電腦碼的偏移量
private final long dataCenterIdShift = computerIdShift + computerBits; //機房碼的偏移量
private final long timeStampShift = dataCenterIdShift + dataCenterBits; //時間戳的偏移量
//根據機房碼的位數(shù)，來計算出機房碼最大值
private final long MAX_DATA_CENTER = -1L ^ (-1L << dataCenterBits); //相當于 11111， 也就是 31
private final long MAX_COMPUTER = -1L ^ (-1L << computerBits); //同上
private final long SEQUENCE_MASK = -1L ^ (-1L << sequenceBits); // 為防止序列號溢出而準備的掩碼，相當于 11111111 111
//定義屬性
private long computerId; //電腦的id 【在分布式系統(tǒng)中，記錄這個雪花號是由哪一臺電腦生成的】
private long dataCenterId; //機房的id 【在分布式系統(tǒng)中，記錄這個雪花號是由哪一個中心機房里的電腦生成的】
//構造
public IdGenerator(long computerId, long dataCenterId) {
//對參數(shù)的有效性進行判斷，由于機房碼和電腦碼都是5位，所以，它們的值最大都不能超過31
if(computerId > MAX_COMPUTER || computerId < 0) {
throw new IllegalArgumentException(String.format("電腦編號不能大于 %d 或者小于 %d n",MAX_COMPUTER,0));
}
if(dataCenterId > MAX_DATA_CENTER || dataCenterId < 0) {
throw new IllegalArgumentException(String.format("機房編號不能大于 %d 或者小于 %dn",MAX_DATA_CENTER, 0));
}
//賦值
this.computerId = computerId;
this.dataCenterId = dataCenterId;
}
/***************
* 核心方法，利用雪花算法來獲取一個唯一性的ID
* @return
*/
public synchronized long nextId() {
//1.獲取當前的系統(tǒng)時間
long currTime = getCurrentTime();
//2. 判斷是否在同一個時間內的請求
if(currTime == lastTimeStamp) {
//2.1 sequence 要增1, 但要預防sequence超過 最大值4095，所以要 與 SEQUENCE_MASK 按位求與
sequence = (sequence + 1) & SEQUENCE_MASK;
//2.2 進一步判斷，如果在同一個毫秒內，sequence達到了4096【1 0000 0000 0000】，則lastTime時間戳必需跳入下一個時間，因為同一個毫秒內
//sequence只能產生4096個【0-4095】，當超過時，必需跳入下一個毫秒
// 【此情況極少出現(xiàn)，但不可不防，這意味著1個毫秒內，JVM要執(zhí)行此方法達到4096次，我這個電腦執(zhí)行遠達不到。】
if(sequence == 0) {
currTime = unitNextTime();
}
} else {
//如果不是與lastTime一樣，則表示進入了下一個毫秒，則sequence重新計數(shù)
sequence = 0L;
}
//3. 把當前時間賦值給 lastTime, 以便下一次判斷是否處在同一個毫秒內
lastTimeStamp = currTime;
//4. 依次把各個部門求出來并通過邏輯或 拼接起來
return (this.lastTimeStamp << timeStampShift) | //把當前系統(tǒng)時間 左移22位
(this.dataCenterId << dataCenterIdShift) | //把機房編號 左移17位
(this.computerId << computerIdShift) | //把計算機號編號左移 12位
this.sequence; //最后的序列號占12位，無需移動
}
/******
* 等待毫秒數(shù)進入下一個時間
* @return
*/
private long unitNextTime() {
//1.再次獲取系統(tǒng)時間
long timestamp = getCurrentTime();
//2. 判斷 lastTime與currentTime是否一樣
while(timestamp <= lastTimeStamp) {
//2.1 繼續(xù)獲取系統(tǒng)時間，直到上面的條件不成立為止
timestamp = getCurrentTime();
}
//3. 返回
return timestamp;
}
/*****
* 用來獲取當前的系統(tǒng)時間，以毫秒為單位
* @return
*/
private long getCurrentTime() {
return System.currentTimeMillis();
}
}
測試類
public class UseIdGenerator {
/****
* 主方法
* @param args
*/
public static void main(String[] args) {
//這里兩個參數(shù)都是1，表示1號機房和1號電腦【在分布式系統(tǒng)中，每個電腦知道自己所在的機房和編號】
IdGenerator ig = new IdGenerator(1,1);
//循環(huán)生成
long result = -1;
for(int i = 0;i<100000;i++) {
result = ig.nextId();
System.out.println(result+" , "+Long.toBinaryString(result));
}
}
}
