傳統的單機情況下，通過內存或者數據的主鍵就可以維護一個唯一ID，但隨著業務增長，免不了增加主機和分庫分表，在這種情況下如何表示一個唯一的訂單或者用戶呢？
這就是分佈式唯一ID的意義。如果並非此場景，利用數據庫自增值或者時間戳隨機種子(為避免1ms內碰撞，可以再維護幾位順序位，可以參考後文snowflake算法)即可。當然由於絕大多數分佈式唯一ID算法效率很高，想用也是可以的。
分佈式唯一ID的要求
分佈式唯一ID的要求可以拆解為三個層面：
- 不重複。本質上不要求隨機，單純遞增也可以，因為不需要避免被猜測。很多時候以隨機代替不重複(隨機算法夠好池子夠大，能夠極大程度避免碰撞)。
- 細化不重複這一要求到時間唯一和空間唯一兩項。如果單純以當前時間戳作為種子，偽隨機數生成器在同一時刻、不同機器可以得出相同結果(下文有介紹原因)。
- 還有一個隱含的要求是有序，分佈式唯一ID需要作為被頻繁查詢的索引列。數據庫索引的基本原理是B+樹，通俗來說，是一個子節點更多的二叉搜索樹，所以需要有序,最好是純數字，可以避免字符類型排序的字符集轉換消耗。
真隨機和偽隨機，系統及語言層面方案
從根本上說，計算出來的數字都不是隨機數。“真”隨機真在這種隨機性跟物理世界的隨機是一致的，來自於大氣運動、分子熱運動等我們在物理世界中找不到確切規律預測下一個值的物理運動。至於這些到底是不是隨機的，就上升到另一個層面了，從我們的認知來看它們就是真實隨機的。“偽”隨機偽在下一個值可以計算出來，只是規則比較複雜，在不知道確切的“種子”時無法計算。
既然是計算出來的，就一定有公式，這個公式的要求是什麼？
- 算出來像隨機，結果應該是很均衡的，不存在某些值比率過高。
- 不能太複雜，速度要快。
- 逆向猜解成本比較高。
目前絕大多數(部分有密碼學要求的隨機算法可以取系統的熵池)語言的隨機算法都是偽隨機，比如線性同餘、梅森旋轉、平方取中，其中最著名的是“線性同餘法”（LCG），其公式為
其中N j
就是我們常說的隨機數種子，A、B、M則一般由語言實現內定。在種子一定的情況下，輸出的“隨機”序列也完全一致。最簡單的驗證方式是golang中的隨機算法，如果不指定種子(默認為1)，多次計算得出的序列都一樣。
計算得出的序列也是有準確長度的，走完一次會再重新循環。具體長度取決於A、B、M三個值的具體取值，但總小於等於M。
為了隨機效果，A、B、M三個值也有一定要求(參考資料中百科鏈接)。這裡是一些被挑選出來，某些編程語言可能內置的值：
為了證明這種“偽”隨機其實有明顯規律，有人利用物理熵(大氣)和線性同餘算法生成的隨機值繪製了兩張圖片：
利用物理熵：
線性同餘：
密碼學上把隨機數分為三種：
- 弱隨機數：統計學偽隨機性，比特流中01出現頻率基本相同，比如這裡說到的線性同餘。
- 強隨機數：密碼學安全偽隨機性:“不能通過給定的隨機序列的一部分而以顯著大於1/2的概率在多項式時間內演算出比特序列的任何其他部分”，比如Trivium、SHA-2算法，一個隨機數算法是否是密碼學安全偽隨機數生成器有CSPRNG驗證集。
- 真隨機數：具備不可重現性。而由於計算機的計算結果是確定的，所以無法利用算法實現，只有利用熵池實現。
為了獲取真隨機數，CPU芯片內置了真隨機數發生器TRNG和偽隨機數發生器PRNG，其中TRNG是利用放大電路的熱噪聲來產生隨機數，而PRNG使用線性反饋移位寄存器，這是一種硬件層面的偽隨機數生成器，其種子是TRNG中的真隨機數。
（此段待考，可以關注筆者在v2ex的提問 /dev/(u)random 是基於 cpu 中的真隨機數生成器(TRNG)和偽隨機數生成器(PRNG)嗎？ - V2EX ） 對應地，linux實現了/dev/random和/dev/urandom兩個虛擬設備，很多語言中密碼學安全的算法都是藉助讀取這兩個設備實現的，比如node中的crypto.randombytes。補充一點，有文章聲稱這兩種設備的隨機性是一樣的(參考資料中知乎專欄)，但筆者沒找到更多詳細資料支撐這一說法，傾向於認為這個說法是錯的。
方案分類
中心節點分發
所謂中心節點分發就是為了避免在分佈式的多臺機器上得到同樣的值，故而將ID計算集中在一臺機器上。這種方案優點很明顯：不存在各類基於隨機數唯一ID算法的碰撞風險，並且可以排序。
mysql或redis等數據庫
常用的方案是利用數據庫主鍵的自增且唯一性，通過LAST_INSERT_ID()來獲取主鍵作為唯一ID。這種方案固然可行，但缺點也很明顯：這不是分佈式的，中心節點的壓力會很大。中心節點故障風險性導致其不具備高可用性。
數據庫演進
兩種比較典型的演進式思路是：
- 批量生成一批，均分給每個機器節點，存在它們內存中，枯竭後再生成，實際上這也是所有可能面臨效率問題的算法採取的通用方案。
- 維護多箇中心節點，設置不同起點相同步長，導致它們永遠都不重複，比如兩臺機器一臺135，一臺246，假如一臺宕機，另外一臺也可以承擔工作，只是效率低點罷了。
完全隨機
還有一些完全依靠隨機的算法，這些算法的核心思想就是隨機池夠大，賭它在可見的產品週期內不足以發生碰撞。其實無論採用什麼算法，即使是不使用隨機數的中心節點下發方案，也可能因為網絡等故障造成重複id，只要業務上設計有一定的保底方案，都不會出問題。比如在數據庫將該列設置為唯一索引，插入該訂單時會檢查訂單號是否唯一，如果報錯則重試。
Nuid
Nuid是一個較新的算法，其核心非常簡單。
使用62個字符(0-9a-zA-Z)生成22位結果，其中前12位是藉助TRNG獲取的真隨機數，而後10位為隨機數。
<code>// Generate a new prefix from crypto/rand.// This call *can* drain entropy and will be called automatically when we exhaust the sequential range.// Will panic if it gets an error from rand.Int()func (n *NUID) RandomizePrefix() { var cb [preLen]byte cbs := cb[:] if nb, err := rand.Read(cbs); nb != preLen || err != nil { panic(fmt.Sprintf("nuid: failed generating crypto random number: %v\\n", err)) } for i := 0; i < preLen; i++ { n.pre[i] = digits[int(cbs[i])%base] }}// Generate the next NUID string.func (n *NUID) Next() string { // Increment and capture. n.seq += n.inc if n.seq >= maxSeq { n.RandomizePrefix() n.resetSequential() } seq := n.seq // Copy prefix var b [totalLen]byte bs := b[:preLen] copy(bs, n.pre) // copy in the seq in base36. for i, l := len(b), seq; i > preLen; l /= base { i -= 1 b[i] = digits[l%base] } return string(b[:])}複製代碼/<code>其主要優點是性能非常高，1s內可以計算出百萬級的id。
uuid部分版本及退化版本
為什麼這裡叫做部分版本及退化版本呢？
uuid想必大多數人都知道，uuid和guid其實是一回事，只是不同的叫法。uuid是rfc4122標準定義的id算法。其原則上是支持分佈式唯一ID的，但具體實現上則不盡然，原因是uuid的標準比較開放，有v1-v5五種版本(v2沒有具體實現)，其中有的版本比如v1版本對於node字段的具體取值沒有強制約束，最標準的方式是使用當前計算機第一塊網卡的mac地址(也有批評暴漏mac地址並不安全，並且mac地址也不能確定唯一不可篡改)，但獲取不到的情況下也可以退化成偽隨機數。值得一提的是SQL中也有GENERATE_UUID()方法。
這裡不詳細介紹所有版本的uuid生成算法，以github上star數量8k+的node uuid npm包的實現為例,其中node節點就沒有使用mac地址而是使用隨機數(事實上大多數的uuid實現都沒有使用mac地址，具體原因待考)：
<code>// rng庫的內容是利用crypto.randomBytes從trng熵池讀取隨機數var rng = require('./lib/rng');var bytesToUuid = require('./lib/bytesToUuid');// **`v1()` - Generate time-based UUID**//// Inspired by https://github.com/LiosK/UUID.js// and http://docs.python.org/library/uuid.htmlvar _nodeId;var _clockseq;// Previous uuid creation timevar _lastMSecs = 0;var _lastNSecs = 0;// See https://github.com/broofa/node-uuid for API detailsfunction v1(options, buf, offset) { var i = buf && offset || 0; var b = buf || []; options = options || {}; var node = options.node || _nodeId; var clockseq = options.clockseq !== undefined ? options.clockseq : _clockseq; // node and clockseq need to be initialized to random values if they're not // specified. We do this lazily to minimize issues related to insufficient // system entropy. See #189 if (node == null || clockseq == null) { var seedBytes = rng(); if (node == null) { // Per 4.5, create and 48-bit node id, (47 random bits + multicast bit = 1) node = _nodeId = [ seedBytes[0] | 0x01, seedBytes[1], seedBytes[2], seedBytes[3], seedBytes[4], seedBytes[5] ]; } if (clockseq == null) { // Per 4.2.2, randomize (14 bit) clockseq clockseq = _clockseq = (seedBytes[6] << 8 | seedBytes[7]) & 0x3fff; } } // UUID timestamps are 100 nano-second units since the Gregorian epoch, // (1582-10-15 00:00). JSNumbers aren't precise enough for this, so // time is handled internally as 'msecs' (integer milliseconds) and 'nsecs' // (100-nanoseconds offset from msecs) since unix epoch, 1970-01-01 00:00. var msecs = options.msecs !== undefined ? options.msecs : new Date().getTime(); // Per 4.2.1.2, use count of uuid's generated during the current clock // cycle to simulate higher resolution clock var nsecs = options.nsecs !== undefined ? options.nsecs : _lastNSecs + 1; // Time since last uuid creation (in msecs) var dt = (msecs - _lastMSecs) + (nsecs - _lastNSecs)/10000; // Per 4.2.1.2, Bump clockseq on clock regression if (dt < 0 && options.clockseq === undefined) { clockseq = clockseq + 1 & 0x3fff; } // Reset nsecs if clock regresses (new clockseq) or we've moved onto a new // time interval if ((dt < 0 || msecs > _lastMSecs) && options.nsecs === undefined) { nsecs = 0; } // Per 4.2.1.2 Throw error if too many uuids are requested if (nsecs >= 10000) { throw new Error('uuid.v1(): Can\\'t create more than 10M uuids/sec'); } _lastMSecs = msecs; _lastNSecs = nsecs; _clockseq = clockseq; // Per 4.1.4 - Convert from unix epoch to Gregorian epoch msecs += 12219292800000; // `time_low` var tl = ((msecs & 0xfffffff) * 10000 + nsecs) % 0x100000000; b[i++] = tl >>> 24 & 0xff; b[i++] = tl >>> 16 & 0xff; b[i++] = tl >>> 8 & 0xff; b[i++] = tl & 0xff; // `time_mid` var tmh = (msecs / 0x100000000 * 10000) & 0xfffffff; b[i++] = tmh >>> 8 & 0xff; b[i++] = tmh & 0xff; // `time_high_and_version` b[i++] = tmh >>> 24 & 0xf | 0x10; // include version b[i++] = tmh >>> 16 & 0xff; // `clock_seq_hi_and_reserved` (Per 4.2.2 - include variant) b[i++] = clockseq >>> 8 | 0x80; // `clock_seq_low` b[i++] = clockseq & 0xff; // `node` for (var n = 0; n < 6; ++n) { b[i + n] = node[n]; } return buf ? buf : bytesToUuid(b);}module.exports = v1;複製代碼/<code>uuid的算法與完全隨機算法相比加入了時間信息和節點信息，但並不具備很好的排序性。
節點+時序
uuid帶節點版本
對應v1版本node字段採用mac地址等硬件地址方案。此處不再贅述。
snowflake雪花算法
Snowflake是twitter提出的一個真正意義上的分佈式唯一ID算法，目前業界大廠常用的方案都是snowflake或者基於snowflake的改造和優化。
注意這裡的64位是bit位，都是0或者1，而非0-10或者字母。
首位總是0，這是因為snowflake的64位bit實際上是一個64位整型數字，第一位表示數字正負，為0表示正數。41位時間戳支持 2^41 個數字，以毫秒為單位一共可以表示69年的範圍，這裡的時間戳並非傳統意義的unix時間戳，而是一個自己定義的相對時間，其中的0值可以是業務開始的時刻。10位的工作機器bit可以表示一個分佈式系統內最多 2^10 個機器，這個id也是自己分配的，比如按照ip排序依次為0123。根據上面兩個字段，我們已經可以確定在1ms內一個機器上的id不會重複了，為了支持在1ms內更大的併發量，還有12位用來表示在1ms內生成的id的順序， 單機器單ms內的最大生產效率為 2^12 個，每秒生產的id也是百萬級別。
最終得到的是64位整型數字，滿足了分佈式ID的各個要求，並且是按照時間順序有序的。
這裡專門提一下機器id，因為這裡的id不像uuid使用mac地址，其碼段長度與mac地址等硬件地址不容易建立映射關係，一般情況下是通過數據庫等中心化的配置中心進行下發。當然如果你的業務並非是自動擴縮容的，那麼直接指定也是可以的。從這個意義上講，snowflake算法並非像某些文章聲稱的不需要中心節點就可以單機生成唯一id。
snowflake演進
國內的廠商進行的snowflake的改造和優化主要集中在兩個方面：
- 避免時針回撥。如果41位的時間重複，那麼有很大可能出現碰撞的id。美團的leaf方案就是在snowflake外加了一個ZooKeeper來記錄時鐘前進，如果回撥啟動報警。還有很多方案是比較現在生成的id與之前生成的id的時間，如果不是前進則報錯或者依舊使用回撥後重復的時間序列+不太可能被用到的較大序列值(賭它不碰撞)。
- 重新劃分64位的碼段和具體含義，比如當機器較多時可以壓縮時鐘序列碼段，擴大工作機器id碼段。
分佈式時鐘一致
Snowflake是目前最優的分佈式唯一ID生成算法，但基於時序的分佈式id算法都具有一個顯著的問題，沒有全局時鐘所以不同機器上的時序是有可能不一致的，這並非是分佈式唯一ID生成算法的缺陷，而是分佈式自己的缺陷，這裡提一下可以當作知識拓展。不過這對唯一id本身並無影響，只是時序碼段不能作為確切的絕對時間依據。
也有用來維護網絡間各個機器的時鐘一致性的方案，比如NTP協議或者GPS時鐘，但也無法做到完全的同步(幾十ms級別的延遲)。至於邏輯時鐘，應當與本文探討的分佈式唯一ID關係不大。
閱讀更多 sandag 的文章
