分布式 ID 生成方案#
內容來自
問題描述#
在單機系統中 (例如一個 MySQL 實例), unique ID 的生成是非常簡單的，直接利用 MySQL 自帶的自增 ID 功能就可以實現.
但在一個存在多個 Shards 的分布式系統 (例如多個 MySQL 實例組成一個集群，在這個集群中插入數據), 這個問題會變得複雜，所生成的全局的 unique ID 要滿足以下需求:
- 保證生成的 ID 全球唯一
- 今後數據在多個 Shards 之間遷移不會受到 ID 生成方式的限制
- 生成的 ID 中最好能帶上時間信息，例如 ID 的前 k 位是 Timestamp, 這樣能夠直接通過對 ID 的前 k 位的排序來對數據按時間排序
- 生成的 ID 最好不大於 64 bits
- 生成 ID 的速度有要求。例如，在一個高吞吐量的場景中，需要每秒生成幾萬個 ID (Twitter 最新的峰值達到了 143,199 Tweets/s, 也就是 10 萬 +/ 秒)
- 整個服務最好沒有單點
時間戳#
用時間做唯一 id，這個在併發比較高或者分布式環境中基本不可行，統一時間生成的 id 是重複的，不滿足全球唯一
利用數據庫自增#
依然利用數據庫產生自增 id，保證唯一性。但是要注意的是沒有分庫分表，可以單獨使用固定數量的數據庫表專門來產生自增 ID，與業務無關，後續不再分表。
好處是實現簡單，容易理解。不足在於 id 產生速率受數據庫性能以及連接數據庫的網絡影響
利用 Redis 原子操作#
- 不依賴於數據庫，靈活方便，且性能優於數據庫。
- 數字 ID 天然排序，對分頁或者需要排序的結果很有幫助
注意:
- 在 Redis 集群情況下，需要設置不同的增長步長
- 生成的 ID 超過自增增長的話，可以採用前綴 + 自增 + 並且設置有效期
利用 UUID/GUID#
基本概念#
UUID 是指在一台機器上生成的數字，它保證對在同一時空中的所有機器都是唯一的。
UUID 組成部分：當前日期和時間 + 時鐘序列 + 隨機數 + 全球唯一的 IEEE 機器識別號
優缺點#
優點:
- 簡單，代碼方便
- 生成 ID 性能非常好，基本不會有性能問題
- 全球唯一，在遇見數據遷移，系統數據合併，或者數據庫變更等情況下，可以從容應對
缺點: - 沒有排序，無法保證趨勢遞增
- UUID 往往是使用字符串存儲，查詢的效率比較低
- 存儲空間比較大，如果是海量數據庫，就需要考慮存儲量的問題。
- 太長，128bit，不適合做數據庫主鍵
Twitter Snowflake#
snowflake 是 Twitter 開源的分布式 ID 生成算法，結果是一個 long 型的 ID。
其核心思想是：高位隨機 + 毫秒數 + 機器碼（數據中心 + 機器 id）+10 位的流水號
ID 生成過程#
- 10 bits 的機器號，在 ID 分配 Worker 啟動的時候，從一個 Zookeeper 集群獲取 (保證所有的 Worker 不會有重複的機器號)
- 41 bits 的 Timestamp: 每次要生成一個新 ID 的時候，都會獲取一下當前的 Timestamp, 然後分兩種情況生成 sequence number:
- 如果當前的 Timestamp 和前一個已生成 ID 的 Timestamp 相同 (在同一毫秒中), 就用前一個 ID 的 sequence number + 1 作為新的 sequence number (12 bits); 如果本毫秒內的所有 ID 用完，等到下一毫秒繼續 (這個等待過程中，不能分配出新的 ID)
- 如果當前的 Timestamp 比前一個 ID 的 Timestamp 大，隨機生成一個初始 sequence number (12 bits) 作為本毫秒內的第一個 sequence number 整個過程中，只是在 Worker 啟動的時候會對外部有依賴 (需要從 Zookeeper 獲取 Worker 號), 之後就可以獨立工作了，做到了去中心化