前言
一般單機或者單數據庫的項目可能規模比較小，適應的場景也比較有限，平臺的訪問量和業務量都較小，業務ID的生成方式比較原始但是夠用，它並沒有給這樣的系統帶來問題和瓶頸，所以這種情況下我們並沒有對此給予太多的關注。但是對於大廠的那種大規模複雜業務、分佈式高併發的應用場景，顯然這種ID的生成方式不會像小項目一樣僅僅依靠簡單的數據自增序列來完成，而且在分佈式環境下這種方式已經無法滿足業務的需求，不僅無法完成業務能力，業務ID生成的速度或者重複問題可能給系統帶來嚴重的故障。所以這一次，我們看看大廠都是怎麼分析和解決這種ID生成問題的，同時，我也將我之前使用過的方式拿出來對比，看看有什麼問題，從中能夠得到什麼啟發。
分佈式ID的生成特性
在分析之前，我們先明確一下業務ID的生成特性，在此特性的基礎上，我們能夠對下面的這幾種生成方式有更加深刻的認識和感悟。
- 全局唯一，這是基本要求，不能出現重複。
- 數字類型，趨勢遞增，後面的ID必須比前面的大，這是從MySQL存儲引擎來考慮的，需要保證寫入數據的性能。
- 長度短，能夠提高查詢效率，這也是從MySQL數據庫規範出發的，尤其是ID作為主鍵時。
- 信息安全，如果ID連續生成，勢必會洩露業務信息，甚至可能被猜出，所以需要無規則不規則。
- 高可用低延時，ID生成快，能夠扛住高併發，延時足夠低不至於成為業務瓶頸。
分佈式ID的幾種生成辦法
下面介紹幾種我積累的分佈式ID生成辦法，網絡上都能夠找得到，我通過學習積累並後期整理加上自己的感悟分享於此。雖然平時可能因為項目規模小而用不著，但是這種提出方案的思想還是很值得學習的，尤其是像美團的Leaf方案，我感覺特別的酷。
目錄：
基於UUID
基於數據庫主鍵自增
基於數據庫多實例主鍵自增
基於類Snowflake算法
基於Redis生成辦法
基於美團的Leaf方案（ID段、雙Buffer、動態調整Step）
基於UUID
這是很容易想到的方案，畢竟UUID全球唯一的特性深入人心，但是，但凡熟悉MySQL數據庫特性的人，應該不會用此來作為業務ID，它不可讀而且過於長，在此不是好主意，除非你的系統足夠小而且不講究這些，那就另說了。下面我們簡要總結下使用UUID作為業務ID的優缺點，以及這種方式適用的業務場景。
優點
- 代碼實現足夠簡單易用。
- 本地生成沒有性能問題。
- 因為具備全球唯一的特性，所以對於數據庫遷移這種情況不存在問題。
缺點
- 每次生成的ID都是無序的，而且不是全數字，且無法保證趨勢遞增。
- UUID生成的是字符串，字符串存儲性能差，查詢效率慢。
- UUID長度過長，不適用於存儲，耗費數據庫性能。
- ID無一定業務含義，可讀性差。
適用場景
- 可以用來生成如token令牌一類的場景，足夠沒辨識度，而且無序可讀，長度足夠。
- 可以用於無純數字要求、無序自增、無可讀性要求的場景。
基於數據庫主鍵自增
使用數據庫主鍵自增的方式算是比較常用的了，以MySQL為例，在新建表時指定主鍵以auto_increment的方式自動增長生成，或者再指定個增長步長，這在小規模單機部署的業務系統裡面足夠使用了，使用簡單而且具備一定業務性，但是在分佈式高併發的系統裡面，卻是不適用的，分佈式系統涉及到分庫分表，跨機器甚至跨機房部署的環境下，數據庫自增的方式滿足不了業務需求，同時在高併發大量訪問的情況之下，數據庫的承受能力是有限的，我們簡單的陳列一下這種方式的優缺點。
優點
- 實現簡單，依靠數據庫即可，成本小。
- ID數字化，單調自增，滿足數據庫存儲和查詢性能。
- 具有一定的業務可讀性。
缺點
- 強依賴DB，存在單點問題，如果數據庫宕機，則業務不可用。
- DB生成ID性能有限，單點數據庫壓力大，無法扛高併發場景。
適用場景
- 小規模的，數據訪問量小的業務場景。
- 無高併發場景，插入記錄可控的場景。
基於數據庫多實例主鍵自增
上面我們大致講解了數據庫主鍵自增的方式，討論的時單機部署的情況，如果要以此提高ID生成的效率，可以橫向擴展機器，平衡單點數據庫的壓力，這種方案如何實現呢？那就是在auto_increment的基礎之上，設置step增長步長，讓DB之前生成的ID趨勢遞增且不重複。
從上圖可以看出，水平擴展的數據庫集群，有利於解決數據庫單點壓力的問題，同時為了ID生成特性，將自增步長按照機器數量來設置，但是，這裡有個缺點就是不能再擴容了，如果再擴容，ID就沒法兒生成了，步長都用光了，那如果你要解決新增機器帶來的問題，你或許可以將第三臺機器的ID起始生成位置設定離現在的ID比較遠的位置，同時把新的步長設置進去，同時修改舊機器上ID生成的步長，但必須在ID還沒有增長到新增機器設置的開始自增ID值，否則就要出現重複了。
優點
- 解決了ID生成的單點問題，同時平衡了負載。
缺點
- 一定確定好步長，將對後續的擴容帶來困難，而且單個數據庫本身的壓力還是大，無法滿足高併發。
適用場景
- 數據量不大，數據庫不需要擴容的場景。
這種方案，除了難以適應大規模分佈式和高併發的場景，普通的業務規模還是能夠勝任的，所以這種方案還是值得積累。
基於類Snowflake算法
我們現在的項目都不大，使用的是IdWorker——國內開源的基於snowflake算法思想實現的一款分佈式ID生成器，snowflake雪花算法是twitter公司內部分佈式項目採用的ID生成算法，現在開源並流行了起來，下面是Snowflake算法的ID構成圖。
這種方案巧妙地把64位分別劃分成多段，分開表示時間戳差值、機器標識和隨機序列，先以此生成一個64位地二進制正整數，然後再轉換成十進制進行存儲。
其中，1位標識符，不使用且標記為0；41位時間戳，用來存儲時間戳的差值；10位機器碼，可以標識1024個機器節點，如果機器分機房部署（IDC），這10位還可以拆分，比如5位表示機房ID，5位表示機器ID，這樣就有32*32種組合，一般來說是足夠了；最後的12位隨即序列，用來記錄毫秒內的計數，一個節點就能夠生成4096個ID序號。所以綜上所述，綜合計算下來，理論上Snowflake算法方案的QPS大約為409.6w/s，性能足夠強悍了，而且這種方式，能夠確保集群中每個節點生成的ID都是不同的，且區間內遞增。
優點
- 每秒能夠生成百萬個不同的ID，性能佳。
- 時間戳值在高位，中間是固定的機器碼，自增的序列在地位，整個ID是趨勢遞增的。
- 能夠根據業務場景數據庫節點佈置靈活挑戰bit位劃分，靈活度高。
缺點
- 強依賴於機器時鐘，如果時鐘回撥，會導致重複的ID生成，所以一般基於此的算法發現時鐘回撥，都會拋異常處理，阻止ID生成，這可能導致服務不可用。
適用場景
- 雪花算法有很明顯的缺點就是時鐘依賴，如果確保機器不存在時鐘回撥情況的話，那使用這種方式生成分佈式ID是可行的，當然小規模系統完全是能夠使用的。
基於Redis生成辦法
Redis的INCR命令能夠將key中存儲的數字值增一，得益於此操作的原子特性，我們能夠巧妙地使用此來做分佈式ID地生成方案，還可以配合其他如時間戳值、機器標識等聯合使用。
優點
- 有序遞增，可讀性強。
- 能夠滿足一定性能。
缺點
- 強依賴於Redis，可能存在單點問題。
- 佔用寬帶，而且需要考慮網絡延時等問題帶來地性能衝擊。
適用場景
- 對性能要求不是太高，而且規模較小業務較輕的場景，而且Redis的運行情況有一定要求，注意網絡問題和單點壓力問題，如果是分佈式情況，那考慮的問題就更多了，所以一幫情況下這種方式用的比較少。
Redis的方案其實可靠性有待考究，畢竟依賴於網絡，延時故障或者宕機都可能導致服務不可用，這種風險是不得不考慮在系統設計內的。
回到頂部(go to top)
基於美團的Leaf方案
從上面的幾種分佈式ID方案可以看出，能夠解決一定問題，但是都有明顯缺陷，為此，美團在數據庫的方案基礎上做了一個優化，提出了一個叫做Leaf-segment的數據庫方案。
原方案我們每次獲取ID都需要去讀取一次數據庫，這在高併發和大數據量的情況下很容易造成數據庫的壓力，那能不能一次性獲取一批ID呢，這樣就無需頻繁的造訪數據庫了。
Leaf-segment的方案就是採用每次獲取一個ID區間段的方式來解決，區間段用完之後再去數據庫獲取新的號段，這樣一來可以大大減輕數據庫的壓力，那怎麼做呢？
很簡單，我們設計一張表如下：
其中biz_tag用來區分業務，max_id表示該biz_tag目前所被分配的ID號段的最大值，step表示每次分配的號段長度，後面的desc和update_time分別表示業務描述和上一次更新號段的時間。原來每次獲取ID都要訪問數據庫，現在只需要把Step設置的足夠合理如1000，那麼現在可以在1000個ID用完之後再去訪問數據庫了，看起來真的很酷。
我們現在可以這樣設計整個獲取分佈式ID的流程了：
- 用戶服務在註冊一個用戶時，需要一個用戶ID；會請求生成ID服務(是獨立的應用)的接口
- 生成ID的服務會去查詢數據庫，找到user_tag的id，現在的max_id為0，step=1000
- 生成ID的服務把max_id和step返回給用戶服務，並且把max_id更新為max_id = max_id + step，即更新為1000
- 用戶服務獲得max_id=0，step=1000；
- 這個用戶服務可以用[max_id + 1，max_id+step]區間的ID，即為[1，1000]
- 用戶服務把這個區間保存到jvm中
- 用戶服務需要用到ID的時候，在區間[1，1000]中依次獲取id，可採用AtomicLong中的getAndIncrement方法。
- 如果把區間的值用完了，再去請求生產ID的服務的接口，獲取到max_id為1000，即可以用[max_id + 1，max_id+step]區間的ID，即為[1001，2000]
顯而易見，這種方式很好的解決了數據庫自增的問題，而且可以自定義max_id的起點，可以自定義步長，非常靈活易於擴容，於此同時，這種方式也很好的解決了數據庫壓力問題，而且ID號段是存儲在JVM中的，性能獲得極大的保障，可用性也過得去，即時數據庫宕機了，因為JVM緩存的號段，系統也能夠因此撐住一段時間。
優點
- 擴張靈活，性能強能夠撐起大部分業務場景。
- ID號碼是趨勢遞增的，滿足數據庫存儲和查詢性能要求。
- 可用性高，即使ID生成服務器不可用，也能夠使得業務在短時間內可用，為排查問題爭取時間。
- 可以自定義max_id的大小，方便業務遷移，方便機器橫向擴張。
缺點
- ID號碼不夠隨機，完整的順序遞增可能帶來安全問題。
- DB宕機可能導致整個系統不可用，仍然存在這種風險，因為號段只能撐一段時間。
- 可能存在分佈式環境各節點同一時間爭搶分配ID號段的情況，這可能導致併發問題而出現ID重複生成。
上面的缺點同樣需要引起足夠的重視，美團技術團隊同樣想出了一個妙招——雙Buffer。
正如上所述，既然可能存在多個節點同時請求ID區間的情況，那麼避免這種情況就好了，Leaf-segment對此做了優化，將獲取一個號段的方式優化成獲取兩個號段，在一個號段用完之後不用立馬去更新號段，還有一個緩存號段備用 ，這樣能夠有效解決這種衝突問題，而且採用雙buffer的方式，在當前號段消耗了10%的時候就去檢查下一個號段有沒有準備好，如果沒有準備好就去更新下一個號段，噹噹前號段用完了就切換到下一個已經緩存好的號段去使用，同時在下一個號段消耗到10%的時候，又去檢測下一個號段有沒有準備好，如此往復。
下面簡要梳理下流程：
- 當前獲取ID在buffer1中，每次獲取ID在buffer1中獲取
- 當buffer1中的Id已經使用到了100，也就是達到區間的10%
- 達到了10%，先判斷buffer2中有沒有去獲取過，如果沒有就立即發起請求獲取ID線程，此線程把獲取到的ID，設置到buffer2中。
- 如果buffer1用完了，會自動切換到buffer2
- buffer2用到10%了，也會啟動線程再次獲取，設置到buffer1中
- 依次往返
雙buffer的方案考慮的很完善，有單獨的線程去觀察下一個buffer何時去更新，兩個buffer之間的切換使用也解決了臨時去數據庫更新號段可能引起的併發問題。這樣的方式能夠增加JVM中業務ID的可用性，而且建議segment的長度為業務高峰期QPS的100倍（經驗值，具體可根據自己業務來設定），這樣即使DB宕機了，業務ID的生成也能夠維持相當長的時間，而且可以有效的兼容偶爾的網絡抖動等問題。
優點
- 基本的數據庫問題都解決了，而且行之有效。
- 基於JVM存儲雙buffer的號段，減少了數據庫查詢，減少了網絡依賴，效率更高。
缺點
- segment號段長度是固定的，業務量大時可能會頻繁更新號段，因為原本分配的號段會一下子用完。
- 如果號段長度設置的過長，但凡緩存中有號段沒有消耗完，其他節點重新獲取的號段與之前相比可能跨度會很大。
針對上面的缺點，美團有重新提出動態調整號段長度的方案。
動態調整Step
一般情況下，如果你的業務不會有明顯的波峰波谷，可以不用太在意調整Step，因為平穩的業務量長期運行下來都基本上固定在一個步長之間，但是如果是像美團這樣有明顯的活動期，那麼Step是要具備足夠的彈性來適應業務量不同時間段內的暴增或者暴跌。
假設服務QPS為Q，號段長度為L，號段更新週期為T，那麼Q * T = L。最開始L長度是固定的，導致隨著Q的增長，T會越來越小。但是本方案本質的需求是希望T是固定的。那麼如果L可以和Q正相關的話，T就可以趨近一個定值了。所以本方案每次更新號段的時候，會根據上一次更新號段的週期T和號段長度step，來決定下一次的號段長度nextStep，下面是一個簡單的算法，意在說明動態更新的意思：
<code>T < 15min，nextStep = step * 215min < T < 30min，nextStep = stepT > 30min，nextStep = step / 2/<code>
至此，滿足了號段消耗穩定趨於某個時間區間的需求。當然，面對瞬時流量幾十、幾百倍的暴增，該種方案仍不能滿足可以容忍數據庫在一段時間不可用、系統仍能穩定運行的需求。因為本質上來講，此方案雖然在DB層做了些容錯方案，但是ID號段下發的方式，最終還是需要強依賴DB，最後，還是需要在數據庫高可用上下足工夫。
閱讀更多 瀟灑的程序員 的文章
