超精妙!Twitter開源分散式自增ID演算法snowflake,附演算驗證過程

語言: CN / TW / HK

點選卡片關注我們,更多技術乾貨,及時為您送達!

1. Snowflake 簡介

網際網路快速發展的今天,分散式應用系統已經見怪不怪,在分散式系統中,我們需要各種各樣的ID,既然是ID那麼必然是要保證全域性唯一。

除此之外,不同的業務還需要不同的特性,比如像併發巨大的業務要求ID生成效率高,吞吐大;比如某些銀行類業務,需要按每日日期制定交易流水號;又比如我們希望使用者的ID是隨機的,無序的,純數字的,且位數長度是小於10位的,等等。

不同的業務場景需要的ID特性各不一樣,於是,衍生了各種ID生成器,但大多數利用資料庫控制ID的生成,效能受資料庫併發能力限制,那麼有沒有一款不需要依賴任何中介軟體(如資料庫,分散式快取服務等)的ID生成器呢?

本著取之於開源,用之於開源的原則,今天,特此介紹Twitter開源的一款分散式自增ID演算法snowflake,並附上演算法原理推導和演算過程!

Snowflake演算法是一款本地生成的(ID生成過程不依賴任何中介軟體,無網路通訊),保證ID全域性唯一,並且ID總體有序遞增,效能每秒生成300w+

2. Snowflake 演算法原理

snowflake生產的ID是一個18位的long型數字,二進位制結構表示如下(每部分用-分開):

0 - 00000000 00000000 00000000 00000000 00000000 0 - 00000 - 00000 - 00000000 0000

第一位未使用,接下來的41位為毫秒級時間(41位的長度可以使用69年,從1970-01-01 08:00:00),然後是5位datacenterId(最大支援2^5=32個,二進位制表示從00000-11111,也即是十進位制0-31),和5位workerId(最大支援2^5=32個,原理同datacenterId),所以datacenterId*workerId最多支援部署1024個節點,最後12位是毫秒內的計數(12位的計數順序號支援每個節點每毫秒產生2^12=4096個ID序號)。

所有位數加起來共64位,恰好是一個Long型(轉換為字串長度為18)。

單臺機器例項,通過時間戳保證前41位是唯一的,分散式系統多臺機器例項下,通過對每個機器例項分配不同的datacenterId和workerId避免中間的10位碰撞。最後12位每毫秒從0遞增生產ID,再提一次:每毫秒最多生成4096個ID,每秒可達4096000個。理論上,只要CPU計算能力足夠,單機每秒可生產400多萬個,實測300w+,效率之高由此可見。

該節改編自:http://www.cnblogs.com/relucent/p/4955340.html

3. Snowflake 演算法原始碼(java版)

@ToString
@Slf4j
public class SnowflakeIdFactory {

private final long twepoch = 1288834974657L;
private final long workerIdBits = 5L;
private final long datacenterIdBits = 5L;
private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
private final long sequenceBits = 12L;
private final long workerIdShift = sequenceBits;
private final long datacenterIdShift = sequenceBits + workerIdBits;
private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
private final long sequenceMask = -1L ^ (-1L << sequenceBits);

private long workerId;
private long datacenterId;
private long sequence = 0L;
private long lastTimestamp = -1L;

public SnowflakeIdFactory(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;
}

public synchronized long nextId() {
long timestamp = timeGen();
if (timestamp < lastTimestamp) {
//伺服器時鐘被調整了,ID生成器停止服務.
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & sequenceMask;
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0L;
}

lastTimestamp = timestamp;
return ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence;
}

protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}

protected long timeGen() {
return System.currentTimeMillis();
}

public static void testProductIdByMoreThread(int dataCenterId, int workerId, int n) throws InterruptedException {
List<Thread> tlist = new ArrayList<>();
Set<Long> setAll = new HashSet<>();
CountDownLatch cdLatch = new CountDownLatch(10);
long start = System.currentTimeMillis();
int threadNo = dataCenterId;
Map<String,SnowflakeIdFactory> idFactories = new HashMap<>();
for(int i=0;i<10;i++){
//用執行緒名稱做map key.
idFactories.put("snowflake"+i,new SnowflakeIdFactory(workerId, threadNo++));
}
for(int i=0;i<10;i++){
Thread temp =new Thread(new Runnable() {
@Override
public void run() {
Set<Long> setId = new HashSet<>();
SnowflakeIdFactory idWorker = idFactories.get(Thread.currentThread().getName());
for(int j=0;j<n;j++){
setId.add(idWorker.nextId());
}
synchronized (setAll){
setAll.addAll(setId);
log.info("{}生產了{}個id,併成功加入到setAll中.",Thread.currentThread().getName(),n);
}
cdLatch.countDown();
}
},"snowflake"+i);
tlist.add(temp);
}
for(int j=0;j<10;j++){
tlist.get(j).start();
}
cdLatch.await();

long end1 = System.currentTimeMillis() - start;

log.info("共耗時:{}毫秒,預期應該生產{}個id, 實際合併總計生成ID個數:{}",end1,10*n,setAll.size());

}

public static void testProductId(int dataCenterId, int workerId, int n){
SnowflakeIdFactory idWorker = new SnowflakeIdFactory(workerId, dataCenterId);
SnowflakeIdFactory idWorker2 = new SnowflakeIdFactory(workerId+1, dataCenterId);
Set<Long> setOne = new HashSet<>();
Set<Long> setTow = new HashSet<>();
long start = System.currentTimeMillis();
for (int i = 0; i < n; i++) {
setOne.add(idWorker.nextId());//加入set
}
long end1 = System.currentTimeMillis() - start;
log.info("第一批ID預計生成{}個,實際生成{}個<<<<*>>>>共耗時:{}",n,setOne.size(),end1);

for (int i = 0; i < n; i++) {
setTow.add(idWorker2.nextId());//加入set
}
long end2 = System.currentTimeMillis() - start;
log.info("第二批ID預計生成{}個,實際生成{}個<<<<*>>>>共耗時:{}",n,setTow.size(),end2);

setOne.addAll(setTow);
log.info("合併總計生成ID個數:{}",setOne.size());

}

public static void testPerSecondProductIdNums(){
SnowflakeIdFactory idWorker = new SnowflakeIdFactory(1, 2);
long start = System.currentTimeMillis();
int count = 0;
for (int i = 0; System.currentTimeMillis()-start<1000; i++,count=i) {
/** 測試方法一: 此用法純粹的生產ID,每秒生產ID個數為300w+ */
idWorker.nextId();
/** 測試方法二: 在log中列印,同時獲取ID,此用法生產ID的能力受限於log.error()的吞吐能力.
* 每秒徘徊在10萬左右. */

//log.error("{}",idWorker.nextId());
}
long end = System.currentTimeMillis()-start;
System.out.println(end);
System.out.println(count);
}

public static void main(String[] args) {
/** case1: 測試每秒生產id個數?
* 結論: 每秒生產id個數300w+ */

//testPerSecondProductIdNums();

/** case2: 單執行緒-測試多個生產者同時生產N個id,驗證id是否有重複?
* 結論: 驗證通過,沒有重複. */

//testProductId(1,2,10000);//驗證通過!
//testProductId(1,2,20000);//驗證通過!

/** case3: 多執行緒-測試多個生產者同時生產N個id, 全部id在全域性範圍內是否會重複?
* 結論: 驗證通過,沒有重複. */

try {
testProductIdByMoreThread(1,2,100000);//單機測試此場景,效能損失至少折半!
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}

測試用例:

/** case1: 測試每秒生產id個數?
* 結論: 每秒生產id個數300w+ */
//testPerSecondProductIdNums();

/** case2: 單執行緒-測試多個生產者同時生產N個id,驗證id是否有重複?
* 結論: 驗證通過,沒有重複. */
//testProductId(1,2,10000);//驗證通過!
//testProductId(1,2,20000);//驗證通過!

/** case3: 多執行緒-測試多個生產者同時生產N個id, 全部id在全域性範圍內是否會重複?
* 結論: 驗證通過,沒有重複. */
try {
testProductIdByMoreThread(1,2,100000);//單機測試此場景,效能損失至少折半!
} catch (InterruptedException e) {
e.printStackTrace();
}

4. Snowflake 演算法推導和演算過程

說明:

  • 演算使用的物件例項:SnowflakeIdFactory idWorker = new SnowflakeIdFactory(1, 2);

  • 執行時資料 workerId=1,datacenterId=2,分別表示機器例項的生產者編號,資料中心編號;

  • sequence=0表示每毫秒生產ID從0開始計數遞增;

  • 以下演算基於時間戳=1482394743339 時刻進行推導。

一句話描述:以下演算模擬了1482394743339這一毫秒時刻,workerId=1,datacenterId=2的id生成器,生產第一個id的過程。

Snowflake演算法推導和演算過程

圖片為作者原創,畫圖不易,轉載請務必註明原出處!http://changle.blog.csdn.net/article/details/54668031

End!

參考

  • http://github.com/twitter/snowflake

  • http://www.cnblogs.com/relucent/p/4955340.html

作者:常樂_smile

http://changle.blog.csdn.net/article/details/54668031

PS:文章有幫助的話,點贊、在看、轉發吧!

-----------------------------------------------

點選卡片關注我們,更多技術乾貨,及時為您送達!

眾號“邏魔程式碼”所發表內容註明來源的,版權歸原出處所有(無法查證版權的或者未註明出處的均來自網路,系轉載,轉載的目的在於傳遞更多資訊,版權屬於原作者。如有侵權,請聯絡,筆者會第一時間刪除處理!