Twitter 早期用 MySQL 存儲數(shù)據(jù)，隨著用戶的增長，單一的 MySQL 實例沒法承受海量的數(shù)據(jù)，后來團隊就研究如何產(chǎn)生完美的自增ID，以滿足兩個基本的要求：
每秒能生成幾十萬條 ID 用于標(biāo)識不同的 記錄；
這些 ID 應(yīng)該可以有個大致的順序，也就是說發(fā)布時間相近的兩條記錄，它們的 ID也應(yīng)當(dāng)相近，這樣才能方便各種客戶端對記錄 進行排序。
Twitter-Snowflake算法就是在這樣的背景下產(chǎn)生的。
Twitter 解決這兩個問題的方案非常簡單高效：每一個 ID 都是 64 位數(shù)字，由時間戳、工作機器節(jié)點和序列號組成， ID是由當(dāng)前所在的機器節(jié)點生成的。如圖：
下面先說明一下各個區(qū)間的作用。
符號位：用于區(qū)分正負(fù)數(shù)。1為負(fù)數(shù)，0為整數(shù)。一般不需要負(fù)數(shù)，所以值固定為0。
時間戳：一共預(yù)留41bit保存毫秒級時間戳。因為毫秒級時間戳長度是13位：41位二進制最大值(T)是：$2^{41}-1 = 2199023255551 $ , 剛好13位?？梢员硎镜哪攴?= T / (3600 * 24 * 365 * 1000) = 69.7年。換算成Unix時間也就是可以表示到：2039-09-07 23:47:35：
大家會覺得這個時間不夠用啊，沒關(guān)系，后面會講如何優(yōu)化。
工作機器：預(yù)留了10bit保存機器ID。只要機器ID不一樣，每毫秒生成的ID是不一樣的。一共可以支持多少臺機器同時生成ID呢？ 答案是 1203 臺（\(2^{10}-1\)）。
如果工作機器比較少，可以使用配置文件來設(shè)置這個id，或者使用隨機數(shù)。如果機器過多就得單獨實現(xiàn)一共工作機器ID分配器了，比如使用redis自增，或者利用Mysql auto_increment機制也可以達到效果。
序列號：序列號一共是12bit，為了處理在同一機器同一毫秒內(nèi)需要給多條消息分配id的情況，一共可以產(chǎn)生4095個序列號(0~4095， \(2^{12}-1\))。
綜上：同一臺機器1毫秒內(nèi)可產(chǎn)生4095個ID，全部機器1毫秒內(nèi)可產(chǎn)生 4095 * 1023 個ID。由于全是在各個機器本地生成，效率非常高。
下面是一個簡單實現(xiàn)：僅有時間戳，機器位為0，序列號為0：
#include <stdio.h>int main(){ long long id; id = 1572057648000 << 22; //相當(dāng)于 id = 1572057648000 << 22 | 0 << 12 | 0; printf("id=%lld\n", id); return 0;}輸出：
id=6593687681236992000代碼實現(xiàn)主要用到了左移和或位運算（或運算），各個語言類似。上面的實現(xiàn)輸出的結(jié)果是一個19位長度的整數(shù)。
1、時間戳優(yōu)化
如果時間戳取當(dāng)前毫秒級時間戳，那么只能表示到2039年，遠(yuǎn)遠(yuǎn)不夠。我們發(fā)現(xiàn)，1970到當(dāng)前時間這個區(qū)間其實是永遠(yuǎn)都不會用了，那么，為何不使用偏移量呢？也就是時間戳部分不直接取當(dāng)前毫秒級時間戳，而是在此基礎(chǔ)上減去一個過去時間：
id = (1572057648000 - 1569859200000) << 22; 輸出：
id=9220959240192000上面代碼中，第一個時間戳是當(dāng)前毫秒級時間戳，第二個則是一個過去時間戳（1569859200000表示2019-10-01 00:00:00）。這樣我們可以表示的年大概是 當(dāng)前年份(例如2019) 69 = 2088 年，很長一段時間內(nèi)都夠用。
2、序列號
序列號默認(rèn)取0，如果已經(jīng)使用了則自增。若自增到4096，也就是同一毫秒內(nèi)的序列號用完了，怎么辦呢？需要等待至下一毫秒。部分代碼示例：
//同一毫秒并發(fā)調(diào)用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 { //同一毫秒沒有重復(fù)的 iw.last_time_stamp = ts;}1、53bits版本：因為js只支持53位bit的數(shù)值
* 0 32 51 53 ----------- ------ ------ |0|time(32) |workid(8) |seq(12) | ----------- ------ ------ 2、其它版本
我們也可以根據(jù)自己的業(yè)務(wù)需求，將不同區(qū)間的bit位進行調(diào)整。機器位和序列號ID并不是必須的，可以合并。或者拆分出更多的區(qū)間表示更多的意義。例如訂單號：
* 0 41 47 59 64 ----------- ------ ------ ------ ------ |0|time(41) |workid(6) |seq(12) | uid(4) ----------- ------ ------ ------ ------ 我們對訂單分16個（2^4）表，每次將 uid & 0xF（也就是 uid & 15）的結(jié)果放到后四位，這樣以后根據(jù)uid查訂單的時候，uid mod 16 就能得到數(shù)據(jù)在哪個分表；同時根據(jù)訂單ID本身也能找到對應(yīng)的分表。示例：
php > echo 1572070381000 << 22 | 1 << 16 | 0 << 4 | (1820 & 15);6593741087309889548php > echo 1572070381000 << 22 | 1 << 16 | 0 << 4 | (5177331 & 15);6593741087309889539驗證測試：
php > echo 1572070381000 << 22 | 1 << 16 | 0 << 4 | (5177331 & 15);6593741087309889539php > echo 6593741087309889548 % 16;12php > echo 1820 % 16;12php > echo 6593741087309889539 % 16;3php > echo 5177331 % 16;3從上面的結(jié)果可以看出來，uid、訂單號都能定位到相同的分表。
對一個2的n次冪的數(shù)num取模，本質(zhì)就是num對應(yīng)二進制的末尾n個bit的和取模。
