Twitter-Snowflake：自增ID算法

簡介

Twitter 早期用 MySQL 存儲數據，隨著用戶的增長，單一的 MySQL 實例沒法承受海量的數據，後來團隊就研究如何產生完美的自增ID，以滿足兩個基本的要求：

• 每秒能生成幾十萬條 ID 用於標識不同的 記錄；
• 這些 ID 應該可以有個大致的順序，也就是說發佈時間相近的兩條記錄，它們的 ID也應當相近，這樣才能方便各種客戶端對記錄 進行排序。

Twitter-Snowflake算法就是在這樣的背景下產生的。

核心

Twitter 解決這兩個問題的方案非常簡單高效：每一個 ID 都是 64 位數字，由時間戳、工作機器節點和序列號組成， ID是由當前所在的機器節點生成的。如圖：

下面先說明一下各個區間的作用。

• 符號位：用於區分正負數。1為負數，0為整數。一般不需要負數，所以值固定為0。
• 時間戳：一共預留41bit保存毫秒級時間戳。因為毫秒級時間戳長度是13位：41位二進制最大值(T)是：241−1=2199023255551241−1=2199023255551 , 剛好13位。可以表示的年份 = T / (3600 * 24 * 365 * 1000) = 69.7年。換算成Unix時間也就是可以表示到：2039-09-07 23:47:35：

大家會覺得這個時間不夠用啊，沒關係，後面會講如何優化。

• 工作機器：預留了10bit保存機器ID。只要機器ID不一樣，每毫秒生成的ID是不一樣的。一共可以支持多少臺機器同時生成ID呢？ 答案是 1023 臺（210−1210−1）。如果工作機器比較少，可以使用配置文件來設置這個id，或者使用隨機數。如果機器過多就得單獨實現一共工作機器ID分配器了，比如使用redis自增，或者利用Mysql auto_increment機制也可以達到效果。
• 序列號：序列號一共是12bit，為了處理在同一機器同一毫秒內需要給多條消息分配id的情況，一共可以產生4095個序列號(0~4095， 212−1212−1)。

綜上：同一臺機器1毫秒內可產生4095個ID，全部機器1毫秒內可產生 4095 * 1023 個ID。由於全是在各個機器本地生成，效率非常高。

簡單實現

下面是一個簡單實現：僅有時間戳，機器位為0，序列號為0：

#include 

int main()
{
 long long id;
 id = 1572057648000 << 22; //相當於 id = 1572057648000 << 22 | 0 << 12 | 0;
 printf("id=%lld\n", id);
 
 return 0;
}

輸出：

id=6593687681236992000

代碼實現主要用到了左移和或位運算（或運算），各個語言類似。上面的實現輸出的結果是一個19位長度的整數。

優化

1、時間戳優化

如果時間戳取當前毫秒級時間戳，那麼只能表示到2039年，遠遠不夠。我們發現，1970到當前時間這個區間其實是永遠都不會用了，那麼，為何不使用偏移量呢？也就是時間戳部分不直接取當前毫秒級時間戳，而是在此基礎上減去一個過去時間：

id = (1572057648000 - 1569859200000) << 22; 

輸出：

id=9220959240192000

上面代碼中，第一個時間戳是當前毫秒級時間戳，第二個則是一個過去時間戳（1569859200000表示2019-10-01 00:00:00）。這樣我們可以表示的年大概是 當前年份(例如2019) + 69 = 2088 年，很長一段時間內都夠用。

2、序列號

序列號默認取0，如果已經使用了則自增。若自增到4096，也就是同一毫秒內的序列號用完了，怎麼辦呢？需要等待至下一毫秒。部分代碼示例：

//同一毫秒併發調用
if (ts == (iw.last_time_stamp)) {
 //序列號自增
 iw.sequence = (iw.sequence+1) & MASK_SEQUENCE;

 //序列號自增到最大值4096，4095 & 4096 = 0
 if (iw.sequence == 0) {
 //等待至下一毫秒
 ts = time_re_gen(ts);
 }
} else { //同一毫秒沒有重複的
 iw.last_time_stamp = ts;
}

算法變種

1、53bits版本：因為js只支持53位bit的數值

* 0 32 51 53
+-----------+------+------+
|0|time(32) |workid(8) |seq(12) |
+-----------+------+------+

2、其它版本

我們也可以根據自己的業務需求，將不同區間的bit位進行調整。機器位和序列號ID並不是必須的，可以合併。或者拆分出更多的區間表示更多的意義。例如訂單號：

* 0 41 47 59 64
+-----------+------+------+------+------+
|0|time(41) |workid(6) |seq(12) | uid(4)
+-----------+------+------+------+------+

我們對訂單分16個（2^4）表，每次將 uid & 0xF（也就是 uid & 15）的結果放到後四位，這樣以後根據uid查訂單的時候，uid mod 16 就能得到數據在哪個分表；同時根據訂單ID本身也能找到對應的分表。示例：

php > echo 1572070381000 << 22 | 1 << 16 | 0 << 4 | (1820 & 15);
6593741087309889548
php > echo 1572070381000 << 22 | 1 << 16 | 0 << 4 | (5177331 & 15);
6593741087309889539

驗證測試：

php > echo 1572070381000 << 22 | 1 << 16 | 0 << 4 | (5177331 & 15);
6593741087309889539
php > echo 6593741087309889548 % 16;
12
php > echo 1820 % 16;
12
php > echo 6593741087309889539 % 16;
3
php > echo 5177331 % 16;
3

從上面的結果可以看出來，uid、訂單號都能定位到相同的分表。

對一個2的n次冪的數num取模(2^n)，本質就是num對應二進制的末尾n個bit的和取模。

代碼實現

參考網上其它語言的版本，自己寫了C和PHP版本的：

1、snowflake-c/snowflake.c at master · 52fhy/snowflake-c

https://github.com/52fhy/snowflake-c

2、52fhy/IDWork: Twitter的 Snowflake的PHP版

https://github.com/52fhy/IDWork

3、github上其它語言版本：

• go語言版本：已用於生產環境，穩定：https://github.com/bwmarrin/snowflake
• php c擴展版：未使用過fgy58963/php_snowflake: https://github.com/fgy58963/php_snowflake

參考

1、Twitter-Snowflake，64位自增ID算法詳解 - 漫漫路

https://www.lanindex.com/twitter-snowflake%EF%BC%8C64%E4%BD%8D%E8%87%AA%E5%A2%9Eid%E7%AE%97%E6%B3%95%E8%AF%A6%E8%A7%A3/

2、多key業務，數據庫水平切分架構一次搞定

https://mp.weixin.qq.com/s/PCzRAZa9n4aJwHOX-kAhtA