[[258183]]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在分布式系統(tǒng)中使用廣播并不是個好主意。谷歌大牛 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)中很好地解釋了這個問題。查詢的總延遲總是大于最慢組件的延遲。單臺機器的一丁點延遲會隨著機器數(shù)量的增多而戲劇性地增加查詢總延遲。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

英文原文：

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