前員工揭內幕：10年了，為何Google還搞不定知識圖譜？

作者｜Manish Rai Jain

譯者｜阿拉丁

編輯｜Debra

AI 前線導讀：最近，前Google開發者、現 Dgraph 創始人 Manish Rai Jain 撰文揭秘了Google內部在知識圖譜領域的探索和發展。他以一個開發和技術前驅者的視角論述了「為什麼Google需要一個知識圖譜系統」，並詳細披露了知識圖譜在Google的探索嘗試的歷程。雖然由於種種原因，他當時的知識圖譜項目最終被放棄，但整個發展探索歷程不失為一個非常棒的知識圖譜技術學習材料和項目管理經典案例。AI 前線對這篇文章進行了編譯，希望能對大家有所幫助。更多乾貨內容請關注微信公眾號「AI 前線」（ID：ai-front）

當我向別人解釋我們在 Dgraph 實驗室所做的東西時，經常會有人問我是不是曾經在 Facebook 工作過，或者我們正在做的東西是否受到 Facebook 的啟發。很多人都知道 Facebook 在社交圖服務方面做了大量工作，因為他們發表了多篇關於如何構建圖基礎設施的文章。

在說到Google時，一般僅限於知識圖譜服務，但卻沒有人提到過其內部基礎設施是怎麼回事。其實Google有專門用於提供知識圖譜的系統。事實上，我們（在Google的時候）在圖服務系統方面也做了大量的工作。早在 2010 年，我就冒險進行了兩次嘗試，看看可以做出些什麼東西。

Google需要構建一個圖服務系統，不僅可以處理知識圖數據中的複雜關係，還可以處理所有可以訪問結構化數據的 OneBox。服務系統需要遍歷事實數據，並具備足夠高的吞吐量和足夠低的延遲，以應對大量的 Web 搜尋。但沒有現成可用的系統或數據庫能夠同時滿足這三個要求。

我已經回答了為什麼Google需要構建一個圖服務系統，在本文的其餘部分，我將帶你回顧我們構建圖服務系統的整個旅程。

我是怎麼知道這些的？

我先自我介紹一下，2006 年到 2013 年期間，我在Google工作。先是實習生，然後是 Web 搜尋基礎設施的軟件工程師。2010 年，Google收購了 Metaweb，那時我的團隊剛剛推出了 Caffeine。我想做一些與眾不同的東西，於是開始與 Metaweb 的人（在舊金山）合作。我的目標是弄清楚如何使用知識圖譜來改進 Web 搜尋。

Metaweb 的故事

之前已經說過，Google在 2010 年收購了 Metaweb。Metaweb 已經使用多種技術構建了一個高質量的知識圖譜，包括爬取和解析維基百科。所有這些都是由他們內部構建的一個圖數據庫驅動的，這個數據庫叫作 Graphd——一個圖守護程序（現在已經發布在 GitHub 上：https://github.com/google/graphd）。

Graphd 有一些非常典型的屬性。和守護程序一樣，它運行在單台服務器上，所有數據都保存在內存中。Freebase 網站讓 Graphd 不堪重負，在被收購之後，Google面臨的一個挑戰是如何繼續經營 Freebase。

Google在商用硬件和分布式軟件領域建立了一個帝國。單台服務器數據庫永遠無法支撐與搜尋相關的爬取、索引和服務工作負載。Google先是推出了 SSTable，然後是 Bigtable，可以橫向擴展到數百甚至數千台機器，為數 PB 數據提供處理能力。他們使用 Borg（K8s 的前身）來配置機器，使用 Stubby（gRPC 的前身）進行通信，通過 Borg 名稱服務解析 IP 地址（BNS，已集成到 K8s 中），並將數據存儲在Google文件系統（GFS）上。進程可能會死亡，機器可能會崩潰，但系統會一直運轉。

Graphd 當時就處在這樣的環境中。使用單個數據庫為運行在單台服務器上的網站提供服務，這種想法與Google（包括我自己）的風格格格不入。特別是，Graphd 需要 64GB 或更多的內存才能運行。如果你認為這樣的內存要求很搞笑，那麼請注意，那是在 2010 年。當時大多數Google服務器的最大內存為 32GB，所以Google必須購買配備足夠多內存的特殊機器來支持 Graphd。

替換 Graphd

有關替換或重寫 Graphd 並讓它支持分布式的想法開始冒了出來，但這對於圖數據庫來說是一件非常困難的事情。它們不像鍵值數據庫那樣，可以將一大塊數據移動到另一台服務器上，在查詢時提供鍵就可以了。圖數據庫承諾的是高效的連接和遍歷，需要以特定的方式來做到。

其中的一個想法是使用一個叫作 MindMeld（IIRC）的項目。這個項目承若通過網路硬件可以更快地訪問另一台服務器內存。這應該比正常的 RPC 要快，快到足以偽復制內存數據庫所需的直接內存訪問。但這個想法並沒有走得太遠。

另一個想法（實際上是一個項目）是構建一個真正的分布式圖服務系統，不僅可以取代 Graphd，還可以為將來的所有知識提供服務。它就是 Dgraph——一種分布式圖守護程序。

Dgraph 實驗室和開源項目 Dgraph 的命名就是從Google的這個項目開始的。

當我在本文中提到 Dgraph 時，指的是Google的內部項目，而不是我們後來構建的開源項目。

Cerebro 的故事：一個知識引擎

雖然我知道 Dgraph 的目標是要取代 Graphd，但我的目標卻是做出一些東西來改進 Web 搜尋。我在 Metaweb 找到了一位研究工程師 DH，Cubed（https://blog.dgraph.io/refs/freebase-cubed.pdf）就是他開發的。

Google紐約辦公室的一些工程師開發了 Squared（https://en.wikipedia.org/wiki/Google_Squared）。DH 則更進一步，開發了 Cubed。雖然 Squared 沒有什麼用，但 Cubed 卻令人印象深刻。我開始想如何也在Google開發一個這樣的東西，畢竟Google已經有一些現成的東西可以利用。

首先是一個搜尋項目，它提供了一種方法，可用於高度準確地分辨哪些單詞應該合在一起。例如，對於 [tom hanks movies] 這樣的短語，它會告訴你 [tom] 和 [hanks] 應該合在一起。同樣，在 [san francisco weather] 這個短語中，[san] 和 [francisco] 應該合在一起。對於人類而言，這些都是顯而易見的事情，但對機器來說可不是這麼回事。

第二個是理解語法。在查詢 [books by french authors] 時，機器可以將其解釋成由 [french authors] 所寫的 [books]（即法國作家所著的書籍）。但它也可以被解釋成 [authors] 所寫的 [french books]（即作家所著的法語書籍）。我使用了史丹佛的詞性（POS）標記器來更好地理解語法，並構建了語法樹。

第三個是理解實體。[french] 可以指很多東西，它可以是指國家（地區）、國籍（法國人）、菜肴（指食物）或語言。我使用了另一個項目來獲取單詞或短語所對應的實體列表。

第四個是理解實體之間的關係。現在我已經知道如何將單詞關聯成短語、短語的執行順序，即語法，以及它們對應的實體，我還需要一種方法來找到這些實體之間的關係，以便創建機器解釋。例如，對於查詢 [books by french authors]，POS 會告訴我們，它指的是 [french authors] 所著的 [books]。我們有一些 [french] 的實體和 [authors] 的實體，算法需要確定如何連接它們。它們可以通過出生地連接在一起，即出生在法國的作家（但可能使用英文寫作），或者是法國藉的作家，或者說法語或使用法語寫作（但可能與法國無關）的作家，或者只是喜歡法國美食的作家。

基於搜尋索引的圖系統

為了確定某些實體是否是連接在一起的，以及是如何連接在一起的，我需要一個圖系統。知識圖譜數據使用了三元組的格式，即每個事實通過三個部分來表示，主語（實體）、謂詞（關係）和賓語（另一個實體）。查詢必須是 [S P]→[O]、[P O]→[S]，有時候是 [S O]→[P]。

我使用了Google的搜尋索引系統，為每個三元組分配了一個 docid，並構建了三個索引，分別為 S、P 和 O。另外，索引允許附帶附件，所以我附上了每個實體的類型信息。

我構建了這個圖服務系統，知道它有連接深度問題（下面會解釋），並且不適用於複雜的圖查詢。事實上，當 Metaweb 團隊的某個人要求我開放系統訪問時，被我拒絕了。

現在，為了確定關係，我會執行一些查詢，看看會產生哪些結果。[french] 和 [author] 會產生什麼結果嗎？選擇這些結果，並看看它們如何與 [books] 連接在一起。這樣會生成多個機器解釋。例如，當你查詢 [tom hanks movies] 時，它會生成 [movies directed by tom hanks]、[movies starring tom hanks]、[movies produced by tom hanks] 這樣的解釋，並自動拒絕像 [movies named tom hanks] 這樣的解釋。

對於每一個解釋，它將生成一個結果列表——圖中的有效實體——並且還將返回實體的類型（存在於附件中）。這個功能非常強大，因為在了解了結果的類型後，就可以進行過濾、排序或進一步擴展。對於電影類型的結果，你可以按照發行年份、電影的長度（短片、長片）、語言、獲獎情況等對電影進行排序。

這個項目看起來很智能，我們（DH 作為這個項目的知識圖譜專家）將它叫作 Cerebro，與《X 戰警》中出現的設備同名。

Cerebro 經常會展示出一些人們最初沒有搜尋過的非常有趣的事實。例如，如果你搜尋 [us presidents]，Cerebro 知道總統是人類，而人類會有身高，你就可以按照身高對總統進行排序，然後會告訴你 Abraham Lincoln 是美國身高最高的總統。還可以通過國籍來過濾搜尋結果。在這個例子中，它顯示的是美國和英國，因為美國有一位英國人總統——George Washington。（免責聲明：這個結果是基於當時的 KG 狀態，所以不保證這些結果的正確性。）

藍色鏈接與知識圖譜

Cerebro 其實是有可能真正理解用戶的查詢的。如果圖中有數據，就可以為查詢生成機器解釋和結果列表，並根據對結果的理解進行進一步的探索。如上所述，在知道了正在處理的是電影、人類或書籍之後，就可以啟用特定的過濾和排序功能。還可以遍歷圖的邊來顯示連接數據，從 [us presidents] 到 [schools they went to]，或者 [children they fathered]。DH 在另一個叫作 Parallax（https://vimeo.com/1513562）的項目中演示了從一個結果列表跳轉到另一個結果列表的能力。

Cerebro 令人印象深刻，Metaweb 的主管層也很支持它。即使是圖服務部分也提供了較好的性能和功能。我把它叫作知識引擎（搜尋引擎的升級），但Google管理層（包括我的經理）對此並不感興趣。後來，有人告訴我應該去找誰溝通這件事，於是我才有機會向搜尋方面的一位高級負責人展示它。

但得到的回應並不是我所希望的那樣。這位負責人向我展示了使用Google搜尋 [books by french authors] 的結果，其中顯示了十個藍色鏈接，並堅持說Google可以做同樣的事情。此外，他們不希望網站的流量被搶走，因為那樣的話這些網站的所有者肯定會生氣。

如果你認為他是對的，那麼請想一下：Google搜尋其實並不能真正理解用戶搜尋的是什麼。它只會在正確的相對位置查找正確的關鍵字，並對頁面進行排名。盡管它是一個極其複雜的系統，但仍然不能真正理解搜尋或搜尋結果意味著什麼。最後，用戶還需要自己查看結果，並從中解析和提取他們需要的信息，並進行進一步的搜尋，然後將完整的結果組合在一起。

例如，對於 [books by french authors] 這個搜尋，用戶首先需要對結果列表進行組合，而這些結果可能不會出現在同一個頁面中。然後按照出版年份對這些書籍進行排序，或者按照出版社等條件進行過濾——所有這些都需要進行大量的鏈接跟蹤、進一步的搜尋和手動聚合。Cerebro 有可能可以減少這些工作量，讓用戶交互變得簡單而完美。

然而，這在當時是一種典型的獲取知識的方法。管理層不確定知識圖譜是否真的有用，或者不確定如何將其用在搜尋中。對於一個已經通過向用戶提供大量超鏈接而取得成功的企業來說，這種獲取知識的新途徑並不容易理解。

在與管理層磨合了一年之後，我沒有興趣再繼續下去了。2011 年 6 月，Google上海辦公室的一位經理找到我，我把項目交給了他。他為這個項目組建了一個由 15 名工程師組成的團隊。我在上海呆了一個星期，把相關的東西都移交給了這個團隊的工程師。DH 也參與了這個項目，並長期指導團隊。

連接深度問題

我為 Cerebro 開發的圖服務系統存在連接深度問題。當一個查詢的後續部分需要用到前臉部分的結果時，就需要執行連接。典型的連接通常涉及到 SELECT 操作，即對通用數據集進行過濾，獲得某些結果，然後使用這些結果來過濾數據集的另一部分。我將用一個例子來說明。

假設你想知道 [people in SF who eat sushi]，而且人們已經分享了他們的數據，包括誰住在哪個城市以及他們喜歡吃哪些食物的信息。

上面的查詢是一個單級連接。如果數據庫外部的應用程序正在執行這個連接，它將先執行一個查詢，然後再執行多個查詢（每個結果一個查詢），找出每個人都吃些什麼，然後挑選出吃壽司的人。

第二步存在扇出（fan-out）問題。如果第一步有一百萬個結果（基於舊金山人口），那麼第二步需要將每個結果放入查詢中，找出他們的飲食習慣，然後進行過濾。

分布式系統工程師通常會通過廣播來解決這個問題。他們根據分片函數將結果分成多個批次，然後查詢集群中的每一台服務器。他們可以通過這種方式做到連接，但會導致嚴重的查詢延遲。

在分布式系統中使用廣播並不是個好主意。Google大牛 Jeff Dean 在他的「Achieving Rapid Response Times in Large Online Services」演講（視頻：https://www.youtube.com/watch?v=1-3Ahy7Fxsc，幻燈片：https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44875.pdf）中很好地解釋了這個問題。查詢的總延遲總是大於最慢組件的延遲。單台機器的一丁點延遲會隨著機器數量的增多而戲劇性地增加查詢總延遲。

想像一下，有一台服務器，它的 50 百分位延遲為 1 毫秒，99 百分位延遲為 1 秒。如果查詢只涉及一台服務器，那麼只有 1％的請求會占用一秒鐘時間。但如果查詢涉及 100 台服務器，那麼就會有 63％的請求占用一秒鐘時間。

因此，廣播會給查詢延遲帶來不利的影響。如果需要進行兩次、三次或更多次的連接，對於實時（OLTP）執行來說就會顯得很慢。

大多數非原生圖數據庫都存在這種高扇出廣播問題，包括 Janus Graph、Twitter 的 FlockDB 和 Facebook 的 TAO。

分布式連接是一個大難題。現有的原生圖數據庫通過將通用數據集保存在一台機器（獨立數據庫）上，並在連接時不訪問其他服務器來避免這個問題，如 Neo4j。

Dgraph：任意深度連接

在結束 Cerebro 之後，我擁有了構建圖服務系統的經驗。隨後，我加入了 Dgraph 項目，成為該項目的三位技術主管之一。Dgraph 的設計理念非常新穎，並解決了連接深度問題。

Dgraph 以一種非常獨特的方式對圖數據進行分片，可以在單台機器上執行連接。回到 SPO 這個問題上，Dgraph 的每個實例都將保存與該實例中的每個謂詞相對應的所有主語和賓語。Dgraph 實例將保存多個謂詞和完整的謂語。

這樣就可以執行任意深度的連接，同時避免了扇出廣播問題。以 [people in SF who eat sushi] 為例，不管集群大小是怎樣的，這個查詢最多需要兩次網路調用。第一次調用會找到所有住在舊金山的人，第二次調用會將這個名單與所有吃壽司的人進行交集操作。然後我們可以添加更多約束或擴展，每個步驟仍然會涉及最多一次網路調用。

這導致了單台服務器上的謂語會變得非常大，不過可以通過進一步拆分謂語服務器來解決這個問題。但是，在最極端的情況下，即所有數據只對應一個謂語，那麼基於整個集群拆分謂語是一種最糟糕的行為。但在其他情況下，基於謂語對數據進行分片的設計可以在實際系統中做到更低的查詢延遲。

分片並不是 Dgraph 的唯一創新。所有的賓語都被分配了一個整型 ID，然後經過排序，保存在倒排列表中，可以與其他倒排列表進行快速的交集操作。這樣可以加快連接期間的過濾、查找公共引用等操作。這里還使用了Google Web 服務系統的一些想法。

通過 Plasma 聯合 OneBoxe

Google的 Dgraph 並不是一個數據庫，而是一個服務系統，相當於Google的 Web 搜尋服務系統。此外，它需要對實時更新做出響應。作為一個實時更新的服務系統，它需要一個實時的圖索引系統。因為之前參與過 Caffeine（https://googleblog.blogspot.com/2010/06/our-new-search-index-caffeine.html）的工作，所以我在實時增量索引系統方面也擁有了很多經驗。

後來我又啟動了一個新項目，基於這個圖索引系統將Google所有的 OneBox 聯合在一起，包括天氣、航班、事件，等等。你可能不知道 OneBox 是什麼，但你肯定見過它們。OneBox 是單獨的顯示框，會在運行某些類型的搜尋時出現，Google可以在這些顯示框中顯示更多的信息。

在開始這個項目之前，每個 OneBox 由獨立的後端提供支持，並由不同的團隊負責維護。它們有一組豐富的結構化數據，但顯示框之間並不會共享這些數據。維護這些後端不僅涉及大量的工作，而且因為缺乏知識共享，限制了Google能夠響應的查詢類型。

例如，[events in SF] 可以顯示事件，[weather in SF] 可以顯示天氣，但如果 [events in SF] 知道當時在下雨，並且知道事件是在室內還是在室外進行，那麼它就可以根據天氣（如果下暴雨，看電影或聽交響樂可能是最好的選擇）對事件進行過濾（或排序）。

在 Metaweb 團隊的幫助下，我們將所有數據轉換為 SPO 格式，並在一個系統中對其進行索引。我將這個系統命名為 Plasma，一個用於 Dgraph 的實時圖索引系統。

管理層變動

與 Cerebro 一樣，Plasma 也是一個缺乏資金支持的項目，但仍在繼續成長。最後，當管理層意識到 OneBoxe 即將使用這個項目時，他們需要找到「合適的人」負責這方面的工作。在這場政治遊戲中，我們經歷了三次管理層變動，但他們都沒有這方面的經驗。

在這次管理層變動過程中，支持 Spanner（一個全球分布式 SQL 數據庫，需要 GPS 時鐘來確保全球一致性）的管理層認為 Dgraph 過於複雜。

最後，Dgraph 項目被取消了，不過 Plasma 幸免於難。一個新團隊接管了這個項目，這個團隊的負責人直接向首席執行官匯報。這個新團隊（他們其實對與圖相關的問題缺乏了解）決定構建一個基於Google現有搜尋索引的服務系統（就像我為 Cerebro 所做的那樣）。我建議使用我為 Cerebro 開發的那個系統，但被拒絕了。我修改了 Plasma，讓它爬取並將每個知識主題擴展出幾個級別，這個系統就可以將其視為一個 Web 文檔。他們稱之為 TS（這只是個縮寫）。

這意味著新的服務系統將無法執行深度連接。我看到很多公司的工程師們在一開始就錯誤地認為「圖實際上是一個很簡單的問題，可以通過在另一個系統之上構建一個層來解決」。

幾個月之後，也就是 2013 年 5 月，我離開了Google，那個時候我在 Dgraph/Plasma 項目上大約已經工作了兩年時間。

後面的故事

• 幾年後，「Web 搜尋基礎設施」被重命為「Web 搜尋和知識圖譜基礎設施」，之前我向他演示 Cerebro 的那個人負責主管這方面的工作。他們打算使用知識圖譜替代藍色鏈接——盡可能為用戶查詢提供最直接的答案。

• 當上海的 Cerebro 團隊即將在生產環境中部署這個項目時，項目卻被Google紐約辦公室搶走了。最後，它改頭換面成了「Knowledge Strip」。如果你搜尋 [tom hanks movies]，會在頂部看到它。自首次發布以來，它有了一些改進，但仍然無法達到 Cerebro 能夠提供的過濾和排序水平。

• 參與 Dgraph 工作的三位技術主管（包括我）最終都離開了Google。據我所知，其他兩位主管現在正在微軟和 LinkedIn 工作。

• 我獲得了兩次晉升，如果算上當時我以高級軟件工程師的身份離開Google，總共是三次。

• 當前版本的 TS 實際上非常接近 Cerebro 的設計，主語、謂語和賓語都有一個索引。因此，它仍然存在連接深度問題。

• 此後，Plasma 被重寫和改名，但仍然是一個支持 TS 的實時圖索引系統。它們繼續托管著Google的所有結構化數據，包括知識圖譜。

• Google在深度連接方面的無能為力在很多地方都可以看出來。首先，我們仍然沒有看到 OneBoxe 之間的數據聯合：[cities by most rain in asia] 並不會生成城市列表，盡管天氣和 KG 數據是可用的。[events in SF] 無法根據天氣進行過濾，[US presidents] 的結果不能進行進一步的排序、過濾或擴展。我懷疑這也是他們停止使用 Freebase 的原因之一。

Dgraph：鳳凰涅槃

離開Google兩年之後，我決定重新開始 Dgraph（https://github.com/dgraph-io/dgraph）。在Google之外，我看到了與當初類似的情況。這個領域有很多不成熟的自定義解決方案，他們匆匆茫茫地在關係型數據庫或 NoSQL 數據庫之上添加了一個層，或者將其作為多模型數據庫的眾多功能之一。如果存在原生解決方案，會遇到可伸縮性問題。

在我看來，沒有人能夠在高性能和可伸縮設計方面一路走下去。構建一個具備水平可伸縮性、低延遲且可進行任意深度連接的圖數據庫是一件非常困難的事情。我希望我們在構建 Dgraph 這件事情上不會走錯路。

在過去的三年里，除了我自己的經驗，Dgraph 團隊還在設計中加入了大量原創研究，開發出了這款無與倫比的圖數據庫。其他公司可以選擇這個強大、可伸縮且高性能的解決方案，而不是另一個不成熟的解決方案。

英文原文：

https://blog.dgraph.io/post/why-google-needed-graph-serving-system/

今日薦文

點擊下方圖片即可閱讀

圖神經網路將成AI下一拐點！MIT史丹佛一文綜述GNN到底有多強