高速核外圖處理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn).pdf

1、現(xiàn)實(shí)世界的大數(shù)據(jù)可以轉(zhuǎn)化為圖數(shù)據(jù)來(lái)處理，由于大數(shù)據(jù)涉及各個(gè)學(xué)科和領(lǐng)域、規(guī)模龐大，并且依然保持高速增長(zhǎng)，從轉(zhuǎn)化后的圖數(shù)據(jù)中提取知識(shí)變得越來(lái)越難。基于磁盤(pán)的圖處理系統(tǒng)（核外圖處理系統(tǒng)）具有使用方便、對(duì)資源使用效率高、不依賴(lài)圖劃分等優(yōu)點(diǎn)，普通人能輕易獲得并完成各種圖查詢(xún)算法，但是大部分圖查詢(xún)算法執(zhí)行時(shí)會(huì)導(dǎo)致頻繁的隨機(jī)磁盤(pán)訪問(wèn)，影響性能。為了提高磁盤(pán)使用效率，現(xiàn)有核外圖處理系統(tǒng)大多采用連續(xù)磁盤(pán)訪問(wèn)，需要載入大塊的數(shù)據(jù)到內(nèi)存，對(duì)某些算法來(lái)說(shuō)，載入

2、內(nèi)存的數(shù)據(jù)使用效率非常低，導(dǎo)致性能下降。此外，內(nèi)存的不足使得計(jì)算過(guò)程中需要磁盤(pán)存儲(chǔ)中間計(jì)算數(shù)據(jù)（update數(shù)據(jù)），造成額外的I/O開(kāi)銷(xiāo)，低效的update數(shù)據(jù)處理方式同樣影響系統(tǒng)性能。
　　高速核外圖處理系統(tǒng)（FOG）提出了核外數(shù)據(jù)的快速索引機(jī)制，通過(guò)使用虛擬內(nèi)存系統(tǒng)將磁盤(pán)數(shù)據(jù)映射到內(nèi)存，并結(jié)合基于位圖管理的混合型調(diào)度機(jī)制，實(shí)現(xiàn)了按需調(diào)度磁盤(pán)數(shù)據(jù)的功能，解決了內(nèi)存數(shù)據(jù)浪費(fèi)的問(wèn)題，并且該混合型調(diào)度機(jī)制在保持了高并發(fā)性的同時(shí)減少了迭

3、代次數(shù)，加快了系統(tǒng)處理速度。針對(duì) update數(shù)據(jù)處理低效的問(wèn)題，F(xiàn)OG實(shí)現(xiàn)了一種核內(nèi)數(shù)據(jù)的置放與處理機(jī)制，通過(guò)分段載入較小的屬性文件的方式在內(nèi)存處理update數(shù)據(jù)，減少了I/O開(kāi)銷(xiāo)，該機(jī)制同時(shí)將大量的隨機(jī)磁盤(pán)訪問(wèn)轉(zhuǎn)化為連續(xù)磁盤(pán)訪問(wèn)，提高磁盤(pán)使用效率，加快系統(tǒng)處理速度。
　　實(shí)驗(yàn)結(jié)果表明，在相同硬件、軟件配置下，對(duì)同樣的圖數(shù)據(jù)執(zhí)行代表性圖查詢(xún)算法時(shí)，相比于開(kāi)源系統(tǒng)GraphChi和X-Stream，F(xiàn)OG的處理速度最多提高了25