微信序列號生成器架構設計及演變
每天萬億級調用的重量級系統，每次申請序列號平時調用耗時1ms，99.9%的調用耗時小于3ms，服務部署于數百臺4核CPU服務器上！
老司機介紹
曾欽松，微信高級工程師，目前負責微信后臺基礎服務、朋友圈后臺等開發優化，致力于高可用高性能后臺系統的設計與研發。2011年畢業于西安電子科技大學，早先曾在騰訊搜搜從事檢索架構、分布式數據庫方面的工作。
微信在立項之初，就已確立了利用數據版本號實現終端與后臺的數據增量同步機制，確保發消息時消息可靠送達對方手機，避免了大量潛在的家庭糾紛。時至今日，微信已經走過第五個年頭，這套同步機制仍然在消息收發、朋友圈通知、好友數據更新等需要數據同步的地方發揮著核心的作用。
而在這同步機制的背后，需要一個高可用、高可靠的序列號生成器來產生同步數據用的版本號。這個序列號生成器我們稱之為seqsvr，目前已經發展為一個每天萬億級調用的重量級系統，其中每次申請序列號平時調用耗時1ms，99.9%的調用耗時小于3ms，服務部署于數百臺4核CPU服務器上。 本文會重點介紹seqsvr的架構核心思想，以及seqsvr隨著業務量快速上漲所做的架構演變。
背景
微信服務器端為每一份需要與客戶端同步的數據（例如消息）都會賦予一個唯一的、遞增的序列號（后文稱為sequence），作為這份數據的版本號。在客戶端與服務器端同步的時候，客戶端會帶上已經同步下去數據的最大版本號，后臺會根據客戶端最大版本號與服務器端的最大版本號，計算出需要同步的增量數據，返回給客戶端。這樣不僅保證了客戶端與服務器端的數據同步的可靠性，同時也大幅減少了同步時的冗余數據。
這里不用樂觀鎖機制來生成版本號，而是使用了一個獨立的seqsvr來處理序列號操作，一方面因為業務有大量的sequence查詢需求——查詢已經分配出去的最后一個sequence，而基于seqsvr的查詢操作可以做到非常輕量級，避免對存儲層的大量IO查詢操作；另一方面微信用戶的不同種類的數據存在不同的Key-Value系統中，使用統一的序列號有助于避免重復開發，同時業務邏輯可以很方便地判斷一個用戶的各類數據是否有更新。
從seqsvr申請的、用作數據版本號的sequence，具有兩種基本的性質：
- 遞增的64位整型變量
- 每個用戶都有自己獨立的64位sequence空間
舉個例子，小明當前申請的sequence為100，那么他下一次申請的sequence，可能為101，也可能是110，總之一定大于之前申請的100。而小紅呢，她的sequence與小明的sequence是獨立開的，假如她當前申請到的sequence為50，然后期間不管小明申請多少次sequence怎么折騰，都不會影響到她下一次申請到的值（很可能是51）。
這里用了每個用戶獨立的64位sequence的體系，而不是用一個全局的64位（或更高位）sequence，很大原因是全局唯一的sequence會有非常嚴重的申請互斥問題，不容易去實現一個高性能高可靠的架構。對微信業務來說，每個用戶獨立的64位sequence空間已經滿足業務要求。
目前sequence用在終端與后臺的數據同步外，同時也廣泛用于微信后臺邏輯層的基礎數據一致性cache中，大幅減少邏輯層對存儲層的訪問。雖然一個用于終端——后臺數據同步，一個用于后臺cache的一致性保證，場景大不相同。
但我們仔細分析就會發現，兩個場景都是利用sequence可靠遞增的性質來實現數據的一致性保證，這就要求我們的seqsvr保證分配出去的sequence是穩定遞增的，一旦出現回退必然導致各種數據錯亂、消息消失；另外，這兩個場景都非常普遍，我們在使用微信的時候會不知不覺地對應到這兩個場景：小明給小紅發消息、小紅拉黑小明、小明發一條失戀狀態的朋友圈，一次簡單的分手背后可能申請了無數次sequence。
微信目前擁有數億的活躍用戶，每時每刻都會有海量sequence申請，這對seqsvr的設計也是個極大的挑戰。那么，既要sequence可靠遞增，又要能頂住海量的訪問，要如何設計seqsvr的架構？我們先從seqsvr的架構原型說起。
架構原型
不考慮seqsvr的具體架構的話，它應該是一個巨大的64位數組，而我們每一個微信用戶，都在這個大數組里獨占一格8bytes的空間，這個格子就放著用戶已經分配出去的最后一個sequence：cur_seq。每個用戶來申請sequence的時候，只需要將用戶的cur_seq+=1，保存回數組，并返回給用戶。
圖1. 小明申請了一個sequence，返回101
預分配中間層
任何一件看起來很簡單的事，在海量的訪問量下都會變得不簡單。前文提到，seqsvr需要保證分配出去的sequence遞增（數據可靠），還需要滿足海量的訪問量（每天接近萬億級別的訪問）。滿足數據可靠的話，我們很容易想到把數據持久化到硬盤，但是按照目前每秒千萬級的訪問量（~10^7 QPS），基本沒有任何硬盤系統能扛住。
后臺架構設計很多時候是一門關于權衡的哲學，針對不同的場景去考慮能不能降低某方面的要求，以換取其它方面的提升。仔細考慮我們的需求，我們只要求遞增，并沒有要求連續，也就是說出現一大段跳躍是允許的（例如分配出的sequence序列：1,2,3,10,100,101）。于是我們實現了一個簡單優雅的策略：
- 內存中儲存最近一個分配出去的sequence：cur_seq，以及分配上限：max_seq
- 分配sequence時，將cur_seq++，同時與分配上限max_seq比較：如果cur_seq > max_seq，將分配上限提升一個步長max_seq += step，并持久化max_seq
- 重啟時，讀出持久化的max_seq，賦值給cur_seq
圖2. 小明、小紅、小白都各自申請了一個sequence，但只有小白的max_seq增加了步長100
這樣通過增加一個預分配sequence的中間層，在保證sequence不回退的前提下，大幅地提升了分配sequence的性能。實際應用中每次提升的步長為10000，那么持久化的硬盤IO次數從之前~10^7 QPS降低到~10^3 QPS，處于可接受范圍。在正常運作時分配出去的sequence是順序遞增的，只有在機器重啟后，第一次分配的sequence會產生一個比較大的跳躍，跳躍大小取決于步長大小。
分號段共享存儲
請求帶來的硬盤IO問題解決了，可以支持服務平穩運行，但該模型還是存在一個問題：重啟時要讀取大量的max_seq數據加載到內存中。
我們可以簡單計算下，以目前uid（用戶唯一ID）上限2^32個、一個max_seq 8bytes的空間，數據大小一共為32GB，從硬盤加載需要不少時間。另一方面，出于數據可靠性的考慮，必然需要一個可靠存儲系統來保存max_seq數據，重啟時通過網絡從該可靠存儲系統加載數據。如果max_seq數據過大的話，會導致重啟時在數據傳輸花費大量時間，造成一段時間不可服務。
為了解決這個問題，我們引入號段Section的概念，uid相鄰的一段用戶屬于一個號段，而同個號段內的用戶共享一個max_seq，這樣大幅減少了max_seq數據的大小，同時也降低了IO次數。
圖3. 小明、小紅、小白屬于同個Section，他們共用一個max_seq。在每個人都申請一個sequence的時候，只有小白突破了max_seq上限，需要更新max_seq并持久化
目前seqsvr一個Section包含10萬個uid，max_seq數據只有300+KB，為我們實現從可靠存儲系統讀取max_seq數據重啟打下基礎。
工程實現
工程實現在上面兩個策略上做了一些調整，主要是出于數據可靠性及災難隔離考慮
- 把存儲層和緩存中間層分成兩個模塊StoreSvr及AllocSvr。StoreSvr為存儲層，利用了多機NRW策略來保證數據持久化后不丟失；AllocSvr則是緩存中間層，部署于多臺機器，每臺AllocSvr負責若干號段的sequence分配，分攤海量的sequence申請請求。
- 整個系統又按uid范圍進行分Set，每個Set都是一個完整的、獨立的StoreSvr+AllocSvr子系統。分Set設計目的是為了做災難隔離，一個Set出現故障只會影響該Set內的用戶，而不會影響到其它用戶。
圖4. 原型架構圖
容災設計
接下來我們會介紹seqsvr的容災架構。我們知道，后臺系統絕大部分情況下并沒有一種唯一的、完美的解決方案，同樣的需求在不同的環境背景下甚至有可能演化出兩種截然不同的架構。既然架構是多變的，那純粹講架構的意義并不是特別大，期間也會講下seqsvr容災設計時的一些思考和權衡，希望對大家有所幫助。
seqsvr的容災模型在五年中進行過一次比較大的重構，提升了可用性、機器利用率等方面。其中不管是重構前還是重構后的架構，seqsvr一直遵循著兩條架構設計原則：
- 保持自身架構簡單
- 避免對外部模塊的強依賴
這兩點都是基于seqsvr可靠性考慮的，畢竟seqsvr是一個與整個微信服務端正常運行息息相關的模塊。按照我們對這個世界的認識，系統的復雜度往往是跟可靠性成反比的，想得到一個可靠的系統一個關鍵點就是要把它做簡單。相信大家身邊都有一些這樣的例子，設計方案里有很多高大上、復雜的東西，同時也總能看到他們在默默地填一些高大上的坑。當然簡單的系統不意味著粗制濫造，我們要做的是理出最核心的點，然后在滿足這些核心點的基礎上，針對性地提出一個足夠簡單的解決方案。
那么， seqsvr最核心的點是什么呢？每個uid的sequence申請要遞增不回退。 這里我們發現，如果seqsvr滿足這么一個約束：任意時刻任意uid有且僅有一臺AllocSvr提供服務，就可以比較容易地實現sequence遞增不回退的要求。
圖5. 兩臺AllocSvr服務同個uid造成sequence回退。Client讀取到的sequence序列為101、201、102
但也由于這個約束，多臺AllocSvr同時服務同一個號段的多主機模型在這里就不適用了。我們只能采用單點服務的模式，當某臺AllocSvr發生服務不可用時，將該機服務的uid段切換到其它機器來實現容災。這里需要引入一個仲裁服務，探測AllocSvr的服務狀態，決定每個uid段由哪臺AllocSvr加載。出于可靠性的考慮，仲裁模塊并不直接操作AllocSvr，而是將加載配置寫到StoreSvr持久化，然后AllocSvr定期訪問StoreSvr讀取最新的加載配置，決定自己的加載狀態。
圖6. 號段遷移示意。通過更新加載配置把0~2號段從AllocSvrA遷移到AllocSvrB
同時，為了避免失聯AllocSvr提供錯誤的服務，返回臟數據，AllocSvr需要跟StoreSvr保持租約。這個租約機制由以下兩個條件組成：
- 租約失效：AllocSvr N秒內無法從StoreSvr讀取加載配置時，AllocSvr停止服務
- 租約生效：AllocSvr讀取到新的加載配置后，立即卸載需要卸載的號段，需要加載的新號段等待N秒后提供服務
圖7. 租約機制。AllocSvrB嚴格保證在AllocSvrA停止服務后提供服務
這兩個條件保證了切換時，新AllocSvr肯定在舊AllocSvr下線后才開始提供服務。但這種租約機制也會造成切換的號段存在小段時間的不可服務，不過由于微信后臺邏輯層存在重試機制及異步重試隊列，小段時間的不可服務是用戶無感知的，而且出現租約失效、切換是小概率事件，整體上是可以接受的。
到此講了AllocSvr容災切換的基本原理，接下來會介紹整個seqsvr架構容災架構的演變
容災1.0架構：主備容災
最初版本的seqsvr采用了主機+冷備機容災模式：全量的uid空間均勻分成N個Section，連續的若干個Section組成了一個Set，每個Set都有一主一備兩臺AllocSvr。正常情況下只有主機提供服務；在主機出故障時，仲裁服務切換主備，原來的主機下線變成備機，原備機變成主機后加載uid號段提供服務。
圖8. 容災1.0架構：主備容災
可能看到前文的敘述，有些同學已經想到這種容災架構。一主機一備機的模型設計簡單，并且具有不錯的可用性——畢竟主備兩臺機器同時不可用的概率極低，相信很多后臺系統也采用了類似的容災策略。
設計權衡
主備容災存在一些明顯的缺陷，比如備機閑置導致有一半的空閑機器；比如主備切換的時候，備機在瞬間要接受主機所有的請求，容易導致備機過載。既然一主一備容災存在這樣的問題，為什么一開始還要采用這種容災模型？事實上，架構的選擇往往跟當時的背景有關，seqsvr誕生于微信發展初期，也正是微信快速擴張的時候，選擇一主一備容災模型是出于以下的考慮：
- 架構簡單，可以快速開發
- 機器數少，機器冗余不是主要問題
- Client端更新AllocSvr的路由狀態很容易實現
前兩點好懂，人力、機器都不如時間寶貴。而第三點比較有意思，下面展開講下
微信后臺絕大部分模塊使用了一個自研的RPC框架，seqsvr也不例外。在這個RPC框架里，調用端讀取本地機器的client配置文件，決定去哪臺服務端調用。這種模型對于無狀態的服務端，是很好用的，也很方便實現容災。我們可以在client配置文件里面寫“對于號段x，可以去SvrA、SvrB、SvrC三臺機器的任意一臺訪問”，實現三主機容災。
但在seqsvr里，AllocSvr是預分配中間層，并不是無狀態的。而前面我們提到，AllocSvr加載哪些uid號段，是由保存在StoreSvr的加載配置決定的。那么這時候就尷尬了，業務想要申請某個uid的sequence，Client端其實并不清楚具體去哪臺AllocSvr訪問，client配置文件只會跟它說“AllocSvrA、AllocSvrB…這堆機器的某一臺會有你想要的sequence”。換句話講，原來負責提供服務的AllocSvrA故障，仲裁服務決定由AllocSvrC來替代AllocSvrA提供服務，Client要如何獲知這個路由信息的變更？
這時候假如我們的AllocSvr采用了主備容災模型的話，事情就變得簡單多了。我們可以在client配置文件里寫：對于某個uid號段，要么是AllocSvrA加載，要么是AllocSvrB加載。Client端發起請求時，盡管Client端并不清楚AllocSvrA和AllocSvrB哪一臺真正加載了目標uid號段，但是Client端可以先嘗試給其中任意一臺AllocSvr發請求，就算這次請求了錯誤的AllocSvr，那么就知道另外一臺是正確的AllocSvr，再發起一次請求即可。
也就是說，對于主備容災模型，最多也只會浪費一次的試探請求來確定AllocSvr的服務狀態，額外消耗少，編碼也簡單。可是，如果Svr端采用了其它復雜的容災策略，那么基于靜態配置的框架就很難去確定Svr端的服務狀態：Svr發生狀態變更，Client端無法確定應該向哪臺Svr發起請求。這也是為什么一開始選擇了主備容災的原因之一。
主備容災的缺陷
在我們的實際運營中，容災1.0架構存在兩個重大的不足：
- 擴容、縮容非常麻煩
- 一個Set的主備機都過載，無法使用其他Set的機器進行容災
在主備容災中，Client和AllocSvr需要使用完全一致的配置文件。變更這個配置文件的時候，由于無法實現在同一時間更新給所有的Client和AllocSvr，因此需要非常復雜的人工操作來保證變更的正確性（包括需要使用iptables來做請求轉發，具體的詳情這里不做展開）。
對于第二個問題，常見的方法是用一致性Hash算法替代主備，一個Set有多臺機器，過載機器的請求被分攤到多臺機器，容災效果會更好。在seqsvr中使用類似一致性Hash的容災策略也是可行的，只要Client端與仲裁服務都使用完全一樣的一致性Hash算法，這樣Client端可以啟發式地去嘗試，直到找到正確的AllocSvr。
例如對于某個uid，仲裁服務會優先把它分配到AllocSvrA，如果AllocSvrA掛掉則分配到AllocSvrB，再不行分配到AllocSvrC。那么Client在訪問AllocSvr時，按照AllocSvrA -> AllocSvrB -> AllocSvrC的順序去訪問，也能實現容災的目的。但這種方法仍然沒有克服前面主備容災面臨的配置文件變更的問題，運營起來也很麻煩。
容災2.0架構：嵌入式路由表容災
最后我們另辟蹊徑，采用了一種不同的思路：既然Client端與AllocSvr存在路由狀態不一致的問題，那么讓AllocSvr把當前的路由狀態傳遞給Client端，打破之前只能根據本地Client配置文件做路由決策的限制，從根本上解決這個問題。
所以在2.0架構中，我們把AllocSvr的路由狀態嵌入到Client請求sequence的響應包中，在不帶來額外的資源消耗的情況下，實現了Client端與AllocSvr之間的路由狀態一致。具體實現方案如下：
seqsvr所有模塊使用了統一的路由表，描述了uid號段到AllocSvr的全映射。這份路由表由仲裁服務根據AllocSvr的服務狀態生成，寫到StoreSvr中，由AllocSvr當作租約讀出，最后在業務返回包里旁路給Client端。
圖9. 容災2.0架構：動態號段遷移容災
把路由表嵌入到請求響應包看似很簡單的架構變動，卻是整個seqsvr容災架構的技術奇點。利用它解決了路由狀態不一致的問題后，可以實現一些以前不容易實現的特性。例如靈活的容災策略，讓所有機器都互為備機，在機器故障時，把故障機上的號段均勻地遷移到其它可用的AllocSvr上；還可以根據AllocSvr的負載情況，進行負載均衡，有效緩解AllocSvr請求不均的問題，大幅提升機器使用率。
另外在運營上也得到了大幅簡化。之前對機器進行運維操作有著繁雜的操作步驟，而新架構只需要更新路由即可輕松實現上線、下線、替換機器，不需要關心配置文件不一致的問題，避免了一些由于人工誤操作引發的故障。
圖10. 機器故障號段遷移
路由同步優化
把路由表嵌入到取sequence的請求響應包中，那么會引入一個類似“先有雞還是先有蛋”的哲學命題：沒有路由表，怎么知道去哪臺AllocSvr取路由表？另外，取sequence是一個超高頻的請求，如何避免嵌入路由表帶來的帶寬消耗？
這里通過在Client端內存緩存路由表以及路由版本號來解決，請求步驟如下：
- Client根據本地共享內存緩存的路由表，選擇對應的AllocSvr；如果路由表不存在，隨機選擇一臺AllocSvr
- 對選中的AllocSvr發起請求，請求帶上本地路由表的版本號
- AllocSvr收到請求，除了處理sequence邏輯外，判斷Client帶上版本號是否最新，如果是舊版則在響應包中附上最新的路由表
- Client收到響應包，除了處理sequence邏輯外，判斷響應包是否帶有新路由表。如果有，更新本地路由表，并決策是否返回第1步重試
基于以上的請求步驟，在本地路由表失效的時候，使用少量的重試便可以拉到正確的路由，正常提供服務。
總結
到此把seqsvr的架構設計和演變基本講完了，正是如此簡單優雅的模型，為微信的其它模塊提供了一種簡單可靠的一致性解決方案，支撐著微信五年來的高速發展，相信在可預見的未來仍然會發揮著重要的作用。