Twitter分布式自增ID算法Snowflake

在分布式系統中，需要生成全局UID的場合還是比較多的，twitter的snowflake解決了這種需求，實作也還是很簡單的，除去配置資訊，核心代碼就是毫秒級時間41位機器ID 10位毫秒内序列12位。

在上面的字元串中，第一位為未使用（實際上也可作為long的符号位），接下來的41位為毫秒級時間，然後5位datacenter辨別位，5位機器ID（并不算辨別符，實際是為線程辨別），然後12位該毫秒内的目前毫秒内的計數，加起來剛好64位，為一個Long型。

這樣的好處是，整體上按照時間自增排序，并且整個分布式系統内不會産生ID碰撞（由datacenter和機器ID作區分），并且效率較高，經測試，snowflake每秒能夠産生26萬ID左右，完全滿足需要。

把時間戳，工作機器id，序列号組合在一起。

除了最高位bit标記為不可用以外，其餘三組bit占位均可浮動，看具體的業務需求而定。預設情況下41bit的時間戳可以支援該算法使用到2082年，10bit的工作機器id可以支援1023台機器，序列号支援1毫秒産生4095個自增序列id。下文會具體分析。

這裡時間戳的細度是毫秒級，具體代碼如下，建議使用64位linux系統機器，因為有vdso，gettimeofday()在使用者态就可以完成操作，減少了進入核心态的損耗。

uint64_t generateStamp()
{
    timeval tv;
    gettimeofday(&tv, 0);
    return(uint64_t)tv.tv_sec * 1000 + (uint64_t)tv.tv_usec / 1000;
}

預設情況下有41個bit可以供使用，那麼一共有T（1llu << 41）毫秒供你使用配置設定，年份 = T / (3600 * 24 * 365 * 1000) = 69.7年。如果你隻給時間戳配置設定39個bit使用，那麼根據同樣的算法最後年份 = 17.4年。

嚴格意義上來說這個bit段的使用可以是程序級，機器級的話你可以使用MAC位址來唯一标示工作機器，工作程序級可以使用IP+Path來區分工作程序。如果工作機器比較少，可以使用配置檔案來設定這個id是一個不錯的選擇，如果機器過多配置檔案的維護是一個災難性的事情。

這裡的解決方案是需要一個工作id配置設定的程序，可以使用自己編寫一個簡單程序來記錄配置設定id，或者利用Mysql auto_increment機制也可以達到效果。

Twitter分布式自增ID算法Snowflake

工作程序與工作id配置設定器隻是在工作程序啟動的時候互動一次，然後工作程序可以自行将配置設定的id資料落檔案，下一次啟動直接讀取檔案裡的id使用。

PS：這個工作機器id的bit段也可以進一步拆分，比如用前5個bit标記程序id，後5個bit标記線程id之類:D

序列号就是一系列的自增id（多線程建議使用atomic），為了處理在同一毫秒内需要給多條消息配置設定id，若同一毫秒把序列号用完了，則“等待至下一毫秒”。

uint64_t waitNextMs(uint64_t lastStamp)
{
    uint64_t cur = 0;
    do{
        cur = generateStamp();
    }while(cur <= lastStamp);
    returncur;
}

總體來說，是一個很高效很友善的GUID産生算法，一個int64_t字段就可以勝任，不像現在主流128bit的GUID算法，即使無法保證嚴格的id序列性，但是對于特定的業務，比如用做遊戲伺服器端的GUID産生會很友善。另外，在多線程的環境下，序列号使用atomic可以在代碼實作上有效減少鎖的密度。

繼續閱讀