雪花算法（SnowFlake）

解決方法：

目前成都創新互聯公司已為上千余家的企業提供了網站建設、域名、網頁空間、網站托管維護、企業網站設計、綏德網站維護等服務，公司將堅持客戶導向、應用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協力一起成長，共同發展。

首先，SnowFlake的末尾12位是序列號，用來記錄同一毫秒內產生的不同id，同一毫秒總共可以產生4096個id，每一毫秒的序列號都是從0這個基礎序列號開始遞增。假設我們的業務系統在單機上的QPS為3w/s，那么其實平均每毫秒只需要產生30個id即可，遠沒有達到設計的4096，也就是說通常情況下序列號的使用都是處在一個低水位，當發生時鐘回撥的時候，這些尚未被使用的序號就可以派上用場了。

因此，可以對給定的基礎序列號稍加修改，后面每發生一次時鐘回撥就將基礎序列號加上指定的步長，例如開始時是從0遞增，發生一次時鐘回撥后從1024開始遞增，再發生一次時鐘回撥則從2048遞增，這樣還能夠滿足3次的時鐘回撥到同一時間點。

改變原來的末尾sequence生成方法：

snowflake算法給workerId預留了10位，即workId的取值范圍為[0, 1023]，事實上實際生產環境不大可能需要部署1024個分布式ID服務，所以：將workerId取值范圍縮小為[0, 511]，[512, 1023]這個范圍的workerId當做備用workerId。workId為0的備用workerId是512，workId為1的備用workerId是513，以此類推……

如何保證數據庫集群中id的唯一性，假設每秒鐘并發20萬次

用雪花算法的工具類,1秒內可以生成26萬不重復的值,數據庫的主鍵不要自增,手動設置

package?entity;

import?java.lang.management.ManagementFactory;

import?java.net.InetAddress;

import?java.net.NetworkInterface;

/**

*?p名稱：IdWorker.java/p

*?p描述：分布式自增長ID/p

*?pre

*?????Twitter的?Snowflake　JAVA實現方案

*?/pre

*?核心代碼為其IdWorker這個類實現，其原理結構如下，我分別用一個0表示一位，用—分割開部分的作用：

*?1||0---0000000000?0000000000?0000000000?0000000000?0?---?00000?---00000?---000000000000

*?在上面的字符串中，第一位為未使用（實際上也可作為long的符號位），接下來的41位為毫秒級時間，

*?然后5位datacenter標識位，5位機器ID（并不算標識符，實際是為線程標識），

*?然后12位該毫秒內的當前毫秒內的計數，加起來剛好64位，為一個Long型。

*?這樣的好處是，整體上按照時間自增排序，并且整個分布式系統內不會產生ID碰撞（由datacenter和機器ID作區分），

*?并且效率較高，經測試，snowflake每秒能夠產生26萬ID左右，完全滿足需要。

*?p

*?64位ID?(42(毫秒)+5(機器ID)+5(業務編碼)+12(重復累加))

*

*?@author?Polim

*/

public?class?IdWorker?{

//?時間起始標記點，作為基準，一般取系統的最近時間（一旦確定不能變動）

private?final?static?long?twepoch?=?1288834974657L;

//?機器標識位數

private?final?static?long?workerIdBits?=?5L;

//?數據中心標識位數

private?final?static?long?datacenterIdBits?=?5L;

//?機器ID最大值

private?final?static?long?maxWorkerId?=?-1L?^?(-1L??workerIdBits);

//?數據中心ID最大值

private?final?static?long?maxDatacenterId?=?-1L?^?(-1L??datacenterIdBits);

//?毫秒內自增位

private?final?static?long?sequenceBits?=?12L;

//?機器ID偏左移12位

private?final?static?long?workerIdShift?=?sequenceBits;

//?數據中心ID左移17位

private?final?static?long?datacenterIdShift?=?sequenceBits?+?workerIdBits;

//?時間毫秒左移22位

private?final?static?long?timestampLeftShift?=?sequenceBits?+?workerIdBits?+?datacenterIdBits;

private?final?static?long?sequenceMask?=?-1L?^?(-1L??sequenceBits);

/*?上次生產id時間戳?*/

private?static?long?lastTimestamp?=?-1L;

//?0，并發控制

private?long?sequence?=?0L;

private?final?long?workerId;

//?數據標識id部分

private?final?long?datacenterId;

public?IdWorker(){

this.datacenterId?=?getDatacenterId(maxDatacenterId);

this.workerId?=?getMaxWorkerId(datacenterId,?maxWorkerId);

}

/**

*?@param?workerId

*????????????工作機器ID

*?@param?datacenterId

*????????????序列號

*/

public?IdWorker(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

*/

public?synchronized?long?nextId()?{

long?timestamp?=?timeGen();

if?(timestamp??lastTimestamp)?{

throw?new?RuntimeException(String.format("Clock?moved?backwards.??Refusing?to?generate?id?for?%d?milliseconds",?lastTimestamp?-?timestamp));

}

if?(lastTimestamp?==?timestamp)?{

//?當前毫秒內，則+1

sequence?=?(sequence?+?1)??sequenceMask;

if?(sequence?==?0)?{

//?當前毫秒內計數滿了，則等待下一秒

timestamp?=?tilNextMillis(lastTimestamp);

}

}?else?{

sequence?=?0L;

}

lastTimestamp?=?timestamp;

//?ID偏移組合生成最終的ID，并返回ID

long?nextId?=?((timestamp?-?twepoch)??timestampLeftShift)

|?(datacenterId??datacenterIdShift)

|?(workerId??workerIdShift)?|?sequence;

return?nextId;

}

private?long?tilNextMillis(final?long?lastTimestamp)?{

long?timestamp?=?this.timeGen();

while?(timestamp?=?lastTimestamp)?{

timestamp?=?this.timeGen();

}

return?timestamp;

}

private?long?timeGen()?{

return?System.currentTimeMillis();

}

/**

*?p

*?獲取?maxWorkerId

*?/p

*/

protected?static?long?getMaxWorkerId(long?datacenterId,?long?maxWorkerId)?{

StringBuffer?mpid?=?new?StringBuffer();

mpid.append(datacenterId);

String?name?=?ManagementFactory.getRuntimeMXBean().getName();

if?(!name.isEmpty())?{

/*

*?GET?jvmPid

*/

mpid.append(name.split("@")[0]);

}

/*

*?MAC?+?PID?的?hashcode?獲取16個低位

*/

return?(mpid.toString().hashCode()??0xffff)?%?(maxWorkerId?+?1);

}

/**

*?p

*?數據標識id部分

*?/p

*/

protected?static?long?getDatacenterId(long?maxDatacenterId)?{

long?id?=?0L;

try?{

InetAddress?ip?=?InetAddress.getLocalHost();

NetworkInterface?network?=?NetworkInterface.getByInetAddress(ip);

if?(network?==?null)?{

id?=?1L;

}?else?{

byte[]?mac?=?network.getHardwareAddress();

id?=?((0x000000FF??(long)?mac[mac.length?-?1])

|?(0x0000FF00??(((long)?mac[mac.length?-?2])??8)))??6;

id?=?id?%?(maxDatacenterId?+?1);

}

}?catch?(Exception?e)?{

System.out.println("?getDatacenterId:?"?+?e.getMessage());

}

return?id;

}

public?static?void?main(String[]?args)?{

//推特??26萬個不重復的ID

IdWorker?idWorker?=?new?IdWorker(0,0);

for?(int?i?=?0;?i?2600?;?i++)?{

System.out.println(idWorker.nextId());

}

}

}

雪花算法源碼

(1)開源ID:Twitter開源開源的分布式ID生成算法

(2)64 bit自增:使用一個64位的long型數字作為一個全局ID,且引入了時間戳概念,基本上保證自增的

(3)64位中,第一位是不用的,其中的41位作為毫秒數,10位(5+5)作為機房機器id,剩下的12位作為序列號

第一個部分，是 1 個 bit: 如果是 1，那么都是負數，但是我們生成的 id 都是正數，所以第一個 bit 統一都是 0。

第二個部分是 41 個 bit: 表示的是時間戳。41 bit 可以標識 2 ^ 41 - 1 個毫秒值，換算成年就是表示 69 年的時間。

第三個部分是 5 個 bit: 表示的是機房 id，10001。

第四個部分是 5 個 bit: 表示的是機器 id，11001。部署在 2^10 臺機器上，也就是 1024 臺機器。

第五個部分是 12 個 bit: 表示的序號，就是某個機房某臺機器上這一毫秒內同時生成的 id 的序號，0000 0000 0000。記錄同一個毫秒內產生的不同 id

(1)請求:某個微服務service需要生成一個全局唯一Id,那就可以給部署了snokeFlake算法的系統發送一個請求來生成唯一Id

(2)二進制生成:接著會用"二進制位運算"來生成一個64位的long型id,并且64位第一個bit無意義,算法系統當然知道當前的時間戳,自己的機房和機器

(3)毫秒內累加序號:最后在判斷下這是這個毫秒下的第幾個請求,給這次生成的Id的請求累加一個序號,作為最后的12個bit

(4)算法保證唯一:在同一毫秒下,同一個機房下的一臺機器,生成一個唯一的id(12位=4096個), 如果一毫秒生成的Id數量超過了4095,就知會等待下一個毫秒在生成!但是估計沒有請求能有這么頻繁!