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

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

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

[[351497]]

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

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

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

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

離散數(shù)學(xué)將圖形定義為一組頂點(diǎn)和邊;而計算機(jī)科學(xué)則將其定義為一種抽象的數(shù)據(jù)類型，它能夠表示連接或關(guān)系。它不同于關(guān)系數(shù)據(jù)庫系統(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ù)量的邊和任意深度(路徑的長度)的窗體路徑。

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

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

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

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

“名人效應(yīng)”

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

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

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

[[351501]]

圖源：unsplash

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

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

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

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

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

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

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

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

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

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

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

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

更智能的解決方法

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

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

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

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

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

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