[转载] Google大数据引擎Dremel剖析(1)

原文: https://mp.weixin.qq.com/s?__biz=MjM5NzAyNTE0Ng==&mid=207895956&idx=1&sn=58e8af26fd3c6025acfa5bc679d2ab01&scene=1&srcid=0919Sz0SAs6DNlHTl7GYxrGW&key=dffc561732c2265121a47642e3bebf851225841a00d06325b09e7d125978a26d60870026c28e5375d5f6f3dd479d73bb&ascene=0&uin=Mjk1ODMyNTYyMg%3D%3D&devicetype=iMac+MacBookPro11%2C4+OSX+OSX+10.10.5+build(14F27)&version=11020201&pass_ticket=VWw5L3fXKRxnYGILAFOTg%2B5jK7t%2FJb5MZ3fNO4RAu2kqv%2FWZS4bYH3n6XCZyy9NX

[译者注]从头到尾读懂一篇国外经典技术论文！相信这是很多技术爱好者一直以来想干的事情。本系列译文的目标是满足广大技术爱好者对原始论文一窥究竟的需求，尽量对原文全量翻译。原始论文中不乏较晦涩的学术性语句，也可能会有您不感兴趣的段落，所以译者会添加【译者预读】【译者总结】等环节帮助大家选择性的阅读，或者帮助读者总结。根据译者的翻译过程，论文中也难免缺少细节的推导过程（Google的天才们总是把我们想的跟他们一样聪明），遂添加特殊的【译者YY】环节，根据译者的理解对较为复杂的内容进行解释和分析，此部分主观性很大难免有误，望读者矫正。所有非原文内容皆以蓝色文字显示。

废话不多说，大家一览为快吧！

【译者预读】此篇是伴随着Dremel神话横空出世的原始论文（不知道Dremel的读者可以立刻搜索感受一下Dremel的强大）。文章深入分析了Dremel是如何利用巧妙的数据存储结构+分布式并行计算，实现了3秒查询1PB的神话。

论文的前几部分是“abstract”、“introduction”、“background”，介绍性的文字较多，其核心意思是：面对海量数据的分析处理，MR（MapReduce）的优势不需多言，其劣势在于时效性较差不满足交互式查询的需求，比如3秒内完成对万亿数据的一次查询等，Dremel应此需求而生，与MR成为有效互补。

摘要

Dremel是一个用于分析只读嵌套数据的可伸缩、交互式ad-hoc查询系统。通过结合多层级树状执行过程和列状数据结构，它能做到几秒内完成万亿行数据之上的聚合查询。此系统可伸缩至成千上万的CPU和PB级别的数据，而且在google已有几千用户。在本篇论文中，我们将描述Dremel的架构和实现，解释它为何是MapReduce计算的有力互补。我们提供一种嵌套记录的列状存储结构，并且讨论在拥有几千个节点的系统上进行的实验。

1. 介绍

大规模分析型数据处理在互联网公司乃至整个行业中都已经越来越广泛，尤其是因为目前已经可以用廉价的存储来收集和保存海量的关键业务数据。如何让分析师和工程师便捷的利用这些数据也变得越来越重要；在数据探测、监控、在线用户支持、快速原型、数据管道调试以及其他任务中，交互的响应时间一般都会造成本质的区别。
执行大规模交互式数据分析对并行计算能力要求很高。例如，如果使用普通的硬盘，希望在1秒内读取1TB压缩的数据，则需要成千上万块硬盘。相似的，CPU密集的查询操作也需要运行在成千上万个核上。在Google，大量的并行计算是使用普通PC组成的共享集群完成的[5]。一个集群通常会部署大量共享资源的分布式应用，各自产生不同的负载，运行在不同硬件配置的机器上。一个分布式应用的单个工作任务可能会比其他任务花费更多的时间，或者可能由于故障或者被集群管理系统取代而永远不能完成。因此，处理好异常、故障是实现快速执行和容错的重要因素[10]。
互联网和科学计算中的数据经常是独立的、互相没有关联的。因此，在这些领域一个灵活的数据模型是十分必要的。在编程语言中使用的数据结构、分布式系统之间交换的消息、结构化文档等等，都可以用嵌套式表达法来很自然的描述。规格化、重新组合这些互联网规模的数据通常是代价昂贵的。嵌套数据模型成为了大部分结构化数据在Google处理的基础[21]，据报道也在其他互联网公司被使用。
这篇论文描述了一个叫做Dremel的系统，它支持在普通PC组成的共享集群上对超大规模的数据集合执行交互式查询。不像传统的数据库，它能够操作原位嵌套数据。原位意味着在适当的位置访问数据的能力，比如，在一个分布式文件系统（比如GFS[14]）或者其他存储层（比如Bigtable[8]）。查询这些数据一般需要一系列的MapReduce（MR[12]）任务，而Dremel可以同时执行很多，而且执行时间比MR小得多。Dremel不是为了成为MR的替代品，而是经常与它协同使用来分析MR管道的输出或者创建大规模计算的原型系统。
Dremel自从2006就投入生产了并且在Google有几千用户。多种多样Dremel的实例被部署在公司里，排列着成千上万个节点。使用此系统的例子包括：

• 分析网络文档

• 追踪Android市场应用程序的安装数据

• Google产品的崩溃报告分析

• Google Books的OCR结果

• 垃圾邮件分析

• Google Maps里地图部件调试

• 托管Bigtable实例中的Tablet迁移

• Google分布式构建系统中的测试结果分析

• 成百上千的硬盘的磁盘IO统计信息

• Google数据中心上运行的任务的资源监控

• Google代码库的符号和依赖关系分析

Dremel基于互联网搜索和并行DBMS的概念。首先，它的架构借鉴了用在分布式搜索引擎中的服务树概念[11]。就像一个web搜索请求一样，查询请求被推入此树、在每个步骤被重写。通过聚合从下层树节点中收到的回复，不断装配查询的最终结果。其次，Dremel提供了一个高级、类SQL的语言来表达ad-hoc查询。与Pig[18]和Hive[16]不同，它使用自己技术执行查询，而不是翻译为MR任务。

最后也是最重要的，Dremel使用了一个column-striped的存储结构，使得它能够从二级存储中读取较少数据并且通过更廉价的压缩减少CPU消耗。列存储曾被采用来分析关系型数据[1]，但是据我们了解还没有推广到嵌套数据模型上。我们所展现的列状存储格式在Google已经有很多数据处理工具支持，包括MR、Sawzall[20]、以及FlumeJava[7]。

在本论文中我们做了如下贡献：

• 我们描述了一个嵌套数据的列状存储格式。并且提供了算法，将嵌套记录解剖为列结构，在查询时重新装配它们（第4章节）。

• 我们描述了Dremel的查询语言和执行过程。两者都被定制化设计，能够在column-striped的嵌套数据上高效执行，不需要装载原始嵌套记录（章节5）。

• 我们展示了在web搜索系统中使用的树状执行过程如何被适用到数据库处理，并且解释他们的优劣，以及如何做到高效聚合查询（章节6）。

• 我们在万亿记录、TB级别的数据集合上进行实验，系统实例拥有1000-4000个节点[章节7]。

这篇论文结构如下。章节2中我们解释了Dremel如何结合其他数据管理工具进行数据分析。它的数据模型在章节3介绍。上述主要贡献覆盖在章节4-8。相关工作在章节9讨论。章节10是总结。

2. 背景

作为开始我们来看一个场景，这个场景说明了交互式查询处理的必要性，以及它在数据管理生态系统上怎么定位。假设一个Google的员工Alice，诞生了一个新奇的灵感，她想从web网页中提取新类型的signals。她运行一个MR任务，分析输入数据然后产生这种signals的数据集合，在分布式文件系统上存储这数十亿条记录。为了分析她实验的结果，她启动Dremel然后执行几个交互式命令：

DEFINE TABLE t AS /path/to/data/*
SELECT TOP(signal1, 100), COUNT(*) FROM t

她的命令只需几秒钟就执行完毕。她也运行了几个其他的查询来证实她的算法是正确的。她发现signal1中有非预期的情况于是写了个FlumeJava[7]程序执行了一个更加复杂的分析式计算。一旦这个问题解决了，她建立一个管道，持续的处理输入数据。然后她编写了一些SQL查询来跨维度的聚合管道的输出结果，然后将它们添加到一个交互式的dashboard，其他工程师能非常快速的定位和查询它。
上述案例要求在查询处理器和其他数据管理工具之间互相操作。第一个组成部分是一个通用存储层。Google File System（GFS[14]）是公司中广泛使用的分布式存储层。GFS使用冗余复制来保护数据不受硬盘故障影响，即使出现掉队者（stragglers）也能达到快速响应时间。对原位数据管理来说，一个高性能的存储层是非常重要的。它允许访问数据时不消耗太多时间在加载阶段。这个要求也导致数据库在分析型数据处理中[13]不太被使用。另外一个好处是，在文件系统中能使用标准工具便捷的操作数据，比如，迁移到另外的集群，改变访问权限，或者基于文件名定义一个数据子集。

第二个构建互相协作的数据管理组件的要素，是一个共享的存储格式。列状存储已经证明了它适用于扁平的关系型数据，但是使它适用于Google则需要适配到一个嵌套数据模型。图1展示了主要的思想：一个嵌套字段比如A.B.C，它的所有值被连续存储。因此，A.B.C被读取时，不需读取A.E、A.B.D等等。我们面临的挑战是如何保护所有的结构化信息，并且能够按任意字段子集来重建记录。下一步我们讨论数据模型，然后是算法和查询处理。

【译者总结】前几部分最需要关注的其实是图1中的嵌套数据和列状存储格式（columnar representatin of nested data）。这是Dremel提升性能的核心理论，而作者没有对此图着重强调，其实对图1右边列状存储的理解是攻克此篇论文的关键。

3.数据模型

【译者预读】有经验的程序员都知道理解一个系统的第一步就是理解它的数据模型，所以此章节可称之为论文最核心的部分之一。其数学公式对于广大coder不很直观，但其实并不复杂，就如图2中描述的结构一样，本质上和JSON、XML描述的数据结构没有区别，就是一种嵌套的、定制化的数据结构。需要着重理解的是在下面章节会频繁使用的几个名词和基础知识。比如记录（record）、字段（field）、列（column）等。记录（record）就是指一条完整的嵌套数据，如果是在DB中一条记录就是一行（row）数据。字段和列在大部分情况下指的是同一个概念，比如图2中Name、Language等，它们是结构中的一个字段（field），将来存储时就是一个列（column）。比如在Google里爬虫抓来的一个网页（Document）的数据就是一条记录，而将其结构化之后其中的Forward链接、Url就是字段（或列）。所谓的列状存储其实就是将原始记录按字段切分，各个字段的数据独立集中存储（比如将所有记录中Name.Url这一列的值放在一起存储）。另外需要注意的是字段的类型，每个字段都属于某种类型，比如required，表示有且仅有一个值；optional，表示可选，0到1个值；repeated（*），表示重复，0到N个值，等。其中repeated和optional类型是非常重要的，作者会从它们身上抽象出一些重要的概念，以便用最少的代价来无损的描述出原始的数据。最后还需要补充两个术语，一是column-stripe，表示图1右边按列存储的一堆列值（列“条”，某个列下顺序存储的一长条数据）；另一个是在论文中广泛使用的路径表达式，xxx.xxx.xxx，其作用类似于XML中的XPath，比如Name.Language.Code，就表示图2中的code字段，因为是在树状结构中，用这样的path能够准确的描述其位置。

在此章节中我们介绍Dremel的数据模型以及一些后续将会用到的术语。这个在分布式系统中经常面对的数据模型(‘Protocol Buffers’[21]）在Google使用广泛，也提供了开源实现。这个数据模型是基于强类型嵌套记录的。它的抽象语法是：

π = dom | <A1 : π [*|?],…,An : π [*|?]>

π是一个原子类型（一个int、一个string…比如DocId）或者记录类型（指向一个子结构，比如Name）。在dom中原子类型包含整型、浮点数、字符串等等。记录则由一到多个字段组成。字段i在一个记录中命名为Ai，以及一个标签（比如(?)或(*),指明该字段是可选的或重复的…）。重复字段（*）表示在一个记录中可能出现多次，是多个值的列表，字段出现的顺序是非常重要的。可选字段(?)可能在记录中不出现。如果不是重复字段也不是可选字段，则该字段在记录中必须有值，有且仅有一个。

图2进行了举例说明。它描述了一个叫Document的schema，表示一个网页。schema定义使用了[21]中介绍的具体语法。一个网页文档必有整型DocId和可选的Links属性，包含Forward和Backword列表，列表中每一项代表其他网页的DocId。一个网页能有多个名字Name，表示不同的URL。名字包含一系列Code和（可选）Country的组合（也就是Language）。图2也展现了两个示例记录，r1和r2，遵循上述schema。我们将使用这些示例记录来解释下一章节涉及到的算法。schema的字段定义按照树状层级。一个嵌套字段的完整路径使用简单的点缀符号表示，如，Name.Language.Code。
嵌套数据模型为Google的序列化、结构化数据奠定了一个平台无关的可扩展机制。而且有为C++、Java等语言打造的代码生成工具。通过使用标准二进制on-the-wire结构，实现跨语言互操作性，字段值按它们在记录中出现的次序被顺序的陈列。这样一来，一个Java编写的MR程序能利用一个C++库暴露的数据源。因此，如果记录被存储在一个列状结构中，快速装配就成为了MR和其他数据处理工具之间互操作性的重要因素。

4. 嵌套列状存储

如图1所示，我们目标是连续的存储一个字段的所有值来改善检索效率。在本章节中，我们面对下列挑战：一个列状格式记录的无损表示（章节4.1），快速encoding（章节4.2），高效的记录装配（章节4.3）。

4.1 重复深度、定义深度

只有字段值不能表达清楚记录的结构。给出一个重复字段的两个值，我们不知道此值是按什么‘深度’被重复的（比如，这些值是来自两个不同的记录，还是相同的记录中两个重复的值）。同样的，给出一个缺失的可选字段，我们不知道整个路径有多少字段被显示定义了。因此我们将介绍重复深度和定义深度的概念。图3概述了所有原子字段的重复和定义深度以供参考。

【译者注】读者请重新审视一下图1右边的列状存储结构，这是Dremel的目标，它就是要将图2中Document那种嵌套结构转变为列状存储结构。要实现这个目标的方式多种多样，而此章节中Dremel信心满满的推出了它设计的最优化、最节省成本、效率最高的方法，并且引出了两个全新的概念，重复深度和定义深度。因为Dremel会将记录肢解、再按列各自集中存储，此举难免会导致数据失真，比如图2中，我们把r1和r2的URL列值放在一起得到[“http://A”,"http://B","http://C"]，那怎么知道它们各自属于哪条记录、属于记录中的哪个Name…这里提出的两个深度概念其实就是为了解决此失真问题，实现无损表达。

【译者YY】在翻译上面一段文字的译者其实感觉很突兀，原文作者试图摆出一个难题来引发读者的思考（只有一个赤裸裸的字段值如何弄清楚它所属的记录和结构），但是像我这样按部就班的人，读到这里脑子里思考的是一些更浅显的问题。上面论文中虽然提到“列状存储已经证明了它适用于扁平的关系型数据”、“Dremel希望按字段连续的存储所有值来提升检索效率”，但都是一笔带过，没有详述这么做为何能提升检索效率？提升检索效率的方法多种多样，这么做是不是唯一的、最好的方法？Dremel作者是怎么一步步想到这个方法的（不要告诉我就是灵光一现、一挥而就的）？作者之所以省略，应该是有其他论文早就证明、推导过列状存储的优势和诞生过程。但在此文中直接将其面临的细节问题搬上台面，引出两个陌生的深度概念，不禁略显突兀，让人困惑。这里会先保留这些困惑，直译原文，在此节结束的译者YY环节，译者将尝试与拥有同样困惑的读者一起，YY一下个中奥妙。

重复深度。注意在图2中的Code字段。可以看到它在r1出现了3次。‘en-us’、‘en’在第一个Name中，而‘en-gb’在第三个Name中。结合了图2你肯定能理解我上一句话并知道‘en-us’、‘en’、‘en-gb’出现在r1中的具体位置，但是不看图的话呢？怎么用文字，或者说是一种定义、一种属性、一个数值，诠释清楚它们出现的位置？这就是重复深度这个概念的作用，它能用一个数字告诉我们在路径中的什么重复字段，此值重复了，以此来确定此值的位置（注意，这里的重复，特指在某个repeated类型的字段下“重复”出现的“重复”）。我们用深度0表示一个纪录的开头（虚拟的根节点），深度的计算忽略非重复字段（标签不是repeated的字段都不算在深度里）。所以在Name.Language.Code这个路径中，包含两个重复字段，Name和Language，如果在Name处重复，重复深度为1（虚拟的根节点是0，下一级就是1），在Language处重复就是2，不可能在Code处重复，它是required类型，表示有且仅有一个；同样的，在路径Links.Forward中，Links是optional的，不参与深度计算（不可能重复），Forward是repeated的，因此只有在Forward处重复时重复深度为1。现在我们从上至下扫描纪录r1。当我们遇到’en-us’，我们没看到任何重复字段，也就是说，重复深度是0。当我们遇到‘en’，字段Language重复了（在‘en-us’的路径里已经出现过一个Language），所以重复深度是2.最终，当我们遇到’en-gb‘，Name重复了（Name在前面‘en-us’和‘en’的路径里已经出现过一次，而此Name后Language只出现过一次，没有重复），所以重复深度是1。因此，r1中Code的值的重复深度是0、2、1.

【译者注】树的深度很好理解，根节点是0，下一级就是1，再下一级就是2，依次类推。但重复深度有所不同，它skip掉了所有非repeated类型的字段，也就是说只有repeated类型才能算作一级深度。这么做的原因是在已知schema的情况下，对于重复深度这个值而言，只需要repeated类型的参与就够了（够下面的split和装配算法所需了），没必要按照完整的schema树来计算深度值。

要注意第二个Name在r1中没有包含任何Code值。为了确定‘en-gb’出现在第三个Name而不是第二个，我们添加一个NULL值在‘en’和‘en-gb’之间（如图3所示）。在Language字段中Code字段是必须值，所以它缺失意味着Language也没有定义。一般来说，确定一个路径中有哪些字段被明确定义需要一些额外的信息，也就是接下来介绍的定义深度。。

定义深度。路径p中一个字段的每个值，尤其是NULL，都有一个定义深度，说明了在p中有多少个可选字段实际上是有值的。例如，我们看到r1没有Backward链接，而link字段是定义了的（在深度1）。为了保护此信息，我们为Links.Backward列添加一个NULL值，并设置其定义深度为1。相似的，在r2中Name.Language.Country定义深度为1，而在r1中分别为2（‘en’处）和1（‘http://B’处）。

定义深度使用整型而不是简单的is-null二进制位，这样叶子节点的数据（比如，Name.Language.Country）才能包含足够的信息，指明它父节点出现的情况；在章节4.3给出了使用该信息的具体例子。

【译者注】定义深度从某种意义上是服务于重复深度的。在论文中其实有一个非常重要的理论介绍的不是很明显，只是简单的用sequentially、contiguously这样的单词带过。这个理论就是在图1右边的列状存储中，所有列都是先存储r1，后存储r2，也就是说对所有的列，记录存储的顺序是一致的。这个顺序就像所有列值都包含的一个唯一主键，逻辑上能够将被肢解出来的列值串在一起，知道它们属于同一条记录，这也是保证记录被拆分之后不会失真的一个重要手段。既然顺序是十分必要的不能失真的因素，那当某条记录的某一列的值为空时就不能简单的跳过，必须显式的为其存储一个NULL值，以保证记录顺序有效。而NULL值本身能诠释的信息不够，比如记录中某个Name.Language.Country列为空，那可能表示Country没有值（如‘en’），也可能表示Language没有值（如‘http://B’），这两种情况在装配算法中是需要区分处理的，不能失真，所以才需要引出定义深度，能够准确描述出此信息。

上面大概提到的encoding保证了record的结构是无损的。这个比较好理解，此处就不过多介绍证明过程了。

Encoding（编码）。每一列被存储为块的集合。每个块包含重复深度和定义深度（下文统称为深度）并且包含字段值。NULLs没有明确存储因为他们根据定义深度可以确定：任何定义深度小于重复和可选字段数量之和就意味着一个NULL。必须字段的值不需要存储定义深度。相似的，重复深度只在必要时存储；比如，定义深度0意味着重复深度0，所以后者可省略。事实上，图3中，没有为DocId存储深度。深度被打包为bit序列。我们只使用必需的位；比如，如果最大定义深度是3，我们只需使用2个bit。

【译者总结】这里又提到了块（block）等概念，其实论文应该简而言之——图3中那多张类似“表”的结构（长得很像一张Table，暂称其为“表”，无伤大雅），一张“表”就是一个column-stripe，就是块（block）集合，“表”中的每一行就是一个block，就是图1右边所示的列状存储。物理上像一张张独立的“表”，而逻辑上可以做到图1右部所示的树状、列状结构。在后面装配状态机算法一节中读者能对此有较深理解

【译者YY】读完原文章节后，这里YY一下上面提到的种种困惑

大家都知道任何的技术方案都不是空想出来的，肯定是因为某些痛处催生优化而得来的。译者尝试YY一下Dremel的推导过程：

step1. 首先，不考虑任何性能、优化，也不考虑分布式环境，只想要实现功能，最直接的做法就是按记录存储，比如把一个爬虫抓来的一个Document（如图2中的r1、r2），直接存储到一个GFS的文件中。查询时读取出必需的文件，解析为结构化数据，查询出结果。这样做肯定是能实现功能的，但是我们不会这么做，因为它的劣势十分明显——我只需要读取r1中的Name.URL信息，这里却需要把整条记录都读出来，无用数据远超过有效数据，是性能的极大浪费。（其实也就是论文中一直强调的面向记录存储的劣势）

step2. 第一步中失败就失败在存储时数据是非结构化的（存储时非结构化就意味着需要读取整条数据然后在内存中解析为结构化数据），那当前的优化目标就是做到在存储介质里数据就是结构化的（这样就可以按结构只读取出必要的数据）。不用想的太远，最经典的结构化存储就是众人皆知的关系型数据库，它的表、列、行、关联等概念足以在存储时就按实现数据结构化，而且同样能做到无损。对于嵌套型数据，关系型数据库也早有设计表结构的定式了（其实就是一系列一对多的表结构），以Name.Language.Country这样的路径为例，就三张表，Name、Language、Country，三表包含自己内部的required字段，同时包含父表的外键体现一对多的关联关系（Country表包含Language_id，Language表包含Name_id）。这样一个老掉牙的设计其实就能实现Dremel的一个重要目标——只读取必需的列。query要统计Country，就只需要遍历Country表，如果还要统计Language字段，那就是Language+Country两表join查询，一点不浪费（要知道Dremel查询过程中对一个column-stripe的遍历也是逃不掉的，就相当于这里遍历一张表了）。

第二步的YY有点不靠谱了，但是并没有跑题，如果不考虑通用性、不考虑为嵌套结构建表多么恶心（事实上利用动态schema将一个嵌套结构翻译成关系表也不是难事），也不考虑酷不酷，为什么不能这么做呢？但是答案还是不能，原因有二。Language+Country这个示例太简单了，假如是Name+Country的统计（比如统计Country是‘xxx’的Name有多少个），问题就暴露的很明显了，除了遍历Name、Country表，还需要涉及到Language表（从Country表只能得到关联的Language，需要三表join查询Name+Language+Country才能得到结果），这就违背了Dremel的目标（只遍历必需的表）。改变表设计是可以解决该问题——在Country表里增加对Name的外键关联。那就继续往极端情况去发散，假如Name之上还有一层呢？Country下面还有一层呢？这些层都可能会join查询呢？最终你会发现按照这个方向，你需要在所有的表里加上它所有祖先表的外键。不仅如此，上面曾经提到过为避免失真Dremel采用顺序化存储，顺序就相当于一条记录的主键，所有列值都要包含它，那就意味着在这个方案里各张表还要再加上record_id这个外键。这样一来已经足够令人无法直视了（光是冗余的外键存储就浪费了很大的空间）。第二个原因其实很简单，即使能动态schema、动态控制表结构，也不够通用，较难扩展，不适合通用数据分析平台。

step3. 经过上面对第二步的纠结，我们发现摆在面前的难题其实就是2个，一是要解决每张表上可能无穷无尽的外键，二是这个方案要足够通用化。再回过头看看Dremel最终采用的方案，也许你会发现它其实就是在第二步上做了两个天才的改良：第一，用重复深度+定义深度+顺序这三剑客取代所有外键；第二，表设计时不区分required、repeated等类型，一视同仁，都设计为字段值+重复深度+定义深度这样三列。对于第一个改良，我只能说这三剑客确实是神器，它们足够为任意两张“表”的数据建立关联关系（具体是如何做到请看下面4.3中的状态机算法），足以取代繁杂的外键；对于第二个改良，其实也是为了支持通用的结构和算法而妥协的结果，论文中不止一次的提到那两个深度并不是对所有字段都是必须的，比如DocId字段的r和d永远都是0（如果在关系型数据库中设计表的话DocId只会作为某张表的一个列而不是独立成为一张表）、所有字段非NULL的定义深度永远都相等，这些造成的些许浪费是为了通用化所付出的代价，但是问题不大，只要在存储、计算时稍作手脚就可以尽量避免浪费（上面encoding一节提到如何做手脚）。

上面3个step的推导看似毫无章法，其实是逻辑紧密的，代表了译者这样一个普通coder为了实现一个目标而不断反省优化的过程，并没有任何跳跃性的思维，除了step3中那两个改良，不是译者的YY水平所能驾驭的。我这里也妄自揣测一下，Google的天才们想出这样的方案可能是基于两条路线：一是对数据分析计算过程进行了高等级的抽象，建立了数学模型，帮助了推导过程（数学题的好处就是它大部分情况下是有解的）；另一种就是为了避免存储record_id、避免处理复杂的外键关联，得出按顺序存储、按顺序遍历的思路，通过在“顺序”二字上做足文章（各column-stripe中，记录间是按固定顺序的，那记录内也可以按由上而下的固定顺序，扫描时把“顺序”发挥到极致），推导出4.3中状态机算法的大概流程，剩下最后一道难题——面前只有一个字段值，没有任何外键（关联信息），仅仅知道它和其他字段值都是按严格顺序存储的，怎么能知道它属于哪条记录以及在记录内的确切位置？针对这一问题最终推导出重复深度和定义深度的概念（在4.1刚开头，作者就直接提出了摆在他面前的这最后一道难题去引读者入戏——“只有字段值不能表达清楚记录的结构……这些值是来自两个不同的记录，还是相同的记录中两个重复的值？……”）。但对于按部就班、接受不了跳跃性思维的译者来说，还是希望论文里能详细介绍这最后一道难题之前的推导过程的——为什么要按照列状结构、为什么把记录拆解的这么零散、无损表示的方法有很多种为何要选择这一种…… 所以才有如上YY，仅供读者参考和矫正。另外论文中曾经提到“列状存储已经证明了它适用于扁平的关系型数据”，这也是为什么译者会联想到基于关系型数据库遇到的问题进行推导。

4.2 分割记录为列状存储

上面我们展示了使用列状格式表达出记录结构并进行encoding。我们要面对的下一个挑战是如何高效率制造column-stripe以及重复和定义深度。计算重复和定义深度的基础的算法在Appendix A中给出。算法遍历记录结构然后计算每个列值的深度，为NULL时也不例外。在Google，经常会有一个schema包含了成千上万的字段，却只有几百个在记录中被使用。因此，我们需要尽可能廉价的处理缺失字段。为了制造column-stripe，我们创建一个树状结构，节点为字段的writer，它的结构与schema中的字段层级匹配。基础的想法是只在字段writer有自己的数据时执行更新，而不尝试往下传递父节点状态，除非绝对必要。子节点writer继承父节点的深度值。当任意值被添加时，一个子writer将深度值同步到父节点。

4.3 记录装配

【译者预读】遍历column-stripe时，面前是赤裸裸的字段值（比如‘en’）和两个int（重复深度、定义深度），没有任何的关联信息，怎么知道它属于哪条记录？处于记录内的什么位置？这就是本章节状态机算法要解决的问题。译者认为此算法的核心在于“顺序”二字，在没有任何关联信息的情况下，记录存储顺序就是record的主键，record内由上而下的字段顺序就是位置，而两个int就是判断顺序的唯一线索。

从列状数据高效的装配记录是很重要的。拿到一个字段的子集，我们的目标是重组原始记录就好像他们只包含选择的字段，其他列就当不存在。核心想法是：我们为每个字段创建一个有限状态机（FSM），读取字段值和深度，然后顺序的将值添加到输出结果上。一个字段的FSM状态对应这个字段的reader。重复深度驱动状态变迁。一旦一个reader获取了一个值，我们将查看下一个值的重复深度来决定状态如何变化、跳转到哪个reader。一个FSM状态变化的始终就是一条记录装配的全过程。

图4以Document为例，展示了一个FSM重组一条完整记录的过程。开始状态是DocId。一旦一个DocId值被读取，FSM转变到Links.Backward。获取完所有重复字段Backward的值，FSM跳向Links.Forward，依次类推。记录装配算法细节在Appendix B中。

【译者注】由于Appendix B的存在（原始论文中对核心算法都附带了源代码和解释，可在原文中查阅），这里对状态跳转的介绍过于简单，所以稍作补充。首先要确定3个思路：第一，所有数据都是按图3那种类似一张张“表”的形式存储的；第二，算法会结合schema，按照一定次序一张张的读取某些“表”（不是所有的，比如只统计Forward那就只会读取这一张“表”），次序是不固定的，这个次序也就是状态机内状态变迁的过程；第三，无论次序多么不固定，它都是按记录的顺序不断循环的（比如当前数据按顺序存储着r1,r2,r3… 那会进入第一个循环读取并装配出r1，第二个循环装配出r2…），一个循环就是一个状态机从开始到结束的生命周期。

通过对上面三点的思考，可以想到扫描过程中需要不断做一件非常重要的事情——扫描到某张“表”的某一行时要判断这一行是不是属于下一条记录了，如果是，那为了继续填充当前记录，就需要跳至下一张“表”继续扫描另一个字段值，否则就用此行的值装配当前记录，如此重复直到需要跳出最后一张“表”，一次循环结束（一个状态机结束，一条记录被装配完毕，进入下一个循环）。理解了这一点就能理解为何要用状态机来实现算法了，因为循环内就是不断进行状态判断的过程。再深入思考一下，可以想到这个判断不仅是简单的“是否属于下一条记录”，对于repeated字段的子孙字段，还需要判断是否属于同一个记录的下一个祖先、并且是哪个层级的祖先。举个例子：

比如当前正在装配r1中的某个Name的某个Language，扫描到了Name.Language.Country的某一行，如果此行重复深度为0，表示属于下一条记录，说明当前Name下Language不会再重复了（当前Name的所有Language装配完毕），于是跳至Name.Url继续装配其他属性；如果为1，表示属于r1的下一个Name，也说明当前Name下Language不会再重复（当前Name的所有Language装配完毕），那也跳到Name.Url；如果为2，表示属于当前Name的下一个Language（当前Name的Language还未装配完毕），那就走一个小循环，跳回上一个Name.Language.Code以装配当前Name的下一个Language。

示例还可以举更多，但重要的是从示例中抽象出状态变化的本质，下面一段是论文对该本质的简单描述

FSM的构造逻辑可以这么表示：设置r为当前字段读取器为字段f所返回的下一个重复深度。在schema树中，我们找到它在深度r的祖先，然后选择该祖先节点的第一个叶子字段n。这给了我们一个FSM状态变化(f;r)->n.比如，让r=1作为f=Name.Language.Country读取的下一个重复深度。它的祖先重复深度1的是Name，它的第一个叶子字段是n=Name.Url。FSM组装算法细节在Appendix C中。

如果只有一个字段子集需要被处理，FSM则更简单。图5描述了一个FSM，读取字段DocId和Name.Language.Country。图中展示了输出记录s1和s2。注意我们的encoding和装配算法保护了字段Country的封闭结构。这个对于应用访问过程很重要，比如，Country出现在第二个Name的第一个Language，在XPath中，就可以用此表达式访问：/Name[2]/Language[1]/Country.

（下文继续......）