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