0
| 本文作者： 楊曉凡 | 2017-08-29 15:03 |
雷鋒網(wǎng) AI 科技評論按：Facebook今天在研究blog上發(fā)布了一篇文章，介紹了自己的超大規(guī)模圖分區(qū)優(yōu)化算法SHP。這是 Facebook 為了處理自己的規(guī)模過大的圖分區(qū)問題開發(fā)的方法，而且在大規(guī)模優(yōu)化問題中確實發(fā)揮了作用。這項研究的論文也已經(jīng)被數(shù)據(jù)庫領域著名國際會議 VLDB 2017（Very Large Data Bases）收錄。雷鋒網(wǎng) AI 科技評論把這篇介紹文章編譯如下。
對Facebook來說，每天它要服務的用戶是十億級別的。為了支持這種規(guī)模的訪問量，F(xiàn)acebook 需要在許多個不同的層次上設計分布式的負載。Facebook 在全球建立了多個數(shù)據(jù)中心來提升用戶訪問的可靠性、容錯性，以及改善延遲。不過單個托管服務器的容量和計算資源總是有限的，F(xiàn)acebook 的存儲系統(tǒng)需要在多個托管服務器之間共享數(shù)據(jù)，批量計算任務也需要在上千個工作站形成的集群上運行，以便提升計算規(guī)模、加快計算速度。
這些系統(tǒng)的核心是一系列小安排，就是決定如何把請求、數(shù)據(jù)條目、計算任務等等任務元素分配給數(shù)據(jù)中心、托管服務器或者工作站等等計算小組中的某一個。能夠分配任務的方法有無數(shù)種，但是不同的分配方法帶來的響應時間和服務質量可謂天差地別。
要考慮的第一個方面就是負載平衡：如果某一個計算小組已經(jīng)過載了，它就沒辦法達到原定的響應時間或者服務水平。對于給定的負載分布，總還有進一步優(yōu)化的潛力，因為很多的事情在同一處做的效果都比分開做的效果更好。比如把兩個經(jīng)常需要同時訪問的數(shù)據(jù)放在同一個存儲托管服務器上就能夠提升會用到這些數(shù)據(jù)的查詢性能。
平衡圖分區(qū)（balanced graph partitioning）就提供了一種有用的方法來處理任務背后的工作量分配問題。在這種方法中，圖里的節(jié)點會被分給多個“bucket”中的一個，代表著計算項目會被平衡地分配給多個計算小組中的一個，整個過程中還持續(xù)對任務的某些特征進行優(yōu)化，比如單個小組內(nèi)的任務相似性。以前Facebook就在文章中介紹過他們?nèi)绾斡闷胶鈭D分區(qū)的方法達到了前所未有的系統(tǒng)表現(xiàn)，在他們的新論文「Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner」中，F(xiàn)acebook 介紹了一種分區(qū)二分圖的新方法，它能夠讓扇出（fan-out）最小化。這種新方法在Facebook的許多分布式負載優(yōu)化任務中都發(fā)揮了效果。Facebook 把基于這種方法形成的框架稱作 Social Hash Partitioner (SHP)，因為它可以作為之前 Facebook NSDI 2016論文中的 Social Hash 框架的超圖分區(qū)組件。
以下對 SHP 的亮點作逐一介紹
Facebook 研究員們研究如何減少扇出問題的起源就是分布式數(shù)據(jù)集中經(jīng)常出現(xiàn)的碎片化問題。假設有這樣一個情況，一個很大的數(shù)據(jù)集，其中的數(shù)據(jù)記錄分布在許多個數(shù)據(jù)服務器上。對數(shù)據(jù)集的一次查詢可能會用到好幾條數(shù)據(jù)記錄，如果這些數(shù)據(jù)記錄分散在好幾個服務器上，那么就需要給這每一個服務器都發(fā)送查詢才能夠應答原來的查詢。這樣一來，把數(shù)據(jù)記錄分配給不同的服務器的方式就決定了處理一個查詢的時候需要發(fā)起的新查詢的數(shù)目；這個數(shù)字就被稱作這次查詢的“扇出 fan-out”。扇出低的查詢就可以執(zhí)行得更快，因為過程中需要與一個較慢的服務器溝通的可能性更低，而且也通過減少溝通計算量的方式降低了整個系統(tǒng)的負載。所以，一種常見的優(yōu)化目標就是為數(shù)據(jù)集選擇一種數(shù)據(jù)分配方法，讓不同的查詢所需要的數(shù)據(jù)直接存放在同一個地方。
圖1就給出了分別用生成的訪問請求和真實的請求測試后的系統(tǒng)表現(xiàn)。
圖1
在圖中，縱坐標t代表了系統(tǒng)的平均延遲?？梢钥吹礁呱瘸龅恼埱蟪惺艿难舆t也更高。具體來說，40左右就是很高的扇出值了，如果降低到10，這個查詢的延遲就可以達到平均值。
碎片化存儲問題可以建模為一個二分圖分區(qū)問題。圖2中，數(shù)據(jù)條目和需要訪問它們的查詢被表示為二分圖中的頂點，然后要把數(shù)據(jù)分為k個組；分的過程中每個組要分到近似的數(shù)據(jù)量，而且每個查詢需要連接到的不同的組數(shù)目的平均值要越小越好。
圖2
找到一個圖的優(yōu)化分區(qū)往往是一個很難計算的問題。一種典型的啟發(fā)式方法是從一些初始的平衡分區(qū)開始，在一個迭代過程中對某些頂點的分配做局部小調(diào)整，逐漸提高分組的效果。在每輪迭代中，每一個頂點都會估計把自己換到其它分組里面去的偏好，這個稱作“收益 gain”。如果新的收益比目前分配方式的收益高，就可以嘗試在保持總體負載平衡的情況下把這個頂點移到另一個組里面去。
不過，這個方法用在扇出優(yōu)化里面的效果很不好，圖3中就是一種出現(xiàn)問題的情形，圖中標出的V1和V2分別在兩個組之中。
圖3
每個查詢 (q1, q2, q3) 都剛好訪問了兩個分組，所以平均扇出就是2。但這并不是最優(yōu)分組，因為如果把頂點3、4和5、6交換位置的話就會把q1和q2查詢的扇出降低為1，平均扇出就會降低為1.33。然而，從每一個頂點自己的角度看來，把自己更換到另一個分組里面去并不會有更高的收益，所以需要用到這個節(jié)點的扇出就不會得到任何優(yōu)化。
Facebook 的新研究改善了這種狀況，他們把優(yōu)化目標變得“平滑”：不再假設一個查詢需要求出所有所需數(shù)據(jù)的扇出，而假設它會以一個概率p訪問每個數(shù)據(jù)條目。這樣就把每個頂點從分組 i 更換到分組 j 的收益 v 表示為：
圖4
其中的 N(v) 是訪問 v 的一組查詢，ni(q) 是查詢 q 在分組 i 中訪問的數(shù)據(jù)條目數(shù)量。采用了這樣的收益估計之后，頂點就更容易表現(xiàn)出對含有同類查詢的分組的偏好，即便在執(zhí)行了這樣的更換之后也沒有降低實際扇出。
這樣，論文中的算法就可以表示為如下的形式：
初始化一組平衡的分組（比如隨機）
重復如下步驟直到收斂
對于每一個頂點 v
根據(jù)以上的方程，找到移動收益最高的分組 j
記錄下頂點 v 有想從當前分組 i 移動到新分組 j 的意愿
對于每一對分組 i 和 j
找到有從 i 到 j 的意愿的頂點和有從 j 到 i 的意愿的節(jié)點，更換它們
扇出最小化問題等效于一個平衡超圖分區(qū)問題。目前就有一些超圖分區(qū)框架，但是Facebook的圖規(guī)模太大了，現(xiàn)有框架都處理不了。
Facebook 在 Apache Giraph 構建了他們的解決方案，而且為圖的大小和理想的分組數(shù)目做了精心的設計：頂點運動的評價可以用分布式的方式完成，而且發(fā)生在當前頂點與其它頂點溝通過任務分配之后。同樣地，頂點更換的操作也可以用分布式的方法完成，成對的小組 (i,j) 可以分布在不同的托管服務器上，或者用概率選擇對更換的決定做近似。在實際應用中，F(xiàn)acebook 的研究人員們發(fā)現(xiàn)以分布式方法實現(xiàn)的算法能夠處理的圖要比其它現(xiàn)有方法能處理的最大的圖還要大100倍，同時還無需犧牲優(yōu)化質量。
圖5展現(xiàn)了算法的運行時數(shù)據(jù)（SHP的兩個變體 SHP-2和 SHP-K）并與其它現(xiàn)有的分區(qū)框架進行了對比。測試內(nèi)容包含在三個不同大小的圖（邊的數(shù)目不同，從一千萬到五十億）和不同的分組數(shù)目中的表現(xiàn)。在小規(guī)模的優(yōu)化任務中，SHP往往是完成得最快的那個；而對于大規(guī)模優(yōu)化任務，SHP是唯一一個能夠在合理的時間內(nèi)求出一個優(yōu)化方案的參賽者。
圖5
圖6展現(xiàn)了SHP和其它框架的優(yōu)化質量的對比。由于網(wǎng)絡真正的最優(yōu)平均扇出目前并不能確定，所以圖中展示的是各個結果高出現(xiàn)有最優(yōu)算法的百分比。在大規(guī)模優(yōu)化任務中，SHP的效果是最好的；不過在小規(guī)模優(yōu)化任務中，SHP最多可以比現(xiàn)有算法中最好的結果差12%。
圖6
扇出減少模型可以在Facebook的許多基礎優(yōu)化問題中起到作用，比如數(shù)據(jù)碎片化、查詢路由和索引壓縮。從 SHP 開發(fā)成功之后，F(xiàn)acebook 就經(jīng)常用它來解決具有十億節(jié)點和萬億條邊的圖扇出優(yōu)化問題，內(nèi)部實驗表明在分布式系統(tǒng)上使用 SHP 的數(shù)據(jù)分配方案可以把 CPU 消耗下降一半之多。這篇論文也被收錄在了 VLDB 2017。SHP 也已經(jīng)作為一個 Giraph 應用開源，可以用在優(yōu)化任務和教育中。
論文地址：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 科技評論編譯
雷峰網(wǎng)版權文章，未經(jīng)授權禁止轉載。詳情見轉載須知。
