理解分布式id生成算法--雪花算法（SnowFlake）

分布式ID生成算法的有很多種，Twitter的SnowFlake就是其中經典的一種。

注：

1B就是1個字節。
Byte、KB、B、MB、GB之間的關系是：
Bit——比特 ； B ——字節；KB——千字節；MB——兆字節；GB——吉字節；TB——太字節
1bit=0.125b?；1B=8 Bit? ?；1KB＝1024B? ? ? 1MB＝1024KB；1GB＝1024MB；1TB=1024GB

?

1位，不用。二進制中最高位為1的都是負數，但是我們生成的ID一般都使用整數，所以這個最高位固定是0.

41位，用來記錄時間戳（毫秒）

? ? ? ? ? ? 41位可以表示正整數（計算機中整數包含0），可以表示的數值范圍是：0至$2^{41}-1$,

? ? ? ? ? ? 減1是因為可表示的的數值范圍是從0開始算的，而不是1.

? ? ? ? ? ? ?也就是說41位可以表示$2^{41}-1$個毫秒的值，轉化成單位年則是$2^({41}-1)/(1000*60*60*24*365)=69$年

10位,用來記錄工作機器ID。

? ? ? ? ?可以部署在$2^{10}=1024$個字節。包括5位datacenterId和5位workerId。

? ? ? ? ? 5位（bit）可以表示的最大正整數是$2^{5}-1=31$,即可以用0,1,2,3....31這32個數字，來表示不同的datacenterId?

? ? ? ? ? 或者workerId.

12位，序列號，用來記錄同毫秒內產生的不同Id。

? ? ? ? 12位（bit）可以表示的最大整數是$2^{12}-1=4095$,即可以用0、1、2、3....4094這4095個數字，來表示同一機器

? ? ? ? ?同一時間戳（毫秒）內產生的4095個ID序號。

由于在java中64bit的整數是long類型，所以在java中SnowFlake算法生產的ID就是longKauai存儲的，

?

SnowFlake可以保證：

所有生成ID按時間趨勢遞增。

整個分布式系統內不會產生重復ID（因為datacenterID和wokerID來做區分）

?

?

java代碼工具類：

?

package suanfa;

/**
* ### 雪花算法：
SnowFlake算法用來生成64位的ID，剛好可以用long整型存儲，能夠用于分布式系統中生產唯一的ID， 并且生成的ID有大致的順序。 在這次實現中，生成的64位ID可以分成5個部分：

`0 - 41位時間戳 - 5位數據中心標識 - 5位機器標識 - 12位序列號`

````java
* twitter的snowflake算法 -- java實現
*
* @author beyond
* @date 2016/11/26
*/
public class SnowFlake {

/**
* 起始的時間戳
*/
private final static long START_STMP = 1480166465631L;

/**
* 每一部分占用的位數
*/
private final static long SEQUENCE_BIT = 12; //序列號占用的位數
private final static long MACHINE_BIT = 5; //機器標識占用的位數
private final static long DATACENTER_BIT = 5;//數據中心占用的位數

/**
* 每一部分的最大值
*/
//最大支持數據中心節點數0~31，一共32個
private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
//最大支持機器節點數0~31，一共32個
private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
//序列號0~12,一共12個
private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);

/**
* 每一部分向左的位移
*/
//機器節點左移12位
private final static long MACHINE_LEFT = SEQUENCE_BIT;
//數據中心節點左移17位
private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
//時間毫秒數左移22位
private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;

private long datacenterId; //數據中心
private long machineId; //機器標識
private long sequence = 0L; //序列號
private long lastStmp = -1L;//上一次時間戳 //最大為4095

public SnowFlake(long datacenterId, long machineId) {
if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
}
if (machineId > MAX_MACHINE_NUM || machineId < 0) {
throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0");
}
this.datacenterId = datacenterId;
this.machineId = machineId;
}

/**
* 產生下一個ID
*
* @return
*/
public synchronized long nextId() {
long currStmp = getNewstmp();
if (currStmp < lastStmp) {
throw new RuntimeException("Clock moved backwards. Refusing to generate id");
}

if (currStmp == lastStmp) {
//相同毫秒內，序列號自增
sequence = (sequence + 1) & MAX_SEQUENCE;
//同一毫秒的序列數已經達到最大
if (sequence == 0L) {
currStmp = getNextMill();
}
} else {
//不同毫秒內，序列號置為0
sequence = 0L;
}

lastStmp = currStmp;

return (currStmp - START_STMP) << TIMESTMP_LEFT //時間戳部分
| datacenterId << DATACENTER_LEFT //數據中心部分
| machineId << MACHINE_LEFT //機器標識部分
| sequence; //序列號部分
}

private long getNextMill() {
long mill = getNewstmp();
while (mill <= lastStmp) {
mill = getNewstmp();
}
return mill;
}

private long getNewstmp() {
return System.currentTimeMillis();
}

public static void main(String[] args) {
//數據中心id,機器標識id
SnowFlake snowFlake = new SnowFlake(2, 3);
System.out.println(snowFlake.nextId());

}

}

?