大数据技术的发展是一个非常典型的技术工程的发展过程，荣辛通过对于谷歌经典论文的盘点，希望可以帮助工程师们看到技术的探索、选择过程，以及最终历史告诉我们什么是正确的选择。#研发效能#
何为大数据
“大数据”这个名字流行起来到现在，差不多已经有十年时间了。在这十年里，不同的人都按照自己的需要给大数据编出了自己的解释。有些解释很具体，来自于一线写Java代码的工程师，说用Hadoop处理数据就是大数据；有些解释很高大上，来自于市场上靠发明大词儿为生的演说家，说我们能采集和处理全量的数据就是大数据，如果只能采集到部分数据，或者处理的时候要对数据进行采样，那就不是大数据。
在笔者看来，其实“大数据”技术的核心理念是非常清晰的，基本上可以被三个核心技术理念概括。
服务器规模：能够伸缩到一千台服务器以上的分布式数据处理集群的技术。
服务器架构：这个上千个节点的集群，是采用廉价的PC架构搭建起来的。
编程模式：“把数据中心当作是一台计算机”（DatacenterasaComputer）。
大型集群让处理海量数据变得“可能”；基于开放的PC架构，让处理海量数据变得“便宜”；而优秀的封装和抽象，则是让处理海量数据变得“容易”。这也是现在谁都能用上大数据技术的基础。可以说，这三个核心技术理念，真正引爆了整个“大数据”技术，让整个技术生态异常繁荣。
笔者认为，Google能成为散播大数据火种的人，是有着历史的必然性的：作为一个搜索引擎，Google在数据层面，面临着比任何一个互联网公司都更大的挑战。无论是Amazon这样的电商公司，还是Yahoo这样的门户网站，都只需要存储自己网站相关的数据。而Google，则是需要抓取所有网站的网页数据并存下来。而且光存下来还不够，早在年，两个创始人就发表了PageRank的论文，也就是说，Google不只是简单地根据网页里面的关键字来排序搜索结果，而是要通过网页之间的反向链接关系，进行很多轮的迭代计算，才能最终确认排序。而不断增长的搜索请求量，让Google还需要有响应迅速的在线服务。
三驾马车和基础设施
面对存储、计算和在线服务这三个需求，Google就在、以及年，分别抛出了三篇重磅论文。也就是我们常说的“大数据”的三驾马车：GFS、MapReduce和Bigtable。
GFS的论文发表于年，它主要是解决了数据的存储问题。作为一个上千节点的分布式文件系统，Google可以把所有需要的数据都能很容易地存储下来。GFS它运行于廉价的普通硬件上，并提供容错功能，和以往的文件系统的不同，系统中部件错误不再被当作异常，而是将其作为常见的情况加以处理。其的新颖之处并不在于它采用了多么令人惊讶的新技术，而在于它采用廉价的商用计算机集群构建分布式文件系统，在降低成本的同时经受了实际应用的考验。
然后，光存下来还不够，我们还要基于这些数据进行各种计算。这个时候，就轮到年发表的MapReduce出场了。通过借鉴Lisp，Google利用简单的Map和Reduce两个函数，对于海量数据计算做了一次抽象，这就让“处理”数据的人，不再需要深入掌握分布式系统的开发了。而且他们推出的PageRank算法，也可以通过多轮的MapReduce的迭代来实现。MapReduce解决了处理数据的问题，可以对数据进行各种计算。
这样，无论是GFS存储数据，还是MapReduce处理数据，系统的吞吐量都没有问题了，因为所有的数据都是顺序读写。但是这两个，其实都没有办法解决好数据的高性能随机读写问题。
因此，面对这个问题，年发表的Bigtable就站上了历史舞台了。它是直接使用GFS作为底层存储，来做好集群的分片调度，以及利用MemTable+SSTable的底层存储格式，来解决大集群、机械硬盘下的高性能的随机读写问题。
到这里，GFS、MapReduce和Bigtable这三驾马车的论文，就完成了“存储”、“计算”、“实时服务”这三个核心架构的设计。不过这三篇论文其实还依赖了两个基础设施。
保障数据一致性的分布式锁。对于这个问题，Google在发表Bigtable的同一年，就发表了实现了Paxos算法的Chubby锁服务的论文。
数据怎么序列化以及分布式系统之间怎么通信。Google在前面的论文里都没有提到这一点，但是Facebook在年发表的Thrift的相关论文解决了相关问题。
实际上，Bigtable的开源实现HBase，就用了Thrift作为和外部多语言进行通信的协议。Twitter也开源了elephant-bird，使得Hadoop上的MapReduce可以方便地使用Thrift来进行数据的序列化。
OLAP和OLTP数据库
可以说，Google这三驾马车是为整个业界带来了大数据的火种，但是整个大数据领域的进化才刚刚开始。
首先MapReduce，作为一个“计算”引擎，在有着更大计算需求的背景下（OLAP），其开始朝着以下方式进化。
编程模型：MapReduce的编程模型还是需要工程师去写程序的，所以它进化的方向就是通过一门DSL，进一步降低写MapReduce的门槛。在这个领域的第一阶段最终胜出的，是Facebook在年发表的Hive。Hive通过一门基本上和SQL差不多的HQL，大大降低了数据处理的门槛，从而成为了大数据数据仓库的事实标准；
执行引擎。Hive虽然披上了一个SQL的皮，但是它的底层仍然是一个个的MapReduce的任务，所以延时很高，没法当成一个交互式系统来给数据分析师使用。于是Google又在年，发表了Dremel这个交互式查询引擎的论文，采用数据列存储+并行数据库的方式。这样一来，Dremel不仅有了一个SQL的皮，还进一步把MapReduce这个执行引擎给替换掉了。
多轮迭代问题：在MapReduce这个模型里，一个MapReduce就要读写一次硬盘，这对硬盘是无比大的负担。年的Spark论文，通过把数据放在内存而不是硬盘里，大大提升了分布式数据计算性能。
围绕MapReduce，整个技术圈都在不断优化和迭代计算性能，Hive、Dremel和Spark分别从“更容易写程序”，“查询响应更快”，“更快的单轮和多轮迭代”的角度，完成了对MapReduce的彻底进化。
作为一个“在线服务”的数据库，Bigtable的进化是这样的：
事务问题和Schema问题：Google先是在年发表了Megastore的论文，在Bigtable之上，实现了类SQL的接口，提供了Schema，以及简单的跨行事务。如果说Bigtable为了伸缩性，放弃了关系型数据库的种种特性。那么Megastore就是开始在Bigtable上逐步弥补关系型数据库的特性。
异地多活和跨数据中心问题：Google在年发表的Spanner，能够做到“全局一致性”。这样，就算是基本解决了这两个问题，第一次让我们有一个“全球数据库”。
本质上说，MapReduce的迭代是在不断优化OLAP类型的数据处理性能，而Bigtable的进化，则是在保障伸缩性的前提下，获得了更多的关系型数据库的能力。
实时数据处理的抽象进化
从MapReduce到Dremel，我们查询数据的响应时间就大大缩短了。但是计算的数据仍然是固定的、预先确定的数据，这样系统往往有着大到数小时、小到几分钟的数据延时。所以，为了解决好这个问题，流式数据处理就走上了舞台。
首先是Yahoo在年发表了S4的论文并将其开源。而几乎是在同一时间，Twitter工程师南森·马茨（NathanMarz）以一己之力开源了Storm，并且在很长一段时间成为了工业界的事实标准。和GFS一样，Storm还支持“至少一次”（At-Least-Once）的数据处理。另外，基于Storm和MapReduce，南森更是提出了Lambda架构，它可以称之为是第一个**“流批协同”**的大数据处理架构。
接着在年，Kafka的论文也发表了。最早的Kafka其实只是一个“消息队列”，但是由于Kafka里发送的消息可以做到“正好一次”（Exactly-Once），所以大家就动起了在上面直接解决Storm解决不好的消息重复问题的念头。于是，Kafka逐步进化出了KafkaStreams这样的实时数据处理方案。而后在年，Kafka的作者JayKrepson提出了Kappa架构，这个可以被称之为第一代“流批一体”的大数据处理架构。
在大数据的流式处理领域似乎没有Google什么事儿，但是在年，Google发表的Dataflow的模型，可以说是对于流式数据处理模型做出了最好的总结和抽象。一直到现在，Dataflow就成为了真正的“流批一体”的大数据处理架构。而后来开源的Flink和ApacheBeam，则是完全按照Dataflow的模型实现的了。
一致性与调度
到了现在，随着“大数据领域”本身的高速发展，数据中心里面的服务器越来越多，我们对于数据一致性的要求也越来越高。为了解决一致性问题，我们就有了基于Paxos协议的分布式锁。但是Paxos协议的性能很差，于是有了进一步的Multi-Paxos协议。可惜的是Paxos协议并不容易理解，于是就有了Raft这个更容易理解的算法的出现。Kubernetes依赖的etcd就是用Raft协议实现的。
也正是因为数据中心里面的服务器越来越多，我们会发现原有的系统部署方式越来越浪费。当我们有数百乃至数千台服务器的时候，浪费的硬件和电力成本就成为不能承受之重了。于是，尽可能用满硬件资源成为了刚需。由此一来，我们对于整个分布式系统的视角，也从虚拟机转向了容器，这也是Kubernetes这个系统的由来。其从更加全面的角度来进行资源管理和调度系统。
争论与分歧
到此为止，笔者为大家简单地介绍了大数据技术的论文演进的脉络。但是整个技术的发展也并不是一个直线上升的状态:
有争论，比如MapReduce的论文发表之后，数据库领域知名的科学家大卫·德维特（DavidDeWitt）就发表过一篇论文“MapReduce：Amajorstepbackwards”，抨击MapReduce相比于并行数据库是一种倒退；
有妥协，比如，Bigtable不支持跨行事务也不支持SQL，就是一个明证。直到5年后发表的Megastore，他们才开始着手解决这两个问题；
更有不成功的尝试，典型的就是Sawzall和Pig，Google在发表MapReduce论文之前，就发表了Sawzall这个用来撰写MapReduce任务的DSL，Yahoo也很早就完成了对应的开源实现ApachePig。但是10年后的今天，我们的主流选择是用SQL或者DataFrame，Pig的用户已经不多了，而Sawzall也没有再听Google提起过。
所以可以说，大数据技术的发展是一个非常典型的技术工程的发展过程，跟随这个脉络，我们可以看到工程师们对于技术的探索、选择过程，以及最终历史告诉我们什么是正确的选择。
大数据技术盘点
相比于某一门计算机课程、某一门编程语言或者某一个开源框架，“大数据”涉及到的知识点多而繁杂。所以这里，笔者就整理了一份知识地图，好让读者可以对论文中提到的知识点有迹可循。
分布式系统
所有的大数据系统都是分布式系统。我们需要大数据系统，就是因为普通的单机已经无法满足我们期望的性能了。那么作为一个分布式的数据系统，它就需要满足三个特性：可靠性、可扩展性和可维护性。
可靠性：如果只记录一份数据，那么当硬件故障的时候就会遇到丢数据的问题，所以我们需要对数据做复制。而数据复制之后，以哪一份数据为准，又给我们带来了主从架构、多主架构以及无主架构的选择。在最常见的主从架构里，根据复制过程，可以有同步复制和异步复制之分。同步复制的节点可以作为高可用切换的BackupMaster，而异步复制的节点只适合作为只读的ShadowMaster。
可扩展性：在“大数据”的场景下，单个节点存不下所有数据，于是就有了数据分区。常见的分区方式有两种，第一种是通过区间进行分片，典型的代表就是Bigtable，第二种是通过哈希进行分区，在大型分布式系统中常用的是一致性Hash，典型的代表是Cassandra。
可维护性。我们需要考虑容错，在硬件出现故障的时候系统仍然能够运作。我们还需要考虑恢复，也就是当系统出现故障的时候，仍能快速恢复到可以使用的状态。而为了确保我们不会因为部分网络的中断导致作出错误的判断，我们就需要利用共识算法，来确保系统中能够对哪个节点正在正常服务作出判断。这也就引出了CAP这个所谓的“不可能三角”。
分布式系统的核心问题就是CAP这个不可能三角，我们需要在一致性、可用性和分区容错性之间做权衡和选择。因此，我们选择的主从架构、复制策略、分片策略，以及容错和恢复方案，都是根据我们实际的应用场景下对于CAP进行的权衡和选择。
存储引擎
上万台的分布式集群，最终还是要落到每一台单个服务器上完成数据的读写。那么在存储引擎上，关键的技术点主要包括三个部分。
事务。在传统的数据库领域，我们有ACID这样的事务特性即原子性（Atomic）、一致性（Consistency）、隔离性（Isolation）以及持久性（Durability）。而在大数据领域，很多时候因为分布式的存在，事务常常会退化到BASE的模型，即表基本可用（BasicallyAvailable）、软状态（SoftState）以及最终一致性（EventuallyConsistent）。不过无论是ACID还是BASE，在单机上，我们都会使用预写日志（WAL）、快照（Snapshot）和检查点（Checkpoints）以及写时复制（Copy-on-Write）这些技术，来保障数据在单个节点的写入是原子的。而只要写入的数据记录是在单个分片上，我们就可以保障数据写入的事务性，所以我们很容易可以做到单行事务，或者是进一步的实体组（EntityGroup）层面的事务。
写入和存储。这个既要考虑到计算机硬件的特性，比如数据的顺序读写比随机读写快，在内存上读写比硬盘上快；也要考虑到我们在算法和数据结构中的时空复杂度，比如Hash表的时间复杂度是O(1)，B+树的时间复杂度是O(logN)。这样，通过结合硬件性能、数据结构和算法特性，我们会看到分布式数据库最常使用的，其实是基于LSM树（Log-StructuredMergeTree）的MemTable+SSTable的解决方案。
数据的序列化。出于存储空间和兼容性的考虑，我们会选用Thrift这样的二进制序列化方案。而为了在分析数据的时候尽量减少硬盘吞吐量，我们则要研究Parquet或者ORCFile这样的列存储格式。然后，为了在CPU、网络和硬盘的使用上取得平衡，我们又会选择Snappy或者LZO这样的快速压缩算法。
计算引擎
计算的维度实际上也是大数据领域本身进化和迭代最快的一部分。
起初，最原始粗糙的MapReduce来进行批数据处理，然后围绕它不断迭代出了让数据处理更快的Spark和让数据处理更容易的各种DSL（比如Hive）。
然后，围绕着实时数据处理，有了“最少一次”的S4/Storm，并把它和批处理综合到一起，产生了著名的Lambda架构。
紧接着有了“以批为流”，通过Mini-Batch来进行实时数据处理的SparkStreaming，以及“流批一体”，能够做到“正好一次”的Kafka和Kappa结构。
最后，还是Google一锤定音，给出了统一的Dataflow模型，并伴随着有了ApacheFlink和ApacheBeam这两个开源项目。
随着Dataflow论文的发表，整个大数据的处理引擎逐渐收敛成了一个统一的模型，这是大数据领域发展的一个新的里程碑。
经典文章总结
最后，笔者把文中提到的这些论文的前后之间的脉络联系专门做了一张图，放在了下面。如果读者对某一篇论文感到困惑的时候，就可以去翻看它前后对应的论文，找到对应问题的来龙去脉。
同时笔者把在文中提到的论文清单列在了下面，供读者作为一个索引。另外，如果有读者觉得本文的内还不够过瘾，笔者强烈推荐你可以读一下BigData:ASurvey这篇综述文章，可以让读者更加深入“大数据”技术的全貌。
有的读者可能担心如何找到和下载这些论文。笔者已经贴心的为大家收集好了全部论文并上传到云盘中，只要点击下方连接，即可获得全套经典论文。
#百度网盘链接: