這是一篇兩年前 Twitter 開發(fā)團隊寫的文章，今天挖出來研究了一下。原文地址 http://engineering.twitter.com/2010/06/announcing-snowflake.html
Twitter 早期用 MySQL 存儲數(shù)據(jù)，隨著用戶的增長，單一的 MySQL 實例沒法承受海量的數(shù)據(jù)，開發(fā)團隊就開始用 Cassandra 和 sharded MySQL 替代原有的系統(tǒng)。然而和 MySQL 不同的是，Cassandra 沒有內(nèi)置為每一條數(shù)據(jù)生成唯一 ID 的功能，因為在一個分布式環(huán)境下，很難有完美的 ID 生成方案。
對于 Twitter 而言，這樣的 ID 生成方案要滿足兩個基本的要求，一是每秒能生成幾十萬條 ID 用于標(biāo)識不同的 tweet；二是這些 ID 應(yīng)該可以有個大致的順序，也就是說發(fā)布時間相近的兩條 tweet，它們的 ID 也應(yīng)當(dāng)相近，這樣才能方便各種客戶端對 tweet 進行排序。
第一個要求意味著 ID 生成要以一種非協(xié)作的（uncoordinated）的方式進行，例如不能有一個全局的原子變量。
第二個要求使得 tweet 按 ID 排序后滿足 k-sorted 條件。如果序列 A 要滿足 k-sorted，當(dāng)且僅當(dāng)對于任意的 p, q，如果 1 <= p <= q - k (1 <= p <= q <= n)，則有 A[p] <= A[q]。換句話說，如果元素 p 排在 q 前面，且相差至少 k 個位置，那么 p 必然小于或等于 q。如果 tweet 序列滿足這個條件，要獲取第 r 條 tweet 之后的消息，只要從第 r - k 條開始查找即可。
Twitter 解決這兩個問題的方案非常簡單高效：每一個 ID 都是 64 位數(shù)字，由時間戳、節(jié)點號和序列編號組成。其中序列編號是每個節(jié)點本地生成的序號，而節(jié)點號則由 ZooKeeper 維護。
具體的參數(shù)可以在這個 IdWorker.scala 中看到。序列編號有 12 位，意味著每個節(jié)點在每毫秒可以產(chǎn)生 4096 個 ID。節(jié)點號在源碼中被分成兩部分，數(shù)據(jù)中心的 ID 和節(jié)點 ID，各自占 5 位。時間戳則是記錄了從 1288834974657 (Thu, 04 Nov 2010 01:42:54 GMT) 這一時刻到當(dāng)前時間所經(jīng)過的毫秒數(shù)，占 41 位（還有一位是符號位，永遠為 0）。