开源图数据库项目 DGraph 的前世今生 | 技术头条

谷歌为什么要构建图数据服务系统？Dgraph是如何一步一步被构建出来的呢？本文跟你聊聊图数据库Dgraph的前世今生。

作者 | ManishRai Jain

责编 | 伍杏玲

每当我向别人介绍自己，并解释我们在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工作了两年。

后记

• 几年后，Web搜索基础设施团队被重命名为Web搜索和知识图形基础设施团队，我曾经向其演示Cerebro的领导开始重新领导知识图谱工作，大谈特谈他们打算如何用知识图谱取代超链接，并直接回应尽可能多的用户查询。

• 当上海的Cerebro研发团队的即将将项目上线时，该项目从上海直接被拉到了谷歌纽约办公室。最终，它以Knowledge Strip的形式上线。如果你搜索[tom hanks movies]，你会在搜索结果顶部看到它。自首次发布以来，它有一些迭代改进，但仍然不支持Cerebro提供的过滤和排序级别。

• 在Dgraph工作的所有三位技术主管（包括我）最终都离开了谷歌。

• 当我作为高级软件工程师离开谷歌时，我确实获得了两次晋升，目前准备迎接第三次。

• 小道消息，当前版本的TS实际上非常接近Cerebro的图形系统设计，主题，谓词和对象都有一个索引。因此，它将继续受到加入连接深度问题的困扰。

• 此后，Plasma被重写并重命名，但仍然继续充当实时图形索引系统，支持TS。他们一起继续托管和提供Google的所有结构化数据，包括知识图谱。

• 从很多地方都可以看出，Google无法进行深度连接。首先，我们仍然没有看到OneBoxes的各种数据反馈的结合：尽管天气和KG数据随时可用， [cities by most rain in asia] （亚洲下雨最多的城市）都、没有生成城市实体列表（相反，结果是来自网页的引用）; [events in SF]无法根据天气进行过滤; [US presidents]的结果不能进一步分类，过滤或扩展到他们的孩子或他们就读的学校。我怀疑这也是停止使用Freebase的原因之一。

离开谷歌两年后，我决定建立Dgraph。不在Google的日子里，我见证了很多与在内部研发图数据系统时的犹豫不决。图形空间有很多半生不熟的解决方案，特别是很多自定义解决方案，草率的将系统搭建在关系型或NoSQL数据库之上，或者作为多模型数据库的众多功能之一。如果存在一个本地单击解决方案，则会遇到可伸缩性问题。

Dgraph团队花了三年的时间，不仅吸收了我自己之前的经验，而且还对系统设计进行了大量的原创型研究，建立了市场上无与伦比的图形数据库。因此，公司具备了强大，可扩展且高性能的解决方案，用来替代那些半生不熟的解决方案。

作者：ManishRai Jain，Dgraph Labs创始人

声明：本文由腾讯云数据库产品团队整理，页面原始内容来自于db weekly英文官网。

本文由腾讯云投稿，如需转载请联系腾讯云。

【完】

 热 文 推 荐 

System.out.println("点个在看吧！");
console.log("点个在看吧！");
print("点个在看吧！");
printf("点个在看吧！\n");
cout << "点个在看吧！" << endl;
Console.WriteLine("点个在看吧！");
Response.Write("点个在看吧！");
alert("点个在看吧！")
echo "点个在看吧！"

点击阅读原文，输入关键词，即可搜索您想要的 CSDN 文章。

喜欢就点击“好看”吧！