分布式架構系統生成全局唯一序列號的一個思路
一、相關背景
分布式架構下，唯一序列號生成是我們在設計一個系統，尤其是數據庫使用分庫分表的時候常常會遇見的問題。當分成若干個sharding表后，如何能夠快速拿到一個唯一序列號，是經常遇到的問題。
在攜程賬號數據庫遷移MySql過程中，我們對用戶ID的生成方案進行了新的設計，要求能夠支撐攜程現有的新用戶注冊體量。
本文通過攜程用戶ID生成器的實現，希望能夠對大家設計分庫分表的唯一id有一些新的思路。
二、特性需求
- 全局唯一
- 支持高并發
- 能夠體現一定屬性
- 高可靠，容錯單點故障
- 高性能
三、業內方案
生成ID的方法有很多，來適應不同的場景、需求以及性能要求。
常見方式有：
1、利用數據庫遞增，全數據庫唯一。
優點：明顯，可控。
缺點：單庫單表，數據庫壓力大。
2、UUID， 生成的是length=32的16進制格式的字符串，如果回退為byte數組共16個byte元素，即UUID是一個128bit長的數字，一般用16進制表示。
優點：對數據庫壓力減輕了。
缺點：但是排序怎么辦？
此外還有UUID的變種，增加一個時間拼接，但是會造成id非常長。
3、twitter在把存儲系統從MySQL遷移到Cassandra的過程中由于Cassandra沒有順序ID生成機制，于是自己開發了一套全局唯一ID生成服務：Snowflake。
- 41位的時間序列（精確到毫秒，41位的長度可以使用69年）
- 10位的機器標識（10位的長度最多支持部署1024個節點）
- 12位的計數順序號（12位的計數順序號支持每個節點每毫秒產生4096個ID序號） ***位是符號位，始終為0。
優點：高性能，低延遲；獨立的應用；按時間有序。
缺點：需要獨立的開發和部署。
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毫秒；
附流程圖：
