分布式ID生成器 | 架構師之路

一、需求緣起

幾乎所有的業務系統,都有生成一個唯一記錄標識的需求,例如:

消息標識:message-id

訂單標識:order-id

帖子標識:tiezi-id

這個記錄標識往往就是數據庫中的主鍵,數據庫上會建立聚集索引(cluster index),即在物理存儲上以這個字段排序。

這個記錄標識上的查詢,往往又有分頁或者排序的業務需求,例如:

拉取最新的一頁消息

select message-id/ order by time/ limit 100

拉取最新的一頁訂單

select order-id/ order by time/ limit 100

拉取最新的一頁帖子

select tiezi-id/ order by time/ limit 100

所以往往要有一個time字段,並且在time字段上建立普通索引(non-cluster index)。

普通索引存儲的是實際記錄的指針,其訪問效率會比聚集索引慢,如果記錄標識在生成時能夠基本按照時間有序,則可以省去這個time字段的索引查詢:

select message-id/ (order by message-id)/limit 100

強調,能這麽做的前提是,message-id的生成基本是趨勢時間遞增的。

這就引出了記錄標識生成(也就是上文提到的三個XXX-id)的兩大核心需求:

全局唯一

趨勢有序

這也是本文要討論的核心問題:如何高效生成趨勢有序的全局唯一ID。

二、常見方法、不足與優化

方法一:使用數據庫的 auto_increment 來生成全局唯一遞增ID

優點:

簡單,使用數據庫已有的功能

能夠保證唯一性

能夠保證遞增性

步長固定

缺點:

可用性難以保證:數據庫常見架構是一主多從+讀寫分離,生成自增ID是寫請求,主庫掛了就玩不轉了

擴展性差,性能有上限:因為寫入是單點,數據庫主庫的寫性能決定ID的生成性能上限,並且難以擴展

改進方法:

冗余主庫,避免寫入單點

數據水平切分,保證各主庫生成的ID不重複
图片[1]-分布式ID生成器 | 架構師之路-小科科的春天

如上圖所述,由1個寫庫變成3個寫庫,每個寫庫設置不同的auto_increment初始值,以及相同的增長步長,以保證每個數據庫生成的ID是不同的(上圖中庫0生成0,3,6,9…,庫1生成1,4,7,10,庫2生成2,5,8,11…)

改進後的架構保證了可用性,但缺點是:

喪失了ID生成的“絕對遞增性”:先訪問庫0生成0,3,再訪問庫1生成1,可能導致在非常短的時間內,ID生成不是絕對遞增的(這個問題不大,目標是趨勢遞增,不是絕對遞增)

數據庫的寫壓力依然很大,每次生成ID都要訪問數據庫

為了解決上述兩個問題,引出了第二個常見的方案。

方法二:單點批量ID生成服務

分布式系統之所以難,很重要的原因之一是“沒有一個全局時鐘,難以保證絕對的時序”,要想保證絕對的時序,還是只能使用單點服務,用本地時鐘保證“絕對時序”。

數據庫寫壓力大,是因為每次生成ID都訪問了數據庫,可以使用批量的方式降低數據庫寫壓力。

图片[2]-分布式ID生成器 | 架構師之路-小科科的春天

如上圖所述,數據庫使用雙master保證可用性,數據庫中只存儲當前ID的最大值,例如0。

ID生成服務假設每次批量拉取6個ID,服務訪問數據庫,將當前ID的最大值修改為5,這樣應用訪問ID生成服務索要ID,ID生成服務不需要每次訪問數據庫,就能依次派發0,1,2,3,4,5這些ID了。

當ID發完後,再將ID的最大值修改為11,就能再次派發6,7,8,9,10,11這些ID了,於是數據庫的壓力就降低到原來的1/6。

優點:
保證了ID生成的絕對遞增有序

大大的降低了數據庫的壓力,ID生成可以做到每秒生成幾萬幾十萬個

缺點:

服務仍然是單點

如果服務掛了,服務重啟起來之後,繼續生成ID可能會不連續,中間出現空洞(服務內存是保存著0,1,2,3,4,5,數據庫中max-id是5,分配到3時,服務重啟了,下次會從6開始分配,4和5就成了空洞,不過這個問題也不大)

雖然每秒可以生成幾萬幾十萬個ID,但畢竟還是有性能上限,無法進行水平擴展

改進方法:

單點服務的常用高可用優化方案是“備用服務”,也叫“影子服務”,所以我們能用以下方法優化上述缺點(1):

图片[3]-分布式ID生成器 | 架構師之路-小科科的春天

如上圖,對外提供的服務是主服務,有一個影子服務時刻處於備用狀態,當主服務掛了的時候影子服務頂上。

這個切換的過程對調用方是透明的,可以自動完成,常用的技術是vip+keepalived,具體就不在這里展開。

另外,ID-gen-service也可以實施水平擴展,以解決上述缺點(3),但會引發一致性問題,具體解決方案詳見《淺談CAS在分布式ID生成方案上的應用》。

方法三:uuid/guid

不管是通過數據庫,還是通過服務來生成ID,業務方Application都需要進行一次遠程調用,比較耗時。

有沒有一種本地生成ID的方法,即高性能,又時延低呢?

uuid是一種常見的方案:

string ID =GenUUID();

優點:

本地生成ID,不需要進行遠程調用,時延低

擴展性好,基本可以認為沒有性能上限

缺點:

無法保證趨勢遞增

uuid過長,往往用字符串表示,作為主鍵建立索引查詢效率低,常見優化方案為“轉化為兩個uint64整數存儲”或者“折半存儲”(折半後不能保證唯一性)

方法四:取當前毫秒數

uuid是一個本地算法,生成性能高,但無法保證趨勢遞增,且作為字符串ID檢索效率低,有沒有一種能保證遞增的本地算法呢?

取當前毫秒數是一種常見方案:

uint64 ID = GenTimeMS();

優點:

本地生成ID,不需要進行遠程調用,時延低

生成的ID趨勢遞增

生成的ID是整數,建立索引後查詢效率高

缺點:

如果並發量超過1000,會生成重複的ID

這個缺點要了命了,不能保證ID的唯一性。當然,使用微秒可以降低沖突概率,但每秒最多只能生成1000000個ID,再多的話就一定會沖突了,所以使用微秒並不從根本上解決問題。

方法五:類snowflake算法

snowflake是twitter開源的分布式ID生成算法,其核心思想為,一個long型的ID:

41bit作為毫秒數

10bit作為機器編號

12bit作為毫秒內序列號

算法單機每秒內理論上最多可以生成1000*(2^12),也就是400W的ID,完全能滿足業務的需求。

借鑒snowflake的思想,結合各公司的業務邏輯和並發量,可以實現自己的分布式ID生成算法。

舉例,假設某公司ID生成器服務的需求如下:

  • 單機高峰並發量小於1W,預計未來5年單機高峰並發量小於10W
  • 有2個機房,預計未來5年機房數量小於4個
  • 每個機房機器數小於100臺
  • 目前有5個業務線有ID生成需求,預計未來業務線數量小於10個

分析過程如下:

高位取從2017年1月1日到現在的毫秒數(假設系統ID生成器服務在這個時間之後上線),假設系統至少運行10年,那至少需要10年365天24小時3600秒1000毫秒=320*10^9,差不多預留39bit給毫秒數

每秒的單機高峰並發量小於10W,即平均每毫秒的單機高峰並發量小於100,差不多預留7bit給每毫秒內序列號

5年內機房數小於4個,預留2bit給機房標識

每個機房小於100臺機器,預留7bit給每個機房內的服務器標識

業務線小於10個,預留4bit給業務線標識

图片[4]-分布式ID生成器 | 架構師之路-小科科的春天

這樣設計的64bit標識,可以保證:

每個業務線、每個機房、每個機器生成的ID都是不同的

同一個機器,每個毫秒內生成的ID都是不同的

同一個機器,同一個毫秒內,以序列號區區分保證生成的ID是不同的

將毫秒數放在最高位,保證生成的ID是趨勢遞增的

缺點:

由於“沒有一個全局時鐘”,每臺服務器分配的ID是絕對遞增的,但從全局看,生成的ID只是趨勢遞增的(有些服務器的時間早,有些服務器的時間晚)

© 版權聲明
THE END
喜歡就支持一下吧
點讚0 分享
評論 搶沙發
头像
歡迎您留下寶貴的見解!
提交
头像

暱稱

取消
暱稱表情代碼圖片