分散式架構系統生成全局唯一序列號的一個思路

一、相關背景

分散式架構下，唯一序列號生成是我們在設計一個系統，尤其是資料庫使用分庫分表的時候常常會遇見的問題。當分成若干個sharding表後，如何能夠快速拿到一個唯一序列號，是經常遇到的問題。

在攜程賬號資料庫遷移MySql過程中，我們對用戶ID的生成方案進行了新的設計，要求能夠支撐攜程現有的新用戶註冊體量。

本文通過攜程用戶ID生成器的實現，希望能夠對大家設計分庫分表的唯一id有一些新的思路。

二、特性需求

1. 全局唯一
2. 支持高並發
3. 能夠體現一定屬性
4. 高可靠，容錯單點故障
5. 高性能

三、業內方案

生成ID的方法有很多，來適應不同的場景、需求以及性能要求。

常見方式有：

1、利用資料庫遞增，全資料庫唯一。

優點：明顯，可控。

缺點：單庫單表，資料庫壓力大。

2、UUID， 生成的是length=32的16進位格式的字元串，如果回退為byte數組共16個byte元素，即UUID是一個128bit長的數字，一般用16進位表示。

優點：對資料庫壓力減輕了。

缺點：但是排序怎麼辦？

此外還有UUID的變種，增加一個時間拼接，但是會造成id非常長。

3、twitter在把存儲系統從MySQL遷移到Cassandra的過程中由於Cassandra沒有順序ID生成機制，於是自己開發了一套全局唯一ID生成服務：Snowflake。

1 41位的時間序列（精確到毫秒，41位的長度可以使用69年）

優點：高性能，低延遲；獨立的應用；按時間有序。

缺點：需要獨立的開發和部署。

4、Redis生成ID

當使用資料庫來生成ID性能不夠要求的時候，我們可以嘗試使用Redis來生成ID。這主要依賴於Redis是單線程的，所以也可以用生成全局唯一的ID。可以用Redis的原子操作INCR和INCRBY來實現。

可以使用Redis集群來獲取更高的吞吐量。假如一個集群中有5台Redis。可以初始化每台Redis的值分別是1,2,3,4,5，然後步長都是5。各個Redis生成的ID為：

A：1,6,11,16,21

B：2,7,12,17,22

C：3,8,13,18,23

D：4,9,14,19,24

E：5,10,15,20,25

比較適合使用Redis來生成每天從0開始的流水號。比如訂單號=日期+當日自增長號。可以每天在Redis中生成一個Key，使用INCR進行累加。

優點：

不依賴於資料庫，靈活方便，且性能優於資料庫。

數字ID天然排序，對分頁或者需要排序的結果很有幫助。

使用Redis集群也可以防止單點故障的問題。

缺點：

如果系統中沒有Redis，還需要引入新的組件，增加系統複雜度。

需要編碼和配置的工作量比較大，多環境運維很麻煩，

在開始時，程序實例負載到哪個redis實例一旦確定好，未來很難做修改。

5. Flicker的解決方案

因為MySQL本身支持auto_increment操作，很自然地，我們會想到藉助這個特性來實現這個功能。

Flicker在解決全局ID生成方案里就採用了MySQL自增長ID的機制（auto_increment + replace into + MyISAM）。

6．還有其他一些方案，比如京東淘寶等電商的訂單號生成。因為訂單號和用戶id在業務上的區別，訂單號儘可能要多些冗餘的業務信息，比如：

滴滴：時間+起點編號+車牌號

淘寶訂單：時間戳+用戶ID

其他電商：時間戳+下單渠道+用戶ID，有的會加上訂單第一個商品的ID。

而用戶ID，則要求含義簡單明了，包含註冊渠道即可，盡量短。

四、最終方案

最終我們選擇了以flicker方案為基礎進行優化改進。具體實現是，單表遞增，內存緩存號段的方式。

首先建立一張表，像這樣：

SEQUENCE_GENERATOR_TABLE

id stub

1 192.168.1.1

其中id是自增的，stub是伺服器ip

因為新資料庫採用mysql，所以使用mysql的獨有語法 replace to來更新記錄來獲得唯一id，例如這樣：

REPLACE INTO SEQUENCE_GENERATOR_TABLE (stub) VALUES ("192.168.1.1");

再用SELECT id FROM SEQUENCE_GENERATOR_TABLEWHERE stub = "192.168.1.1"; 把它拿回來。

到上面為止，我們只是在單台資料庫上生成ID，從高可用角度考慮，接下來就要解決單點故障問題。

這也就是為什麼要有這個機器ip欄位呢？就是為了防止多伺服器同時更新數據，取回的id混淆的問題。

所以，當多個伺服器的時候，這個表是這樣的：

id stub

5 192.168.1.1

2 192.168.1.2

3 192.168.1.3

4 192.168.1.4

每台伺服器只更新自己的那條記錄，保證了單線程操作單行記錄。

這時候每個機器拿到的分別是5,2,3,4這4個id。

至此，我們似乎解決這個伺服器隔離，原子性獲得id的問題，也和flicker方案基本一致。

但是追根溯源，在原理上，方案還是依靠資料庫的特性，每次生成id都要請求db，開銷很大。我們對此又進行優化，把這個id作為一個號段，而並不是要發出去的序列號，並且這個號段是可以配置長度的，可以1000也可以10000，也就是對拿回來的這個id放大多少倍的問題。

OK，我們從DB一次查詢操作的開銷，拿回來了1000個用戶id到內存中了。

現在的問題就是要解決同一台伺服器在高並發場景，讓大家順序拿號，別拿重複，也別漏拿。

這個問題簡單來說，就是個保持這個號段對象隔離性的問題。

AtomicLong是個靠譜的辦法。

當第一次拿回號段id後，擴大1000倍，然後賦值給這個變數atomic，這就是這個號段的第一個號碼。

atomic.set(n * 1000);

並且內存里保存一下最大id，也就是這個號段的最後一個號碼

currentMaxId = (n + 1) * 1000;

一個號段就形成了。

此時每次有請求來取號時候，判斷一下有沒有到最後一個號碼，沒有到，就拿個號，走人。

Long uid = atomic.incrementAndGet();

如果到達了最後一個號碼，那麼阻塞住其他請求線程，最早的那個線程去db取個號段，再更新一下號段的兩個值，就可以了。

這個方案，核心代碼邏輯不到20行，解決了分散式系統序列號生成的問題。

這裡有個小問題，就是在伺服器重啟後，因為號碼緩存在內存，會浪費掉一部分用戶ID沒有發出去，所以在可能頻繁發布的應用中，盡量減小號段放大的步長n，能夠減少浪費。

經過實踐，性能的提升遠遠重要於浪費一部分id。

如果再追求極致，可以監聽spring或者servlet上下文的銷毀事件，把當前即將發出去的用戶ID保存起來，下次啟動時候再撈回內存即可。

五、上線效果

運行5個多月，十分穩定。

SOA服務平均響應時間 0.59毫秒；

客戶端調用平均響應時間2.52毫秒；

附流程圖：

【作者簡介】丁宜人，10年java開發經驗。攜程技術中心基礎業務研發部用戶中心資深java工程師，負責攜程賬號的基礎服務和相關框架組件研發。之前在惠普公司供職6年，負責消息中間件產品研發。

更多來自攜程技術人的一手乾貨，歡迎搜索關注「攜程技術中心」微信公號。