基于FODA算法mongodb大數(shù)據(jù)負(fù)載均衡策略的改進(jìn)摘要：隨著Web2.0技術(shù)的發(fā)展和云存儲(chǔ)技術(shù)的成熟，如何有效地存儲(chǔ)、處理海量數(shù)據(jù)成了一個(gè)非常嚴(yán)峻的問(wèn)題。對(duì)于數(shù)據(jù)庫(kù)的并發(fā)性、可擴(kuò)展性能力的要求也變的越來(lái)越高。云計(jì)算就在這樣的環(huán)境下產(chǎn)生。云計(jì)算是一種通過(guò)Internet以服務(wù)的方式提供動(dòng)態(tài)可伸縮性的虛擬化的資源計(jì)算模式，由計(jì)算機(jī)和其它設(shè)備提供共享資源，軟件和信息作為網(wǎng)絡(luò)的計(jì)量服務(wù)。很多大學(xué)，供應(yīng)商和政府組織投資關(guān)于云計(jì)算的研究，比如：亞馬遜推出的簡(jiǎn)單存儲(chǔ)服務(wù)和彈性計(jì)算云，谷歌提出的可擴(kuò)展的分布式文件系統(tǒng)(GFS)，BigTable和MapReduce，這些技術(shù)都已經(jīng)成功用于生產(chǎn)環(huán)境。 相對(duì)于此，傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)（ORDBMS）在面對(duì)并發(fā)量極高的Web2.0網(wǎng)站時(shí)已經(jīng)顯得捉襟見(jiàn)肘，主要體現(xiàn)在一下幾個(gè)方面：對(duì)大并發(fā)量的訪問(wèn)需求。當(dāng)前Web2.0網(wǎng)站的數(shù)據(jù)庫(kù)有很高的并發(fā)量，每秒上萬(wàn)次讀寫(xiě)要求已是常事，對(duì)于上萬(wàn)次查詢來(lái)說(shuō)，關(guān)系型數(shù)據(jù)庫(kù)勉強(qiáng)還撐得住，但面對(duì)上萬(wàn)次寫(xiě)入訪問(wèn)，硬盤(pán)IO就無(wú)法承受了。對(duì)大數(shù)據(jù)量的存儲(chǔ)效率和快速訪問(wèn)的需求。當(dāng)前大型的SNS網(wǎng)站每天生成的數(shù)據(jù)數(shù)以億計(jì)。以國(guó)外的Friendfeed為例，一個(gè)月的用戶動(dòng)態(tài)就可以達(dá)到2億條以上。對(duì)于關(guān)系數(shù)據(jù)庫(kù)來(lái)說(shuō)，在一張如此龐大的表里面進(jìn)行查詢，其效率必然是極其低下的。由于傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)無(wú)法滿足以上需求，因此NoSQL數(shù)據(jù)庫(kù)系統(tǒng)在主要互聯(lián)網(wǎng)公司的應(yīng)用不斷上升，比如Google，Amazon，Twitter和Facebook。在眾多NoSQL數(shù)據(jù)庫(kù)當(dāng)中，MongoDB是比較出色的一款。MongoDB是一個(gè)類(lèi)似于關(guān)系數(shù)據(jù)庫(kù)的非關(guān)系數(shù)據(jù)庫(kù)，它支持的數(shù)據(jù)結(jié)構(gòu)跟Json格式類(lèi)似，稱(chēng)為Bson，因此可以存儲(chǔ)比較復(fù)雜的數(shù)據(jù)類(lèi)型。本文主要討論MongoDB的工作機(jī)制、自動(dòng)分片原理，最后基于源代碼分析MongoDB的負(fù)載均衡算法，并提出一定的改進(jìn)。關(guān)鍵字： 大數(shù)據(jù)，F(xiàn)ODA（FrequencyOfDataAccess），MongoDB，負(fù)載均衡1引言 1.1MongoDB數(shù)據(jù)庫(kù)簡(jiǎn)介MongoDB是一個(gè)基于分布式文件存儲(chǔ)的數(shù)據(jù)庫(kù)。由C++語(yǔ)言編寫(xiě)。它支持的數(shù)據(jù)結(jié)構(gòu)非常松散，是類(lèi)似Json的Bson格式，因此可以存儲(chǔ)比較復(fù)雜的數(shù)據(jù)類(lèi)型。MongoDB的特點(diǎn)：面向集合存儲(chǔ)；模式自由；支持動(dòng)態(tài)查詢；支持完全索引；支持查詢；支持復(fù)制和故障轉(zhuǎn)移；自動(dòng)處理碎片；支持RUBY，PYTHON，JAVA，C++，PHP等多種語(yǔ)言；文件存儲(chǔ)格式為BSON（一種JSON的擴(kuò)展）；可通過(guò)網(wǎng)絡(luò)訪問(wèn)；所謂“面向集合”（Collenction-Orented），意思是數(shù)據(jù)被分組存儲(chǔ)在數(shù)據(jù)集中，被稱(chēng)為一個(gè)集合（Collenction)。每個(gè)集合在數(shù)據(jù)庫(kù)中都有一個(gè)唯一的標(biāo)識(shí)名，并且可以包含無(wú)限數(shù)目的文檔。集合的概念類(lèi)似關(guān)系型數(shù)據(jù)庫(kù)（RDBMS）里的表（table），不同的是它不需要定義任何模式（schema)。模式自由（schema-free)，意味著對(duì)于存儲(chǔ)在mongodb數(shù)據(jù)庫(kù)中的文件，我們不需要知道它的任何結(jié)構(gòu)定義。如果需要的話，你完全可以把不同結(jié)構(gòu)的文件存儲(chǔ)在同一個(gè)數(shù)據(jù)庫(kù)里。存儲(chǔ)在集合中的文檔，被存儲(chǔ)為鍵-值對(duì)的形式。鍵用于唯一標(biāo)識(shí)一個(gè)文檔，為字符串類(lèi)型，而值則可以是各中復(fù)雜的文件類(lèi)型。我們稱(chēng)這種存儲(chǔ)形式為BSON（BinarySerializeddOcumentFormat）。MongoDB服務(wù)端可運(yùn)行在Linux、Windows或OSX平臺(tái)，支持32位和64位應(yīng)用，默認(rèn)端口為27017。推薦運(yùn)行在64位平臺(tái)，因?yàn)镸ongoDB在32位模式運(yùn)行時(shí)支持的最大文件尺寸為2GB。MongoDB把數(shù)據(jù)存儲(chǔ)在文件中（默認(rèn)路徑為：/data/db），為提高效率使用內(nèi)存映射文件進(jìn)行管理。1.2MongoDB集群系統(tǒng)一個(gè)MongoDB的集群系統(tǒng)如圖1所致，主要由片（Sharding）、Mongos路由服務(wù)器和Config服務(wù)器三部分組成。片：片就是主要存儲(chǔ)數(shù)據(jù)的容器。每個(gè)片可以是單獨(dú)的服務(wù)器，也可以是副本集。Mongos路由器：每個(gè)分片都包含部分集群數(shù)據(jù)，那么還需要一個(gè)接口連接整個(gè)集群，這就是Mongos。Mongos進(jìn)程是一個(gè)路由器的工作，它可以將所有的讀寫(xiě)請(qǐng)求指引到合適的分片上，從而為客戶端提供了一個(gè)合理的視圖。Config服務(wù)器：Config服務(wù)器中持久化了分片集群中的元數(shù)據(jù)，包括全局集群配置，每個(gè)數(shù)據(jù)庫(kù)、集合和特定范圍的位置，以及一份變更記錄，保存了數(shù)據(jù)在分片之間進(jìn)行遷移的歷史信息。圖1.集群系統(tǒng)的架構(gòu)2MongoDB的自動(dòng)分片功能什么時(shí)候需要分片:a.機(jī)器的磁盤(pán)不夠用了b.單個(gè)Mongod已經(jīng)不能滿足些數(shù)據(jù)的性能需要了c.想將大量數(shù)據(jù)放在內(nèi)存中提高性能一般來(lái)說(shuō),先要從不分片開(kāi)始,然后在需要的時(shí)候?qū)⑵滢D(zhuǎn)換成分片。2.1MongoDB的數(shù)據(jù)分割原理分片是MongoDB提供的一種機(jī)制，其可以將大型的集合分割保存到不同的服務(wù)器上。與其他的分區(qū)方案相比，MongoDB幾乎能自動(dòng)為我們完成所有事情。只要我們進(jìn)行簡(jiǎn)單的配置，并告訴MongoDB要分配的數(shù)據(jù)，它就可以自動(dòng)維護(hù)數(shù)據(jù)在不同服務(wù)器之間的平衡。同時(shí)根據(jù)需要增減服務(wù)器，MongoDB也會(huì)自動(dòng)移動(dòng)平移已有數(shù)據(jù)。分片機(jī)制提供了如下三種優(yōu)勢(shì)：對(duì)集群進(jìn)行抽象，讓集群“不可見(jiàn)”。MongoDB自帶了一個(gè)叫做mongos的專(zhuān)有路由進(jìn)程。mongos就是掌握統(tǒng)一路口的路由器，其會(huì)將客戶端發(fā)來(lái)的請(qǐng)求準(zhǔn)確無(wú)誤的路由到集群中的一個(gè)或者一組服務(wù)器上，同時(shí)會(huì)把接收到的響應(yīng)拼裝起來(lái)發(fā)回到客戶端。保證集群總是可讀寫(xiě)。MongoDB通過(guò)多種途徑來(lái)確保集群的可用性和可靠性。將MongoDB的分片和復(fù)制功能結(jié)合使用，在確保數(shù)據(jù)分片到多臺(tái)服務(wù)器的同時(shí)，也確保了每分?jǐn)?shù)據(jù)都有相應(yīng)的備份，這樣就可以確保有服務(wù)器換掉時(shí)，其他的副本可以立即接替壞掉的部分繼續(xù)工作。使集群易于擴(kuò)展。當(dāng)系統(tǒng)需要更多的空間和資源的時(shí)候，MongoDB使我們可以按需方便的擴(kuò)充系統(tǒng)容量。 為了在分片間均勻地分配數(shù)據(jù)，MongoDB會(huì)在不同分片間移動(dòng)被分割了的數(shù)據(jù)子集，并會(huì)根據(jù)片鍵來(lái)決定移動(dòng)哪些數(shù)據(jù)。例如，我們可能選擇按用戶名（username）字段來(lái)劃分用戶集合。MongoDB使用基于區(qū)間的方式進(jìn)行劃分，即按照給定區(qū)間將數(shù)據(jù)分割成不同塊，例如[“a”，“f”]。MongoDB中分片多用[a，b]來(lái)表示區(qū)間范圍，該區(qū)間表示為“從a開(kāi)始且包含a，到b為止但不包含b”。舉例來(lái)說(shuō)，假設(shè)users集合是以u(píng)sername為片鍵進(jìn)行分片，它分布在兩個(gè)分片A和B上，并且被分成了如表1所示的多個(gè)塊，每個(gè)塊的范圍由key的起始值和終止值來(lái)標(biāo)識(shí)。圖2.MongoDB數(shù)據(jù)分割2.2MongoDB自動(dòng)分片的平衡策略 MongoDB數(shù)據(jù)庫(kù)的自動(dòng)分片技術(shù)就是將原先數(shù)據(jù)庫(kù)中集合依據(jù)一定的規(guī)則切分成若干小塊，這些分片小塊統(tǒng)一由mongos路由管理，當(dāng)有請(qǐng)求查詢或?qū)懭霑r(shí)，路由會(huì)依據(jù)分片shardkey規(guī)則找到對(duì)應(yīng)的分片操作。分片解決了寫(xiě)密集操作，用于分散單一寫(xiě)服務(wù)器負(fù)載。亦或者原先的存儲(chǔ)空間不夠了，這個(gè)時(shí)候可能通過(guò)分片操作將之后的數(shù)據(jù)寫(xiě)入其它存儲(chǔ)空間上?？梢钥闯?，集合的分片和數(shù)據(jù)庫(kù)的分表類(lèi)似，并且每個(gè)分片都支持寫(xiě)操作。由于分片的出現(xiàn)，導(dǎo)致數(shù)據(jù)被分布式的存儲(chǔ)到不同的服務(wù)器上，當(dāng)某一服務(wù)器出現(xiàn)問(wèn)題時(shí)就可能導(dǎo)致數(shù)據(jù)丟失，其次路由mongos也會(huì)出現(xiàn)問(wèn)題，另外存儲(chǔ)分片的信息的配置服務(wù)器也可能會(huì)發(fā)生問(wèn)題。當(dāng)然我們可以利用mastersalve/Replicasets機(jī)制去備份每個(gè)分片、Mongos、configs。如下官網(wǎng)配置圖示，即使我們使用服務(wù)器交叉?zhèn)浞菀残枰罅康姆?wù)器資源，因此分片是一件極具耗費(fèi)資源的事情。圖3.Mongos的數(shù)據(jù)均衡MongoDB使用均衡器使數(shù)據(jù)均衡地分布到集群中的所有服務(wù)器上。每個(gè)數(shù)據(jù)塊做為一個(gè)傳輸單元，均衡器等待不均衡塊計(jì)數(shù)的閾值發(fā)生。一旦達(dá)到閾值時(shí)，均衡器將重新分配數(shù)據(jù)塊。直到任何二個(gè)分片數(shù)據(jù)塊數(shù)目差異小于閾值。在數(shù)據(jù)遷移的過(guò)程中，仍然可以進(jìn)行數(shù)據(jù)讀寫(xiě)，并不會(huì)因此而影響可用性。那么mongodb是怎么做到的呢？在數(shù)據(jù)遷移過(guò)程中，數(shù)據(jù)讀寫(xiě)操作首先在源數(shù)據(jù)節(jié)點(diǎn)中進(jìn)行。待遷移完畢后，再將這期間的更新操作同步到新節(jié)點(diǎn)中去。最后再更新config節(jié)點(diǎn)，標(biāo)記數(shù)據(jù)已經(jīng)在新的地方，完成遷移。只有在最后同步遷移期間的操作的時(shí)候，需要鎖定數(shù)據(jù)更新。這樣就講鎖定時(shí)間盡可能縮小，大大降低數(shù)據(jù)遷移對(duì)服務(wù)的影響。mongodb的sharding和傳統(tǒng)sharding的最大區(qū)別就在于引入了元數(shù)據(jù)。看似增加了復(fù)雜度，并增加了一些額外的存儲(chǔ)，但是由此帶來(lái)的靈活性卻是顯而易見(jiàn)的。傳統(tǒng)的sharding本質(zhì)上是對(duì)數(shù)據(jù)的靜態(tài)映射，所有那些數(shù)據(jù)遷移的困難都是由此而來(lái)。而引入元數(shù)據(jù)以后，就變靜態(tài)映射為動(dòng)態(tài)映射。數(shù)據(jù)遷移就不再是難事了。從而從根本上解決了問(wèn)題。另一方面，用元數(shù)據(jù)實(shí)現(xiàn)chunk則降低了實(shí)現(xiàn)難度，后端節(jié)點(diǎn)仍然可以使用原有的技術(shù)。同時(shí)，因?yàn)椴恍枰獙?duì)后端數(shù)據(jù)進(jìn)行變動(dòng)，也使部署遷移變得更容易，只需要另外加上mongos節(jié)點(diǎn)和config節(jié)點(diǎn)即可。 為了減少數(shù)據(jù)的傳輸量，每一個(gè)分片都包含多個(gè)范圍。當(dāng)一個(gè)新的分片加入到集群中或者一些分片達(dá)到了最大閾值，均衡器會(huì)把獲取頻率最高的數(shù)據(jù)移到使用頻率最低的分片中，通過(guò)移動(dòng)最少的數(shù)據(jù)量使數(shù)據(jù)均衡地分布到集群中。均衡器的目的不僅是為了保持?jǐn)?shù)據(jù)的均衡分布而且也要減少數(shù)據(jù)量的傳輸。這個(gè)均衡器的算法沒(méi)有想象的那么智能，而是基于片中的總體數(shù)據(jù)移動(dòng)。它們僅僅轉(zhuǎn)移分片頂端的數(shù)據(jù)塊，并沒(méi)有考慮到數(shù)據(jù)訪問(wèn)的頻率。這樣不能對(duì)系統(tǒng)的數(shù)據(jù)進(jìn)行有效的均衡。所以非常有必要來(lái)改進(jìn)在MongoDB的自動(dòng)分片的策略。2.3FODA算法原理 MongoDBsharding主要分為3大部分。shard節(jié)點(diǎn)、config節(jié)點(diǎn)和config節(jié)點(diǎn)。對(duì)客戶端來(lái)說(shuō)，直接訪問(wèn)的是圖中綠色的mongos節(jié)點(diǎn)。背后的config節(jié)點(diǎn)和shard節(jié)點(diǎn)是客戶端不能直接訪問(wèn)的。mongos的主要作用是數(shù)據(jù)路由。從元數(shù)據(jù)中定位數(shù)據(jù)位置，合并查詢結(jié)果。另外，mongos節(jié)點(diǎn)還負(fù)責(zé)數(shù)據(jù)遷移和數(shù)據(jù)自動(dòng)平衡，并作為sharding集群的管理節(jié)點(diǎn)。它對(duì)外的接口就和普通的mongod一樣。因此，可以使用標(biāo)準(zhǔn)mongodb客戶端和驅(qū)動(dòng)進(jìn)行訪問(wèn)。mongos節(jié)點(diǎn)是無(wú)狀態(tài)的，本身不保存任何數(shù)據(jù)和元數(shù)據(jù)，因此可以任意水平擴(kuò)展，這樣任意一個(gè)節(jié)點(diǎn)發(fā)生故障都可以很容易的進(jìn)行故障轉(zhuǎn)移，不會(huì)造成嚴(yán)重影響。 為了解決數(shù)據(jù)在自動(dòng)分片中數(shù)據(jù)分布不均的問(wèn)題，提出了基于數(shù)據(jù)訪問(wèn)頻率的改進(jìn)算法。在MongoDB中，數(shù)據(jù)塊作為數(shù)據(jù)傳輸?shù)膯卧?。在每個(gè)分片中有n個(gè)數(shù)據(jù)塊，用Pi表示第i個(gè)數(shù)據(jù)塊，用Fodi表示第i塊數(shù)據(jù)塊的數(shù)據(jù)訪問(wèn)頻率代價(jià)。在MongoDB中數(shù)據(jù)的主要訪問(wèn)是增加、查找、修改和刪除。假設(shè)每個(gè)塊的平均數(shù)據(jù)訪問(wèn)頻率為AVG_T_Ci,每個(gè)塊的增、刪、改、查訪問(wèn)次數(shù)分別記為Ii，Di，Ui，Si，則Fodi的計(jì)算公式為： Fodi=Ii/∑Ii+Di/∑Di+Ui/∑Ui+Si/∑Si.......................................................................（1）但是，對(duì)于數(shù)據(jù)塊的插入、查詢、修改、刪除訪問(wèn)，給數(shù)據(jù)庫(kù)所帶來(lái)的負(fù)擔(dān)是不一樣的。對(duì)于查詢功能，由于數(shù)據(jù)庫(kù)都啟用了緩存機(jī)制，因此很多查詢其實(shí)無(wú)需向數(shù)據(jù)庫(kù)發(fā)請(qǐng)求就可以完成；而對(duì)于插入操作來(lái)說(shuō)，每次插入都要與數(shù)據(jù)庫(kù)建立連接，因此插入操作給數(shù)據(jù)庫(kù)所帶來(lái)的壓力要大于其他的操作，故在此對(duì)于插入操作，給其一個(gè)小于1的加權(quán)系數(shù)inc，故公式（1）修改為式（2）。Fodi=inc*Ii/∑Ii+Di/∑Di+Ui/∑Ui+Si/∑Si................................................................（2）每個(gè)分片的fod值是包含fodi數(shù)據(jù)塊值的綜合。計(jì)算公式如下：S（Fod）=i=1需要修改數(shù)據(jù)結(jié)構(gòu)來(lái)記錄數(shù)據(jù)塊中的信息，Ii，Di，Ui，Si和Fodi五個(gè)變量分別存儲(chǔ)增加、查找、修改和更新Fodi的值。2.4FODA算法在MongoDB中的應(yīng)用 FODA的值代表了每個(gè)數(shù)據(jù)庫(kù)操作的頻率。如果數(shù)據(jù)庫(kù)的Fodi的值高代表該數(shù)據(jù)塊使用頻率高。數(shù)據(jù)塊重分布的閾值根據(jù)分片中數(shù)據(jù)庫(kù)數(shù)目的不同而不同，但遷移數(shù)據(jù)庫(kù)的選擇是根據(jù)Fodj的值來(lái)確定的。它們會(huì)在分片的總體規(guī)模和數(shù)據(jù)的訪問(wèn)頻率之間進(jìn)行權(quán)衡。數(shù)據(jù)均衡分為一下三個(gè)步驟：據(jù)遷移的閾值：計(jì)算每個(gè)分片中數(shù)據(jù)庫(kù)的數(shù)量。如果它們的差值大于8，則進(jìn)行數(shù)據(jù)均衡直到它們之間的差值小于2。將從數(shù)據(jù)塊最多的分片的數(shù)據(jù)塊移(起始分片)到數(shù)據(jù)塊最少的分片中(目的分片)；選擇遷移數(shù)據(jù)塊：計(jì)算起始分片和目的分片中Fod值。如果ｆ(Fod)>t(Fd)，則選擇起始分片中Fodi值最大的數(shù)據(jù)塊。否則，選擇起始數(shù)據(jù)塊中Fodi值最小的數(shù)據(jù)塊；遷移數(shù)據(jù)：遷移在步驟2)中選中的數(shù)據(jù)到目的數(shù)據(jù)塊，再次分別計(jì)算起始分片和目的分片中每個(gè)數(shù)據(jù)塊的Fodi的值； 流程圖如圖3所示：此外，還需要確定inc的值。inc作為數(shù)據(jù)插人操作的權(quán)重，所以該權(quán)重值應(yīng)該大于1。inc具體的值應(yīng)該與服務(wù)器性能和系統(tǒng)負(fù)載有關(guān)，可以根據(jù)業(yè)務(wù)需求來(lái)設(shè)置和調(diào)整該值。在大數(shù)據(jù)背景下，數(shù)十萬(wàn)規(guī)模吞吐量的情況下（根據(jù)如下圖4和圖5），大概inc值為5左右。圖3.數(shù)據(jù)負(fù)載均衡流程圖圖4.MongoDB插入測(cè)試圖5.Mon