介紹Snowflake算法
SnowFlake算法是國際大公司Twitter的采用的一種生成分布式自增id的策略，這個算法產(chǎn)生的分布式id是足夠我們我們中小公司在日常里面的使用了。我也是比較推薦這一種算法產(chǎn)生的分布式id的。
算法snowflake的生成的分布式id結(jié)構(gòu)組成部分
算法snowflake生成id的結(jié)果是一個64bit大小的整數(shù)案铺，它的結(jié)構(gòu)如下圖，
這里我么來講一下這個結(jié)構(gòu)：首先因為window是64位的，然后整數(shù)的時候第一位必須是0货抄，所以最大的數(shù)值就是63位的111111111111111111111111111111111111111111111111111111111111111，然后呢Snowflake算法分出來41位作為毫秒值，然后10位作為redis節(jié)點的數(shù)量碉熄，然后12位做成redis節(jié)點在每一毫秒的自增序列值
41位的二進制11111111111111111111111111111111111111111轉(zhuǎn)換成10進制的毫秒就是2199023255551桨武，然后我們把 2199023255551轉(zhuǎn)換成時間就是2039-09-07，也就是說可以用20年的（這里在網(wǎng)上會有很多說是可以使用69年的锈津，他們說69年的也對呀酸，因為1970年+69年的結(jié)果就是2039年击喂，但是如果從今年2019年來說擅笔，也就只能用20年了）
然后10位作為節(jié)點，所以最多就是12位的1111111111杨蛋，也就是最多可以支持1023個節(jié)點茎杂，
然后10位表示每一個節(jié)點自增序列值错览，這里最多就是10位的111111111111，也就是說每一個節(jié)點可以每一毫秒可以最多生成4059個不重復(fù)id值
由于在Java中64bit的整數(shù)是long類型煌往，所以在Java中SnowFlake算法生成的id就是long來存儲的倾哺。
Java實現(xiàn)Snowflake算法的源碼
Snowflake算法的源碼如下所示(這個是我從網(wǎng)上找到的)，這里我進行了測試了一波刽脖，結(jié)果如下所示
package com.hello;
import java.text.SimpleDateFormat;
import java.util.Date;
public class Test {
/**
* 開始時間截 (1970-01-01)
*/
private final long twepoch = 0L;
/**
* 機器id所占的位數(shù)
*/
private final long workerIdBits = 5L;
/**
* 數(shù)據(jù)標(biāo)識id所占的位數(shù)
*/
private final long datacenterIdBits = 5L;
/**
* 支持的最大機器id羞海，結(jié)果是31 (這個移位算法可以很快的計算出幾位二進制數(shù)所能表示的最大十進制數(shù))
*/
private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
/**
* 支持的最大數(shù)據(jù)標(biāo)識id，結(jié)果是31
*/
private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
/**
* 序列在id中占的位數(shù)
*/
private final long sequenceBits = 12L;
/**
* 機器ID向左移12位
*/
private final long workerIdShift = sequenceBits;
/**
* 數(shù)據(jù)標(biāo)識id向左移17位(12+5)
*/
private final long datacenterIdShift = sequenceBits + workerIdBits;
/**
* 時間截向左移22位(5+5+12)
*/
private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
/**
* 生成序列的掩碼曲管，這里為4095 (0b111111111111=0xfff=4095)
*/
private final long sequenceMask = -1L ^ (-1L << sequenceBits);
/**
* 工作機器ID(0~31)
*/
private long workerId;
/**
* 數(shù)據(jù)中心ID(0~31)
*/
private long datacenterId;
/**
* 毫秒內(nèi)序列(0~4095)
*/
private long sequence = 0L;
/**
* 上次生成ID的時間截
*/
private long lastTimestamp = -1L;
public Test(long workerId, long datacenterId) {
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
}
if (datacenterId > maxDatacenterId || datacenterId < 0) {
throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
}
this.workerId = workerId;
this.datacenterId = datacenterId;
}
/**
* 獲得下一個ID (該方法是線程安全的)
*
* @return SnowflakeId
*/
public synchronized long nextId() {
long timestamp = timeGen();
//如果當(dāng)前時間小于上一次ID生成的時間戳却邓，說明系統(tǒng)時鐘回退過這個時候應(yīng)當(dāng)拋出異常
if (timestamp < lastTimestamp) {
throw new RuntimeException(
String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
//如果是同一時間生成的，則進行毫秒內(nèi)序列
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & sequenceMask;
//毫秒內(nèi)序列溢出
if (sequence == 0) {
//阻塞到下一個毫秒,獲得新的時間戳
timestamp = tilNextMillis(lastTimestamp);
}
}
//時間戳改變院水，毫秒內(nèi)序列重置
else {
sequence = 0L;
}
//上次生成ID的時間截
lastTimestamp = timestamp;
//移位并通過或運算拼到一起組成64位的ID
return ((timestamp - twepoch) << timestampLeftShift) //
| (datacenterId << datacenterIdShift) //
| (workerId << workerIdShift) //
| sequence;
}
/**
* 阻塞到下一個毫秒腊徙，直到獲得新的時間戳
*
* @param lastTimestamp 上次生成ID的時間截
* @return 當(dāng)前時間戳
*/
protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
/**
* 返回以毫秒為單位的當(dāng)前時間
*
* @return 當(dāng)前時間(毫秒)
*/
protected long timeGen() {
return System.currentTimeMillis();
}
public static void parseId(long id) {
long miliSecond = id >>> 22;
long shardId = (id & (0xFFF << 10)) >> 10;
System.err.println("分布式id-"+id+"生成的時間是："+new SimpleDateFormat("yyyy-MM-dd").format(new Date(miliSecond)));
}
public static void main(String[] args) {
Test idWorker = new Test(0, 0);
for (int i = 0; i < 10; i++) {
long id = idWorker.nextId();
System.out.println(id);
parseId(id);
}
}
}
執(zhí)行結(jié)果如下所示，此時我們可以看到檬某，不僅可以可以把分布式id給創(chuàng)建處理撬腾，而且可以把這個創(chuàng)建的時間也打印出來，此時就可以滿足我們的分布式id的創(chuàng)建了
6566884785623400448
分布式id-6566884785623400448生成的時間是：2019-08-13
6566884785812144128
分布式id-6566884785812144128生成的時間是：2019-08-13
6566884785812144129
分布式id-6566884785812144129生成的時間是：2019-08-13
6566884785812144130
分布式id-6566884785812144130生成的時間是：2019-08-13
6566884785812144131
分布式id-6566884785812144131生成的時間是：2019-08-13
6566884785812144132
分布式id-6566884785812144132生成的時間是：2019-08-13
6566884785816338432
分布式id-6566884785816338432生成的時間是：2019-08-13
6566884785816338433
分布式id-6566884785816338433生成的時間是：2019-08-13
6566884785816338434
分布式id-6566884785816338434生成的時間是：2019-08-13
6566884785816338435
分布式id-6566884785816338435生成的時間是：2019-08-13
縮小版Snowflake算法生成分布式id
因為Snowflake算法的極限是每毫秒的每一個節(jié)點生成4059個id值恢恼，也就是說每毫秒的極限是生成023*4059=4 152 357個id值民傻，這樣生成id值的速度對于twitter公司來說是很符合標(biāo)準(zhǔn)的(畢竟人家公司大嘛)，但是對于咱們中小公司來說是不需要的厅瞎，所以我們可以根據(jù)Snowflake算法來修改一下分布式id的創(chuàng)建饰潜，讓每秒創(chuàng)建的id少一些，但是把可以使用的時間擴大一些
這里我看廖雪峰老師的文章之后和簸，采用了53位作為分布式id值的位數(shù)彭雾，因為如果后端和前端的JavaScript打交道的話，由于JavaScript支持的最大整型就是53位锁保，超過這個位數(shù)薯酝，JavaScript將丟失精度半沽。因此，使用53位整數(shù)可以直接由JavaScript讀取吴菠，而超過53位時者填，就必須轉(zhuǎn)換成字符串才能保證JavaScript處理正確，所以我們的分布式id就用53位來生成
這53位里面做葵，第一位還是0占哟，然后剩下的52位，33位作為秒數(shù)酿矢，4位作為節(jié)點數(shù)榨乎，15位作為每一個節(jié)點在每一秒的生成序列值
33位的二進制111111111111111111111111111111111轉(zhuǎn)換成10進制的秒就是8589934591，然后我們把 8589934591轉(zhuǎn)換成時間就是2242-03-16瘫筐，也就是說可以用220年的蜜暑，足夠我們的使用了
然后4位節(jié)點，所以最多就是4位的1111策肝，也就是最多可以支持15個節(jié)點肛捍，
然后15位表示每一個節(jié)點每一秒自增序列值，這里最多就是10位的11111111111111111之众，也就是說每一個節(jié)點可以每一秒可以最多生成131071個不重復(fù)id值
這樣算起來拙毫，就是說每一秒每一個節(jié)點生成131071個不重復(fù)的節(jié)點，所以極限就是每秒生成15*131071=1 966 065個分布式id酝枢，夠我們在開發(fā)里面的日常使用了
所以代碼就可以變成下面這樣恬偷，這里主要講一下下面的nextId()方法悍手，
首先藍色代碼是獲取當(dāng)前秒帘睦，然后進行校驗，就是把當(dāng)前時間和上一個時間戳進行比較坦康，如果當(dāng)前時間比上一個時間戳要小竣付，那就說明系統(tǒng)時鐘回退，所以此時應(yīng)該拋出異常
然后是下面的紅色代碼滞欠，首先如果是同一秒生成的古胆，那么就把這一秒的生成序列id值一直增加，一直增加到131071個筛璧，如果在增加逸绎，那么下面的紅色代碼里面的sequence = (sequence + 1) & sequenceMask;的值就會是0，那么就會執(zhí)行紅色代碼里面的tilNextMillis()方法進行阻塞夭谤，直到獲取到下一秒繼續(xù)執(zhí)行
然后下面的綠色代碼表示每一秒過去之后棺牧，都要把這個生成序列的id值都變成0，這樣在新的一秒里面就可以在繼續(xù)生成1到131071個分布式id值了
然后下面的黃色代碼就是把咱們的秒朗儒，節(jié)點值颊乘，節(jié)點每秒生成序列id值加起來組成一個分布式id返回
package com.hello;
import java.text.SimpleDateFormat;
import java.util.Date;
public class Test {
/**
* 開始時間截 (1970-01-01)
*/
private final long twepoch = 0L;
/**
* 機器id参淹，范圍是1到15
*/
private final long workerId;
/**
* 機器id所占的位數(shù)，占4位
*/
private final long workerIdBits = 4L;
/**
* 支持的最大機器id乏悄，結(jié)果是15
*/
private final long maxWorkerId = ~(-1L << workerIdBits);
/**
* 生成序列占的位數(shù)
*/
private final long sequenceBits = 15L;
/**
* 機器ID向左移15位
*/
private final long workerIdShift = sequenceBits;
/**
* 生成序列的掩碼浙值，這里為最大是32767 (1111111111111=32767)
*/
private final long sequenceMask = ~(-1L << sequenceBits);
/**
* 時間截向左移19位(4+15)
*/
private final long timestampLeftShift = 19L;
/**
* 秒內(nèi)序列(0~32767)
*/
private long sequence = 0L;
/**
* 上次生成ID的時間截
*/
private long lastTimestamp = -1L;
public Test(long workerId) {
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
}
this.workerId = workerId;
}
/**
* 獲得下一個ID (該方法是線程安全的)
*
* @return SnowflakeId
*/
public synchronized long nextId() {
//藍色代碼注釋開始
long timestamp = timeGen();
//如果當(dāng)前時間小于上一次ID生成的時間戳，說明系統(tǒng)時鐘回退過這個時候應(yīng)當(dāng)拋出異常
if (timestamp < lastTimestamp) {
throw new RuntimeException(
String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
//藍色代碼注釋結(jié)束
//紅色代碼注釋開始
//如果是同一時間生成的檩小，則進行秒內(nèi)序列
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & sequenceMask;
//秒內(nèi)序列溢出
if (sequence == 0) {
//阻塞到下一個秒,獲得新的秒值
timestamp = tilNextMillis(lastTimestamp);
}
//時間戳改變开呐，秒內(nèi)序列重置
}
//紅色代碼注釋結(jié)束
//綠色代碼注釋開始
else {
sequence = 0L;
}
//綠色代碼注釋結(jié)束
//上次生成ID的時間截
lastTimestamp = timestamp;
//黃色代碼注釋開始
//移位并通過或運算拼到一起組成53 位的ID
return ((timestamp - twepoch) << timestampLeftShift)
| (workerId << workerIdShift)
| sequence;
//黃色代碼注釋結(jié)束
}
/**
* 阻塞到下一個秒，直到獲得新的時間戳
*
* @param lastTimestamp 上次生成ID的時間截
* @return 當(dāng)前時間戳
*/
protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
/**
* 返回以秒為單位的當(dāng)前時間
*
* @return 當(dāng)前時間(秒)
*/
protected long timeGen() {
return System.currentTimeMillis()/1000L;
}
public static void parseId(long id) {
long second = id >>> 19;
System.err.println("分布式id-"+id+"生成的時間是："+new SimpleDateFormat("yyyy-MM-dd").format(new Date(second*1000)));
}
public static void main(String[] args) {
Test idWorker = new Test(0);
for (int i = 0; i < 10; i++) {
long id = idWorker.nextId();
System.out.println(id);
parseId(id);
}
}
}
此時結(jié)果如下所示规求，都是ok的负蚊，????乛?乛????
820870564020224
分布式id-820870564020224生成的時間是：2019-08-13
820870564020225
分布式id-820870564020225生成的時間是：2019-08-13
820870564020226
分布式id-820870564020226生成的時間是：2019-08-13
820870564020227
分布式id-820870564020227生成的時間是：2019-08-13
820870564020228
分布式id-820870564020228生成的時間是：2019-08-13
820870564020229
分布式id-820870564020229生成的時間是：2019-08-13
820870564020230
分布式id-820870564020230生成的時間是：2019-08-13
820870564020231
分布式id-820870564020231生成的時間是：2019-08-13
820870564020232
分布式id-820870564020232生成的時間是：2019-08-13
820870564020233
分布式id-820870564020233生成的時間是：2019-08-13
時間回撥問題的解決
- 第一種方式
可以通過創(chuàng)建一個數(shù)組的方式，比如說200長度的數(shù)組颓哮，這個數(shù)組中存儲上一次該位置對應(yīng)的毫秒數(shù)的生成的唯一id
就比如111毫秒和311毫秒吧家妆，那么就把111毫秒生成的id值和311毫秒生成的id值放到索引位置的第111位
然后當(dāng)發(fā)生時間回撥的時候，假設(shè)時間是第523毫秒冕茅，這可能是最新時間伤极，也可能是從某個時間回撥回來的，不去care姨伤，只看第523毫秒有沒有生成過id哨坪，怎么看？我們?nèi)タ?23號索引位置處查看值乍楚，有三種可能的情況：
a.123號索引沒值——用523毫秒生成新id当编，肯定不重復(fù)；
b.123號索引有值徒溪、記錄的時間是323毫秒——用523毫秒生成新id忿偷，肯定不重復(fù)；
c.123號索引里有值臊泌、記錄的時間是723毫秒——把此時723毫秒對應(yīng)的記錄的id+1當(dāng)成523毫秒的id值鲤桥，肯定不重復(fù)
c情況里面思考一個問題：就比如523毫秒吧，如果此時是c情況渠概，那么此時523毫秒生成的id值就是(723毫秒生成的id+1)茶凳，怎么確保(723毫秒生成的id+1)這個id值不會被724毫秒，或者725毫秒生成呢播揪，答案是很小幾率重復(fù)的：因為時間戳是id的組成部分贮喧，所以如果毫秒數(shù)不同，id不會重復(fù)的猪狈。但是在極端情況下也是有可能的箱沦，如下：當(dāng)123號索引里的值恰好是第723毫秒所有可能id中的最大值（即：后22bit全是1），對這個值+1罪裹，由于進位饱普，會導(dǎo)致時間戳部分變成724毫秒
具體的思路可以看下面的代碼：http://www.reibang.com/p/b1124283fc43
- 第二種方式：可以利用擴展位
因為Snowflake算法的極限是每毫秒的每一個節(jié)點生成4059個id值运挫，也就是說每毫秒的極限是生成023*4059=4 152 357個id值，這對于中小公司來說根本就是浪費套耕，所以我們可以把這里的位數(shù)給減少一些谁帕，就比如把12位的序列號變成10位，留兩位給時間回撥冯袍，這樣就很容易的解決了時間回撥問題匈挖，如果發(fā)生時間回撥，那么就直接給當(dāng)前id加1
雪法算法Snowflake適合做分布式ID嗎
根據(jù)一系列的分布式id講解康愤，雪法算法Snowflake是目前網(wǎng)上最適合做分布式Id的了儡循，大家如果想用的話，可以根據(jù)我上面的縮小版的Snowflake算法來作為我們開發(fā)中的使用征冷。????乛?乛????
