節(jié)選自《大數(shù)據(jù)日知錄：架構(gòu)與算法》十四章，書籍目錄在此

??????? 對(duì)于海量待挖掘數(shù)據(jù)，在分布式計(jì)算環(huán)境下，首先面臨的問(wèn)題就是如何將數(shù)據(jù)比較均勻地分配到不同的服務(wù)器上。對(duì)于非圖數(shù)據(jù)來(lái)說(shuō)，這個(gè)問(wèn)題解決起來(lái)往往比較直觀，因?yàn)橛涗浿g獨(dú)立無(wú)關(guān)聯(lián)，所以對(duì)數(shù)據(jù)切分算法沒有特別約束，只要機(jī)器負(fù)載盡可能均衡即可。由于圖數(shù)據(jù)記錄之間的強(qiáng)耦合性，如果數(shù)據(jù)分片不合理，不僅會(huì)造成機(jī)器之間負(fù)載不均衡，還會(huì)大量增加機(jī)器之間的網(wǎng)絡(luò)通信（見圖14-5），再考慮到圖挖掘算法往往具有多輪迭代運(yùn)行的特性，這樣會(huì)明顯放大數(shù)據(jù)切片不合理的影響，嚴(yán)重拖慢系統(tǒng)整體的運(yùn)行效率，所以合理切分圖數(shù)據(jù)對(duì)于離線挖掘類型圖應(yīng)用的運(yùn)行效率來(lái)說(shuō)非常重要，但是這也是至今尚未得到很好解決的一個(gè)潛在問(wèn)題。

?????? 對(duì)于圖數(shù)據(jù)的切片來(lái)說(shuō)，怎樣才是一個(gè)合理或者是好的切片方式？其判斷標(biāo)準(zhǔn)應(yīng)該是什么？就像上面的例子所示，衡量圖數(shù)據(jù)切片是否合理主要考慮兩個(gè)因素：機(jī)器負(fù)載均衡以及網(wǎng)絡(luò)通信總量。如果單獨(dú)考慮機(jī)器負(fù)載均衡，那么最好是將圖數(shù)據(jù)盡可能平均地分配到各個(gè)服務(wù)器上，但是這樣不能保證網(wǎng)絡(luò)通信總量是盡可能少的（參考圖14-5右端切割方式，負(fù)載比較均衡，但是網(wǎng)絡(luò)通信較多）；如果單獨(dú)考慮網(wǎng)絡(luò)通信，那么可以將密集連通子圖的所有節(jié)點(diǎn)盡可能放到同一臺(tái)機(jī)器上，這樣就有效地減少了網(wǎng)絡(luò)通信量，但是這樣很難做到機(jī)器之間的負(fù)載均衡，某個(gè)較大的密集連通子圖會(huì)導(dǎo)致某臺(tái)機(jī)器高負(fù)載。所以，合理的切片方式需要在這兩個(gè)因素之間找到一個(gè)較穩(wěn)妥的均衡點(diǎn)，以期系統(tǒng)整體性能最優(yōu)。

????????

??

????? 下面介紹兩類從不同出發(fā)點(diǎn)切割圖數(shù)據(jù)的方法，并分別介紹典型的具體切分算法及其對(duì)應(yīng)的數(shù)學(xué)分析，首先需要強(qiáng)調(diào)一點(diǎn)：在選擇具體的切分算法時(shí)并非越復(fù)雜的算法越可能在實(shí)際系統(tǒng)中被采納，讀者可以思考其中的道理，在后面會(huì)給出解答。

??????

14.3.1? 切邊法（Edge-Cut）

????? 現(xiàn)在面臨的問(wèn)題是：給定一個(gè)巨大的圖數(shù)據(jù)和p臺(tái)機(jī)器，如何將其切割成p份子圖？解決這個(gè)圖切割問(wèn)題有兩種不同的思路。

????? 切邊法代表了最常見的一種思路，切割線只能穿過(guò)連接圖節(jié)點(diǎn)的邊，通過(guò)對(duì)邊的切割將完整的圖劃分為p個(gè)子圖。圖14-6代表將7個(gè)節(jié)點(diǎn)的圖分發(fā)到3臺(tái)機(jī)器上，左端展示了切邊法方式，圖節(jié)點(diǎn)的編號(hào)代表節(jié)點(diǎn)被分發(fā)到的機(jī)器編號(hào)。

??????????

??? ? 通過(guò)切邊法切割后的圖數(shù)據(jù)，任意一個(gè)圖節(jié)點(diǎn)只會(huì)被分發(fā)到一臺(tái)機(jī)器，但是被切割開的邊數(shù)據(jù)會(huì)在兩臺(tái)機(jī)器中都保存，而且被切割開的邊在圖計(jì)算的時(shí)候意味著機(jī)器間的遠(yuǎn)程通信。很明顯，系統(tǒng)付出的額外存儲(chǔ)開銷和通信開銷取決于被切割開的邊的數(shù)量，圖切割時(shí)通過(guò)的邊越多，則系統(tǒng)需額外承載的存儲(chǔ)開銷和通信開銷越高。

???? 前文有述，衡量圖數(shù)據(jù)分片合理與否有兩個(gè)考慮因素：負(fù)載均衡和機(jī)器通信量，所以對(duì)于切邊法來(lái)說(shuō)，所有具體的切割算法追求的目標(biāo)不外是：如何在盡可能均衡地將圖節(jié)點(diǎn)分配到集群中的不同機(jī)器上這一約束下，來(lái)獲得最小化切割邊數(shù)量。

???

???? 即在每臺(tái)機(jī)器被分發(fā)到的節(jié)點(diǎn)盡可能均勻的條件約束下，求切割邊最少的方法。其中，|V|/p代表所有的節(jié)點(diǎn)被p臺(tái)機(jī)器均分所得數(shù)值，l≥1代表不平衡調(diào)節(jié)因子，通過(guò)調(diào)節(jié)l的大小可以控制節(jié)點(diǎn)分配的均勻度，當(dāng)其值為1時(shí)，要求完全均分，其值越大，允許的不均衡程度越高。

????? 從上述形式化描述可以看出，lamda約等于1的時(shí)候，這個(gè)問(wèn)題本質(zhì)上是一個(gè)圖切割中的均衡p路分區(qū)（Balanced p-way Partitioning）問(wèn)題，解決這個(gè)問(wèn)題有很多相關(guān)研究（有興趣的讀者可以閱讀本章參考文獻(xiàn)[4]），但是由于圖切割算法的時(shí)間復(fù)雜度較高，基本不太適合處理大規(guī)模數(shù)據(jù)，所以在真實(shí)的大規(guī)模數(shù)據(jù)場(chǎng)景下很少被采用。

????? 在實(shí)際的圖計(jì)算系統(tǒng)中，經(jīng)常使用的策略是節(jié)點(diǎn)隨機(jī)均分法，即通過(guò)哈希函數(shù)將節(jié)點(diǎn)均分到集群的各個(gè)機(jī)器中，并不仔細(xì)考慮邊切割情況。Pregel和GraphLab都采用了這種策略。這種方法的優(yōu)點(diǎn)是快速、簡(jiǎn)單且易實(shí)現(xiàn)，但是從定理14.1可以證明這種方法會(huì)將圖中絕大多數(shù)的邊都切開。??

????? 由定理14.1可知，假設(shè)集群包含10臺(tái)機(jī)器，則被切割的邊比例大約為90%，即90%的邊會(huì)被切開，而如果包含100臺(tái)機(jī)器，則99%的邊會(huì)被切開。可見，這種切分方式是效率很低的一種。

???

14.3.2? 切點(diǎn)法（Vertex-Cut）

????? 切點(diǎn)法代表另外一種切割圖的不同思路。與切邊法不同，切點(diǎn)法在切割圖的時(shí)候，切割線只能通過(guò)圖節(jié)點(diǎn)而非邊，被切割線切割的圖節(jié)點(diǎn)可能同時(shí)出現(xiàn)在多個(gè)被切割后的子圖中。圖14-6右側(cè)是切點(diǎn)法示意圖，從圖中可看出，圖中心的節(jié)點(diǎn)被切割成三份，也就是意味著這個(gè)節(jié)點(diǎn)會(huì)同時(shí)出現(xiàn)在被切割后的三個(gè)子圖中。

???? 與切邊法正好相反，切點(diǎn)法切割后的圖中，每條邊只會(huì)被分發(fā)到一臺(tái)機(jī)器上，不會(huì)重復(fù)存儲(chǔ)，但是被切割的節(jié)點(diǎn)會(huì)被重復(fù)存儲(chǔ)在多臺(tái)機(jī)器中，因此，同樣存在額外存儲(chǔ)開銷。另外，如此切割帶來(lái)的問(wèn)題是：圖算法在迭代過(guò)程中往往會(huì)不斷更新圖節(jié)點(diǎn)的值，因?yàn)槟硞€(gè)節(jié)點(diǎn)可能存儲(chǔ)在多臺(tái)機(jī)器中，也即存在數(shù)據(jù)多副本問(wèn)題，所以必須解決圖節(jié)點(diǎn)值數(shù)據(jù)的一致性問(wèn)題。對(duì)這個(gè)問(wèn)題，在后面講解PowerGraph系統(tǒng)時(shí)，會(huì)給出一種典型的解決方案。

???? 那么，既然切點(diǎn)法圖中的邊都沒有被切割，機(jī)器之間是否就無(wú)須通信開銷了呢？事實(shí)并非如此，在維護(hù)被切割的圖節(jié)點(diǎn)值數(shù)據(jù)一致性時(shí)仍然會(huì)產(chǎn)生通信開銷。所以，對(duì)于切點(diǎn)法來(lái)說(shuō)，所有具體算法追求的合理切分目標(biāo)是：如何在盡可能均勻地將邊數(shù)據(jù)分發(fā)到集群的機(jī)器中這個(gè)約束條件下，最小化被切割開的圖節(jié)點(diǎn)數(shù)目。

??

???????? 即在每臺(tái)機(jī)器被分發(fā)到的邊盡可能均勻的條件約束下，求平均副本數(shù)最少的方法。其中，|E|/p代表所有邊被p臺(tái)機(jī)器均分所得數(shù)值，l≥1代表不平衡調(diào)節(jié)因子，通過(guò)調(diào)節(jié)l的大小可以控制邊分配的均勻度，當(dāng)其值為1時(shí)，要求完全均分，其值越大，允許的不均衡程度越高。

????? 同樣，由于采用復(fù)雜圖切割算法的時(shí)間復(fù)雜度太高，所以實(shí)際系統(tǒng)中最常用的還是邊隨機(jī)均分

?????? 現(xiàn)實(shí)世界中的大多數(shù)圖的邊分布都遵循power law法則，理論和實(shí)踐已經(jīng)證明，對(duì)于遵循這一法則的圖數(shù)據(jù)來(lái)說(shuō)，屬于切點(diǎn)法的邊隨機(jī)均分法要比切邊法里的節(jié)點(diǎn)隨機(jī)均分法強(qiáng)，其計(jì)算效率要高出至少一個(gè)數(shù)量級(jí)。所以總體而言，對(duì)于一般情形的圖數(shù)據(jù)，采取切點(diǎn)法要明顯優(yōu)于切邊法。

請(qǐng)思考：為何不是越復(fù)雜、有效的切分算法越受歡迎？

解答：一般來(lái)說(shuō)，圖挖掘算法分為兩個(gè)階段。

階段一：集中式圖數(shù)據(jù)切分與分發(fā)；階段二：分布式圖計(jì)算。

如果采用復(fù)雜的圖切割算法，則系統(tǒng)負(fù)載均衡好，機(jī)器間通信量較少，所以第二階段運(yùn)行的效率高，但是采用復(fù)雜算法不僅開發(fā)成本高，在第一階段付出的時(shí)間成本也很高，甚至因此付出的時(shí)間成本要高于在第二階段產(chǎn)生的效率收益，所以選擇何種切分算法也需要有全局的效率權(quán)衡。

超強(qiáng)干貨來(lái)襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的大数据图数据库之数据分片的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。