應用場景(Scenario)

現實中很多業務都有生成唯一ID的需求，例如：

• 用戶ID
• 微博ID
• 聊天消息ID
• 帖子ID
• 訂單ID

需求(Needs)

這個ID往往會作為數據庫主鍵，所以需要保證全局唯一。數據庫會在這個字段上建立聚集索引(Clustered Index，參考 MySQL InnoDB)，即該字段會影響各條數據再物理存儲上的順序。

ID還要盡可能短，節省內存，讓數據庫索引效率更高。基本上64位整數能夠滿足絕大多數的場景，但是如果能做到比64位更短那就更好了。需要根據具體業務進行分析，預估出ID的最大值，這個最大值通常比64位整數的上限小很多，于是我們可以用更少的bit表示這個ID。

查詢的時候，往往有分頁或者排序的需求，所以需要給每條數據添加一個時間字段，并在其上建立普通索引(Secondary Index)。但是普通索引的訪問效率比聚集索引慢，如果能夠讓ID按照時間粗略有序，則可以省去這個時間字段。為什么不是按照時間精確有序呢？因為按照時間精確有序是做不到的，除非用一個單機算法，在分布式場景下做到精確有序性能一般很差。

這就引出了ID生成的三大核心需求：

• 全局唯一(unique)
• 按照時間粗略有序(sortable by time)
• 盡可能短

下面介紹一些常用的生成ID的方法。

UUID

用過MongoDB的人會知道，MongoDB會自動給每一條數據賦予一個唯一的ObjectId,保證不會重復，這是怎么做到的呢？實際上它用的是一種UUID算法，生成的ObjectId占12個字節，由以下幾個部分組成，

• 4個字節表示的Unix timestamp,
• 3個字節表示的機器的ID
• 2個字節表示的進程ID
• 3個字節表示的計數器

UUID是一類算法的統稱，具體有不同的實現。UUID的有點是每臺機器可以獨立產生ID，理論上保證不會重復，所以天然是分布式的，缺點是生成的ID太長，不僅占用內存，而且索引查詢效率低。

多臺MySQL服務器

既然MySQL可以產生自增ID，那么用多臺MySQL服務器，能否組成一個高性能的分布式發號器呢？ 顯然可以。

假設用8臺MySQL服務器協同工作，第一臺MySQL初始值是1，每次自增8，第二臺MySQL初始值是2，每次自增8，依次類推。前面用一個 round-robin load balancer 擋著，每來一個請求，由 round-robin balancer 隨機地將請求發給8臺MySQL中的任意一個，然后返回一個ID。

Flickr就是這么做的，僅僅使用了兩臺MySQL服務器。可見這個方法雖然簡單無腦，但是性能足夠好。不過要注意，在MySQL中，不需要把所有ID都存下來，每臺機器只需要存一個MAX_ID就可以了。這需要用到MySQL的一個REPLACE INTO特性。

這個方法跟單臺數據庫比，缺點是ID是不是嚴格遞增的，只是粗略遞增的。不過這個問題不大，我們的目標是粗略有序，不需要嚴格遞增。

Twitter Snowflake

比如 Twitter 有個成熟的開源項目，就是專門生成ID的，Twitter Snowflake?。Snowflake的核心算法如下：

最高位不用，永遠為0，其余三組bit占位均可浮動，看具體的業務需求而定。默認情況下41bit的時間戳可以支持該算法使用到2082年，10bit的工作機器id可以支持1023臺機器，序列號支持1毫秒產生4095個自增序列id。

Instagram用了類似的方案，41位表示時間戳，13位表示shard Id(一個shard Id對應一臺PostgreSQL機器),最低10位表示自增ID，怎么樣，跟Snowflake的設計非常類似吧。這個方案用一個PostgreSQL集群代替了Twitter Snowflake 集群，優點是利用了現成的PostgreSQL，容易懂，維護方便。

有的面試官會問，如何讓ID可以粗略的按照時間排序？上面的這種格式的ID，含有時間戳，且在高位，恰好滿足要求。如果面試官又問，如何保證ID嚴格有序呢？在分布式這個場景下，是做不到的，要想高性能，只能做到粗略有序，無法保證嚴格有序。

總結

以上是生活随笔為你收集整理的如何设计一个分布式ID生成器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。