分布式Unique ID的生成方法是怎樣的

這篇文章給大家介紹分布式Unique ID的生成方法是怎樣的，內(nèi)容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

分布式的Unique ID的用途如此廣泛，從業(yè)務(wù)對象Id到日志的TraceId，小編總結(jié)了林林總總的各種生成算法。

1. 發(fā)號器

我接觸的最早的Unique ID，就是Oracle的自增ID。

特點是準連續(xù)的自增數(shù)字，為什么說是準連續(xù)？因為性能考慮，每個Client一次會領(lǐng)20個ID回去慢慢用，用完了再來拿。另一個Client過來，拿的就是另外20個ID了。

新浪微博里，Tim用Redis做相同的事情，Incr一下拿一批ID回去。如果有多個數(shù)據(jù)中心，那就拿高位的幾個bit來區(qū)分。

只要舍得在總架構(gòu)里增加額外Redis帶來的復(fù)雜度，一個64bit的long就夠表達了，而且不可能有重復(fù)ID。

批量是關(guān)鍵，否則每個ID都遠程調(diào)用一次誰也吃不消。

2. UUID

2.1 概述

Universally Unique IDentifier(UUID)，有著正兒八經(jīng)的RFC規(guī)范，是一個128bit的數(shù)字，也可以表現(xiàn)為32個16進制的字符，中間用”-"分割。

- 時間戳＋UUID版本號，分三段占16個字符(60bit+4bit)，
- Clock Sequence號與保留字段，占4個字符(13bit＋3bit)，
- 節(jié)點標識占12個字符(48bit)，

比如：f81d4fae-7dec-11d0-a765-00a0c91e6bf6

實際上，UUID一共有多種算法，能用于TraceId的是：

- version1: 基于時間的算法
- version4: 基于隨機數(shù)的算法

version 4

先說Version4，這是最暴力的做法，也是JDK里的算法，不管原來各個位的含義了，除了少數(shù)幾個位必須按規(guī)范填，其余全部用隨機數(shù)表達。

JDK里的實現(xiàn)，用 SecureRandom生成了16個隨機的Byte，用2個long來存儲。記得加-Djava.security.egd=file:/dev/./urandom，否則會鎖住程序等噪音。
詳見 JVM上的隨機數(shù)與熵池策略

version 1

然后是Version1，嚴格守著原來各個位的規(guī)矩：

因為時間戳有滿滿的60bit，所以可以盡情花，以100納秒為1，從1582年10月15日算起(能撐3655年，真是位數(shù)多給燒的，1582年有意思么)

節(jié)點標識也有48bit，一般用MAC地址表達，如果有多塊網(wǎng)卡就隨便用一塊。如果沒網(wǎng)卡，就用隨機數(shù)湊數(shù)，或者拿一堆盡量多的其他的信息，比如主機名什么的，拼在一起再hash一把。

順序號這16bit則僅用于避免前面的節(jié)點標示改變（如網(wǎng)卡改了），時鐘系統(tǒng)出問題（如重啟后時鐘快了慢了），讓它隨機一下避免重復(fù)。

但好像Version 1就沒考慮過一臺機器上起了兩個進程這類的問題，也沒考慮相同時間戳的并發(fā)問題，所以嚴格的Version1沒人實現(xiàn)，接著往下看各個變種吧。

Version1變種 - Hibernate

Hibernate的CustomVersionOneStrategy.java，解決了之前version 1的兩個問題

- 時間戳(6bytes, 48bit)：毫秒級別的，從1970年算起，能撐8925年....
- 順序號(2bytes, 16bit, 最大值65535): 沒有時間戳過了一秒要歸零的事，各搞各的，short溢出到了負數(shù)就歸0。
- 機器標識(4bytes 32bit): 拿localHost的IP地址，IPV4呢正好4個byte，但如果是IPV6要16個bytes，就只拿前4個byte。
- 進程標識(4bytes 32bit)： 用當前時間戳右移8位再取整數(shù)應(yīng)付，不信兩條線程會同時啟動。

值得留意就是，機器進程和進程標識組成的64bit Long幾乎不變，只變動另一個Long就夠了。

Version1變種 - MongoDB

MongoDB的ObjectId.java

- 時間戳(4 bytes 32bit): 是秒級別的，從1970年算起，能撐136年。

- 自增序列(3bytes 24bit, 最大值一千六百萬)： 是一個從隨機數(shù)開始（機智）的Int不斷加一，也沒有時間戳過了一秒要歸零的事，各搞各的。因為只有3bytes，所以一個4bytes的Int還要截一下后3bytes。

- 機器標識(3bytes 24bit): 將所有網(wǎng)卡的Mac地址拼在一起做個HashCode，同樣一個int還要截一下后3bytes。搞不到網(wǎng)卡就用隨機數(shù)混過去。

- 進程標識(2bytes 16bits)：從JMX里搞回來到進程號，搞不到就用進程名的hash或者隨機數(shù)混過去。

可見，MongoDB的每一個字段設(shè)計都比Hibernate的更合理一點，比如時間戳是秒級別的?？傞L度也降到了12 bytes 96bit，但如果果用64bit長的Long來保存有點不上不下的，只能表達成byte數(shù)組或16進制字符串。

另外對Java版的driver在自增序列那里好像有bug。
 

Twitter的snowflake派號器

snowflake也是一個派號器，基于Thrift的服務(wù)，不過不是用redis簡單自增，而是類似UUID version1，

只有一個Long 64bit的長度，所以IdWorker緊巴巴的分配成：

- 時間戳(42bit) 自從2012年以來(比那些從1970年算起的會過日子)的毫秒數(shù)，能撐139年。
- 自增序列(12bit，最大值4096), 毫秒之內(nèi)的自增，過了一毫秒會重新置0。
- DataCenter ID (5 bit, 最大值32），配置值。
- Worker ID ( 5 bit, 最大值32)，配置值，因為是派號器的id，所以一個數(shù)據(jù)中心里最多32個派號器就夠了，還會在ZK里做下注冊。

可見，因為是派號器，把機器標識和進程標識都省出來了，所以能夠只用一個Long表達。

另外，這種派號器，client每次只能一個ID，不能批量取，所以額外增加的延時是問題。

最后問題，能不能不用派號器，又一個Long搞定UUID??

前面說這么多都是鋪墊，如果當初你的ID一開始類型設(shè)為了Long，又不用派號器的話，怎么辦？
從UUID的128位壓縮到Long的64位，又不用中央派號器而是本地生成，最難還是怎么來區(qū)分本地的機器＋進程號。

思路一，壓縮其他字段，留足夠多的長度來做機器＋進程號標識

時間戳是秒級別，1年要24位，兩年要25位.....
自增序列，6萬QPS要16位，10萬要17位...
剩下20－24位，百萬分之一到一千六百萬分之一的重復(fù)率，然后把網(wǎng)卡Mac＋進程號拼在一起再hash，取結(jié)果32個bit的后面20或24個bit。但假如這個標識字段重復(fù)了，后面時間戳和自增序列也很容易重復(fù)，不停的重復(fù)。

思路二，使用ZK 或 mysql 或 redis來自增管理標識號

如果workder字段只留了12位（4096），就要用ZK或etcd，當進程關(guān)閉了要回收這個號。
如果workder字段的位數(shù)留得夠多，比如有20位（一百萬），那用redis或mysql來自增最簡單，每個進程啟動時拿一個worker id。

思路三，繼續(xù)Random

繼續(xù)拼了，直接拿JDK UUID.randomUUID()的低位long（按UUID規(guī)范，高位的long被置了4個默認值的bit，低位只被設(shè)置3個bit），或者直接SecureRandom.nextLong()，不浪費了那3個bit。

關(guān)于分布式Unique ID的生成方法是怎樣的就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。