分散式系統中的唯一 ID 生成器

分散式系統的 ID 生成

在分散式系統當中，如何在每部機器獨立的生成唯一 ID 是一項蠻重要的議題，作為每筆資料的主鍵 (primary key)，ID 的唯一性是必須要被謹慎維護的，如果採用直觀的 auto increment 遞增方法，很可能會因為 race condition 而導致產生出重複 ID 的嚴重問題。因此下面會介紹幾種在分散式系統中能夠用來協調、生成唯一 ID 的一些方法。

Multi-master replication

這個方法其實算是 auto increment 的一種衍生，它的概念是根據系統中的機器數量來進行 ID 的遞增，有別於一般的 auto increment 是每次將 ID 的值 +1，Multi-master replication 則是在每次把 ID 的值 +k，而這個 k 就是系統中的機器數量，這樣的做法可以避免機器之間產生出重複的 ID。不過這個方法對於多個分散式系統之間的協調性就沒有很好的處理，同時對於增加或移除機器時的擴展性也不是特別好。

UUID

UUID 是一種常見且簡便的生成唯一 ID 的方法，UUID 是一種 128 位元的辨識碼，它的特點是不需要一個中央的設備或機構來統合就可以在系統中的各個機器裡面獨立的生成，且 UUID 本身的重複率是低到近乎為零的程度，可以被忽略不計。因此在沒有特別需求的狀況下 UUID 是一個非常適合作為分散式系統中 ID 生成的方法。

不過 UUID 也會有一些由於它的特性所帶來的限制，例如 128 位元的長度可能過長、其 ID 的組成有包含非數字，以及 ID 本身並沒有遞增的特性，這些限制可能對於某些應用來說就會有一些侷限性。

Ticket server

Ticket server 是由 Flickr 所開發的一種唯一 ID 的生成方法，它的概念是運用一個中央伺服器來進行 ID 生成的管理分配，生成的方法也是採用一般的 auto increment，詳細的資訊可以參考它們的部落格文章。

這種方法對於中小型的應用來說在實作上相當方便且簡易，不過最大的問題當然是會面臨到單點故障的風險，如果想要用多個中央伺服器來增加可用性的話，又會衍生出資料同步的問題需要處理。

Twitter snowflake

snowflake 是 Twitter 開法的 ID 生成系統，其核心的概念相當有趣且特別，它將 ID 拆分成好幾個區塊並以不同的意義來賦值，最後形成一個唯一的 ID，可以參考下圖的例子所形成的一個 64 位元的 ID。

snowflake-id

各個分段所代表的意義如下：

第一個 0 是一個保留的位元以供未來使用
時間戳是代表 ID 生成的相對時間，通常會以一個自行定義的起始時間為起點，到生成 ID 當下所經過的毫秒數即是這個時間戳的值 (類似 Unix time 的概念)
資料中心 ID 表示該機器所在的資料中心的編號
機器 ID 則是該機器在自己的資料中心裡面的機器編號
序列編號是同一部機器在生成 ID 時，會以每次 +1 的方式去遞增的編號，並在每毫秒重新歸零 (因為時間戳更新了，所以可以重新計算序列編號)

另外，這段 ID 當中各個分段的大小都可以根據需求自行來調整，像是可以根據系統的規模來調整資料中心 ID 和機器 ID 的長度，以及評估應用的運行時間來調控時間戳的長度讓 ID 可以橫跨更久的時間等等。