1、引言

在中大型IM系統中，聊天消息的唯一ID生成策略是個很重要的技術點。不夸張的說，聊天消息ID貫穿了整個聊天生命周期的幾乎每一個算法、邏輯和過程，ID生成策略的好壞有可能直接決定系統在某些技術點上的設計難易度。

有中小型IM場景下，消息ID可以簡單處理，反正只要唯一就行，而中大型場景下，因為要考慮到分布式的性能、一致性等，所以要考慮的問題點又是另一回事。

總之就是，IM的消息ID生成這件事，可深可淺，看似簡單但實際可探索的邊界可以很大，這也是為什么即時通訊網為此專門整理了《IM消息ID技術專題》系列文章的原因。做技術所謂厚積薄發，了解的越多，你的技術可操作空間也就越大，希望隨著這個系列文章的閱讀，可以為你在ID生成這一塊的技術選型帶來更多有益的啟發。

另外，因為即時通訊網主要關注的是即時通訊方面的系統開發，但并不意味著這個系統文章只適用于IM或消息推送等實時通信系統，它同樣適用于其它需要唯一ID的應用中。

本文將要分享的是滴滴開源的分布式ID生成器Tinyid的技術原理、使用方法等等，希望能進一步為你打開這方面的技術視野。

學習交流：

- 移動端IM開發入門文章：《新手入門一篇就夠：從零開發移動端IM》

- 開源IM框架源碼：https://github.com/JackJiang2011/MobileIMSDK

（本文同步發布于：http://www.52im.net/thread-3129-1-1.html）

2、專題目錄

本文是“IM消息ID技術專題”系列文章的第6篇，專題總目錄如下：

《IM消息ID技術專題(一)：微信的海量IM聊天消息序列號生成實踐（算法原理篇）》

《IM消息ID技術專題(二)：微信的海量IM聊天消息序列號生成實踐（容災方案篇）》

《IM消息ID技術專題(三)：解密融云IM產品的聊天消息ID生成策略》

《IM消息ID技術專題(四)：深度解密美團的分布式ID生成算法》

《IM消息ID技術專題(五)：開源分布式ID生成器UidGenerator的技術實現》

《IM消息ID技術專題(六)：深度解密滴滴的高性能ID生成器(Tinyid)》（* 本文）

3、什么是Tinyid？

Tinyid是滴滴用JAVA開發的一款分布式id生成系統，基于數據庫號段算法實現。

Tinyid是在美團的ID生成算法Leaf的基礎上擴展而來，支持數據庫多主節點模式，它提供了REST API和Java客戶端兩種獲取方式，相對來說使用更方便。不過，和美團的Leaf算法不同的是，Tinyid只支持號段一種模式（并不支持Snowflake模式）。（有關美團的Leaf算法，可以詳讀《IM消息ID技術專題(四)：深度解密美團的分布式ID生成算法》）

Tinyid目前在滴滴客服部門使用，且通過tinyid-client方式接入，每天生成的是億級別的id。性能上，據稱單實例能達到1千萬QPS。

它的開源地址是：

主地址：https://github.com/didi/tinyid

備地址：https://github.com/52im/tinyid

PS：滴滴在Tinyid工程頁面寫了一句話，“tinyid，并不是滴滴官方產品，只是滴滴擁有的代碼”，我語文不好，這句該怎么理解呢？

4、Tinyid的主要技術特性

主要特性總結一下就是：

1）全局唯一的long型ID：即id極限數量是2的64次方；

2）趨勢遞增的id：趨勢遞增的意思是，id是遞增但不一定是連續的（這跟微信的ID生成策略類似）；

3）提供 http 和 java-client 方式接入；

4）支持批量獲取ID；

5）支持生成1,3,5,7,9…序列的ID；

6）支持多個db的配置。

適用的場景：只關心ID是數字，趨勢遞增的系統，可以容忍ID不連續，可以容忍ID的浪費。

不適用場景：像類似于訂單ID的業務，因生成的ID大部分是連續的，容易被掃庫、或者推算出訂單量等信息。

另外：微信的聊天消息ID生成算法也是基于號段、趨勢遞增這種邏輯，如果有興趣，可以詳見：《IM消息ID技術專題(一)：微信的海量IM聊天消息序列號生成實踐（算法原理篇）》。

5、Tinyid的技術優勢

性能方面：

1）http方式：訪問性能取決于http server的能力，網絡傳輸速度；

2）java-client方式：id為本地生成，號段長度(step)越長，qps越大，如果將號段設置足夠大，則qps可達1000w+。

可用性方面：

1）當db不可用時，因為server有緩存，所以還可以使用一段時間；

2）如果配置了多個db，則只要有1個db存活，則服務可用；

3）使用tiny-client時，只要server有一臺存活，則理論上server全掛，因為client有緩存，也可以繼續使用一段時間。

6、Tinyid的技術原理詳解

6.1 ID生成系統的技術要點

在簡單系統中，我們常常使用db的id自增方式來標識和保存數據，隨著系統的復雜，數據的增多，分庫分表成為了常見的方案，db自增已無法滿足要求。

這時候全局唯一的id生成系統就派上了用場，當然這只是id生成其中的一種應用場景。

那么，一個成熟的id生成系統應該具備哪些能力呢？

1）唯一性：無論怎樣都不能重復，id全局唯一是最基本的要求；

2）高性能：基礎服務盡可能耗時少，如果能夠本地生成最好；

3）高可用：雖說很難實現100%的可用性，但是也要無限接近于100%的可用性；

4）易用性：能夠拿來即用，接入方便，同時在系統設計和實現上要盡可能的簡單。

6.2 Tinyid的實現原理

我們先來看一下最常見的id生成方式，db的auto_increment，相信大家都非常熟悉。

我也見過一些同學在實戰中使用這種方案來獲取一個id，這個方案的優點是簡單，缺點是每次只能向db獲取一個id，性能比較差，對db訪問比較頻繁，db的壓力會比較大。

那么，是不是可以對這種方案優化一下呢？可否一次向db獲取一批id呢？答案當然是可以的。

一批id，我們可以看成是一個id范圍，例如(1000,2000]，這個1000到2000也可以稱為一個“號段”，我們一次向db申請一個號段，加載到內存中，然后采用自增的方式來生成id，這個號段用完后，再次向db申請一個新的號段，這樣對db的壓力就減輕了很多，同時內存中直接生成id，性能則提高了很多。

PS：簡單解釋一下什么是號段模式：

號段模式就是從數據庫批量的獲取自增ID，每次從數據庫取出一個號段范圍，例如 (1,1000] 代表1000個ID，業務服務將號段在本地生成1~1000的自增ID并加載到內存。

那么保存db號段的表該怎設計呢？我們繼續往下看。

6.3 DB號段算法描述

如上表，我們很容易想到的是db直接存儲一個范圍(start_id,end_id]，當這批id使用完畢后，我們做一次update操作，update start_id=2000(end_id), end_id=3000(end_id+1000)，update成功了，則說明獲取到了下一個id范圍。仔細想想，實際上start_id并沒有起什么作用，新的號段總是(end_id,end_id+1000]。

所以這里我們更改一下，db設計應該是這樣的：

如上表所示：

1）我們增加了biz_type，這個代表業務類型，不同的業務的id隔離；

2）max_id則是上面的end_id了，代表當前最大的可用id；

3）step代表號段的長度，可以根據每個業務的qps來設置一個合理的長度；

4）version是一個樂觀鎖，每次更新都加上version，能夠保證并發更新的正確性。

那么我們可以通過如下幾個步驟來獲取一個可用的號段：

A、查詢當前的max_id信息：select id, biz_type, max_id, step, version from tiny_id_info where biz_type='test';

B、計算新的max_id: new_max_id = max_id + step；

C、更新DB中的max_id：update tiny_id_info set max_id=#{new_max_id} , verison=version+1 where id=#{id} and max_id=#{max_id} and version=#{version}；

D、如果更新成功，則可用號段獲取成功，新的可用號段為(max_id, new_max_id]；

E、如果更新失敗，則號段可能被其他線程獲取，回到步驟A，進行重試。

6.4 號段生成方案的簡單架構

如上述內容，我們已經完成了號段生成邏輯。

那么我們的id生成服務架構可能是這樣的：

如上圖，id生成系統向外提供http服務，請求經過我們的負載均衡router，到達其中一臺tinyid-server，從事先加載好的號段中獲取一個id。

如果號段還沒有加載，或者已經用完，則向db再申請一個新的可用號段，多臺server之間因為號段生成算法的原子性，而保證每臺server上的可用號段不重，從而使id生成不重。

可以看到：

1）如果tinyid-server如果重啟了，那么號段就作廢了，會浪費一部分id；

2）同時id也不會連續；

3）每次請求可能會打到不同的機器上，id也不是單調遞增的，而是趨勢遞增的（不過這對于大部分業務都是可接受的）。

6.5 簡單架構的問題

到此一個簡單的id生成系統就完成了，那么是否還存在問題呢？

回想一下我們最開始的id生成系統要求：高性能、高可用、簡單易用。

在上面這套架構里，至少還存在以下問題：

1）當id用完時需要訪問db加載新的號段，db更新也可能存在version沖突，此時id生成耗時明顯增加；

2）db是一個單點，雖然db可以建設主從等高可用架構，但始終是一個單點；

3）使用http方式獲取一個id，存在網絡開銷，性能和可用性都不太好。

6.6 優化辦法及最終架構

1）雙號段緩存：

對于號段用完需要訪問db，我們很容易想到在號段用到一定程度的時候，就去異步加載下一個號段，保證內存中始終有可用號段，則可避免性能波動。

2）增加多db支持：

db只有一個master時，如果db不可用(down掉或者主從延遲比較大)，則獲取號段不可用。實際上我們可以支持多個db，比如2個db，A和B，我們獲取號段可以隨機從其中一臺上獲取。那么如果A,B都獲取到了同一號段，我們怎么保證生成的id不重呢？tinyid是這么做的，讓A只生成偶數id，B只生產奇數id，對應的db設計增加了兩個字段，如下所示

delta代表id每次的增量，remainder代表余數，例如可以將A，B都delta都設置2，remainder分別設置為0，1則，A的號段只生成偶數號段，B是奇數號段。通過delta和remainder兩個字段我們可以根據使用方的需求靈活設計db個數，同時也可以為使用方提供只生產類似奇數的id序列。

3）增加tinyid-client：

使用http獲取一個id，存在網絡開銷，是否可以本地生成id？

為此我們提供了tinyid-client，我們可以向tinyid-server發送請求來獲取可用號段，之后在本地構建雙號段、id生成，如此id生成則變成純本地操作，性能大大提升，因為本地有雙號段緩存，則可以容忍tinyid-server一段時間的down掉，可用性也有了比較大的提升。

4）tinyid最終架構：

最終我們的架構可能是這樣的：

下面是更具體的代碼調用邏輯：

如上圖所示，下面是關于這個代碼調用邏輯圖的說明：

1）nextId和getNextSegmentId是tinyid-server對外提供的兩個http接口；

2）nextId是獲取下一個id，當調用nextId時，會傳入bizType，每個bizType的id數據是隔離的，生成id會使用該bizType類型生成的IdGenerator；

3）getNextSegmentId是獲取下一個可用號段，tinyid-client會通過此接口來獲取可用號段；

4）IdGenerator是id生成的接口；

5）IdGeneratorFactory是生產具體IdGenerator的工廠，每個biz_type生成一個IdGenerator實例。通過工廠，我們可以隨時在db中新增biz_type，而不用重啟服務；

6）IdGeneratorFactory實際上有兩個子類IdGeneratorFactoryServer和IdGeneratorFactoryClient，區別在于，getNextSegmentId的不同，一個是DbGet,一個是HttpGet；

7）CachedIdGenerator則是具體的id生成器對象，持有currentSegmentId和nextSegmentId對象，負責nextId的核心流程。nextId最終通過AtomicLong.andAndGet(delta)方法產生。

具體的代碼實現，有興趣可以直接閱讀源碼：

主地址：https://github.com/didi/tinyid

備地址：https://github.com/52im/tinyid

7、Tinyid的最佳實踐

1）tinyid-server推薦部署到多個機房的多臺機器：

多機房部署可用性更高，http方式訪問需使用方考慮延遲問題。

2）推薦使用tinyid-client來獲取id，好處如下：

a、id為本地生成(調用AtomicLong.addAndGet方法)，性能大大增加；

b、client對server訪問變的低頻，減輕了server的壓力；

c、因為低頻，即便client使用方和server不在一個機房，也無須擔心延遲；

d、即便所有server掛掉，因為client預加載了號段，依然可以繼續使用一段時間

注：使用tinyid-client方式，如果client機器較多頻繁重啟，可能會浪費較多的id，這時可以考慮使用http方式。

3）推薦db配置兩個或更多：

db配置多個時，只要有1個db存活，則服務可用多db配置，如配置了兩個db，則每次新增業務需在兩個db中都寫入相關數據。