一種自平衡解決數據傾斜的分表方法

作者：京東零售 梁強

1、背景

這篇主要描述了B端令牌系統應用數據分表解決業務數據量增大，且存在的數據傾斜問題，主要面向的場景是一對多數據傾斜問題

1）B令牌的業務背景

先簡述一下B令牌的業務背景，B令牌系統是用於營銷場景中，將許多用戶綁定在一個令牌上，再將令牌綁定在促銷上，從而實現差異和精準營銷，一般情況下一個令牌的生命周期等同於這個促銷。

2）B端令牌的結構現狀

令牌和令牌用戶關係是一個一對多的關係，早期的令牌系統使用jed分庫，2個分片，中間進行了一次擴容達到了8個分片，存儲的數據行數達到了1.2億

3）數據和業務現狀

1.2億數據，分佈在8個分庫中，每個分庫平均1500萬，但由於分庫欄位使用的是令牌ID(token_uuid)，有得令牌用戶少，只有幾千到一萬，有的令牌用戶多，有100萬到150萬，令牌總數量並不多，只有2萬左右，所以導致數據存在傾斜，有的分庫有3000多萬數據，有的分庫可能只有幾百萬，這已經開始導致資料庫讀寫性能下降。而又因為令牌用戶關係表數據結構很簡單，雖然數據行數很多，但占用的空間卻不大。8個分庫總占用量還不足20G。同時令牌的生命周期基本和促銷相同，一個令牌服務於一個或幾個促銷後，就會慢慢過期被棄之不用，後續會繼續創建新的令牌。所以這些過期令牌是可以進行歸檔的。

同時由於B端業務的發展，業務訴求也更多，和業務溝通中瞭解到，未來會上線自動選人系統，由系統自動創建令牌，並選擇適合促銷的人群，未來每個月數據增量在3000萬左右，如果運行一年就會增加3.6億，屆時單表數據量平均會達到6000萬，當前的設計架構已經完全不能滿足業務需求。

同時目前也存在根據令牌ID分頁查詢令牌下用戶的功能，但僅限於給管理端運營使用，使用也不頻繁。

2、解決方案的思考

1) 怎麼解決這個問題

面對日益下降的資料庫讀寫性能，以及業務增長的需求，當下麵臨以下幾個問題：

1. 如何解決單表數據行數過多的問題

2. 當前分庫方案存在比較嚴重的數據傾斜

3. 如果應對未來數據的增長

2) 技術方案調研和對比

a.資料庫分表

一般情況應對第一個問題，通常都是分庫分表，而當下我們已經是8個分庫，而且8個分庫才占用了不足20G空間，單庫資源浪費嚴重，所以完全不會考慮繼續增加分庫的方式，所以分表才是解決辦法。

數據分表通常有兩種方式：垂直分表和水平分表。

垂直分表指的是將數據的列進行拆分，然後應用主鍵或其他業務欄位進行關聯，從而降低單表數據占用空間，或減少冗餘存儲，B令牌的場景數據結構簡單，數據占用空間小，所以不會使用該分表方式。

水平分表指的是將數據的行以一種路由演算法拆分到多張表中，讀取時候也基於這種路由演算法來讀取數據，這種分表策略一般用來應對數據結構不複雜，但數據行特別多的場景。這也是我們即將使用的方式。使用這種方式需要考慮的就是如何設計路由演算法，這裡也是使用這種方式來分表。

b.路由演算法

數據分表路由演算法的使用在業內也有多種，一種是利用一致性hash，選擇合適的分表欄位，對欄位值hash後值是固定的，使用該值通過取模或者按位運算的方式得到一個固定的序號，從而確定數據存儲在哪張表中。

比較常見的應用如分庫大多就是使用一致性hash的方式，通過即時計算分庫欄位的值判斷數據屬於哪個分庫從而決定將數據存入哪個分庫或者從哪個分庫讀取數據。而如果查詢時沒有指定分庫欄位則需要同時向所有分庫發出查詢請求，最後在彙總結果。

另外像java代碼的HashMap數據結構其實也是一種一致性hash演算法的分表策略，通過對key進行hash後決定將數據存入數組的哪個序號，HashMap裡面用的不是取模的方式獲取序號，而是使用按位運算的方式，使用這種方式也決定了HashMap的擴容都是按照2的x次方的大小進行擴容，以後有機會可以介紹這個原理。

上面就是HashMap中的一個簡化的數據Hash存儲過程，當然我省略了一些細節，比如HashMap中每一個節點都是一個鏈表（衝突過多還會變成紅黑樹）。應用在我們的場景中就可以將每個序號當成是一張數據表即可。

以上這種路由演算法的優點的路由策略簡單，實時計算也不用增加額外存儲空間，但也存在一個問題就是如果要擴容則需要將歷史數據重新hash一遍進行遷移，比如資料庫分庫如果增加分庫則需要將所有數據重新計算分庫，HashMap擴容也會執行rehash重新計算key在數組的序號。如果數據量太大，這種計算過程耗時將會很長。同時，如果數據表太少，或者選擇分片的欄位離散程度低都會導致數據傾斜。

還有一種分表演算法優化了這種rehash過程，這便是一致性hash環，這種方式是在實體節點之間抽象出很多虛擬節點，然後再利用一致性hash演算法將數據打在這些虛擬節點上，而每個實體節點其實是負責的該實體節點逆時針方向上和另一個實體節點相鄰的虛擬節點的數據。這種方式的好處是假如需要擴容增加節點，增加的節點放在環上任意位置，也只會影響到該節點順時針方向上相鄰節點的數據，只需要將該節點中的部分數據遷移到這個新節點上即可，大大降低rehash的過程。同時由於虛擬節點多，也可以增加讓數據更均勻的分佈在這個環上，只要將實體節點放置在合適的位置，就能最大程度保證的解決數據傾斜問題。

比如圖上就是一個一致性Hash環的hash過程，在整個環上有從0到2^32-1個節點，其中實線的就是真實節點，其他都是虛擬節點，張三通過hash後落到環上的虛擬節點，然後從虛擬節點的位置順時針尋找真實節點，最終數據就存儲在真實節點上，所以瘋驢子和李四就存儲在節點2上，王五在節點3上，鄭六在節點4上。

擴容了一個節點5號後，則需要將節點1和節點5之間的數據遷移到節點5上，其他節點數據則不用變更。但如圖上看到的，只加這一個節點，也容易導致每個節點負責的數據不均勻，比如節點2和節點5，相比於其他節點負責的數據就少了很多，所以擴容時最好是成倍擴容，這樣數據可以繼續保持均勻。

3) 思考我的方案

再回到B令牌的業務場景上來，需要能達成以下訴求

1. 首先必須使用水平分表來解決單表數據量過大的問題

2. 需要能支持根據令牌分頁查詢用戶

3. 由於當前業務數據增量在3000萬，但不排除未來業務繼續增長的可能，分表數量需要能支持未來擴展

4. 數據行數過高，未來在擴展時必須保證無需數據遷移或者數據遷移成本低

5. 需要解決數據傾斜問題，確保不因為單表數據量過大而導致整體性能降低

基於以上訴求，首先看問題b，如果要支持根據令牌分頁查詢用戶，就需要保證令牌下的所有用戶都在同一張表上，才能簡單的支持分頁查詢，否則用一些彙總歸併演算法則複雜程度過高了，而且表太多也會降低查詢性能。雖然也可以通過將數據異構es提供查詢功能，但僅僅是為了少量管理端的查詢訴求再進行數據異構，成本有些高收益並不明顯，也有些浪費資源。所以分表欄位就只能確定使用令牌ID。

而上面也提到令牌ID數量並不多，而且令牌下的用戶也從1萬到100萬不等，單純使用一致性hash的方式用令牌ID作為分表策略則會導致數據傾斜嚴重，而且未來擴容時數據遷移成本也很高。

但使用一致性hash環又會導致未來在擴容時最好是按2的倍數擴容，不然就會存在有的節點負責的虛擬節點多，有的節點負責虛擬節點少，導致數據不均勻。然而在和資料庫同事進行溝通，一個資料庫下的數據表數量不宜太多，否則會對資料庫帶來較大壓力，而一致性hash環這種方式可能擴兩三次容就會導致分表數達到一個很高的數值。

基於以上問題，在確定使用令牌id作為分表的前提下，就需要著重思考如何支持動態擴容和解決數據傾斜的問題。

3、方案落地

1) 方案概述

a.如何支持動態擴容

分表的欄位已經確定使用令牌ID，而前面也提到我們的數據結構是令牌和用戶是一對多的關係數據，那麼在創建令牌時hash出的分表序號存儲下來，後續基於存儲的分表序號進行路由，就可以保證未來擴容時也不會影響存量數據的路由，無需進行數據遷移。

b.如何解決數據傾斜

由於選用了令牌ID作為分表欄位，而各令牌數據量大小不一，數據傾斜就會是一個大問題。所以這裡就想辦法引入了一個分表水位的概念。

在用戶請求保存或刪除關係用戶數的時候，基於分表序號對當前分表數量進行一個增減的計數，當某個分表中的數據量處於高水位時，就將該分表從分表演算法中剔除，從而讓該分表不會繼續產生新的數據。

比如當設置閾值1000萬為高水位，由於以上5張表都沒有達到高水位，則創建令牌時根據令牌ID進行Hash後取模得到3，按順序獲取表，則當前令牌的分表號為b2b_token_user_3。後續關係數據都從該表中獲取。

運行一段時間後，表b2b_token_user_1數據量已經增長到了1200萬，超過了1000萬的水位，這時候在創建令牌則將該表移除，在此進行Hash後取模得到1，則當前分到的表就是b2b_token_user_2。而如果b2b_token_user_1的水位如果一直不能降下來，則該表後續都不會再參與分表，表中的數據量也不會再增加。

當然有一種可能就是所有表都進入了高水位，為了兜底，這時水位功能就失效，所有表都加入到分表中來。

c.定期數據歸檔，降低分表水位

如果表中的數據量只會不斷增加，而不會減少的話，那麼早晚所有的表都會達到高水位，這就不能達到動態的效果。上面背景中有提到，令牌創建後是為某一批促銷服務，促銷終止後，令牌也會失去作用，同時令牌上也有有效期，超過有效期的令牌也會失去作用。所以定期對數據進行歸檔就可以讓那些處於高水位的表把水位慢慢降下來，重新加入到分表中。

而且當前令牌已經存在了一張b2b_token_user的表，裡面的數據已經有1.2億，可以將該表作為圖上的0號表，這樣在第一次上線時只要將歷史令牌都的分表序號都記為0即可，存量數據就不需要再進行遷移，而該表數據量水位高，也不會參與分表。再搭配定期的數據歸檔，該表的水位也會慢慢將下來。

d.監控機制

雖然可以通過定期進行數據歸檔，可以讓表的水位降下來，但隨著業務發展，可能會存在大多數表都進入了高水位，並且都是有效數據的情況。這時候系統就會像HashMap判斷容量達到75%就自動擴容一樣，我們不能夠自動創建表，但當75%的表都進入高水位可以告警出來，開發人員監聽到告警人工介入，觀察是需要調高水位，還是進行表的擴容。

3) 不足

• 水位閾值和擴容監控

目前水位的閾值還是依靠人工手動設置，應該設置多大還是比較感性的，只能設置一個，在告警以後適當調整。不過其實可以在系統中自動監控介面讀寫性能的波動，發現大多數表達到高水位時，介面讀寫性能都沒有明顯變化，可以系統自動調高閾值，從而形成智能閾值。

而介面性能讀寫出現明顯變化時發現大多數表都達到了閾值，則可以告警提示應當考慮擴容。

4、總結

解決問題從來沒有銀彈，我們需要利用手裡的技術手段和工具，進行組合、適配，使之適合我們當下的業務和場景，沒有好或不好，只有適不適合。