谷歌知識圖譜系統發展內幕：從MetaWeb到Cerebro 直到放棄
image
前谷歌前開發者Dgraph創始人Manish Rai Jain撰寫了關於谷歌內部在知識圖譜領域的探索和發展。他以一個開發和技術前驅者論述了"為什麼谷歌需要一個知識圖譜系統"，並且知識圖譜在谷歌的探索嘗試的歷程，雖然由於種種原因他們的專案最後被放棄了，但是整個發展探索的歷程是一個非常棒的知識圖譜技術學習的材料和專案管理經典案例，所以蟲蟲引用過來和一起學習，“它山之石，可以攻玉”希望能對大家有所幫助。
背景
谷歌知識圖譜系統的建立源於2010年，並於2012年在搜尋引擎中提供了改功能。為了實現該功能，需要構建一個圖服務系統，不僅可以處理知識圖資料中的複雜關係，還要連線互動OneBoxes，處理和訪問所有結構化資料。該圖服務系統需要能遍歷資料，具有足夠高的吞吐量和足夠低的延遲，可以支援巨量的網路搜尋查詢。當時業界還沒有可用的系統或資料庫能夠滿足這三個需求，所以谷歌內部就有圖譜系統的探索。
Metaweb的故事
谷歌在2010年收購了Metaweb。Metaweb使用多種技術構建了一個高質量的知識圖譜，包括抓取和解析維基百科，以及使用類似維基百科的多來源資料通過Freebas網站提供服務。所有這些功能都由他們內部構建的圖形資料庫驅動的，該資料庫名為Graphd，是一個圖形守護程式。谷歌已經在GitHub上開源（地址為 github：/google/graphd）。
Graphd有一些非常典型的屬性。像一般守護程序一樣，它在一臺伺服器上執行，所有資料都放在記憶體中。整個Freebase網站都都基於Graphd。
谷歌基於一般商品級別的硬體和分散式軟體構建了搜尋帝國。單個伺服器資料庫永遠滿足不了其巨大的蜘蛛爬蟲，索引和搜尋服務。為此谷歌構建了SSTable，進化到了Bigtable，它可以橫向擴充套件到數百或數千臺伺服器，協同執行PB級的資料。還構建了Borg（K8s的前驅）分配機器，使用Stubby（gRPC前驅）進行通訊，通過Borg的名稱服務解析IP地址（BNS，K8s元件之一），資料儲存在Google檔案系統GFS上（Hadoop FS）。基於分散式架構，在谷歌體系中" 程序會死，機器會崩，服務永不down "。
所以收購後Graphd必須面對這樣架構文化，服務於在單個伺服器上執行的資料庫的想法與Google架構大相徑庭。而且Graphd需要至少64GB的記憶體才能執行，而當時谷歌大多數伺服器的最大記憶體為32GB。為了滿足Graphd的需要，谷歌就要額外採購。
基於上面提到了問題，重構Graphd以分散式方式執行的被提上議題。但是圖系統不同於一般的鍵值資料庫，需要大量的連線和遍歷操作，需要以特定方式構建軟體。
一個選擇是使用名為MindMeld（IIRC）的專案。利用該專案可以通過網路可以更快地訪問另一臺伺服器的記憶體。據推測，這會比正常的RPC更快，足以快速複製記憶體資料庫所需的虛擬複製直接進行異機記憶體訪問。
實際上採納的是另一個方案構建一個真正的分散式圖服務系統。不僅可以取代Graphd，還可以為將來的所有知識工作服務。該專案被命名為Dgraph，分散式圖，graph守護程序。
Cerebro：一個知識引擎
無意中構建了圖服務系統。
Manish當時在谷歌的任務是改進搜尋引擎。他和Metaweb的工程師DH（建立了Cubed），基於Cubed和Squared打算重建一個系統用於改進搜尋引擎。
首先是一個搜尋專案，它提供了一種方法，可以實現高度準確地理解哪些詞可以合併起來。比如，對於[tom hanks movies]這樣的短語時，它可以判定 [tom]和[hanks]屬於一個詞。同樣，從[san francisco weather]，[san]和[francisco]應該合併到一起。對於人類而言，這是顯而易見的。
第二部分是理解語法。當查詢[books by french authors]時，機器可以其解析為[books]和[french authors]（即法國人寫的書）。但它也可以解釋為[french books]和[authors]（即任何作者的法語書籍）。系統使用了斯坦福的Part-Of-Speech（POS）標記器來更好地理解語法並構建一棵樹。
第三部分是理解實體。 [french]可能意味著許多事情。它可以是國家（地區），國籍（指法國人），菜餚（指食物）或語言。可以使用上一部分獲取的單詞或短語可以對到的實體列表。
第四部分是瞭解實體之間的關係。現在系統可以將單詞關聯到短語，短語應該執行的順序，即語法，以及它們可以對應的實體，需要一種方法來找到這些實體之間的關係以建立機器解釋。例如，一個查詢說[books by french authors]和POS的結果[french authors]的[books]。有多個[french]的實體，也有多個[authors]的實體，演算法需要確定它們的連線方式。例如可以通過出生地連線起來：即出生在法國的作者（但可能是英文寫作）；或者是法國人作者；或者說寫法語（但可能與法國，國家無關）的作者；或者只喜歡法國美食的作家。
基於搜尋索引的圖形系統
為了確定實體是連線，並且怎麼連線，需要用到一個圖系統。 Graphd需要擴充套件到Google分散式搜尋架構，而Manish理解谷歌搜尋。知識圖資料以三元組格式化，即每個事實由三個部分表示，主題（實體），謂詞（關係）和物件（另一個實體）。查詢必須來自[S P]→[O]，或者[P O]→[S]，偶爾是[S O]→[P]。
image
Manish使用Google的搜尋索引系統，為每個三元組分配了一個docid，並構建了三個索引，分別為S，P和O。另外，索引允許附件，所以附上了每個實體的型別資訊（即演員，書，人等等）。
建立的這個圖服務系統，有連線深度問題（如下所述），並且不適合任何複雜的圖形查詢。
為了確定關係，需要查詢每個產生的結果。 [french]和[author]會產生結果嗎？選擇這些結果並檢視它們與[books]的連線方式，等等。這需要查詢的多個結果。例如，當你執行[tom hanks movies]時，它會產生如[movies directed by tom hanks]，[movies starring tom hanks]，[movies produced by tom hanks]；類似的結果，並自動拒絕諸如[movies named tom hanks]的查詢。
image
對於每個查詢，它將生成結果列表，圖中的有效實體。 並且還將返回其型別（存在於附件中）。這非常強大，因為了解結果的型別允許過濾，排序或進一步擴充套件等功能。對於電影結果，你可以按照發行年份，電影的長度（短片，長片），語言，獲獎等等對電影進行分類。這個系統被命名為Cerebro。
Cerebro經常會揭示到人們最初沒有搜尋過的非常有趣的一些事實。比如當你查詢[us presidents]時，Cerebro會明白總統是人類，人類有高度。因此，它允許你按高度對總統進行分類，並表明亞伯拉罕林肯是美國最高的總統。它還可以讓人們按國籍過濾。在這種情況下，它顯示了美國和英國的名單，因為美國有一位英國總統，即喬治華盛頓。
Cerebro可以真正理解使用者查詢。如相簿中有資料，就可以生成查詢，得到結果列表並解析結果還支援進一步探索。如上面介紹，一旦他了解到你正在處理電影或人類或書籍等，就可以啟用特定的過濾和排序功能。也可以進行邊緣遍歷來顯示連線到的資料，從[us presidents]到[schools they went to]，或者[children they fathered]。Cerebro非常令人印象深刻，Metaweb的領導層也支援它。即使是服務於其中一部分知識引擎（從搜尋引擎升級）的圖也具有高效能和功能性。
連線深度的問題
Cerebro構建的圖服務系統存在一個連線深度的問題。當需要查詢的已有部分的結果集來執行其後續部分時，執行連線操作。典型的連線涉及一些SELECT，即來自通用資料集的某些結果中過濾，然後使用這些結果來過濾資料集的另一部分。例如，你想知道[people in SF who eat sushi]。資料通過人分類，並且有關於誰住在哪個城市以及他們吃什麼食物的資訊。
以上查詢是單級連線。如果資料庫外部的應用程式正在執行此操作，它將執行一個查詢來執行第一步。然後執行多個查詢（每個結果一個查詢），找出每個人吃什麼，只挑選吃壽司的人。
第二步是出現fan-out問題。如果第一步有一百萬個結果（舊金山人口），那麼第二步需要將每個結果放入查詢中，檢索他們的飲食習慣，然後是過濾。
image
分散式系統工程師通常通過廣播來解決這個問題。通過將批量處理結果與其分片功能相對應，並對群集中的每個伺服器進行查詢。這會返回一個連線集，但會導致查詢延遲問題。
在分散式系統中的廣播很耗時。對此，谷歌Jeff Dean的"在大型線上服務中實現快速響應時間"報告中最好地解釋過這個問題。查詢的總延遲總是大於最慢部件的延遲。單個機器上的小問題會導致整個系統的延遲，每次查詢涉及的伺服器越多，這種由個體導致的延遲會越多。
試想一個伺服器，其50% ile延遲為1ms，但99%ile延遲為1s。如果查詢僅有一個伺服器，則只有1%的請求會佔用一秒。但如果查詢涉及其中的100臺伺服器，則63%的請求會佔用一秒。
因此，執行一個廣播查詢的對於查詢效能非常不利。考慮是否需要進行兩次，三次或更多次連線操作的情況。對於實時（OLTP）執行，它們會變得太慢。大多數非原生圖資料庫共享這種高fan-out廣播問題，包括JanusGraph，Twitter的FlockDB和Facebook的TAO。
分散式連線操作是一個難題。現有的本機圖資料庫通過將通用資料集保持在一個機器（獨立資料庫）內，並且在不涉及其他伺服器的情況下進行所有連線來避免這個問題。例如，Neo4j。
image
深入Dgraph：任意深度連線引擎
在Cerbro進化後變成了Dgraph專案，其設計中引入了很多新的概念，並解決了連線深度的問題。特別的，Dgraph以一種方式對圖資料進行分片，其中每個連線可以完全由一臺機器執行。回到主題—謂詞—物件（SPO），Dgraph的每個例項將儲存與該例項中的每個謂詞相對應的所有主題和物件。多個謂詞儲存在例項上，每個謂詞都被整個儲存。這允許查詢執行任意深度連線，同時避免fan-out廣播問題。對查詢[people in SF who eat sushi]，資料庫內最多發起兩次網路呼叫，而於管群集的大小無關。第一個呼叫會找到所有住在SF的人。第二個呼叫會發送這個人列表並與所有吃壽司的人做交集。並且還可以新增更多約束或擴充套件，每個步驟頂多會涉及一個網路呼叫。
image
但是這樣一來，就需要在單個伺服器上儲存的巨大的謂詞。解決方法是隨著大小的增長在兩個或更多個例項之間進行謂詞分割。即便是如此，整個叢集中的單個謂詞拆分也只會發生在最極端情況下，其中所有資料僅對應於一個謂詞。在其他情況下，謂詞對資料進行分片設計的效果更好，可以在實際系統中實現更快的查詢延遲。
Sharding分片集不是Dgraph的唯一創新。Dgraph還為所有物件分配了整數ID，並對其進行排序並存儲在釋出列表結構中，以便快速選擇釋出列表。這樣可以在連線期間快速過濾，公共引用查詢等。部分借鑑了Google的Web服務系統的。
Plasma：和OneBoxes互動
谷歌的Dgraph不是一個數據庫，而是一個服務系統，相當於谷歌的網路搜尋服務系統。因此，他必須對實時更新做出反應。作為實時更新服務系統，它需要一個實時圖形索引系統。借鑑Caffeine的實時增量索引系統，又建立一個新專案，在這個圖表索引系統下統一所有Google OneBox，其中包括天氣，航班，事件等。OneBox是一個單獨的顯示框，在執行某些特定型別的查詢時顯示，Google可以返回更豐富準確的資訊。比如，在谷歌搜尋 [weather in beijing],會直接顯示
image
在此專案之前，每個OneBox由獨立後端執行並由不同的團隊維護。有一組豐富的結構化資料，但專案之間沒有共享資料。不僅在操作上保留了針對所有這些後端的大量工作，而且知識共享的缺乏限制了Google可響應的查詢型別。
例如，[events in Beijing]可以顯示事件，[weather in beijing]可以顯示天氣。但如果[events in Beijing]可以理解天氣多雨並且知道事件是在室內還是在室外，它可以根據天氣過濾（或至少排序）事件。
image
在Metaweb團隊的幫助下，我們開始將所有這些資料轉換為SPO格式並在一個系統下對其進行索引。系統被命名為Plasma，這是一個圖服務系統Dgraph的實時圖形索引系統。
管理洗牌，專案被放棄
和Cerebro一樣，Plasma也是一個資金不足的專案，而且還在繼續增長。最終，當管理層意識到OneBoxes即將轉到這個專案，他們需要負責知識的“合適的人”。在那場政治遊戲中，經歷了管理上的變化。Spanner的管理層認為Dgraph過於複雜，而實際上Spanner也是一個全球分散式的SQL資料庫，還需要GPS時鐘來確保全域性一致性。儘管如此，Dgraph專案還是被放棄了。Plasma雖然倖免於難，但移交給新領導下的新團隊負責管理，新團隊對圖形問題缺乏瞭解，他們決定建立一個基於Google現有搜尋索引的服務系統（就像Cerebro所做的那樣）。Plasma被用於抓取和知識主題擴充套件，因此新的系統可視其為Web文件，它有個新的名稱TS。TS不支援進行深度連線。
Dgraph：鳳凰涅槃
Manish於2013年5月離開谷歌，離開谷歌兩年後，Manish建立了Dgraph。
圖形空間，市場上有很多半生不熟的解決方案，特別是很多自定義解決方案，基於關係或NoSQL資料庫建立。而基於單機方案的圖資料庫方案，則必然存在可伸縮性問題，缺乏一個一個高效能，可擴充套件的解決方案。
構建支援任意深度連線、水平可伸縮、低延遲的圖形資料庫是一個非常棘手的問題，而Manish也沒有收手,直面挑戰，建立了Dgraph.io來延續在谷歌未做成的目標。