当我自我介绍并说我们的创业公司正在做什么时，对话者立即提出一个问题：您之前曾在Facebook上工作过，还是在Facebook的影响下创建了您的开发项目？ 许多人都知道Facebook为维护社交图谱所做的努力，因为该公司已发布了几张有关该图的基础结构的文章 ，并已精心构建。

Google谈论了她的知识图 ，但没有谈论内部基础架构。 但是，该公司还具有专门的子系统。 实际上，知识图已经引起了很多关注。 就个人而言，我至少对这匹马进行了两次促销-并于2010年开始制作新图表。

Google需要建立基础架构，不仅要服务于“知识图”中的复杂关系，还需要支持可访问结构化数据的搜索结果中的所有OneBox主题块。 该基础结构对于1）事实的质量规避具有2）足够高的带宽和3）足够低的延迟以设法获得网络上的大量搜索查询而言是必要的。 事实证明，没有一个可用的系统或数据库可以执行所有这三个操作。

现在，当我告诉您为什么需要基础架构时，在本文的其余部分中，我将讲述我在构建此类系统（包括Knowledge Graph和OneBox）方面的经验 。

我怎么知道

我将简要介绍一下自己。 从2006年到2013年，我在Google工作。 首先是实习生，然后是网络搜索基础架构中的软件工程师。 Google在2010年收购了Metaweb ，而我的团队刚刚推出了Caffeine 。 我想做些其他的事情-并开始与Metaweb（位于旧金山）的人一起工作，花时间在旧金山和山景城之间旅行。 我想弄清楚如何使用知识图来改善我的网络搜索。

我之前在Google上就有过这样的项目。 值得注意的是，名为Squared的项目是在纽约办公室创建的，并且有一些关于知识卡的讨论。 然后，个人/小型团队进行了零星的工作，但是那时没有建立的团队链，最终迫使我离开了Google。 但是我们稍后会再说...

Metaweb的历史

如前所述，Google在2010年收购了Metaweb。 Metaweb使用多种方法构建了高质量的知识图，包括Wikipedia爬网和解析，以及使用Freebase的众包Wiki风格的编辑系统。 所有这些工作都基于Graphd自己的图形数据库-graph守护程序（现已在GitHub上发布）。

Graphd具有一些相当典型的属性。 作为守护程序，它可以在一台服务器上工作，并将所有数据存储在内存中，并且可以发出整个Freebase站点。 购买后，Google设置了一项任务以继续使用Freebase。

Google在标准硬件和分布式软件上建立了一个帝国。 一个服务器端DBMS将永远无法提供爬网，索引和搜索结果。 首先创建SSTable，然后创建Bigtable，然后将Bigtable横向扩展到共享PB级数据的数百或数千台计算机。 机器由Borg分配（ K8来自此处），它们通过Stubby（gRPC来自此处）进行通信，并通过Borg名称服务（K8中的BNC）解析IP地址并将数据存储在Google文件系统（ GFS ，您可以说Hadoop FS）中。 进程可能会死掉，机器可能会崩溃，但是整个系统是坚不可摧的，并且会持续嗡嗡作响。

图进入了这样的环境。 在一个服务器上为整个网站服务的数据库的想法与Google（包括我）无关。 特别是，Graphed需要64 GB或更多的内存才能运行。 如果您觉得这有点小，请记住：这是2010年。 大多数Google服务器配备的最大容量为32 GB。 实际上，Google必须购买具有足够RAM的特殊机器才能以其当前形式提供Graphd服务。

图形替换

头脑风暴开始于如何移动图形数据或重写系统以分布式方式工作。 但是，您会看到，这些图很复杂。 这不是适合您的键值数据库，您可以在其中简单地获取一条数据，将其移至另一台服务器，然后在请求密钥时将其发布。 图执行有效的联接和变通办法，要求软件以特定方式工作。

一种想法是使用一个名为MindMeld（IIRC）的项目。 假定来自另一台服务器的内存可以通过网络设备更快地获得。 它本来应该比常规RPC更快，但要足够快以伪造内存数据库所需的直接内存访问。 但是这个想法并不过分。

实际上成为项目的另一个想法是创建一个真正的分布式图形服务系统。 不仅可以代替Graphed for Freebase，而且在生产中也确实可以使用。 她被称为Dgraph-分布式图形，是从Graphd（graph-daemon）反转而来的。

如果您有兴趣，那就可以。 我的初创公司Dgraph Labs，公司和开源项目Dgraph以该项目在Google上的名字命名（注意：Dgraph是Dgraph Labs的商标；据我所知，Google不会发布名称与内部名称相匹配的项目）。

在几乎所有其他文本中，当我提到Dgraph时，我的意思是内部Google项目，而不是我们创建的开源项目。 但是稍后会更多。

脑的故事：知识引擎

无意中创建图的基础结构

尽管我通常了解Dgraph试图替代Graphd，但我的目标是创建一些改进Web搜索的方法。 在Metaweb，我遇到了创建Cubed的DH研究工程师。

正如我提到的，纽约分部的一群杂色工程师开发了Google Squared 。 但是DH系统要好得多。 我开始考虑如何在Google上实施它。 Google有我可以轻松使用的拼图。

难题的第一部分是搜索引擎。 这是一种准确确定哪些单词相互关联的方法。 例如，当您看到类似[tom hanks电影]的短语时，可能会告诉您[tom]和[hanks]是相关的。 同样，从[旧金山天气]我们可以看到[旧金山]和[旧金山]之间的联系。 这些对于人们来说是显而易见的事情，但对于汽车却不是那么明显。

难题的第二部分是理解语法。 在查询[法国作家的书籍]时，机器可以将其解释为[法国作家]的[书籍]，即那些法国作家的书籍。 但是她也可以将其解释为来自[作者]的[法语书籍]，即任何作者使用的法语书籍。 我使用了斯坦福大学的词性 （POS）标记器来更好地解析语法并构建树。

难题的第三部分是了解实体。 [法语]可能有很多意义。 这可能是一个国家（地区），国籍（与法国人有关），美食（与食品有关）或语言。 然后，我应用了另一个系统来获取单词或短语可以对应的实体列表。

难题的第四部分是了解实体之间的关系。 当知道如何将单词连接到短语中时，应该以什么顺序执行短语，即它们的语法以及它们可以对应的实体，您需要找到这些实体之间的关系才能创建机器解释。 例如，我们运行查询[法国作家的书籍]，而POS表示它是[法国作家]的[书籍]。 我们为[法语]和[作者]有多个实体：算法应确定它们之间的关系。 例如，他们可能是按出生地来关联的，即在法国出生的作者（尽管他们可以用英语写）。 或者可能是法国公民的作家。 会说或会说法语（但可能与法国作为一个国家无关）的作者，或者只喜欢法国美食的作者。

搜索索引图系统

要确定对象之间是否存在连接以及它们如何连接，您需要一个图形系统。 Graphd永远不会扩展到Google级别，但是您可以使用搜索本身。 知识图数据以三元组三元组格式存储，即每个事实都由三个部分表示：主题（实体），谓词（关系）和宾语（其他实体）。 请求像[SP] → [O]或[PO] → [S] ，有时甚至是[SO] → [P] 。



我使用了Google搜索索引 ，为每个三元组分配了一个docid，并建立了三个索引，一个索引用于S，P和O。此外，该索引是可嵌套的，因此我添加了有关每个实体类型的信息（例如，演员，书，人物和等）。

我创建了这样一个系统，尽管我看到了联接深度的问题（下面将进行解释），并且它不适用于复杂的查询。 实际上，当Metaweb团队的某人要我为同事发布系统时，我拒绝了。

要确定这种关系，您可以查看每个查询给出多少结果。 例如，[法语]和[作者]给出多少个结果？ 我们获得这些结果，并查看它们与[books]等的关系。因此，出现了许多机器对查询的解释。 例如，查询[tom hanks电影]会生成各种解释，例如[tom hanks执导的电影]，[tom hanks主演的电影]，[tom hanks制作的电影]，但会自动拒绝诸如[tom hanks的电影]之类的解释。


每种解释都会生成结果列表（图表上的有效实体），并返回其类型（在附件中显示）。 事实证明，这是一项功能非常强大的功能，因为了解结果的类型会带来各种可能性，例如过滤，排序或进一步扩展。 您可以按照发行年份，电影的长度（短，长），语言，获得的奖项等来整理电影。

这个项目看起来是如此聪明，以至于我们（DH也作为知识图谱的专家也参与其中）将其命名为Cerebro，以纪念电影《 X战警》中的同名设备。

Cerebro经常揭示非常有趣的事实 ，这些事实本来不在搜索查询中。 例如，应[美国总统]的要求，Cerebro将意识到总统是人民，人民有成长。 这使我们能够按增长对总统进行排序，并表明亚伯拉罕·林肯是美国最高的总统。 此外，还可以按国籍过滤人员。 在这种情况下，美国和英国出现在名单上，因为美国有一位英国总统，即乔治·华盛顿。 （免责声明：结果基于实验时知识图的状态；我不能保证其正确性）。

蓝色链接与知识

Cerebro能够真正理解用户的请求。 收到整个图的数据后，我们可以生成查询的机器解释，生成结果列表，并从这些结果中了解很多内容，以进一步研究图。 上面已经解释过：只要系统了解到正在处理电影，人物或书籍等，就可以激活某些过滤器和种类。 您甚至可以遍历节点并显示相关信息：从[美国总统]到[他们去的学校]或[他们生的孩子]。 这是系统本身产生的其他一些查询：[女非裔美国政治家]，[嫁给政治家的好莱坞演员]，[美国总统之子]，[由90年代汤姆·汉克斯主演的电影]

卫生署展示了这个机会，可以在一个名为Parallax的项目中从一个列表移动到另一个列表。

Cerebro展示了非常令人印象深刻的结果，Metaweb管理层对此给予了支持。 即使在基础架构方面，事实证明它也是高效且实用的。 我称它为知识引擎 （就像搜索引擎一样）。 但是在Google上，没有人专门解决这个话题。 她对我的经理没什么兴趣，他们建议我先与一个人交谈，然后再与另一个人交谈，结果，我有机会向一位非常高级的搜索经理演示该系统。

答案不是我所希望的 。 为了演示[法国作者的书]知识引擎的结果，他发起了Google搜索，显示了十行带有蓝色链接的行，并表示Google可以这样做。 另外，他们不希望从站点获取流量，因为他们会生气。

如果您认为他是对的，请考虑以下问题：当Google在Internet上进行搜索时，它实际上不理解该请求。 系统会根据页面的重量等在正确的位置搜索正确的单词。 这是一个非常复杂的系统，但无法理解查询或结果。 用户自己进行所有工作：阅读，分析，从结果中提取必要的信息并进行进一步搜索，将结果的完整列表加在一起等。

例如，对于[法国作家的书]，一个人将首先尝试找到详尽的列表，尽管可能找不到包含该列表的页面。 然后按出版年限对这些书进行排序，或按出版者进行筛选，依此类推-所有这些都需要一个人处理大量信息，进行大量搜索并处理结果。 Cerebro能够减少这些工作，并使用户交互变得简单而完美。

但是，那时对知识图的重要性还没有完全的了解。 该手册不确定其实用性或如何将其与搜索相关联。 对于通过为用户提供网页链接而取得如此巨大成功的组织来说，这种新的知识获取方法并不容易。

在一年的时间里，我因对经理的误解而苦苦挣扎，最终放弃了。 上海办公室的一位经理找我，我于2011年6月将项目交给了他。 他聘请了一支由15名工程师组成的团队。 我在上海呆了一个星期，将我创建和学习的所有内容都传达给了工程师。 DH也参与了这项业务，他领导了很长时间的团队。

连接深度问题

在Cerebro绘图系统中，联合的深度存在问题。 当需要早期查询的结果来完成后续查询时，将执行联接。 典型的并集包括一些SELECT ，即从通用数据集中筛选某些结果的过滤器，然后将这些结果用于数据集的另一部分的过滤。 我将举例说明。

假设您想知道[旧金山的吃寿司的人]。 为所有人分配了一些数据，包括谁住在哪个城市以及他们吃哪种食物。

上面的查询是单级联接。 如果应用程序访问数据库，它将对第一步提出一个请求。 然后进行几个查询（每个结果一个查询）以找出每个人的饮食，只选择那些吃寿司的人。

第二步是扇出问题。 如果第一步给出一百万个结果（旧金山人口），则应根据每个人的要求给出第二步，询问他们的饮食习惯，然后应用过滤器。



分布式系统工程师通常通过广播 （即无处不在的分发）解决此问题。 它们累积相应的结果，向集群中的每台服务器发出一个请求。 这提供了一个联接，但是导致请求延迟问题。

在分布式系统中，广播效果不佳。 Google的Jeff Dean在演讲“在大型在线服务中实现快速响应”（ 视频 ， 幻灯片 ）中可以最好地解释这个问题。 总延迟始终大于最慢组件的延迟。 个别计算机上的小眩光会导致延迟，并且查询中包含许多计算机会大大增加延迟的可能性。

考虑一台服务器，在50％的情况下延迟超过1 ms，在1％的情况下延迟超过1 s。 如果请求仅发送到一台这样的服务器，则只有1％的响应超过一秒钟。 但是，如果请求发送到数百个此类服务器，则63％的响应将超过一秒钟。

因此，一个请求的广播大大增加了延迟。 现在想想，如果您需要两个，三个或更多个关联？ 它太慢了，无法实时执行。

大多数非本机图数据库（包括Janus图 ， Twitter FlockDB和Facebook TAO）中 ，请求广播是固有的风扇部署问题。

分布式关联是一个复杂的问题。 本机图形数据库可通过在一个服务器（独立数据库）中存储通用数据集并执行所有联接而无需访问其他服务器来避免此问题。 例如， Neo4j执行此操作。

Dgraph：具有任意深度的并集

在完成有关Cerebro的工作并拥有构建图形管理系统的经验之后，我参加了Dgraph项目，成为三位技术项目经理之一。 我们应用了创新的概念，解决了联盟深度的问题。

特别是，Dgraph分离图数据，以便每个连接可以完全由一台机器执行。 返回subject-predicate-object （SPO） subject-predicate-object ，每个Dgraph实例都包含与该实例中每个谓词相对应的所有主题和对象。 几个谓词存储在一个实例中，每个谓词都被完全存储。

这使我们能够以任意深度的关联来满足请求 ，从而消除了广播期间风扇部署的问题。 例如，查询[在SF中吃寿司的人]将在数据库中最多生成两个网络调用 ，而与群集大小无关。 第一个挑战是找到住在旧金山的所有人。 第二个请求将发送此列表，以与所有吃寿司的人相交。 然后，您可以添加其他限制或扩展，每个步骤仍提供不超过一个网络呼叫。


这在同一服务器上产生了很大的谓词问题，但是可以通过随着大小的增长在两个或更多实例之间进一步划分谓词来解决。 在最坏的情况下，一个谓词将分散在整个集群中。 但这只会在一种极好的情况下发生，即所有数据仅对应一个谓词。 在其他情况下，这种方法可以大大减少实际系统中的请求延迟。

分片并不是Dgraph中唯一的创新。 所有对象都被分配了整数标识符，它们被排序并以列表（发布列表）的形式保存，以便以后快速通过此类列表。 这样一来，您就可以在合并过程中快速进行过滤，查找常用链接等。这里，来自Google搜索引擎的建议也很有用。

通过等离子组合所有OneBox块

Google的dgraph不是数据库 。 这是子系统之一，它也响应更新。 所以她需要索引。 我在使用Caffeine下运行的实时增量索引系统方面拥有丰富的经验。

我启动了一个项目，以统一该图形索引系统中的所有OneBox，包括天气，航班时刻表，事件等。 您可能不知道“单一框”一词，但您肯定看到了它-这是一个单独的窗口，在执行某些类型的查询时会出现，其中Google返回更丰富的信息。 要查看实际使用的OneBox，请尝试[ 平方英尺的天气 ]。

以前，每个OneBox都在自治后端上工作，并得到不同开发小组的支持。 那里有一组丰富的结构化数据，但是OneBox单元之间并不交换数据。 首先，不同的后端增加了许多倍的人工成本。 其次，缺乏信息共享限制了Google可以响应的请求范围。

例如，[SF中的事件]可以显示事件，[SF中的天气]可以显示天气。 但是，如果[SF中的事件]了解到现在正在下雨，那么您可以按“室内”或“室外”类型对事件进行过滤或排序（ 也许最好去电影院，而不是在大雨中踢足球） ）

在Metaweb团队的帮助下，我们开始将所有这些数据转换为SPO格式，并使用一个系统对其进行索引。 我将其命名为Plasma，这是用于Dgraph 的实时图形索引引擎 。

跨越式管理

与Cerebro一样，Plasma项目获得的资源很少，但仍保持增长势头。 最后，当管理层意识到OneBox块不可避免地成为我们项目的一部分时，它立即决定由“合适的人”来管理图形系统。 在政治竞赛的高峰期，三位领导人被替换，每位领导人在使用图表方面的经验均为零。

在Dgraph的这一跨越期间， Spanner项目经理将Dgraph称为过于复杂的系统。 作为参考，Spanner是一个全球分布式SQL数据库，需要使用自己的GPS手表来确保全局一致性。 具有讽刺意味的是，这仍然在吹牛。

Dgraph被取消，等离子幸存。 在项目负责人的头上，他们组建了一个新团队，新领导者，层次清晰，并向首席执行官汇报。 新团队对图表和相关问题了解甚少，因此决定根据现有的Google搜索索引创建一个基础架构子系统（就像我为Cerebro所做的那样）。 我建议使用已经为Cerebro使用的系统，但是被拒绝了。 我修改了Plasma，以将每个知识节点爬网并扩展到几个级别，以便系统可以将其作为Web文档查看。 他们称此系统为TS（ 缩写 ）。

这意味着新子系统将无法执行深度关联。 再次，这是我在许多公司中看到的一个诅咒，因为工程师一开始就错误地提出了一个错误的想法，即“图形是一个简单的问题，只需在另一个系统之上构建一个层即可解决。

几个月后，2013年5月，我在Dgraph / Plasma上工作了大约两年后离开了Google。

后记

• 几年后，“ Internet搜索基础结构”部分重命名为“ Internet搜索基础结构和知识图”，我曾向其展示过Cerebro的领导者领导了“知识图”的方向，讲述了他们打算如何替换简单的图。蓝色知识链接尽可能直接地直接回答用户问题。
  
• 当负责Cerebro的上海团队即将投入生产时，该项目就从他们那里接手并移交给了纽约部门。 最后，它以“知识带”的形式启动。 如果您正在寻找[ 汤姆·汉克斯电影 ]，您会在顶部看到它。 自首次发布以来，它有所改进，但仍不支持Cerebro中设置的过滤和排序级别。
  
• 从事Dgraph工作的所有三位技术经理（包括我自己）最终都离开了Google。 据我所知，其余的人现在都在Microsoft和LinkedIn工作。
  
• 我设法在Google获得了两次晋升，当我离开公司担任高级软件工程师（高级软件工程师）时，我应该获得第三名。
  
• 从一些零散的谣言来看，TS的当前版本实际上非常接近Cerebro图系统的设计，并且每个主语，谓语和宾语都有一个索引。 因此，她仍然遭受统一深度的困扰。
  
• 此后，等离子体已被重写和重命名，但它仍继续作为TS的实时图形索引系统。 他们一起继续在Google上发布和处理所有结构化数据，包括知识图。
  
• Google在很多地方都无法进行深层联合。 例如，我们仍然看不到OneBox块之间的数据交换：[所有亚洲降雨最多的城市]没有提供城市列表，尽管所有数据都在知识列中（而是在搜索结果中引用了网页）； [SF中的事件]无法按天气过滤； [美国总统]的结果没有通过其他事实进行排序，过滤或扩展：他们的孩子或所学习的学校。 我相信这是停止Freebase支持的原因之一。

图：凤凰鸟

离开Goog​​le两年后，我决定开发Dgraph 。 在其他公司中，我对图形的犹豫不决与Google一样。 图空间中有许多未完成的解决方案，特别是许多急于在关系数据库或NoSQL数据库之上或作为多模型数据库的众多功能之一组装的自定义解决方案。 如果有本机解决方案，那么它将遭受可伸缩性问题的困扰。

我没有看到关于高效，可扩展设计的连贯故事。 建立具有低延迟和任意深度联接的水平可伸缩图形数据库是一项极其困难的任务 ，我想确保我们正确地构建了Dgraph。

Dgraph团队在过去的三年中不仅学习了我自己的经验，还投入了自己的大量精力进行设计-创建了一个市场上没有类似产品的图形数据库。 因此，公司有机会使用可靠，可扩展且高效的解决方案，而不是另一半完成的解决方案。