譯者 | 李睿

審校 | 孫淑娟

許多企業(yè)發(fā)現(xiàn)了圖形數(shù)據(jù)庫在解決連接數(shù)據(jù)的復(fù)雜問題方面提供的巨大價(jià)值。在關(guān)系數(shù)據(jù)庫關(guān)注數(shù)據(jù)模型中的數(shù)據(jù)時(shí)，它們很難從同一數(shù)據(jù)模型中的數(shù)據(jù)項(xiàng)之間的關(guān)系中獲取價(jià)值。而圖形數(shù)據(jù)庫旨在從數(shù)據(jù)模型中的數(shù)據(jù)和關(guān)系中獲取價(jià)值。

當(dāng)需要捕獲和分析的圖形數(shù)據(jù)包含地理元素時(shí)會(huì)發(fā)生什么？當(dāng)企業(yè)的大部分分析都關(guān)注數(shù)據(jù)模型的“位置”方面時(shí)會(huì)發(fā)生什么情況？  

Uber公司工程團(tuán)隊(duì)開發(fā)了名稱為H3的分層六邊形索引，作為將世界劃分為六邊形的模型，并且他們創(chuàng)建了一組用于與這些六邊形交互的API。他們沒有提供H3 API的數(shù)據(jù)庫或存儲(chǔ)模型，但I(xiàn)nfiniteGraph可以發(fā)揮重要作用。  

本文描述了開發(fā)人員實(shí)現(xiàn)圖形數(shù)據(jù)模型來表示Uber H3索引的方法。這個(gè)模型擴(kuò)展了H3模型，允許開發(fā)人員將域數(shù)據(jù)模型組件與存儲(chǔ)在數(shù)據(jù)庫中的H3六邊形相關(guān)聯(lián)。

將所有這些結(jié)合在一起，為開發(fā)人員提供了一組強(qiáng)大的功能，可以根據(jù)域模型和底層H3地理模型來存儲(chǔ)和查詢域數(shù)據(jù)。通過使用InfiniteGraph作為圖形數(shù)據(jù)庫平臺(tái)，可以在高性能系統(tǒng)和分析中以近乎實(shí)時(shí)的速度和規(guī)模對(duì)這些數(shù)據(jù)執(zhí)行復(fù)雜的查詢。InfiniteGraph支持垂直和水平可擴(kuò)展性，以及通過分布實(shí)現(xiàn)的可擴(kuò)展性。因此，可以輕松地向上和向下擴(kuò)展應(yīng)用程序。

統(tǒng)一的地理環(huán)境：一個(gè)故事

為了更深入地了解其現(xiàn)有運(yùn)營(yíng)的業(yè)務(wù)并幫助他們規(guī)劃未來，一家全國(guó)性零售商從其所有的商店的各種來源收集數(shù)據(jù)。所有收集的數(shù)據(jù)都提供了對(duì)其業(yè)務(wù)有直接影響的事物的可見性。

零售商收集以下數(shù)據(jù)：

• 購(gòu)買：  

o購(gòu)買了什么商品  

o購(gòu)買時(shí)間  

o購(gòu)買地點(diǎn)  

• 顧客：  

o客戶住址  

o客戶的電子郵件、電話號(hào)碼和購(gòu)買歷史記錄  

• 供應(yīng)鏈：  

o哪些供應(yīng)商供應(yīng)哪些商品  

o交貨延遲  

o批發(fā)價(jià)格波動(dòng)  

• 運(yùn)營(yíng)商店數(shù)據(jù)：  

o勞動(dòng)力成本  

o水電費(fèi)  

o庫存損失  

• 天氣：  

o每日溫度  

o即將來臨的風(fēng)暴  

每個(gè)數(shù)據(jù)項(xiàng)都存儲(chǔ)在創(chuàng)建統(tǒng)一地理環(huán)境的數(shù)字地圖上。購(gòu)買信息與進(jìn)行購(gòu)買的商店的地圖位置相關(guān)聯(lián)。客戶數(shù)據(jù)與每個(gè)客戶的住址、鄰居和社區(qū)相關(guān)聯(lián)。供應(yīng)鏈數(shù)據(jù)與供應(yīng)商的位置和他們使用的交付路線相關(guān)聯(lián)。運(yùn)營(yíng)商店數(shù)據(jù)與商店的位置相關(guān)聯(lián)。最后，將天氣數(shù)據(jù)應(yīng)用于與商店、客戶和供應(yīng)鏈相關(guān)的所有區(qū)域的地圖。

使用圖形數(shù)據(jù)庫時(shí)，所有這些數(shù)據(jù)匯集在一起，提供了一個(gè)強(qiáng)大的新工具，使零售商能夠?qū)蛻糍?gòu)買模式和人口統(tǒng)計(jì)、復(fù)雜的供應(yīng)鏈互動(dòng)以及惡劣天氣對(duì)銷售和供應(yīng)鏈績(jī)效的影響進(jìn)行預(yù)測(cè)分析。

什么是圖形數(shù)據(jù)庫？

從根本上說，圖形數(shù)據(jù)庫是將數(shù)據(jù)表示為節(jié)點(diǎn)和邊的數(shù)據(jù)庫。節(jié)點(diǎn)通常表示域中的數(shù)據(jù)項(xiàng)（如人物、地點(diǎn)或事物），邊表示節(jié)點(diǎn)之間的關(guān)系。例如，可以將一個(gè)人和一個(gè)地址表示為節(jié)點(diǎn)，然后可以在他們之間創(chuàng)建一條邊來表示“LivesAt”關(guān)系。

圖形數(shù)據(jù)模型為表示數(shù)據(jù)提供了極大的靈活性，可以通過在LivesAt邊緣包含一個(gè)日期范圍來擴(kuò)展Person-LivesAt地址模型，這樣就可以表示一個(gè)人居住過的所有地方。

什么是InfiniteGraph？

InfiniteGraph是一個(gè)面向?qū)ο蟮膱D形數(shù)據(jù)庫平臺(tái)。InfiniteGraph使用聯(lián)合架構(gòu)來實(shí)現(xiàn)大規(guī)模的可擴(kuò)展性。單個(gè)InfiniteGraph聯(lián)合數(shù)據(jù)庫可以分布在65,000臺(tái)服務(wù)器上，理論上可以容納1.84×1019個(gè)對(duì)象。  

開發(fā)人員創(chuàng)建使用InfiniteGraph API庫與聯(lián)合數(shù)據(jù)庫交互的應(yīng)用程序。InfiniteGraph部署了兩個(gè)輕量級(jí)服務(wù)器：一個(gè)鎖服務(wù)器，用于協(xié)調(diào)所有正在運(yùn)行的應(yīng)用程序的鎖；一個(gè)頁面服務(wù)器，響應(yīng)來自客戶端應(yīng)用程序中運(yùn)行的InfiniteGraph API的頁面請(qǐng)求。所有圖形處理都發(fā)生在客戶端應(yīng)用程序和API中。API用作鏈接到客戶端應(yīng)用程序的數(shù)據(jù)庫服務(wù)器，使其速度非常快。  

在許多其他圖形數(shù)據(jù)庫產(chǎn)品使用屬性模型方法的情況下，InfiniteGraph使用基于模式的方法。InfiniteGraph基于模式的方法要求開發(fā)人員在存儲(chǔ)任何數(shù)據(jù)之前，為要存儲(chǔ)的數(shù)據(jù)類型創(chuàng)建模式定義。這提供了許多優(yōu)點(diǎn)，其中包括支持InfiniteGraph的布局管理功能（PMC）。PMC是一個(gè)基于規(guī)則的系統(tǒng)，允許開發(fā)人員定義規(guī)則，規(guī)定數(shù)據(jù)在數(shù)據(jù)庫中的放置方式。PMC規(guī)則可以告訴InfiniteGraph，可能是不同類型的兩個(gè)對(duì)象（例如Person和Address）應(yīng)該放在同一個(gè)磁盤頁面上，因?yàn)樗鼈兘?jīng)常一起使用。

當(dāng)用戶對(duì)人員（Person）執(zhí)行查詢時(shí)，他們接下來可能會(huì)請(qǐng)求相關(guān)的地址（Address）對(duì)象。如果這兩個(gè)對(duì)象在同一個(gè)磁盤頁面上，當(dāng)磁盤頁面被讀取以響應(yīng)對(duì)人員（對(duì)象）的查詢時(shí)，同一磁盤頁面上的相關(guān)地址對(duì)象將被讀入客戶端應(yīng)用程序中的InfiniteGraph頁面緩存中。當(dāng)用戶隨后請(qǐng)求地址對(duì)象時(shí)，將不需要進(jìn)行第二次讀取頁面，因?yàn)閹в械刂穼?duì)象的頁面已在內(nèi)存中。

所有這些功能共同創(chuàng)建了一個(gè)可大規(guī)模擴(kuò)展的高性能對(duì)象圖分析平臺(tái)，客戶可以在該平臺(tái)上構(gòu)建尖端應(yīng)用程序。

什么是H3？  

H3是Uber的六邊形分層空間索引系統(tǒng)。  

Uber公司指出，“……我們開發(fā)了網(wǎng)格系統(tǒng)，以有效地優(yōu)化乘車的定價(jià)和調(diào)度，以可視化和探索空間數(shù)據(jù)。H3使我們能夠分析地理信息以設(shè)置動(dòng)態(tài)價(jià)格，并在全市范圍內(nèi)做出其他決策。我們使用H3作為整個(gè)市場(chǎng)的分析和優(yōu)化網(wǎng)格系統(tǒng)。H3就是為這一目的而設(shè)計(jì)的，并引導(dǎo)我們做出一些選擇，例如使用六邊形層次索引。”  

H3六邊形地址  

H3為每個(gè)六邊形分配一個(gè)唯一的地址。H3地址是形式為“852A1077FFFFF”的十六進(jìn)制值，它們表示特定的六邊形。

該地址允許H3確定：  

• 六邊形的分辨率  
• 六邊形中心的經(jīng)緯度  
• 六邊形每個(gè)角的經(jīng)緯度  
• 它的父地址（假設(shè)它不是分辨率為0的六邊形）  
• 它的7個(gè)H3的子地址（假設(shè)它不是分辨率為15的六邊形）  

H3地址主要是開發(fā)人員與H3索引系統(tǒng)交互的方式。  

H3分辨率  

H3還引入了分辨率概念，以支持不同尺寸的六邊形層次。下表給出了每種解決方案的詳細(xì)信息。在15個(gè)解決方案中，每個(gè)六邊形都有7個(gè)子六邊形。每個(gè)子六邊形約占其父六邊形覆蓋面積的1/7。在除0以外的所有分辨率下，每個(gè)六邊形都有一個(gè)父六邊形。每個(gè)父六邊形覆蓋的面積約為子六邊形的7倍。圖1顯示了分辨率為9的單個(gè)六邊形，它的七個(gè)六邊形分辨率為10，這些六邊形的子六邊形分辨率為11。

圖1：H3六邊形分辨率

構(gòu)建H3圖數(shù)據(jù)庫  

H3 API支持廣泛的轉(zhuǎn)換，使H3成為管理地理數(shù)據(jù)模型的優(yōu)雅工具。但是，H3不提供存儲(chǔ)模型。H3不附帶底層數(shù)據(jù)庫。它本質(zhì)上是一組工具，用于獲取有關(guān)映射到地球上的六邊形的信息。  

因?yàn)镠3提供了有趣的功能，例如根據(jù)其緯度/經(jīng)度計(jì)算六邊形的地址或給六邊形的鄰居的地址，所以創(chuàng)建一個(gè)H3六邊形對(duì)象的圖形數(shù)據(jù)庫似乎是合理的，其中每個(gè)六邊形都是一個(gè)節(jié)點(diǎn)，它與鄰居、其父節(jié)點(diǎn)（分辨率減1）及其子節(jié)點(diǎn)（分辨率加1）邊連接。這正是開發(fā)人員所要做的。  

H3數(shù)據(jù)的InfiniteGraph模式  

六邊形類的初始模式非常簡(jiǎn)單。因此需要地址、分辨率、對(duì)父六邊形的引用，對(duì)子六邊形引用的一個(gè)列表，以及一個(gè)對(duì)相鄰六邊形參考的列表。

這給出以下信息：

這是一個(gè)很好的開始，但是為了有用，需要添加更多的信息。首先，為了支持更廣泛的地理查詢，需要添加字段，為六邊形的緯度和經(jīng)度提供最小值和最大值。最后，想將一些數(shù)據(jù)與六邊形對(duì)象相關(guān)聯(lián)，因此需要一個(gè)對(duì)某種數(shù)據(jù)對(duì)象的引用，現(xiàn)在稱之為HexagonData。

這給出以下定義：

這為構(gòu)建H3圖數(shù)據(jù)庫提供了強(qiáng)大的基礎(chǔ)。  

HexagonData 類  

擁有邊連接六邊形的圖形數(shù)據(jù)庫非常棒。它使能夠跨連接的六邊形執(zhí)行圖形導(dǎo)航查詢。但是，除非可以使用與六邊形相關(guān)聯(lián)的某種域數(shù)據(jù)來限定導(dǎo)航查詢，否則它并不是很有用。

一種方法是將域數(shù)據(jù)屬性放在Hexagon類定義中。更好的方法是將Hexagon對(duì)象與域數(shù)據(jù)分開。這就是HexagonData類發(fā)揮作用的地方。  

如下圖所示，HexagonData類只有一個(gè)屬性“itemMap”。itemMap屬性是一個(gè)NameToReferenceMap，它允許將字符串鍵映射到將存儲(chǔ)實(shí)際數(shù)據(jù)值的DataItem對(duì)象的引用。在這種情況下，鍵本質(zhì)上是數(shù)據(jù)字段名稱，關(guān)聯(lián)的字段值包含在引用的DataItem對(duì)象中。

HexagonData對(duì)象用作六邊形地圖對(duì)象和可能與其關(guān)聯(lián)的任何數(shù)據(jù)之間的間接層次?？梢园踩丶僭O(shè)六邊形對(duì)象在其初始創(chuàng)建后不會(huì)經(jīng)常更改。假設(shè)可能有大量數(shù)據(jù)被攝取并與每個(gè)六邊形相關(guān)聯(lián)，或者更具體地說，與每個(gè)HexagonData對(duì)象相關(guān)聯(lián)，也可能是安全的。  

將六邊形對(duì)象與HexagonData和DataItem對(duì)象分開的另一個(gè)優(yōu)點(diǎn)是對(duì)象放置?？梢詫⒘呅螌?duì)象放在聯(lián)合架構(gòu)的一個(gè)部分，然后將HexagonData和DataItem對(duì)象放在聯(lián)合架構(gòu)的完全不同的部分。在數(shù)百個(gè)甚至數(shù)千個(gè)線程從數(shù)據(jù)庫讀取和寫入數(shù)據(jù)庫的環(huán)境中，一個(gè)理想的放置策略將最大限度地減少鎖的爭(zhēng)用。  

DataItem類  

DataItem類是實(shí)際將值與六邊形關(guān)聯(lián)的旅程的最后一站。  

這是DataItem類的簡(jiǎn)化版本：

DataItem類有一個(gè)時(shí)間戳，用于指示值何時(shí)出現(xiàn)，然后有一個(gè)strValue String屬性用于存儲(chǔ)文本數(shù)據(jù)，還有一個(gè)realValue用于存儲(chǔ)十進(jìn)制值。在當(dāng)前設(shè)計(jì)中，DataItem對(duì)象中沒有任何信息可以指示值所代表的內(nèi)容。該信息源自HexagonData對(duì)象中itemMap指向DataItem對(duì)象的鍵。  

一圖勝千言…  

給定一個(gè)特定的六邊形對(duì)象，與其關(guān)聯(lián)的DataItems的“路徑”如下所示。  

在這個(gè)圖中，有一些由變量“hex”表示的六邊形。它有一個(gè)屬性“data”，它是對(duì)HexagonData對(duì)象的引用。該HexagonData對(duì)象有一個(gè)屬性：“itemMap”。itemMap有一個(gè)鍵值對(duì)，其鍵為“Population.density”，該鍵與對(duì)DataItem對(duì)象的引用相關(guān)聯(lián)，其中存儲(chǔ)了Hexagon的Population.density值hex。同一個(gè)HexagonData對(duì)象還有一個(gè)鍵“Climate.avgTemp”，它與存儲(chǔ)Climate.avgTemp值的DataItem相關(guān)聯(lián)。  

圖2：DataItems的路徑

查詢

InfiniteGraph支持幾種不同類型的查詢，這些查詢分為兩大類：FROM查詢和匹配（MATCH）查詢。 

（1）FROM查詢  

FROM查詢?cè)试S根據(jù)特定的類類型和可能的謂詞從對(duì)象返回?cái)?shù)據(jù)。例如，以下查詢返回所有Hexagon對(duì)象的每個(gè)屬性：

如果只想要所有Hexagon對(duì)象的地址屬性，可以修改return子句只返回地址：

可以添加一個(gè)謂詞來縮小結(jié)果集。

最后，可以使用點(diǎn)符號(hào)返回連接到每個(gè)符合WHERE子句的六邊形對(duì)象的DataItem對(duì)象。

（2）匹配查詢  

匹配查詢是可以真正利用圖片的強(qiáng)大功能的地方。

一個(gè)簡(jiǎn)單的匹配查詢?cè)试S找到到1度鄰居的所有路徑：

圖3：1度鄰居

如果不想要路徑，而是想要out degree=1鄰居中的地址，可以通過將返回的內(nèi)容從“p”修改為“h2.addresses” 來實(shí)現(xiàn)。

在這里，為目標(biāo)六邊形和返回的h2.address分配了一個(gè)變量h2。這將提供degree=1相鄰六邊形對(duì)象的從0到6個(gè)地址的列表。  

如果想獲得degree=2相鄰六邊形的地址，只需在查詢中間添加另一個(gè)邊緣節(jié)點(diǎn)子句：

圖4：2度鄰居

（3）查詢之間的路徑  

可以使用匹配查詢來查找兩個(gè)六邊形對(duì)象之間的路徑。在六邊形網(wǎng)格系統(tǒng)中，會(huì)有很多路徑，所以只對(duì)兩個(gè)六邊形之間的最短路徑感興趣。需要注意的是，設(shè)置希望查詢搜索距離的上限也很重要，否則查詢可能最終需要很長(zhǎng)時(shí)間才能運(yùn)行，因?yàn)樾枰幚泶罅繑?shù)據(jù)才能找到端點(diǎn)。這是通過設(shè)置一個(gè)變量但有界的邊緣限定符來完成的，例如“-[:neighbors*1..20]->”?！?1..20”表示在進(jìn)行搜索時(shí)從1跳到不超過20跳。  

給定兩個(gè)六邊形地址，可以通過將最短運(yùn)算符合并到匹配查詢中來找到它們之間的最短路徑，如下所示：

這是路徑之間查詢的最簡(jiǎn)單形式。

（4）數(shù)據(jù)符合匹配查詢

假設(shè)有一個(gè)六邊形，被要求在20度以內(nèi)的某個(gè)屬性內(nèi)找到平均大于72度的最近的六邊形。只需在目標(biāo)六邊形中添加一個(gè)限定符，就很容易做到這一點(diǎn)。

這個(gè)查詢將找到20度內(nèi)相鄰六邊形的最短路徑，其中“Climate.avgTemp”值大于72度。

（5）沿路徑限定的六邊形

最后一個(gè)查詢演示了如何限定路徑末端的頂點(diǎn)六邊形。如果想限定一條路徑上的所有六邊形怎么辦？具體來說，如果想找到一條從一個(gè)六邊形到另一個(gè)六邊形的路徑，并且該路徑上的每個(gè)六邊形都滿足某些條件，該怎么辦？為此，將采用稍微不同的方法，并使用DO查詢語言加權(quán)圖權(quán)重計(jì)算器運(yùn)算符。

權(quán)重計(jì)算器允許定義一組函數(shù)來根據(jù)某些標(biāo)準(zhǔn)計(jì)算邊的權(quán)重。如果有一張由道路連接的城市圖，可能會(huì)說道路是城市頂點(diǎn)之間的邊，并且每條邊的權(quán)重是每條道路的長(zhǎng)度。

圖5：加權(quán)邊

可以擴(kuò)展加權(quán)圖和查詢的概念以及之前討論的點(diǎn)符號(hào)，以找到兩個(gè)六邊形之間的最短路徑，其中每個(gè)六邊形沿著路徑滿足某些標(biāo)準(zhǔn)。在這個(gè)示例中，希望找到從定義的原點(diǎn)六邊形到定義的目標(biāo)六邊形的六邊形路徑，其中沿路徑的每個(gè)六邊形的Climate.avgTemp大于72度。  

在六邊形類定義中，“鄰居”邊沒有屬性，這很好。將通過檢查每個(gè)鄰居邊參考遠(yuǎn)端的六邊形來推斷邊的權(quán)重。

希望通向符合條件的六邊形的每條邊都具有較低的邊權(quán)重，與其相反，希望通向不符合條件的六邊形的每條邊都具有非常高的邊權(quán)重。以下是如何使用權(quán)重計(jì)算器實(shí)現(xiàn)的：

這個(gè)權(quán)重計(jì)算器定義了兩個(gè)邊匹配模式。第一個(gè)匹配源自六邊形并導(dǎo)致Climate.avgTemp >72.00的六邊形的邊。對(duì)于符合這些條件的邊，權(quán)重計(jì)算器將分配1的權(quán)重。  

第二個(gè)邊匹配模式將匹配源自六邊形的邊緣并導(dǎo)致Climate.avgTemp<=72.00的六邊形。對(duì)于與此模式匹配的任何邊緣，將分配1000的權(quán)重。  

使用這個(gè)權(quán)重計(jì)算器，查詢就變成了：

這一查詢將返回權(quán)重最低的路徑（最短，因?yàn)榉蠗l件的邊的權(quán)重為1）并將取消權(quán)重（長(zhǎng)度）超過21.0的任何路徑，因此如果存在則返回結(jié)果路徑。  

權(quán)重計(jì)算器的真正優(yōu)點(diǎn)在于可以更改，甚至編寫新的權(quán)重計(jì)算器來限定相同圖形數(shù)據(jù)上的邊，而無需更改節(jié)點(diǎn)和邊上的數(shù)據(jù)。權(quán)重計(jì)算器是動(dòng)態(tài)的，它從任何可用節(jié)點(diǎn)和邊數(shù)據(jù)計(jì)算權(quán)重，這些數(shù)據(jù)可以從源節(jié)點(diǎn)、邊或目標(biāo)節(jié)點(diǎn)訪問。在這個(gè)例子中，創(chuàng)建了兩個(gè)邊權(quán)重函數(shù)，它們使用連接到節(jié)點(diǎn)的對(duì)象中的信息。

結(jié)論

H3分層六邊形索引方案是組織、管理和與地理數(shù)據(jù)交互的極好方式。創(chuàng)建InfiniteGraph圖形數(shù)據(jù)庫六邊形模型提供了一個(gè)很好的基礎(chǔ)，可以在這個(gè)基礎(chǔ)上捕獲其他數(shù)據(jù)，并將其與六邊形相關(guān)聯(lián)。這一切都構(gòu)建了一個(gè)地理圖形分析平臺(tái)，該平臺(tái)可用于對(duì)大量數(shù)據(jù)執(zhí)行高級(jí)和復(fù)雜的數(shù)據(jù)分析。

原文標(biāo)題：??Massively Scalable Geographic Graph Analytics: InfiniteGraph and Uber’s Hexagonal Hierarchical Spatial Index???，作者：Daniel Hall?