摘要：SnowFlake算法生成的ID大致上是按照時(shí)間遞增的喂柒，用在分布式系統(tǒng)中時(shí)辣卒，需要注意數(shù)據(jù)中心標(biāo)識(shí)和機(jī)器標(biāo)識(shí)必須唯一拧晕，這樣就能保證每個(gè)節(jié)點(diǎn)生成的ID都是唯一的紊扬。
概述
SnowFlake算法是Twitter設(shè)計(jì)的一個(gè)可以在分布式系統(tǒng)中生成唯一的ID的算法蜒茄，它可以滿足Twitter每秒上萬(wàn)條消息ID分配的請(qǐng)求，這些消息ID是唯一的且有大致的遞增順序餐屎。
原理
SnowFlake算法產(chǎn)生的ID是一個(gè)64位的整型檀葛，結(jié)構(gòu)如下（每一部分用“-”符號(hào)分隔）：
0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
1位標(biāo)識(shí)部分，在java中由于long的最高位是符號(hào)位腹缩，正數(shù)是0屿聋，負(fù)數(shù)是1，一般生成的ID為正數(shù)藏鹊，所以為0润讥；
41位時(shí)間戳部分，這個(gè)是毫秒級(jí)的時(shí)間盘寡，一般實(shí)現(xiàn)上不會(huì)存儲(chǔ)當(dāng)前的時(shí)間戳楚殿，而是時(shí)間戳的差值（當(dāng)前時(shí)間-固定的開始時(shí)間），這樣可以使產(chǎn)生的ID從更小值開始竿痰；41位的時(shí)間戳可以使用69年脆粥，(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年砌溺；
10位節(jié)點(diǎn)部分，Twitter實(shí)現(xiàn)中使用前5位作為數(shù)據(jù)中心標(biāo)識(shí)变隔，后5位作為機(jī)器標(biāo)識(shí)规伐，可以部署1024個(gè)節(jié)點(diǎn)；
12位序列號(hào)部分匣缘，支持同一毫秒內(nèi)同一個(gè)節(jié)點(diǎn)可以生成4096個(gè)ID猖闪；
SnowFlake算法生成的ID大致上是按照時(shí)間遞增的，用在分布式系統(tǒng)中時(shí)肌厨，需要注意數(shù)據(jù)中心標(biāo)識(shí)和機(jī)器標(biāo)識(shí)必須唯一萧朝，這樣就能保證每個(gè)節(jié)點(diǎn)生成的ID都是唯一的∠目蓿或許我們不一定都需要像上面那樣使用5位作為數(shù)據(jù)中心標(biāo)識(shí)检柬，5位作為機(jī)器標(biāo)識(shí)，可以根據(jù)我們業(yè)務(wù)的需要竖配，靈活分配節(jié)點(diǎn)部分何址，如：若不需要數(shù)據(jù)中心，完全可以使用全部10位作為機(jī)器標(biāo)識(shí)进胯；若數(shù)據(jù)中心不多用爪，也可以只使用3位作為數(shù)據(jù)中心，7位作為機(jī)器標(biāo)識(shí)胁镐。
/**
* twitter的snowflake算法 -- java實(shí)現(xiàn)
*
* @author rock
* @date 2016/11/26
*/
public class SnowFlake {
/**
* 起始的時(shí)間戳
*/
private final static long START_STMP = 1480166465631L;
/**
* 每一部分占用的位數(shù)
*/
private final static long SEQUENCE_BIT = 12; //序列號(hào)占用的位數(shù)
private final static long MACHINE_BIT = 5; //機(jī)器標(biāo)識(shí)占用的位數(shù)
private final static long DATACENTER_BIT = 5;//數(shù)據(jù)中心占用的位數(shù)
/**
* 每一部分的最大值
*/
private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
/**
* 每一部分向左的位移
*/
private final static long MACHINE_LEFT = SEQUENCE_BIT;
private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;
private long datacenterId; //數(shù)據(jù)中心
private long machineId; //機(jī)器標(biāo)識(shí)
private long sequence = 0L; //序列號(hào)
private long lastStmp = -1L;//上一次時(shí)間戳
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;
}
/**
* 產(chǎn)生下一個(gè)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) {
//相同毫秒內(nèi)偎血，序列號(hào)自增
sequence = (sequence + 1) & MAX_SEQUENCE;
//同一毫秒的序列數(shù)已經(jīng)達(dá)到最大
if (sequence == 0L) {
currStmp = getNextMill();
}
} else {
//不同毫秒內(nèi)，序列號(hào)置為0
sequence = 0L;
}
lastStmp = currStmp;
return (currStmp - START_STMP) << TIMESTMP_LEFT //時(shí)間戳部分
| datacenterId << DATACENTER_LEFT //數(shù)據(jù)中心部分
| machineId << MACHINE_LEFT //機(jī)器標(biāo)識(shí)部分
| sequence; //序列號(hào)部分
}
private long getNextMill() {
long mill = getNewstmp();
while (mill <= lastStmp) {
mill = getNewstmp();
}
return mill;
}
private long getNewstmp() {
return System.currentTimeMillis();
}
}
可以寫一代碼測(cè)試一下盯漂，如下所示：
public static void main(String[] args) {
SnowFlake snowFlake = new SnowFlake(2, 3);
for (int i = 0; i < (1 << 12); i++) {
System.out.println(snowFlake.nextId());
}
}
可以看到生成的ID都是遞增的颇玷，而且都是唯一的。
