本文轉(zhuǎn)載自公眾號(hào)“讀芯術(shù)”(ID：AI_Discovery)。

生活中的許多地方都在運(yùn)用著數(shù)據(jù)庫(kù)技術(shù)，例如詐騙檢測(cè)、知識(shí)圖譜、資產(chǎn)管理、推薦瀏覽器、物聯(lián)網(wǎng)、權(quán)限管理等等。數(shù)據(jù)庫(kù)技術(shù)能夠快速分析相關(guān)度高的數(shù)據(jù)點(diǎn)以及其之間的聯(lián)系，圖形數(shù)據(jù)庫(kù)便是其中之一。

但由于圖形數(shù)據(jù)本身性質(zhì)特殊，其在架構(gòu)方面還面臨諸多挑戰(zhàn)。那么，圖形數(shù)據(jù)庫(kù)是否能夠擴(kuò)展呢?本文將全面分析可能阻礙圖形數(shù)據(jù)庫(kù)擴(kuò)展的兩個(gè)挑戰(zhàn)，并討論當(dāng)前可用的解決方案。

[[351497]]

什么是"圖形數(shù)據(jù)庫(kù)的可擴(kuò)展性"?

“擴(kuò)展”，不只是指將更多的數(shù)據(jù)存入一臺(tái)計(jì)算機(jī)或隨便存進(jìn)多臺(tái)計(jì)算機(jī)。對(duì)于大型數(shù)據(jù)集或不斷增長(zhǎng)的數(shù)據(jù)集，良好的查詢性能十分必要。

所以，其中真正的問(wèn)題在于，當(dāng)單臺(tái)計(jì)算機(jī)上的數(shù)據(jù)集增長(zhǎng)到會(huì)影響其他功能時(shí)，圖形數(shù)據(jù)庫(kù)的表現(xiàn)能否令人滿意呢?如果你還不能理解為什么這是首要問(wèn)題，請(qǐng)和我一起快速回顧以下圖形數(shù)據(jù)庫(kù)。

簡(jiǎn)單來(lái)說(shuō)，圖形數(shù)據(jù)庫(kù)用于存儲(chǔ)無(wú)架構(gòu)對(duì)象(頂點(diǎn)或節(jié)點(diǎn))以及任意數(shù)據(jù)(屬性)和對(duì)象(邊緣)的關(guān)聯(lián)數(shù)據(jù)。邊通常能夠指出對(duì)象之間的著力點(diǎn)，頂點(diǎn)和邊共同構(gòu)成圖形網(wǎng)絡(luò)數(shù)據(jù)集。

離散數(shù)學(xué)將圖形定義為一組頂點(diǎn)和邊;而計(jì)算機(jī)科學(xué)則將其定義為一種抽象的數(shù)據(jù)類型，它能夠表示連接或關(guān)系。它不同于關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)中的表格數(shù)據(jù)結(jié)構(gòu)，后者表達(dá)數(shù)據(jù)關(guān)系的能力十分有限。

如上所述，圖形由節(jié)點(diǎn)(又名頂點(diǎn)[V]) 組成，這些節(jié)點(diǎn)由關(guān)系(即邊[E])連接。

頂點(diǎn)具有任意數(shù)量的邊和任意深度(路徑的長(zhǎng)度)的窗體路徑。

它也可以針對(duì)跨行金融交易進(jìn)行圖形建模，如下圖所示。此例中，我們可以將銀行帳戶定義為節(jié)點(diǎn)，銀行交易記錄與其他關(guān)系定義為邊緣。

以這種方式存儲(chǔ)帳戶和交易信息，以遍歷創(chuàng)建圖形未知或變化的數(shù)據(jù)深度。在關(guān)系數(shù)據(jù)庫(kù)中編寫和運(yùn)行此類查詢功能往往是一項(xiàng)復(fù)雜的工作(使用多模型數(shù)據(jù)庫(kù)能夠以銀行與其分支機(jī)構(gòu)之間的關(guān)系來(lái)建模)。

圖形數(shù)據(jù)庫(kù)提供各種算法，以便用戶查詢所存儲(chǔ)的數(shù)據(jù)及分析其間關(guān)系。包括遍歷、模式匹配、最短路徑或分布式圖形處理，如分析社區(qū)偵測(cè)、連接組件或中心性。大多數(shù)算法都有一個(gè)共同點(diǎn)，這也是解決超節(jié)點(diǎn)和網(wǎng)絡(luò)躍點(diǎn)問(wèn)題的本質(zhì)——算法通過(guò)邊從一個(gè)節(jié)點(diǎn)遍歷到另一個(gè)節(jié)點(diǎn)。

快速回顧之后，挑戰(zhàn)就要開(kāi)始啦!

“名人效應(yīng)”

上文已提到頂點(diǎn)或節(jié)點(diǎn)可以具有任意數(shù)量的邊。超級(jí)點(diǎn)的一個(gè)經(jīng)典例子便是網(wǎng)紅——超節(jié)點(diǎn)是圖形數(shù)據(jù)集中傳入或傳出邊條數(shù)過(guò)多的節(jié)點(diǎn)。帕特里克·斯圖爾特爵士的Twitter賬戶目前就擁有340多萬(wàn)粉絲。

如果現(xiàn)在將帳戶和推文數(shù)據(jù)進(jìn)行圖形建模，遍歷其數(shù)據(jù)即Patrick Stewart的帳戶信息，那么算法必須定向分析Steward帳戶所有的340萬(wàn)條邊。這就會(huì)延長(zhǎng)查詢執(zhí)行時(shí)間，甚至可能突破被授權(quán)的權(quán)限。類似的問(wèn)題存在于欺詐檢測(cè)(帳戶進(jìn)行大量交易、網(wǎng)絡(luò)管理-大型 IP hub)等案例中。

超級(jí)節(jié)點(diǎn)是圖形的固有問(wèn)題，也是所有圖形數(shù)據(jù)庫(kù)面臨的問(wèn)題，以下兩種方法能盡量減少超節(jié)點(diǎn)的影響。

[[351501]]

圖源：unsplash

方法一：拆分超節(jié)點(diǎn)

更準(zhǔn)確來(lái)說(shuō)，可以復(fù)制節(jié)點(diǎn)"Patrick Stewart"，并按某個(gè)屬性(如粉絲的國(guó)家/地區(qū)或其他特定分組)拆分?jǐn)?shù)據(jù)邊緣。這樣就會(huì)將超節(jié)點(diǎn)遍歷數(shù)據(jù)對(duì)性能的影響降至最低，以便查詢分類時(shí)所用。

方法二：中心節(jié)點(diǎn)索引

以頂點(diǎn)為中心的索引同時(shí)存儲(chǔ)邊緣信息和有關(guān)節(jié)點(diǎn)的信息。還是以帕特里克·斯圖爾特的 Twitter 帳戶為例，可以這樣分組：粉絲的起始關(guān)注日期/時(shí)間信息、粉絲的國(guó)家/地區(qū)、粉絲的粉絲數(shù)等等，以上所有屬性都可以為更高效地使用()提供選擇性。

查詢引擎可使用索引來(lái)減少執(zhí)行遍歷功能所需的線性查找次數(shù)，詐騙檢測(cè)也可采用此方法。上文中金融交易便是邊緣，交易日期或交易金額等屬性可以增加選擇效率。

某些情況下，以上兩種方法都不適用;遍歷超節(jié)點(diǎn)時(shí)，性能一定程度上會(huì)下降。多數(shù)情況下，還是有辦法優(yōu)化性能，但另一個(gè)問(wèn)題是大多數(shù)圖形數(shù)據(jù)庫(kù)尚未解決的。

網(wǎng)絡(luò)躍點(diǎn)問(wèn)題

假如需要遍歷一個(gè)高度連接的數(shù)據(jù)集，查詢所需的所有數(shù)據(jù)的記憶都負(fù)荷在同一臺(tái)計(jì)算機(jī)上，查詢單個(gè)主要記憶大約需要100ns。

假設(shè)數(shù)據(jù)集已經(jīng)遠(yuǎn)遠(yuǎn)滿足單個(gè)實(shí)例所需，或者操作者想要提高群集或是全包的可用性和處理能力。在圖形案例中，分片的意思就是拆除之前所建立的連接，因?yàn)閳D形遍歷所需的數(shù)據(jù)當(dāng)前可能留在不同計(jì)算機(jī)上。這會(huì)導(dǎo)致的查詢信息時(shí)網(wǎng)絡(luò)延遲，網(wǎng)絡(luò)可能不是開(kāi)發(fā)人員的問(wèn)題，但查詢性能就是了。

即使現(xiàn)代Gbit 網(wǎng)絡(luò)和服務(wù)器位于同一機(jī)架，網(wǎng)絡(luò)查找的成本也比內(nèi)存中在查找貴5000倍左右。若在連接群集服務(wù)器的網(wǎng)絡(luò)上添加一點(diǎn)負(fù)載，后果不可預(yù)想。

這種情況下，遍歷可能從數(shù)據(jù)庫(kù)服務(wù)器1開(kāi)始，點(diǎn)擊具有指向存儲(chǔ)在 DB Server 2上的頂點(diǎn)邊緣的節(jié)點(diǎn)，從而通過(guò)網(wǎng)絡(luò)進(jìn)行查找網(wǎng)絡(luò)躍點(diǎn)?？紤]到更多實(shí)際中的情況，在單個(gè)遍歷查詢中，實(shí)際上是存在多個(gè)躍點(diǎn)的。

在詐騙檢測(cè)、IT網(wǎng)絡(luò)管理，甚至現(xiàn)代企業(yè)識(shí)別和訪問(wèn)管理案例中，可能會(huì)涉及到分配圖形數(shù)據(jù)，同時(shí)還需要以低于秒的性能執(zhí)行查詢功能。而查詢執(zhí)行期間產(chǎn)生的大量網(wǎng)絡(luò)躍點(diǎn)可能會(huì)使之失敗，付出高昂的縮放代價(jià)。

更智能的解決方法

大多數(shù)情況下，如果對(duì)數(shù)據(jù)有一些了解，你就可以更智能地來(lái)分片圖形(客戶 ID、區(qū)域等)。其他時(shí)候，也可以使用分布式圖形分析，通過(guò)使用社區(qū)檢測(cè)算法(例如ArangoDB的Pregel 套件)生成此域知識(shí)，從而進(jìn)行計(jì)算。

例如，詐騙檢測(cè)就需要分析財(cái)務(wù)交易以確定詐騙套路。在過(guò)去，騙子利用某些國(guó)家或地區(qū)的銀行來(lái)洗錢。我們可以使用此領(lǐng)域知識(shí)作為圖形數(shù)據(jù)集的分片密鑰，并在 DB 服務(wù)器1上分配在此區(qū)域執(zhí)行的所有財(cái)務(wù)事務(wù)，并在其他服務(wù)器上分配處理其他事務(wù)。

而現(xiàn)在，使用ArangoDB的SmartGraph功能，本地就能阻止洗錢或查詢其他圖形的請(qǐng)求，避免或至少大幅度降低了查詢期間所產(chǎn)生的網(wǎng)絡(luò)躍點(diǎn)。這究竟是如何做到的?

ArangoDB中的查詢引擎能夠記憶遍歷所需的數(shù)據(jù)存儲(chǔ)位置，并向每個(gè)數(shù)據(jù)庫(kù)服務(wù)器的查詢引擎發(fā)送請(qǐng)求，然后在本地處理請(qǐng)求。之后，每個(gè)數(shù)據(jù)庫(kù)服務(wù)器上結(jié)果的差異會(huì)被合并到協(xié)調(diào)器并發(fā)送到客戶端。對(duì)于層次分明的圖形，還可以利用不相交的智能圖來(lái)優(yōu)化查詢。

對(duì)于解決數(shù)據(jù)縮放問(wèn)題的呼聲越來(lái)越高，而圖形技術(shù)對(duì)于回答此類復(fù)雜的問(wèn)題也愈發(fā)重要。

筆者可以肯定地說(shuō)，圖形數(shù)據(jù)庫(kù)在垂直方向上擴(kuò)展是可行的，在ArangoDB中，水平擴(kuò)展也能實(shí)現(xiàn)。當(dāng)然，在有些極端不常見(jiàn)的情況下，中心節(jié)點(diǎn)索引和SmartGraphs也都無(wú)能為力。