詳解Twitter開源分布式自增ID算法snowflake，附演算驗證過程

1.snowflake簡介

網際網路快速發展的今天，分布式應用系統已經見怪不怪，在分布式系統中，我們需要各種各樣的ID，既然是ID那麼必然是要保證全局唯一，除此之外，不同當業務還需要不同的特性，比如像并發巨大的業務要求ID生成效率高，吞吐大；比如某些銀行類業務，需要按每日日期制定交易流水号；又比如我們希望使用者的ID是随機的，無序的，純數字的，且位數長度是小于10位的。等等，不同的業務場景需要的ID特性各不一樣，于是，衍生了各種ID生成器，但大多數利用資料庫控制ID的生成，性能受資料庫并發能力限制，那麼有沒有一款不需要依賴任何中間件（如資料庫，分布式緩存服務等）的ID生成器呢？本着取之于開源，用之于開源的原則，今天，特此介紹Twitter開源的一款分布式自增ID算法snowflake，并附上算法原理推導和演算過程！

snowflake算法是一款本地生成的（ID生成過程不依賴任何中間件，無網絡通信），保證ID全局唯一，并且ID總體有序遞增，性能每秒生成300w＋。

2.snowflake算法原理

snowflake生産的ID二進制結構表示如下(每部分用-分開):

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+，效率之高由此可見。

3.snowflake算法源碼（java版）

測試用例：

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

說明：

演算使用的對象執行個體：SnowflakeIdFactory idWorker = new SnowflakeIdFactory(1, 2);

運作時資料workerId＝1，datacenterId＝2，分别表示機器執行個體的生産者編号，資料中心編号；

sequence＝0表示每毫秒生産ID從0開始計數遞增；

以下演算基于時間戳＝1482394743339時刻進行推導。

一句話描述：以下演算模拟了1482394743339這一毫秒時刻，workerId＝1，datacenterId＝2的id生成器，生産第一個id的過程。

我自己弄的一個

end！

參考

<a href="https://github.com/twitter/snowflake">https://github.com/twitter/snowflake</a>

<a href="http://www.cnblogs.com/relucent/p/4955340.html">http://www.cnblogs.com/relucent/p/4955340.html</a>