基于聚類分析分庫策略的社交網絡數據庫查詢性能與數據遷移

梁 雙，周麗華，楊培忠

(云南大學 信息學院，昆明 650000) (*通信作者電子郵箱lhzhou@ynu.edu.cn)

基于聚類分析分庫策略的社交網絡數據庫查詢性能與數據遷移

梁 雙，周麗華*，楊培忠

(云南大學 信息學院，昆明 650000) (*通信作者電子郵箱lhzhou@ynu.edu.cn)

社交網絡數據具有一定的聚合性，即特征上相近的用戶之間更容易產生某種行為。依照常規的水平切分方法，在執行這些事件的信息查詢時，將會耗費大量的時間和連接損耗去依次訪問多個數據庫。針對此問題，提出了基于聚類分析的社交網絡數據庫分庫策略。將社交網絡主體的特征標量進行聚類，使得聚集程度高的主體盡量分割到一個或盡可能少的幾個分庫中去，從而提高事件的查詢效率，并在此基礎上兼顧負載均衡與大數據遷移等問題。實驗結果表明，該策略在社交網絡的主流事件查詢上都表現出不同程度的性能提升，最高提升程度達到23.4%，并且實現了局部最優負載均衡和零數據遷移。總的來說，基于聚類分析的社交網絡數據庫分庫策略在提高查詢效率、平衡負載以及大數據遷移可行性上，比傳統水平切割分庫有了相當的優勢。

社交網絡; 數據庫分庫; 聚類分析; 查詢性能; 數據遷移

0 引言

隨著科技和社會的發展，社交網絡在人們的日常生活中發揮著越來越重要的作用，越來越多的人將社交網絡作為獲取信息、分享信息以及溝通交流的主要途徑。數據庫作為社交網絡的底層數據載體，隨著社交網絡的發展與壯大，其數據量快速地增長，使得海量數據的存儲和訪問成為了系統設計的瓶頸問題。通過數據庫分庫[1]來提高網站性能，橫向擴展數據層已經成為各大互聯網公司的首選方式。

常規的數據庫分庫，主要通過垂直切分與水平切分兩種方法來進行單一數據向多數據庫(陣列)擴展。其中垂直切分是將數據庫內與其他表的聯合查詢較少相對獨立的表獨立出來部署到一個新的庫中；水平切分是將某個數據量大且增速快的數據表中的數據按照某種規則切分到多個數據庫中去。一般常用的水平切分策略主要是物理分庫，如分段分庫與取模哈希分庫。這些分割方法能夠做到各分庫的數據量的均衡，降低單個數據庫的連接數目與負載。

但是社交網絡具有一定的特殊性，很多事件的主體都呈現出一定的相似性，即關系上相近的用戶之間更容易產生某種相同的行為。很多學者的研究證明了對于社交網絡的非物理切分更加有利于系統查詢效率的提高與資源的節省。Karagiannis等[2]部署并評估了企業郵箱服務優化引擎——Hermans，根據通信數據分析生成用戶的社交圖，并對用戶進行空間并置。將空間分布緊密的用戶放置在同一個服務器上，以此減少郵件收發雙方的郵件副本的二次存儲空間浪費。Agarwal等[3]研究一個類似的系統——Volley，依照用戶的訪問日志，將其數據按照地理分布進行服務器劃分，從而降低存儲和帶寬的要求，即讓信息的接收者更加靠近信息源。同樣， Pujol等[4]研發的SPAR系統將社交網絡中的用戶和所有的鄰居都放置于同一個服務器上，從而減少必要的分庫數量并提高了查詢效率，降低帶寬損耗。Duong等[5]提出一種新的算法，以貝葉斯網絡為模型進行社交網絡社區劃分，使得社區中的人員聯系更加緊密，并在一定程度上兼顧了負載均衡。

以上Karagiannis、Agarwal與Pujol的研究使庫內用戶的關系緊密從而提升了查詢效率，節省存儲與帶寬損耗，Duong等更是一定程度上兼顧了負載均衡，但是有兩點問題需要解決：1)這些基于用戶相似性的分庫是需要對系統中數據進行復雜的分析，然后進行分庫處理，這樣就必須面對原始數據遷移[6]的問題。2)對社交網絡用戶進行關系分析然后進行基于“關系”的分庫是一個NP問題，以上研究雖然對系統現存數據進行了很好的切分，但是卻沒有處理新數據(無行為日志、無用戶間關系記錄等)添加的問題。

基于聚類分析的數據庫分庫策略是對非物理水平分庫的一種嘗試，其在兼顧負載均衡、零數據遷移的基礎上，將具有相似或相同屬性的數據聚集到同一個或者有限的幾個數據分庫之中去，從而減少了事件查詢中不同數據分庫的訪問次數，并節約了數據庫的連接資源。另外，聚類分析是從數據存儲底層進行數據切分，避開了對系統中的具體業務邏輯關系的詳細把握，只針對數據的屬性及取值進行相應聚類處理，操作相對簡單、高效。

1 社交網絡模型以及問題定義

1.1 社交網絡模型定義

社交網絡的數據主要包含各種事件主體信息，以及發生在各事件主體間的事件。其中各事件主體之間的關系也可以看成是一種特殊事件，即建立起主體間的關系的事件。由此可以看出，社交網絡的數據結構其實是一種復雜的圖結構。

在社交網絡數據中各主體信息構成圖中的頂點V，而頂點間的事件構成了圖中的邊E，但是社交網絡數據與普通的圖結構有著三方面不同：

1)允許存在邊E的兩個端點為同一個點V。

2)允許某起點i至某終點j之間有多條邊。

3)圖中Eij一般用來記錄頂點i與j之間的距離，而在社交網絡數據中Eij記錄著主體i對主體j之間的事件。

綜上，根據圖論，將社交網絡模型相關定義如下：

社交網絡主體V即社交網絡中各種行為或者虛擬行為涉及的所有擁有特征屬性的個體的集合。和常規的語句中的“主語”定義不同，社交網絡的主體擁有更大的范圍。例如某人閱讀某篇文章的行為中，人和文章均為主體，都擁有自己的特征屬性。一般在數據庫的數據存儲中，會把具有一樣的特征屬性的主體存在同一個數據表中，如把所有的用戶信息存放在用戶信息表(User)中。一個行為涉及的主體可以是人和物，也可以是人和人，甚至物和物。例如一個虛擬行為：一個圖書購買清單包含許多的圖書，行為的雙方主體均為物。在社交網絡數據中，大多數情況下行為中主體至少一方為人。本文的研究范圍也是如此，作為行為雙方均為物的虛擬行為，暫不納入本文的研究范圍。

社交網絡事件E即對社交網絡行為的一種抽象描述，主要包含兩個方面：行為所涉及的主體以及行為的描述，主體行為間具有方向性。VA為行為的主動行使者，VB為行為的被動接受者，而行為的說明為依賴于現實的具體的業務邏輯T。

(1)

例如某人閱讀了某篇文章，其中行為的主動行使者VA為某人，行為的被動接受者VB為某篇文章，而具體的業務邏輯T是圖書閱讀。一般情況下會把具有相同業務邏輯的行為數據存在一個數據表中，比如把所有文章閱讀行為的數據存在Read_Log中，假設VA、VB屬于不同類型的主體，則其主體信息數據存在其各自的信息記錄表中。

社交網絡數據Q=(V,E*) 復雜圖結構，其中集合V中的元素為社交網絡中的主體，構成圖的各個頂點，集合E*的元素為基于主體的事件E的集合，即為兩點之間的有向的多條邊。

1.2 問題定義

在社交網絡中，很多事件的主體都呈現出一定的相似性，即關系上相近的用戶之間更容易產生某種行為。在社交網絡系統中會發生大量的事件查詢，而這種查詢一般都需要跨表(跨庫)。例如查詢某篇“養生類”文章的最近十條閱讀者的詳細信息。依照常規的水平切分方法，該文章的閱讀者被分散到各個數據分庫中，在執行相關查詢時，將會耗費大量的時間去依次訪問多個數據庫，并對數據庫的連接資源造成一定的浪費；但是實際上，該文章的閱讀者具有很高的相似性，比如他們大部分屬于中老年、中等收入、本科以下學歷群體，如果數據庫是按照年齡、收入、學歷進行聚類分析分庫，這些讀者的信息就會被很大程度地集中在一個或少量的幾個庫中，從而減少了各分庫的訪問次數，提升整體的查詢效率，并節約相應的連接資源。

定義在社交網絡數據中的執行某事件查詢S，其返回的結果為數據集合T*，其描述如下：

T*=S(V,T)

(2)

在傳統的水平分庫系統中，其集合T*中所有的VA或VB元素的信息表數據均勻分散在各個分庫中，設T*共有m個元素，分庫系統中一共有n個分庫，則執行某事件查詢S返回m條數據所要查詢的數據庫個數n′的數學期望為：

E(n′)=m(1-((m-1)/m)n)

(3)

一般為了減少I/O吞吐和數據庫查詢負擔，m的值會低于某個設定值，如m=10即一次只提取10條數據。隨著分庫個數的增加，E(n′)會逐漸趨于m。

假若能夠對根據特征變量進行聚類，使得具有相似或者相同特征的VA或VB放置在少數q(q≥1)個數據庫中，假設某事件的主體聚集程度為P，即：

P=處于某一類的主體發生該事件的記錄數量/總體發生該事件的數量

則需要查詢的數據庫個數n″的數學期望為：

E(n″)=m-(mp-q)

(4)

即當某行為聚類水平P>q/m時，其需要查詢的數據庫個數就會有可能小于m。另外因為聚集最差的情況為隨機分布，即p≥1/m，所以可得E(n″)≤m，即在聚集水平最差的事件中，其查詢數據庫的個數也不會比傳統水平策略所要查詢的個數多。由式(4)可知，在某行為的主體聚集程度P客觀一定的情況下，通過聚類分析減少該聚類存放的數據分庫個數q，即可提高分庫的事件查詢效率。

2 基于聚類分析的數據庫分庫策略

2.1 概述

基于聚類分析的水平分庫策略的基本思想是：通過對事件的主體(人)進行聚類分析，并對其主表以及相應的從表進行分庫，使得相似度高的事件的主體(人)盡量在同一個或者有限的幾個分庫之內，使得在執行事件查詢時減少不同分庫的訪問次數。該分庫策略需要達到3個目的：1)保證分庫內數據的聚合性；2)新數據的高效分庫與兼顧負載均衡；3)分庫擴容時零數據遷移。其主要的構成分為3個部分：

1)初始數據積累。確定最小分庫數據樣本量n，并對初始樣本進行積累。根據行業經驗，確定聚類主體的特征變量指標。

2)聚類分析分庫。選擇合適的K個初始基點，使用K-means算法對初始數據進行聚類分析，并對結果進行裝載分庫。在使用“認證庫”機制的基礎上，維護“分類信息表”“分庫信息表”，定義新數據的分類距離與分庫距離，并確定“模糊距離上限”，從而實現新增數據的聚類效果與負載均衡的兼顧。

3)分庫擴容。選擇需要擴容的“靶庫”，通過設置“分庫信息表”進行假分裂擴容，實現零數據遷移。

2.2 初始數據積累

在社交網絡中數據量是極為龐大的，如果對全部數據進行聚類分析，不但會消耗大量的時間、人力以及硬件資源，而且分析后的結果用于數據庫分庫要面臨大量數據遷移的問題，所以新的方法希望能夠使用最少的數據(樣本)來完成聚類分析，確定目標聚類。在統計學中對于大樣本的數量沒有一個明確的設定，所以需要根據各行業經驗以及特征變量的分布、取值區間等信息進行事先確定。由于社交網絡數據的主體的特征變量一般服從近似正態分布[7]，根據行業經驗，本文認為達到1 000條數據[8]即可以很好地描述單個分類的狀況。所以，本文初步確定數據庫分庫最小樣本量為：

N=1 000*n;n為分庫個數

(5)

積累足夠容量的樣本以后，由領域專家對于輸入的原始數據，根據業內經驗選取合適的指標特征變量來確定能夠深刻刻畫樣本主體的性質和結構，使其具有廣泛的事件影響性。另外，為了盡可能地使事件都能在該主題的特征變量上體現出一定的聚合性，而且考慮運算復雜度問題，指標特征變量的維度不應選擇過高。選擇好特征變量后，根據變量性質，考慮是否需要量綱或加權變換。

2.3 聚類分析分庫與負載均衡

通過聚類分析將初始數據根據其相似度，即特征標量的差異程度進行分類，使用K-means算法進行聚類分析是一個很好的選擇。K-means算法對各數據進行特征變量的歐氏距離計算，距離值越小代表相似性越高，并以所有數據的各類的總體方差為聚類效果評定標準，高效、直觀地反映出數據的聚類效果。

使用K-means算法，對初始的數據進行聚類分析，并得到目標的K=n個類。將聚類的結果，將這些聚類依次劃分到n個分庫中去，具體操作步驟如下：

1)創建“分類信息表C-info”與“分類信息表T-info”。其結構如表1所示，T-info(分庫名id，類名id，數據規模N)，如表2所示，C-info(聚類名C_id,，聚類質心坐標μ，聚類規模M)，其中T-info.C_id與C_info.C_id為主外鍵約束關系。注：為了簡明起見，以下距離、坐標等均以2維來舉例。

表1 分庫信息表T-info

表2 分類信息表C-info

2)初始化C-info與T-info表中的數據。其中C-info中逐條記錄經過K-means算法處理后的各聚類的id，質心坐標以及類中元素的個數。T-info與C-info一一對應，其數據規模即為對應的聚類規模。

3)創建“認證庫”，記錄各user_id與目標分庫的映射。注：創建“認證庫”，不僅可以用來查詢user_id與目標分庫的映射，還可以在映射規則發生改變時避免舊數據的分庫遷移。

初始數據分庫分配以后，需要處理陸續新入庫的數據。對于新加入點X(i)，按照其距離各類質心的歐氏距離來判定其所屬分類，即判定公式為：

(6)

其所屬分庫的判定公式為：

(7)

分庫的判定公式是在歐氏距離的基礎上進行了基于分庫數據量Nj、總數據量s、負載能力λj的加權設置。其中s表示當前總數據量，Nj表示第j庫的當前數據量，λj表示第j分庫的負載能力，一般來說各分庫的負載能力是相同的所以全部取λ=1。這樣，擁有較高數據量的分庫具有相對低的權值，從而使得原本屬于該分庫的數據有很大可能被平衡到該分庫(類)附近的分庫中去。

綜上，在添加新的數據時所需執行的步驟如下：

1)取得數據的向量(x′，y′)；

2)計算其到各分類質心的歐氏距離，選擇距離最小的類即為該點的目標分類C；找到其距離小于最大模糊距離上限的幾個分庫，再對這些分庫計算其分庫加權距離，選擇距離最小的庫即為新增數據的目標分庫P；

3)將新數據寫入分庫P，并在“驗證庫”中記錄其映射；

4)更新分類信息表中C類的質心(xc，yc)、聚類規模Mc與分庫信息表中P庫的數據規模Np如下：

(8)

基于以上步驟會得到所有數據的隸屬聚類，并且單個數據有且只有一個所屬聚類。

2.4 分庫擴容與零數據遷移

采用傳統的水平切分分庫擴容時，只需改變映射規則，即擴大id%N中的N值，并添加相應數量的分庫即可。而基于聚類分析的數據庫分庫系統其擴容方法有所不同：根據所添加的每一個分庫都與原分庫系統中的一個 “靶庫”具有一一映射關系即可以把新增庫看作相應“靶庫”的一個子節點。

定義“靶庫”，為當前分庫系統中被選定需要被擴容的分庫，一般為一定的預期內，數據量最先達到數據負載上限的分庫。一般“靶庫”都是具有相對高的數據量或者高的數據增速。

假設第P個庫數據量較大，預期內將會達到其負載上限，現需要對其進行擴容，由于采用“驗證庫”的機制，所以無需數據遷移，只需要在“分庫信息表T-info”中添加一個新的分庫Q信息即可。其中Q的數據規模為NQ=0，類名C_id為CP即可。這樣當有新的屬于類CP的數據加入時，該數據都會被優先分配到Q庫，直到Q庫的數據量達到或超過P庫為止。

3 實驗結果與分析

3.1 實驗數據說明

本章使用Facebook上SimlySam應用(已作名稱處理)的真實數據，通過實驗驗證了基于聚類分析的社交網絡數據庫分庫策略相比傳統水平分庫策略的優越性。Facebook是全球最大的社交網絡平臺，SimlySam是該平臺上的一款社區類應用，其月均活躍用戶600萬，每天的處理的數據請求達到2億人次。為了快速實現整個數據庫分庫的過程，本文選擇SmilySarm東南亞版本的數據(400萬用戶)進行目標K=20的分庫實驗。

3.2 實驗方案設計

本次實驗將對Simly Sam中用戶信息庫(Account，Profile)進行基于聚類的水平切分分庫，并放置在原水平切分的局域網分庫的主機之上，然后與當前Hash取模切分的傳統分庫事件查詢效果進行對比。

由于社交網絡中很多用戶行為的發生都會受到用戶的年紀，學歷，收入的影響，所以本文簡單選取(age，degree，income)為Account的特征指標變量，并根據其各自的分布確定其有效取值區間，然后進行量綱處理，使其具有相同的量綱。

設置最小初始樣本容量n=20 000，進行初始樣本分庫，然后依次對剩下的所有的Account數據進行目標分庫的數據添加，以及副表Profile的數據添加。其初始聚類分析結果如圖1所示。

圖1 初始數據樣本聚類分析結果

選擇一個可能的特征事件，即可能對主體(age，degree，income)特征變量指標體現出一定“聚合性”的事件。例如：對熱門文章的閱覽記錄。不同年紀、學歷、收入的人對活動的關注度表現出相當大的聚合性。隨機提取某一篇熱門日志的閱覽記錄，每次取M=10條不同的數據，對數據中的id進行認證庫查詢，獲得分庫的查詢次數為n″，根據id%20計算出傳統水平分庫下分庫的查詢次數n′。重復執行100次上述過程，獲得平均的效率提升度：

(9)

再變更分庫數量n與信息查詢量m，對比其查詢效率提升的變化情況。

3.3 實驗結果分析

3.3.1 特征事件查詢實驗效果對比

選取特征事件：官方活動Event的閱讀事件，即認為該事件的行為主體在特征向量的分布上，具有一定的聚合性。

定義查詢行為：查詢某活動最新的10條回復的人的詳細信息。具體查詢步驟為：先從“官方活動庫”的Reply表查詢最近某Event的10條回復記錄，然后根據記錄中的user_id去“認證庫”查找其映射的目標DB，然后去目標DB查詢相應的用戶信息。

如果用戶對某一官方活動Event的感興趣程度依賴于主體的特征指標的分布，則ρ>P*，P*為設定閾值，實驗中設定P*=2%，即平均效率提升低于2%，認為沒有帶來查詢效率提升。設定X軸為隨即選取的官方活動序列，Y軸為查詢某活動最新的10條回復的人的詳細信息的具體時間消耗。注：在分庫的部署環境中，其平均數據庫認證連接級數據傳輸時間約為0.07 s，在S=4 000 000的數據規模中執行一次有索引查找的時間約為0.001 s，其實驗結果如圖2所示。

圖2 查詢某Event閱讀事件的查詢耗時

由圖2發現在100次隨機實驗中，基于聚類分庫策略的分庫訪問次數分布基本都在傳統分庫策略(Hash取模分庫)的下方或與之持平，少部分情況會出現n″>n′。

根據實驗數據得到基于熱門文章閱讀事件的兩種策略下訪問效率提升的分布，并且基于實驗數據計算出平均效率提升，如圖3所示：

ρ(官方活動Event的閱讀事件查詢)=7.61%>p*

注：由于分庫間網絡連接與傳輸耗時波動的存在，對效率提升的對比造成了一定的干擾，所以實驗選擇集群負載較低時進行實驗測試。

圖3 查詢某Event閱讀事件的查詢效率提升分布

3.3.2 其他事件查詢實驗效果對比

根據上述方法，實驗選取對FamilyFarm中較為重要的獎品兌換行為(Gift_Log)事件、充值行為(Pay_Log)事件、用戶登錄(Signon)事件在分庫數目n=20，信息提取量m=10的情況下得到基于聚類的水平分庫策略的效率提升分布，如圖4～6所示。

圖4 積分兌換紀念品事件的數據查詢訪問效率提升分布

圖5 充值行為事件的數據查詢訪問效率提升分布

圖6 用戶登錄事件的數據查詢訪問效率提升分布

由以上數據可以得出，基于聚類分析的數據庫分庫策略對用戶充值行為事件的查詢效率提升最大，對獎品兌換行為事件有一定的效率提升，對用戶登錄事件提升有限。

如果基于聚類分析的分庫策略對某事件的效率提升沒有影響，或者影響有限，有兩種可能：1)該事件的發生在事件主體的特征空間里確實近乎隨機分布，也就是不呈現明顯的聚合性；2)該事件對選取的主體的特征變量不敏感，從而影響了效率的提升。

實驗將初始的特征變量(age，degree，income)降為二維(age，income)，從新執行聚類分析分庫，然后對積分兌換紀念品事件進行新的查詢效率實驗，得到新的查詢效率提升分布如圖7。

圖7 新特征變量下積分兌換紀念品事件的查詢效率提升分布

由此可以看出不同的特征變量的選取會對事件的查詢效率的提升產生很大的影響，所以在初始選擇特征變量時，應選取能夠深刻刻畫樣本主題性質，并盡量能被更廣泛事件所“響應”的特征變量。

綜合實驗結果可得，基于聚類分析的社交網絡數據分庫策略能夠很好地提升社交網絡數據內部分事件的查詢效率，從而提升整個系統的性能，但是初始特征變量的選取將對整體查詢效率的提升有著重大的影響，所以應根據行業經驗或者由領域專家選擇相對最優的特征變量。

3.3.3 分庫數量n對事件查詢效率提升度ρ的影響

上文提到，在傳統水平分庫下，執行某事件查詢返回m條數據所要查詢的數據庫個數n′的數學期望為：

E(n′)=m(1-((m-1)/m)n)

隨著n的增大E(n′) →m。現對用戶信息庫(Account，Profile)以n=10，20，30，40不同分庫個數進行分庫，并比較查詢Event閱讀事件的查詢效率提升情況如圖8所示。

圖8 不同分庫數目n下Event閱讀事件查詢效率提升

由圖8可知：1)隨著分庫個數n的增加，事件查詢效率的提升度ρ也在升高；2)隨著分庫個數的n的增加，ρ增速放緩，趨于穩定。造成這兩點現象的原因是，當m一定時，隨著n的升高，在傳統分庫下，E(n′)收斂于m，使得效率提升ρ遞增且趨于穩定。

3.3.4 查詢信息量m對事件查詢效率度提升度ρ的影響

在公式E(n′)=m(1-((m-1)/m)n)中，當n一定時，隨著m的增大，尤其m>n以后E(n′) →n。現對在分庫個數n=20的情況下，設置每次提取信息個數m=10，20，30，40，并比較查詢Event閱讀事件的查詢效率提升情況如圖9所示。

由圖9、10可知：1)當mn時，其效率提升度逐漸下降最后趨于0。

綜合3.3.3節與3.3.4節的實驗結果，得出結論：

1)數據分庫的個數越多，進行聚類分析所帶來的查詢效率提升效果越好。

2)當數據分庫個數不大于業內一次信息提取個數(一般為10～20)設定時，不建議進行聚類分析分庫。

圖9 不同查詢信息數目m下Event閱讀事件查詢效率提升

3.3.5 分庫負載均衡分析

負載均衡是基于聚類的數據庫分庫策略需要解決的問題之一。在對初始20 000條數據進行聚類分析后一般不對數據進行遷移，所以初始20 000條數據放置在第1分庫中，然后對剩余的所有數據進行分庫，并通過計算各分庫數據量的變異系數q來記錄各分庫的負載均衡程度：

q=σ/μ

(10)

其中:σ為各分庫數據量標準差，μ為其數據量均值。

由圖10可以看出：隨著總數據量的增多，各分庫數量也在逐漸增加，但是由于各分類的差異，會有部分分庫的數量與其他分庫有較大差異，但是隨著數據的進一步擴大，各分庫的數據最終會向數據量均線收斂。總的來看，基于聚類的數據庫分庫策略基本實現了分庫的負載均衡，總數據量越大，效果越好。

圖10 各分庫數據量變異系數q變化

3.3.6 無數據遷移的分庫擴容

基于聚類的數據庫分庫策略在進行分庫擴容時，需要先選取需要擴容的“靶庫”，然后在“分庫信息表”中添加一個一條新增庫信息即可實現“靶庫”的擴容。

實驗在總數據量為1 000 000時，選擇數據量最大的第10庫(第1庫實際分庫數據應約為74 715-20 000=54 715)進行擴容，并添加第21庫信息在分庫信息表里。分庫信息表內容如表3所示。

表3 對第10庫進行擴容的分庫信息表設置

對第10庫進行擴容后，繼續進行新數據的添加，觀察第10庫與第21庫的數據增長情況，如圖11所示：在數據總量為1 000 000時對靶庫第10庫進行擴容，隨后第10庫數據量保持不變，其擴容庫第21庫數量開始逐漸上升，直到第21庫的數據量和第10庫數據量持平以后，兩庫數據量一起上升。

圖11 “靶庫”第10庫與擴容庫第21庫數據增長情況

由以上得出結論，擴容庫實現了對“靶庫”的無數據遷移擴容，分擔了“靶庫”的數據負載，而且這種擴容可以隨時實施，實施以后原“靶庫”的剩余空間依然可以得到充分利用。

4 結語

基于聚類分析的社交網絡數據分庫策略能夠很好地提升社交網絡中部分事件的查詢效率，基本兼顧了分庫的負載均衡，并實現了零數據遷移的分庫擴容，但是需要注意以下兩點：

查詢效率的提升程度依賴于信息提取量m與分庫個數n的值，n值越大，效率提升效果越好。一般情況下n>m時，基于聚類分析的分庫才有必要。

另外，初始特征變量的選取將對整體查詢效率的提升有著重大的影響，所以應根據行業經驗或者由領域專家選擇相對最優的特征變量。

)

[1] 肖凌,劉繼紅,姚建初.分布式數據庫系統的研究與應用[J].計算機工程,2001,27(1):33-35.(XIAOL,LIUJH,YAOJC.Researchandapplicationofdistributeddatabase[J].ComputerEngineering, 2001, 27(1): 33-35.)

[2]KARAGIANNIST,GKANTSIDISC,NARAYANAND,etal.Hermes:clusteringusersinlarge-scalee-mailservices[C]//Proceedingsofthe1stACMSymposiumonCloudComputing.NewYork:ACM, 2010:89-100.

[3]AGARWALS,DUNAGANJ,JAINN,etal.Volley:automateddataplacementforgeo-distributedcloudservices[C]//Proceedingsofthe7thUSENIXConferenceonNetworkedSystemsDesignandImplementation.Berkeley,CA:USENIXAssociation, 2010: 2.

[4]PUJOLJM,ERRAMILLIV,SIGANOSG,etal.Thelittleengine(s)thatcould:scalingonlinesocialnetworks[C]//ProceedingsoftheACMSIGCOMM2010Conference.NewYork:ACM, 2010: 375-386.

[5]DUONGQ,GOELS,HOFMANJ,etal.Shardingsocialnetworks[C]//WSDM’13:Proceedingsofthe6thACMInternationalConferenceonWebSearchandDataMining.NewYork:ACM, 2013: 223-232.

[6] 熊華平,李莉嬌,陳付平,等.大型異構數據庫數據遷移系統的研究與應用[J].計算機應用與軟件,2012,29(7):178-181.(XIONGHP,LILJ,CHENFP,etal.Researchandapplicationofdatamigrationsysteminlargescaleheterogeneousdatabase[J].ComputerApplicationsandSoftware, 2012, 29(7):178-181.)

[7] 張友蘭.大型信息系統可靠性試驗最小樣本量方法研究[J].環境技術,2013(11):59-64.(ZHANGYL.Researchonthereliabilityexperimentminimumsizesamplemethodforlarge-scaleinformationsystem[J].EnvironmentalTechnology, 2013(11):59-64.)

[8] 李進芳,郭海明.樣本量確定的經濟學分析[J].統計與決策,2009(19):22-23.(LIJF,GUOHM.Economicanalysisofsamplesizedetermination[J].StatisticsandDecision, 2009(19):22-23.)

[9]MISLOVEA,MARCONM,GUMMADIKP,etal.Measurementandanalysisofonlinesocialnetworks[C]//Proceedingsofthe7thACMSIGCOMMConferenceonInternetMeasurement.NewYork:ACM, 2007: 29-42.

[10]MOENSS,AKSEHIRLIE,GOETHALSB.Frequentitemsetminingforbigdata[C]//Proceedingsofthe2013IEEEInternationalConferenceonBigData.Piscataway,NJ:IEEE, 2013: 111-118.

[11]FORTUNATOS.Communitydetectioningraphs[J].PhysicsReports, 2010, 486(3/4/5): 75-174.

[12]DENGJ,DONGW,SOCHERR,etal.ImageNet:alarge-scalehierarchicalimagedatabase[C]//Proceedingsofthe2009IEEEComputerSocietyConferenceonComputerVisionandPatternRecognition.Washington,DC:IEEEComputerSociety, 2009: 248-255.

[13]HUANGJ,ERTEKINS,GILESCL.Efficientnamedisambiguationforlarge-scaledatabases[C]//Proceedingsofthe10thEuropeanConferenceonPrincipleandPracticeofKnowledgeDiscoveryinDatabases.Berlin:Springer, 2006: 536-544.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61262069, 61472346),theNaturalScienceFoundationofYunnanProvince(2015FB114, 2015FB149, 2016FA026),theProgramforYoungandMiddle-agedSkeletonTeachersinYunnanUniversity,theProgramforInnovationResearchTeaminYunnanUniversity(XT412011).

LIANG Shuang, born in 1987, M. S. His research interests include social network analysis, distributed databases.

ZHOU Lihua, born in 1968, Ph.D., professor. Her research interests include data mining, social network analysis.

YANG Peizhong, born in 1992, M. S. candidate. His research interests include data mining, social network analysis.

Query performance and data migration for social network database with shard strategy based on clustering analysis

LIANG Shuang, ZHOU Lihua*, YANG Peizhong

(CollegeofInformation,YunnanUniversity,KunmingYunnan650000,China)

Social network data has a certain degree of aggregation, namely the similar users are more prone to the same behavior. According to the conventional horizontal database shard method, a large amount of time and connection loss were consumed in order to access a plurality of databases in turn when performing the information query of these events. In order to solve this problem, the database shard strategy based on clustering analysis was proposed. Through clustering the characteristic scalars of social network subjects, the main body with the high aggregation was divided into one or as possible libraries to improve the query efficiency of the events, and to give consideration to load balancing, large data migration and other issues. The experimental results show that for the mainstream social networking events, the performance improvement of the proposed strategy is up to 23.4% at most, and local optimal load balance and zero data migration are realized. In general, the database shard strategy based on clustering analysis of social network, has a considerable advantage on improving query efficiency, balance load balancing and large data migration feasibility over the traditional conventional horizontal database shard method of cutting library.

social network; database shard; clustering analysis; query performance; data migration

2016- 09- 26;

2016- 10- 23。

國家自然科學基金資助項目(61262069, 61472346)；云南省自然科學基金資助項目(2016FA026, 2015FB114, 2015FB149)；云南大學中青年骨干教師、創新研究團隊發展計劃(XT412011)。

梁雙(1987—)，男，河南信陽人，碩士，主要研究方向：社交網絡分析、分布式數據庫； 周麗華(1968—)，女，云南昆明人，教授，博士，CCF會員，主要研究方向：數據挖掘、社交網絡分析； 楊培忠(1992—)，男，云南保山人，碩士研究生，CCF會員，主要研究方向：數據挖掘、社交網絡分析。

1001- 9081(2017)03- 0673- 07

10.11772/j.issn.1001- 9081.2017.03.673

TP302

A