[[258183]]

本文由微信公眾號 「AI 前線」原創（ID：ai-front），未經授權不得轉載。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

首先是一個搜索項目，它提供了一種方法，可用于高度準確地分辨哪些單詞應該合在一起。例如，對于 [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]。

我使用了谷歌的搜索索引系統，為每個三元組分配了一個 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 的領導層也很支持它。即使是圖服務部分也提供了較好的性能和功能。我把它叫作知識引擎(搜索引擎的升級)，但谷歌管理層(包括我的經理)對此并不感興趣。后來，有人告訴我應該去找誰溝通這件事，于是我才有機會向搜索方面的一位高級負責人展示它。

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

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

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

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

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

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

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

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

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

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

在分布式系統中使用廣播并不是個好主意。谷歌大牛 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。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

英文原文：

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