[TOC] ## 前言 幾乎所有的業務系統，都有生成一個記錄標識的需求，例如： 1. 消息標識：message-id 2. 訂單標識：order-id 3. 帖子標識：tiezi-id 這個記錄標識往往就是數據庫中的**唯一主鍵**，數據庫上會建立聚集索引（cluster index），即在物理存儲上以這個字段排序。 這個記錄標識上的查詢，往往又有分頁或者排序的業務需求，例如： 1. 拉取最新的一頁消息：selectmessage-id/ order by time/ limit 100 2. 拉取最新的一頁訂單：selectorder-id/ order by time/ limit 100 3. 拉取最新的一頁帖子：selecttiezi-id/ order by time/ limit 100 所以往往要有一個time字段，并且在time字段上建立普通索引（non-cluster index）。 我們都知道普通索引存儲的是實際記錄的指針，其訪問效率會比聚集索引慢，如果記錄標識在生成時能夠基本按照時間有序，則可以省去這個time字段的索引查詢： `select message-id/ (order by message-id)/limit 100` 再次強調，能這么做的前提是，message-id的生成基本是**趨勢時間遞增的**。 這就引出了記錄標識生成（也就是上文提到的三個XXX-id）的兩大核心需求： 1. 全局唯一 2. 趨勢有序 > 小節:由于普通索引慢與主鍵索引,但分頁和排序又需要又時間索引,所以可以使用時間相關的遞增主鍵 ## 使用數據庫的 auto_increment 來生成全局唯一遞增ID **優點：** 1. 簡單，使用數據庫已有的功能 2. 能夠保證唯一性 3. 能夠保證遞增性 4. 步長固定 **缺點：** 1. 可用性難以保證：數據庫常見架構是一主多從+讀寫分離，生成自增ID是寫請求，主庫掛了就玩不轉了 1. 擴展性差，性能有上限：因為寫入是單點，數據庫主庫的寫性能決定ID的生成性能上限，并且難以擴展 **改進方法：** 1. 增加主庫，避免寫入單點 2. 數據水平切分，保證各主庫生成的ID不重復  **缺點**是： 1. 喪失了ID生成的“絕對遞增性”：先訪問庫0生成0,3，再訪問庫1生成1，可能導致在非常短的時間內，ID生成不是絕對遞增的（這個問題不大，我們的目標是趨勢遞增，不是絕對遞增） 1. 數據庫的寫壓力依然很大，每次生成ID都要訪問數據庫 ## 單點批量ID生成服務 使用批量的方式降低數據庫寫壓力  數據庫使用雙master保證可用性，數據庫中只存儲當前ID的最大值，例如ID生成服務假設每次批量拉取6個ID，服務訪問數據庫，將當前ID的最大值修改為5，這樣應用訪問ID生成服務索要ID，ID生成服務不需要每次訪問數據庫，就能依次派發0,1,2,3,4,5這些ID了，當ID發完后，再將ID的最大值修改為11，就能再次派發6,7,8,9,10,11這些ID了，于是數據庫的壓力就降低到原來的1/6了。 **優點：** （1）保證了ID生成的絕對遞增有序 （2）大大的降低了數據庫的壓力，ID生成可以做到每秒生成幾萬幾十萬個 **缺點：** （1）服務仍然是單點 （2）如果服務掛了，服務重啟起來之后，繼續生成ID可能會不連續，中間出現空洞（服務內存是保存著0,1,2,3,4,5，數據庫中max-id是5，分配到3時，服務重啟了，下次會從6開始分配，4和5就成了空洞，不過這個問題也不大） （3）雖然每秒可以生成幾萬幾十萬個ID，但畢竟還是有性能上限，無法進行水平擴展 **改進方法：** 單點服務的常用高可用優化方案是“備用服務”，也叫“影子服務”，所以我們能用以下方法優化上述缺點（1）：  如上圖，對外提供的服務是主服務，有一個影子服務時刻處于備用狀態，當主服務掛了的時候影子服務頂上。這個切換的過程對調用方是透明的，可以自動完成，常用的技術是vip+keepalived，具體就不在這里展開 ## uuid 上述方案來生成ID，雖然性能大增，但由于是單點系統，總還是存在性能上限的。同時，上述兩種方案，不管是數據庫還是服務來生成ID，業務方Application都需要進行一次遠程調用，比較耗時。有沒有一種本地生成ID的方法，即高性能，又時延低呢？ uuid是一種常見的方案：string ID =GenUUID(); 優點： （1）本地生成ID，不需要進行遠程調用，時延低 （2）擴展性好，基本可以認為沒有性能上限 缺點： （1）無法保證趨勢遞增 （2）uuid過長，往往用字符串表示，作為主鍵建立索引查詢效率低，常見優化方案為“轉化為兩個uint64整數存儲”或者“折半存儲”（折半后不能保證唯一性） ## 類雪花算法 snowflake是twitter開源的分布式ID生成算法，其**核心思想**是：一個long型的ID，使用其中41bit作為毫秒數，10bit作為機器編號，12bit作為毫秒內序列號。這個算法單機每秒內理論上最多可以生成1000\*(2^12)，也就是400W的ID，完全能滿足業務的需求。 借鑒snowflake的思想，結合各公司的業務邏輯和并發量，可以實現自己的分布式ID生成算法。 舉例，假設某公司ID生成器服務的需求如下： （1）單機高峰并發量小于1W，預計未來5年單機高峰并發量小于10W （2）有2個機房，預計未來5年機房數量小于4個 （3）每個機房機器數小于100臺 （4）目前有5個業務線有ID生成需求，預計未來業務線數量小于10個 （5）… 分析過程如下： （1）高位取從2016年1月1日到現在的毫秒數（假設系統ID生成器服務在這個時間之后上線），假設系統至少運行10年，那至少需要10年\*365天\*24小時\*3600秒\*1000毫秒=320\*10^9，差不多預留39bit給毫秒數 （2）每秒的單機高峰并發量小于10W，即平均每毫秒的單機高峰并發量小于100，差不多預留7bit給每毫秒內序列號 （3）5年內機房數小于4個，預留2bit給機房標識 （4）每個機房小于100臺機器，預留7bit給每個機房內的服務器標識 （5）業務線小于10個，預留4bit給業務線標識  這樣設計的64bit標識，可以保證： （1）每個業務線、每個機房、每個機器生成的ID都是不同的 （2）同一個機器，每個毫秒內生成的ID都是不同的 （3）同一個機器，同一個毫秒內，以序列號區區分保證生成的ID是不同的 （4）將毫秒數放在最高位，保證生成的ID是趨勢遞增的 **缺點：** （1）由于“沒有一個全局時鐘”，每臺服務器分配的ID是絕對遞增的，但從全局看，生成的ID只是趨勢遞增的（有些服務器的時間早，有些服務器的時間晚） **最后一個容易忽略的問題：** 生成的ID，例如message-id/ order-id/ tiezi-id，在數據量大時往往需要分庫分表，這些ID經常作為取模分庫分表的依據，為了分庫分表后數據均勻，ID生成往往有“取模隨機性”的需求，所以我們通常把每秒內的序列號放在ID的最末位，保證生成的ID是隨機的。 又如果，我們在跨毫秒時，序列號總是歸0，會使得序列號為0的ID比較多，導致生成的ID取模后不均勻。解決方法是，序列號不是每次都歸0，而是歸一個0到9的隨機數，這個地方