pos树是什么(前员工揭内幕：10 年了，为何谷歌还搞不定知识图谱？)

近日，前谷歌开发者、现 Dgraph 创始人 Manish Rai Jain 撰文揭秘了谷歌内部在知识图谱领域的探索和发展。他以一个开发和技术前驱者的视角论述了“为什么谷歌需要一个知识图谱系统”，并详细披露了知识图谱在谷歌的探索尝试的历程。虽然由于种种原因，他当时的知识图谱项目最终被放弃，但整个发展探索历程不失为一个非常棒的知识图谱技术学习材料和项目管理经典案例。AI 前线对这篇文章进行了编译，希望能对大家有所帮助。

当我向别人解释我们在 Dgraph 实验室所做的东西时，经常会有人问我是不是曾经在 Facebook 工作过，或者我们正在做的东西是否受到 Facebook 的启发。很多人都知道 Facebook 在社交图服务方面做了大量工作，因为他们发表了多篇关于如何构建图基础设施的文章。

在说到谷歌时，一般仅限于知识图谱服务，但却没有人提到过其内部基础设施是怎么回事。其实谷歌有专门用于提供知识图谱的系统。事实上，我们（在谷歌的时候）在图服务系统方面也做了大量的工作。早在 2010 年，我就冒险进行了两次尝试，看看可以做出些什么东西。

谷歌需要构建一个图服务系统，不仅可以处理知识图数据中的复杂关系，还可以处理所有可以访问结构化数据的 OneBox。服务系统需要遍历事实数据，并具备足够高的吞吐量和足够低的延迟，以应对大量的 Web 搜索。但没有现成可用的系统或数据库能够同时满足这三个要求。

我已经回答了为什么谷歌需要构建一个图服务系统，在本文的其余部分，我将带你回顾我们构建图服务系统的整个旅程。

我是怎么知道这些的？

我先自我介绍一下，2006 年到 2013 年期间，我在谷歌工作。先是实习生，然后是 Web 搜索基础设施的软件工程师。2010 年，谷歌收购了 Metaweb，那时我的团队刚刚推出了 Caffeine。我想做一些与众不同的东西，于是开始与 Metaweb 的人（在旧金山）合作。我的目标是弄清楚如何使用知识图谱来改进 Web 搜索。

Metaweb 的故事

之前已经说过，谷歌在 2010 年收购了 Metaweb。Metaweb 已经使用多种技术构建了一个高质量的知识图谱，包括爬取和解析维基百科。所有这些都是由他们内部构建的一个图数据库驱动的，这个数据库叫作 Graphd——一个图守护程序（现在已经发布在 GitHub 上：

Graphd 有一些非常典型的属性。和守护程序一样，它运行在单台服务器上，所有数据都保存在内存中。Freebase 网站让 Graphd 不堪重负，在被收购之后，谷歌面临的一个挑战是如何继续运营 Freebase。

谷歌在商用硬件和分布式软件领域建立了一个帝国。单台服务器数据库永远无法支撑与搜索相关的爬取、索引和服务工作负载。谷歌先是推出了 SSTable，然后是 Bigtable，可以横向扩展到数百甚至数千台机器，为数 PB 数据提供处理能力。他们使用 Borg（K8s 的前身）来配置机器，使用 Stubby（gRPC 的前身）进行通信，通过 Borg 名称服务解析 IP 地址（BNS，已集成到 K8s 中），并将数据存储在谷歌文件系统（GFS）上。进程可能会死亡，机器可能会崩溃，但系统会一直运转。

Graphd 当时就处在这样的环境中。使用单个数据库为运行在单台服务器上的网站提供服务，这种想法与谷歌（包括我自己）的风格格格不入。特别是，Graphd 需要 64GB 或更多的内存才能运行。如果你认为这样的内存要求很搞笑，那么请注意，那是在 2010 年。当时大多数谷歌服务器的最大内存为 32GB，所以谷歌必须购买配备足够多内存的特殊机器来支持 Graphd。

替换 Graphd

有关替换或重写 Graphd 并让它支持分布式的想法开始冒了出来，但这对于图数据库来说是一件非常困难的事情。它们不像键值数据库那样，可以将一大块数据移动到另一台服务器上，在查询时提供键就可以了。图数据库承诺的是高效的连接和遍历，需要以特定的方式来实现。

其中的一个想法是使用一个叫作 MindMeld（IIRC）的项目。这个项目承若通过网络硬件可以更快地访问另一台服务器内存。这应该比正常的 RPC 要快，快到足以伪复制内存数据库所需的直接内存访问。但这个想法并没有走得太远。

另一个想法（实际上是一个项目）是构建一个真正的分布式图服务系统，不仅可以取代 Graphd，还可以为将来的所有知识提供服务。它就是 Dgraph——一种分布式图守护程序。

Dgraph 实验室和开源项目 Dgraph 的命名就是从谷歌的这个项目开始的。

当我在本文中提到 Dgraph 时，指的是谷歌的内部项目，而不是我们后来构建的开源项目。

Cerebro 的故事：一个知识引擎

虽然我知道 Dgraph 的目标是要取代 Graphd，但我的目标却是做出一些东西来改进 Web 搜索。我在 Metaweb 找到了一位研究工程师 DH，Cubed（就是他开发的。

谷歌纽约办公室的一些工程师开发了 Squared（ 则更进一步，开发了 Cubed。虽然 Squared 没有什么用，但 Cubed 却令人印象深刻。我开始想如何也在谷歌开发一个这样的东西，毕竟谷歌已经有一些现成的东西可以利用。

首先是一个搜索项目，它提供了一种方法，可用于高度准确地分辨哪些单词应该合在一起。例如，对于 [tom hanks movies] 这样的短语，它会告诉你 [tom] 和 [hanks] 应该合在一起。同样，在 [san francisco weather] 这个短语中，[san] 和 [francisco] 应该合在一起。对于人类而言，这些都是显而易见的事情，但对机器来说可不是这么回事。

第二个是理解语法。在查询 [books by french authors] 时，机器可以将其解释成由 [french authors] 所写的 [books]（即法国作家所著的书籍）。但它也可以被解释成 [authors] 所写的 [french books]（即作家所著的法语书籍）。我使用了斯坦福的词性（POS）标记器来更好地理解语法，并构建了语法树。

第三个是理解实体。[french] 可以指很多东西，它可以是指国家（地区）、国籍（法国人）、菜肴（指食物）或语言。我使用了另一个项目来获取单词或短语所对应的实体列表。

第四个是理解实体之间的关系。现在我已经知道如何将单词关联成短语、短语的执行顺序，即语法，以及它们对应的实体，我还需要一种方法来找到这些实体之间的关系，以便创建机器解释。例如，对于查询 [books by french authors]，POS 会告诉我们，它指的是 [french authors] 所著的 [books]。我们有一些 [french] 的实体和 [authors] 的实体，算法需要确定如何连接它们。它们可以通过出生地连接在一起，即出生在法国的作家（但可能使用英文写作），或者是法国藉的作家，或者说法语或使用法语写作（但可能与法国无关）的作家，或者只是喜欢法国美食的作家。

基于搜索索引的图系统

为了确定某些实体是否是连接在一起的，以及是如何连接在一起的，我需要一个图系统。知识图谱数据使用了三元组的格式，即每个事实通过三个部分来表示，主语（实体）、谓词（关系）和宾语（另一个实体）。查询必须是 [S P]→[O]、[P O]→[S]，有时候是 [S O]→[P]。

我使用了谷歌的搜索索引系统，为每个三元组分配了一个 docid，并构建了三个索引，分别为 S、P 和 O。另外，索引允许附带附件，所以我附上了每个实体的类型信息。

我构建了这个图服务系统，知道它有连接深度问题（下面会解释），并且不适用于复杂的图查询。事实上，当 Metaweb 团队的某个人要求我开放系统访问时，被我拒绝了。

现在，为了确定关系，我会执行一些查询，看看会产生哪些结果。[french] 和 [author] 会产生什么结果吗？选择这些结果，并看看它们如何与 [books] 连接在一起。这样会生成多个机器解释。例如，当你查询 [tom hanks movies] 时，它会生成 [movies directed by tom hanks]、[movies starring tom hanks]、[movies produced by tom hanks] 这样的解释，并自动拒绝像 [movies named tom hanks] 这样的解释。

对于每一个解释，它将生成一个结果列表——图中的有效实体——并且还将返回实体的类型（存在于附件中）。这个功能非常强大，因为在了解了结果的类型后，就可以进行过滤、排序或进一步扩展。对于电影类型的结果，你可以按照发行年份、电影的长度（短片、长片）、语言、获奖情况等对电影进行排序。

这个项目看起来很智能，我们（DH 作为这个项目的知识图谱专家）将它叫作 Cerebro，与《X 战警》中出现的设备同名。

Cerebro 经常会展示出一些人们最初没有搜索过的非常有趣的事实。例如，如果你搜索 [us presidents]，Cerebro 知道总统是人类，而人类会有身高，你就可以按照身高对总统进行排序，然后会告诉你 Abraham Lincoln 是美国身高最高的总统。还可以通过国籍来过滤搜索结果。在这个例子中，它显示的是美国和英国，因为美国有一位英国人总统——George Washington。（免责声明：这个结果是基于当时的 KG 状态，所以不保证这些结果的正确性。）

蓝色链接与知识图谱

Cerebro 其实是有可能真正理解用户的查询的。如果图中有数据，就可以为查询生成机器解释和结果列表，并根据对结果的理解进行进一步的探索。如上所述，在知道了正在处理的是电影、人类或书籍之后，就可以启用特定的过滤和排序功能。还可以遍历图的边来显示连接数据，从 [us presidents] 到 [schools they went to]，或者 [children they fathered]。DH 在另一个叫作 Parallax（的项目中演示了从一个结果列表跳转到另一个结果列表的能力。

Cerebro 令人印象深刻，Metaweb 的领导层也很支持它。即使是图服务部分也提供了较好的性能和功能。我把它叫作知识引擎（搜索引擎的升级），但谷歌管理层（包括我的经理）对此并不感兴趣。后来，有人告诉我应该去找谁沟通这件事，于是我才有机会向搜索方面的一位高级负责人展示它。

但得到的回应并不是我所希望的那样。这位负责人向我展示了使用谷歌搜索 [books by french authors] 的结果，其中显示了十个蓝色链接，并坚持说谷歌可以做同样的事情。此外，他们不希望网站的流量被抢走，因为那样的话这些网站的所有者肯定会生气。

如果你认为他是对的，那么请想一下：谷歌搜索其实并不能真正理解用户搜索的是什么。它只会在正确的相对位置查找正确的关键字，并对页面进行排名。尽管它是一个极其复杂的系统，但仍然不能真正理解搜索或搜索结果意味着什么。最后，用户还需要自己查看结果，并从中解析和提取他们需要的信息，并进行进一步的搜索，然后将完整的结果组合在一起。

例如，对于 [books by french authors] 这个搜索，用户首先需要对结果列表进行组合，而这些结果可能不会出现在同一个页面中。然后按照出版年份对这些书籍进行排序，或者按照出版社等条件进行过滤——所有这些都需要进行大量的链接跟踪、进一步的搜索和手动聚合。Cerebro 有可能可以减少这些工作量，让用户交互变得简单而完美。

然而，这在当时是一种典型的获取知识的方法。管理层不确定知识图谱是否真的有用，或者不确定如何将其用在搜索中。对于一个已经通过向用户提供大量超链接而取得成功的企业来说，这种获取知识的新途径并不容易理解。

在与管理层磨合了一年之后，我没有兴趣再继续下去了。2011 年 6 月，谷歌上海办公室的一位经理找到我，我把项目交给了他。他为这个项目组建了一个由 15 名工程师组成的团队。我在上海呆了一个星期，把相关的东西都移交给了这个团队的工程师。DH 也参与了这个项目，并长期指导团队。

连接深度问题

我为 Cerebro 开发的图服务系统存在连接深度问题。当一个查询的后续部分需要用到前面部分的结果时，就需要执行连接。典型的连接通常涉及到 SELECT 操作，即对通用数据集进行过滤，获得某些结果，然后使用这些结果来过滤数据集的另一部分。我将用一个例子来说明。

假设你想知道 [people in SF who eat sushi]，而且人们已经分享了他们的数据，包括谁住在哪个城市以及他们喜欢吃哪些食物的信息。

上面的查询是一个单级连接。如果数据库外部的应用程序正在执行这个连接，它将先执行一个查询，然后再执行多个查询（每个结果一个查询），找出每个人都吃些什么，然后挑选出吃寿司的人。

第二步存在扇出（fan-out）问题。如果第一步有一百万个结果（基于旧金山人口），那么第二步需要将每个结果放入查询中，找出他们的饮食习惯，然后进行过滤。

分布式系统工程师通常会通过广播来解决这个问题。他们根据分片函数将结果分成多个批次，然后查询集群中的每一台服务器。他们可以通过这种方式实现连接，但会导致严重的查询延迟。

在分布式系统中使用广播并不是个好主意。谷歌大牛 Jeff Dean 在他的“Achieving Rapid Response Times in Large Online Services”演讲（视频：幻灯片：中很好地解释了这个问题。查询的总延迟总是大于最慢组件的延迟。单台机器的一丁点延迟会随着机器数量的增多而戏剧性地增加查询总延迟。

想象一下，有一台服务器，它的 50 百分位延迟为 1 毫秒，99 百分位延迟为 1 秒。如果查询只涉及一台服务器，那么只有 1％的请求会占用一秒钟时间。但如果查询涉及 100 台服务器，那么就会有 63％的请求占用一秒钟时间。

因此，广播会给查询延迟带来不利的影响。如果需要进行两次、三次或更多次的连接，对于实时（OLTP）执行来说就会显得很慢。

大多数非原生图数据库都存在这种高扇出广播问题，包括 Janus Graph、Twitter 的 FlockDB 和 Facebook 的 TAO。

分布式连接是一个大难题。现有的原生图数据库通过将通用数据集保存在一台机器（独立数据库）上，并在连接时不访问其他服务器来避免这个问题，如 Neo4j。

Dgraph：任意深度连接

在结束 Cerebro 之后，我拥有了构建图服务系统的经验。随后，我加入了 Dgraph 项目，成为该项目的三位技术主管之一。Dgraph 的设计理念非常新颖，并解决了连接深度问题。

Dgraph 以一种非常独特的方式对图数据进行分片，可以在单台机器上执行连接。回到 SPO 这个问题上，Dgraph 的每个实例都将保存与该实例中的每个谓词相对应的所有主语和宾语。Dgraph 实例将保存多个谓词和完整的谓语。

这样就可以执行任意深度的连接，同时避免了扇出广播问题。以 [people in SF who eat sushi] 为例，不管集群大小是怎样的，这个查询最多需要两次网络调用。第一次调用会找到所有住在旧金山的人，第二次调用会将这个名单与所有吃寿司的人进行交集操作。然后我们可以添加更多约束或扩展，每个步骤仍然会涉及最多一次网络调用。

这导致了单台服务器上的谓语会变得非常大，不过可以通过进一步拆分谓语服务器来解决这个问题。但是，在最极端的情况下，即所有数据只对应一个谓语，那么基于整个集群拆分谓语是一种最糟糕的行为。但在其他情况下，基于谓语对数据进行分片的设计可以在实际系统中实现更低的查询延迟。

分片并不是 Dgraph 的唯一创新。所有的宾语都被分配了一个整型 ID，然后经过排序，保存在倒排列表中，可以与其他倒排列表进行快速的交集操作。这样可以加快连接期间的过滤、查找公共引用等操作。这里还使用了谷歌 Web 服务系统的一些想法。

通过 Plasma 联合 OneBoxe

谷歌的 Dgraph 并不是一个数据库，而是一个服务系统，相当于谷歌的 Web 搜索服务系统。此外，它需要对实时更新做出响应。作为一个实时更新的服务系统，它需要一个实时的图索引系统。因为之前参与过 Caffeine（的工作，所以我在实时增量索引系统方面也拥有了很多经验。

后来我又启动了一个新项目，基于这个图索引系统将谷歌所有的 OneBox 联合在一起，包括天气、航班、事件，等等。你可能不知道 OneBox 是什么，但你肯定见过它们。OneBox 是单独的显示框，会在运行某些类型的搜索时出现，谷歌可以在这些显示框中显示更多的信息。

在开始这个项目之前，每个 OneBox 由独立的后端提供支持，并由不同的团队负责维护。它们有一组丰富的结构化数据，但显示框之间并不会共享这些数据。维护这些后端不仅涉及大量的工作，而且因为缺乏知识共享，限制了谷歌能够响应的查询类型。

例如，[events in SF] 可以显示事件，[weather in SF] 可以显示天气，但如果 [events in SF] 知道当时在下雨，并且知道事件是在室内还是在室外进行，那么它就可以根据天气（如果下暴雨，看电影或听交响乐可能是最好的选择）对事件进行过滤（或排序）。

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

管理层变动

与 Cerebro 一样，Plasma 也是一个缺乏资金支持的项目，但仍在继续成长。最后，当管理层意识到 OneBoxe 即将使用这个项目时，他们需要找到“合适的人”负责这方面的工作。在这场政治游戏中，我们经历了三次管理层变动，但他们都没有这方面的经验。

在这次管理层变动过程中，支持 Spanner（一个全球分布式 SQL 数据库，需要 GPS 时钟来确保全球一致性）的管理层认为 Dgraph 过于复杂。

最后，Dgraph 项目被取消了，不过 Plasma 幸免于难。一个新团队接管了这个项目，这个团队的负责人直接向首席执行官汇报。这个新团队（他们其实对与图相关的问题缺乏了解）决定构建一个基于谷歌现有搜索索引的服务系统（就像我为 Cerebro 所做的那样）。我建议使用我为 Cerebro 开发的那个系统，但被拒绝了。我修改了 Plasma，让它爬取并将每个知识主题扩展出几个级别，这个系统就可以将其视为一个 Web 文档。他们称之为 TS（这只是个缩写）。

这意味着新的服务系统将无法执行深度连接。我看到很多公司的工程师们在一开始就错误地认为“图实际上是一个很简单的问题，可以通过在另一个系统之上构建一个层来解决”。

几个月之后，也就是 2013 年 5 月，我离开了谷歌，那个时候我在 Dgraph/Plasma 项目上大约已经工作了两年时间。

后面的故事几年后，“Web 搜索基础设施”被重命为“Web 搜索和知识图谱基础设施”，之前我向他演示 Cerebro 的那个人负责领导这方面的工作。他们打算使用知识图谱替代蓝色链接——尽可能为用户查询提供最直接的答案。当上海的 Cerebro 团队即将在生产环境中部署这个项目时，项目却被谷歌纽约办公室抢走了。最后，它改头换面成了“Knowledge Strip”。如果你搜索 [tom hanks movies]，会在顶部看到它。自首次发布以来，它有了一些改进，但仍然无法达到 Cerebro 能够提供的过滤和排序水平。

参与 Dgraph 工作的三位技术主管（包括我）最终都离开了谷歌。据我所知，其他两位主管现在正在微软和 LinkedIn 工作。我获得了两次晋升，如果算上当时我以高级软件工程师的身份离开谷歌，总共是三次。当前版本的 TS 实际上非常接近 Cerebro 的设计，主语、谓语和宾语都有一个索引。因此，它仍然存在连接深度问题。此后，Plasma 被重写和改名，但仍然是一个支持 TS 的实时图索引系统。它们继续托管着谷歌的所有结构化数据，包括知识图谱。谷歌在深度连接方面的无能为力在很多地方都可以看出来。首先，我们仍然没有看到 OneBoxe 之间的数据联合：[cities by most rain in asia] 并不会生成城市列表，尽管天气和 KG 数据是可用的。[events in SF] 无法根据天气进行过滤，[US presidents] 的结果不能进行进一步的排序、过滤或扩展。我怀疑这也是他们停止使用 Freebase 的原因之一。Dgraph：凤凰涅槃

离开谷歌两年之后，我决定重新开始 Dgraph（在谷歌之外，我看到了与当初类似的情况。这个领域有很多不成熟的自定义解决方案，他们匆匆茫茫地在关系型数据库或 NoSQL 数据库之上添加了一个层，或者将其作为多模型数据库的众多功能之一。如果存在原生解决方案，会遇到可伸缩性问题。

在我看来，没有人能够在高性能和可伸缩设计方面一路走下去。构建一个具备水平可伸缩性、低延迟且可进行任意深度连接的图数据库是一件非常困难的事情。我希望我们在构建 Dgraph 这件事情上不会走错路。

在过去的三年里，除了我自己的经验，Dgraph 团队还在设计中加入了大量原创研究，开发出了这款无与伦比的图数据库。其他公司可以选择这个强大、可伸缩且高性能的解决方案，而不是另一个不成熟的解决方案。