最近看一個新系統，發現裡面有很多場景用到唯一id，便蒐羅了一下常見的方案。
對於分佈式id，需要滿足下面的基本要求
- 全局唯一
- 趨勢遞增
1. UUID
UUID（Universally Unique Identifier）全局唯一標識符，定義為一個字符串主鍵，採用32位數字組成，編碼採用16進制，定義了在時間和空間都完全惟一的系統信息。
UUID的編碼規則：
- 1~8位採用系統時間，在系統時間上精確到毫秒級保證時間上的惟一性；
- 9~16位採用底層的IP地址，在服務器集群中的惟一性；
- 17~24位採用當前對象的HashCode值，在一個內部對象上的惟一性；
- 25~32位採用調用方法的一個隨機數，在一個對象內的毫秒級的惟一性。
通過以上4種策略可以保證惟一性。在系統中需要用到隨機數的地方都可以考慮採用UUID算法。
UUID可能會是大家很快想到的，因為它現成，全球唯一，不需要中心協調器來控制唯一。主流語言中都會有內置現成的api直接生成。但卻不推薦，因為它
- 無序，沒有自增趨勢，作為主鍵插入效率低下（如MySql）
- 過長，浪費存儲空間
- 無法存儲業務邏輯，可讀性差，當然如果你的id沒有長度限制，可以通過拼接前綴/後綴來增加信息
2. 中心協調器類
可以引入中心協調器類，通過該系統自帶的特性來完成id的生成和分配。
2.1 數據庫自增主鍵
Don't say so match，大家應該都用過，通過DB的auto_increment自增主鍵來控制id的唯一以及有序，使用簡單。當然缺點也是明顯的，依賴DB存在單點問題，當然可以通過主從模式來解決單點問題。
網上還有有人介紹了自增主鍵的另一種模式，如下
引入多實例，為每個實例設置初始值以及固定的步長來降低單點的風險，以及分攤DB壓力。當然只是降低，單點問題還是存在的，同時還不容易擴容，也需要客戶端做支持。對於趨勢遞增則需要ID服務來維持，它需要輪訓訪問後端的各個DB實例，以維持趨勢遞增的特性。
2.2 Redis
Redis提供了incr命令可以實現id的原子性自增，能夠達到類似DB的auto_increment的效果。使用Redis需要注意持久化的問題，避免Redis重啟後數據丟失導致id重複。
2.3 ZooKeeper
zookeeper自帶生成順序節點的功能，可以使用其生成順序節點的編號來作為id。客戶端創建完節點後，通過解析返回的節點名來獲得當前分配的id。
中心協調器類其實都差不多，將id的生成轉到中心協調器上。
3. 數據庫號段
數據庫號段的方式如下：
涉及的表結構如下：
type字段用來區分不同的業務，隔離不同業務之間的相互影響；max_id字段則表示當前業務類型已經分配的最大id值，下一次分配則從該值開始；step為步長；state用來做鎖控制，這裡用的是樂觀鎖，也可以不用該字段，改為行鎖(select ... for update)。
以bizType1為例，數據庫中記錄著bizType1的下一個id起始值3000，以及對應的步長1000。當應用啟動後首次使用時，嘗試去獲取bizType1這條記錄的鎖，獲取到鎖的應用讀取max_id和step的值，同步更新到內存，然後將max_id的值加上步長後更新回表中，這個值便是下一個id的起始值。當應用實例內存中的步長沒有消耗完前，直接通過應用內部自己自增返回id，避免頻繁請求DB。當應用消耗完後則再次訪問DB同步更新max_id和step，反覆循環下去。
開頭講到的最近接觸的新系統用的就是號段的方式來生成唯一id，但它不是用樂觀鎖的方式而是用行鎖。測試環境給的步長比較小，剛好測試同學在做壓測造數據的時候併發開的大，導致搶鎖鎖頻繁拋異常了。當然如果使用樂觀鎖也會存在飢餓的情況，會導致一直獲取不到鎖而一直忙等。
看完上面的過程，其實核心點在於有個第三方系統來提供鎖和存儲以及應用端的配合，所以其實不用DB也可以實現該功能。
4. Snowflake雪花算法
相信大家都聽過這個算法，都知道這個算法是由Twitter提出來的，既然大家都知道就不多說了，那大家也都看過下面這張圖：
該算法使用一個64 bit的整型數據，包括
- 首位不用的1個bit(最高位是標識位，為1表示為負數，不使用)
- 41個bit的毫秒級時間(41位的長度可以使用69年)，
- 10個bit的工作機器id，包括5個bit的datacenterId和5個bit的workerId(10位的長度最多支持部署1024個節點）
- 12個bit的毫秒內的計數（12位的計數順序號支持每個節點每毫秒產生4096個ID序號）
一共加起來剛好64位，為一個Long型。
Snowflake算法核心把時間戳，工作機器id，序列號組合在一起。整體上按照時間自增排序，並且整個分佈式系統內不會產生ID碰撞（由datacenter和機器ID作區分），並且效率較高，經測試，snowflake每秒能夠產生26萬id左右，完全滿足需要。
Snowflake算法中41個bit的時間戳完全依賴於時間的，如果有時鐘回撥的情況發生，則會生成重複的id。時鐘回撥涉及兩種情況
- 實例停機→時鐘回撥→實例重啟→計算ID
- 實例運行中→時鐘回撥→計算ID
對於時間回撥，網上給出了很多處理方法，包括：
- 如果發現有時鐘回撥，時間很短比如5毫秒,就等待，然後再生成；或者就直接報錯，交給業務層去處理
- 可以找2bit位作為時鐘回撥位，發現有時鐘回撥就將回撥位加1，達到最大位後再從0開始進行循環
- 實例啟動後，改用內存生成時間，如百度開源的UidGenerator，該方式可以解決時鐘回撥的第2種情況。對於時鐘回撥的第1種情況，UidGenerator在實例啟動後使用未分配過的工作機器id來解決，當然這樣做就得管理工作機器id，因而需要一個外部存儲，增加了複雜度。
