大局僅有的 ID 幾乎是一切體系都會(huì)遇到的剛需。這個(gè) id 在查找, 存儲(chǔ)數(shù)據(jù), 加快檢索速度 等等很多方面都有著重要的意義。有多種戰(zhàn)略來獲取這個(gè)大局僅有的id，針對常見的幾種場景，我在這兒進(jìn)行簡略的總結(jié)和對比。

簡略剖析一下需求

所謂大局僅有的 id 其實(shí)往往對應(yīng)是生成僅有記載標(biāo)識(shí)的事務(wù)需求 。

這個(gè) id 常常是數(shù)據(jù)庫的主鍵，數(shù)據(jù)庫上會(huì)樹立集合索引（cluster index），即在物理存儲(chǔ)上以這個(gè)字段排序。這個(gè)記載標(biāo)識(shí)上的查詢，往往又有分頁或許排序的事務(wù)需求。所以往往要有一個(gè)time字段，而且在time字段上樹立一般索引（non-cluster index）。

一般索引存儲(chǔ)的是實(shí)踐記載的指針，其拜訪效率會(huì)比集合索引慢，假如記載標(biāo)識(shí)在生成時(shí)能夠基本依照時(shí)刻有序，則能夠省去這個(gè)time字段的索引查詢。

這就引出了記載標(biāo)識(shí)生成的兩大中心需求：

• 大局僅有
• 趨勢有序

常見生成戰(zhàn)略的優(yōu)缺陷對比

辦法一: 用數(shù)據(jù)庫的 auto_increment 來生成

長處：

• 此辦法運(yùn)用數(shù)據(jù)庫原有的功能，所以相對簡略
• 能夠確保僅有性
• 能夠確保遞加性
• id 之間的步長是固定且可自定義的

缺陷：

• 可用性難以確保：數(shù)據(jù)庫常見架構(gòu)是 一主多從 + 讀寫分離，生成自增ID是寫請求 主庫掛了就玩不轉(zhuǎn)了
• 擴(kuò)展性差，功能有上限：因?yàn)閷懭胧菃吸c(diǎn)，數(shù)據(jù)庫主庫的寫功能決定ID的生成功能上限，而且 難以擴(kuò)展

改善計(jì)劃：

• 冗余主庫，防止寫入單點(diǎn)
• 數(shù)據(jù)水平切分，確保各主庫生成的ID不重復(fù)

如上圖所述，由1個(gè)寫庫變成3個(gè)寫庫，每個(gè)寫庫設(shè)置不同的 auto_increment 初始值，以及相同的增長步長，以確保每個(gè)數(shù)據(jù)庫生成的ID是不同的（上圖中DB 01生成0,3,6,9…，DB 02生成1,4,7,10，DB 03生成2,5,8,11…）

改善后的架構(gòu)確保了可用性，但缺陷是

• 喪失了ID生成的“肯定遞加性”：先拜訪DB 01生成0,3，再拜訪DB 02生成1，可能導(dǎo)致在十分短的時(shí)刻內(nèi)，ID生成不是肯定遞加的（這個(gè)問題不大，目標(biāo)是趨勢遞加，不是肯定遞加
• 數(shù)據(jù)庫的寫壓力仍然很大，每次生成ID都要拜訪數(shù)據(jù)庫

為了處理這些問題，引出了以下辦法：

辦法二：單點(diǎn)批量ID生成服務(wù)

分布式體系之所以難，很重要的原因之一是“沒有一個(gè)大局時(shí)鐘，難以確?？隙ǖ臅r(shí)序”，要想確?？隙ǖ臅r(shí)序，仍是只能運(yùn)用單點(diǎn)服務(wù)，用本地時(shí)鐘確?！翱隙〞r(shí)序”。

數(shù)據(jù)庫寫壓力大，是因?yàn)槊看紊蒊D都拜訪了數(shù)據(jù)庫，能夠運(yùn)用批量的方式下降數(shù)據(jù)庫寫壓力。

如上圖所述，數(shù)據(jù)庫運(yùn)用雙master確?？捎眯裕瑪?shù)據(jù)庫中只存儲(chǔ)當(dāng)時(shí)ID的最大值，例如4。

ID生成服務(wù)假定每次批量拉取5個(gè)ID，服務(wù)拜訪數(shù)據(jù)庫，將當(dāng)時(shí)ID的最大值修改為4，這樣運(yùn)用拜訪ID生成服務(wù)索要ID，ID生成服務(wù)不需求每次拜訪數(shù)據(jù)庫，就能依次派發(fā)0,1,2,3,4這些ID了。

當(dāng)ID發(fā)完后，再將ID的最大值修改為11，就能再次派發(fā)6,7,8,9,10,11這些ID了，于是數(shù)據(jù)庫的壓力就下降到原來的1/6。

長處：

• 確保了ID生成的肯定遞加有序
• 大大的下降了數(shù)據(jù)庫的壓力，ID生成能夠做到每秒生成幾萬幾十萬個(gè)

缺陷：

• 服務(wù)仍然是單點(diǎn)
• 假如服務(wù)掛了，服務(wù)重啟起來之后，繼續(xù)生成ID可能會(huì)不連續(xù)，中心出現(xiàn)空泛（服務(wù)內(nèi)存是保存著0,1,2,3,4，數(shù)據(jù)庫中max-id是4，分配到3時(shí)，服務(wù)重啟了，下次會(huì)從5開端分配，3和4就成了空泛，不過這個(gè)問題也不大）
• 雖然每秒能夠生成幾萬幾十萬個(gè)ID，但畢竟仍是有功能上限，無法進(jìn)行水平擴(kuò)展

改善計(jì)劃

• 單點(diǎn)服務(wù)的常用高可用優(yōu)化計(jì)劃是“備用服務(wù)”，也叫“影子服務(wù)”，所以咱們能用以下辦法優(yōu)化上述缺陷：

如上圖，對外供給的服務(wù)是主服務(wù)，有一個(gè)影子服務(wù)時(shí)刻處于備用狀況，當(dāng)主服務(wù)掛了的時(shí)候影子服務(wù)頂上。這個(gè)切換的進(jìn)程對調(diào)用方是透明的，能夠主動(dòng)完成，常用的技術(shù)是 vip+keepalived。另外，id generate service 也能夠進(jìn)行水平擴(kuò)展，以處理上述缺陷，但會(huì)引發(fā)一致性問題。

辦法三：uuid / guid

不管是經(jīng)過數(shù)據(jù)庫，仍是經(jīng)過服務(wù)來生成ID，事務(wù)方Application都需求進(jìn)行一次長途調(diào)用，比較耗時(shí)。uuid是一種常見的本地生成ID的辦法。

UUID uuid = UUID.randomUUID();

長處：

• 本地生成ID，不需求進(jìn)行長途調(diào)用，時(shí)延低
• 擴(kuò)展性好，基本能夠以為沒有功能上限

缺陷：

• 無法確保趨勢遞加
• uuid過長，往往用字符串表明，作為主鍵樹立索引查詢效率低，常見優(yōu)化計(jì)劃為“轉(zhuǎn)化為兩個(gè)uint64整數(shù)存儲(chǔ)”或許“減半存儲(chǔ)”（減半后不能確保僅有性）

辦法四：取當(dāng)時(shí)毫秒數(shù)

uuid是一個(gè)本地算法，生成功能高，但無法確保趨勢遞加，且作為字符串ID檢索效率低，有沒有一種能確保遞加的本地算法呢？- 取當(dāng)時(shí)毫秒數(shù)是一種常見計(jì)劃。

長處：

• 本地生成ID，不需求進(jìn)行長途調(diào)用，時(shí)延低
• 生成的ID趨勢遞加
• 生成的ID是整數(shù)，樹立索引后查詢效率高

缺陷：

• 假如并發(fā)量超越1000，會(huì)生成重復(fù)的ID
• 這個(gè)缺陷要了命了，不能確保ID的僅有性。當(dāng)然，運(yùn)用微秒能夠下降沖突概率，但每秒最多只能生成1000000個(gè)ID，再多的話就一定會(huì)沖突了，所以運(yùn)用微秒并不從根本上處理問題。

辦法五：運(yùn)用 Redis 來生成 id

當(dāng)運(yùn)用數(shù)據(jù)庫來生成ID功能不行要求的時(shí)候，咱們能夠嘗試運(yùn)用Redis來生成ID。這主要依賴于Redis是單線程的，所以也能夠用生成大局僅有的ID。能夠用Redis的原子操作 INCR 和 INCRBY 來完成。

長處：

• 依賴于數(shù)據(jù)庫，靈活方便，且功能優(yōu)于數(shù)據(jù)庫。
• 數(shù)字ID天然排序，對分頁或許需求排序的結(jié)果很有協(xié)助。

缺陷：

• 假如體系中沒有Redis，還需求引進(jìn)新的組件，增加體系復(fù)雜度。
• 需求編碼和配置的作業(yè)量比較大。

辦法六：Twitter 開源的 Snowflake 算法

snowflake 是 twitter 開源的分布式ID生成算法，其中心思想為，一個(gè)long型的ID：

• 41 bit 作為毫秒數(shù) - 41位的長度能夠運(yùn)用69年
• 10 bit 作為機(jī)器編號(hào) （5個(gè)bit是數(shù)據(jù)中心，5個(gè)bit的機(jī)器ID） - 10位的長度最多支撐布置1024個(gè)節(jié)點(diǎn)
• 12 bit 作為毫秒內(nèi)序列號(hào) - 12位的計(jì)數(shù)順序號(hào)支撐每個(gè)節(jié)點(diǎn)每毫秒發(fā)生4096個(gè)ID序號(hào)

算法單機(jī)每秒內(nèi)理論上最多能夠生成1000*(2^12)，也就是400W的ID，完全能滿足事務(wù)的需求。

該算法 java 版本的完成代碼如下：

package com; public class SnowflakeIdGenerator {  //================================================Algorithm's Parameter=============================================  // 體系開端時(shí)刻截 (UTC 2017-06-28 00:00:00)  private final long startTime = 1498608000000L;  // 機(jī)器id所占的位數(shù)  private final long workerIdBits = 5L;  // 數(shù)據(jù)標(biāo)識(shí)id所占的位數(shù)  private final long dataCenterIdBits = 5L;  // 支撐的最大機(jī)器id(十進(jìn)制)，結(jié)果是31 (這個(gè)移位算法能夠很快的計(jì)算出幾位二進(jìn)制數(shù)所能表明的最大十進(jìn)制數(shù))  // -1L 左移 5位 (worker id 所占位數(shù)) 即 5位二進(jìn)制所能取得的最大十進(jìn)制數(shù) - 31  private final long maxWorkerId = -1L ^ (-1L << workerIdBits);  // 支撐的最大數(shù)據(jù)標(biāo)識(shí)id - 31  private final long maxDataCenterId = -1L ^ (-1L << dataCenterIdBits);  // 序列在id中占的位數(shù)  private final long sequenceBits = 12L;  // 機(jī)器ID 左移位數(shù) - 12 (即末 sequence 所占用的位數(shù))  private final long workerIdMoveBits = sequenceBits;  // 數(shù)據(jù)標(biāo)識(shí)id 左移位數(shù) - 17(12+5)  private final long dataCenterIdMoveBits = sequenceBits + workerIdBits;  // 時(shí)刻截向 左移位數(shù) - 22(5+5+12)  private final long timestampMoveBits = sequenceBits + workerIdBits + dataCenterIdBits;  // 生成序列的掩碼(12位所對應(yīng)的最大整數(shù)值)，這兒為4095 (0b111111111111=0xfff=4095)  private final long sequenceMask = -1L ^ (-1L << sequenceBits);  //=================================================Works's Parameter================================================  /**  * 作業(yè)機(jī)器ID(0~31)  */  private long workerId;  /**  * 數(shù)據(jù)中心ID(0~31)  */  private long dataCenterId;  /**  * 毫秒內(nèi)序列(0~4095)  */  private long sequence = 0L;  /**  * 前次生成ID的時(shí)刻截  */  private long lastTimestamp = -1L;  //===============================================Constructors=======================================================  /**  * 構(gòu)造函數(shù)  *  * @param workerId     作業(yè)ID (0~31)  * @param dataCenterId 數(shù)據(jù)中心ID (0~31)  */  public SnowflakeIdGenerator(long workerId, long dataCenterId) {  if (workerId > maxWorkerId || workerId < 0) {  throw new IllegalArgumentException(String.format("Worker Id can't be greater than %d or less than 0", maxWorkerId));  }  if (dataCenterId > maxDataCenterId || dataCenterId < 0) {  throw new IllegalArgumentException(String.format("DataCenter Id can't be greater than %d or less than 0", maxDataCenterId));  }  this.workerId = workerId;  this.dataCenterId = dataCenterId;  }  // ==================================================Methods========================================================  // 線程安全的取得下一個(gè) ID 的辦法  public synchronized long nextId() {  long timestamp = currentTime();  //假如當(dāng)時(shí)時(shí)刻小于上一次ID生成的時(shí)刻戳: 闡明體系時(shí)鐘回退過 - 這個(gè)時(shí)候應(yīng)當(dāng)拋出反常  if (timestamp < lastTimestamp) {  throw new RuntimeException(  String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));  }  //假如是同一時(shí)刻生成的，則進(jìn)行毫秒內(nèi)序列  if (lastTimestamp == timestamp) {  sequence = (sequence + 1) & sequenceMask;  //毫秒內(nèi)序列溢出 即 序列 > 4095  if (sequence == 0) {  //阻塞到下一個(gè)毫秒,取得新的時(shí)刻戳  timestamp = blockTillNextMillis(lastTimestamp);  }  }  //時(shí)刻戳改動(dòng)，毫秒內(nèi)序列重置  else {  sequence = 0L;  }  //前次生成ID的時(shí)刻截  lastTimestamp = timestamp;  //移位并經(jīng)過或運(yùn)算拼到一起組成64位的ID  return ((timestamp - startTime) << timestampMoveBits) //  | (dataCenterId << dataCenterIdMoveBits) //  | (workerId << workerIdMoveBits) //  | sequence;  }  // 阻塞到下一個(gè)毫秒 即 直到取得新的時(shí)刻戳  protected long blockTillNextMillis(long lastTimestamp) {  long timestamp = currentTime();  while (timestamp <= lastTimestamp) {  timestamp = currentTime();  }  return timestamp;  }  // 取得以毫秒為單位的當(dāng)時(shí)時(shí)刻  protected long currentTime() {  return System.currentTimeMillis();  }  //====================================================Test Case=====================================================  public static void main(String[] args) {  SnowflakeIdGenerator idWorker = new SnowflakeIdGenerator(0, 0);  for (int i = 0; i < 100; i++) {  long id = idWorker.nextId();  //System.out.println(Long.toBinaryString(id));  System.out.println(id);  }  } }