Twitter早期使用MySQL存儲數(shù)據(jù),隨著用戶的增長,單一MySQL實例無法支持海量數(shù)據(jù),Twitter開始把存儲系統(tǒng)從MySQL遷移到Cassandra,但是Cassandra沒有內(nèi)置的順序ID生成機制,因此Twitter開發(fā)了一套分布式系統(tǒng)全局唯一ID生成服務(wù):Snowflake。
對于Twitter而言,必須滿足每秒上萬條消息的請求,并且每條消息能夠分配一個全局唯一的ID,因此,ID生成服務(wù)要求必須滿足高性能(>10K ids/s)、低延遲(<2ms)、高可用的特性,同時生成的ID還可以進(jìn)行大致的排序,以方便客戶端的排序。
Snowflake滿足了以上的需求。Snowflake生成的每一個ID都是64位的整型數(shù),它的核心算法也比較簡單高效,結(jié)構(gòu)如下:
41位的時間序列,精確到毫秒級,41位的長度可以使用69年。時間位還有一個很重要的作用是可以根據(jù)時間進(jìn)行排序。
10位的機器標(biāo)識,10位的長度最多支持部署1024個節(jié)點。
12位的計數(shù)序列號,序列號即一系列的自增id,可以支持同一節(jié)點同一毫秒生成多個ID序號,12位的計數(shù)序列號支持每個節(jié)點每毫秒產(chǎn)生4096個ID序號。
最高位是符號位,始終為0,不可用。
Snowflake是一個高效方便的GUID生成算法,可用性強,速度快并且可以根據(jù)時間排序。但是,就目前來看部署Snowflake需要引入ZooKeeper和Snowflake專用服務(wù)器,Twitter也聲明希望可以讓Snowflake運行在Twitter以外更多的環(huán)境中,如果可以實現(xiàn),Snowflake的使用就會更方便。
Snowflake是用Scala實現(xiàn)的,如果想要了解更多細(xì)節(jié),請移步至Snowflake項目。