一種自平衡解決資料傾斜的分表方法

作者：京東零售樑強

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) 怎麼解決這個問題

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

如何解決單表資料行數過多的問題
當前分庫方案存在比較嚴重的資料傾斜
如果應對未來資料的增長

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令牌的業務場景上來，需要能達成以下訴求

首先必須使用水平分表來解決單表資料量過大的問題
需要能支援根據令牌分頁查詢使用者
由於當前業務資料增量在3000萬，但不排除未來業務繼續增長的可能，分表數量需要能支援未來擴充套件
資料行數過高，未來在擴充套件時必須保證無需資料遷移或者資料遷移成本低
需要解決資料傾斜問題，確保不因為單表資料量過大而導致整體效能降低

基於以上訴求，首先看問題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、總結

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