熊 峰 劉 宇

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

1 引言

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

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

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

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

圖1 自動(dòng)分片集群

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

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

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

3 MongoDB自動(dòng)分片機(jī)制

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

4 分片策略

4.1 分片鍵選擇機(jī)制

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

故針對(duì)分片鍵，本文嘗試提出基于以下幾點(diǎn)的選擇機(jī)制。

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

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

3）復(fù)合鍵：應(yīng)盡可能使用單字段片鍵，但如果沒有合適的單字段片鍵，可選擇使用復(fù)合片鍵。

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

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

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

｛coarseLocality：1，search ：1｝

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

4.2 片鍵公式應(yīng)用實(shí)例

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

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

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

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

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

5.1 自動(dòng)分片均衡策略的不足

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

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

5.2.1 算法思想

算法思想具體如下：

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

分片約束信息映射表shardToLimits；

分片分塊映射表shardToChunks；

塊均衡設(shè)定值α，負(fù)載選擇比例β，

負(fù)載均衡設(shè)定值γ

輸出：遷移源分片from；遷移目標(biāo)分片to

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

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

For each shard s∈ns DO

shardLimits←shardToLimits.find(s)

load←getLoad(shardLimits)

sumLoad←sumLoad+load

3）逐項(xiàng)比較找出負(fù)載最高的分片，算法表達(dá)式為

IF s.load＞maxLoad.load

ΤHEN maxLoad←s

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

IF!isSizeMaxed(shardLimits)

AND!isDraining(shardLimits)

ΤHEN minList.add(s)

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

IF s.size＞max.size

ΤHEN max←s

IF isDraining(shardLimits)

ΤHEN drainingShards.add(s)

avgLoad←sumLoad/n

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

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è)定值，則確定源分片為塊數(shù)最大的分片，算法表達(dá)式為

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

ΤHEN from←max;to←min

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

ELSE IF!drainingShards.IsEmpty()

ΤHEN from←drainingShards.get()

AND to←min

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

ELSE IF(maxLoad-avgLoad)/avgLoad＞γ

ΤHEN from←maxLoad

AND to←min

ELSE return NULL

圖2展示了算法的詳細(xì)流程。

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

5.2.2 算法性能測試

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

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

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

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

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

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

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

6 結(jié)語

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

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