滴滴開源分佈式 ID 生成服務
ID Generator id 生成器 分佈式 id 生成系統,簡單易用、高性能、高可用的 id 生成系統
簡介
Tinyid 是用 Java 開發的一款分佈式 id 生成系統,基於數據庫號段算法實現,關於這個算法可以參考美團 leaf 或者 tinyid 原理介紹。Tinyid 擴展了 leaf-segment 算法,支持了多 db(master),同時提供了 java-client(sdk) 使 id 生成本地化,獲得了更好的性能與可用性。Tinyid 在滴滴客服部門使用,均通過 tinyid-client 方式接入,每天生成億級別的 id。
tinyid 系統架構圖
下面是一些關於這個架構圖的說明:
-
nextId 和 getNextSegmentId 是 tinyid-server 對外提供的兩個 http 接口
-
nextId 是獲取下一個 id,當調用 nextId 時,會傳入 bizType,每個 bizType 的 id 數據是隔離的,生成 id 會使用該 bizType 類型生成的 IdGenerator。
-
getNextSegmentId 是獲取下一個可用號段,tinyid-client 會通過此接口來獲取可用號段
-
IdGenerator 是 id 生成的接口
-
IdGeneratorFactory 是生產具體 IdGenerator 的工廠,每個 biz_type 生成一個 IdGenerator 實例。通過工廠,我們可以隨時在 db 中新增 biz_type,而不用重啓服務
-
IdGeneratorFactory 實際上有兩個子類 IdGeneratorFactoryServer 和 IdGeneratorFactoryClient,區別在於,getNextSegmentId 的不同,一個是 DbGet, 一個是 HttpGet
-
CachedIdGenerator 則是具體的 id 生成器對象,持有 currentSegmentId 和 nextSegmentId 對象,負責 nextId 的核心流程。nextId 最終通過 AtomicLong.andAndGet(delta) 方法產生。
性能與可用性
性能
-
http 方式訪問,性能取決於 http server 的能力,網絡傳輸速度
-
java-client 方式,id 爲本地生成,號段長度 (step) 越長,qps 越大,如果將號段設置足夠大,則 qps 可達 1000w+
可用性
-
依賴 db,當 db 不可用時,因爲 server 有緩存,所以還可以使用一段時間,如果配置了多個 db,則只要有 1 個 db 存活,則服務可用
-
使用 tiny-client,只要 server 有一臺存活,則理論上可用,server 全掛,因爲 client 有緩存,也可以繼續使用一段時間
Tinyid 的特性
-
全局唯一的 long 型 id
-
趨勢遞增的 id,即不保證下一個 id 一定比上一個大
-
非連續性
-
提供 http 和 java client 方式接入
-
支持批量獲取 id
-
支持生成 1,3,5,7,9… 序列的 id
-
支持多個 db 的配置,無單點
適用場景: 只關心 id 是數字,趨勢遞增的系統,可以容忍 id 不連續,有浪費的場景 不適用場景: 類似訂單 id 的業務 (因爲生成的 id 大部分是連續的,容易被掃庫、或者測算出訂單量)
推薦使用方式
-
tinyid-server 推薦部署到多個機房的多臺機器
-
多機房部署可用性更高,http 方式訪問需使用方考慮延遲問題
-
推薦使用 tinyid-client 來獲取 id,好處如下:
-
id 爲本地生成 (調用 AtomicLong.addAndGet 方法),性能大大增加
-
client 對 server 訪問變的低頻,減輕了 server 的壓力
-
因爲低頻,即便 client 使用方和 server 不在一個機房,也無須擔心延遲
-
即便所有 server 掛掉,因爲 client 預加載了號段,依然可以繼續使用一段時間 注: 使用 tinyid-client 方式,如果 client 機器較多頻繁重啓,可能會浪費較多的 id,這時可以考慮使用 http 方式
-
推薦 db 配置兩個或更多:
-
db 配置多個時,只要有 1 個 db 存活,則服務可用 多 db 配置,如配置了兩個 db,則每次新增業務需在兩個 db 中都寫入相關數據
tinyid 的原理
Id 生成系統要點
在簡單系統中,我們常常使用 db 的 id 自增方式來標識和保存數據,隨着系統的複雜,數據的增多,分庫分表成爲了常見的方案,db 自增已無法滿足要求。這時候全局唯一的 id 生成系統就派上了用場。當然這只是 id 生成其中的一種應用場景。那麼 id 生成系統有哪些要求呢?
-
全局唯一的 id: 無論怎樣都不能重複,這是最基本的要求了
-
高性能: 基礎服務儘可能耗時少,如果能夠本地生成最好
-
高可用: 雖說很難實現 100% 的可用性,但是也要無限接近於 100% 的可用性
-
簡單易用: 能夠拿來即用,接入方便,同時在系統設計和實現上要儘可能的簡單
Tinyid 的實現原理
我們先來看一下最常見的 id 生成方式,db 的 auto_increment,相信大家都非常熟悉,我也見過一些同學在實戰中使用這種方案來獲取一個 id,這個方案的優點是簡單,缺點是每次只能向 db 獲取一個 id,性能比較差,對 db 訪問比較頻繁,db 的壓力會比較大。那麼是不是可以對這種方案優化一下呢,可否一次向 db 獲取一批 id 呢?答案當然是可以的。
一批 id,我們可以看成是一個 id 範圍,例如 (1000,2000],這個 1000 到 2000 也可以稱爲一個 "號段",我們一次向 db 申請一個號段,加載到內存中,然後採用自增的方式來生成 id,這個號段用完後,再次向 db 申請一個新的號段,這樣對 db 的壓力就減輕了很多,同時內存中直接生成 id,性能則提高了很多。那麼保存 db 號段的表該怎設計呢?
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 設計應該是這樣的
-
這裏我們增加了 biz_type,這個代表業務類型,不同的業務的 id 隔離
-
max_id 則是上面的 end_id 了,代表當前最大的可用 id
-
step 代表號段的長度,可以根據每個業務的 qps 來設置一個合理的長度
-
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,進行重試
號段生成方案的簡單架構
如上我們已經完成了號段生成邏輯,那麼我們的 id 生成服務架構可能是這樣的
id 生成系統向外提供 http 服務,請求經過我們的負載均衡 router,到達其中一臺 tinyid-server,從事先加載好的號段中獲取一個 id,如果號段還沒有加載,或者已經用完,則向 db 再申請一個新的可用號段,多臺 server 之間因爲號段生成算法的原子性,而保證每臺 server 上的可用號段不重,從而使 id 生成不重
可以看到如果 tinyid-server 如果重啓了,那麼號段就作廢了,會浪費一部分 id;同時 id 也不會連續;每次請求可能會打到不同的機器上,id 也不是單調遞增的,而是趨勢遞增的,不過這對於大部分業務都是可接受的。
簡單架構的問題
到此一個簡單的 id 生成系統就完成了,那麼是否還存在問題呢?回想一下我們最開始的 id 生成系統要求,高性能、高可用、簡單易用,在上面這套架構裏,至少還存在以下問題:
-
當 id 用完時需要訪問 db 加載新的號段,db 更新也可能存在 version 衝突,此時 id 生成耗時明顯增加
-
db 是一個單點,雖然 db 可以建設主從等高可用架構,但始終是一個單點
-
使用 http 方式獲取一個 id,存在網絡開銷,性能和可用性都不太好
優化辦法如下:
(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 最終架構
最終我們的架構可能是這樣的
-
tinyid 提供 http 和 tinyid-client 兩種方式接入
-
tinyid-server 內部緩存兩個號段
-
號段基於 db 生成,具有原子性
-
db 支持多個
-
tinyid-server 內置 easy-router 選擇 db
項目地址
github 地址:https://github.com/didi/tinyid
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/0ClrLh00d1R70tiQJdHhbQ