基于MongoDB的數(shù)據(jù)分片與分配策略研究?

熊 峰 劉 宇

（1.武漢郵電科學研究院 武漢 430074）（2.南京烽火星空通信發(fā)展有限公司 南京 210019）

1 引言

如今的時代，是互聯(lián)網(wǎng)的時代，是信息爆炸的時代，也是大數(shù)據(jù)的時代。而在大數(shù)據(jù)時代的背景下，根據(jù)Eric Brewer教授在PODC會議上提出的CAP 理論［1～3］，表明為了追求系統(tǒng)可用性與數(shù)據(jù)一致性，傳統(tǒng)的并行關系型數(shù)據(jù)庫限制了其本身的擴展能力，不適用于海量數(shù)據(jù)的存儲?；诖?，在大數(shù)據(jù)管理的迫切需求下，擁有負載均衡的自適應特性，大多數(shù)復雜查詢都能夠靈活支持，并且有著高效讀寫效率的NoSQL（非關系型數(shù)據(jù)庫）存儲技術從眾多大數(shù)據(jù)存儲技術中脫穎而出［4～6］，而 Mon?goDB作為最具代表性的NoSQL數(shù)據(jù)庫，具有面向集合存儲、使用BSON存儲、支持動態(tài)查詢和完全索引、自動分片、支持故障恢復、支持各種語言驅(qū)動程序，自動處理碎片等功能［7～9］，能夠適應現(xiàn)代Web應用飛速增長的海量數(shù)據(jù)，并且在分布式架構下可以達到很好的性能［10］，是目前最有影響力的NoSQL數(shù)據(jù)庫之一。

然而在分布式的系統(tǒng)架構下，如何將數(shù)據(jù)進行分片和分配［11～12］是必須要考慮的，因為兩者策略的選擇會直接影響到整個系統(tǒng)的擴展性以及負載均衡性能［13］。因此本文選擇MongoDB數(shù)據(jù)庫，通過剖析其工作機制以及自動分片的實現(xiàn)算法，提出了分片鍵選擇機制來嘗試提高集群的擴展性能；并在考慮了節(jié)點訪問負載差異的情況下，嘗試對內(nèi)置的數(shù)據(jù)分配均衡策略［14～15］進行算法優(yōu)化。

2 MongoDB自動分片集群系統(tǒng)

MongoDB自動分片（auto-sharding）集群由數(shù)據(jù)庫分片（shard）、配置服務器和mongos路由進程組成，其體系架構圖如圖1所示。

圖1 自動分片集群

1）分片：分片存儲集合中的文檔，可以是單個服務器，但為了在生產(chǎn)環(huán)境中提供高可用和數(shù)據(jù)一致性，應考慮使用副本集，它們提供分片的主副本和備份副本。

2）查詢路由器：查詢路由器運行一個mongos實例。它提供讓客戶端應用程序能夠與集合交互的接口，并隱藏數(shù)據(jù)被分片的事實。查詢路由器處理請求，將操作發(fā)送給分片，再將各個分片的響應合并成發(fā)送給客戶端的單個響應。一個分片集群可包含多個查詢路由器，在存在大量客戶端請求時，這是一種極佳的負載均衡方式。

3）配置服務器：配置服務器存儲有關分片集群的元數(shù)據(jù)，包含集群數(shù)據(jù)集到分片的映射。查詢路由器根據(jù)這些元數(shù)據(jù)確定要將操作發(fā)送給哪些分片。查詢路由器進程向配置服務器寫入時，會使用兩階段提交。這能保證配置服務器之間的一致性。

3 MongoDB自動分片機制

MongoDB自動分片的基本思想就是將數(shù)據(jù)集合根據(jù)用戶指定的分片鍵（shard key）來從邏輯上分割成小的數(shù)據(jù)塊（chunk）。這些數(shù)據(jù)塊相應的存儲到各個分片中，每個片只負責這個集合數(shù)據(jù)的一部分。由于配置服務器的存在，應用程序在收到用戶的查詢指令后，不需要知道所要查詢的數(shù)據(jù)在哪個片上，甚至不需要知道數(shù)據(jù)已經(jīng)被拆分成塊了，對應用來說，它僅知道連接了一個普通的mongod服務器（隱藏數(shù)據(jù)被分片的事實）。路由器知道數(shù)據(jù)與片的對應關系，能夠轉(zhuǎn)發(fā)請求到正確的片上。如果請求有了回應，路由器將其收集起來回送給應用。所以在分片之前查詢路由器要運行一個路由進程，該進程名為mongos，這個路由器知道所有數(shù)據(jù)的存放位置，所以應用可以連接它來正常發(fā)送請求。

4 分片策略

4.1 分片鍵選擇機制

MongoDB的auto-sharding自動分片機制實現(xiàn)海量數(shù)據(jù)在各數(shù)據(jù)庫節(jié)點上的分布式存儲及各分片上的負載均衡，其性能主要由分片鍵的選取情況來決定。如果選擇了合適的分片鍵，使得數(shù)據(jù)能夠在每段片鍵上分配更均衡，并且數(shù)據(jù)量增長時也能夠在每段上均勻分布，這樣就能確保每個數(shù)據(jù)庫實例的訪問負載相當，不至于出現(xiàn)任何分片服務器負載過重的情況。而糟糕的片鍵選擇則會嚴重影響系統(tǒng)性能，出現(xiàn)數(shù)據(jù)分布不均衡，單個數(shù)據(jù)庫實例下存儲了大量數(shù)據(jù)，進而造成單點負載過重，而其他數(shù)據(jù)庫節(jié)點則基本處于閑置狀態(tài)，極大地浪費了硬件資源。所以選擇恰當?shù)钠I至關重要。然而大多數(shù)研究通常假定認為適當?shù)姆制I已被選定而專注于分片部署及實施策略，對于分片鍵的選擇問題卻鮮有渉及［16］。

故針對分片鍵，本文嘗試提出基于以下幾點的選擇機制。

1）易于拆分：分片鍵應該易于將數(shù)據(jù)集分割成塊。

2）隨機性：MongoDB是基于范圍分片的，故隨機的片鍵可確保文檔在分片之間的分配更加均衡，從而確保沒有任何分片服務器負載過重。

3）復合鍵：應盡可能使用單字段片鍵，但如果沒有合適的單字段片鍵，可選擇使用復合片鍵。

4）基數(shù)：基數(shù)（cardinality）指的是字段值獨一無二的程度。如果字段值是獨一無二的（如社會保障卡號），字段的基數(shù)就很高；如果字段值獨一無二的可能性較?。ㄈ缪劬︻伾?，字段的基數(shù)就很低，即分片鍵的取值個數(shù)有限，根據(jù)片鍵范圍劃分的單個塊數(shù)據(jù)量會十分龐大。在MongoDB的分片機制中，是按塊來進行存儲及遷移的，若整個數(shù)據(jù)集僅分割成有限的幾個塊，那么根本就達不到將數(shù)據(jù)分布式存儲的初衷。通常，基數(shù)較高的字段更適合用作片鍵。

5）以查詢?yōu)閷颍貉芯吭诔绦蚴褂弥械牟樵?。如果能夠從單個分片收集到所有的數(shù)據(jù)，查詢的性能將更佳。如果片鍵與常用的查詢參數(shù)一致，將獲得更佳的性能。許多應用訪問新數(shù)據(jù)比老數(shù)據(jù)更頻繁，所以我們希望數(shù)據(jù)大致上按照時間排序，但同時也要均勻分布。這樣一來既能把我們正在讀寫的數(shù)據(jù)保持在內(nèi)存中，又可以使負載均衡地分散在集群中。

基于上面的內(nèi)容，我們可以概括出一個片鍵選擇公式：

｛coarseLocality：1，search ：1｝

即用準升序鍵加搜索鍵的復合片（compound shard key）策略來實現(xiàn)上面的目標。其中coarseLo?cality字段是基數(shù)較低的，最好此鍵的每個值能對應幾十到幾百個數(shù)據(jù)塊，用來控制數(shù)據(jù)局部化（da?ta locality）；而search字段則是基數(shù)較高的，是數(shù)據(jù)上常用到的一個檢索字段。

4.2 片鍵公式應用實例

本文以某分析程序為例詳細說明分片鍵選擇公式的應用。在此分析程序中，用戶會定期通過它訪問過去一個月的數(shù)據(jù)，而我們希望能盡量保持數(shù)據(jù)易于使用。因此可以在｛month：1，user：1｝上分片，其中month是一個小基數(shù)的升序字段，即每個月它都會有一個更新更大的值。user適合作為第二個字段，因為我們會經(jīng)常查詢某個特定用戶的數(shù)據(jù)。

從第一個數(shù)據(jù)塊開始，組合區(qū)間是（（-∞，-∞），（∞，∞））。當它被填滿，將其分為兩個塊，分別是區(qū)間（（-∞，-∞），（“2017-04”，“rex”））和（（“2017-04”，“rex”），（∞，∞））。假設現(xiàn)在還是4月份（“2017-04”），則所有的寫操作都會被均勻地分到兩個數(shù)據(jù)塊上來。所有用戶名小于“rex”的用戶都會被放在第一個塊上，而所有用戶名大于“rex”的用戶都會被放在第二個塊上。

隨著數(shù)據(jù)持續(xù)增長，這個方案還會持續(xù)有效。4月里后續(xù)創(chuàng)建的塊都會移動到不同的分片上，從而確保了讀寫在集群中的負載均衡。等5月到來時，我們開始創(chuàng)建邊界為“2017-05”的塊。隨著6月的到來，“2017-04”的塊的訪問頻率已經(jīng)很低，所以就可以將這些塊安靜地換出內(nèi)存使之不再占用資源。盡管以后仍有可能因為歷史原因再查看這些塊，但是應該不需要再分割或遷移它們了。

綜上所述，month+user的復合片鍵作為分片鍵的選擇策略，既可以滿足有足夠的粒度進行塊拆分，又能夠?qū)⒉迦霐?shù)據(jù)均勻分布到各個分片上，且保證了CRUD操作能夠利用數(shù)據(jù)局部性，是恰當?shù)姆制I選擇。

5 數(shù)據(jù)均衡策略

5.1 自動分片均衡策略的不足

在分片鍵確定后，MongoDB將按照用戶指定的分片鍵對數(shù)據(jù)進行范圍分區(qū)，形成一系列數(shù)據(jù)塊（負載均衡器（balencer）進行數(shù)據(jù)遷移的基本單位）。當前的均衡算法下［17］，均衡器會查詢各分片內(nèi)的總塊數(shù)，若塊數(shù)最多與塊數(shù)最少的分片的塊數(shù)之差超過某個設定值，負載均衡器將會遷移前者的數(shù)據(jù)塊到后者。但問題在于，該均衡算法僅僅只是從各分片內(nèi)的數(shù)據(jù)塊數(shù)量差異這個角度進行了考慮，而沒能將各個數(shù)據(jù)分片節(jié)點訪問負載的大小差異情況考慮進來，從而無法在超高并發(fā)的數(shù)據(jù)訪問狀態(tài)下做到數(shù)據(jù)分配的實時均衡?；诖耍疚膶?shù)據(jù)均衡算法進行了優(yōu)化改進，提出基于節(jié)點負載差異的數(shù)據(jù)均衡算法，從數(shù)據(jù)量以及節(jié)點負載差異這兩個方面實現(xiàn)均衡。

5.2 基于節(jié)點負載差異的數(shù)據(jù)均衡算法

5.2.1 算法思想

算法思想具體如下：

輸入：集合命名空間ns；分片數(shù)n；

分片約束信息映射表shardToLimits；

分片分塊映射表shardToChunks；

塊均衡設定值α，負載選擇比例β，

負載均衡設定值γ

輸出：遷移源分片from；遷移目標分片to

1）首先定義最小分片列表minList以及存儲即將耗盡等待移除分片集drainingShards，算法表達式為

2）接著遍歷數(shù)據(jù)集命名空間內(nèi)的所有分片來獲取各分片s的信息，再通過分片s的信息來獲取所在節(jié)點的負載，進而求和得出總負載，算法表達式為

For each shard s∈ns DO

shardLimits←shardToLimits.find(s)

load←getLoad(shardLimits)

sumLoad←sumLoad+load

3）逐項比較找出負載最高的分片，算法表達式為

IF s.load＞maxLoad.load

ΤHEN maxLoad←s

4）若分片s滿足塊數(shù)既不是最大的也不是存儲即將耗盡等待移除的分片的雙重條件，則將其加入候選minList列表，算法表達式為

IF!isSizeMaxed(shardLimits)

AND!isDraining(shardLimits)

ΤHEN minList.add(s)

5）逐項比較找出塊數(shù)最大的分片，找出存儲即將耗盡分片加入drainingShards，求出平均負載，算法表達式為

IF s.size＞max.size

ΤHEN max←s

IF isDraining(shardLimits)

ΤHEN drainingShards.add(s)

avgLoad←sumLoad/n

6）對 minList排序生成minSortedList，對同時滿足分片s屬于minSortedList以及分片s的排名位于分片總數(shù)前β比例的分片s集合進行遍歷，逐項比較找出塊數(shù)最小的分片，算法表達式為

minSortedList←Sort(minList)

FOR each shard s∈minSortedList

AND s.rank＜n×β DO

IF s.nodeload＞min.nodeload

ΤHEN min←s

7）檢查以下條件，確定遷移源分片：若分片內(nèi)塊數(shù)之差超過設定值，則確定源分片為塊數(shù)最大的分片，算法表達式為

IF max.size-min.size＞n×α

ΤHEN from←max;to←min

8）若7）不滿足，檢查以下條件，確定遷移源分片：若存在存儲耗盡待刪除分片集合，則從集合中選取一個分片作為源分片，算法表達式為

ELSE IF!drainingShards.IsEmpty()

ΤHEN from←drainingShards.get()

AND to←min

9）若8）不滿足，則檢查以下條件，確認是否需要進行遷移：若存在負載與平均負載之差超過額定值的分片，則確定過載分片中負載最高的分片為源分片，否則不需要進行遷移，算法表達式為

ELSE IF(maxLoad-avgLoad)/avgLoad＞γ

ΤHEN from←maxLoad

AND to←min

ELSE return NULL

圖2展示了算法的詳細流程。

圖2 數(shù)據(jù)平衡負載流程圖

5.2.2 算法性能測試

測試場景基于MongoDB集群，由12臺虛擬機組成，每臺虛擬機配置均為8GB內(nèi)存+1T硬盤，且均安裝了redhat enterprise linux7.0操作系統(tǒng)，虛擬機間通過100Mbps局域網(wǎng)互連。MongoDB采用分片模式，共3個分片，由于是測試用，為簡化操作，故沒有采用復制集模式。MongoDB版本為3.4.0，開啟3個mongos查詢路由服務。

將新的基于節(jié)點負載差異的數(shù)據(jù)均衡算法在MongoDB中實現(xiàn)，并比較新舊兩種算法的并發(fā)讀寫性能。為模擬真實環(huán)境，測試數(shù)據(jù)均參照真實互聯(lián)網(wǎng)節(jié)點采集系統(tǒng)數(shù)據(jù)格式隨機生成，數(shù)據(jù)總量為30000000條。實驗首先驗證了新舊算法下Mon?goDB集群的高并發(fā)寫性能，在不同的并發(fā)數(shù)下，保持數(shù)據(jù)總量不變。集群在不同的并發(fā)數(shù)下，將所有測試數(shù)據(jù)均插入完畢所用耗時如表1所示，表中單位為s。表中的數(shù)據(jù)是在相同的條件下，取5次測試的平均值所得。圖3給出了兩種算法寫性能的對比情況。

表1 并發(fā)寫性能比較

圖3 并發(fā)寫性能比較

保持測試中的并發(fā)數(shù)與數(shù)據(jù)總量不變的條件下，將新舊兩種算法進行比較，測試集群的并發(fā)讀性能。讀取完所有測試數(shù)據(jù)所用耗時如表2所示，表中單位為s。集群的并發(fā)讀性能對比圖如圖4所示。

表2 并發(fā)讀性能比較

圖4 并發(fā)讀性能比較

6 結語

針對大數(shù)據(jù)環(huán)境下，對于分布式存儲系統(tǒng)擴展性及負載均衡性能至關重要的數(shù)據(jù)分片及分配問題，以MongoDB為研究對象，提出了分片鍵選擇機制，并證明了該片鍵選擇策略的有效性，既可以滿足字段基數(shù)足夠進行塊拆分，又能使插入數(shù)據(jù)在各個片上均勻分布，且CRUD操作亦能夠利用數(shù)據(jù)局部性；而針對MongoDB現(xiàn)有的負載均衡策略未考慮實際負載的情況，提出了基于節(jié)點負載差異的數(shù)據(jù)均衡算法，并通過實驗驗證了自動分片集群在并發(fā)情況下讀寫性能相比舊的算法有著明顯的提升。

下一步工作主要是將數(shù)據(jù)分片、數(shù)據(jù)分配以及負載執(zhí)行三個相互關聯(lián)的課題進行關系建模與歸納，對影響數(shù)據(jù)分布問題的三大要素數(shù)據(jù)、負載和節(jié)點進行著重分析，研究自動數(shù)據(jù)分布的可行方案。