雷鋒網(wǎng) AI 科技評(píng)論按：Facebook今天在研究blog上發(fā)布了一篇文章，介紹了自己的超大規(guī)模圖分區(qū)優(yōu)化算法SHP。這是 Facebook 為了處理自己的規(guī)模過(guò)大的圖分區(qū)問(wèn)題開發(fā)的方法，而且在大規(guī)模優(yōu)化問(wèn)題中確實(shí)發(fā)揮了作用。這項(xiàng)研究的論文也已經(jīng)被數(shù)據(jù)庫(kù)領(lǐng)域著名國(guó)際會(huì)議 VLDB 2017（Very Large Data Bases）收錄。雷鋒網(wǎng) AI 科技評(píng)論把這篇介紹文章編譯如下。

對(duì)Facebook來(lái)說(shuō)，每天它要服務(wù)的用戶是十億級(jí)別的。為了支持這種規(guī)模的訪問(wèn)量，F(xiàn)acebook 需要在許多個(gè)不同的層次上設(shè)計(jì)分布式的負(fù)載。Facebook 在全球建立了多個(gè)數(shù)據(jù)中心來(lái)提升用戶訪問(wèn)的可靠性、容錯(cuò)性，以及改善延遲。不過(guò)單個(gè)托管服務(wù)器的容量和計(jì)算資源總是有限的，F(xiàn)acebook 的存儲(chǔ)系統(tǒng)需要在多個(gè)托管服務(wù)器之間共享數(shù)據(jù)，批量計(jì)算任務(wù)也需要在上千個(gè)工作站形成的集群上運(yùn)行，以便提升計(jì)算規(guī)模、加快計(jì)算速度。

這些系統(tǒng)的核心是一系列小安排，就是決定如何把請(qǐng)求、數(shù)據(jù)條目、計(jì)算任務(wù)等等任務(wù)元素分配給數(shù)據(jù)中心、托管服務(wù)器或者工作站等等計(jì)算小組中的某一個(gè)。能夠分配任務(wù)的方法有無(wú)數(shù)種，但是不同的分配方法帶來(lái)的響應(yīng)時(shí)間和服務(wù)質(zhì)量可謂天差地別。

要考慮的第一個(gè)方面就是負(fù)載平衡：如果某一個(gè)計(jì)算小組已經(jīng)過(guò)載了，它就沒(méi)辦法達(dá)到原定的響應(yīng)時(shí)間或者服務(wù)水平。對(duì)于給定的負(fù)載分布，總還有進(jìn)一步優(yōu)化的潛力，因?yàn)楹芏嗟氖虑樵谕惶幾龅男Ч急确珠_做的效果更好。比如把兩個(gè)經(jīng)常需要同時(shí)訪問(wèn)的數(shù)據(jù)放在同一個(gè)存儲(chǔ)托管服務(wù)器上就能夠提升會(huì)用到這些數(shù)據(jù)的查詢性能。

平衡圖分區(qū)（balanced graph partitioning）就提供了一種有用的方法來(lái)處理任務(wù)背后的工作量分配問(wèn)題。在這種方法中，圖里的節(jié)點(diǎn)會(huì)被分給多個(gè)“bucket”中的一個(gè)，代表著計(jì)算項(xiàng)目會(huì)被平衡地分配給多個(gè)計(jì)算小組中的一個(gè)，整個(gè)過(guò)程中還持續(xù)對(duì)任務(wù)的某些特征進(jìn)行優(yōu)化，比如單個(gè)小組內(nèi)的任務(wù)相似性。以前Facebook就在文章中介紹過(guò)他們?nèi)绾斡闷胶鈭D分區(qū)的方法達(dá)到了前所未有的系統(tǒng)表現(xiàn)，在他們的新論文「Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner」中，F(xiàn)acebook 介紹了一種分區(qū)二分圖的新方法，它能夠讓扇出（fan-out）最小化。這種新方法在Facebook的許多分布式負(fù)載優(yōu)化任務(wù)中都發(fā)揮了效果。Facebook 把基于這種方法形成的框架稱作 Social Hash Partitioner (SHP)，因?yàn)樗梢宰鳛橹?Facebook NSDI 2016論文中的 Social Hash 框架的超圖分區(qū)組件。

以下對(duì) SHP 的亮點(diǎn)作逐一介紹

減少扇出

Facebook 研究員們研究如何減少扇出問(wèn)題的起源就是分布式數(shù)據(jù)集中經(jīng)常出現(xiàn)的碎片化問(wèn)題。假設(shè)有這樣一個(gè)情況，一個(gè)很大的數(shù)據(jù)集，其中的數(shù)據(jù)記錄分布在許多個(gè)數(shù)據(jù)服務(wù)器上。對(duì)數(shù)據(jù)集的一次查詢可能會(huì)用到好幾條數(shù)據(jù)記錄，如果這些數(shù)據(jù)記錄分散在好幾個(gè)服務(wù)器上，那么就需要給這每一個(gè)服務(wù)器都發(fā)送查詢才能夠應(yīng)答原來(lái)的查詢。這樣一來(lái)，把數(shù)據(jù)記錄分配給不同的服務(wù)器的方式就決定了處理一個(gè)查詢的時(shí)候需要發(fā)起的新查詢的數(shù)目；這個(gè)數(shù)字就被稱作這次查詢的“扇出 fan-out”。扇出低的查詢就可以執(zhí)行得更快，因?yàn)檫^(guò)程中需要與一個(gè)較慢的服務(wù)器溝通的可能性更低，而且也通過(guò)減少溝通計(jì)算量的方式降低了整個(gè)系統(tǒng)的負(fù)載。所以，一種常見的優(yōu)化目標(biāo)就是為數(shù)據(jù)集選擇一種數(shù)據(jù)分配方法，讓不同的查詢所需要的數(shù)據(jù)直接存放在同一個(gè)地方。

圖1就給出了分別用生成的訪問(wèn)請(qǐng)求和真實(shí)的請(qǐng)求測(cè)試后的系統(tǒng)表現(xiàn)。

圖1

在圖中，縱坐標(biāo)t代表了系統(tǒng)的平均延遲?？梢钥吹礁呱瘸龅恼?qǐng)求承受的延遲也更高。具體來(lái)說(shuō)，40左右就是很高的扇出值了，如果降低到10，這個(gè)查詢的延遲就可以達(dá)到平均值。

碎片化存儲(chǔ)問(wèn)題可以建模為一個(gè)二分圖分區(qū)問(wèn)題。圖2中，數(shù)據(jù)條目和需要訪問(wèn)它們的查詢被表示為二分圖中的頂點(diǎn)，然后要把數(shù)據(jù)分為k個(gè)組；分的過(guò)程中每個(gè)組要分到近似的數(shù)據(jù)量，而且每個(gè)查詢需要連接到的不同的組數(shù)目的平均值要越小越好。

圖2

找到低扇出的分區(qū)

找到一個(gè)圖的優(yōu)化分區(qū)往往是一個(gè)很難計(jì)算的問(wèn)題。一種典型的啟發(fā)式方法是從一些初始的平衡分區(qū)開始，在一個(gè)迭代過(guò)程中對(duì)某些頂點(diǎn)的分配做局部小調(diào)整，逐漸提高分組的效果。在每輪迭代中，每一個(gè)頂點(diǎn)都會(huì)估計(jì)把自己換到其它分組里面去的偏好，這個(gè)稱作“收益 gain”。如果新的收益比目前分配方式的收益高，就可以嘗試在保持總體負(fù)載平衡的情況下把這個(gè)頂點(diǎn)移到另一個(gè)組里面去。

不過(guò)，這個(gè)方法用在扇出優(yōu)化里面的效果很不好，圖3中就是一種出現(xiàn)問(wèn)題的情形，圖中標(biāo)出的V1和V2分別在兩個(gè)組之中。

圖3

每個(gè)查詢 (q1, q2, q3) 都剛好訪問(wèn)了兩個(gè)分組，所以平均扇出就是2。但這并不是最優(yōu)分組，因?yàn)槿绻秧旤c(diǎn)3、4和5、6交換位置的話就會(huì)把q1和q2查詢的扇出降低為1，平均扇出就會(huì)降低為1.33。然而，從每一個(gè)頂點(diǎn)自己的角度看來(lái)，把自己更換到另一個(gè)分組里面去并不會(huì)有更高的收益，所以需要用到這個(gè)節(jié)點(diǎn)的扇出就不會(huì)得到任何優(yōu)化。

Facebook 的新研究改善了這種狀況，他們把優(yōu)化目標(biāo)變得“平滑”：不再假設(shè)一個(gè)查詢需要求出所有所需數(shù)據(jù)的扇出，而假設(shè)它會(huì)以一個(gè)概率p訪問(wèn)每個(gè)數(shù)據(jù)條目。這樣就把每個(gè)頂點(diǎn)從分組 i 更換到分組 j 的收益 v 表示為：

圖4

其中的 N(v) 是訪問(wèn) v 的一組查詢，n_i(q) 是查詢 q 在分組 i 中訪問(wèn)的數(shù)據(jù)條目數(shù)量。采用了這樣的收益估計(jì)之后，頂點(diǎn)就更容易表現(xiàn)出對(duì)含有同類查詢的分組的偏好，即便在執(zhí)行了這樣的更換之后也沒(méi)有降低實(shí)際扇出。

這樣，論文中的算法就可以表示為如下的形式：

1. 初始化一組平衡的分組（比如隨機(jī)）

2. 重復(fù)如下步驟直到收斂

1. 對(duì)于每一個(gè)頂點(diǎn) v

1. 根據(jù)以上的方程，找到移動(dòng)收益最高的分組 j

2. 記錄下頂點(diǎn) v 有想從當(dāng)前分組 i 移動(dòng)到新分組 j 的意愿
   

2. 對(duì)于每一對(duì)分組 i 和 j

1. 找到有從 i 到 j 的意愿的頂點(diǎn)和有從 j 到 i 的意愿的節(jié)點(diǎn)，更換它們

優(yōu)化效果和大規(guī)模問(wèn)題的表現(xiàn)

扇出最小化問(wèn)題等效于一個(gè)平衡超圖分區(qū)問(wèn)題。目前就有一些超圖分區(qū)框架，但是Facebook的圖規(guī)模太大了，現(xiàn)有框架都處理不了。

Facebook 在 Apache Giraph 構(gòu)建了他們的解決方案，而且為圖的大小和理想的分組數(shù)目做了精心的設(shè)計(jì)：頂點(diǎn)運(yùn)動(dòng)的評(píng)價(jià)可以用分布式的方式完成，而且發(fā)生在當(dāng)前頂點(diǎn)與其它頂點(diǎn)溝通過(guò)任務(wù)分配之后。同樣地，頂點(diǎn)更換的操作也可以用分布式的方法完成，成對(duì)的小組 (i,j) 可以分布在不同的托管服務(wù)器上，或者用概率選擇對(duì)更換的決定做近似。在實(shí)際應(yīng)用中，F(xiàn)acebook 的研究人員們發(fā)現(xiàn)以分布式方法實(shí)現(xiàn)的算法能夠處理的圖要比其它現(xiàn)有方法能處理的最大的圖還要大100倍，同時(shí)還無(wú)需犧牲優(yōu)化質(zhì)量。

圖5展現(xiàn)了算法的運(yùn)行時(shí)數(shù)據(jù)（SHP的兩個(gè)變體 SHP-2和 SHP-K）并與其它現(xiàn)有的分區(qū)框架進(jìn)行了對(duì)比。測(cè)試內(nèi)容包含在三個(gè)不同大小的圖（邊的數(shù)目不同，從一千萬(wàn)到五十億）和不同的分組數(shù)目中的表現(xiàn)。在小規(guī)模的優(yōu)化任務(wù)中，SHP往往是完成得最快的那個(gè)；而對(duì)于大規(guī)模優(yōu)化任務(wù)，SHP是唯一一個(gè)能夠在合理的時(shí)間內(nèi)求出一個(gè)優(yōu)化方案的參賽者。

圖5

圖6展現(xiàn)了SHP和其它框架的優(yōu)化質(zhì)量的對(duì)比。由于網(wǎng)絡(luò)真正的最優(yōu)平均扇出目前并不能確定，所以圖中展示的是各個(gè)結(jié)果高出現(xiàn)有最優(yōu)算法的百分比。在大規(guī)模優(yōu)化任務(wù)中，SHP的效果是最好的；不過(guò)在小規(guī)模優(yōu)化任務(wù)中，SHP最多可以比現(xiàn)有算法中最好的結(jié)果差12%。

圖6

結(jié)論和拓展閱讀

扇出減少模型可以在Facebook的許多基礎(chǔ)優(yōu)化問(wèn)題中起到作用，比如數(shù)據(jù)碎片化、查詢路由和索引壓縮。從 SHP 開發(fā)成功之后，F(xiàn)acebook 就經(jīng)常用它來(lái)解決具有十億節(jié)點(diǎn)和萬(wàn)億條邊的圖扇出優(yōu)化問(wèn)題，內(nèi)部實(shí)驗(yàn)表明在分布式系統(tǒng)上使用 SHP 的數(shù)據(jù)分配方案可以把 CPU 消耗下降一半之多。這篇論文也被收錄在了 VLDB 2017。SHP 也已經(jīng)作為一個(gè) Giraph 應(yīng)用開源，可以用在優(yōu)化任務(wù)和教育中。

論文地址：http://www.vldb.org/pvldb/vol10/p1418-pupyrev.pdf 

NSDI 2016的分區(qū)優(yōu)化器論文地址：https://www.usenix.org/system/files/conference/nsdi16/nsdi16-paper-shalita.pdf 

via Facebook Research Blog，雷鋒網(wǎng) AI 科技評(píng)論編譯

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。