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