分布式Unique ID的生成方法一覽
來自： http://calvin1978.blogcn.com/articles/uuid.html
分布式的Unique ID的用途如此廣泛，從業務對象Id到日志的TraceId，本文總結了林林總總的各種生成算法。
1. 發號器
我接觸的最早的Unique ID，就是Oracle的自增ID。
特點是準連續的自增數字，為什么說是準連續？因為性能考慮，每個Client一次會領20個ID回去慢慢用，用完了再來拿。另一個Client過來，拿的就是另外20個ID了。
新浪微博里，Tim用Redis做相同的事情，Incr一下拿一批ID回去。如果有多個數據中心，那就拿高位的幾個bit來區分。
只要舍得在總架構里增加額外Redis帶來的復雜度，一個64bit的long就夠表達了，而且不可能有重復ID。
2. UUID
2.1 概述
Universally Unique IDentifier(UUID)，有著正兒八經的RFC規范，是一個128bit的數字，也可以表現為32個16進制的字符，中間用”-"分割。
- 時間戳＋UUID版本號，分三段占16個字符(60bit+4bit)，
- Clock Sequence號與保留字段，占4個字符(13bit＋3bit)，
- 節點標識占12個字符(48bit)，
比如：f81d4fae-7dec-11d0-a765-00a0c91e6bf6
實際上，UUID一共有多種算法，能用于TraceId的是：
- version1: 基于時間的算法- version4: 基于隨機數的算法
version 4
先說Version4，這是最暴力的做法，也是JDK里的算法，不管原來各個位的含義了，除了少數幾個位必須按規范填，其余全部用隨機數表達。
JDK里的實現，用 SecureRandom生成了16個隨機的Byte，用2個long來存儲。記得加-Djava.security.egd=file:/dev/./urandom，否則會鎖住程序等噪音。
version 1
然后是Version1，嚴格守著原來各個位的規矩：
因為時間戳有滿滿的60bit，所以可以盡情花，以100納秒為1，從1582年10月15日算起(能撐3655年，真是位數多給燒的，1582年有意思么)
節點標識也有48bit，一般用MAC地址表達，如果有多塊網卡就隨便用一塊。如果沒網卡，就用隨機數湊數，或者拿一堆盡量多的其他的信息，比如主機名什么的，拼在一起再hash一把。
順序號這16bit則僅用于避免前面的節點標示改變（如網卡改了），時鐘系統出問題（如重啟后時鐘快了慢了），讓它隨機一下避免重復。
但好像Version 1就沒考慮過一臺機器上起了兩個進程這類的問題，也沒考慮相同時間戳的并發問題，所以嚴格的Version1沒人實現，接著往下看各個變種吧。
Version1變種 - Hibernate
Hibernate的 CustomVersionOneStrategy.java ，解決了之前version 1的兩個問題
- 時間戳(6bytes, 48bit)：毫秒級別的，從1970年算起，能撐8925年....
- 順序號(2bytes, 16bit, 最大值65535): 沒有時間戳過了一秒要歸零的事，各搞各的，short溢出到了負數就歸0。
- 機器標識(4bytes 32bit): 拿localHost的IP地址，IPV4呢正好4個byte，但如果是IPV6要16個bytes，就只拿前4個byte。
- 進程標識(4bytes 32bit)： 用當前時間戳右移8位再取整數應付，不信兩條線程會同時啟動。
值得留意就是，機器進程和進程標識組成的64bit Long幾乎不變，只變動另一個Long就夠了。
Version1變種 - MongoDB
MongoDB的ObjectId.java
- 時間戳(4 bytes 32bit): 是秒級別的，從1970年算起，能撐136年。
- 自增序列(3bytes 24bit, 最大值一千六百萬)： 是一個從隨機數開始（機智）的Int不斷加一，也沒有時間戳過了一秒要歸零的事，各搞各的。因為只有3bytes，所以一個4bytes的Int還要截一下后3bytes。
- 機器標識(3bytes 24bit): 將所有網卡的Mac地址拼在一起做個HashCode，同樣一個int還要截一下后3bytes。搞不到網卡就用隨機數混過去。
- 進程標識(2bytes 16bits)：從JMX里搞回來到進程號，搞不到就用進程名的hash或者隨機數混過去。
可見，MongoDB的每一個字段設計都比Hibernate的更合理一點，比如時間戳是秒級別的。總長度也降到了12 bytes 96bit，但如果果用64bit長的Long來保存有點不上不下的，只能表達成byte數組或16進制字符串。
另外對Java版的driver在自增序列那里好像有bug。
推ter的snowflake
snowflake也是一個派號器，基于Thrift的服務，不過不是用redis簡單自增，而是類似UUID version1，
只有一個Long 64bit的長度，所以IdWorker緊巴巴的分配成：
- 時間戳(42bit) 自從2012年以來(比那些從1970年算起的會過日子)的毫秒數，能撐139年。
- 自增序列(12bit，最大值4096), 毫秒之內的自增，過了一毫秒會重新置0。
- DataCenter ID (5 bit, 最大值32），配置值。
- Worker ID ( 5 bit, 最大值32)，配置值，因為是派號器的id，所以一個數據中心里最多32個派號器就夠了，還會在ZK里做下注冊。
可見，因為是派號器，把機器標識和進程標識都省出來了，所以能夠只用一個Long表達。
但是，這種派號器，client每次只能一個ID，不能批量取，所以額外增加的延時是問題。
可能覺得用原生的Thirft做傳輸層不夠好，snowflake后來又收回去了不對外開源了。
最后問題，能不能不用派號器，又一個Long搞定UUID??
如果當初你的ID一開始類型設為了Long，又不用派號器的話，怎么辦？
思路一，壓縮其他字段，留足夠多的長度來做機器＋進程號標識
時間戳是秒級別，1年要24位，兩年要25位.....
自增序列，6萬QPS要16位，10萬要17位...
剩下20－24位，百萬分之一到一千六百萬分之一的重復率，然后把網卡Mac＋進程號拼在一起再hash，取結果32個bit的后面20或24個bit。但假如這個標識字段重復了，后面時間戳和自增序列也很容易重復，不停的重復。
思路二，使用ZK 或 mysql 或 redis來自增管理標識號
如果workder字段的位數留得夠多，比如有20位（一百萬），那用redis或mysql來自增最簡單，每個進程啟動時拿一個wokrder id。如果只留了12位（4096），就要用ZK或etcd，當進程關閉了要回收這個號。
思路三，繼續Random
繼續拼了，直接拿JDK UUID.randomUUID()的低位long（按UUID規范，高位的long被置了4個默認值的bit，低位只被設置3個bit），或者直接SecureRandom.nextLong()，不浪費了那3個bit。
參考資料：
一樂那篇《業務系統需要什么樣的ID生成器》 ，其中 唯一性，時間相關，粗略有序，可反解，可制造 這個提法很好，說白了就是讓大家盡量用UUID version1風格。
</div>