文章/答案/技术大牛

发布

社区首页 >专栏 >孙荣辛｜大数据穿针引线进阶必看——带你盘点那些必知必会的Google经典大数据论文

孙荣辛｜大数据穿针引线进阶必看——带你盘点那些必知必会的Google经典大数据论文

laofo

发布于 2022-12-26 02:37:31

52700

代码可运行

文章被收录于专栏：研发效能EE研发效能EE

运行总次数：0

代码可运行

大数据技术的发展是一个非常典型的技术工程的发展过程，荣辛通过对于谷歌经典论文的盘点，希望可以帮助工程师们看到技术的探索、选择过程，以及最终历史告诉我们什么是正确的选择。

何为大数据

“大数据”这个名字流行起来到现在，差不多已经有十年时间了。在这十年里，不同的人都按照自己的需要给大数据编出了自己的解释。有些解释很具体，来自于一线写 Java 代码的工程师，说用 Hadoop 处理数据就是大数据；有些解释很高大上，来自于市场上靠发明大词儿为生的演说家，说我们能采集和处理全量的数据就是大数据，如果只能采集到部分数据，或者处理的时候要对数据进行采样，那就不是大数据。

在笔者看来，其实“大数据”技术的核心理念是非常清晰的，基本上可以被三个核心技术理念概括。

服务器规模：能够伸缩到一千台服务器以上的分布式数据处理集群的技术。
服务器架构：这个上千个节点的集群，是采用廉价的 PC 架构搭建起来的。
编程模式：“把数据中心当作是一台计算机”（Datacenter as a Computer）。

触发问题	大数据技术	传统数据处理技术	解决的问题
服务器规模	千台服务器以上	几十台服务器	可行性
服务器架构	普通x86服务器，普通硬盘	专用硬件，如大型机、小型机	性价比
编程模型	Datacenter as a Computer	使用方自己处理分布式和容错问题	复杂性

大型集群让处理海量数据变得“可能”；基于开放的 PC 架构，让处理海量数据变得“便宜”；而优秀的封装和抽象，则是让处理海量数据变得“容易”。这也是现在谁都能用上大数据技术的基础。可以说，这三个核心技术理念，真正引爆了整个“大数据”技术，让整个技术生态异常繁荣。

笔者认为，Google 能成为散播大数据火种的人，是有着历史的必然性的：作为一个搜索引擎，Google 在数据层面，面临着比任何一个互联网公司都更大的挑战。无论是 Amazon 这样的电商公司，还是 Yahoo 这样的门户网站，都只需要存储自己网站相关的数据。而 Google，则是需要抓取所有网站的网页数据并存下来。而且光存下来还不够，早在 1999 年，两个创始人就发表了 PageRank 的论文，也就是说，Google 不只是简单地根据网页里面的关键字来排序搜索结果，而是要通过网页之间的反向链接关系，进行很多轮的迭代计算，才能最终确认排序。而不断增长的搜索请求量，让 Google 还需要有响应迅速的在线服务。

三驾马车和基础设施

面对存储、计算和在线服务这三个需求，Google 就在 2003、2004 以及 2006 年，分别抛出了三篇重磅论文。也就是我们常说的“大数据”的三驾马车：GFS、MapReduce 和 Bigtable。

GFS 的论文发表于 2003 年，它主要是解决了数据的存储问题。作为一个上千节点的分布式文件系统，Google 可以把所有需要的数据都能很容易地存储下来。GFS它运行于廉价的普通硬件上，并提供容错功能，和以往的文件系统的不同，系统中部件错误不再被当作异常，而是将其作为常见的情况加以处理。其的新颖之处并不在于它采用了多么令人惊讶的新技术，而在于它采用廉价的商用计算机集群构建分布式文件系统，在降低成本的同时经受了实际应用的考验。

然后，光存下来还不够，我们还要基于这些数据进行各种计算。这个时候，就轮到 2004 年发表的 MapReduce 出场了。通过借鉴 Lisp，Google 利用简单的 Map 和 Reduce 两个函数，对于海量数据计算做了一次抽象，这就让“处理”数据的人，不再需要深入掌握分布式系统的开发了。而且他们推出的 PageRank 算法，也可以通过多轮的 MapReduce 的迭代来实现。MapReduce 解决了处理数据的问题，可以对数据进行各种计算。

这样，无论是 GFS 存储数据，还是 MapReduce 处理数据，系统的吞吐量都没有问题了，因为所有的数据都是顺序读写。但是这两个，其实都没有办法解决好数据的高性能随机读写问题。

因此，面对这个问题，2006 年发表的 Bigtable 就站上了历史舞台了。它是直接使用 GFS 作为底层存储，来做好集群的分片调度，以及利用 MemTable + SSTable 的底层存储格式，来解决大集群、机械硬盘下的高性能的随机读写问题。

到这里，GFS、MapReduce 和 Bigtable 这三驾马车的论文，就完成了“存储”、“计算”、“实时服务”这三个核心架构的设计。不过这三篇论文其实还依赖了两个基础设施。

保障数据一致性的分布式锁。对于这个问题，Google 在发表 Bigtable 的同一年，就发表了实现了 Paxos 算法的 Chubby 锁服务的论文。
数据怎么序列化以及分布式系统之间怎么通信。Google 在前面的论文里都没有提到这一点，但是Facebook 在 2007 年发表的 Thrift 的相关论文解决了相关问题。

实际上，Bigtable 的开源实现 HBase，就用了 Thrift 作为和外部多语言进行通信的协议。Twitter 也开源了 elephant-bird，使得 Hadoop 上的 MapReduce 可以方便地使用 Thrift 来进行数据的序列化。

OLAP 和 OLTP 数据库

可以说，Google这三驾马车是为整个业界带来了大数据的火种，但是整个大数据领域的进化才刚刚开始。

首先 MapReduce，作为一个“计算”引擎，在有着更大计算需求的背景下（OLAP），其开始朝着以下方式进化。

编程模型：MapReduce 的编程模型还是需要工程师去写程序的，所以它进化的方向就是通过一门 DSL，进一步降低写 MapReduce 的门槛。在这个领域的第一阶段最终胜出的，是 Facebook 在 2009 年发表的 Hive。Hive 通过一门基本上和 SQL 差不多的 HQL，大大降低了数据处理的门槛，从而成为了大数据数据仓库的事实标准；
执行引擎。Hive 虽然披上了一个 SQL 的皮，但是它的底层仍然是一个个的 MapReduce 的任务，所以延时很高，没法当成一个交互式系统来给数据分析师使用。于是 Google 又在 2010 年，发表了 Dremel 这个交互式查询引擎的论文，采用数据列存储 + 并行数据库的方式。这样一来，Dremel 不仅有了一个 SQL 的皮，还进一步把 MapReduce 这个执行引擎给替换掉了。
多轮迭代问题：在 MapReduce 这个模型里，一个 MapReduce 就要读写一次硬盘，这对硬盘是无比大的负担。2010年的Spark论文，通过把数据放在内存而不是硬盘里，大大提升了分布式数据计算性能。

围绕 MapReduce，整个技术圈都在不断优化和迭代计算性能，Hive、Dremel 和 Spark 分别从“更容易写程序”，“查询响应更快”，“更快的单轮和多轮迭代”的角度，完成了对 MapReduce 的彻底进化。

作为一个“在线服务”的数据库，Bigtable 的进化是这样的：

事务问题和 Schema 问题：Google 先是在 2011 年发表了 Megastore 的论文，在 Bigtable 之上，实现了类 SQL 的接口，提供了 Schema，以及简单的跨行事务。如果说 Bigtable 为了伸缩性，放弃了关系型数据库的种种特性。那么 Megastore 就是开始在 Bigtable 上逐步弥补关系型数据库的特性。
异地多活和跨数据中心问题：Google 在 2012 年发表的 Spanner，能够做到“全局一致性”。这样，就算是基本解决了这两个问题，第一次让我们有一个“全球数据库”。

本质上说，MapReduce 的迭代是在不断优化OLAP类型的数据处理性能，而Bigtable的进化，则是在保障伸缩性的前提下，获得了更多的关系型数据库的能力。

实时数据处理的抽象进化

从 MapReduce 到 Dremel，我们查询数据的响应时间就大大缩短了。但是计算的数据仍然是固定的、预先确定的数据，这样系统往往有着大到数小时、小到几分钟的数据延时。所以，为了解决好这个问题，流式数据处理就走上了舞台。

首先是 Yahoo 在 2010 年发表了 S4 的论文并将其开源。而几乎是在同一时间，Twitter 工程师南森·马茨（Nathan Marz）以一己之力开源了 Storm，并且在很长一段时间成为了工业界的事实标准。和 GFS 一样，Storm 还支持“至少一次”（At-Least-Once）的数据处理。另外，基于 Storm 和 MapReduce，南森更是提出了 Lambda 架构，它可以称之为是第一个流批协同的大数据处理架构。

接着在 2011 年，Kafka的论文也发表了。最早的 Kafka 其实只是一个“消息队列”，但是由于 Kafka 里发送的消息可以做到“正好一次”（Exactly-Once），所以大家就动起了在上面直接解决 Storm 解决不好的消息重复问题的念头。于是，Kafka 逐步进化出了 Kafka Streams 这样的实时数据处理方案。而后在 2014 年，Kafka 的作者 Jay Krepson 提出了 Kappa 架构，这个可以被称之为第一代“流批一体”的大数据处理架构。

在大数据的流式处理领域似乎没有 Google 什么事儿，但是在 2015 年，Google 发表的 Dataflow 的模型，可以说是对于流式数据处理模型做出了最好的总结和抽象。一直到现在，Dataflow 就成为了真正的“流批一体”的大数据处理架构。而后来开源的 Flink 和 Apache Beam，则是完全按照 Dataflow 的模型实现的了。

一致性与调度

到了现在，随着“大数据领域”本身的高速发展，数据中心里面的服务器越来越多，我们对于数据一致性的要求也越来越高。为了解决一致性问题，我们就有了基于 Paxos 协议的分布式锁。但是 Paxos 协议的性能很差，于是有了进一步的 Multi-Paxos 协议。可惜的是Paxos 协议并不容易理解，于是就有了 Raft 这个更容易理解的算法的出现。Kubernetes 依赖的 etcd 就是用 Raft 协议实现的。

也正是因为数据中心里面的服务器越来越多，我们会发现原有的系统部署方式越来越浪费。当我们有数百乃至数千台服务器的时候，浪费的硬件和电力成本就成为不能承受之重了。于是，尽可能用满硬件资源成为了刚需。由此一来，我们对于整个分布式系统的视角，也从虚拟机转向了容器，这也是 Kubernetes 这个系统的由来。其从更加全面的角度来进行资源管理和调度系统。

争论与分歧

到此为止，笔者为大家简单地介绍了大数据技术的论文演进的脉络。但是整个技术的发展也并不是一个直线上升的状态:

有争论，比如 MapReduce 的论文发表之后，数据库领域知名的科学家大卫·德维特（David DeWitt）就发表过一篇论文“MapReduce：A major step backwards”，抨击 MapReduce 相比于并行数据库是一种倒退；
有妥协，比如，Bigtable 不支持跨行事务也不支持 SQL，就是一个明证。直到 5 年后发表的 Megastore，他们才开始着手解决这两个问题；
更有不成功的尝试，典型的就是 Sawzall 和 Pig，Google 在发表 MapReduce 论文之前，就发表了 Sawzall 这个用来撰写 MapReduce 任务的 DSL，Yahoo 也很早就完成了对应的开源实现 Apache Pig。但是 10 年后的今天，我们的主流选择是用 SQL 或者 DataFrame，Pig 的用户已经不多了，而 Sawzall 也没有再听 Google 提起过。所以可以说，大数据技术的发展是一个非常典型的技术工程的发展过程，跟随这个脉络，我们可以看到工程师们对于技术的探索、选择过程，以及最终历史告诉我们什么是正确的选择。

大数据技术盘点

相比于某一门计算机课程、某一门编程语言或者某一个开源框架，“大数据”涉及到的知识点多而繁杂。所以这里，笔者就整理了一份知识地图，好让读者可以对论文中提到的知识点有迹可循。

分布式系统

所有的大数据系统都是分布式系统。我们需要大数据系统，就是因为普通的单机已经无法满足我们期望的性能了。那么作为一个分布式的数据系统，它就需要满足三个特性：可靠性、可扩展性和可维护性。

可靠性：如果只记录一份数据，那么当硬件故障的时候就会遇到丢数据的问题，所以我们需要对数据做复制。而数据复制之后，以哪一份数据为准，又给我们带来了主从架构、多主架构以及无主架构的选择。在最常见的主从架构里，根据复制过程，可以有同步复制和异步复制之分。同步复制的节点可以作为高可用切换的 Backup Master，而异步复制的节点只适合作为只读的 Shadow Master。
可扩展性：在“大数据”的场景下，单个节点存不下所有数据，于是就有了数据分区。常见的分区方式有两种，第一种是通过区间进行分片，典型的代表就是 Bigtable，第二种是通过哈希进行分区，在大型分布式系统中常用的是一致性 Hash，典型的代表是 Cassandra。
可维护性。我们需要考虑容错，在硬件出现故障的时候系统仍然能够运作。我们还需要考虑恢复，也就是当系统出现故障的时候，仍能快速恢复到可以使用的状态。而为了确保我们不会因为部分网络的中断导致作出错误的判断，我们就需要利用共识算法，来确保系统中能够对哪个节点正在正常服务作出判断。这也就引出了 CAP 这个所谓的“不可能三角”。分布式系统的核心问题就是 CAP 这个不可能三角，我们需要在一致性、可用性和分区容错性之间做权衡和选择。因此，我们选择的主从架构、复制策略、分片策略，以及容错和恢复方案，都是根据我们实际的应用场景下对于 CAP 进行的权衡和选择。

存储引擎

上万台的分布式集群，最终还是要落到每一台单个服务器上完成数据的读写。那么在存储引擎上，关键的技术点主要包括三个部分。

事务。在传统的数据库领域，我们有 ACID 这样的事务特性即原子性（Atomic）、一致性（Consistency）、隔离性（Isolation）以及持久性（Durability）。而在大数据领域，很多时候因为分布式的存在，事务常常会退化到 BASE 的模型，即表基本可用（Basically Available）、软状态（Soft State）以及最终一致性（Eventually Consistent）。不过无论是 ACID 还是 BASE，在单机上，我们都会使用预写日志（WAL）、快照（Snapshot）和检查点（Checkpoints）以及写时复制（Copy-on-Write）这些技术，来保障数据在单个节点的写入是原子的。而只要写入的数据记录是在单个分片上，我们就可以保障数据写入的事务性，所以我们很容易可以做到单行事务，或者是进一步的实体组（Entity Group）层面的事务。
写入和存储。这个既要考虑到计算机硬件的特性，比如数据的顺序读写比随机读写快，在内存上读写比硬盘上快；也要考虑到我们在算法和数据结构中的时空复杂度，比如 Hash 表的时间复杂度是 O(1)，B+ 树的时间复杂度是 O(logN)。这样，通过结合硬件性能、数据结构和算法特性，我们会看到分布式数据库最常使用的，其实是基于 LSM 树（Log-Structured Merge Tree）的 MemTable+SSTable 的解决方案。
数据的序列化。出于存储空间和兼容性的考虑，我们会选用 Thrift 这样的二进制序列化方案。而为了在分析数据的时候尽量减少硬盘吞吐量，我们则要研究 Parquet 或者 ORCFile 这样的列存储格式。然后，为了在 CPU、网络和硬盘的使用上取得平衡，我们又会选择 Snappy 或者 LZO 这样的快速压缩算法。

计算引擎

计算的维度实际上也是大数据领域本身进化和迭代最快的一部分。

起初，最原始粗糙的 MapReduce 来进行批数据处理，然后围绕它不断迭代出了让数据处理更快的 Spark 和让数据处理更容易的各种 DSL（比如Hive）。
然后，围绕着实时数据处理，有了“最少一次”的 S4/Storm，并把它和批处理综合到一起，产生了著名的 Lambda 架构。
紧接着有了“以批为流”，通过 Mini-Batch 来进行实时数据处理的 Spark Streaming，以及“流批一体”，能够做到“正好一次”的 Kafka 和 Kappa 结构。
最后，还是 Google 一锤定音，给出了统一的 Dataflow 模型，并伴随着有了 Apache Flink 和 Apache Beam 这两个开源项目。

随着 Dataflow 论文的发表，整个大数据的处理引擎逐渐收敛成了一个统一的模型，这是大数据领域发展的一个新的里程碑。

经典文章总结

最后，笔者把文中提到的这些论文的前后之间的脉络联系专门做了一张图，放在了下面。如果读者对某一篇论文感到困惑的时候，就可以去翻看它前后对应的论文，找到对应问题的来龙去脉。

同时笔者把在文中提到的论文清单列在了下面，供读者作为一个索引。另外，如果有读者觉得本文的内还不够过瘾，笔者强烈推荐你可以读一下 Big Data: A Survey 这篇综述文章，可以让读者更加深入“大数据”技术的全貌。

有的读者可能担心如何找到和下载这些论文。笔者已经贴心的为大家收集好了全部论文并上传到云盘中，只要点击下方连接，即可获得全套经典论文。

# 百度网盘
链接: https://pan.baidu.com/share/init?surl=h9eoDbgIYZMeQKb1zDAPOw
提取码: 4mei

其它相关

izx 问题：

这文章有几个问题，一个关于序列化和服务间通信的问题，protobuf/grpc是事实标准，thrift在grpc出现以后用的人就少了。另外，Bigtable不支持跨行事务按当时的场景也的确不需要，Google在跨行事务上是通过Percolator来解决的。

荣辛：高质量的回复，很好的补充!

1. 今日而言，如果新项目选择rpc，grpc绝对是比thrift更合适的选择。但Hadoop和HBase 又在使用thrift 和外部交互，要深入了解这些技术，thrift暂时还没法绕开 2. BigTable不支持跨行事务，但Megastore已经在EntityGroup层面支持，到Spanner已经完全支持了。我的表述目的是在于这个演进的过程 3. Percolator个人感觉在学术和搜索引擎的索引更相关一些，本人水平有限，篇幅有限，就没有讲到。有兴趣的读者欢迎参考 https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Peng.pdf

izx：