基于MongoDB的數據分片與分配策略研究?

熊 峰 劉 宇

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

1 引言

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

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

2 MongoDB自動分片集群系統

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

圖1 自動分片集群

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

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

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

3 MongoDB自動分片機制

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

4 分片策略

4.1 分片鍵選擇機制

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

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

1）易于拆分：分片鍵應該易于將數據集分割成塊。

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

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

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

5）以查詢為導向：研究在程序使用中的查詢。如果能夠從單個分片收集到所有的數據，查詢的性能將更佳。如果片鍵與常用的查詢參數一致，將獲得更佳的性能。許多應用訪問新數據比老數據更頻繁，所以我們希望數據大致上按照時間排序，但同時也要均勻分布。這樣一來既能把我們正在讀寫的數據保持在內存中，又可以使負載均衡地分散在集群中。

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

｛coarseLocality：1，search ：1｝

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

4.2 片鍵公式應用實例

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

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

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

綜上所述，month+user的復合片鍵作為分片鍵的選擇策略，既可以滿足有足夠的粒度進行塊拆分，又能夠將插入數據均勻分布到各個分片上，且保證了CRUD操作能夠利用數據局部性，是恰當的分片鍵選擇。

5 數據均衡策略

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

在分片鍵確定后，MongoDB將按照用戶指定的分片鍵對數據進行范圍分區，形成一系列數據塊（負載均衡器（balencer）進行數據遷移的基本單位）。當前的均衡算法下［17］，均衡器會查詢各分片內的總塊數，若塊數最多與塊數最少的分片的塊數之差超過某個設定值，負載均衡器將會遷移前者的數據塊到后者。但問題在于，該均衡算法僅僅只是從各分片內的數據塊數量差異這個角度進行了考慮，而沒能將各個數據分片節點訪問負載的大小差異情況考慮進來，從而無法在超高并發的數據訪問狀態下做到數據分配的實時均衡。基于此，本文對數據均衡算法進行了優化改進，提出基于節點負載差異的數據均衡算法，從數據量以及節點負載差異這兩個方面實現均衡。

5.2 基于節點負載差異的數據均衡算法

5.2.1 算法思想

算法思想具體如下：

輸入：集合命名空間ns；分片數n；

分片約束信息映射表shardToLimits；

分片分塊映射表shardToChunks；

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

負載均衡設定值γ

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

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

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

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滿足塊數既不是最大的也不是存儲即將耗盡等待移除的分片的雙重條件，則將其加入候選minList列表，算法表達式為

IF!isSizeMaxed(shardLimits)

AND!isDraining(shardLimits)

ΤHEN minList.add(s)

5）逐項比較找出塊數最大的分片，找出存儲即將耗盡分片加入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的排名位于分片總數前β比例的分片s集合進行遍歷，逐項比較找出塊數最小的分片，算法表達式為

minSortedList←Sort(minList)

FOR each shard s∈minSortedList

AND s.rank＜n×β DO

IF s.nodeload＞min.nodeload

ΤHEN min←s

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

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 數據平衡負載流程圖

5.2.2 算法性能測試

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

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

表1 并發寫性能比較

圖3 并發寫性能比較

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

表2 并發讀性能比較

圖4 并發讀性能比較

6 結語

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

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