本文由云 + 社区发表
作者：ManishRai Jain
作者：ManishRai Jain Dgraph Labs 创始人
版权声明：本文由腾讯云数据库产品团队整理，页面原始内容来自于 db weekly 英文官网，若转载请注明出处。翻译目的在于传递更多全球最新数据库领域相关信息，并不意味着腾讯云数据库产品团队赞同其观点或证实其内容的真实性。如果其他媒体、网站或其他任何形式的法律实体和个人使用，必须经过著作权人合法书面授权并自负全部法律责任。不得擅自使用腾讯云数据库团队的名义进行转载，或盗用腾讯云数据库团队名义发布信息。
每当我向别人介绍自己，并解释我们在 Dgraph Labs 所建设的内容时，我经常被人问到是否在 Facebook 工作过，或者我现在所做的尝试是否受到 FaceBook 的启发。很多人都知道 FaceBook 为社交图数据库所做的努力，是因为他们发布了很多关于图数据库基础设施的文章。
来自谷歌的 Word 仅限于提供知识图谱，但在这个项目之前，几乎没有人认为内部基础架构就可以实现这个服务。Google 提供专门的系统来提供知识图谱服务。事实上，在谷歌工作的时候，我和我的团队对图数据库服务系统下了很大的赌注。远在 2010 年，我自己就至少做了两个比较激进的尝试去研究新的图数据库理论，来看看我们可以创造什么。
Google 需要构建一个新的图数据库服务系统，不仅可以处理知识图谱数据中的复杂关系，还可以处理所有访问结构化数据的搜索服务（OneBoxes）。该服务系统要具备遍历所有数据的能力，还要具备足够高的吞吐量和足够低的延时，这样就可以应用于海量的网络搜索查询。当时几乎没有可用的系统或者数据库能同时满足上面三个要求。
现在我已经回答了谷歌为什么要构建图数据服务系统，剩下的篇幅我会向你们介绍，我们是如何一步一步，构建一个符合要求的图数据库系统来服务知识图谱和搜索引擎的。
我是怎么知道这些的？
先允许我快速的自我介绍一下，2006 年到 2013 年，我在谷歌工作。最开始是作为一个实习生，后面在 Web Search Infrastructure 组作为一个软件工程师工作。2010 年，Google 收购了 Metaweb，我的团队刚刚推出了 Caffeine。我想做一些与众不同的事情，并开始与 Metaweb 人合作，穿梭在旧金山和山景之间。我当时的目标是弄清楚如何使用知识图谱来改进网络搜索。
在我致力于研发图数据库之前，Google 有一些项目。值得注意的是，Google 在纽约办公室创建了一个名为 Squared 的项目，并且有一些关于知识卡片的讨论。这些是个人和小团队的零星努力。但那时候还没有形成一个既定的决策链，这也最终使我离开了谷歌。这个我们稍后再谈。
Metaweb 故事
如上所述，谷歌在 2010 年收购了 Metaweb。Metaweb 使用多种技术构建了一个高质量的知识图谱，包括爬取和解析维基百科，以及使用类似维基百科的众包策略通过 Freebase 运作。所有这些都是由他们内部构建的图形数据库驱动的，这个数据库名为 Graphd ，一个图数据库程序（现已经 GitHub 上发布）。
Graphd 有一些非常典型的属性。像守护进程一样，它在一台服务器上运行，所有数据都在内存中。整个 Freebase 网站都用了 Graphd。收购完成后，谷歌面临的挑战之一就是继续运行 Freebase。
Google 构建了 SSTable，然后是 Bigtable，它们可以横向扩展到数百或数千台机器，共同服务于数 PB 的数据。而且它们使用 Borg（一个集群管理工具，K8s 的前身）分配机器，使用 Stubby（gRPC 出来）进行通信，通过 Borg 名称服务解析 IP 地址（BNS，baked into K8s），并将数据存储在 Google 文件系统（GFS，类似 Hadoop FS）。进程可能会死亡，机器可能会崩溃，但系统还是会一直保持运行。
正是基于这个环境，Graphd 得以发扬光大，服务于在单个服务器上运行整个网站的数据库的想法与 Google（包括我自己）最初的想法千差万别。Graphd 需要 64GB 或更多内存才能运行。如果你在嘲笑这内存，请注意时间点，这是在 2010 年。大多数 Google 服务器的最大容量为 32GB。事实上，Google 必须购买具有足够大 RAM 的特殊机器来支持 Graphd。
GraphD 的替代者
关于如何移动和重写 GraphD 以分布式方式工作的想法被提出，但是他们不是存储键值对的数据库，人们只需要获取一大块数据，将其移动到另一个服务上，当访问对应的 key，就可以提供服务了。图数据库需要保证有效的连接和遍历，这就需要我们使用特定的方式构建软件。
在这些想法中，其中一个是使用名为 MindMeld（IIRC）的项目。该项目可以通过网络硬件可以更快地访问来自另一台服务器的内存。据推算，这种访问方式正常的 RPC 更快，足以快速复制内存数据库所需的伪复制直接内存访问。这个想法并没有走得太远。
另一个真正被采纳的想法是构建一个真正的图数据库服务系统。不仅可以取代 Graphd for Freebase，还可以为将来的所有知识图谱工作服务。这被命名为 Dgraph，一个分布式的图数据库服务系统，一个升级版的 Graphd。
不用感到疑惑，答案是肯定的。在 Google 内部，Dgraph Labs 这家公司和开源项目 Dgraph，就是这样被命名的。
对于本博文的大部分内容，当我提到 Dgraph 时，我指的是 Google 内部的项目，而不是我们构建的开源项目。当然开源项目后面也会有更多介绍。
Cerebro 的故事：一个知识图谱引擎
一个无意中造就的图数据库服务系统
虽然那时是我已经意识到 Dgraph 在努力取代 Graphd 的路上，但我当时的目标是改进网络搜索的体验。我在 Metaweb 找到了一位研发工程师 DH，他同时也是 Cubed 的创始人。
正如我前面提到的，Google 纽约的一些工程师已经建立了 Google Squared。DH 建立了一个类似的项目 Cubed。虽然 Squared 这个项目最终烂尾了，但 Cubed 非常令人印象深刻。我开始考虑如何在 Google 上构建它。Google 提供了一些小特性，帮助我更轻松的搞定整个构建过程。
第一个特性是搜索，谷歌提供了一种方法，可以高度准确地判断哪些词是连在一起理解的。例如，当看到像 [tom hanks movies] 这样的短语时，它可以告诉你 [tom] 和 [hanks] 应该连起来。同样，看到 [san francisco weather] 就知道 [san] 和 [francisco] 连在一起表达一个意思。对于人类而言，这些都是显而易见的事情，然而对于机器来说，做到这一点很难。
第二个特性是理解语法，当一个类似于 [books by french authors] 的搜索请求产生时，机器可以理解为 [french authors] 写的 [books]（即法国籍作者写的书）。但这个短语还可以被理解为写 [french books] 的 [authors]，即写法国书籍的作者。我使用斯坦福的词性（POS）标记器来更好地理解语法并构建一棵语法树。
第三个特性是理解实体，[french] 一词可以代表很多实体。它可以代表国家（地区），国籍（指法国人），菜肴（指法式食物）或法语。这里我可以使用另一个项目来获取单词或短语可以对应的实体列表。
第四部分是了解实体之间的关系。现在我已经知道如何将单词连接成到短语，短语应该被以什么样的形式组织（即语法），以及它们可以对应的实体，我需要一种方法来找到这些实体之间的关系以创建机器解释。例如，一个查询说 [books by french authors]，然后 POS 告诉我们它代表 [french authors] 写的 [books]。我们有 [french] 的几个实体，[authors] 的几个实体，接下来算法需要确定它们的连接方式。他们可以通过出生地联系起来，即出生在法国的作者（但可能是英文写作），或者是法国国民的作者，或者说或写法语（但可能与法国这个国家无关）的作者，或者仅仅是喜欢法国美食的作家。
基于搜索索引的图数据库系统
为了确定实体是否需要以及如何连接，我需要一个图数据库系统。Graphd 从未扩展到整个 Google 级别，而我擅长的是网络搜索。知识图谱元数据以三元组格式化，即每个事实由三个部分表示，主题 S（实体），谓词 P（关系）和对象 O（另一个实体）。查询必须来自 [S P]→[O]，来自 [P O]→[S]，有时来自 [S O]→[P]。
我使用了 Google 的搜索索引系统，为每个三元组分配了一个 Id，并构建了三个索引，分别为 S，P 和 O.另外，索引允许附件，所以我附上了每个实体的类型信息（即演员，书，人等等）。
我建立了这个图数据服务系统，但知道它存在连接深度问题（如下所述），并且不适合任何复杂的图数据查询。事实上，当 Metaweb 团队的某个人让我开放该系统给其他团队访问时，我坚持拒绝了。
为了确定实体间的关系，我会遍历查询实体间的所有可能性。比如，[french] 和 [author] 之间会产生的所有关系，从中选一部分结果出来，在判断 [book] 和这些结果之间产生的任何联系，以此类推不断推演。这会导致同一个短语会产生多个解释，比如 [tom hanks movies] 这个短语，它会产生如 [汤姆汉克斯执导的电影]、[汤姆汉克斯主演的电影]、[汤姆汉克斯制作的电影] 这样的解释，并自动过滤像 [电影命名汤姆汉克斯] 的解释。
对于每个可能解释，图数据库系统将生成结果列表，包含图中的有效实体，并且还将返回其类型（存在于附件中）。使用起来非常强大，因为结果的类型允许过滤，排序或进一步扩展等功能。比如对于电影搜索结果，您可以按照发行年份，电影的长度（短片，长片），语言，获奖等等对电影进行分类。
这个项目看起来很常智能，我们（DH 作为知识图谱专家也参与了一部分）将它命名为 Cerebro，之后 X 战警电影里出现了同名机器（脑波触发器）。
Cerebro 的运行经常会揭示一个人们最初没有探索过的非常有趣的事实。当运行像 [美国总统] 那样的查询时，Cerebro 会明白总统是人类，而人类有身高。因此，它允许你按身高对总统进行分类，并表明亚伯拉罕林肯是美国最高的总统。它还可以允许人们按国籍查询总统，在这种情况下，它同时显示了美国和英国总统的名单，因为美国有一位英国国籍总统：乔治华盛顿。（免责声明：基于当时 KG 状态的结果，不能保证这些结果的正确性。）
超链接 vs 知识图谱
Cerebro 是有机会真正理解用户查询的含义的。利用图数据库的中的数据库，我们可以生成查询的机器解释，生成结果列表并理解结果以支持进一步探索。如前面介绍的，您可以对结果启动特定的过滤和排序操作，也可以进行对连接进行遍历来显示数据的连接关系。从 [美国总统] 到 [他们去的学校]，或者 [他们所生的孩子]。 DH 在另一个他称为 Parallax 的项目中证明了从一个结果列表跳转到另一个结果列表的能力。
Cerebro 令人非常印象深刻，Metaweb 的领导层也支持它。即使是服务于其中的一部分的，Cerebro 也具有令人满意的高性能和功能，我称之为知识引擎（从搜索引擎升级）。但是谷歌的领导没有知识图谱相关领域的。我的经理对此也并不感兴趣，在跟他沟通之后，我获得了将其展示给一位非常高级的搜索部门领导的机会。
然而展示之后的回应令人沮丧。对于 [法国作者的书籍] 的演示，该领导向我展示了谷歌查询的搜索结果，其中显示了十个相关的超链接，他认为谷歌可以做同样的事情。此外，他们不想从网站上取走大量信息，也许会侵犯搜索者的隐私。
如果你也认为这个高管说的有道理，不妨再想一想：当 Google 进行网络搜索时，它并不能真正理解查询。它会在正确的相对位置，页面的等级中查找正确的关键字，以及做诸如此类的事。它是一个非常复杂和极其复杂的系统，但它并不能真正理解查询或结果。用户需要自行从结果中读取，解析和提取他们需要的信息，并进一步搜索以将完整的结果列表放在一起。
例如，对于 [法国作者的书籍]，首先需要将一个详尽的列表放在一起，内容多大单个网页可能都放不下。然后按出版年份对这些书籍进行排序，或者按出版社等进行过滤，所有这些操作都需要大量的链接跟踪，进一步搜索和人工聚合结果。 Cerebro 有能力将所有用户过滤信息的步骤省除，让人机交互简单而完美。
然而，这是当时典型的知识图谱方法。Google 的管理层不确定知识图谱的效用，也不确定搜索引擎应该如何跟知识图谱结合起来。这个通过向用户提供网页链接而获得巨大成功的组织，难以轻易消化这种接近更知识的新方式。
在与 Google 管理层对峙了一年后，我几乎丧失了继续的信心。此时谷歌上海办公室的一位经理向我伸出手，我于 2011 年 6 月将项目交给了他。他组建了一个由 15 名工程师组成的团队。我在上海呆了一个星期，将我建造和学到的东西转移给工程师。 DH 也参与其中，他在这里长期指导团队。
连接深度问题
我为 Cerebro 构建的图数据库服务系统存在一个连接深度问题。当需要查询的先前部分的结果集来执行其后续部分时，一个连接就被建立了。典型的连接将涉及一些 SELECT 操作，即来自通用数据集的某些结果中的过滤器，然后使用这些结果来过滤数据集的另一部分。我将以一个例子来说明。
比如说，你想知道 [people in SF who eat sushi]（住在旧金山且吃寿司的人）。数据被人们分成两类：住在 SF 的人和吃寿司的人这两类信息。
以上查询是单级连接。如果数据库外部的应用程序正在执行此操作，它将执行一个查询来执行第一步。然后执行多个查询（每个结果一个查询），找出每个人吃什么，只挑选吃寿司的人。
第二步是出现扇出问题。如果第一步有一百万个结果（所有旧金山人口），那么第二步需要将每个结果放入查询中，检索他们的饮食习惯，然后通过过滤器过滤出符合条件的人。
分布式系统工程师通常通过广播来解决这个问题。他们将结果分成很多批量任务，使用分片功能进行分割，并将查询任务分配到集群中的每个服务器。使用分布式会完成连接，但会导致查询延迟问题。
分布式系统中的广播很糟糕。谷歌的 Jeff Dean 在他的 “Achieving Rapid Response Times in Large Online Services” 演讲中最好地解释了这个问题。查询的总延迟总是大于最慢的那台机器的延迟。单个机器上的小问题就会导致延迟，每次查询涉及到海量的机器就会大大增加延迟的可能性。
考虑一个服务器，其 50％延迟为 1ms，但 99％延迟为 1s（即百分之 99 的延迟都小于等于 1s）。如果查询仅仅在一个服务器上处理，则只有 1％的请求会占用一秒钟以上。但如果查询触及其中的 100 台服务器，则 63％的请求将占用一秒钟以上。
因此，执行一个查询的广播对于查询延迟是不利的。现在考虑是否需要进行两次，三次或更多次连接。对于实时 OLTP 场景来说，会变得太慢，延时超出人们的接受范围。
大多数非原生图数据库都存在这种高扇出的广播问题，包括 Janus 图，Twitter 的 FlockDB 和 Facebook 的 TAO。
分布式连接是一个难题。现有的单机图形数据库通过将通用数据集保持在一个机器（独立数据库）内，并且在不触及其他服务器的情况下进行所有连接操作，则可以避免这个问题，比如 Neo4j。
进入 Dgraph：任意深度连接引擎
在结束 Cerebro 之后，我有了构建图形服务系统的经验，参与了 Dgraph 项目，并成为该项目的三位技术主管之一。 Dgraph 设计中涉及的概念是新颖的，解决了连接深度问题。
Dgraph 以一种特殊的方式对图形数据进行分片，其中每个连接都可以完全由一台机器执行，回到之前说的概念主题 - 谓词 - 对象（SPO），Dgraph 的每个实例将保存与该实例中的每个谓词相对应的所有主题和对象。多个谓词将存储在实例上，每个谓词都以整体存储。
这实际上允许了查询执行任意深度连接，同时避免扇出广播问题。比如查询 [people in SF who eat sushi]，会导致数据库内最多进行两次网络调用，无论集群规模大小。第一个调用会找到所有住在旧金山的人。第二个调用会发送这个人名单并与所有吃寿司的人求并集。我们还可以添加更多约束或扩展，每个步骤仍然会涉及最多一个网络调用。
这引入了位于单个服务器上的非常大的谓词的问题，但是这个问题可以通过随着大小的增长在两个或更多个实例之间进一步分割谓词来解决。即使这样，整个集群中的单个谓词拆分也只是在最极端情况下的最坏行为，其中所有数据仅对应于一个谓词。在其他情况下，这种通过谓词对数据进行分片的技术表现都很好，可以在实际系统中实现更快的查询延迟。
分片技术并不是 Dgraph 的唯一创新。Dgraph 为所有对象分配了整数 ID，并对其进行排序并存储在发布列表结构中，以便快速对这些发布列表求进行交叉计算。这些创新将在连接期间加快过滤速度，还可以用来查找公共引用等。这些想法里涉及到了 Google 的 Web 服务系统。
通过 Plasma 项目统一所有 OneBox
谷歌的 Dgraph 不是一个数据库，而是一个服务系统，相当于谷歌的网络搜索服务系统。使用 Dgraph 还可以对实时更新做出反应。作为实时更新服务系统，它需要一个实时图形索引系统。我在 Caffeine 项目中积累了很多实时增量索引系统方面的经验。
我发起一个项目，通过图数据索引系统来统一所有 Google OneBox，其中包括天气，航班，事件新闻等。你可能不知道 OneBox 这个词，但你肯定已经看过了。 OneBox 不同于其他搜索结果，是一个单独的显示框，在运行某些类型的查询时显示，Google 可以在 OneBox 返回更丰富的信息。想了解一下 OneBox，请尝试搜索 [weather in sf]。
在发起这个项目之前，每个 OneBox 由独立后端运行并由不同的团队维护。有一组很复杂的结构化数据，但每个 OneBox 之间没有共享数据。这样不仅在操作上保留了后端的大量的重复工作，而且每个 Box 之间缺乏知识共享也限制了 Google 可以响应的查询类型。
举个例子，[events in SF] 可以显示旧金山的事件新闻，[weather in SF] 可以显示旧金山的天气。但如果 [events in SF] 这个 OneBox 了解到天气多雨并且知道用户需要查找的事件是在室内还是在室外，它就可以根据天气过滤（或至少排序）事件（在暴雨中，可能电影或交响乐等室内活动是最好的选择）。
在 Metaweb 团队的帮助下，我们开始将所有这些数据转换为 SPO 格式并在一个系统下对其进行索引。我将系统命名为 Plasma，一个基于图数据服务系统 Dgraph 的实时图形索引系统。
管理混乱
像 Cerebro 一样，Plasma 项目资金不足，但仍在继续。最终，当管理层意识到 OneBox 团队即将迁移到这个项目时，他们需要负责知识图谱的 “合适人选”。在那场 “权利的游戏” 中，我经历了三次管理层变化，但每次都没有对知识图谱有经验的人加入。
在此次管理层洗牌期间，支持 Spanner 的管理层认为 Dgraph 过于复杂，Spanner 是一个全球分布式的 SQL 数据库，需要 GPS 时钟来确保全局一致性。具有讽刺意味的是，这至今仍然令人难以置信。
最终，Dgraph 取消了，Plasma 幸免于难，但由新的领导和新的团队来负责继续运营，并直接汇报给 CEO。新团队对知识图谱缺乏了解，他们决定建立一个基于 Google 现有搜索索引的服务系统（就像我为 Cerebro 所做的那样）。我建议使用我已经为 Cerebro 建立的系统，但是被拒绝了。我将 Plasma 改造为一个爬取并可以扩展知识话题到若干层的系统，这样 Google 现有的搜索服务可以把结果当成 Web 文档来处理。他们称之为 TS（名称缩写）。
这种改造也意味着新的服务系统将无法进行任何深度连接。在很多公司，我都看到一个关于知识图谱的 “决策诅咒”，是因为工程师们通常错误地认为 “图数据服务是一个简单的问题，可以通过在另一个已有系统之上构建一个层来解决”。
几个月之后，2013 年 5 月，我离开谷歌，此时我已经为 Dgraph / Plasma 工作了两年。
后记
搜索关注 “腾讯云数据库 TencentDB"官方微信，最新最热数据库前沿知识和手把手实战教程等你来约，更可在移动端一键管理数据库。
Dgraph：凤凰磐涅
离开谷歌两年后，我决定建立 Dgraph。不在 Google 的日子里，我见证了很多与在内部研发图数据系统时的犹豫不决。图形空间有很多半生不熟的解决方案，特别是很多自定义解决方案，草率的将系统搭建在关系型或 NoSQL 数据库之上，或者作为多模型数据库的众多功能之一。如果存在一个本地单击解决方案，则会遇到可伸缩性问题。
Dgraph 团队花了三年的时间，不仅吸收了我自己之前的经验，而且还对系统设计进行了大量的原创型研究，建立了市场上无与伦比的图形数据库。因此，公司具备了强大，可扩展且高性能的解决方案，用来替代那些半生不熟的解决方案。
此文已由腾讯云 + 社区在各渠道发布
获取更多新鲜技术干货，可以关注我们腾讯云技术社区 - 云加社区官方号及知乎机构号
