本文由微信公众号“AI前线”（ID：ai-front）原创，未经授权不得转载。当我向人们解释我们在DgraphLabs做什么时，我经常被问到我是否曾经在Facebook工作过，或者我们正在做的事情是否受到Facebook的启发。很多人都知道Facebook在社交图谱服务方面做了很多工作，因为他们发表了多篇关于如何构建图谱基础设施的文章。说到谷歌，一般仅限于知识图谱服务，但没有人提到其内部基础设施是怎么回事。事实上，谷歌有一个专门提供知识图谱的系统。事实上，我们（在谷歌期间）也在图服务系统方面做了很多工作。早在2010年，我就进行了几次冒险，看看我能做什么。Google需要构建一个图服务系统，不仅可以处理知识图谱数据中的复杂关系，还可以处理所有可以访问结构化数据的OneBox。服务系统需要以足够高的吞吐量和足够低的延迟来遍历事实数据，以处理大量的网络搜索。但是没有现成的系统或数据库可以同时满足所有这三个要求。我已经回答了为什么Google需要构建图服务系统，在本文的其余部分，我将带您完成构建图服务系统的整个过程。我怎么知道的？让我自我介绍一下，我从2006年到2013年在谷歌工作。首先是实习生，然后是网络搜索基础设施的软件工程师。2010年，当Google收购Metaweb时，我的团队刚刚推出Caffeine。我想做一些不同的事情，所以我开始与Metaweb的人（在旧金山）一起工作。我的目标是弄清楚如何使用知识图来改进网络搜索。Metaweb的故事以前讲过，谷歌在2010年收购了Metaweb。Metaweb使用各种技术构建了高质量的知识图谱，包括爬取和解析维基百科。所有这一切都由他们内部构建的图形数据库驱动，称为Graphd——图形守护程序（现已发布在GitHub上：https://github.com/google/graphd）。Graphd有一些非常典型的属性。与守护进程一样，它在单个服务器上运行，所有数据都保存在内存中。Graphd被Freebase网站压得喘不过气来，谷歌在收购后面临的挑战之一是如何继续运行Freebase。谷歌在商品硬件和分布式软件领域建立了一个帝国。单个服务器数据库永远无法支持与搜索相关的爬网、索引和服务工作负载。Google首先推出了SSTable，然后是Bigtable，它可以扩展到数百甚至数千台机器，提供PB级数据的处理能力。他们使用Borg（K8s的前身）提供机器，使用Stubby（gRPC的前身）进行通信，通过BorgNameService（BNS，集成到K8s中）解析IP地址，并将数据存储在Google文件系统（GFS）上级。进程可能会死亡，机器可能会崩溃，但系统会继续运行。Graphd当时就处于这样的环境中。使用单一数据库为在单一服务器上运行的网站提供服务的想法并不适合谷歌（包括我自己）。特别是，Graphd需要64GB或更多的内存才能运行。如果你觉得这样的内存要求很有趣，请注意这是在2010年。当时大多数Google服务器的最大RAM为32GB，因此Google不得不购买具有足够RAM的特殊机器来支持Graphd。替换Graphd的想法开始冒出来，关于替换或重写Graphd并使其分布式，但这对于图数据库来说是一件非常困难的事情。它们不像键值数据库，您可以在键值数据库中将一大块数据移动到另一台服务器并在查询时提供键。图数据库承诺高效的连接和遍历，这需要以特定的方式实现。其中一个想法是使用一个名为MindMeld(IIRC)的项目。该项目承诺通过网络硬件更快地访问另一台服务器的内存。这应该比普通RPC更快，速度足以伪复制内存数据库所需的直接内存访问。但这个想法并没有走得太远。另一个想法（实际上是一个项目）是构建一个真正的分布式图服务系统，不仅可以取代Graphd，而且可以为未来的所有知识服务。它是Dgraph——一个分布式图形守护进程。DgraphLab的命名和开源项目Dgraph就是从Google的这个项目开始的。当我在本文中提到Dgraph时，我指的是Google的内部项目，而不是我们后来构建的开源项目。Cerebro的故事：一个知识引擎虽然我知道Dgraph的目标是取代Graphd，但我的目标是做一些改进网络搜索的东西。我找到了DH，他是Metaweb的一名研究工程师，他开发了Cubed(https://blog.dgraph.io/refs/freebase-cubed.pdf)。Google纽约办事处的一些工程师开发了Squared(https://en.wikipedia.org/wiki/Google_Squared)。DH更进一步，开发了Cubed。虽然Squared毫无用处，但Cubed却令人印象深刻。我开始思考如何在谷歌开发这样的东西，毕竟谷歌已经有现成的东西了。第一个是搜索项，它提供了一种高度准确地判断哪些词应该放在一起的方法。例如，对于像[tomhanksmovies]这样的短语，它会告诉你[tom]和[hanks]应该放在一起。同样，在短语[sanfranciscoweather]中，[san]和[francisco]应该放在一起。这些对人类来说是显而易见的事情，但对机器来说却不是。第二是理解语法。当查询[booksbyfrenchauthors]时，机器可以将其解释为[books]by[frenchauthors]（即法国作者的书）。但它也可以被解释为[frenchbooks]by[authors]（即作者的法语书籍）。我使用斯坦福的词性(POS)标记器来更好地理解语法并构建语法树。三是认识实体。[french]可以指代很多东西，它可以指国家（地区）、民族（法国）、美食（指食物）或语言。我使用另一个项目来获取单词或短语对应的实体列表。第四是理解实体之间的关系。既然我知道如何将单词关联到短语、短语执行的顺序（即语法）及其对应的实体，我还需要一种方法来找到这些实体之间的关系，以便创建机器解释。例如，对于[booksbyfrenchauthors]的查询，POS会告诉我们它指的是[frenchauthors]的[books]。我们有一些[french]实体和[authors]实体，算法需要弄清楚如何连接它们。他们可以通过出生地联系起来，即出生在法国的作家（但可能用英语写作），或者是法国借贷者，或者说或写法语（但可能与法国无关），或者只是喜欢法国美食作家。基于搜索索引的图形系统为了确定某些实体是否连接在一起以及如何连接在一起，我需要一个图形系统。知识图谱数据采用三元组的格式，即每个事实由主语（实体）、谓语（关系）和宾语（另一个实体）三部分表示。查询必须是[SP]→[O]，[PO]→[S]，有时是[SO]→[P]。我使用了Google的搜索索引系统，为每个三元组分配了一个docid，并构建了三个索引S、P和O。此外，索引允许附件，因此我为每个实体附加了类型信息。我构建这个图形服务系统时知道它存在连接深度问题（如下所述）并且不适合复杂的图形查询。事实上，当Metaweb团队的某人要求我开放系统访问权限时，我拒绝了。现在，为了确定关系，我运行了一些查询并查看出现了什么结果。[french]和[author]产生任何结果吗？选择这些结果并查看它们如何与[书籍]联系起来。这会产生多种机器解释。例如，当你查询[tomhanksmovies]时，它会生成[由tomhanks执导的电影]、[由tomhanks主演的电影]、[由tomhanks制作的电影]等解释，并自动拒绝[名为tomhanks的电影]等解释]这样的解释。对于每个解释，它将生成一个结果列表——图中的有效实体——并且还将返回实体的类型（存在于附件中）。这是非常强大的，因为一旦您知道结果的类型，您就可以进一步过滤、排序或扩展它。对于电影类型结果，您可以按发行年份、电影长度（短片、长片）、语言、奖项等对电影进行排序。这个项目看起来很智能，我们（DH作为这个项目的知识图谱专家）称它为Cerebro，与《X 战警》中出现的设备同名。Cerebro经常揭示一些人们最初没有搜索的非常有趣的事实。比如你搜索[uspresidents]，Cerebro知道总统是人，人是有身高的，所以你可以把总统按身高排序，它会告诉你亚伯拉罕林肯是美国最高的总统。也可以按国籍过滤搜索结果。在这个例子中，它显示了美国和英国，因为美国有一位英国总统——乔治·华盛顿。（免责声明：这个结果是基于当时的KG状态，所以不保证这些结果的正确性。）蓝色链接和知识图谱Cerebro其实是可以真正理解用户查询的。如果图中有数据，则可以为查询生成机器解释和结果列表，并根据对结果的理解进行进一步的探索。如上所述，知道您是在处理电影、人物还是书籍，您可以启用特定的过滤和排序。也可以遍历图表的边缘以显示连接数据，从[美国总统]到[他们去过的学校]，或[他们生的孩子]。DH在另一个名为Parallax(https://vimeo.com/1513562)的项目中展示了从一个结果列表跳转到另一个结果列表的能力。Cerebro令人印象深刻，背后有Metaweb的领导力。甚至图形服务部分也提供了良好的性能和功能。我称它为知识引擎（搜索引擎的升级版），但谷歌管理层（包括我的经理）对它不感兴趣。然后我被告知要和谁谈谈，所以我有机会把它展示给一位高级搜索主管。但是我得到的回应并不是我所希望的。负责人给我看了谷歌搜索[法国作家的书]的结果，结果显示有十个蓝色链接，并坚持谷歌也可以这样做。此外，他们不希望他们网站的流量被抢走，因为那样的话这些网站的所有者肯定会生气。如果您认为他是对的，请考虑一下：Google搜索并不真正了解用户在搜索什么。它只是在正确的相对位置寻找正确的关键字并对页面进行排名。即使它是一个极其复杂的系统，它仍然不能真正理解搜索或搜索结果的含义。***，用户还需要自己查看结果，从中解析提取自己需要的信息，进行进一步的搜索，然后将完整的结果拼凑在一起。例如，对于[法国作者的书籍]的搜索，用户首先需要合并结果列表，这些结果可能不会出现在同一页面上。然后，这些书籍按出版年份排序，或按出版商过滤等——所有这些都需要广泛的链接跟踪、进一步搜索和手动汇总。Cerebro有可能减少这些工作量，使用户交互变得简单高效。然而，这是当时典型的获取知识的方式。管理层不确定知识图谱是否真的有用，或者它如何用于搜索。对于一个已经通过为用户提供大量超链接而获得成功的企业来说，这种获取知识的新途径并不容易理解。经过一年与管理层的磨合，我没有兴趣继续下去。2011年6月，谷歌上海办公室的一位经理找到我，我将项目交给了他。他为这个项目组建了一个由15名工程师组成的团队。我在上海呆了一周，把相关的东西都交给了这个团队的工程师。DH也参与了该项目并长期指导团队。连接深度问题我为Cerebro开发的图形服务系统存在连接深度问题。当查询的后续部分需要前一部分的结果时，将执行连接。典型的连接通常涉及一个SELECT操作，该操作过滤一个公共数据集，获取一些结果，然后使用这些结果过滤数据集的另一部分。我将举例说明。假设您想了解[SF吃寿司的人]，并且人们共享了他们的数据，包括有关谁住在哪个城市以及他们喜欢吃什么食物的信息。上面的查询是单级连接。如果数据库外部的应用程序正在执行此连接，它将执行一个查询，然后执行多个查询（每个结果一个），找出每个人都吃了什么，然后找出谁吃了寿司。第二步有扇出问题。如果第一步有一百万个结果（以旧金山人口为基准），那么第二步就需要把每一个结果都放到一个query中，找出他们的饮食习惯是什么，然后进行过滤。分布式系统工程师通常通过广播来解决这个问题。他们根据分片功能将结果分成批次，然后查询集群中的每个服务器。他们可以通过这种方式加入，但会导致显着的查询延迟。在分布式系统中使用广播不是一个好主意。谷歌大师JeffDean在他的“在大型在线服务中实现快速响应时间”演讲（视频：https://www.youtube.com/watch?v=1-3Ahy7Fxsc，幻灯片：https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44875.pdf）很好地解释了这个问题。查询的总延迟总是大于最慢组件的延迟。随着机器数量的增加，单台机器上的一点点延迟都会显着增加整体查询延迟。假设一台服务器的第50个百分位数延迟为1毫秒，第99个百分位数延迟为1秒。如果查询只涉及一台服务器，则只有1%的请求需要一秒钟。但是如果查询涉及100台服务器，那么63%的请求需要一秒钟。因此，广播会对查询延迟产生不利影响。如果需要两个、三个或更多连接，实时(OLTP)执行可能会很慢。大多数非原生图形数据库都存在这种高扇出广播问题，包括JanusGraph、Twitter的FlockDB和Facebook的TAO。分布式连接是一个大问题。现有的原生图数据库，例如Neo4j，通过将公共数据集保存在一台机器上（独立数据库）并且在连接时不访问其他服务器来避免这个问题。Dgraph：任意深度连接完成Cerebro后，我有了构建图服务系统的经验。然后我加入了Dgraph项目，成为该项目的三位技术负责人之一。Dgraph的设计理念很新颖，解决了连接深度问题。Dgraph以一种非常独特的方式对图形数据进行分片，可以在一台机器上执行连接。回到SPO问题，Dgraph的每个实例将保存与该实例中每个谓词对应的所有主题和对象。一个Dgraph实例将包含多个谓词和完整的谓词。这允许执行任意深度连接，同时避免扇出广播问题。以【SF吃寿司的人】为例，不管集群大小，这个查询最多需要两次网络调用。第一个调用将找到所有住在旧金山的人，第二个调用将与这个列表相交，包括所有吃寿司的人。然后我们可以添加更多约束或扩展，每一步仍然最多涉及一次网络调用。这会导致单个服务器上的谓词非常大，但这可以通过进一步拆分谓词服务器来解决。然而，在最极端的情况下，所有数据只对应一个谓词，那么基于整个集群拆分谓词是一种最坏情况的行为。但在其他情况下，基于谓词的分片数据设计可以在实际系统中实现更低的查询延迟。分片并不是Dgraph的唯一创新。所有对象都分配一个整数ID，然后排序并存储在发布列表中，可以快速与其他发布列表进行交叉。这加快了连接期间的过滤、查找公共引用等。这里也使用了来自GoogleWeb服务系统的一些想法。Google的Dgraph通过Plasma与OneBoxe结合的不是数据库，而是服务系统，相当于Google的Web搜索服务系统。此外，它需要响应实时更新。作为一个实时更新的服务系统，它需要一个实时的图索引系统。我在实时增量索引系统方面也有很多经验，之前曾在Caffeine(https://googleblog.blogspot.com/2010/06/our-new-search-index-caffeine.html)上工作过。后来，我基于这个图索引系统开始了一个新项目，将谷歌所有的OneBox统一起来，包括天气、航班、事件等等。您可能不知道什么是单一框，但您肯定见过它们。单一框是在您运行某些类型的搜索时出现的单独显示框，Google可以在这些显示框中显示更多信息。在开始这个项目之前，每个OneBox都由一个独立的后端提供支持，并由不同的团队维护。他们拥有一组丰富的结构化数据，但这些数据不会在显示器之间共享。不仅维护这些后端需要大量工作，而且缺乏知识共享限制了谷歌可以响应的查询类型。例如，[eventsinSF]可以显示事件，[weatherinSF]可以显示天气，但是如果[eventsinSF]知道正在下雨并且知道事件是在室内还是室外进行，那么它可以显示基于天气（如果下大雨，看电影或听交响乐可能是最好的选择）来过滤（或排序）事件。在Metaweb团队的帮助下，我们将所有数据转换为SPO格式并在一个系统中对其进行索引。我将这个系统命名为Plasma，一个用于Dgraph的实时图索引系统。管理层变动与Cerebro一样，Plasma是一个资金不足但仍在持续增长的项目。***，当管理层意识到OneBoxe将使用这个项目时，他们需要找到“合适的人”来处理这个项目。在这场政治游戏中，我们经历了三次管理层变动，但都没有这方面的经验。在此次管理层变动期间，Spanner（一个全球分布式SQL数据库，需要GPS时钟以实现全球一致性）背后的管理层认为Dgraph过于复杂。***，Dgraph项目被取消，但Plasma幸存下来。一个新的团队接管了这个项目，这个团队的领导直接向CEO汇报。这个新团队（他们确实缺乏对图形相关问题的理解）决定基于Google现有的搜索索引构建一个服务系统（就像我为Cerebro所做的那样）。我建议使用我为Cerebro开发的相同系统，但被拒绝了。我修改了Plasma以爬取每个知识主题并将其扩展几个级别，以便系统可以将其视为网络文档。他们称之为TS（这只是一个首字母缩写词）。这意味着新的服务系统将无法执行深度连接。我看到很多公司的工程师一开始就错误地认为“图实际上是一个简单的问题，可以通过在另一个系统之上构建一层来解决”。几个月后，即2013年5月，我在Dgraph/Plasma项目工作了大约两年后离开了谷歌。背景故事几年后，“网络搜索基础设施”更名为“网络搜索和知识图谱基础设施”，我向其展示Cerebro的那个人正在领导这项工作。他们打算使用知识图作为蓝色链接的替代品——为用户查询提供最直接的答案。当上海的Cerebro团队准备将该项目部署到生产环境时，该项目被谷歌纽约办公室抢走了。***，它更名为“知识带”。如果您搜索[tomhanksmovies]，您会在顶部看到它。自从***发布后，它有所改进，但仍然没有达到Cerebro能够进行过滤和排序的水平。在Dgraph工作的三位技术主管（包括我）最终离开了谷歌。据我所知，另外两位高管现在分别在微软和LinkedIn工作。我获得了两次晋升，如果你算上我离开谷歌时担任高级软件工程师的话，总共是三次。现在的TS版本其实和Cerebro的设计很接近，主谓宾都有索引。所以它仍然存在连接深度问题。Plasma此后被重写和重命名，但仍然是支持TS的实时图形索引系统。他们继续托管Google的所有结构化数据，包括知识图谱。谷歌对于深度连接的无能，在很多地方都可以看到。首先，我们仍然没有看到OneBox之间的数据联合：[亚洲降雨最多的城市]没有生成城市列表，尽管天气和KG数据可用。[SF中的事件]无法按天气过滤，[美国总统]的结果无法进一步排序、过滤或扩展。我怀疑这也是他们停止使用Freebase的原因之一。Dgraph：离开谷歌两年后，我决定重新开始Dgraph（https://github.com/dgraph-io/dgraph）。在谷歌之外，我看到了与原来类似的情况。这个领域有很多半生不熟的自定义解决方案，它们在关系数据库或NoSQL数据库之上匆忙添加一层，或者作为多模型数据库的众多功能之一。如果存在本机解决方案，您将遇到可伸缩性问题。在我看来，在高性能和可扩展设计方面，没有人一路走来。构建具有水平可扩展性、低延迟和任意深度连接的图形数据库非常困难。我希望我们在构建Dgraph时不要走错路。在过去的三年里，Dgraph团队在设计中融入了大量的原始研究，加上我自己的经验，开发出了这个最先进的图数据库。其他公司可以选择这种功能强大、可扩展且高性能的解决方案，而不是另一种半生不熟的解决方案。英文原文：https://blog.dgraph.io/post/why-google-needed-graph-serving-system/
