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来延续在谷歌未做成的目标。